Базовый CS с нуля
Булева логика
Ты уже знаешь, что бит — это либо 0, либо 1. Теперь подумай вот о чём: эти два значения
могут означать нечто большее, чем просто числа. Они могут означать истину и ложь.
Единица в переменной isLoggedIn означает «да, этот пользователь вошёл в систему».
Ноль в fileExists означает «нет, этот файл не существует».
Как только бит несёт значение истинности, нужны операции, работающие с этими значениями:
способы спросить «верны ли оба условия?», «верно ли хотя бы одно?» или «сделать это из
истины ложью?». Это операции булевой логики, и они лежат в основе каждого решения,
которое когда-либо принимает компьютер — от простого оператора if до миллиарда
транзисторов, параллельно определяющих, по какому адресу памяти обратиться.
После этого урока ты сможешь объяснить, что такое булево значение, читать и строить таблицы истинности для операций И, ИЛИ и НЕ, вычислять любую комбинацию этих операций для заданных входов и объяснять на концептуальном уровне, почему И, ИЛИ и НЕ вместе достаточны для выражения любого возможного правила истина/ложь.
Истина и ложь как бит. Булево значение — это значение, которое может быть
только истинным или ложным, без промежуточных вариантов. В аппаратуре и большинстве
языков программирования истина хранится как 1, а ложь как 0. (Некоторые языки
используют тип boolean или bool; другие просто используют целое число и считают 0
ложью, а любое ненулевое значение — истиной.)
Название происходит от имени Джорджа Буля (1815–1864) — математика, формализовавшего систему алгебры, работающей со значениями истинности вместо чисел. В его алгебре 1 обозначает истину, 0 — ложь, а операции отображают значения истинности в значения истинности. Именно это и нужно компьютеру: состояние транзистора — либо высокое (1, истина), либо низкое (0, ложь), а логические схемы комбинируют эти состояния для принятия решений.
Ключевое озарение: бит уже является булевым значением. Читая бит, ты можешь интерпретировать его как число 0 или 1, или как значение истинности «ложь» или «истина». Аппаратура хранит одно и то же; смысл зависит от того, как твоя программа это интерпретирует.
Таблица истинности: полное определение операции. Таблица истинности перечисляет все возможные комбинации входов и результат, который операция выдаёт для каждой из них. Для операций над значениями истинности каждый вход — либо 0 (ложь), либо 1 (истина), поэтому два входа дают 2 × 2 = 4 строки. Один вход даёт 2 строки.
Таблица истинности — это не просто удобная сводка, она и есть определение операции. Две операции совпадают тогда и только тогда, когда их таблицы истинности идентичны. Это делает таблицы истинности главным инструментом рассуждений о булевой логике: чтобы доказать эквивалентность двух выражений, достаточно показать, что они дают одинаковый результат в каждой строке.
НЕ: простейшая операция. НЕ принимает один вход и инвертирует его. Если вход истинен (1), результат — ложь (0). Если вход ложен (0), результат — истина (1). Это всё, что она делает — переворачивает.
| Вход A | НЕ A |
|---|---|
| 0 | 1 |
| 1 | 0 |
В коде это записывается как !a (большинство языков) или not a (Python). В цифровых
схемах это называется инвертором. На схемах его обозначают маленьким кружком на
выходе.
И: истина только когда оба входа истинны. И принимает два входа и выдаёт 1 тогда и только тогда, когда оба входа равны 1. Если хотя бы один вход (или оба) равен 0, результат — 0.
| Вход A | Вход B | A И B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
В коде: a && b или a and b. Аналог в обычном языке: «A истинно и B истинно».
Только одна строка из четырёх даёт 1 — нижняя, где оба входа равны 1. Это совпадает
с повседневным значением слова «и»: фраза «идёт дождь и у меня есть зонт» истинна
только когда обе части верны.
Конкретный пример: isLoggedIn И hasPermission равно 1 только когда пользователь
и вошёл в систему, и имеет нужное разрешение. Невыполнение любого из условий
достаточно для отказа в доступе.
ИЛИ: истина когда хотя бы один вход истинен. ИЛИ принимает два входа и выдаёт 1, если хотя бы один вход равен 1. Результат равен 0 только когда оба входа — 0.
| Вход A | Вход B | A ИЛИ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
В коде: a || b или a or b. Три строки из четырёх дают 1; только верхняя строка
(оба входа ложны) даёт 0. Это включающее или — «A или B или оба».
Конкретный пример: isCacheHit ИЛИ isPreloaded равно 1, если данные доступны любым
из этих путей. Запрашивающий не знает, какой путь доставил данные, — любой подходит.
Граничные случаи
Булево ИЛИ в вычислениях — это включающее или (истинно, если одно или оба условия верны). В обычном языке «или» часто означает исключающее или (XOR) — «суп или салат» обычно подразумевает одно из двух, но не оба сразу. Операция XOR истинна только когда входы различаются (A=0 B=1 даёт 1; A=1 B=0 даёт 1; A=0 B=0 даёт 0; A=1 B=1 даёт 0). XOR — полезная и широко используемая операция, но это не примитив из трёх основных: она строится из И, ИЛИ и НЕ.
Комбинирование операций. В реальных программах И, ИЛИ и НЕ комбинируются в более сложные выражения. Вычисление следует приоритету операторов: сначала НЕ, затем И, затем ИЛИ (как умножение перед сложением в арифметике). Скобки изменяют приоритет.
Рассмотрим: НЕ A ИЛИ (B И C). При A=1, B=1, C=0:
- НЕ A = НЕ 1 = 0
- B И C = 1 И 0 = 0
- 0 ИЛИ 0 = 0
При A=0, B=1, C=1:
- НЕ A = НЕ 0 = 1
- B И C = 1 И 1 = 1
- 1 ИЛИ 1 = 1 (ИЛИ двух единиц по-прежнему даёт 1)
Составные выражения постоянно встречаются в коде: проверки контроля доступа, правила инвалидации кеша, логика повторных попыток, валидация входных данных — всё это сводится к булевым выражениям, вычисляемым над значениями истинности в один бит.
Почему это работает
Почему И, ИЛИ и НЕ достаточны? Утверждение: любое возможное правило вычисления результата истина/ложь из любого числа входов — сколь угодно сложное — можно выразить только через И, ИЛИ и НЕ. Почему?
Любая таблица истинности с N входами содержит 2^N строк. Для каждой строки, где результат равен 1, можно написать одно выражение И, истинное ровно для этой строки (используя НЕ для инвертирования входов, равных 0 в данной строке). Затем эти выражения для каждой строки объединяются через ИЛИ. Результат истинен ровно для тех строк, где результат равен 1, и ложен во всех остальных — что в точности соответствует исходной таблице истинности.
Эта конструкция называется дизъюнктивной нормальной формой (ДНФ). Она доказывает, что И, ИЛИ и НЕ могут выразить каждую таблицу истинности, которую только можно написать, а значит — каждую булеву функцию, которая существует. Множество (И, ИЛИ, НЕ) является функционально полным.
Можно пойти ещё дальше: (И, НЕ) само по себе полно (ИЛИ строится из них:
A ИЛИ B = НЕ(НЕ A И НЕ B)), как и (ИЛИ, НЕ). Наиболее впечатляюще: только И-НЕ
(NAND) одного достаточно — весь компьютер можно построить из единственного типа
элемента, — что и является исходной посылкой курса nand2tetris.
Вычислим (A И НЕ B) ИЛИ (НЕ A И B) для всех четырёх комбинаций входов.
Это выражение называется XOR (исключающее или): оно истинно, когда ровно один вход истинен.
| A | B | НЕ B | НЕ A | A И НЕ B | НЕ A И B | результат (ИЛИ) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
Результат равен 1 ровно тогда, когда A и B различаются. Вот как XOR строится из И, ИЛИ и НЕ — демонстрируя, что трёх операций действительно достаточно для построения новых.
1 И 0 = ?
1 ИЛИ 0 = ?
НЕ 0 = ?
0 ИЛИ 0 = ?
НЕ 1 И 1 = ? (Сначала вычисли НЕ, затем И.)
Сколько строк в таблице истинности для операции с двумя входами?
Можно ли выразить XOR (истинно, когда ровно один вход истинен) только через И, ИЛИ и НЕ?
Булево значение — это истина (1) или ложь (0): один бит, интерпретируемый как значение истинности. НЕ инвертирует: НЕ 1 = 0, НЕ 0 = 1. И равно 1 только когда оба входа равны 1; во всех остальных случаях результат — 0. ИЛИ равно 0 только когда оба входа равны 0; во всех остальных случаях результат — 1. Таблица истинности перечисляет все комбинации входов и соответствующий результат — это полное и однозначное определение операции. И, ИЛИ и НЕ вместе функционально полны: любую булеву функцию, сколь угодно сложную, можно построить из этих трёх операций. Метод называется дизъюнктивной нормальной формой: для каждой строки с результатом 1 пишется одно выражение И, затем эти выражения объединяются через ИЛИ. Эта полнота объясняет, почему трёх операций (или даже одного только И-НЕ) достаточно для построения целого компьютера.