Нека L е непразно множество, затворено от две двоични операции, наречени среща и присъединяване, означени с ∧ и ∨. Тогава L се нарича решетка, ако са валидни следните аксиоми, където a, b, c са елементи в L:

1) Комутативно право: -
(a) a ∧ b = b ∧ a (b) a ∨ b = b ∨ a

2) Асоциативен закон: -
(a) (a ∧ b)∧ c = a ∧(b∧ c) (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) Закон за абсорбцията: -
(a) a ∧ ( a ∨ b) = a (b) a ∨ ( a ∧ b) = a

Двойственост:

Двойственото на всяко твърдение в решетка (L,∧ ,∨) се дефинира като твърдение, което се получава чрез размяна на ∧ an ∨.

Например , дуалното на a ∧ (b ∨ a) = a ∨ a е a ∨ (b ∧ a )= a ∧ a

Ограничени решетки:

Решетка L се нарича ограничена решетка, ако има най-голям елемент 1 и най-малък елемент 0.

Пример:

1. Степенното множество P(S) на множеството S при операциите на пресичане и обединение е ограничена решетка, тъй като ∅ е най-малкият елемент на P(S), а множеството S е най-големият елемент на P(S).
2. Наборът от +ve цяло число I₊под обичайния ред на ≦ не е ограничена решетка, тъй като има най-малък елемент 1, но най-големият елемент не съществува.

Свойства на ограничените решетки:

Ако L е ограничена решетка, тогава за всеки елемент a ∈ L имаме следните идентичности:

1. a ∨ 1 = 1
2. a ∧1= a
3. a ∨0=a
4. a ∧0=0

Теорема: Докажете, че всяка крайна решетка L = {a₁,а₂,а₃....а_н} е ограничен.

Доказателство: Дадохме крайната решетка:

L = {a₁,а₂,а₃....а_н}

По този начин най-големият елемент на решетките L е a₁∨ а₂∨ а_{3∨....∨aн.}

Също така, най-малкият елемент на решетката L е a₁∧ а₂∧a₃∧....∧a_н.

Тъй като най-големият и най-малкият елемент съществуват за всяка крайна решетка. Следователно L е ограничено.

Подрешетки:

Помислете за непразно подмножество L₁на решетка L. Тогава L₁се нарича подрешетка на L, ако L₁самата тя е решетка, т.е. операцията на L, т.е. a ∨ b ∈ L₁и a ∧ b ∈ L₁когато a ∈ L₁и b ∈ L₁.

Пример: Разгледайте решетката на всички + пет цели числа I₊под действието на делимостта. Решетката D_нна всички делители на n > 1 е подрешетка на I₊.

Определете всички подрешетки на D₃₀които съдържат поне четири елемента, D₃₀={1,2,3,5,6,10,15,30}.

Решение: Подрешетките на D₃₀които съдържат поне четири елемента са както следва:

1. {1, 2, 6, 30} 2. {1, 2, 3, 30}
3. {1, 5, 15, 30} 4. {1, 3, 6, 30}
5. {1, 5, 10, 30} 6. {1, 3, 15, 30}
7. {2, 6, 10, 30}

Изоморфни решетки:

Две решетки L₁и Л₂се наричат ​​изоморфни решетки, ако има биекция от L₁към Л₂т.е. f: L₁⟶ Л₂, така че f (a ∧ b) =f(a)∧ f(b) и f (a ∨ b) = f (a) ∨ f (b)

Пример: Определете дали решетките, показани на фиг., са изоморфни.

Решение: Решетките, показани на фиг., са изоморфни. Разгледайте преобразуването f = {(a, 1), (b, 2), (c, 3), (d, 4)}. Например f (b ∧ c) = f (a) = 1. Също така, ние има f (b) ∧ f(c) = 2 ∧ 3 = 1

Разпределителна решетка:

Решетка L се нарича разпределителна решетка, ако за всеки елемент a, b и c от L, тя удовлетворява следните разпределителни свойства:

1. a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
2. a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Ако решетката L не отговаря на горните свойства, тя се нарича неразпределителна решетка.

Пример:

1. Степенното множество P (S) на множеството S при операция на пресичане и обединение е разпределителна функция. От,
   a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
   и също a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) за всякакви множества a, b и c на P(S).
2. Решетката, показана на фиг. II, е разпределителна. Тъй като той удовлетворява разпределителните свойства за всички подредени тройки, които са взети от 1, 2, 3 и 4.

Допълнения и допълнени решетки:

Нека L е ограничена решетка с долна граница o и горна граница I. Нека a е елемент, ако L. Елемент x в L се нарича допълнение на a, ако a ∨ x = I и a ∧ x = 0

инстанция в java

Казва се, че решетка L е допълнена, ако L е ограничена и всеки елемент в L има допълнение.

Пример: Определете допълнението на a и c на фиг.

Решение: Допълнението към a е d. Тъй като a ∨ d = 1 и a ∧ d = 0

Допълнението на c не съществува. Тъй като не съществува такъв елемент c, че c ∨ c'=1 и c ∧ c'= 0.

Модулна решетка:

Решетка (L, ∧,∨) се нарича модулна решетка, ако a ∨ (b ∧ c) = (a ∨ b) ∧ c винаги, когато a ≦ c.

Директен продукт на решетки:

Нека (Л₁∨₁∧₁) и (Л₂∨₂∧₂) са две решетки. Тогава (L, ∧,∨) е прякото произведение на решетките, където L = L₁x L₂в която двоичната операция ∨(join) и ∧(meet) на L са такива, че за всяко (a₁,б₁) и (а₂,б₂) в L.

(а₁,б₁)∨( а₂,б₂)=(а₁∨₁а₂,б₁∨₂b₂)
и (а₁,б₁) ∧ ( а₂,б₂)=(а₁∧₁а₂,б₁∧₂b₂).

Пример: Помислете за решетка (L, ≦), както е показано на фиг. където L = {1, 2}. Определете решетките (L², ≦), където L²=L x L.

Решение: Решетката (L², ≦) е показано на фиг.