Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.

ЛИЧНЫЙ КАБИНЕТВ  Здравствуйте гость! В  Логин : Пароль : В  Запомнить В  В  Забыли пароль? Регистрация В

Поиск учебного материала на сайте Предмет: Название:

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.

Ответы Поясните сущность явления вязкого трения. Какова природа сил внутреннего трения жидкости? Информация: Тип работы: Ответы. Предмет: Физика. Добавлен: 14.12.2017. Год: 2017. Страниц: 4. Уникальность по antiplagiat.ru: < 30% Описание (план):

ГлавнаяКоллекция “Revolution”Программирование, компьютеры и кибернетикаПрименение алгебры логики в информатике

Основные понятия алгебры логики, её применение в информатике. Решение задачи с расчетом стоимости стеклопакетов. Информационная и аналитическая модель задачи, технология решения задачи в MS Excel. Результаты компьютерного эксперимента и их анализ.

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	22.01.2015
Размер файла	44,7В K

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.PPT, PPTX и PDF-файлы представлены только в архивах.Рекомендуем скачать работу.

• Главная
• Справочник
• Информатика
• Основы
• Логические основы компьютеров

• Логика – это наука о том, как правильно рассуждать, делать выводы, доказывать утверждения.
• Формальная логика отвлекается от конкретного содержания, изучает только истинность и ложность высказываний.
• Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.
• Алгебра логики – это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразуют логические высказывания.
• Логическая функция – правила преобразования входных логических значений в выходные.
• Операция “И” – Логическое умножение – коньюнкция (союз, связь).Результат: истина когда выбирается минимальное из исходных значений.
• Операция “ИЛИ” – Логическое сложение – дизьюнкция (разделение).Результат: истина когда из исходных значений выбирается наибольшее.
• Операция Исключающее ИЛИ – разделительная дизъюнкция – “один или другой, но не оба вместе” – сложение по модулю два.Результат: Истина в том и только в том случае, когда два значения не равны.
• Операция Импликация (следование) – логическая связка “если … , то”.
• Операция Эквивалентность (или эквиваленция, равносильность) – это логическая операция, которая соответсвует связке “тогда и только тогда”.

Порядок выполнения логических операций:

1. действия в скобках
2. отрицание (НЕ)
3. логическое умножение (И)
4. логическое сложение (ИЛИ) и оперция “исключающее ИЛИ”
5. импликация (следование)
6. эквивалентность

• Формализация – это переход от конкретного содержания к формальной записи с помощью некоторого языка.
• Унарные (лат. uno – один) или одноместные операции – операции, которые выполняются над одной величиной.
• Бинарные (лат. bis – дважды) операции – операции, которые выполняются над двумя значениями.
• Выражения тождественно равны или равносильны если два выражения принимают одинаковые значения при всех значениях переменных
• Диаграммы Венна или круги Эйлера – выражения, зависящие от небольшого количества переменных (обычно не более четырёх).
• Предикат (от лат. praedicatum – заявленное, упомянутое, сказанное) – это утверждение, содержащее переменные.
• Квантор (от лат. quantum – сколько) – это знак или выражение, обозначающее количество.
• Триггер – электронная схема, которая может находиться только в двух состояниях (их можно обозначить как 0 и 1) и способна почти мгновенно переходить из одного состояния в другое.
• RS-триггер имеет два входа, которые обозначаются как S (англ. set – установить) и R (англ. reset – сброс), и два выхода Q и Q, причём выходной сигнал Q является логическим отрицанием сигнала Q (если Q = 1, то Q = 0, и наоборот).
• Полусумматор выполняет сложение двух бит с учетом того, что в результате может получится двухразрядное число (с переносом в следующий разряд).

Больше интересного в телеграм @calcsboxНазначение сервиса. Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения. Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе. Таблица истинности содержит 2ⁿ строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные. Инструкция. При вводе с клавиатуры используйте следующие обозначения:

