Булеви решетки
Алгебрично представяне на решетки.
Концепция за решетка
Нека разглежданите по-долу множества A и B са чуми.
Най-големият (най-малкият) елемент aОА е елемент a, ако a ³ (£) x, където x О А.
Теорема: Ако има най-голям елемент в множеството A, то той е уникален.
Доказателство: Да приемем, че има два най-големи елемента a1 и a 2, тогава:
| a1 = a2; |
| > |
Максималният (минималният) елемент на множеството A е елементът aОА, когато не е вярно, че a £ (³)x, където x О А.
Мажорантата (миноранта) на множество B (така че Æ Ì B Í A) е
елемент a Î A, така че елемент a е най-големият (най-малкият) елемент за множеството B.
Наборът от мажоранти (миноранти) на набор B образувагорната (долната) граница на набор B.
Най-малкият елемент от горната граница се наричаSupremum илиSupremum (Sup).
Най-големият елемент от инфимума се наричаточен инфимум илиИнфимум (Inf).
Частично подредено множество, в което всяка двойка елементи има Sup и Inf, се наричарешетка.
 |
Нека въведем обозначението Sup(a, b) = a È b, Inf(a, b) = a Ç b,
Ще считаме, че традиционно използваните тук символи È и Ç нямат нищо общо с операциите на теорията на множествата на обединение и пресичане.
Ако се спазват законите:
1. a È b = b È a 1'. a Ç b = b Ç a
2. (a È b) È c = (b È c) Èa = a È b È c 2'. (a Ç b) Ç c = (b Ç c) Ç a = a Ç b Ç c
3. a È (a Ç b) = a 3'. и З (b = a) = a
4. a È a = a 4'. и З a = a
тогава се извършварешетка.
Тоест решетката може да се дефинира като алгебра Z = , за операциите на която са изпълнени горните закони.
Решетка се наричаразпределителна, ако в допълнение към горното е валиден законът за разпределение:
5. a È b Ç c = (a È b) Ç(a È c) 5'. a Ç (b È c) = a Ç b È a Ç c
Пример: Неразпределителна решетка:
a È b Ç e = (a È b) Ç (a È e)
b È c Ç d = b Ç c È b Ç d
b ¹ неразпределимост
Тази решетка е неразпределителна.
Една решетка се наричаограничена, ако има максимален и минимален елемент.
Например, ако вземете сегмент от реалната ос от 0 до 1 (заедно с крайните точки) и съотношението е "по-малко от", тогава това ще бъде ограничена решетка. Премахвайки крайните точки, получаваме неограничена решетка.
единадесет
- неограничена решетка - ограничена
Обикновено минималният елемент на решетката се обозначава с 0, а максималният с 1.
ā- допълнение a, ако a È ā = 1 и a Ç ā =0
Решетката ерешетка с допълнение, ако всеки елемент има поне едно допълнение.
Ограничената разпределителна решетка с комплемент ебулева.