Эльвин говорит друзьям: «Если в субботу будет хорошая погода и я закончу уроки, пойду на Приморский бульвар». В этой фразе два условия, соединённых словом «и». Компьютер принимает решения точно так же — соединяет простые условия логическими операциями. Только вместо «да» и «нет» он использует 1 и 0.
Высказывания: истина и ложь
ВысказываниеОпределение
Утверждение, о котором можно однозначно сказать, истинно оно или ложно. Истинному высказыванию приписывают значение 1, ложному — 0.
Например, «Баку — столица Азербайджана» — истинное высказывание (1), а «5 > 8» — ложное (0). «Какая сегодня погода?» — вовсе не высказывание: вопрос не может быть ни истинным, ни ложным.
Чтобы читать дальше, зарегистрируйся бесплатно
Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.
Основные логические операции
- НЕ (инверсия, NOT) меняет значение на противоположное: НЕ 1 = 0, НЕ 0 = 1.
- И (конъюнкция, AND) даёт 1, только когда оба высказывания истинны.
- ИЛИ (дизъюнкция, OR) даёт 1, когда истинно хотя бы одно высказывание.
- Исключающее ИЛИ (XOR) даёт 1, только когда истинно ровно одно высказывание, то есть когда входы различны.
Эти операции легко представить с обычными выключателями и лампой. Замкнутый выключатель — 1, разомкнутый — 0; горящая лампа — 1, погасшая — 0.
| Операция | Картинка из жизни |
|---|---|
| И (AND) | Два выключателя друг за другом (последовательно): лампа горит, только когда замкнуты оба |
| ИЛИ (OR) | Два выключателя рядом (параллельно): лампа горит, если замкнут хотя бы один |
| НЕ (NOT) | Кнопка «наоборот»: нажмёшь — свет гаснет, отпустишь — загорается |
| XOR | Свет на лестнице: выключатели внизу и наверху, и щелчок любого из них меняет состояние лампы |
Таблица, которая показывает результат операции для всех возможных случаев, называется таблицей истинности. Для двух входов существует всего 4 случая:
| A | B | A И B | A ИЛИ B | A XOR B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Посчитай случаи
У n входов 2ⁿ случаев: два входа — 4 строки, три входа — 8 строк.
Запиши строки двоичным счётом
Записывай входы так, будто считаешь в двоичной системе: 00, 01, 10, 11 — так ни один случай не потеряется.
Заполняй столбец за столбцом
И работает как обычное умножение: 1 · 1 = 1, остальное даёт 0. ИЛИ отвечает на вопрос «есть ли хотя бы одна 1?»
| A | НЕ A |
|---|---|
| 0 | 1 |
| 1 | 0 |
В математике и во многих учебниках эти операции записывают символами: A ∧ B (И), A ∨ B (ИЛИ), ¬A (НЕ), A ⊕ B (исключающее ИЛИ). Для них выполняются законы алгебры логики, и каждый закон можно проверить таблицей истинности из 4 или 8 строк. Одни похожи на обычную алгебру, другие — нет: например, у второго распределительного закона нет аналога для чисел (a + b · c ≠ (a + b) · (a + c)).
| Закон | Формула |
|---|---|
| Переместительный | A ∧ B = B ∧ A, A ∨ B = B ∨ A |
| Распределительный | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) |
| Законы де Моргана | ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B |
| Поглощение | A ∨ (A ∧ B) = A, A ∧ (A ∨ B) = A |
| Дополнение и двойное отрицание | A ∨ ¬A = 1, A ∧ ¬A = 0, ¬¬A = A |
| Идемпотентность | A ∧ A = A, A ∨ A = A |
Логические элементы
Внутри компьютера логические операции выполняют логические элементы (вентили). Это крошечные электронные схемы из транзисторов: на входы подаются сигналы 0 или 1, а на выходе получается результат. В современном процессоре миллиарды транзисторов, и собранные из них элементы складывают числа, сравнивают их и хранят в памяти.
Интерактив
Кроме основных элементов широко используются их сочетания: И-НЕ (NAND) инвертирует результат И, а ИЛИ-НЕ (NOR) — результат ИЛИ. Интересно, что из одних только элементов И-НЕ можно собрать любую другую логическую схему.
Есть ещё два элемента. И-НЕ (NAND) означает «не оба сразу»: он переворачивает ответ И. ИЛИ-НЕ (NOR) означает «ни один»: он переворачивает ответ ИЛИ. Интересно, что из одних только элементов И-НЕ можно собрать любую другую логическую схему — как построить целый дом из кирпичей одного вида.
| A | B | A И B | NAND | NOR |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Всё из NAND
Задача
Используя только элементы NAND, постройте НЕ, И, ИЛИ и XOR. Сколько элементов нужно для XOR?
Показать решениеСкрыть решение
Решение
A И B = НЕ NAND(A, B) = NAND(N, N), где N = NAND(A, B).
A ИЛИ B = NAND(¬A, ¬B) — по закону де Моргана ¬(¬A ∧ ¬B) = A ∨ B.
XOR: пусть N = NAND(A, B); тогда A ⊕ B = NAND(NAND(A, N), NAND(B, N)) — всего 4 элемента. Таблица истинности это подтверждает: во всех четырёх случаях результат совпадает с A ⊕ B.
Благодаря этому свойству микросхемы часто собирают из элементов одного вида.
Логические выражения и двоичное сложение
Операции соединяются в логические выражения. Если скобок нет, сначала выполняется НЕ, затем И, а последним — ИЛИ; это похоже на то, как в математике умножение выполняется раньше сложения.
Выражение без скобок читай как в математике: НЕ похоже на минус перед буквой и выполняется первым, И похоже на умножение, а ИЛИ — на сложение. Поэтому НЕ A ИЛИ B И C читается как (НЕ A) ИЛИ (B И C) — как −a + b · c.
Вычисли по порядку
Задача
Найди значение выражения НЕ A ИЛИ B И C при A = 1, B = 1, C = 0.
Показать решениеСкрыть решение
Решение
2) B И C = 1 И 0 = 0.
3) 0 ИЛИ 0 = 0.
Порядок: НЕ → И → ИЛИ.
Пример: значение выражения
Задача
Найди значение выражения (A ИЛИ B) И НЕ C при A = 1, B = 0, C = 1.
Показать решениеСкрыть решение
Решение
2) НЕ C = НЕ 1 = 0.
3) 1 И 0 = 0.
Выражение ложно, так как один из входов операции И равен 0.
Бывает и обратная задача: дана таблица истинности, нужно найти формулу. Универсальный способ: для каждой строки, где результат равен 1, соедини переменные этой строки знаком ∧ (перед переменной, равной 0, поставь ¬), соедини такие слагаемые знаком ∨ и упрости по законам алгебры логики. В таблице с n переменными 2ⁿ строк, поэтому различных функций 2^(2ⁿ): для двух переменных — 16.
От таблицы к формуле
Задача
Функция F задана так: F(0, 0) = 1, F(0, 1) = 1, F(1, 0) = 0, F(1, 1) = 1. Найдите для F самую короткую формулу.
Показать решениеСкрыть решение
Решение
F = (¬A ∧ ¬B) ∨ (¬A ∧ B) ∨ (A ∧ B).
В первых двух слагаемых выносим ¬A за скобки: ¬A ∧ (¬B ∨ B) = ¬A ∧ 1 = ¬A.
F = ¬A ∨ (A ∧ B) = (¬A ∨ A) ∧ (¬A ∨ B) = ¬A ∨ B (второй распределительный закон).
Эта функция — импликация A → B («если A, то B»): она ложна только при A = 1, B = 0.
Как компьютер складывает? Полусумматор
Задача
Нужно сложить два бита A и B. Какие элементы дают цифру суммы (S) и перенос в следующий разряд (C)?
Показать решениеСкрыть решение
Решение
0 + 0 = 00₂ → S = 0, C = 0
0 + 1 = 01₂ → S = 1, C = 0
1 + 0 = 01₂ → S = 1, C = 0
1 + 1 = 10₂ → S = 0, C = 1
Столбец S совпадает с таблицей исключающего ИЛИ, а столбец C — с таблицей И.
Значит, S = A XOR B, C = A И B. Соединяя такие схемы, процессор складывает числа любой длины.
Полусумматор умеет складывать только самый правый разряд: он не учитывает перенос из предыдущего разряда. У полного сумматора три входа — A, B и входящий перенос Cin: S = A ⊕ B ⊕ Cin, Cout = (A ∧ B) ∨ (Cin ∧ (A ⊕ B)). Он собирается из двух полусумматоров и одного элемента ИЛИ. Соединив цепочкой 8 полных сумматоров, получим схему, складывающую 8-битные числа, — простейшую часть арифметико-логического устройства (АЛУ) процессора.
| A | B | Cin | S | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Интерактив
print('A B | AND OR XOR')
for a in (0, 1):
for b in (0, 1):
print(f'{a} {b} | {a & b} {a | b} {a ^ b}')Ожидаемый результат
A B | AND OR XOR 0 0 | 0 0 0 0 1 | 0 1 1 1 0 | 0 1 1 1 1 | 1 1 0
& выполняет И, | — ИЛИ, а ^ — исключающее ИЛИ. Программа сама строит всю таблицу истинности.Запомни
- Высказывание либо истинно (1), либо ложно (0).
- И даёт 1, только когда оба входа равны 1; ИЛИ — когда хотя бы один вход равен 1.
- НЕ меняет значение на противоположное, а XOR даёт 1, когда входы различны.
- Без скобок порядок такой: НЕ, затем И, затем ИЛИ.
- Логические элементы строятся из транзисторов; XOR и И вместе складывают два бита.