Как составить СКНФ по таблице: пошаговое решение

Дано: булева функция $F(A,B,C)$, заданная таблицей истинности, столбец значений 1 1 0 1 0 1 0 1 по наборам от 000 до 111. Найти: совершенную конъюнктивную нормальную форму и проверить её подстановкой набора 110.

Преобразовывать формулу не придётся: СКНФ читается прямо из таблицы. Берём только строки, где функция равна нулю, каждую превращаем в дизъюнкцию всех трёх переменных и соединяем полученные скобки конъюнкцией. Нулевых строк здесь три, значит и сомножителей в ответе будет три: $F = (A \vee \neg B \vee C) \wedge (\neg A \vee B \vee C) \wedge (\neg A \vee \neg B \vee C)$.

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

Решение по шагам

Шаг 1. Пронумеровать строки и найти нули. Переменных три, поэтому строк ровно $2^3 = 8$. Номер строки и есть её набор в двоичной записи: строка 0 это 000, строка 6 это 110. Столбец значений из условия раскладывается так:

Нули стоят в строках с номерами 2, 4 и 6, то есть на наборах 010, 100 и 110. Остальные пять строк для СКНФ не нужны совсем.

Шаг 2. Записать правило перевода строки в макстерм. Для каждой нулевой строки составляется полная дизъюнкция всех переменных функции, по одному литералу на переменную. Литерал берётся с отрицанием, если в этой строке переменная равна единице, и без отрицания, если равна нулю. Такую дизъюнкцию называют макстермом или конституентой нуля.

Шаг 3. Перевести нулевые строки. Набор 010: у $A$ стоит ноль, значит литерал $A$; у $B$ единица, значит $\neg B$; у $C$ ноль, значит $C$. Получается $A \vee \neg B \vee C$. Набор 100 даёт $\neg A \vee B \vee C$, набор 110 даёт $\neg A \vee \neg B \vee C$.

Шаг 4. Соединить макстермы конъюнкцией. Порядок сомножителей значения не имеет, но привычнее выписывать их по возрастанию номера строки:

$$F = (A \vee \neg B \vee C) \wedge (\neg A \vee B \vee C) \wedge (\neg A \vee \neg B \vee C).$$

Шаг 5. Проверить подстановкой. Возьмём набор 110, то есть $A = 1$, $B = 1$, $C = 0$. Первый сомножитель: $1 \vee 0 \vee 0 = 1$. Второй: $0 \vee 1 \vee 0 = 1$. Третий: $0 \vee 0 \vee 0 = 0$. Вся конъюнкция обращается в ноль, а в таблице на строке 6 как раз $F = 0$ - сходится.

Для контроля проверим и единичную строку, например 011: сомножители дают $0 \vee 0 \vee 1 = 1$, $1 \vee 1 \vee 1 = 1$ и $1 \vee 0 \vee 1 = 1$, произведение равно единице, в таблице там тоже стоит единица.

Ответ: $F = (A \vee \neg B \vee C) \wedge (\neg A \vee B \vee C) \wedge (\neg A \vee \neg B \vee C)$, в числовой записи $F = \prod M(2, 4, 6)$.

Формула и откуда берётся правило отрицания

Правило «отрицание на единицах» выглядит вывернутым наизнанку ровно до тех пор, пока не посмотреть, что должен делать один макстерм. Дизъюнкция ложна в единственном случае: когда ложны все её слагаемые. Значит макстерм, собранный по строке $\sigma$, обязан обратиться в ноль именно на наборе $\sigma$ и остаться единицей на всех остальных семи наборах.

Чтобы литерал переменной $A$ стал нулём на наборе, где $A = 1$, его нужно взять с отрицанием: $\neg A$ при $A = 1$ даёт ноль. А если в строке $A = 0$, то нулём становится сама переменная без отрицания. Отсюда и зеркальность по отношению к минтерму.

В общем виде для функции $n$ переменных макстерм строки $\sigma = (\sigma_1, \dots, \sigma_n)$ записывается через степенное обозначение литерала $x^{\sigma}$, где $x^1 = x$ и $x^0 = \neg x$:

$$M_{\sigma} = x_1^{\overline{\sigma_1}} \vee x_2^{\overline{\sigma_2}} \vee \dots \vee x_n^{\overline{\sigma_n}}, \qquad F = \bigwedge_{\sigma:\, F(\sigma) = 0} M_{\sigma}.$$

Черта над показателем и означает то самое переворачивание: единица в строке даёт отрицание литерала. Каждый сомножитель гасит ровно одну нулевую строку, а все остальные наборы пропускает, поэтому конъюнкция макстермов воспроизводит столбец $F$ точка в точку. Из этого же следует единственность: СКНФ у функции ровно одна с точностью до порядка скобок и порядка литералов внутри скобки. Не существует она только у тождественно истинной функции, у которой нулевых строк нет вообще.

Чем СКНФ отличается от СДНФ

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

