Образовательный блог – всё для учебы

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

Определение: Булева Алгебра А=(А, ∨, ∧, ⌐, 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), тогда система (А, ∨, ∧) – есть ЧУМ.

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

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

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

Реклама: скачать программы по математике. Специальные математические программы помогут упростить решения Ваших задач по математике.

1. Примеры универсальных алгебр, подалгебры, гомоморфизм и изоморфизм алгебр
2. Конгруенции и фактор-алгебры, теоремы о гомоморфизме
3. Решетки
4. Функции алгебры логики
5. Булевы свойства логических операций. Эквивалентные преобразования формул
6. Суперпозиция функций. Функционально замкнутые классы
7. Основы реляционной алгебры
8. Теорема Поста о функциональной полноте
9. Шкала мощностей
10. Мощность континуума
11. Целые числа, сравнения – дискретная математика
12. Фундаментальная система решений, общее решение однородного и неоднородного ЛРУ с помощью ФСР
13. Графы, мультиграфы, псевдографы, орграфы. Изоморфизм графов
14. Правило суммы и правило произведения
15. Верхняя и нижняя оценки для хроматического числа. Внутренне и внешне устойчивые множества вершин графа
16. Многочлен Жигалкина
17. СДНФ и СКНФ