Генератор выражений по таблице истинности
Задайте столбец результата так, как вам нужно, и инструмент прочитает по нему формулу: каноническую ДНФ (сумму произведений), каноническую КНФ (произведение сумм) и кратчайшую эквивалентную форму. Всё считается в браузере, а собранная таблица помещается прямо в ссылку.
| p | q | Результат |
|---|---|---|
| ⊥ | ⊥ | |
| ⊤ | ⊥ | |
| ⊥ | ⊤ | |
| ⊤ | ⊤ |
Нажимайте на значения результата, чтобы переключать истину (⊤) и ложь (⊥)
Построенное выражение
Как превратить таблицу истинности в булево выражение
Любая таблица истинности — это таблица истинности какой-то формулы, и две такие формулы читаются прямо по ней: без алгебры и без перебора.
- Выпишите все 2ⁿ строк для своих n переменных и отметьте те, где результат равен ⊤.
- Для каждой строки ⊤ запишите минтерм: все переменные через И, с отрицанием там, где строка делает их ложными. Соедините минтермы через ИЛИ — это ДНФ.
- Для каждой строки ⊥ запишите макстерм: все переменные через ИЛИ, с отрицанием там, где строка делает их истинными. Соедините макстермы через И — это КНФ.
- У обеих формул ровно та таблица, с которой вы начали, так что любая из них — верный ответ. Минимизируйте потом, если нужна самая короткая.
Минтерм
Конъюнкция всех переменных, каждая с отрицанием или без, истинная ровно в одной строке таблицы. ДНФ — это дизъюнкция минтермов тех строк, где результат равен ⊤, поэтому в ней по одному слагаемому на каждую строку ⊤.
Макстерм
Дизъюнкция всех переменных, каждая с отрицанием или без, ложная ровно в одной строке таблицы. КНФ — это конъюнкция макстермов тех строк, где результат равен ⊥, поэтому в ней по одному множителю на каждую строку ⊥.
Разбор примера: исключающее ИЛИ
Таблица выше — та, с которой инструмент открывается: p и q, истинно ровно в тех двух строках, где входы различны.
- Две строки дают ⊤, поэтому в ДНФ два минтерма: (p ∧ ¬q) ∨ (¬p ∧ q)
- Две другие дают ⊥, поэтому в КНФ два макстерма: (p ∨ q) ∧ (¬p ∨ ¬q)
Ни одну из них не сократить: исключающему ИЛИ действительно нужны оба слагаемых. Это стоит увидеть хотя бы раз — каноническая форма не всегда длинный путь. По-настоящему минимальная форма выигрывает на таблицах вроде «не более одного из p, q, r».
Как устроен синтез булевых функций
Дизъюнктивная нормальная форма (ДНФ)
ДНФ записывает формулу как ИЛИ из И (сумма произведений). Для каждой строки, где результат истинен, строится минтерм: все переменные соединяются через И, причём ложные берутся с отрицанием. Минтермы затем соединяются через ИЛИ и дают всё выражение.
Конъюнктивная нормальная форма (КНФ)
КНФ записывает формулу как И из ИЛИ (произведение сумм). Для каждой строки, где результат ложен, строится макстерм: все переменные соединяются через ИЛИ, причём истинные берутся с отрицанием. Макстермы затем соединяются через И и дают всё выражение.
ДНФ и КНФ в сравнении
| Признак | Дизъюнктивная нормальная форма (сумма произведений) | Конъюнктивная нормальная форма (произведение сумм) |
|---|---|---|
| Строится по | Строкам, где результат ⊤ — по минтерму на каждую | Строкам, где результат ⊥ — по макстерму на каждую |
| Вид | Дизъюнкция конъюнкций: ИЛИ из И | Конъюнкция дизъюнкций: И из ИЛИ |
| Когда выбирать | Нужно перечислить случаи, в которых формула истинна, или разложить схему И-ИЛИ | Нужны условия, которые должны выполняться одновременно, или клаузальная форма для SAT-решателя |
Насколько велика таблица?
У функции от n переменных 2ⁿ строк, так что с каждой новой переменной таблица удваивается: 4 строки для двух переменных, 8 для трёх, 16 для четырёх и 32 для пяти — на этом инструмент останавливается. ДНФ берёт по слагаемому на строку ⊤, а КНФ — по множителю на строку ⊥, так что вместе они учитывают каждую строку ровно один раз, и одна из них всегда оказывается более коротким началом.
Где применяется синтез по таблице истинности
Переход от таблицы истинности к логическому выражению — базовый приём в информатике и цифровой электронике. Инструмент помогает:
- Проектировать цифровые схемы — получать булевы уравнения для логических элементов по нужному поведению входов и выходов
- Разрабатывать программы — выводить условную логику из таблицы требований
- Учиться — осваивать булеву алгебру и логику высказываний на практике
- Оптимизировать логику — сравнивать ДНФ и КНФ и выбирать более простое эквивалентное выражение
Часто задаваемые вопросы
Ответы на распространённые вопросы о работе с Логическим калькулятором
Что делает инструмент «от таблицы истинности к выражению»?
Он запускает калькулятор в обратную сторону. Вы задаёте столбец результата таблицы истинности, щёлкая по строкам, а он выдаёт формулу ровно с такой таблицей истинности — в дизъюнктивной нормальной форме (ИЛИ из И) или в конъюнктивной нормальной форме (И из ИЛИ).
В чём разница между ДНФ и КНФ?
ДНФ — это сумма произведений: по одной конъюнкции на каждую строку, где результат истинен, и все они соединены через ИЛИ. КНФ — произведение сумм: по одной дизъюнкции на каждую строку, где результат ложен, и все они соединены через И. Обе описывают одну и ту же функцию, так что выбирать стоит ту, которая для вашей таблицы короче: преимущественно ложный столбец даёт короткую ДНФ, преимущественно истинный — короткую КНФ.
Сколько переменных выдерживает инструмент синтеза?
До пяти, то есть таблица из 32 строк. Каждая добавленная переменная удваивает число строк, и после пяти таблицу уже нельзя заполнить вручную.
Почему полученное выражение такое длинное?
Нормальная форма строится построчно: по одному полному терму на каждую покрываемую строку, поэтому её длина следует таблице истинности, а не идее, стоящей за формулой. Она корректна по построению, но не компактна. Чтобы её сократить, откройте её в калькуляторе — он перечислит эквивалентные формы, включая минимизированную ДНФ.
Можно ли получить упрощённый вариант формулы?
Да. Введите её в калькулятор и посмотрите на эквивалентные формы под таблицей истинности. Среди них есть формы, полученные преобразованием по законам алгебры, а также ДНФ и КНФ, считанные с таблицы истинности, вместе с минимизированной ДНФ.