Булева алгебра: от условия в коде к логической схеме

Теория

Булева функция $F(A, B, C)$ принимает значения 0 и 1 и строится из операций конъюнкции ($\land$, И), дизъюнкции ($\lor$, ИЛИ), отрицания ($\lnot$, НЕ) и исключающего ИЛИ ($\oplus$). Функция трёх переменных полностью задаётся таблицей истинности из $2^3 = 8$ строк.

СДНФ. Совершенная дизъюнктивная нормальная форма составляется по строкам таблицы, где $F = 1$: для каждой такой строки записывается конъюнкция всех переменных (с отрицанием, если переменная равна 0), а конъюнкции объединяются дизъюнкцией. Например, для $F = A \oplus B$:

$$ F = (\lnot A \land B) \lor (A \land \lnot B). $$

Любая булева функция представима в виде СДНФ, поэтому набор $\{\land, \lor, \lnot\}$ функционально полон.

Законы де Моргана позволяют переносить отрицание через скобки:

$$ \lnot (A \land B) = \lnot A \lor \lnot B, \qquad \lnot (A \lor B) = \lnot A \land \lnot B . $$

Полусумматор складывает два бита: сумма $S = A \oplus B$, перенос $P = A \land B$. Полный сумматор добавляет перенос из младшего разряда, и цепочка из 64 сумматоров складывает 64-битные числа.

На схемах по ГОСТ 2.743 элемент И обозначается символом «&», ИЛИ — «1», исключающее ИЛИ — «=1», отрицание — кружком на выходе.