hpqscan0002 (3)

Wyniki

Imię i nazwisko ..............................................................

Egzamin z matematyki dyskretnej. I rok studiów magisterskich.

I termin, 19 czerwca 2007.

Uwaga. Wszystkie rozwiązania powinny być bardzo dokładnie i w miarę możliwości formalnie uzasadnione. Rozwiązania poszczególnych zadań oceniane są jako całość. Na ocenę wpływa również sposób, poprawność i precyzja argumentacji. Duże błędy mogą dyskwalifikować całe rozwiązanie danego zadania, a błędy o charakterze zasadniczym

mogą dyskwalifikować cały egzamin.

1. Niech <£q(A) = (Eq(A); n,    gdzie

U<5₅(<Hq(A)): Eq(A)² —*Eq(A) ((x, y) J_5((£q(A))(x U y)) będzie algebrą typu (2, 2). Czy <£q(A) jest kratą? Jeśli tak to opisać jej własno-

2.    (i) Niech IB = (U; -, +,' , 0,1) będzie skończoną algebrą BooIe’a. Kratę 03/ =

{B\ •,+) nazywamy kratowym reduktem algebry Boołe’a 03. Wykazać, że

(a)    At(OB) jest zbiorem niepustym.    (2pt)

(b)    Wykazać następujące twierdzenie:

Stwierdzenie 1

Vx € 3 3! y € 7^:>(At(t3)) z = sup(y).

<

gdzm < jest kratowym porządkiem częścioujym w 23/.

(ii)    Niech 03i, 03₂ będą skończonymi algebrami Boole’a. Wykazać, że:    (3pt)

(a)    03i ~    «=► |At(Si)| = |At(S_?)J.

(b)    (y: Si ^ S₂, ip: Si ^ S₂₎ v|At(»!) = ^Utc®!)) => <f = p.

(iii)    Niech Q3i, 03₂ będą skończonymi algebrami Boole’a. Czy prawdą jest,

że:    (5pt)

(a)    Si < 0S₂ => At(Si) C At(S₂) ?

(b)    At(Si) C At(S₂) => Si < 0S₂ ?

(iv)    Niech 03 będzie skończoną algebrą Boole’a. Wykazać, że algebra 03 ~

S(At(Q3)), gdzie ip(At(S)) = (iP(At(93)); fi, U/ , 0, At(SB)). Mówiąc mniej dokładnie: skończona algebra Boole’a jest izomorficzna algebrze Boole’a określonej na zbiorze podzbiorów jej atomów z działaniami iloczynu mnogościowego, sumy mnogościowej, dopełnienia zbioru oraz zbiorem pustym i zbiorem atomów algebry IB jako wyróżnionymi elementami.    (5pt)

(v)    Czy istnieje algebra Boole^!a 23 taka. że At(03) = 0?    (5pt)

3.    Diagram Hassego zamieszczony obok przedstawia pewną kratę £.

(i)    Znaleźć atomy i coatomy tej kraty.    (lpt)

(ii)    Czy krata £ jest dystrybutywna?    (ipt)

------(iii) Czy krata £ jest modularna?    (ipt)

(iv)    Czy diagram ten może być diagramem algebry Boole^!a?    (2pt)

(v)    Narysować diagram Hassego £on(£).    (lOpt)

(vi)    Czy krata £ jest rozkładalna na produkt prosty? Jeśli tak, to przedstawić

jej rozkład.    (⁵p0

(vii)    Czy krata £ jest rozkładalna na produkt podprosty? Jeśli tak, to przedsta

wić jej rozkład na produkt podprosty. Przedstawić na diagramie podproste zanurzenie.    f⁵P^fc)

4.    Wykazać następujące stwierdzenie:

Stwierdzenie 2 Niech 21 będzie algebrą typu u, (5h)ig/ rodziną algebr typu u.

1
2
3
4
6

4

S = min{ £ _Pil 50), i = l

gdzie p,- oznacza liczbę punktów uzyskaną za zadanie o numerze :.

(15pt)

(20pt)

Symbol 3! ma następujące znaczenie: istnieje dokładnie jedno....

(25p t)

(lOpt)