2.3.1 Определение алгебры. Теорема Стоуна

Как и любая алгебра, алгебра Буля состоит из двух множеств:

A = , ,

где  - основное множество (носитель), в данном случае это множе -ство высказываний;

 - множество операций данной алгебры (сигнатура).

Высказывание – повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. Обозначают «истинность» как 1, «ложность» как 0.

Т.о. множество М = 0, 1, т.е. имеем двухэлементную булевую алгебру.

Как уже отмечалось, в алгебре Буля используются следующие булевские операции:

 = , , , т.е.

• логическое сложение – дизъюнкция (операция „или”)

Таблица 2.7 – Операция дизъюнкция

• логическое умножение – конъюнкция (операция „и”)

Таблица 2.8 – Операция конъюнкция

• инверсия – отрицание (операция „не”)

Таблица 2.9 - Операция отрицание

Примечание: из таблицы 2.6 видно, что одна из операций - дизъюнкция или конъюнкция – лишняя. Можно было обойтись одной из них и отрицанием. Т.е. алгебра Буля избыточна. А это значит, что одну и ту же функцию можно записать в этой алгебре разными способами.

Правила старшинства логических операций

По старшинству операции подразделяются так:

• отрицание – логическая операция первой ступени;

• конъюнкция – логическая операция второй ступени;

• дизъюнкция – логическая операция третьей ступени.

Правила старшинства:

1. Если в логических выражениях встречаются операции только одной и той же ступени, то их выполняют в том порядке, в котором они записаны.

2. Если в логических выражениях встречаются операции различных ступеней, то вначале выполняются операции 1 ступени, затем 2 ступени, и только потом – 3 ступени.

Примечание: для изменения порядка выполнения операций используются скобки.

Теорема Стоуна

Теорема Стоуна: алгебра Буля изоморфна алгебре Кантора.

Примечание: алгебра Кантора – алгебра множеств.

Примечание: отображение всей алгебраической системы G в другую G’ называется гомоморфизмом, если каждому элементу а  G соответствует определенный элемент а’  G’, и если при этом c = a  b, то c’ = a’ ’ b’. Где * - операция, определенная в G, а *’ – операция, определенная в G’.

Если такое отображение взаимно однозначно, то оно называется изоморфизмом.

Т.е. законы алгебры множеств, относящиеся к операциям объединения (), пересечения (), дополнения (), выполняются в булевой алгебре соответственно для операций дизъюнкции (), конъюнкции () и отрицания (). Универсальное множество (U) в алгебре Буля – это 1, а пустое множество () – соответственно 0.