Нехай 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,∧ ,∨) визначається як твердження, отримане шляхом заміни ∧ на ∨.

Наприклад , подвійний до 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 ₁ ,a ₂ ,a ₃ ....а _п } є обмеженим.

Доказ: Ми дали скінченну решітку:

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

Таким чином, найбільшим елементом решіток L є a ₁ ∨ a ₂ ∨ a _{3∨....∨a п .}

Крім того, найменшим елементом решітки L є a ₁ ∧ a ₂ ∧a ₃ ∧....∧a _п .

Оскільки для кожної кінцевої решітки існують найбільший і найменший елементи. Отже, L є обмеженим.

Субрешітки:

Розглянемо непорожню підмножину L ₁ решітки L. Тоді L ₁ називається підрешіткою L, якщо L ₁ сама є решіткою, тобто операція L, тобто a ∨ b ∈ L ₁ і a ∧ b ∈ L ₁ коли a ∈ L ₁ і b ∈ L ₁ .

приклад: Розглянемо решітку всіх +pe цілих чисел 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 ₁ до Л ₂ тобто 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

Решітка 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 ₁ ,b ₁ ) і (а ₂ ,b ₂ ) в Л.

(а ₁ ,b ₁ )∨( а ₂ ,b ₂ )=(а ₁ ∨ ₁ a ₂ ,b ₁ ∨ ₂ b ₂ )
і (а ₁ ,b ₁ ) ∧ ( а ₂ ,b ₂ )=(а ₁ ∧ ₁ a ₂ ,b ₁ ∧ ₂ b ₂ ).

приклад: Розглянемо решітку (L, ≦), як показано на рис. де L = {1, 2}. Визначити решітки (Л ² , ≦), де L ² =L x L.

рішення: Решітка (Л ² , ≦) показано на рис.