Teoria krat jest ....niezwykle ciekawą ideą i..celem tego topiku jest wprowadzenie podstawowych pojęc tego działu. Opiera się ona na pojęciu relacji (porządku), jakie jest ogólnie znane, ... ale tym niemniej wszystko należy wprowadzic "od początku". Dość duża ilość przykłądow i ćwiczen pozwoli nam, szybko zrozumiec na czym rzecz polega. Także -co ważne pewne prawidła dotyczace zbiorów i liczb naturalnych zostaną zapisane w jezyku nieco innym...
Wpierw garść definicji...czyli małe wprowadzenie: Zbiór zwiemy "częsciowo uporzadkowanym" przez te rel. ,wtedy gdy zachodzą w nim takie trzy warunki tj. zwrotność, przechodniosc i antysymetria:
1) , Jesli \(\displaystyle{ \ x \in X}\) , to \(\displaystyle{ \ \ \ x \leq x}\)
2) \(\displaystyle{ x \leq y}\)i \(\displaystyle{ y \leq z}\), to \(\displaystyle{ x \leq z}\)
3) \(\displaystyle{ x \leq y}\)i \(\displaystyle{ y \leq x}\) , to \(\displaystyle{ x=y}\)
Zamiast pisac \(\displaystyle{ x \leq y}\) można też uzywac notacji \(\displaystyle{ (x,y) \in R}\). tak więc \(\displaystyle{ R \subset X \times X}\). Relacje porzadkujące oznaczamy zwykle przez \(\displaystyle{ \leq}\). Elementy x, y zwiemy porównywalnymi , gdy \(\displaystyle{ x \leq y}\) lub \(\displaystyle{ y \leq x}\). Jesli każde dwa elem. zbioru X sa porównywalne to X zwie się łańcuchem lub zbiorem liniowo uporzadkowanym. Element \(\displaystyle{ x_0}\) jest największy, gdy dla każdego \(\displaystyle{ x\in X}\) mamy: \(\displaystyle{ x \leq x_0}\). Podobnie def. ma element najmniejszy....Jeśli teraz \(\displaystyle{ E \subset X}\) to mowimy, ze zbiór E ma kres dolny \(\displaystyle{ a \in X}\), piszać a =inf E, gdy:
1. \(\displaystyle{ a \leq x}\) dla \(\displaystyle{ x \in E}\)
2. jesli \(\displaystyle{ b \leq x}\) dla \(\displaystyle{ x \in E}\), to \(\displaystyle{ b \leq a}\) .
Mówiąc "opisowo" kres dolny to największe z "ograniczeń" dolnych zbioru-i analogicznie całkiem okreslamy kres górny zbioru, tj. jako najmniejsze z ograniczeń górnych...co jest intuicyjnie jasne...
! Definicja
Zbiór L uporządkowany przez relację porządku nazwywa się kratą (ang. lattice) względem tej relacji, jeśli każdy dwuelementowy podzbiór L ma oba kresy: górny i dolny. Gdy L jest kratą, \(\displaystyle{ x, y \in L}\), to kres dolny zbioru \(\displaystyle{ \{x, y\}}\) oznaczamy \(\displaystyle{ x \wedge y}\), zaś kres górny tegoż zbioru przez \(\displaystyle{ x \vee y}\) i zwiemy odpowiednio iloczynem i sumą x i y. A oto dwa "modelowe" i przykłady krat:
Krata \(\displaystyle{ \subset}\)>
P(X) to rodzina wszystkich podzbiorów zbioru X. Jest to algebra Boole'a, w której działaniami \(\displaystyle{ \wedge, \ \vee , \ -}\), są tutaj zwykłe operacje teoriomnogosciowe: iloczynu sumy i uzupełnienia, a el. wyróznione to \(\displaystyle{ 0=\emptyset , \ 1=X}\)....
Krata ,
Zbiór liczb naturalnych z relacją podzielności stanowi kratę rozdzielna, w której \(\displaystyle{ a \wedge b}\) to najwiekszy wspolny dzielnik liczb a,b...zaś \(\displaystyle{ a\vee b}\) to najmniejsza wspolna wielokrotnosc a i b. Zerem tej karty jest 1, jedności ta krata nie ma..,
Przykłady !
Zbior X= \(\displaystyle{ \{ a,b, c, d \}}\) uporzadkowany przez relację S= \(\displaystyle{ \{ (a, a), (b,b), (c, c), (d, d), (a, c), (b, c), (c, d), (a, d), (b, d) \}}\) nie jest kratą gdyz podzbiór \(\displaystyle{ \{a, b \}}\) nie ma kresu dolnego. Elem. największym w zbiorze X jest d, elem. najmniejszego brak...Z kolei przykłądem nieskończnonego zbioru uporzadkowanego, który nie jest kratą jest zbior wszystkich kół na płaszczyznie z relacją inkluzji.
Klasyfikacje Krat
Zaopatrzeni w stosowne narzedzia mozemy w tym miejscu wprowadzić jeden z najważniejszych rodzajów krat....Mają one szeczególnie ciekawe wlasnosci..... Mówimy że krata L jest dystrybutywna (lub rozdzielna), jesli dla dowolnych jej trzech elementów x, y, z zachodzi wzór:
\(\displaystyle{ x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)}\).
Uwaga: W dowolnej kracie można napisać- miedzy elementami wystepującymi w powyższym wzorze po obu stronach rownania- znak \(\displaystyle{ \geq}\). ..... Zachodzi tez ciekawa własnośc (wkw. ) przysługująca tej klasie krat:
jesli \(\displaystyle{ x \wedge z = y \wedge z}\) i \(\displaystyle{ x \vee z = y \vee z}\) , to x=y
Definicja
Gdy krata (L, \(\displaystyle{ \leq}\)) na element najmniejszy, to zwie się on zerem tej kraty i oznaczamy go 0, a gdy L ma element największy, to zwiemy go jednością karty L i oznaczamy 1 . Kratę z zerem i jednością nazywamy ograniczoną.
Jesli \(\displaystyle{ x \in L}\) to element a zwiemy uzupełnieniem x, w ograniczonej kracie L gdy: \(\displaystyle{ a \vee x =1 \ , a \wedge x =0}\). Łatwo pokazać, że w kracie dystrybutywnej, takie uzupełnienie-o ile istnieje, jest jedyne. Wynika to wprost z definicji kraty.... Kratę dystrybutywną z zerem i jednością, której każdy element x ma uzupełnienie (oznaczane: -x), nazywamy algebrą Boole'a. Tak wiec mamy w a. B:
\(\displaystyle{ x \vee -x =1 \ , x \wedge -x =0}\)
Szersze omówienie terii krat znalezc mozna m.in w ksiazkach: G. Birkhoff, Lattice Theory, G. Gratzer General Lattice theory, Z. Moszner, O teorii relacji, i ...T. Traczyk, Wstep do teorii algebr Boole'a.
Zadania
1. Niech symbol Part(X) oznacza zbior wszystkich relacji równowaznosci na zb. X. Wykaż iż jest to krata-ze wzgledu na relacje inkluzji- i zbadaj jej własnosci...., np czym są relacje totalna i pusta w tej kracie....?!
2. Wezmy jako F zbior wszystkich funkcji rzeczywistych o dziedzinie ,. Relacja porzadkujaca \(\displaystyle{ \leq}\) jest okreslona tak :
\(\displaystyle{ f \leq g}\), wtw., gdy \(\displaystyle{ f(x) \leq g(x)}\) dla \(\displaystyle{ x \in \ }\). Wykaz, iz w F nie ma elementow najwiekszego i najmniejszego, ale jest to krata.
3. Okreslmy Y jako rodzinę utworzoną ze zbioru pustego i wszystkich przedziałow ...Jest to krata (relacja inkluzji...). Wykaż ze nie jest ona dystrybutywna.
4. Zauwaz, iz kazdy zbior liniowo uporzadkowany jest krata, (czy musi byc rozdzielna...?) a nastepnie wykaz ze w dowolnej kracie ma miejsce fakt: nastepujace tzr warunki sa sobie rownowazne
a \(\displaystyle{ x \leq y}\)
b \(\displaystyle{ x \wedge y = x}\)
c \(\displaystyle{ x \vee y =y}\)
5. 1) Dany mamy zbior X = \(\displaystyle{ \{ a, b, c, d, e \}}\) wykaz ze z relacją R okresloną ponizej X jest algebra Boole'a., podaj zero i jedność, a nastepnie znajdz uzupełnienie każdego elementu. Wreszcie narysuj jaj diagram (graf) *
R= {(a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (b,c), (b,d), (c,d), (e,d) }
2) Wróć do przykłądu z relacją S (nie kraty- skończonej). Podaj jej graf i przekonaj sie ze ma on kształt "trójnogu" tj. "odwroconej litery Y", zwroc uwage na połozenie elem. a i b.
*Uwaga: Graf relacji porzadkujacej okr. na skonczonym zbiorze X rysuje się jak ponizej: gdy x,y są rozne, \(\displaystyle{ x \leq y}\) i nie mozna "wcisnąć" miedzy nie żadnego elementu z, to fakt ten oznacza sie łaczac punkty x i y odcinkiem i zaznaczajac y powyzej x.