Логические основы компьютера

Разбор темы

Высказывания и логические значения 10 класс

Высказывание — повествовательное предложение, которое либо истинно, либо ложно: «$2 + 2 = 4$» (истина), «Солнце вращается вокруг Земли» (ложь).

Не являются высказываниями вопросы, восклицания, приказы («Закройте дверь!») и предложения с неизвестной переменной: «$x > 3$» станет высказыванием, только когда мы подставим конкретное $x$.

Истину обозначают 1 (True), ложь — 0 (False). Простые высказывания обозначают буквами A, B, C, а из них с помощью связок «и», «или», «не», «если…то» строят составные.

Основные операции: НЕ, И, ИЛИ 10 класс

Инверсия $\neg A$ (НЕ, $\overline{A}$, not) меняет значение на противоположное.

Конъюнкция $A \land B$ (И, $A \cdot B$, &, and) равна 1 только когда $A = 1$ и $B = 1$. Её называют логическим умножением: значение совпадает с произведением $A\cdot B$.

Дизъюнкция $A \lor B$ (ИЛИ, $A + B$, |, or) равна 0 только когда $A = 0$ и $B = 0$. Логическое сложение: $1 \lor 1 = 1$, а не 2.

A B | not A | A and B | A or B
0 0 |   1   |    0    |   0
0 1 |   1   |    0    |   1
1 0 |   0   |    0    |   1
1 1 |   0   |    1    |   1

Пример из жизни: «Пойду гулять, если нет дождя И я сделал уроки» — $\neg D \land U$.

Импликация, эквивалентность, исключающее ИЛИ 10–11 класс

Импликация $A \to B$ («если A, то B») ложна в единственном случае: из истины следует ложь ($1 \to 0 = 0$). Из лжи следует что угодно: $0 \to 0 = 1$, $0 \to 1 = 1$. Формула для упрощения: $A \to B = \neg A \lor B$.

Эквивалентность $A \equiv B$ равна 1, когда значения совпадают ($0 \equiv 0 = 1$, $1 \equiv 1 = 1$).

Исключающее ИЛИ $A \oplus B$ (XOR, сложение по модулю 2) — противоположность эквивалентности: 1, когда значения разные. $1 \oplus 1 = 0$ — как последняя цифра суммы $1 + 1 = 10_2$.

A B | A→B | A≡B | A⊕B
0 0 |  1  |  1  |  0
0 1 |  1  |  0  |  1
1 0 |  0  |  0  |  1
1 1 |  1  |  1  |  0

Порядок операций и построение таблицы истинности 10 класс

Приоритет: скобки → НЕ → И → ИЛИ → импликация → эквивалентность. Значит, $\neg A \lor B \land C$ читается как $(\neg A) \lor (B \land C)$.

Алгоритм построения таблицы: 1) посчитать число переменных $n$, строк будет $2^n$ (2 переменные — 4 строки, 3 — 8, 4 — 16); 2) выписать все наборы по порядку, как двоичные числа от $0$ до $2^n - 1$ (000, 001, 010, …, 111); 3) сделать столбцы для промежуточных действий в порядке приоритета; 4) вычислить итоговый столбец.

Пример: $F = \neg A \lor B \land C$. Сначала столбец $\neg A$, потом $B \land C$, потом их дизъюнкция. Для $A = 1, B = 1, C = 0$: $\neg A = 0$, $B \land C = 0$, $F = 0$.

В задачах «по фрагменту таблицы определите выражение» подставляйте строки фрагмента в каждый вариант ответа и отбрасывайте варианты, которые дают хотя бы одно несовпадение.

Законы алгебры логики и упрощение выражений 10–11 класс

Константы: $A \land 1 = A$, $A \land 0 = 0$, $A \lor 0 = A$, $A \lor 1 = 1$. Идемпотентность: $A \land A = A$, $A \lor A = A$.

Противоречие и исключённое третье: $A \land \neg A = 0$, $A \lor \neg A = 1$. Двойное отрицание: $\neg\neg A = A$.

