Булевы решетки

Алгебраическое представление решеток.

Введем обозначения Sup(a, b) = a È b, Inf(a, b) = a Ç b,

Будем считать традиционно используемые здесь значки È, Ç не имеющими никакого отношения к теоретико-множественным операциям объединения и пересечения.

Если выполняются законы:

1. a È b = b È a 1’. a Ç b = b Ç a

2. (a È b) È c = (b È c) Èa = a È b È c 2’. (a Ç b) Ç c = (b Ç c) Ç a = a Ç b Ç c

3. a È (a Ç b) = a 3’. а Ç (b È a) = a

4. a È a = a 4’. а Ç a = a

то имеет место решетка.

То есть решетка можно определить как алгебру Z = < L, Ç, È >, для операций которой выполняются вышеперечисленные законы.

Решетка называется дистрибутивной, если дополнительно к вышеперечисленным выполняется дистрибутивный закон:

5. a È b Ç c = (a È b) Ç(a È c) 5'. а Ç (b È c) = a Ç b È a Ç c

Пример: Недистрибутивная решетка:

a È b Ç e = (a È b) Ç (a È e)

а È e = a Ç a

a = a

b È c Ç d = b Ç c È b Ç d

b È e = a È a

b ¹ a недистрибутивность

Эта решетка недистрибутивная.

Решетка называется ограниченной, если она имеет максимальный и минимальный элементы.

Например, если взять отрезок действительной оси от 0 до 1 (вместе с конечными точками) и отношение "меньше", то это будет ограниченная решетка. Убрав крайние точки, получаем неограниченную решетку.

1 1

- неограниченная решетка - ограниченная

(без 1 и 0)

0 0

Обычно минимальный элемент решетки обозначают как 0, а максимальный как 1.

ā - дополнение а, если а È ā = 1 и а Ç ā =0

Решетка является решеткой с дополнением, если каждый элемент имеет хотя бы одно дополнение.

Ограниченная дистрибутивная решетка с дополнением является булевой.

Примеры булевых решеток:

					2^n

Дата добавления: 2014-01-06