Булева алгебра: законы, теоремы де Моргана и упрощение

7 мин чтения · Команда bitGateLab

Булева алгебра — это язык, на котором описывают и преобразуют цифровые схемы. Каждому выражению соответствует некоторое соединение логических элементов, а каждый закон, применённый для упрощения, оборачивается сэкономленными элементами. Здесь вы повторите аксиомы, самые полезные законы, теоремы де Моргана и научитесь упрощать выражение шаг за шагом, обосновывая каждое действие.

Переменные и операции

Булева переменная принимает только значения 0 и 1. Основных операций три: инверсия, или отрицание (A, элемент NOT), логическое умножение (A·B или AB, элемент AND) и логическое сложение (A + B, элемент OR). Если скобок нет, порядок действий такой: сначала инверсия, затем умножение и в последнюю очередь сложение. Так, A + BC означает A + (B·C), как и в обычной алгебре.

Аксиомы

Вся алгебра опирается на несколько аксиом. Обратите внимание, что они идут парами: одна для сложения, другая для умножения.

Аксиома	Форма для сложения	Форма для умножения
Нейтральный элемент	A + 0 = A	A · 1 = A
Переместительный закон	A + B = B + A	AB = BA
Распределительный закон	A + BC = (A + B)(A + C)	A(B + C) = AB + AC
Дополнение	A + A = 1	A · A = 0

Принцип двойственности: если равенство верно, то верно и равенство, которое получится, если поменять местами + и ·, а также 0 и 1 (не трогая ни переменные, ни черты над ними). Поэтому у каждого закона есть «близнец». Обратите внимание на распределительный закон для сложения, A + BC = (A + B)(A + C): в алгебре действительных чисел его нет, а здесь он совершенно справедлив.

Полезные законы и теоремы

Из аксиом выводятся следующие правила — именно ими вы будете пользоваться при упрощении чаще всего:

Закон	Форма для сложения	Форма для умножения
Идемпотентность	A + A = A	AA = A
Законы нуля и единицы	A + 1 = 1	A · 0 = 0
Двойное отрицание	A = A
Сочетательный закон	A + (B + C) = (A + B) + C	A(BC) = (AB)C
Поглощение	A + AB = A	A(A + B) = A
Поглощение отрицания	A + AB = A + B	A(A + B) = AB
Склеивание	AB + AB = A	(A + B)(A + B) = A
Консенсус (обобщённое склеивание)	AB + AC + BC = AB + AC	(A + B)(A + C)(B + C) = (A + B)(A + C)

Любой из этих законов можно проверить по таблице истинности: если два столбца совпадают во всех строках, равенство верно. Например, для A + AB = A: при A = 0 обе части равны 0 независимо от B; при A = 1 обе равны 1. Поглощение отрицания доказывается так: A + AB = (A + A)(A + B) = 1·(A + B) = A + B — с помощью распределительного закона для сложения.

Теоремы де Моргана

Эти две теоремы говорят, как «разорвать» длинную черту:

A · B = A + B (инверсия произведения равна сумме инверсий).
A + B = A · B (инверсия суммы равна произведению инверсий).

Практическое правило: разрывая черту, замените операцию, которая была под ней (· на + или + на ·), и поставьте отрицание над каждым членом. Это работает для любого числа переменных: ABC = A + B + C.

A	B	AB	A + B	A + B	AB
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

На языке схем теоремы де Моргана означают, что элемент NAND эквивалентен элементу OR с кружками на входах, а NOR — элементу AND с кружками на входах. На этом основан перевод любой схемы в базис только NAND или только NOR, о чём рассказано в теме «логические элементы».

Пример 1: применение теоремы де Моргана. Упростите F = AB + C.

Длинная черта накрывает сумму: AB + C = AB · C.
Разорвите черту над произведением: AB = A + B.
Результат: F = (A + B)C = AC + BC.

Проверка при A = 1, B = 1, C = 0: исходное выражение даёт 1 + 0 = 0; результат даёт (0 + 0)·1 = 0. При A = 0, B = 1, C = 0: исходное 0 + 0 = 1; результат (1 + 0)·1 = 1.

Алгебраическое упрощение шаг за шагом

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

Ищите пары членов, которые различаются только одной переменной, и применяйте склеивание.
Выносите общий множитель за скобки и ищите спрятанное A + A = 1.
Если один член содержится в другом, уберите его по закону поглощения.
Член можно продублировать (идемпотентность), чтобы объединить его с двумя разными соседями.

Пример 2. Упростите F = AB + AB + AB.

Вынесите множитель из первых двух членов: AB + AB = A(B + B) = A·1 = A.
Остаётся F = A + AB.
Поглощение отрицания: A + AB = A + B.

F = A + B. Вместо трёх элементов AND, трёхвходового OR и двух инверторов остался один-единственный элемент OR.

Пример 3: мажоритарная функция. Упростите F = ABC + ABC + ABC + ABC.

По закону идемпотентности ABC = ABC + ABC + ABC. Запишите три копии, чтобы объединить каждую с одним из соседей.
ABC + ABC = BC(A + A) = BC.
ABC + ABC = AC(B + B) = AC.
ABC + ABC = AB(C + C) = AB.

F = AB + AC + BC. Функция равна 1, когда хотя бы два из трёх входов равны 1: это схема голосования. Позже вы увидите, что это ещё и выход переноса полного сумматора.

Пример 4: распределительный закон для сложения. Упростите F = (A + B)(A + C).

Раскройте скобки: AA + AC + AB + BC = A + AC + AB + BC.
Вынесите A за скобки: A(1 + C + B) + BC.
Закон единицы: 1 + C + B = 1, поэтому остаётся A + BC.

Это и есть распределительный закон для сложения, прочитанный справа налево.

Типичные ошибки

Применять теорему де Моргана, не меняя операцию: AB — это не AB, а A + B.
«Сокращать» члены, как в обычной алгебре. В булевой алгебре нет ни вычитания, ни деления: из A + B = A + C не следует, что B = C.
Забывать о порядке действий: A + BC — это не (A + B)C.
Разрывать только часть длинной черты. Черта в AB + C относится ко всей сумме; двигайтесь от самой внешней черты внутрь.
Останавливаться слишком рано. После каждого шага проверяйте, не осталось ли чего-нибудь, что можно поглотить, или избыточного члена консенсуса.

Попробуйте в симуляторе

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

Соберите в редакторе исходную схему одного из примеров, например AB + AB + AB, с её входами и выходом.
Постройте её таблицу истинности и запишите её.
На другом выходе того же холста соберите упрощённый вариант (A + B) с теми же входами.
Переберите на входах все комбинации и убедитесь, что оба выхода всегда совпадают.
Запросите упрощённое выражение по таблице и сравните его с тем, что получили вручную.

Упражнения

Упростите F = AB + AB + AB.
Ответ
AB + AB = A. Затем A + AB = A + B (поглощение отрицания). F = A + B = AB: это NAND.
Упростите F = A + B.
Ответ
По теореме де Моргана: A · B = AB.
Упростите F = A(A + B) + B(B + C).
Ответ
По закону поглощения A(A + B) = A и B(B + C) = B. F = A + B.
Докажите теорему консенсуса: AB + AC + BC = AB + AC.
Ответ
Запишите BC = BC(A + A) = ABC + ABC. Тогда AB + ABC = AB (поглощение) и AC + ABC = AC (поглощение). Остаётся AB + AC.