Булева алгебра и булевы функции. Операции и алгебры. Гомоморфизмы

Булева алгебра и булевы функции. 

   Лекция 7.

Операции и алгебры. Гомоморфизмы.  Булевы алгебры.

Под словом "алгебра", как правило, понимают раздел математики, изучающий свойства разнообразных операций на различных множествах, например, алгебра чисел, алгебра векторов, алгебра матриц и т.п. Однако это слово используется и для обозначения конкретных объектов – алгебраических структур, изучаемых в данном разделе.

Пусть  –какое-либо непустое множество,  - декартово произведение множества  на себя, выполненное  раз.

Определение 7.1. Функциональное соответствие  называют  -арной ( местной) алгебраической операцией на .

Двуместными операциями на булеане Ρ являются операции пересечения и объединения множеств, унарной операцией – операция дополнения.

Наряду с унарными и бинарными операциями рассматривают также нульарные операции. Например, выделение "наименьшего" – пустого, и "наибольшего" – универсального, множеств в булеане есть нульарные операции. Операции арность которых больше, чем 2,

– это трехместные, четырехместные и т.д. операции, сопоставляющие последовательностям трех-, четырех- и т.д. элементов множества  определенный элемент этого же множества.

Определение 7.2. Непустое множество  с заданной последовательностью операций и указанием арностей этих операций называюталгебраической структурой или алгеброй. При этом множество  называют носителем алгебры, последовательность операций на нем  – сигнатурой алгебры, последовательность числа мест каждой

операции  – типом алгебры.

Например, алгебра  типа  – это алгебра, носителем которой

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

Различные алгебры могут отличаться друг от друга носителем, сигнатурой или типом. Кроме того, они могут отличаться системой аксиом алгебры, в которой записаны свойства операций сигнатуры. Основные свойства операций – это ассоциативность, коммутативность, дистрибутивность, поглощение, идемпотентность и т.д. (см. табл. 1.7). Некоторые из свойств операций записываются в систему аксиом алгебры, другие представляют собой следствия из аксиом, т.е. являются теоремами и требуют доказательства.

Пусть A= и B= – две алгебры одного типа. На множестве  имеется функциональное соответствие , сохраняющее операции. Требование сохранения операций можно пояснить следующей схемой (рис.

4.1).

Схема показывает, что в алгебре A результатом операции  является элемент  , в алгебре B результатом операции  является элемент  . Образом элемента  в функциональном соответствии  является элемент