Сравним на нашей функции. Единиц в столбце пять, поэтому СДНФ состоит из пяти минтермов и содержит $5 \cdot 3 = 15$ литералов, а СКНФ из трёх макстермов и $3 \cdot 3 = 9$ литералов. Правило простое: короче та форма, которой соответствует меньшее число строк. Если нулей в столбце меньше половины, выгоднее СКНФ, если меньше половины единиц, то СДНФ.

Удобна и числовая запись: наша функция это $\prod M(2, 4, 6)$ для конъюнктивной формы и $\sum m(0, 1, 3, 5, 7)$ для дизъюнктивной. Номера в двух списках дополняют друг друга до полного набора от 0 до 7, потому что каждая строка таблицы попадает ровно в один из них.

Если функция задана формулой, а не столбцом

Тогда добавляется нулевой шаг: по формуле строится таблица истинности, а дальше всё как выше. Столбец из условия соответствует формуле $F = (A \vee B) \to C$. Импликация ложна только при истинной посылке и ложном следствии, то есть когда $A \vee B = 1$ и $C = 0$: это наборы 010, 100 и 110, те самые три нулевые строки.

Заполнять таблицу лучше по промежуточным столбцам, а не считать формулу целиком в уме; порядок действий и разбор приоритета операций разобраны в задаче как построить таблицу истинности. Ошибка в одной клетке столбца $F$ тихо меняет ответ: лишний ноль добавит в СКНФ лишний сомножитель, пропущенный ноль отнимет нужный.

Проверка эквивалентности и упрощение

Совершенные формы канонические, поэтому они дают самый прямой способ проверить равносильность двух формул: строишь для каждой таблицу, выписываешь СКНФ и сравниваешь. Совпали с точностью до порядка скобок - формулы равносильны, разошлись хотя бы одним макстермом - нет. Например, для $(\neg A \wedge \neg B) \vee C$ таблица даёт те же нули на наборах 010, 100 и 110, значит эта формула равносильна нашей.

Сама СКНФ почти никогда не минимальна. Второй и третий сомножители отличаются только знаком при $B$, поэтому склеиваются в $\neg A \vee C$; первый и третий отличаются знаком при $A$ и дают $\neg B \vee C$. Минимальная КНФ получается вдвое короче: $(\neg A \vee C) \wedge (\neg B \vee C)$. Склейка макстермов делается теми же приёмами, что и склейка минтермов, в карте Карно или упрощением логического выражения.

Частые ошибки

• Берут строки с единицей. Это самая частая путаница: для СКНФ нужны нулевые строки, единичные работают на СДНФ.
• Ставят отрицание на нулях. В макстерме отрицание идёт туда, где в строке стоит единица. Проверка за одну секунду: подставь набор своей строки в свою же скобку, должен получиться ноль.
• Пишут конъюнкцию внутри скобки, а дизъюнкцию между скобками. Внутри макстерма только $\vee$, между макстермами только $\wedge$; перепутанные знаки превращают ответ в СДНФ чужой функции.
• Теряют переменную. Форма называется совершенной именно потому, что каждая скобка содержит все $n$ переменных ровно по одному разу. Скобка $A \vee C$ без $B$ это уже не макстерм, а элемент обычной КНФ.
• Сокращают ответ по ходу дела. Склеивать сомножители можно только после того, как СКНФ выписана целиком, иначе проверить её по таблице уже нельзя.
• Забывают случай тождественной истины. Если нулей в столбце нет, СКНФ не существует, и правильный ответ звучит именно так, а не «формула пустая».

FAQ

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

Сколько сомножителей должно получиться? Ровно столько, сколько нулей в столбце значений. Для функции $n$ переменных это число от 0 до $2^n$: при нуле СКНФ не существует (функция тождественно истинна), при $2^n$ конъюнкция гасит все наборы и функция тождественно ложна.

Можно ли получить СКНФ, не строя таблицу? Да, равносильными преобразованиями: снять импликации, загнать отрицания к переменным по законам де Моргана, раскрыть по дистрибутивному закону до КНФ и дополнить неполные скобки выражением вида $x \wedge \neg x$. Путь через таблицу короче и почти не даёт ошибок, поэтому в контрольных обычно требуют именно его.

Зачем нужна СКНФ, если она длиннее минимальной формы? Она каноническая: у равносильных функций она совпадает буква в букву. На этом держатся проверка равносильности, сравнение схем и стартовая форма для минимизации, а ещё перевод функции в базис ИЛИ-НЕ. Если нужна не каноническая, а компактная запись, посмотри на полином Жегалкина как на ещё одну каноническую форму.

Коротко

1. Построй или выпиши таблицу истинности и отметь строки, где $F = 0$.
2. Каждую такую строку переведи в макстерм: дизъюнкция всех переменных, отрицание ставится там, где в строке стоит единица.
3. Соедини все макстермы знаком конъюнкции, порядок скобок роли не играет.
4. Проверь подстановкой: на своём наборе макстерм должен давать ноль, на чужих единицу.
5. Для столбца 1 1 0 1 0 1 0 1 ответ равен $F = (A \vee \neg B \vee C) \wedge (\neg A \vee B \vee C) \wedge (\neg A \vee \neg B \vee C)$, то есть $\prod M(2, 4, 6)$.