Булева алгебра (алгебра логики)
Понятие алгебры логики
На этом уроке знакомимся с алгеброй логики (булевой алгеброй). Одним из её основателей стал английский математик Джордж Буль (1815-1864), который был из довольно бедной семьи, а в юности зарабатывал переводами сочинений древнегреческих философов. За этим занятием его и посетила мысль о том, что высказываниям можно присваивать значения 1 ("истина") и 0 "ложь".
Итак, алгебра логики (булева алгебра) — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Алгебра логики позволяет закодировать любые утверждения, истинность или ложность которых нужно доказать, а затем манипулировать ими подобно обычным числам в математике.
Создание алгебры логики в середине ХIХ века в трудах Джорджа Буля представляло собой попытку решать традиционные логические задачи алгебраическими методами.
Пусть функция 
от
n переменных и любой из её аргументов могут принимать значения только из множества {0, 1}. Тогда эта
функция называется логической, или булевой, или переключательной,
или функцией алгебры логики. Описанную функцию часто называют также
булевым вектором. Количество функций от n переменных
равно 2 в степени n. То же самое можно сказать и иначе: число различных n-мерных
булевых векторов равно 2 в степени n. А число различных функций алгебры логики от этих векторов
равно уже 
.
Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая "1") или сигнал отсутствует (логический "0").
На логических элементах, реализующих булевы функции, строятся логические схемы электронных устройств.
Законы булевой алгебры применяются и в программировании - при написании сложных логических условий и сложных запросов к базе данных. Один пример со скриптом на PHP приведён здесь (это статья о системе многокритериального поиска по сайту с базой данных). Ещё один пример - применение алгебры логики в создании многоуровневого меню сайта, в котором были бы открыты все пункты всех уровней, по которому пролегает путь к конечному открытому пункту меню.
Часто оказывается, что изначально построенное логическое выражение можно упростить, используя аксиомы, теоремы и законы алгебры логики.
Способам и приёмам минимизации логических функций посвящены отдельные материалы сайта - минимизация логических функций: общие сведения, минимизация логических функций: метод непосредственных преобразований и минимизация логических функций: метод Квайна.
Логические функции
Логические функции одной переменной
| Функция | Название | Обозначение |
 | Константа нуля |  |
 | Повторение x |  |
 | Логическое отрицание, инверсия, "НЕ" |  |
 | Константа единицы |  |
| Переменная | Логические функции | |||
| x | | | | |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
Логические функции двух переменных
| Функция | Название | Обозначение |
 | Константа нуля |  или False |
 | Логическое умножение, конъюнкция, "И" |  или  или  или  |
 | Запрет по  |  или  |
 | Переменная  |  |
 | Запрет по |  или  |
 | Переменная |  |
 | Сложение по модулю 2, отрицание эквивалентности, исключающее "ИЛИ" |  или  или  |
 | Логическое сложение, дизъюнкция, "ИЛИ" |  или  или  или  |
 | Функция Пирса (Вебба), "ИЛИ-НЕ" |  или  или  |
 | Логическая равнозначность, эквиваленция |  или  или  или  |
 | Отрицание |  |
 | Правая импликация |  или  |
 | Отрицание |  |
 | Левая импликация |  или  |
 | Функция Шеффера, "И-НЕ" |  или  или  |
 | Константа единицы |  или True |
Ниже дана таблица истинности для логических функций от двух переменных.
| X1 | 0 | 0 | 1 | 1 |
| X2 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
В логических схемах функции могут быть реализованы с произвольных количеством входных переменных, примеры - в материале Логические схемы и таблицы истинности.
Ответить на контрольные вопросы, а затем посмотреть ответы
Контрольный вопрос 1. Даны две переменные x1 и x2. Число различных булевых векторов и различных ФАЛ от полученных векторов равны соответственно:
- 8 и 16
- 8 и 32
- 4 и 8
- 4 и 16
Контрольный вопрос 2. Какие из функций не являются ФАЛ одной переменной (и одна, и вторая в варианте ответа):
- отрицание и сложение по модулю два
- эквивалентность и повторение x
- отрицание и импликация
- функция Шеффера и эквивалентность
- запрет по x2 и отрицание
Булев базис (логический базис)
Любую булеву функцию с произвольным количеством аргументов можно построить через подстановку элементарных функции вместо аргументов (суперпозицию). Набор простейших функций, с помощью которого можно выразить любые другие, сколь угодно сложные логические функции, называется функционально полным набором, или логическим базисом.
Инверсия (логическое отрицание, "НЕ")
.
 |  |
| 0 | 1 |
| 1 | 0 |
Конъюнкция (логическое умножение, "И")
.
|  |  |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Дизъюнкция (логическое сложение, "ИЛИ")
.
| |  |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
В булевом базисе обычно строятся логические схемы, которые реализуют сколь угодно сложные логические функции, примеры - в материале Логические схемы и таблицы истинности.
Аналитическое представление логических функций
В качестве исходного описания сложных логических функций обычно используется таблица истинности, однако упрощение функций удобнее производить в аналитической форме. При аналитической записи функция алгебры логики представляется либо в виде логической суммы элементарных логических произведений (дизъюнкции элементарных конъюнкций), либо в виде логического произведения элементарных логических сумм (конъюнкции элементарных дизъюнкций). Первая форма записи имеет название дизъюнктивной нормальной формы (ДНФ), вторая - конъюнктивной нормальной формы (КНФ). В этих названиях термин "нормальная" означает отсутствие общей инверсии (отрицания) над несколькими перемнными сразу.
Дизъюнктивная нормальная форма
.
| X1 | X2 | f |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Конъюнктивная нормальная форма
.
| X1 | X2 | f |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Способы описания логических функций
Применяются следующие способы описания логических функций:
- словесный;
- табличный;
- числовой;
- аналитический;
- координатный;
- графический.
Пример табличного описания функций алгебры логики. В верхней таблице под набором подразумевается набор значений логических переменных (1 или 0), а f - это значение функции алгебры логики, заданной определённой формулой. Нижняя таблица несёт в себе более подробную информацию о наборах, поскольку в ней указаны значения переменных.
| Номер набора | f |
| 0 | 0 |
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 1 |
| 5 | 1 |
| 6 | 0 |
| 7 | 1 |
| X1 | X2 | X3 | f |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Приведённые выше таблицы имеют название таблиц истинности. Такие таблицы в практике необходимо строить для любой, сколь либо сложной булевой функции. Примеры таблиц истинности для булевых функций, реализованных в логических схемах - в материале Логические схемы и таблицы истинности.
Пример числового описания логических функций
или 
.
Пример аналитического описания логических функций
Пример координатного описания логических функций
Карта Карно
Пример графического описания логических функций
Аксиомы алгебры логики
Аксиомы конъюнкции
.
Аксиомы дизъюнкции
.
Аксиомы отрицания
если 
,
то 
; если 
,
то 
.
Теоремы алгебры логики
Теоремы исключения констант
.
Теоремы идемпотентности (тавтологии, повторения)
.
для n переменных
.
Теорема противоречия
.
Теорема "исключённого третьего"
.
Теорема двойного отрицания (инволюции)
.
Законы алгебры логики
Ассоциативный (сочетательный) закон
.
Коммутативный (переместительный) закон
.
Дистибутивный (распределительный) закон
.
.
Законы де Моргана (законы общей инверсии или дуальности)
.
.
Закон поглощения (элиминации)
.
Закон склеивания (исключения)
.
