Egzamin z matematyki dyskretnej.
I termin, 15 czerwca 2010.
1. Diagram Hassego zamieszczony obok przedstawia pewną kratę L.
(a) Znaleźć atomy i coatomy tej kraty.
(b) Czy krata L jest dystrybutywna?
q
(c) Czy krata L jest modularna?
q q q
q
@
(d) Czy diagram ten może być diagramem algebry Boole’a?
q @q
q
@
(e) Narysować diagram Hassego kraty Con(L) tj. kraty kongruencji kraty L.
L
(f) Czy krata L jest rozkładalna na produkt prosty? Jeśli tak, to przedstawić jej rozkład.
(g) Czy krata L jest rozkładalna na produkt podprosty? Jeśli tak, to przedstawić jej rozkład na produkt podprosty. Przedstawić na diagramie podproste zanurzenie.
Szkic rozwiązania
Punkt (a).
Na rysunku poniżej zaznaczone są atomy i coatomy kraty L.
coatomy
b
b
b
b
b
b
b
atomy
b
Punkty (b) i (c).
Krata L nie jest ani dystrybutywna ani modularna gdyż można w niej zanurzyć pięciokąt:
b
b
b
b
b
b
b
b
b
b
b
b
b
Punkt (d).
Krata L nie jest dystrybutywna a zatem nie może być diagramem algebry Boole’a.
Punkt (e).
Na poniższym rysunku przedstawione są kongruencje kraty L: b
b
r3
b
b
r2
b
b
b
r1
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
r7
r6
b
b
r5
b
b
b
b
b
b
r4
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
r10
r11
b
b
b
b
b
r9
r8
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Tworzą one kratę o następującym diagramie Hassego: b
r11
b
b
b r10
r9
b
b
b
r8
r7
r6
b
b
b
r4
r5
r3
b
b
r1
r2
b
Punkt (f).
Krata L nie jest rozkładalna na produkt prosty. Istotnie. Załóżmy, że istnieją dwie nietrywialne kraty L1 oraz L2 takie, że: L ' L1 × L2.
Wtedy L ' 23 lub L ' 2 × C4 - sprzeczność.
Punkt (g).
Krata Con(L) ma dwa atomy: r1 oraz r2. Zatem krata L jest podprosto rozkładalna. Zauważmy, że
L/r1 ' L/r2 ' N5.
N5 jest kratą podprosto nierozkładalną. Rysunek poniżej przedstawia podproste zanurzenie kraty L w produkt N25.
bb
b
bb
b
b
b
bb
bb
b
b
b
bb
bb
bb
b
bb
bb
b
b
b
b
bb
bb
bb
b
b
bb
b
b
bb
bb
b
bb
2