Логика — это алгебра. Значения {0, 1} со связками ∧, ∨, ¬ образуют булеву алгебру со своими законами. А каждая связка — это вентиль; из вентилей собираются схемы, и так логика становится вычислением в железе. Здесь сходятся алгебра из главы I и логика из главы II.
Запишем истину как 1, ложь как 0. Тогда «и» становится операцией $\wedge$, «или» — $\vee$, «не» — $\neg$, и у них оказываются законы, как у сложения и умножения. Это булева алгебра — алгебраическая структура на двух элементах. Логика из главы II и алгебра из главы I здесь — одно и то же.
$a\vee 0=a,\quad a\wedge 1=a,\qquad a\vee\neg a=1,\quad a\wedge\neg a=0$
$a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c)$
$\neg(a\wedge b)=\neg a\vee\neg b,\qquad \neg(a\vee b)=\neg a\wedge\neg b$
Они позволяют упрощать выражения, не меняя их значения — то есть оптимизировать логику (и схемы) алгебраически, как многочлены.
«Не (A и B)» = «не A или не B». Это ежедневный инструмент при работе с условиями в коде и при проектировании схем.
Вот и вся связь: высказывания → булева алгебра → вентили → схемы → вычисление. Логика — не отвлечённая дисциплина, а буквальный чертёж того, как машина считает. Эта же логика, поднятая на уровень программ, даёт корректность — о доказательстве программ см. соседнее углубление.
Углубление: логика Хоара — доказательство программчитать →Истина и ложь — это 1 и 0; связки — операции булевой алгебры со своими законами; каждая связка — вентиль; из вентилей собираются схемы, которые считают. Так алгебра из главы I и логика из главы II встречаются в самом основании вычислений.