Что такое булева алгебра
ББулева алгебра — раздел математики, изучающий логические операции над двумя значениями: 0 (ложь) и 1 (истина). Создана Джорджем Булем в 1854 г. Фундамент цифровой электроники, информатики, логики. Без неё не было бы компьютеров — все CPU работают на основе булевых схем.
Клод Шеннон в 1938 г. показал связь булевой алгебры с релейной логикой — это открыло путь к созданию современных компьютеров. Сегодня булева алгебра — основа языков программирования (if/else, логические условия), SQL-запросов, поиска, ML.
Логические операторы
Основные законы
Коммутат.: A ∧ B = B ∧ A
Ассоц.: (A ∧ B) ∧ C = A ∧ (B ∧ C)
Дистриб.: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
Де Морган: ¬(A ∧ B) = ¬A ∨ ¬B
Поглощение: A ∨ (A ∧ B) = A
Двойное отрицание: ¬¬A = A
Нейтральные: A ∧ 1 = A, A ∨ 0 = A
Нулевой/единичный: A ∧ 0 = 0, A ∨ 1 = 1
Законы, которым подчинены символы логики, полностью соответствуют законам алгебры, применяемой к числам, с единственным исключением — ограничением на значения 0 и 1.— Дж. Буль, 'Исследование законов мышления' (1854)
СДНФ и СКНФ
СДНФ (совершенная ДНФ) — дизъюнкция конъюнкций, где каждая конъюнкция содержит все переменные. Строится по строкам ТИ, где F=1. СКНФ (совершенная КНФ) — конъюнкция дизъюнкций. Строится по строкам, где F=0 (с инверсией переменных).
Применение
Цифровая электроника: логические вентили (AND, OR, NOT). Программирование: if-else, условия в циклах. SQL: WHERE A AND B OR C. Поиск: булевы запросы в Google, Elastic. Криптография: XOR-шифры, потоковые шифры. ML: бинарные признаки, деревья решений.
- Дискретная математика. С.В. Яблонский. Наука. 1979 (переиздания).
- Investigation of the Laws of Thought. G. Boole. Walton & Maberly. 1854.
- Symbolic Analysis of Relay and Switching Circuits. C. Shannon. MIT Press. 1938.
- Дискретная математика и комбинаторика. А.С. Холл, Р. Хеард. Диалектика. 2019.