Переместительный и сочетательный законы — как в алгебре. Распределительный работает в обе стороны: $A \land (B \lor C) = A \land B \lor A \land C$ и $A \lor B \land C = (A \lor B) \land (A \lor C)$.

Законы де Моргана: $\neg(A \land B) = \neg A \lor \neg B$, $\neg(A \lor B) = \neg A \land \neg B$ («отрицание переходит внутрь, И меняется на ИЛИ»).

Поглощение: $A \lor A \land B = A$, $A \land (A \lor B) = A$. Склеивание: $A \land B \lor A \land \neg B = A$, $(A \lor B) \land (A \lor \neg B) = A$. Полезно также $A \lor \neg A \land B = A \lor B$.

Порядок упрощения: убрать $\to$ и $\equiv$ по формулам, внести отрицания внутрь по де Моргану, затем применять поглощение и склеивание. Результат проверяйте таблицей истинности.

Логические элементы и схемы 10 класс

Логический элемент (вентиль) — электронная схема, которая выполняет одну логическую операцию над сигналами 0 и 1. Основные: конъюнктор (И, на схемах знак &), дизъюнктор (ИЛИ, знак 1 или $\geq 1$), инвертор (НЕ, кружок на выходе).

Есть также И-НЕ ($\neg(A \land B)$) и ИЛИ-НЕ ($\neg(A \lor B)$): из одних только элементов И-НЕ можно собрать любую схему.

Схема → формула: идём от входов к выходу и записываем выражение на выходе каждого элемента. Если на входы элемента И подаются A и выход инвертора от B, на выходе $A \land \neg B$.

Формула → схема: последняя выполняемая операция — это элемент на выходе; его входы — подвыражения. Для $F = (A \lor B) \land \neg C$ нужны дизъюнктор (A, B), инвертор (C) и конъюнктор на выходе.

Чтобы найти выход схемы при заданных входах, вычисляйте элементы по порядку, подписывая 0 или 1 на каждом проводе.

Сумматор, триггер и процессор 10–11 класс

Полусумматор складывает два бита A и B: сумма $S = A \oplus B$, перенос $P = A \land B$. Для $1 + 1$: $S = 0$, $P = 1$, то есть $10_2$.

Полный (одноразрядный) сумматор учитывает ещё перенос из младшего разряда: $S = A \oplus B \oplus P_{\text{вх}}$, $P = A \land B \lor (A \oplus B) \land P_{\text{вх}}$. Цепочка из $n$ сумматоров складывает $n$-битные числа.

Триггер — схема из логических элементов с обратной связью, которая хранит 1 бит (два устойчивых состояния). RS-триггер имеет входы S (установить 1) и R (сбросить в 0). Из триггеров строят регистры и кэш-память процессора.

В процессоре арифметико-логическое устройство (АЛУ) выполняет вычисления и логические операции (в его основе сумматоры), устройство управления (УУ) координирует выполнение команд, регистры хранят данные, с которыми работает процессор.

Логика в Python и задачи ЕНТ 10–11 класс

Операторы: not, and, or; приоритет not > and > or, а сравнения (<, ==, !=) выполняются раньше всех логических. not a > b означает not (a > b).

print(not True or True and False)   # False
print(True or False and False)       # True
print((True or False) and False)     # False

Короткое вычисление: or возвращает первый истинный операнд, and — первый ложный (или последний): 0 or 5 → 5, 3 and 7 → 7. Ложными считаются 0, пустая строка и пустой список.

Для 0/1 и True/False: a == b — эквивалентность, a != b и a ^ b — XOR, (not a) or b — импликация. Операторы &, |, ^ работают поразрядно над целыми: 12 & 10 → 8.

Типовая задача ЕНТ: «Для какого числа X истинно НЕ(X > 5) И (X нечётное)?» Переводим: $X \leq 5$ и $X$ нечётно, затем проверяем варианты ответа.