Нехай 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₁.

string.contains java

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

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