Математика · объяснение и практика

Как построить КНФ по ложным строкам таблицы истинности

Как превратить полную таблицу истинности в конъюнктивную нормальную форму: исключить каждую ложную строку своей скобкой, выбрать отрицания и проверить совпадение результатов.

Синяя и оранжевая половины складываются в целый круг.

В теме Множества, отношения и математическая логика · Учебная карта

В маршруте Условия и доказательные связи · 10 тем

Главная мысль

Для каждой ложной строки составьте дизъюнкцию, которая ложна ровно на этой строке: переменную со значением 0 берите без отрицания, со значением 1 — с отрицанием. Соедините полученные скобки знаком «и». Итоговая КНФ имеет ту же таблицу истинности, что исходное высказывание.

Скобка должна запрещать ровно одну оценку

Работаем с классическими высказываниями p и q: каждое независимо получает значение 0 или 1. Таблица должна содержать все четыре сочетания, а не только наблюдавшиеся примеры. Конъюнктивная нормальная форма, сокращённо КНФ, состоит из скобок с «или», соединённых знаком «и». Внутри скобки используются переменные либо их отрицания.

Пусть нужно исключить строку p=0, q=1. Выражение p∨¬q ложно именно здесь: оба его члена равны нулю. Если изменить хотя бы одно значение строки, один член станет истинным. Поэтому знак выбирается не копированием единицы из таблицы: единичное значение требует отрицания, чтобы соответствующий член скобки оказался ложным.

Собрать скобки для всех запрещённых строк

Зададим собственную таблицу: результат истинен на (0;0) и (1;1), ложен на (0;1) и (1;0). Ложная строка (0;1) даёт p∨¬q, а строка (1;0) — ¬p∨q. Их конъюнкция (p∨¬q)∧(¬p∨q) запрещает обе нежелательные оценки. Это построение формулы по условиям, а не угадывание по двум совпавшим значениям.

Почему таблица сохраняется целиком? На любой исходно ложной строке её собственная скобка ложна, значит ложна вся конъюнкция. На исходно истинной строке каждая скобка истинна: эта оценка отличается от запрещённой хотя бы одной переменной. Поэтому итог истинен ровно там, где он должен быть истинным. Так доказаны оба направления равносильности.

Пример

Проверьте построенную формулу на всех четырёх строках в порядке (0;0), (0;1), (1;0), (1;1).

Значения скобок равны соответственно (1;1), (0;1), (1;0), (1;1). Соединение знаком «и» даёт 1, 0, 0, 1 — точно заданный столбец результатов. Одной удачной строки для такого вывода было бы недостаточно.

Различить построение, упрощение и неизвестные данные

При трёх переменных в каждой скобке этого способа стоят три члена. Например, ложной оценке (p;q;r)=(1;0;1) соответствует ¬p∨q∨¬r. Конъюнкция таких скобок по всем ложным строкам является полной формой, однако не обязана быть самой короткой. Упрощённая равносильная КНФ может содержать меньше скобок.

Если ложных строк нет, функция тождественно истинна; это можно обозначить константой 1 вместо обычной записи скобок. Неполная таблица не определяет единственную функцию: неизвестную строку нельзя молча объявить ложной. Кроме того, при n переменных имеется 2ⁿ оценок, поэтому прямое построение быстро растёт. Здесь проверяется конечная логическая модель, а не истинность самих исходных фактов о мире.

От чтения к действию

А теперь — вы

Для ложной строки полной таблицы (p;q;r)=(0;0;1) какую скобку нужно включить в построение КНФ, чтобы она была ложна ровно здесь?

Частые вопросы

Почему единицу из ложной строки заменяют отрицанием?

Нужна скобка, ложная именно на этой оценке. При p=1 член ¬p равен нулю; сама p сделала бы скобку истинной и не исключила нужную строку.

Разные КНФ обязательно задают разные функции?

Нет. После равносильных упрощений записи могут различаться. Сравнивают значения на всех оценках, а не только число или порядок скобок.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться