Булева алгебра и теория множеств. Коммутационные схемы

Можно легко заметить аналогию между свойствами операций над множествами и свойствами логических операций. Это не случайно.

Множество вместе с заданными на нём операциями называется алгеброй и обозначается .

Определение.Всякая алгебра, содержащая две бинарные и одну унарную операции, которые удовлетворяют соотношениям 1) - 9) (см. основные эквивалентные соотношения булевой алгебры, или основные свойства операций над множествами) называется булевой.

Таким образом, булевыми алгебрами будут:

а) - булева алгебра всех логических функций с операциями конъюнкции, дизъюнкции, отрицания;

б) - булева алгебра логических функций m переменных – это подалгебра алгебры , т.к. ;

в) (P - булева алгебра множеств над - универсумом, с операциями пересечения, объединения, дополнения;

г) - булева алгебра двоичных векторов длины n с покомпонентными логическими операциями над двоичными векторами, определёнными следующим образом:

имеет место:

1) , где если ; в любом другом случае .

2) , где если ; в любом другом случае .

3) , где если , если .

Если мощности множеств P и равны ( P ), то между ними можно установить взаимно однозначное соответствие, а соответствующие булевы алгебры будут изоморфны.

Изоморфизм булевых алгебр широко используется в компъютерных вычислениях, например, вместо выполнения операций над множествами или логическими функциями используют их изоморфные аналоги – поразрядные операции над двоичными векторами.

Дата добавления: 2014-12-27