От таблицы истинности к схеме: СДНФ и СКНФ
Каждый уровень в режиме «Задачи» проверяет схему векторами: на входы подаются комбинации битов, а выходы сверяются с таблицей. Из любой заполненной таблицы истинности схему можно вычислить механически, без озарений и перебора. Рецепт для строк с единицами называется СДНФ, для строк с нулями — СКНФ. В этой статье соберём обе формы на одной таблице и обозначим границу, за которой рецепт перестаёт работать.
Схема без памяти — это формула
Комбинационная схема с одним выходом вычисляет булеву функцию: каждому набору входов она сопоставляет 0 или 1. Вентили при этом работают как операции записи: AND перемножает, OR складывает, NOT переворачивает бит. Из этих трёх деталей собирается любая функция — универсальность NAND из законов де Моргана тому подтверждение. Остаётся научиться строить схему по рецепту, а не наугад.
Таблица-пример: голосование трёх судей
Три судьи голосуют кнопками A, B и C. Лампа F загорается, если «за» отданы хотя бы два голоса. Полная таблица умещается в восемь строк:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Шаг 1: минтермы для строк с единицей
Минтерм закрывает ровно одну строку таблицы. Пишется он как И (конъюнкция) всех переменных набора, причём если переменная в строке равна 1, берут её саму, а если 0, то с инверсией. Строка A = 0, B = 1, C = 1 даёт минтерм «НЕ A И B И C».
Свойство минтерма простое: он равен 1 на своём наборе и равен 0 на всех остальных семи. Ни один другой набор его не «включает».
Шаг 2: СДНФ, ИЛИ всех минтермов
СДНФ (совершенная дизъюнктивная нормальная форма) записывается в одно действие: соедините через ИЛИ минтермы всех строк, где F = 1. У голосования таких строк четыре:
F = (НЕ A И B И C) ИЛИ (A И НЕ B И C)
ИЛИ (A И B И НЕ C) ИЛИ (A И B И C)На Verilog та же формула выглядит так:
assign f = (~a & b & c) | (a & ~b & c) |
(a & b & ~c) | (a & b & c);Схеме понадобятся 3 инвертора, 4 вентиля AND с тремя входами и один OR с четырьмя: всего 8 вентилей. Работу гарантирует свойство минтермов: на каждом наборе входов ровно один из четырёх минтермов может быть равен 1, остальные выдают 0, поэтому OR возвращает правильное значение F на всех восьми строках.
«Совершенная» в названии означает, что в каждый минтерм входят все переменные. Рецепт применим к любой таблице: XOR, например, записывается двумя минтермами — (НЕ A И B) ИЛИ (A И НЕ B).
Шаг 3: СКНФ, И всех макстермов
Двойственный рецепт работает со строками, где F = 0. Макстерм записывается через ИЛИ всех переменных, но инверсия берётся наоборот: единица остаётся собой, ноль получает инверсию. Макстермы соединяются через И. У голосования нулевых строк тоже четыре:
F = (A ИЛИ B ИЛИ C) И (A ИЛИ B ИЛИ НЕ C)
И (A ИЛИ НЕ B ИЛИ C) И (НЕ A ИЛИ B ИЛИ C)Здесь зеркальная логика: макстерм равен 0 на своём наборе (один его член равен 0, поэтому весь OR равен 0) и равен 1 на всех остальных. AND из макстермов выдаёт 0, как только попадает в любую нулевую строку. Форма получается длинной или короткой в зависимости от таблицы: мало единиц, берите СДНФ; мало нулей, берите СКНФ.
Переход между формами
СДНФ и СКНФ связаны двойным отрицанием и теми самыми законами де Моргана: обёртка «НЕ (...)» превращает ИЛИ минтермов в И от инверсий, а инверсия каждого минтерма по де Моргану даёт готовый макстерм. Обе формы удобно сверять в генераторе таблиц истинности: постройте таблицы для СДНФ и СКНФ голосования — они совпадут строка в строку.
Граница рецепта: схемы с памятью
СДНФ и СКНФ описывают комбинационную логику: выход зависит только от текущих входов. Мультиплексор, дешифратор и сумматор подходят под это определение, поэтому рецепт работает для них от начала до конца.
Триггер под определение не попадает: он хранит бит, и его выход зависит от того, что подавалось на вход раньше. Такие схемы описывают уравнением следующего состояния Q⁺ = f(входы, Q), где f — обычная комбинационная функция, и вот к ней рецепт применим снова. У D-триггера f повторяет вход: Q⁺ = D. Как из этой записи с обратной связью рождается настоящий триггер, рассказано в статьях про SR-защёлку и D-триггер.
Зачем это в игре
Уровень 1.9 «Перекрёсток» просит собрать мультиплексор 2→1: при S = 0 выход повторяет A, при S = 1 повторяет B. СДНФ даёт ответ двумя минтермами, без единой подсказки: (НЕ S И A) ИЛИ (S И B). Понадобятся два AND, один OR и один NOT, всего четыре вентиля.
В части 2 та же техника собирает дешифратор: на уровне «Анатомия дешифратора» каждый выход распознаёт свой опкод, и каждый распознаватель — это минтерм из трёх бит опкода. Проверяйте формулу в генераторе таблиц истинности до сборки: расхождение с заданием видно сразу.
Схема из СДНФ работает сразу, но почти всегда содержит лишние вентили: голосование обошлось в 8, хотя хватает 4. Откуда берётся экономия, разбирает следующая статья о картах Карно.
Проверь себя
Выпишите минтерм строки A = 1, B = 0, C = 1.
A И НЕ B И C: единицы берутся сами, ноль берётся с инверсией.
Когда СКНФ получится короче СДНФ?
Когда нулевых строк меньше, чем единичных: каждый макстерм гасит одну нулевую строку, и лишних макстермов не будет.
Почему триггер не строится из СДНФ напрямую?
Выход триггера зависит ещё и от сохранённого состояния, а СДНФ описывает функции только от текущих входов. СДНФ применима к комбинационной части: уравнению следующего состояния Q⁺ = f(входы, Q).
Резюме
1. Минтерм закрывает одну строку с единицей: переменные берутся сами, нули с инверсией.
2. СДНФ — это ИЛИ всех минтермов; она даёт работающую схему для любой таблицы.
3. Макстерм гасит одну строку с нулём (инверсии наоборот); СКНФ — это И всех макстермов.
4. Форма короче тогда, когда в таблице меньше соответствующих строк: при редких единицах берите СДНФ, при редких нулях СКНФ.
5. Обе формы описывают комбинационную логику; для схем с памятью рецепт применяется к функции следующего состояния.
На уровне 1.9 «Перекрёсток» соберите мультиплексор по СДНФ и убедитесь, что четыре вентиля проходят все векторы. Если нужно освежить базовые вентили, вернитесь к статье «Логические вентили И, ИЛИ, НЕ», а затем переходите к минимизации по картам Карно.