Как упростить таблицу истинности
Упрощение логических выражений
Основная образовательная задача урока – научить учащихся умению упрощать логические выражения, правильно определять порядок выполнения операций в логическом выражении, устанавливать связи между различными частями сложных логических выражений, умение выбирать лучший вариант решения.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Обозначим: X – логическое высказывание, 
– инверсия, & – конъюнкция, 
– дизъюнкция, 
– импликация, 
– эквиваленция.
Применение основных законов логики для упрощения логических выражений.
Представленные примеры демонстрируют основные приемы упрощения логических выражений.
Упростить логическое выражение:
1) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций:
Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией.
Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией, затем операцией с константами.
2) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных дизъюнкцией. Сначала преобразуем выражения в скобках.
В первой скобке воспользуемся распределительным законом, во второй скобке – раскроем инверсию по правилу де Моргана и избавимся от инверсии по закону двойного отрицания.
Воспользуемся операцией переменной с ее инверсией.
3) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных конъюнкцией. Сначала преобразуем выражения в скобках.
Раскроем инверсию по правилу де Моргана, избавимся от инверсии по закону двойного отрицания.
Воспользуемся переместительным законом и поменяем порядок логических сомножителей.
Применим закон склеивания 
Воспользуемся распределительным законом, затем операцией переменной с ее инверсией, затем операцией с константами.
4) 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
В выражении присутствует импликация. Сначала преобразуем импликацию 
.
Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.
Применим закон идемпотенции и перегруппируем логические слагаемые.
Воспользуемся распределительным законом и вынесем за скобки общий логический множитель.
Воспользуемся операцией с константами.
5) 
Рассмотрим 3 способа упрощения этого логического выражения.
1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.
Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией и законом идемпотенции.
Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией.
Воспользуемся законом идемпотенции.
2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.
Воспользуемся законом склеивания 
Воспользуемся операцией переменной с ее инверсией.
3 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.
Повторим второй сомножитель 
, что разрешено законом идемпотенции.
Сгруппируем два первых и два последних сомножителя.
Воспользуемся законом склеивания 
6) 
Рассмотрим 2 способа упрощения этого логического выражения.
1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
Воспользуемся распределительным законом и вынесем общий логический множитель за скобки.
2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
Введем вспомогательный логический сомножитель 
Сгруппируем 1 и 4, 2 и 3 логические слагаемые. Вынесем общие логические множители за скобки.
Воспользуемся операцией с константами и операцией переменной с ее инверсией.
Получили два логических выражения:
Теперь построим таблицы истинности и посмотрим, правильно ли упрощено логическое выражение
| X | Y | Z |  |  |  |  |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| X | Y | Z |  |  |  |  |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| X | Y | Z |  |  |  |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 |
| X | Y | Z |  |  |  |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Как видно из сравнения таблиц истинности формулы являются равносильными.
Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.
Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.
Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина
введите функцию или её вектор
Построено таблиц, форм:
Как пользоваться калькулятором
Видеоинструкция к калькулятору
Используемые символы
Для смены порядка выполнения операций используются круглые скобки ().
Обозначения логических операций
Что умеет калькулятор
Что такое булева функция
Что такое таблица истинности?
Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.
Логические операции
Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).
Таблица истинности логических операций
| a | b | a ∧ b | a ∨ b | ¬a | ¬b | a → b | a = b | a ⊕ b |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
Как задать логическую функцию
Есть множество способов задать булеву функцию:
Рассмотрим некоторые из них:
Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c
Способы представления булевой функции
С помощью формул можно получать огромное количество разнообразных функций, причём с помощью разных формул можно получить одну и ту же функцию. Иногда бывает весьма полезно узнать, как построить ту или иную функцию, используя лишь небольшой набор заданных операций или используя как можно меньше произвольных операций. Рассмотрим основные способы задания булевых функций:
Совершенная дизъюнктивная нормальная форма (ДНФ)
Простая конъюнкция — это конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция простых конъюнкций.
Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ относительно некоторого заданного конечного набора переменных, в каждую конъюнкцию которой входят все переменные данного набора.
Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.
Совершенная конъюнктивная нормальная форма (КНФ)
Простая дизъюнкция — это дизъюнкция одной или нескольких переменных, или их отрицаний, причём каждая переменная входит в неё не более одного раза.
Конъюнктивная нормальная форма (КНФ) — это конъюнкция простых дизъюнкций.
Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ относительно некоторого заданного конечного набора переменных, в каждую дизъюнкцию которой входят все переменные данного набора.
Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.
Алгебраическая нормальная форма (АНФ, полином Жегалкина)
Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.
Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1
Алгоритм построения СДНФ для булевой функции
Алгоритм построения СКНФ для булевой функции
Алгоритм построения полинома Жегалкина булевой функции
Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.
Примеры построения различных представлений логических функций
Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬a b∨ ¬b c∨ca
1. Построим таблицу истинности для функции
| a | b | c | ¬a | ¬a ∧b | ¬b | ¬b ∧c | ¬a ∧b∨ ¬b ∧c | c∧a | ¬a ∧b∨ ¬b ∧c∨c∧a |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Построение совершенной дизъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает истинное значение: < 0, 0, 1 > < 0, 1, 0 > < 0, 1, 1 > < 1, 0, 1 >
В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:
Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:
Построение совершенной конъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает ложное значение: < 0, 0, 0 > < 1, 0, 0 >
В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:
Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:
Построение полинома Жегалкина:
Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:
| a | b | c | F | 1 | |
| 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 0 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 1 | 1 | 0 | 0 | → | 0 |
| 1 | 1 | 1 | 1 | ⊕ 0 | 1 |
Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:
| a | b | c | F | 1 | 2 | |
| 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | 1 | → | 1 |
| 1 | 1 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:
| a | b | c | F | 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | → | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | ⊕ 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
Окончательно получим такую таблицу:
| a | b | c | F | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):
Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc
Programforyou — это сообщество, в котором Вы можете подтянуть свои знания по программированию, узнать, как эффективно решать те или иные задачи, а также воспользоваться нашими онлайн сервисами.