Булева алгебра

Булева алгебра — математическая система с двумя значениями (истина/ложь, 1/0) и операциями AND (И), OR (ИЛИ), NOT (НЕ). Разработана Джорджем Булем в 1854 году для формализации логики, стала основой цифровой электроники.

Включить свет — замкнуть цепь (1). Выключить — разомкнуть (0). Два выключателя последовательно — логическое И (оба должны быть включены). Параллельно — логическое ИЛИ (хотя бы один). Вся цифровая техника — миллиарды таких переключателей, работающих по законам математика, умершего за 74 года до первого компьютера.

Почему логика стала алгеброй

До Буля логика была философией. Аристотель в IV веке до н.э. описал силлогизмы словами: "Все люди смертны. Сократ — человек. Следовательно, Сократ смертен." Но это не формулы — нельзя подставить переменные и вычислить.

Джордж Буль в 1854 году издал "Законы мысли" — превратил логику в алгебру с операциями. Переменная x = 1, если утверждение истинно, x = 0 — если ложно. Операции: x · y (конъюнкция, AND), x + y (дизъюнкция, OR), x' (отрицание, NOT). Законы: x · x = x, x + x' = 1 (закон исключённого третьего).

На практике булева алгебра спала 83 года. Клод Шеннон в 1937 году (магистерская диссертация MIT) понял: релейные схемы — это и есть булева алгебра. Замкнутое реле — 1, разомкнутое — 0. Последовательное соединение — AND, параллельное — OR. Формулы Буля упрощают электрические схемы.

Три операции, которые строят компьютеры

AND (конъюнкция, ∧) — истина, только если оба операнда истинны. Таблица истинности: 0∧0=0, 0∧1=0, 1∧0=0, 1∧1=1. В схемах — два транзистора последовательно. Пример: "Дверь откроется, если есть ключ И код введён".

OR (дизъюнкция, ∨) — истина, если хотя бы один операнд истинен. Таблица: 0∨0=0, 0∨1=1, 1∨0=1, 1∨1=1. В схемах — транзисторы параллельно. Пример: "Тревога сработает, если открыта дверь ИЛИ разбито окно".

NOT (отрицание, ¬) — инверсия. ¬0=1, ¬1=0. В схемах — инвертор. Пример: "Свет горит, если НЕ день". Комбинация даёт NAND (НЕ-И) и NOR (НЕ-ИЛИ) — функционально полные наборы (любую логическую функцию можно выразить только через них).

Законы, которые оптимизируют процессоры

Законы де Моргана (Огастес де Морган, 1847): ¬(A ∧ B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A ∧ ¬B. "Не (дождь И снег)" = "не дождь ИЛИ не снег". Компиляторы оптимизируют код, применяя эти тождества — меньше вентилей, быстрее работа.

Коммутативность: A ∧ B = B ∧ A, A ∨ B = B ∨ A. Порядок не важен. Ассоциативность: (A ∧ B) ∧ C = A ∧ (B ∧ C). Группировка не важна. Дистрибутивность: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C). Как в обычной алгебре, только с логическими операциями.

Идемпотентность: A ∧ A = A, A ∨ A = A. "Если дождь И дождь" — просто "дождь". Поглощение: A ∧ (A ∨ B) = A. "Если A истинно, то (A ИЛИ что-угодно)" — всё равно A. Минимизация логических схем убирает избыточные вентили.

От релейных схем к нанометровым транзисторам

В 1930-х компьютеры собирали из электромеханических реле — катушка притягивает контакт, замыкая цепь. Медленно (миллисекунды), шумно (щелчки), ненадёжно (контакты окисляются). Но работало по булевой алгебре.

Транзисторы (1947, Bell Labs) заменили реле. Полупроводник управляет током: подали напряжение на затвор — ток течёт (1), убрали — не течёт (0). Быстро (наносекунды), бесшумно, миниатюрно. Интегральные схемы (1958) упаковали тысячи транзисторов на кремниевый чип.

Современный процессор — миллиарды транзисторов размером 3-5 нм. Каждый — логический вентиль (AND, OR, NOT, NAND, NOR, XOR). Сложение двух чисел — цепочка вентилей (полусумматор, полный сумматор). Умножение — ещё сложнее. Но всё сводится к формулам Буля 1854 года.

Где булева алгебра работает сегодня

Программирование — операторы if, &&, ||, ! — прямое применение булевой алгебры. Условие (x > 5) && (y < 10) — конъюнкция двух предикатов. Оптимизация: компилятор вычисляет константные выражения (true && false = false) на этапе компиляции.

Поисковые системы — булевы запросы. Google понимает "кофе AND (латте OR капучино) NOT растворимый" — пересечение множеств документов. Elasticsearch, Solr используют булеву логику для фильтрации результатов.

Цифровая электроника — любая микросхема проектируется через булевы функции. FPGA (программируемые матрицы) позволяют пользователю задать логику вентилей. Язык описания аппаратуры (Verilog, VHDL) — булева алгебра в синтаксисе кода.

Границы двоичной логики

Не всё в мире бинарно. Нечёткая логика (fuzzy logic, Лофти Заде, 1965) оперирует степенями истинности: "температура высокая" = 0.7 (не полностью истина). Применяется в автоматике, где границы размыты (тёплый/холодный, быстрый/медленный).

Квантовые вычисления выходят за рамки булевой алгебры. Кубит может быть в суперпозиции 0 и 1 одновременно (до измерения). Квантовые вентили — унитарные матрицы, не булевы функции. Но на выходе — всё равно 0 или 1, классическая логика.

Контринтуитивный факт: XOR (исключающее ИЛИ, ⊕) нельзя выразить только через AND и OR без NOT. A ⊕ B = (A ∨ B) ∧ ¬(A ∧ B). Нужны все три операции. Но {NAND} или {NOR} — функционально полные сами по себе. Процессоры строят из NAND-вентилей — проще в производстве.