Информатика · ЕНТ 2026 · 02. Информационные процессы
Логические основы компьютера
Чтобы пройти тест, нужно войти или зарегистрироваться.
Конспект
Учебниковая опора
- Кадиркулов Р. А., Нурмуханбетова Г. К. «Информатика. Учебник для 10 классов ЕМН», 10 класс, Алматыкітап баспасы, 2019, с. 41–55 (§§ 4–7)
- Wolfram MathWorld, «Implies», https://mathworld.wolfram.com/Implies.html
- Wolfram MathWorld, «Equivalent», https://mathworld.wolfram.com/Equivalent.html
- Wolfram MathWorld, «de Morgan's Laws», https://mathworld.wolfram.com/deMorgansLaws.html
- Harvey B., UC Berkeley, Computer Science Logo Style, vol. 3, ch. 2 «Discrete Mathematics», https://people.eecs.berkeley.edu/~bh/v3ch2/math.html
- Edinboro University, Math 104, «Truth Tables for the Conditional and Biconditional», https://mirkwood.cs.edinboro.edu/~bennett/class/math104/fall2010/notes/ch3/two.html
- CUNY City Tech, MAT 2571, Lesson 6 «Biconditionals, truth tables and logical equivalence», https://openlab.citytech.cuny.edu/2021-fall-mat-2571-reitz/2021/09/16/lesson-6-biconditionals-truth-tables-and-logical-equivalence/
- Сайт «Фоксфорд Экстернат», https://externat.foxford.ru/polezno-znat/algebra-logiki
- Сайт «Википедия», https://ru.wikipedia.org/wiki/Алгебра_логики
Главное
- Высказывание — повествовательное предложение, которое однозначно истинно (1) или ложно (0).
- Инверсия (НЕ, $\neg A$) меняет значение; конъюнкция (И, $A \land B$) = 1 только если оба 1; дизъюнкция (ИЛИ, $A \lor B$) = 0 только если оба 0.
- Приоритет: скобки → НЕ → И → ИЛИ.
- Таблица истинности для $n$ переменных — $2^n$ строк.
- Вентили: инвертор (1 вход), конъюнктор «&», дизъюнктор «1».
- Процессор = УУ + АЛУ + регистры; АЛУ выполняет арифметические и логические операции.
Теория
Базовые операции
| $A$ | $B$ | $\neg A$ | $A \land B$ | $A \lor B$ |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
Обозначения: НЕ — $\neg A$, $\bar{A}$, not A; И — $A \land B$, $A \cdot B$, $A \& B$, and (логическое умножение); ИЛИ — $A \lor B$, $A + B$, or (логическое сложение).
Алгоритм построения таблицы истинности
- Найти число переменных $n$; строк — $2^n$ (плюс заголовок).
- Столбцов = число переменных + число операций.
- Перебрать наборы от $00\ldots0$ до $11\ldots1$ (двоичный счёт).
- Вычислить промежуточные столбцы по приоритету, затем итоговый.
Виды формул: тавтология (в итоге только 1), противоречие (только 0), выполнимая (есть и 0, и 1).
Логические элементы (вентили). Логический 0 — низкое напряжение (около 0 В), 1 — высокое (+3,3 или +5 В).
| Элемент | Операция | Обозначение | Выход = 1, когда |
|---|---|---|---|
| Инвертор (НЕ) | $\neg A$ | прямоугольник «1» с кружком на выходе | на входе 0 |
| Конъюнктор (И) | $A \land B$ | прямоугольник «&» | на всех входах 1 |
| Дизъюнктор (ИЛИ) | $A \lor B$ | прямоугольник «1» ($\ge 1$) | хотя бы на одном входе 1 |
Конъюнктор + инвертор = элемент И-НЕ (Шеффера), универсальный: из него строится любая схема.
Выражение ↔ схема. Схема по формуле: входные линии для переменных → вентиль на каждую операцию в порядке выполнения → выход последнего элемента = $F$. Формула по схеме: идти от входов к выходу, на выходе каждого вентиля записывать выражение, ставить скобки.
Полусумматор складывает два одноразрядных числа $A$ и $B$:
- сумма $S = A \oplus B = (A \lor B) \land \neg(A \land B)$;
- перенос $P = A \land B$.
Процессор. УУ считывает команду из ОЗУ по адресу из счётчика команд, дешифрует её, формирует управляющие сигналы. АЛУ выполняет арифметику (+, −, ×, ÷) и логику (И, ИЛИ, НЕ, сдвиги). Регистры — сверхбыстрая память на кристалле: счётчик команд (адрес следующей команды), регистр команд (текущая команда), регистр флагов (ноль, перенос, знак, переполнение), регистры общего назначения.
Импликация, эквивалентность, законы де Моргана
| $A$ | $B$ | $A\to B$ | $A\leftrightarrow B$ |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
$A\to B=\neg A\lor B$. Законы де Моргана: $\neg(A\lor B)=\neg A\land\neg B$; $\neg(A\land B)=\neg A\lor\neg B$.
Другие законы алгебры логики
- Переместительный: $A\land B=B\land A$; $A\lor B=B\lor A$.
- Сочетательный: $(A\land B)\land C=A\land(B\land C)$; то же для $\lor$.
- Идемпотентность: $A\land A=A$; $A\lor A=A$.
- Двойное отрицание: $\neg\neg A=A$.
- Исключённое третье: $A\lor\neg A=1$; противоречие: $A\land\neg A=0$.
- С константами: $A\land 1=A$; $A\land 0=0$; $A\lor 0=A$; $A\lor 1=1$.
Примеры
- $F = (\neg A \lor B) \land C$ при $A = 1, B = 0, C = 1$. $\neg A = 0$; $0 \lor 0 = 0$; $0 \land 1 = 0$. Ответ: $F = 0$.
- Таблица для $F = \neg A \lor (A \land B)$.
| $A$ | $B$ | $\neg A$ | $A \land B$ | $F$ |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
$F$ ложна только при $A = 1, B = 0$ — формула выполнимая (равносильна импликации $A \to B$). 3. Схема для $F = \neg(A \land B) \lor C$. $A, B$ → конъюнктор → инвертор; его выход и $C$ → дизъюнктор → $F$. 4. Сколько строк в таблице истинности для 4 переменных? $2^4 = 16$.
# перебор всех наборов и таблица истинности F = not A or (A and B)
for A in (0, 1):
for B in (0, 1):
F = int((not A) or (A and B))
print(A, B, F)
Типичные ошибки на ЕНТ
- Выполняют ИЛИ раньше И: приоритет НЕ → И → ИЛИ.
- Считают, что дизъюнкция 1 только при обеих единицах — это конъюнкция.
- Для $n$ переменных пишут $2n$ строк вместо $2^n$.
- Путают обозначения вентилей: «&» — И, «1» — ИЛИ, кружок на выходе — НЕ.
- В полусумматоре путают: перенос — конъюнкция, сумма — исключающее ИЛИ.
Самопроверка
- Когда конъюнкция ложна? — Если хотя бы один операнд равен 0.
- Сколько входов у инвертора? — Один.
- Как называется формула, у которой в итоговом столбце только 1? — Тавтология (тождественно-истинная).
- Чему равно $1 \lor 0 \land 0$? — 1 (сначала И: $0 \land 0 = 0$, затем $1 \lor 0 = 1$).
- Какой регистр хранит адрес следующей команды? — Счётчик команд.