Логические схемы и решение логических уравнений
От алгебры логики — к «железу»: как операции превращаются в вентили, и как находить решения логических уравнений.
Логический вентиль (элемент) — простейшая электронная схема, реализующая одну логическую операцию над входными сигналами.
Зачем это нужно
Процессор, память, любая цифровая микросхема собраны из миллиардов крошечных вентилей — элементов И, ИЛИ, НЕ. Понимание логических схем связывает абстрактную алгебру логики с реальным «железом» и объясняет, как из простых деталей рождается сумматор, а из сумматоров — арифметика. А логические уравнения (найти, при каких значениях переменных выражение истинно) — отдельный, стабильно сложный тип заданий ЕГЭ, где умение перебирать и рассуждать решает всё.
Этот урок — кульминация всего раздела логики, потому что он замыкает цепочку «абстракция → железо». В первом уроке мы научились вычислять выражения, во втором — упрощать их, а теперь увидим, как выражение превращается в физическую схему и наоборот. Это удивительный мост: одна и та же формула (A ∧ B) ∨ ¬C существует сразу в трёх ипостасях — как строчка в таблице истинности, как набор соединённых вентилей на кристалле и как условие в программе. Инженер свободно переходит между этими тремя языками. Когда вы поймёте, что сложение чисел — это просто хитро соединённые вентили И и исключающего ИЛИ, у вас исчезнет ощущение, что компьютер «волшебный»: внутри он целиком собран из логики, которую вы уже умеете читать.
Вентили: кирпичики цифровой техники
Каждой логической операции соответствует свой вентиль. У него есть входы (сигналы 0 или 1) и один выход. Смоделируем базовые вентили функциями и заодно соберём из них вентиль И-НЕ (NAND) — он знаменит тем, что из одних только NAND можно собрать вообще любую схему:
def gate_not(a): return 0 if a else 1
def gate_and(a, b): return 1 if (a and b) else 0
def gate_or(a, b): return 1 if (a or b) else 0
def gate_nand(a, b): return gate_not(gate_and(a, b)) # И, затем НЕ
print("a b | AND OR NAND")
for a in (0, 1):
for b in (0, 1):
print(f"{a} {b} | {gate_and(a,b)} {gate_or(a,b)} {gate_nand(a,b)}")Вывод:
a b | AND OR NAND 0 0 | 0 0 1 0 1 | 0 1 1 1 0 | 0 1 1 1 1 | 1 1 0
Читаем схему: от входов к выходу
Схема — это вентили, соединённые проводами: выход одного идёт на вход другого. Чтобы найти выход схемы, вычисляют сигналы слой за слоем, от входов к выходу. Рассмотрим схему, реализующую F = (A ∧ B) ∨ ¬C: сначала вентиль И над A и B, параллельно вентиль НЕ над C, затем их выходы — на вентиль ИЛИ. Соберём эту цепочку в коде и построим таблицу:
def gate_not(a): return 0 if a else 1
def gate_and(a, b): return 1 if (a and b) else 0
def gate_or(a, b): return 1 if (a or b) else 0
def scheme(a, b, c):
w1 = gate_and(a, b) # выход первого вентиля
w2 = gate_not(c) # выход вентиля НЕ
return gate_or(w1, w2) # финальное ИЛИ
print("A B C | F")
for a in (0, 1):
for b in (0, 1):
for c in (0, 1):
print(f"{a} {b} {c} | {scheme(a, b, c)}")Вывод:
A B C | F 0 0 0 | 1 0 0 1 | 0 0 1 0 | 1 0 1 1 | 0 1 0 0 | 1 1 0 1 | 0 1 1 0 | 1 1 1 1 | 1
Схема выдаёт 1 всюду, где C=0 (благодаря ¬C), а также в строке A=B=1. Это и есть «чтение» схемы через её модель.
Полусумматор: логика, которая считает
Самое впечатляющее — что из логики получается арифметика. Полусумматор складывает два бита и выдаёт сумму и перенос. Сумма (младший бит результата) — это исключающее ИЛИ входов, а перенос — это И. Проверим, что наша «схема» действительно складывает биты:
def half_adder(a, b):
summa = a ^ b # бит суммы (XOR)
carry = a & b # бит переноса (AND)
return summa, carry
print("a b | сумма перенос | проверка a+b")
for a in (0, 1):
for b in (0, 1):
s, c = half_adder(a, b)
print(f"{a} {b} | {s} {c} | {c}{s} = {2*c + s} (a+b={a+b})")Вывод:
a b | сумма перенос | проверка a+b 0 0 | 0 0 | 00 = 0 (a+b=0) 0 1 | 1 0 | 01 = 1 (a+b=1) 1 0 | 1 0 | 01 = 1 (a+b=1) 1 1 | 0 1 | 10 = 2 (a+b=2)
Вот так из двух вентилей рождается сложение — а из цепочки полусумматоров строится арифметико-логическое устройство процессора.
Решение логических уравнений перебором
Логическое уравнение — это требование «выражение = 1»; нужно найти все наборы переменных, при которых оно выполняется. Для нескольких переменных надёжнее всего перебор всех 2ⁿ комбинаций. Решим уравнение (A → B) ∧ (B → C) = 1 и посчитаем количество решений:
from itertools import product
def impl(x, y):
return (not x) or y
solutions = []
for a, b, c in product((0, 1), repeat=3):
if impl(a, b) and impl(b, c): # выражение равно 1
solutions.append((a, b, c))
print("Решения (A, B, C):")
for s in solutions:
print(" ", s)
print("Всего решений:", len(solutions))Вывод:
Решения (A, B, C): (0, 0, 0) (0, 0, 1) (0, 1, 1) (1, 1, 1) Всего решений: 4
Попробуй сам
Решите уравнение посложнее и убедитесь, что перебор не пугается количества переменных. Найдём все наборы, при которых (A ∨ B) ∧ (¬B ∨ C) ∧ (¬A ∨ ¬C) истинно:
from itertools import product
count = 0
for a, b, c in product((0, 1), repeat=3):
expr = (a or b) and ((not b) or c) and ((not a) or (not c))
if expr:
count += 1
print("решение:", (a, b, c))
print("Число решений:", count)Вывод:
решение: (0, 1, 1) решение: (1, 0, 0) Число решений: 2
Частые ошибки
- Вычисляют схему «сразу», минуя промежуточные провода. Надёжнее идти слой за слоем: сначала ранние вентили, потом поздние.
- Путают сумму и перенос в полусумматоре. Сумма — это XOR, перенос — это AND, не наоборот.
- При решении уравнений теряют комбинации. Полный перебор гарантирует, что ни один набор не пропущен.
- Считают, что у уравнения одно решение. Их может быть от нуля (противоречие) до 2ⁿ (тавтология).
Итоги
- Вентиль реализует одну операцию; из вентилей И, ИЛИ, НЕ собирается любая схема (а из одних NAND — тем более).
- Выход схемы вычисляют послойно, от входов к выходу.
- Полусумматор: сумма = XOR, перенос = AND — так логика превращается в арифметику.
- Логическое уравнение решают перебором всех 2ⁿ наборов; решений может быть от 0 до 2ⁿ.
