Построение функции по таблице истинности

Урок-алгоритм: дана таблица истинности — нужно получить формулу. Делаем это механически, без подбора.

Синтез функции — это переход от таблицы истинности к формуле. Всегда возможен и однозначен: по единицам получают СДНФ, по нулям — СКНФ.

В предыдущем уроке мы разобрали, что такое совершенные формы. Теперь превратим это в чёткий пошаговый рецепт и применим его к функции трёх переменных — именно такие встречаются в задачах. Главная мысль: не нужно угадывать формулу. Есть алгоритм, который всегда даёт правильный ответ.

Зачем это нужно

На экзамене и в схемотехнике постоянно возникает обратная задача: поведение устройства описано таблицей (для каждого входа известен выход), а реализовать его надо формулой или схемой из логических элементов. Угадывание тут не работает — для трёх переменных таблица содержит $2^3 = 8$ строк, для четырёх уже $2^4 = 16$. Алгоритм синтеза даёт гарантированный результат за конечное число шагов.

Алгоритм построения СДНФ

Дана таблица функции $F(A, B, C)$. Чтобы получить СДНФ:

1. Найдите все строки, где $F = 1$.
2. Для каждой такой строки выпишите конъюнкцию всех переменных: переменную берите без отрицания, если в строке она равна 1, и с отрицанием, если равна 0.
3. Соедините все полученные конъюнкции знаком ИЛИ ($\lor$).

Для СКНФ всё зеркально: берём строки с $F = 0$; в дизъюнкции переменную пишем без отрицания, если она равна 0, и с отрицанием, если равна 1; соединяем дизъюнкции знаком И ($\land$).

Пошаговый разбор

Возьмём конкретную таблицу функции трёх переменных:

Шаг 1. Выписываем единичные строки

$F = 1$ в строках с наборами $(0,0,0)$, $(0,1,1)$, $(1,0,1)$, $(1,1,1)$. Их четыре, значит в СДНФ будет четыре конъюнкции.

Шаг 2. Строим минтермы

• $(0,0,0)$: все нули → все с отрицанием: $\neg A \land \neg B \land \neg C$.
• $(0,1,1)$: $A=0$ → $\neg A$; $B=1$ → $B$; $C=1$ → $C$: $\neg A \land B \land C$.
• $(1,0,1)$: $A \land \neg B \land C$.
• $(1,1,1)$: всё единицы → без отрицаний: $A \land B \land C$.

Шаг 3. Соединяем через ИЛИ

$$ F_{\text{СДНФ}} = (\neg A \land \neg B \land \neg C) \lor (\neg A \land B \land C) \lor (A \land \neg B \land C) \lor (A \land B \land C) $$

Готово. Теперь для тренировки построим СКНФ по нулевым строкам $(0,0,1)$, $(0,1,0)$, $(1,0,0)$, $(1,1,0)$:

• $(0,0,1)$: $A=0$→$A$, $B=0$→$B$, $C=1$→$\neg C$: $A \lor B \lor \neg C$.
• $(0,1,0)$: $A \lor \neg B \lor C$.
• $(1,0,0)$: $\neg A \lor B \lor C$.
• $(1,1,0)$: $\neg A \lor \neg B \lor C$.

$$ F_{\text{СКНФ}} = (A \lor B \lor \neg C) \land (A \lor \neg B \lor C) \land (\neg A \lor B \lor C) \land (\neg A \lor \neg B \lor C) $$

Как это работает

Минтерм $A \land \neg B \land C$ истинен ровно на одном наборе — $(1,0,1)$ — и ложен на всех остальных семи. Когда мы соединяем минтермы через ИЛИ, итоговая функция «загорается» точно на тех наборах, для которых мы взяли минтермы, и нигде больше. Поэтому СДНФ воспроизводит таблицу один-в-один. Проверим это программой: построим СДНФ автоматически и убедимся, что она совпадает с исходным столбцом $F$.

truth = {
    (0,0,0):1, (0,0,1):0, (0,1,0):0, (0,1,1):1,
    (1,0,0):0, (1,0,1):1, (1,1,0):0, (1,1,1):1,
}

def minterm(row, a, b, c):
    # минтерм истинен только на своём наборе row
    return (a, b, c) == row

ones = [row for row, val in truth.items() if val == 1]
print('Единичных строк:', len(ones))

for a, b, c in sorted(truth):
    sdnf = any(minterm(r, a, b, c) for r in ones)
    print((a, b, c), 'СДНФ =', int(sdnf), '| F =', truth[(a, b, c)])

Вывод:

Единичных строк: 4
(0, 0, 0) СДНФ = 1 | F = 1
(0, 0, 1) СДНФ = 0 | F = 0
(0, 1, 0) СДНФ = 0 | F = 0
(0, 1, 1) СДНФ = 1 | F = 1
(1, 0, 0) СДНФ = 0 | F = 0
(1, 0, 1) СДНФ = 1 | F = 1
(1, 1, 0) СДНФ = 0 | F = 0
(1, 1, 1) СДНФ = 1 | F = 1

Столбцы СДНФ и $F$ совпали во всех восьми строках — формула воспроизводит таблицу точно.

Когда выбирать СДНФ, а когда СКНФ

Обе формы правильны, но одна часто короче. Если единиц меньше, чем нулей — короче СДНФ (меньше слагаемых). Если нулей меньше — короче СКНФ. В нашем примере по 4 строки каждого вида, формы вышли одинаковой длины. На практике сначала прикидывают, чего меньше, и строят более компактную форму.

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

• Сдвиг по строкам. Легко взять минтерм не из той строки. Удобно подписывать каждую строку её набором и галочкой, если $F=1$.
• Перепутанные правила знаков. В СДНФ 0 даёт отрицание; в СКНФ — наоборот. Держите перед глазами обе памятки.
• Пропуск переменной. В каждый минтерм входят ВСЕ переменные. Для трёх переменных в каждой скобке должно быть ровно три множителя.
• Неверный внешний оператор. СДНФ снаружи — ИЛИ, СКНФ снаружи — И.

Итоги

• Синтез функции по таблице всегда возможен и однозначен.
• СДНФ: единичные строки → минтермы (0 → отрицание) → соединить через ИЛИ.
• СКНФ: нулевые строки → макстермы (1 → отрицание) → соединить через И.
• Каждый минтерм/макстерм отвечает ровно за одну строку таблицы.
• Выбирайте форму по тому, чего меньше — единиц или нулей.