Клавиша	Оператор
!	В¬	Отрицание (НЕ)
|	|	Штрих Шеффера (И-НЕ)
#	↓	Стрелка Пирса (ИЛИ-НЕ)
*	&	Конъюнкция (И)
+	v	Дизъюнкция (ИЛИ)
^	вЉ•	Исключающее ИЛИ, сумма по модулю 2 (XOR)
@	в†’	Импликация (ЕСЛИ-ТО)
%	в†ђ	Обратная импликация
=	в‰Ў (~, ↔)	Эквивалентность (РАВНО)

Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*cДля ввода данных в виде логической схемы используйте этот сервис. Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики – алгебры логики. В алгебре логики можно выделить три основные логические функции: “НЕ” (отрицание), “И” (конъюнкция), “ИЛИ” (дизъюнкция). Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики. Функция алгебры логики называется полностью определённой если заданы все 2ⁿ её значения, где n – число выходных переменных. Если определены не все значения, функция называется частично определённой. Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики. Для представления функции алгебры логики используется следующие способы:

• словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
• описание функции алгебры логики в виде таблицы истинности.
• описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ: а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу: 1) в таблице выбираются те строки переменных для которых функция на выходе =1. 2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией. 3) полученное произведение логически суммируется. Fднф= X₁*Х₂*Х₃ в€Ё Х₁x₂Х₃ в€Ё Х₁Х₂x₃ в€Ё Х₁Х₂Х₃ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде. б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм. КНФ может быть получена из таблицы истинности по следующему алгоритму: 1) выбираем наборы переменных для которых функция на выходе =02) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией. 3) логически перемножаются полученные суммы. Fскнф=(X₁ V X₂ V X₃) ∧ (X₁ V X₂ V X₃) ∧ (X₁ V X₂ V X₃) ∧ (X₁ V X₂ V X₃) КНФ называется совершенной, если все переменные имеют одинаковый ранг.

По алгебраической форме можно построить схему логического устройства, используя логические элементы. Рисунок1- Схема логического устройства

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2^N строк, так как существует 2^N различных комбинаций возможных значений аргументов.

Операция НЕ — логическое отрицание (инверсия)

Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Для операции отрицания НЕ приняты следующие условные обозначения: не А, ДЂ, not A, ¬А, !A Результат операции отрицания НЕ определяется следующей таблицей истинности:

A	не А
1
1

Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

Операция ИЛИ — логическое сложение (дизъюнкция, объединение)

Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений. Применяемые обозначения: А или В, А V В, A or B, A||B. Результат операции ИЛИ определяется следующей таблицей истинности:

A	B	А или B
1	1
1	1
1	1	1

Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.

Операция И — логическое умножение (конъюнкция)

Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения. Применяемые обозначения: А и В, А О› В, A & B, A and B. Результат операции И определяется следующей таблицей истинности:

A	B	А и B
1
1
1	1	1

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

Операция «ЕСЛИ-ТО» — логическое следование (импликация)

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия. Применяемые обозначения: если А, то В; А влечет В; if A then В; Ав†’ В. Таблица истинности:

A	B	А в†’ B
1
1	1
1
1	1	1

Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Применяемое обозначение: А ↔ В, А ~ В. Таблица истинности:

A	B	А↔B
1
1
1
1	1	1

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Применяемое обозначение: А XOR В, А вЉ• В. Таблица истинности:

A	B	АвЉ•B
1	1
1	1
1	1

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Приоритет логических операций

• Действия в скобках
• Инверсия
• Конъюнкция ( & )
• Дизъюнкция ( V ), Исключающее ИЛИ (XOR), сумма по модулю 2
• Импликация ( в†’ )
• Эквивалентность ( ↔ )

Совершенная дизъюнктивная нормальная форма

Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x₁,x₂,…x_n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

СДНФ можно получить или с помощью таблиц истинности или с помощью равносильных преобразований. Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.

Совершенная конъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:

1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x₁,x₂,…x_n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

Электронное приложение к учебному пособию «Информатика» авторов В. М. Котова, А. И. Лапо, Е. Н. Войтехович для 7 класса учреждений общего среднего образования

