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

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

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

АЛГЕБРА БУЛЯ

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

A = á M, W ñ,

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

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

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

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

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

W = {Ú, Ù, ù}, т.е.

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

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

A	b	a Ú b

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

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

A	b	a Ù b

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

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

а	ù а

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

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

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

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

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

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

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

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

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

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

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

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

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

Т.е. законы алгебры множеств, относящиеся к операциям объединения (È), пересечения (Ç), дополнения (ù), выполняются в булевой алгебре соответственно для операций дизъюнкции (Ú), конъюнкции (Ù) и отрицания (ù). Универсальное множество (U) в алгебре Буля – это 1, а пустое множество (Æ) – соответственно 0.

Дата добавления: 2014-01-06