Компьютеры
и программирование

БУЛЕВА АЛГЕБРА (АЛГЕБРА ЛОГИКИ)

Понятие алгебры логики

Способы описания логических функций

Логические функции

Булев базис (логический базис)

Аналитическое представление логических функций

Аксиомы алгебры логики

Теоремы алгебры логики

Законы алгебры логики

Понятие алгебры логики

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

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Функция от n переменных называется логической или булевой или переключательной или функцией алгебры логики, если сама функция и любой из ее аргументов могут принимать значения только из множества {0, 1}. Количество функций от n переменных равно 2 в степени n.

Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая "1") или сигнал отсутствует (логический "0").

На логических элементах, реализующих булевы функции, строятся логические схемы электронных устройств.

Законы булевой алгебры применяются и в программировании - при написании сложных логических условий и сложных запросов к базе данных. Один пример со скриптом на PHP приведён здесь (это статья о системе многокритериального поиска по сайту с базой данных). Ещё один пример - применение алгебры логики в создании многоуровневого меню сайта, в котором были бы открыты все пункты всех уровней, по которому пролегает путь к конечному открытому пункту меню.

Часто оказывается, что изначально построенное логическое выражение можно упростить, используя аксиомы, теоремы и законы алгебры логики.

Способы описания логических функций

Применяются следующие способы описания логических функций:

  • словесный;
  • табличный;
  • числовой;
  • аналитический;
  • координатный;
  • графический.

Пример табличного описания логических функций

Номер набораf
00
11
20
30
41
51
60
71

 

X1X2X3f
0000
0011
0100
0110
1001
1011
1100
1111

Приведённые выше таблицы имеют название таблиц истинности. Такие таблицы в практике необходимо строить для любой, сколь либо сложной булевой функции. Примеры таблиц истинности для булевых функций, реализованных в логических схемах - в материале Логические схемы и таблицы истинности.

Пример числового описания логических функций

или .

Пример аналитического описания логических функций

Пример координатного описания логических функций

Карта Карно

Пример графического описания логических функций

Логические функции

Логические функции одной переменной

ФункцияНазваниеОбозначение
Константа нуля
Повторение x
Логическое отрицание, инверсия, "НЕ"
Константа единицы

 

ПеременнаяЛогические функции
x
00011
10101

 

Нет времени вникать в решение? Можно заказать работу!

К началу страницы

Логические функции двух переменных

ФункцияНазваниеОбозначение
Константа нуля или False
Логическое умножение, конъюнкция, "И" или или или
Запрет по или
Переменная
Запрет по или
Переменная
Сложение по модулю 2, отрицание эквивалентности, исключающее "ИЛИ" или или
Логическое сложение, дизъюнкция, "ИЛИ" или или или
Функция Пирса (Вебба), "ИЛИ-НЕ" или или
Логическая равнозначность, эквиваленция или или или
Отрицание
Правая импликация или
Отрицание
Левая импликация или
Функция Шеффера, "И-НЕ" или или
Константа единицы или True

 

X10011
X20101
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

В логических схемах функции могут быть реализованы с произвольных количеством входных переменных, примеры - в материале Логические схемы и таблицы истинности.

Булев базис (логический базис)

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

Инверсия (логическое отрицание, "НЕ")

.

01
10

Конъюнкция (логическое умножение, "И")

.

000
010
100
111

Дизъюнкция (логическое сложение, "ИЛИ")

.

000
011
101
111

В булевом базисе обычно строятся логические схемы, которые реализуют сколь угодно сложные логические функции, примеры - в материале Логические схемы и таблицы истинности.

Аналитическое представление логических функций

В качестве исходного описания сложных логических функций обычно используется таблица истинности, однако упрощение функций удобнее производить в аналитической форме. При аналитической записи функция алгебры логики представляется либо в виде логической суммы элементарных логических произведений (дизъюнкции элементарных конъюнкций), либо в виде логического произведения элементарных логических сумм (конъюнкции элементарных дизъюнкций). Первая форма записи имеет название дизъюнктивной нормальной формы (ДНФ), вторая - конъюнктивной нормальной формы (КНФ).

Дизъюнктивная нормальная форма

.

X1X2f
001
011
101
110

Конъюнктивная нормальная форма

.

X1X2f
000
010
101
110

Аксиомы алгебры логики

Аксиомы конъюнкции

.

Аксиомы дизъюнкции

.

Аксиомы отрицания

если , то ; если , то .

Теоремы алгебры логики

Теоремы исключения констант

.

Теоремы идемпотентности (тавтологии, повторения)

.

для n переменных

.

Теорема противоречия

.

Теорема "исключённого третьего"

.

Теорема двойного отрицания (инволюции)

.

Законы алгебры логики

Ассоциативный (сочетательный) закон

.

Коммутативный (переместительный) закон

.

Дистибутивный (распределительный) закон

.

.

Законы де Моргана (законы общей инверсии или дуальности)

.

.

Закон поглощения (элиминации)

.

Закон склеивания (исключения)

.

Нет времени вникать в решение? Можно заказать работу!

К началу страницы

Логические схемы и таблицы истинности