Булева алгебра (алгебра логики)
Понятие алгебры логики
На этом уроке знакомимся с алгеброй логики (булевой алгеброй). Одним из её основателей стал английский математик Джордж Буль (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 |
Логические функции двух переменных
Функция | Название | Обозначение |
![]() | Константа нуля | ![]() |
![]() | Логическое умножение, конъюнкция, "И" | ![]() ![]() ![]() ![]() |
![]() | Запрет по ![]() | ![]() ![]() |
![]() | Переменная ![]() | ![]() |
![]() | Запрет по ![]() | ![]() ![]() |
![]() | Переменная ![]() | ![]() |
![]() | Сложение по модулю 2, отрицание эквивалентности, исключающее "ИЛИ" | ![]() ![]() ![]() |
![]() | Логическое сложение, дизъюнкция, "ИЛИ" | ![]() ![]() ![]() ![]() |
![]() | Функция Пирса (Вебба), "ИЛИ-НЕ" | ![]() ![]() ![]() |
![]() | Логическая равнозначность, эквиваленция | ![]() ![]() ![]() ![]() |
![]() | Отрицание ![]() | ![]() |
![]() | Правая импликация | ![]() ![]() |
![]() | Отрицание ![]() | ![]() |
![]() | Левая импликация | ![]() ![]() |
![]() | Функция Шеффера, "И-НЕ" | ![]() ![]() ![]() |
![]() | Константа единицы | ![]() |
Ниже дана таблица истинности для логических функций от двух переменных.
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 переменных
.
Теорема противоречия
.
Теорема "исключённого третьего"
.
Теорема двойного отрицания (инволюции)
.
Законы алгебры логики
Ассоциативный (сочетательный) закон
.
Коммутативный (переместительный) закон
.
Дистибутивный (распределительный) закон
.
.
Законы де Моргана (законы общей инверсии или дуальности)
.
.
Закон поглощения (элиминации)
.
Закон склеивания (исключения)
.