16. Булевы алгебры и их основные свойства.

Булевой алгеброй называется А ≠ Ø с двумя б.о. + ,*, унарной операцией ( ) – аналог отрицания и двумя выделенными элементами е₁ и е₂: для всех элементов a,b,c ϵ A верны следующие аксиомы:

А1) +,* - коммутативны

a+b=b+a

a*b=b*a

A2)+,* - ассоциативны

a+(b+c)=(a+b)+c и a*(b*c)=(a*b)*c

A3)+,*, различные нейтральные элементы е₁ и е₂ ϵ А: ∀ a ϵ A=>a+e₁=e₁+a=a; a*e₁=e₁*a=a

A4)+,* - дистрибутивны относительно друг друга

a+(b*c)=(a+b)*(a+c)

a*(b+c)=(a*c)+(a*c)

A5) ∀ a ϵ A a+a=e₂

a*a=e₁ – свойство дополнительности

В булевой алгебре справедлив принцип двойственности т.е. в булевой алгебре существует двойственные утвержденияя: они либо одновременно верны либо не верны

Если в формуле верной в некоторой булевой алгебре поменять + на *, а * на +, и е1 на е2, а е2 на е1 то получится формула также истинная в этой булевой алгебре

Свойства:

1. е₁ и е₂ – единственны

2. ∀ a ϵ A ! а ϵ А:a+a = e₂, a*a=e₁ – свойство отрицания

3. Законы иденпотентности: ∀ a ϵ A а+а=а

а*а=а

4. Законы идентичности: ∀ a ϵ A а+е₂=е₂+а=е₂

а*е₁=е₁*а=е₁

5. Закон поглощения: ∀ a,b ϵ A а+(a*b)=a

a*(a+b)=a

6. Закон инвалюции ∀ a ϵ A а=а

7. Закон Де Моргана ∀ a,b,c ϵ A a+b=a*b

a*b=a+b

8. Закон дополнения: е₁=е₂; е₂=е₁

9. Закон склеивания: (a+b)*(a+b)=b

(a*b)+(a*b)=b

17. Алгебраические системы. Решетки. Примеры.

На непустом множестве А кроме алгебраич операц, можно рассматривать и отношения.

Def: алгебраич система – упорядоч тройка < >, где пусто, - мн-во алгебраич операций, - мн-во отношений, заданных на А.

Частные случаи:

1. = пусто, то < >- алгебра

2. =пусто, то < > - модель

Решетки

Def: решеткой наз частично упорядочен мн-во <A, >, в кот каждое двухэлементное подмножество имеет как точную верхнюю (sup) и inf грани.

Для задания элементов х,у А inf{x,y} наз пересечением х и у и обознач через , а sup{x,y} наз объединением .

Замечания.

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

В системе А введены операции , то тогда отношение частичного порядка можно по этим операциям восстановить след образом:

Def: наименьший (наибольший) элем решетки, если он существует, наз нулем(единицей) и обознач 0(1).

Утверждение. В конечных решетках всегда имеется 0 и 1.

Пример.

1. Любое конечное лин упоряд мн-во явл решеткой.

2. |A|>1, то ЧУМ <A, id_A>, где id_A={(x,x)/x A} – тождеств отношение не явл решеткой, поскольку x и у - различных не определена операция inf{x,y} и sup{x,y}.

Def: решетка А=< A, > наз дистрибутивной, если - дистрибутивны, т.е и

Def: дистрибут решетка А=< A, > наз булевой алгеброй, если А имеет 0,1 и 0 1 и : и .