Законы де Моргана: Как собрать схему из того, что есть

Иногда в схемотехнике возникает забавная ситуация: тебе нужен определённый вентиль, например, ИЛИ (OR), но на «заводе» доступны только вентили НЕ-И (NAND) и инверторы (NOT). Можно ли выкрутиться? Да! И здесь на помощь приходит математика, а точнее — законы Августа де Моргана.

Решение уровня «ИЛИ»: вентиль OR, собранный из NAND по законам де Моргана — Вентиль ИЛИ из NAND: авторское решение уровня

Де Морган доказал красивое правило: отрицание логического ИЛИ эквивалентно логическому И от отрицаний. Звучит как заклинание, но на практике всё очень наглядно.

Представь, что мы берём обычный вентиль И (AND), ставим инверторы (НЕ) на оба его входа, а затем ещё один инвертор — на выход. Вся эта конструкция волшебным образом начинает работать в точности как вентиль ИЛИ (OR)!

Две формулы

Законов два, и они симметричны:

НЕ (A И B)    = (НЕ A) ИЛИ (НЕ B)
НЕ (A ИЛИ B)  = (НЕ A) И (НЕ B)

В английских обозначениях: NOT(A AND B) = NOT A OR NOT B и NOT(A OR B) = NOT A AND NOT B. Левая часть первого закона — это вентиль NAND («НЕ-И»), а правая — ИЛИ с инверторами на входах. Получается, что NAND эквивалентен ИЛИ с перевёрнутыми входами.

Доказательство таблицей

Проверим первый закон для всех четырёх комбинаций входов:

A	B	A И B	НЕ (A И B)	НЕ A	НЕ B	(НЕ A) ИЛИ (НЕ B)
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Колонка «НЕ (A И B)» и колонка «(НЕ A) ИЛИ (НЕ B)» совпадают во всех четырёх строках — значит, выражения действительно эквивалентны.

Числовой пример: A = 1, B = 0

Разберём первый закон по шагам для A = 1 и B = 0:

1. Сначала левая часть: A И B = 1 И 0 = 0. Инвертируем: НЕ (A И B) = НЕ 0 = 1.

2. Теперь правая часть: НЕ A = НЕ 1 = 0, а НЕ B = НЕ 0 = 1. ИЛИ от них: 0 ИЛИ 1 = 1.

3. Сравниваем: левая часть дала 1, правая — тоже 1. Равенство выполняется.

Попробуй прогнать оставшиеся три комбинации самостоятельно — результат всегда будет совпадать.

OR из трёх NAND

Теперь применим закон на практике. У нас есть только NAND. Чтобы получить OR(A, B), нужно реализовать формулу НЕ (НЕ A И НЕ B). Сначала строим два инвертора, соединив оба входа NAND вместе:

// Инвертор из NAND: оба входа связаны
NAND n1 (a, a, nA);   // nA = НЕ a
NAND n2 (b, b, nB);   // nB = НЕ b

// ИЛИ из трёх NAND
NAND n3 (nA, nB, or); // or = НЕ (nA И nB) = a ИЛИ b

Готово: вентиль ИЛИ из трёх NAND — и ни одного готового ИЛИ или И. Третий NAND сразу выдаёт ИЛИ: по закону де Моргана НЕ (НЕ a И НЕ b) = a ИЛИ b, поэтому дополнительный инвертор на выходе не нужен.

NAND — универсальный вентиль

Из одного только NAND собираются все базовые элементы:

• НЕ: NAND(A, A) — оба входа связаны.
• И: NAND(A, B) плюс инвертор на выходе — два NAND подряд.
• ИЛИ: инверторы на входах плюс NAND — три NAND.

Реальные процессоры, включая твой смартфон, построены преимущественно на NAND-вентилях: производить десятки разных типов вентилей на одном кристалле дорого и технологически сложно, а вот универсальный NAND дёшев и компактен.

Зачем это в игре: уровень 1.4

На уровне 1.4 «Хотя бы один» тебе нужно собрать вентиль ИЛИ, но под рукой только NAND и уже собранные вентили. Закон де Моргана подсказывает решение: построй И из NAND (через инвертор), а затем подставь его в формулу OR = НЕ (НЕ A И НЕ B) — либо собери OR напрямую из трёх NAND. Оба пути ведут к одной и той же таблице истинности.

Проверить тождества де Моргана легко в генераторе таблиц истинности: постройте таблицы для НЕ(A И B) и (НЕ A) ИЛИ (НЕ B) — они совпадут строка в строку.

Проверь себя

Чему равен НЕ(A И B) по де Моргану?

(НЕ A) ИЛИ (НЕ B): инверсия «проходит» через И, превращая его в ИЛИ.

Как собрать ИЛИ, если под рукой только NAND?

Инвертировать каждый вход (NAND входа с самим собой) и подать оба результата на третий NAND: НЕ(НЕ A И НЕ B) = A ИЛИ B.

Что вернёт НЕ(A ИЛИ B) при A = 1, B = 0?

0: внутри скобок уже 1, инверсия даёт 0. По формуле: (НЕ A) И (НЕ B) = 0 И 1 = 0.

Резюме

1. НЕ (A И B) = (НЕ A) ИЛИ (НЕ B) — отрицание И превращается в ИЛИ отрицаний.

2. НЕ (A ИЛИ B) = (НЕ A) И (НЕ B) — отрицание ИЛИ превращается в И отрицаний.

3. NAND эквивалентен ИЛИ с перевёрнутыми входами, а NOR — И с перевёрнутыми входами.

4. Из NAND собираются НЕ, И и ИЛИ — поэтому NAND называют универсальным вентилем.

5. Законы де Моргана позволяют собрать любую схему из ограниченного набора деталей.

На уровне 1.4 тебе предстоит собрать вентиль ИЛИ по закону де Моргана, используя уже построенные И и НЕ. Подробнее о том, что такое вентили И, ИЛИ и НЕ, — в статье «Логические вентили И, ИЛИ, НЕ», а дальше тебя ждёт вентиль XOR, который станет битом суммы твоего будущего сумматора.