Алгебра логики: функции, логические элементы, схемы

Переменные и операции
Логическая переменная принимает только значения 0 и 1. Основные операции:

• отрицание (НЕ): $\overline{x}$ меняет значение, $\overline{0} = 1$, $\overline{1} = 0$
• конъюнкция (И): $x \& y$ равна 1 только когда обе переменные равны 1
• дизъюнкция (ИЛИ): $x \vee y$ равна 0 только когда обе равны 0

Производные элементы, которые спрашивают в тестах:

• И-НЕ (NAND): $\overline{x \& y}$, то есть И с последующим отрицанием
• ИЛИ-НЕ (NOR): $\overline{x \vee y}$, то есть ИЛИ с последующим отрицанием

Порядок операций
Сначала отрицание, потом И, потом ИЛИ; скобки и черта сверху меняют порядок. Длинная черта над всем выражением означает, что отрицание применяется последним, после того как посчитано то, что под ней.
В функции $f(x_1,x_2,x_3) = \overline{\overline{x_1 \vee x_2}\ \&\ \overline{x_3}}$ сначала считаешь и отрицаешь, потом отрицаешь потом берешь И, а в конце отрицаешь результат. Элементов здесь три: ИЛИ-НЕ, И-НЕ и НЕ.

Таблица истинности
У функции от $n$ переменных $2^n$ строк: 4 строки для двух переменных, 8 для трех. Ее пишешь, когда требуется вид функции или когда нужно проверить схему.

Законы де Моргана
$\overline{x \& y} = \overline{x} \vee \overline{y}$ и $\overline{x \vee y} = \overline{x} \& \overline{y}$. Когда раскрываешь длинную черту, операция под ней меняется: И становится ИЛИ и наоборот. Другие полезные равенства:

Как читать логическую схему
В схемах из тестов прямоугольник с «1» — это элемент ИЛИ, прямоугольник с «&» — элемент И, а кружок на выходе означает отрицание. Идешь от входов к выходу и надписываешь на каждой линии полученное выражение.

Комбинационные и последовательностные схемы

• комбинационная: выход зависит только от текущих входов. Сумматор, вычитатель, мультиплексор, шифратор и дешифратор комбинационные.
• последовательностная: выход зависит еще и от предыдущего состояния, то есть у схемы есть память. Триггеры RS, счетчики и регистры последовательностные.

RS-триггер хранит одно двоичное значение, то есть один бит, а не целую последовательность: поэтому утверждение «RS-триггер предназначен для хранения двоичной последовательности» ложно. Для последовательности нужен регистр, то есть несколько триггеров.