с русским языком обучения

Допущено

Министерством образования

Республики Беларусь

УДК 004(038.3=161.1)

ББК 32.81я721

Рецензенты:

кафедра информационных технологий в культуре факультета культурологии и социокультурной деятельности учреждения образования «Белорусский государственный университет культуры и искусств» (кандидат физико-математических наук, доцент, заведующий кафедрой П. В. Гляков);

учитель информатики высшей квалификационной категории государственного учреждения образования «Гимназия № 25 г. Минска» М. Ю. Симакова

ISBN 978-985-03-2825-0	© Котов В. М., Лапо А. И., Войтехович Е. Н., 2017
© Котов В. М., Лапо А. И., Войтехович Е. Н., 2017
© Оформление. УП «Народная асвета», 2017

От авторов

Дорогие семиклассники! Перед вами электронное приложение к учебному пособию по информатике — предмету, изучение которого позволит вам получить необходимые знания и умения в области информационных технологий, ставших неотъемлемой частью нашей жизни.

В настоящее время исследования по информатике особенно востребованны и актуальны. Роль этой дисциплины в условиях современного мира все более возрастает. Мы, авторы учебного пособия и электронного приложения к нему, постарались сделать так, чтобы изучение информатики было для вас интересным и увлекательным. Надеемся, что полученные знания вы сможете применить для решения практических задач из различных предметных областей.

Материал каждого параграфа разделен на две колонки. Цвет фона поможет вам разобраться в назначении размещенной на этом фоне информации:

белый — основные материалы, обязательные для изучения;

голубой — примеры, иллюстрирующие основные материалы;

желтый — определения основных понятий;

светло-зеленый — исторические сведения, информация об ученых, внесших вклад в развитие информатики, и другие интересные факты.

В электронном приложении к учебному пособию используются следующие условные обозначения:

— тесты;

 — раздел «Упражнения» содержит задания, при выполнении которых используется компьютер;

 — раздел «Упражнения» содержит задания для выполнения в тетради;

 — раздел «Упражнения» содержит задания, при выполнении которых может быть использована информация, размещенная на Национальном образовательном портале;

* — задание или пример для любознательных.

В тексте некоторых заданий вам будет предложено открыть файл. Это означает, что задание можно выполнить, используя файл, размещенный на Национальном образовательном портале (раздел «Электронные образовательные ресурсы» → «Информатика» → «Информатика. 7 класс»). Зайти на портал можно по ссылке http://e-vedy.adu.by или с помощью матричного QR-кода:

Имя файла для скачивания содержит номер параграфа и номер задания из упражнения после этого параграфа. Например, имя файла upr6_3 означает, что файл относится к третьему заданию из упражнения после шестого параграфа. Также на портале размещены файлы с программами, рассмотренными в примерах. Такие файлы имеют имя pr10_1.pas (программа для примера 10.1).

Тесты, содержащиеся в электронном приложении к учебному пособию, можно выполнять в режиме онлайн. Если рядом с вариантами ответа стоит значок , то правильный ответ только один. В тестовых заданиях, варианты ответа которых перечислены с использованием значка , несколько правильных ответов. Чтобы верно выполнить задание такого типа, вам необходимо найти и указать все правильные ответы, иначе компьютер выдаст сообщение об ошибке. В электронном приложении встречаются тестовые задания, ответы в которых необходимо разместить в правильном порядке. Для этого следует перетащить блоки с ответами на соответствующие позиции. Чтобы узнать, правильно ли вы выполнили тестовое задание, нажмите кнопку .

Учебно-электронное издание

Зав. редакцией Г. А. Бабаева. Редактор Е. И. Даниленко. Художественный редактор А. Н. Богушевич. Корректоры А. В. Алешко, В. С. Бабеня, О. С. Козицкая, Е. П. Тхир. Подготовка электронного приложения

.

Свидетельство о государственной регистрации издателя, изготовителя, распространителя печатных изданий 1/2 от 08.07.2013. Пр. Победителей, 11, 220004, Минск, Республика Беларусь.