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

Переменные и операции
Логическая переменная принимает только значения 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}}$ сначала считаешь $x_1\vee x_2$ и отрицаешь, потом отрицаешь $x_3$, потом берешь И, а в конце отрицаешь результат. Элементов здесь три: ИЛИ-НЕ, И-НЕ и НЕ.

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

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

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

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

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

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