Нека је Л непразан скуп затворен под две бинарне операције зване сусрет и спајање, означене са ∧ и ∨. Тада се Л назива решетком ако важе следеће аксиоме где су а, б, ц елементи у Л:
јава низ за листу
1) Комутативни закон: -
(а) а ∧ б = б ∧ а (б) а ∨ б = б ∨ а
2) Закон о удруживању:-
(а) (а ∧ б)∧ ц = а ∧(б∧ ц) (б) (а ∨ б) ∨ ц = а ∨ (б ∨ ц)
3) Закон о апсорпцији: -
(а) а ∧ ( а ∨ б) = а (б) а ∨ ( а ∧ б) = а
дуалност:
Дуал било ког исказа у решетки (Л,∧,∨) је дефинисан као исказ који се добија заменом ∧ и ∨.
На пример , дуал од а ∧ (б ∨ а) = а ∨ а је а ∨ (б ∧ а )= а ∧ а
Ограничене решетке:
Решетка Л се назива ограниченом ако има највећи елемент 1 и најмањи елемент 0.
Пример:
- Скуп снага П(С) скупа С под операцијама пресека и уједињења је ограничена решетка пошто је ∅ најмањи елемент од П(С), а скуп С највећи елемент од П(С).
- Скуп +ве целог броја И+под уобичајеним редоследом ≦ није ограничена решетка пошто има најмањи елемент 1, али највећи елемент не постоји.
Својства ограничених решетки:
Ако је Л ограничена решетка, онда за било који елемент а ∈ Л имамо следеће идентитете:
- а ∨ 1 = 1
- а ∧1= а
- а ∨0=а
- а ∧0=0
теорема: Доказати да је свака коначна решетка Л = {а1,а2,а3....ан} је ограничен.
Доказ: Дали смо коначну решетку:
Л = {а1,а2,а3....ан}
Дакле, највећи елемент решетки Л је а1∨ а2∨ а3∨....∨ан.
Такође, најмањи елемент решетке Л је а1∧ а2∧а3∧....∧ан.
квартал у пословању
Пошто највећи и најмањи елементи постоје за сваку коначну решетку. Дакле, Л је ограничено.
Подрешетке:
Размотримо непразан подскуп Л1решетке Л. Тада је Л1назива се подрешетка од Л ако је Л1сама по себи је решетка, тј. операција Л, тј. а ∨ б ∈ Л1и а ∧ б ∈ Л1кад год је а ∈ Л1и б ∈ Л1.
Пример: Размотримо решетку свих +ве целих бројева И+под операцијом дељивости. Решетка Днсвих делилаца од н > 1 је подрешетка од И+.
Одредити све подрешетке Д30који садрже најмање четири елемента, Д30={1,2,3,5,6,10,15,30}.
име америчког града
Решење: Подрешетке Д30који садрже најмање четири елемента су следећи:
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}
Изоморфне решетке:
Две решетке Л1и ја2називају се изоморфне решетке ако постоји бијекција из Л1до Л2тј, ф: Л1⟶ Л2, такав да је ф (а ∧ б) =ф(а)∧ ф(б) и ф (а ∨ б) = ф (а) ∨ ф (б)
Пример: Одредите да ли су решетке приказане на сл. изоморфне.
Решење: Решетке приказане на сл. су изоморфне. Размотримо пресликавање ф = {(а, 1), (б, 2), (ц, 3), (д, 4)}. На пример, ф (б ∧ ц) = ф (а) = 1. Такође, ми има ф (б) ∧ ф(ц) = 2 ∧ 3 = 1
Дистрибутивна решетка:
Решетка Л се назива дистрибутивна решетка ако за било који елемент а, б и ц од Л задовољава следеће дистрибутивне особине:
- а ∧ (б ∨ ц) = (а ∧ б) ∨ (а ∧ ц)
- а ∨ (б ∧ ц) = (а ∨ б) ∧ (а ∨ ц)
Ако решетка Л не задовољава горња својства, назива се недистрибутивна решетка.
Пример:
- Скуп снага П (С) скупа С под операцијом пресека и уније је дистрибутивна функција. Од,
а ∩ (б ∪ ц) = (а ∩ б) ∪ (а ∩ ц)
и такође а ∪ (б ∩ ц) = (а ∪ б) ∩ (а ∪ц) за било које скупове а, б и ц од П(С). - Решетка приказана на слици ИИ је дистрибутивна. Пошто он задовољава дистрибутивна својства за све уређене тројке које су преузете из 1, 2, 3 и 4.
Комплементи и допуњене решетке:
Нека је Л ограничена решетка са доњом границом о и горњом границом И. Нека је а елемент ако је Л. Елемент к у Л се назива допуном а ако је а ∨ к = И и а ∧ к = 0
За решетку Л се каже да је допуњена ако је Л ограничена и сваки елемент у Л има комплемент.
Пример: Одреди комплемент а и ц на сл.
Решење: Комплемент а је д. Пошто је а ∨ д = 1 и а ∧ д = 0
Допуна ц не постоји. Пошто не постоји ниједан елемент ц такав да је ц ∨ ц'=1 и ц ∧ ц'= 0.
Модуларна решетка:
Решетка (Л, ∧,∨) се назива модуларном решетком ако је а ∨ (б ∧ ц) = (а ∨ б) ∧ ц кад год је а ≦ ц.
Директан производ решетки:
Нека (Л1∨1∧1)и ја2∨2∧2) бити две решетке. Тада је (Л, ∧,∨) директан производ решетки, где је Л = Л1к Л2у којој су бинарне операције ∨(придруживање) и ∧(сусрет) на Л такве да за било које (а1,б1) и (а2,б2) у Л.
јава оператор
(а1,б1)∨( а2,б2)=(а1∨1а2,б1∨2б2)
и (а1,б1) ∧ ( а2,б2)=(а1∧1а2,б1∧2б2).
Пример: Размотримо решетку (Л, ≦) као што је приказано на сл. где је Л = {1, 2}. Одредите решетке (Л2, ≦), где је Л2=Л к Л.
Решење: Решетка (Л2, ≦) је приказан на сл.
