Булева алгебра
Булева алгебра — абстрактная алгебраическая структура с операциями объединения (join), пересечения (meet) и дополнения, удовлетворяющими заданным законам. Модель подмножеств множества — один пример такой структуры.
Алгебра на двух значениях 0 и 1 служит моделью двузначной логики и позволяет описывать логические функции; логические элементы реализуют их в цифровых схемах. Это частный случай булевой алгебры, а не её единственная форма и не вся математическая логика.
Булева алгебра
Логические операции
Конъюнкция (AND, ∧), дизъюнкция (OR, ∨), отрицание (NOT, ¬), импликация (→), эквиваленция (↔). Таблицы истинности.
Законы булевой алгебры
Коммутативность, ассоциативность, дистрибутивность, идемпотентность, законы де Моргана: ¬(A∧B) = ¬A∨¬B.
Нормальные формы
ДНФ (дизъюнкция конъюнкций), КНФ (конъюнкция дизъюнкций). СДНФ и СКНФ — совершенные формы, минимизация.
Применение в схемах
Логические вентили: AND, OR, NOT, NAND, NOR, XOR. Комбинационные схемы, сумматоры, мультиплексоры.
Законы де Моргана
Отрицание объединения: ¬(A ∪ B) = ¬A ∩ ¬B. Отрицание пересечения: ¬(A ∩ B) = ¬A ∪ ¬B. Пример: "Не (жарко ИЛИ дождливо)" = "Не жарко И не дождливо". Применение: логические схемы (упрощение NOT-OR → NAND), программирование (!(a || b) = !a && !b). Обобщение: ¬(⋃Aᵢ) = ⋂¬Aᵢ. Август де Морган (1806-1871), формализация 1847.
Булевы операции
AND (∧), OR (∨), NOT (¬), XOR (⊕), NAND, NOR. Законы: коммутативность, ассоциативность, дистрибутивность, де Моргана. Основа цифровой электроники, SQL.
Минимизация булевых функций
Карты Карно для 2-4 переменных, метод Квайна-МакКласки для любого числа. Уменьшение числа вентилей в схемах. Применение: проектирование микросхем.
Логические вентили
Физическая реализация булевых операций. AND, OR, NOT, NAND, NOR, XOR. NAND и NOR — универсальные (любая функция). Транзисторная реализация. Основа процессоров.