Решетки в дискретной математике


Определение: Решетка L=(A, ∧, ∨) есть множество А с двумя определенными на нем бинарными операциями x ∨ y: A x A → A; x∧y: A*A→A удовлетворяющее следующим аксиомам:
∀a,b,c ∈ A:

L1) x ∨ x = x, x ∧ x=y – идемпотентность.
L2) x ∨ y = y ∨ x, x ∧ y = y ∧ x — коммутативность.
L3) x ∨ (y ∨ z)= (x ∨ y) ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧ z – ассоциативность.
L4) x ∨ (x ∧ y)= x, x ∧ (x ∨ y) = x – поглощение.

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

Определение: Решетка называется дистрибутивной, если для нее выполняются аксиомы L1 — L4 и равенство L5:
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Определение: Решетка называется модулярной, если для нее выполняются аксиомы L1 — L4 и равенство L6:
a ∧ (b ∨ (a ∧ c)) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ (a ∨ c)) = (a ∨ b) ∧ (a ∨ c)

Замечание: (Принцип двойственности): если в верном в решетке L равенстве заменить «∨» на «∧», а «∧» на «∨» с сохранением скобок, то получим снова верное равенство.

Лемма: в решетке L = (A, ∧, ∨) справедливо соотношение a∧b = a ⇔ a∨b = b
Без доказательства.

Введем отношение a ≤ b, положив a ≤ b ⇔ a*b = a, тогда по лемме a ≤ b ⇔ a∨b =b.

Теорема: в решетке L= (A, ∨, ∧) отношение a ≤ b – есть отношение частичного порядка.
Без доказательства.

Следствие: решетка L=(A, ∧, ∨) есть частично упорядоченное множество (A, ≤) c отношением частичного порядка a ≤ b ⇔ ab = a.

Замечание: Во всяком ЧУМе можно определить функции:
x ∨ y = sup(x,y)
x ∧ y = inf(x,y)

Теорема: в ЧУМе справедливы аксиомы L1 — L4 для решетки.

Следствие: Если в ЧУМ (A, ≤) операции sup(x,y) и inf(x,y) всюду определены, то по отношению к этим операциям ЧУМ есть решетка.

Решетки имеющие наименьшее O и наибольшее I элементы называются решетками с универсальными границами. Возможны решетки только с одной универсальной границей, возможны без обеих.

Всякая конечная решетка имеет универсальные границы O и I.
Универсальные границы имеют свойства L7:
a∨I = I
a∨O = a
a∧I = a
a∧O = O

Определение: Дополнение элемента а решетки L есть такой элемент a∈L, что а∨а = I, и a∧a=O.

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


Комментарии запрещены.




Статистика