Таблицы истинности для основных двоичных логических функций
|
Конъюнкция
(AND)
|
Дизъюнкция
(OR)
|
Сложение по модулю 2
(XOR)
|
|||||||||||||||||||||||||||||||||||||||||||||
Импликация
|
Эквиваленция
|
||||||||||||||||||||||||||||||||||||||||||||||
Штрих Шеффера
|
Стрелка Пирса
|
Отрицание
(NOT)
|
В программировании:
- Конъюнкция = AND = И = ∧{\displaystyle \land } = &
- Дизъюнкция = OR = ИЛИ = ∨{\displaystyle \lor } = |
- Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕{\displaystyle \oplus } = ~
- Отрицание = NOT = НЕ = ¬{\displaystyle \neg } = !
Способы представления булевой функции
С помощью формул можно получать огромное количество разнообразных функций, причём с помощью разных формул можно получить одну и ту же функцию. Иногда бывает весьма полезно узнать, как построить ту или иную функцию, используя лишь небольшой набор заданных операций или используя как можно меньше произвольных операций. Рассмотрим основные способы задания булевых функций:
- Совершенная дизъюнктивная нормальная форма (СДНФ)
- Совершенная конъюнктивная нормальная форма (СКНФ)
- Алгебраическая нормальная форма (АНФ, полином Жегалкина)
Совершенная дизъюнктивная нормальная форма (ДНФ)
Простая конъюнкция — это конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция простых конъюнкций. Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ относительно некоторого заданного конечного набора переменных, в каждую конъюнкцию которой входят все переменные данного набора.
Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.
Совершенная конъюнктивная нормальная форма (КНФ)
Простая дизъюнкция — это дизъюнкция одной или нескольких переменных, или их отрицаний, причём каждая переменная входит в неё не более одного раза. Конъюнктивная нормальная форма (КНФ) — это конъюнкция простых дизъюнкций. Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ относительно некоторого заданного конечного набора переменных, в каждую дизъюнкцию которой входят все переменные данного набора.
Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.
Алгебраическая нормальная форма (АНФ, полином Жегалкина)
Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.
Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1
Алгоритм построения СДНФ для булевой функции
- Построить таблицу истинности для функции
- Найти все наборы аргументов, на которых функция принимает значение 1
- Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые конъюнкции с помощью дизъюнкции
Алгоритм построения СКНФ для булевой функции
- Построить таблицу истинности для функции
- Найти все наборы аргументов, на которых функция принимает значение 0
- Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые дизъюнкции с помощью конъюнкции
Алгоритм построения полинома Жегалкина булевой функции
Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.
- Построить таблицу истинности для функции
- Добавить новый столбец к таблице истинности и записать в 1, 3, 5. ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6. прибавить по модулю два значения из соответственно 1, 3, 5. строк.
- Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10. строк, а к 3, 4, 7, 8, 11, 12. строкам аналогично предыдущему пункту прибавить переписанные значения.
- Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
- Выписать булевы наборы, на которых значение последнего столбца равно единице
- Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.
Бизнес и финансы
БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумагиУправлениеОткрытые акционерные обществаПроектыДокументыЦенные бумаги — контрольЦенные бумаги — оценкиОблигацииДолгиВалютаНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыСтрахованиеБюджетФинансовые услугиКредитыКомпанииГосударственные предприятияЭкономикаМакроэкономикаМикроэкономикаНалогиАудитМеталлургияНефтьСельское хозяйствоЭнергетикаАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьерОрганизация и управление производством
Как задать логическую функцию
Есть множество способов задать булеву функцию:
- таблица истинности
- характеристические множества
- вектор значений
- матрица Грея
- формулы
Рассмотрим некоторые из них:
Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n – число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).
Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c
Функции
Для того чтобы составить таблицу истинности к предложенной вам задаче, необходимо знать логические функции. Что это такое? Логическая функция имеет некоторые переменные, которые являются утверждениями (истинными или ложными), и само значение функции должно дать нам ответ на вопрос: «Выражение истинно или ложно?».
Все выражения принимают следующие значения:
- Истина или ложь.
- И или Л.
- 1 или 0.
- Плюс или минус.
Здесь отдавайте предпочтение тому способу, который для вас является более удобным. Для того чтобы составить таблицу истинности, нам нужно перечислить все комбинации переменных. Их количество вычисляется по формуле: 2 в степени n. Результат вычисления – это количество возможных комбинаций, переменной n в данной формуле обозначается количество переменных в условии. Если выражение имеет много переменных, то можно воспользоваться калькулятором или сделать для себя небольшую таблицу с возведением двойки в степень.
Всего в логике выделяют семь функций или связей, соединяющих выражения:
- Умножение (конъюнкция).
- Сложение (дизъюнкция).
- Следствие (импликация).
- Эквиваленция.
- Инверсия.
- Штрих Шеффера.
- Стрелка Пирса.
Первая операция, представленная в списке, имеет название «логическое умножение». Ее графически можно отметить в виде перевернутой галочки, знаками & или *. Вторая в нашем списке операция – логическое сложение, графически обозначается в виде галочки, +. Импликацию называют логическим следствием, обозначается в виде стрелки, указывающей от условия на следствие. Эквиваленция обозначается двухсторонней стрелкой, функция имеет истинное значение только в тех случаях, кода оба значения принимают либо значение «1», либо «0». Инверсию называют логическим отрицанием. Штрих Шеффера называют функцией, которая отрицает конъюнкцию, а стрелку Пирса – функцией, отрицающей дизъюнкцию.
Логические выражения и таблица истинности
Примеры задач с решениями по этой теме Пройти тестирование по теме Контрольная по теме
Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.
Логическое выражение — составные высказывания в виде формулы.
Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».
Алгоритм построения таблицы истинности:
1.подсчитать количество переменных n в логическом выражении;
2. определить число строк в таблице по формуле m=2n, где n — количество переменных;
3. подсчитать количество логических операций в формуле;
4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;
5. определить количество столбцов: число переменных + число операций;
6. выписать наборы входных переменных;
7. провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в пункте 4 последовательностью.
Заполнение таблицы:
1.разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;
2.разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;
3.продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.
Пример 1. Для формулы A/\ (B \/ ¬B /\¬C) постройте таблицу истинности.
Количество логических переменных 3, следовательно, количество строк — 23 = 8.
Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.
Пример 2. Определите истинность логического выражения F(А, В) = (А\/ В)/\(¬А\/¬В) .
1. В выражении две переменные А и В (n=2).
2. mстрок=2n, m=22=4 строки.
3. В формуле 5 логических операций.
4. Расставляем порядок действий
1) А\/ В; 2) ¬А; 3) ¬В; 4) ¬А\/¬В; 5) (А\/ В)/\(¬А\/¬В).
5. Кстолбцов=n+5=2+5=7 столбцов.
|
А |
В |
А\/ В |
¬А |
¬В |
¬А\/¬В |
F |
|
1 |
1 |
1 |
||||
|
1 |
1 |
1 |
1 |
1 |
||
|
1 |
1 |
1 |
1 |
1 |
||
|
1 |
1 |
1 |
Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.
Пример 3. Построёте таблицу истинности для логического выражения
F = (A\/ B) /\ ¬С
- В данной функции три логические переменные – А, В, С
- количество строк таблицы = 23 =8
- В формуле 3 логические операции.
- Расставляем порядок действий
1) А\/ В; 2) ¬С; 3) (AVB) /\ ¬С .
- количество столбцов таблицы = 3 + 3 = 6
|
А |
В |
С |
A\/B |
¬С |
(A\/B) /\ ¬С |
|
1 |
|||||
|
1 |
|||||
|
1 |
1 |
1 |
1 |
||
|
1 |
1 |
1 |
|||
|
1 |
1 |
1 |
1 |
||
|
1 |
1 |
1 |
|||
|
1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
1 |
Пример 4. Определите истинность формулы: F = ((С \/В) => В) /\ (А /\ В) => В.
Построим таблицу истинности этой формулы.
Ответ: формула является тождественно истинной.
Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
|
X |
Y |
Z |
F |
|
1 |
|||
|
1 |
|||
|
1 |
1 |
Какое выражение соответствует F?
1) ¬X/\¬Y/\Z 2) ¬X\/¬Y\/Z 3) X\/Y\/¬Z 4) X\/Y\/Z
Решение (вариант 1, через таблицы истинности):
Чтобы решить данную задачу можно построить часть таблицы истинности для каждой из четырех функций, заданных в ответе для заданных наборов входных переменных, и сравнить полученные таблицы с исходной:
|
X |
Y |
Z |
F |
¬X |
¬Y |
¬Z |
¬X/\¬Y/\Z |
¬X\/¬Y\/Z |
X\/Y\/¬Z |
X\/Y\/Z |
|
1 |
1 |
1 |
1 |
1 |
1 |
|||||
|
1 |
1 |
1 |
1 |
1 |
1 |
|||||
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Очевидно, что значения заданной функции F совпадают со значениями выражения X\/Y\/¬Z. Следовательно, правильный ответ – 3.
Ответ: 3
Решение (Вариант 2):
Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.
Рассмотрим данный конкретный пример:
1)первое заданное выражение ¬X/\¬Y/\Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;
2)второе заданное выражение ¬X\/¬Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;
3)третье выражение X\/Y\/¬Z соответствует F при всех предложенных комбинациях X,Y и Z;
4)четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.
Ответ: 3
Предмет логики
Что же это за предмет — информатика? Таблица истинности – как ее строить? Зачем нужна наука логика? На все эти вопросы мы сейчас с вами ответим.
Информатика – это довольно увлекательный предмет. Он не может вызывать затруднения у современного общества, ведь все, что нас окружает, так или иначе, относится к компьютеру.
Основы науки логики даются преподавателями средней школы на уроках информатики. Таблицы истинности, функции, упрощение выражений – все это должны объяснять учителя информатики. Эта наука просто необходима в нашей жизни. Приглядитесь, все подчиняется каким-либо законам. Вы подбросили мяч, он подлетел вверх, но после этого упал опять на землю, это произошло из-за наличия законов физики и силы земного притяжения. Мама варит суп и добавляет соль. Почему когда мы его едим, нам не попадаются крупинки? Все просто, соль растворилась в воде, подчиняясь законам химии.
Теперь обратите внимание на то, как вы разговариваете
- «Если я отвезу своего кота в ветеринарную клинику, то ему сделают прививку».
- «Сегодня был очень тяжелый день, потому что приходила проверка».
- «Я не хочу идти в университет, потому что сегодня будет коллоквиум» и так далее.
Все, что вы говорите, обязательно подчиняется законам логики. Это относится как к деловой, так и к дружеской беседе. Именно по этой причине необходимо понимать законы логики, чтобы не действовать наугад, а быть уверенным в исходе событий.
Справочная информация
ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организацииМуниципалитетыРайоныОбразованияПрограммыОтчетыпо упоминаниямДокументная базаЦенные бумагиПоложенияФинансовые документыПостановленияРубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датамРегламентыТерминыНаучная терминологияФинансоваяЭкономическаяВремяДаты2015 год2016 годДокументы в финансовой сферев инвестиционной
Таблицы истинности для основных двоичных логических функций
|
Конъюнкция
(AND)
|
Дизъюнкция
(OR)
|
Сложение по модулю 2
(XOR)
|
|||||||||||||||||||||||||||||||||||||||||||||
Импликация
|
Эквиваленция
|
||||||||||||||||||||||||||||||||||||||||||||||
Штрих Шеффера
|
Стрелка Пирса
|
Отрицание
(NOT)
|
В программировании:
- Конъюнкция = AND = И = ∧{\displaystyle \land } = &
- Дизъюнкция = OR = ИЛИ = ∨{\displaystyle \lor } = |
- Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕{\displaystyle \oplus } = ~
- Отрицание = NOT = НЕ = ¬{\displaystyle \neg } = !
Ход урока
1. Организационный момент.
Цель: подготовить учащихся к уроку.
Объявляется тема урока. Перед учащимися ставится задача: показать, как они научились решать задачи по теме.
2. Повторение изученного материала.
Выполнение в тестирующей оболочке MyTest теста на тему «Основные понятия алгебры логики».(приложение1.mtf)
3. Изучение нового материала.
Вопросы для изучения:
- Простые и сложные выражения.
- Основные логические операции.
При объяснении нового материала используется компьютерная презентация (презентация.PPT)
1. Простые и сложные выражения.
Логические выражения могут быть простыми и сложными.
Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата — либо «истина», либо «ложь».
Сложное логическое выражение содержит высказывания, объединенные логическими операциями. По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которыми являются высказывания.
2. Основные логические операции.
По ходу объяснения нового материала ученики заполняют в тетради таблицу следующего вида.
| Название логической операции | Обозначение логической операции | Результат выполнения логической операции | Таблица истинности | Примеры |
| Отрицание | ||||
| Дизъюнкция | ||||
| Конъюнкция | ||||
| Импликация | ||||
| Эквиваленция |
В качестве основных логических операций в сложных логических выражениях используются следующие:
- НЕ (логическое отрицание, инверсия);
- ИЛИ (логическое сложение, дизъюнкция);
- И (логическое умножение, конъюнкция)
Операция НЕ — логическое отрицание (инверсия)
Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:
- если исходное выражение истинно, то результат его отрицания будет ложным;
- если исходное выражение ложно, то результат его отрицания будет истинным.
Для операции отрицания НЕ приняты следующие условные обозначения: НЕ, ‾, ˥ not А. Результат операции отрицания НЕ определяется следующей таблицей истинности.
Операция ИЛИ — логическое сложение (дизъюнкция, объединение)
Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами.
Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Результат операции ИЛИ определяется следующей таблицей истинности:
| А | В | A v В |
| 1 | 1 | |
| 1 | 1 | |
| 1 | 1 | 1 |
Применяемые обозначения: А или В; A v В; А ог В. При выполнении сложных логических преобразований для наглядности условимся пользоваться обозначением А + В, где А, В — аргументы (исходные высказывания).
Операция И — логическое умножение (конъюнкция)
Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение.
Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Результат операции И определяется следующей таблицей истинности:
| А | В | А^ В |
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
Применяемые обозначения: А и В; А ^ В; А & В; A and В.
Условимся пользоваться при выполнении сложных логических преобразований обозначением A-В, где А, В — аргументы (исходные высказывания).
Операция «ЕСЛИ-TO— логическое следование (импликация)
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
Применяемые обозначения:
если А, то В; А влечет В; if A then В; А—»В.
Результат операции следования (импликации) ложен, только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.
Таблица истинности:
| А | В | Если А, то В |
| 1 | ||
| 1 | 1 | |
| 1 | ||
| 1 | 1 | 1 |
Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
Применяемое обозначение: А ~В.
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Таблица истинности:
| А | В | А ~ В |
| 1 | ||
| 1 | 1 | |
| 1 | ||
| 1 | 1 | 1 |
4. Закрепление изученного материала
5. Подведение итогов урока
Скажите был ли сегодняшний урок для вас познавательный?
Что больше всего запомнилось из урока?
6. Домашнее задание
- Учебник. п.23.2., заполнить таблицу «Логические операции» до конца.
- Выполнить задание (приложение 3)
- Подготовиться к тестированию.
- Знать ответы на вопросы:
- какие высказывания бывают;
- какие высказывания называются простыми, а какие – сложными;
- основные логические операции и их свойства.
