Uspořádané množiny:
Nechť A je tvořena všemi konečnými podmnožinami množiny N, jejichž
prvky jsou nesoudělná čísla.
1. Rozhodněte, které z následujících množin patří do A:
(a) {2,3,8} (c) {2,5} (e) {4,6,8}
(b) {2,3,5,8} (d) {2,3,4,5,...} (f) {2,3}
2. A tvoří spolu s uspořádáním inkluzí poset (částečně uspořádanou množinu).
Nechť B je tvořena těmi množinami z A, které patří do A. Nakreslete hasseovský
diagram (B, C).
3. Dokažte, že pokud v uspořídané množině existuje nejmenší (největší) prvek,
pak je určen jednoznačně. Platí totéž i o minimálním (maximálním)
prvku?
4. Nachť je množina {2, 3, 4, 5, 6, 8,10} uspořádána podle relace ,,být násob
kern". Určete
(a) maximální prvky
(b) minimální prvky
(c) největší a nejmenší prvek
5. Uvažme podmnožinu racionálních čísel A = {x e Q;x3
< 3}. Rozhodněte
zda:
(a) Existuje horní (dolní) závora A.
(b) Existuje supremum (infimum) A
Booleovské algebry: Booleovská algebra je čtveřice (if, A, V,'), splňující
pro A,B,C e K:
A A (B A C) = {A AB) A C, AV {By C) = {Ay B)V C (1)
AAB = BAA, AV B = BV A (2)
A A {B V C) = {A A B)V {A A C),
AV {B AC) = {AV B)A{AVC) (3)
existuje 0 tak, že A V 0 = A (4)
existuje 1 tak, že A A 1 = A (5)
AAÄ = {), AVA' = Í. (6)
1. Dokažte, že v booleovské algebře platí:
(a) AA0 = 0, AV1 = 1
(b) (absorpce) A A {A V B) = A, A V {A A B) = A
(c) (idempotence) A A A = A, AV A = A
(d) (de Morganova pravidla) {A A B)' = A'V B', {A V B)' = A' A B'
(e) (involuce) {A')' = A.
2. Nakreslete systém přepínačů odpovídající booleovskému výrazu
[{A A B) V C] A [D V {A' AB)}.
3. Zjednodušte systém přepínačů na obrázku.
4. Navrhněte z přepínačů ,,volební skříňku" pro tři voliče tak, že výstup bude
respektovat vůli většiny.
Atom v Booleově algebře je takový prvek A , že všechny prvky B G K splňují
buď A < B nebo A A B = 0.
Každý prvek v konečné booleovské algebře lze zapsat jako supremum atomů
(a to jednoznačně až na pořadí).
1. Určete disjunktivní normální formu výrazu
{{A AB) V C)' A{A'V {B AC A D)).
2