Булевы решетки и булевы алгебры

Определение: Дистрибутивная решетка с дополнениями называется Булевой решеткой.

Определение: Булева Алгебра А=(А, ∨, ∧, ⌐, 0, 1) есть множество А на котором определены три операции:
1) x∨y: AxA → A
2) x∧y: AxA → A
3) ⌐x: A → A
и два отмеченных элемента (0, 1) (универсальные границы) удовлетворяющие следующим аксиомам ∀ x,y,z ∈A:

B1) x∧x=x, x∨x=x
B2) x∧y=y∧x, x∨y = y∨x
B3) x∧(y∧z) = (x∧y)∧z, (x∨y)∨z = x∨(y∨z)
B4) x∧(x∨y) = x, x∨(x∧y) = x
B5) x∧(y∨z) = (x∧y)∨(x∧z), x∨(y∧z) = (x∨y)∧(x∨z)
B6) ⌐⌐x = x
B7) x∧1=x, x∧0=0, x∨1=1, x∨0=x
B8) x∨⌐x=1, x∧⌐x=0
B9) ⌐(x∨y)=⌐y ∧⌐x, ⌐(x∧y)= ⌐x ∨ ⌐y – правило де Моргана.

Замечание: иногда вместо x∧y пишут x&y, xy xy

Пример 1: Если U – есть конечное множество с n эллементами и P(U) — есть множество всех его 2n подмножеств, то система (P(U), ∨, ∧,-,0,1) – есть Булева алгебра в которой для подмножеств А и В.
A∨B=A∪B
A∧B=A∩B
A=U-A
0=∅
I=U

Пример 2: система ({0,1},∨,&,¬,0,1) – есть Булева алгебра.

Замечание: (Принцип двойственности): Если в Булевой алгебре истинно некоторое равенство, построенное с помощью ∨, &, ¬, 0, 1 с некоторым расставлением скобок, то истинно и равенство, полученное из исходного заменой: ∨ на &, & на ∨, 0 на 1, 1 на 0 с тем же расставлением скобок.

Теорема (Связь булевых решеток и булевых алгебр). Если алгебра является булевой алгеброй, то – булева решётка. Если алгебра – булева решётка, то , где операция ¬ определена как дополнение в булевой решётке, 0 и 1 – соответственно как ноль и единица в булевой решётке – булева алгебра.

Замечание: всякая Булева алгебра (А, ∨, ∧, ¬,0, 1) – есть решетка (А, ∨, ∧) в которой можно задать отношение частичного порядка, определенного соотношением a ≤ b ↔ a*b=a (или a∨b=b), тогда система (А, ≤) – есть ЧУМ.

Теорема: если Ai =(Аi, ∨i, ∧i, ¬ i,0 i, 1 i) i=1,2 – есть две Булевых алгебры, то A1 ≅ A2 ↔ (А1, ≤1) ↔ (А2, ≤2). Другими словами Булевы алгебры A1 ≅ A2 ⇔ когда A1 и A2 – изоморфны как ЧУМ.
Без доказательства.

Теорема (Стоуна, о представлении): каждая конечная Булева алгебра изоморфна Булевой алгебре всех подмножеств некоторого конечного множества.
Без доказательства.

Следствие:
1) конечные Булевы Алгебры изоморфны ⇔ они равноправны
2) Число элементов Булевой алгебры равно степени 2
3) Теорема Стоуна (о представлении) справедлива для бесконечной Булевой алгебры.


Оставить комментарий





Статистика

Рейтинг@Mail.ru