4. Bulove algebre Flashcards
Šta je Bulova algebra?
Bulova algebra je uređena šestorka (B, +,*,’, 0,1) gde su:
- 0 i 1 različiti elementi skupa B
- + i * binarne operacije nad skupom B
- ‘ je unarna operacija nad skupom B
i za koju baže sledeći aksiomi:
B1 (komutativnost) B2 (distributivnost) B3 (def neutralnog elementa) i B4 (def inverznog elementa)
Koliko ima aksioma koje određuju Bulovu algebru?
4 aksiome
O čemu su, zapravo, te četiri aksiome Bulove algebre?
B1: komutativnost sabiranja i množenja
B2: distributivnost sabiranja nad množenjem i obrnuto
B3: 0 je neutral za sabiranje (a 1 za množenje)
B4: inverzni elementi
Kako glasi aksioma B1?
a + b = b + a
a * b = b * a
Kako glasi aksioma B2?
a(b + c) = (a * b) + (0 * c)
a + (b * c) = (a + b) * (a +c)
Kako glasi aksioma B3?
a + 0 = a
a*1 = a
Kako glasi aksioma B4?
a + a’ = 1
a * a’ = 0
Kako se zapravo zapravo zove aksioma B4?
Komplementarnost - a+a’=1, a*a’=0
Kako se pravilno nazivaju ove 4 aksiome Bulove algebre?
B1: komutativnost
B2: distributivnost
B3: postojanje neutralnih elemenata
B4: komplementarnost
Postoje li beskonačne Bulove algebre?
Najverovatnije da, ali sa njima nećemo raditi
Koji su osnovni primeri (modeli) Bulove algebre?
Iskazna algebra, algebra skupova, algebra delitelja nekog broja
Kako izgleda definicija iskazne Bulove algebre?
v. primer 4.2
Kako izgleda definicija Bulove algebre skupova?
v. primer 4.3
Kako izgleda Bulova algebra delitelja nekog skupa?
v.primer 4.4
Šta je dualnost?
Dualnost je osobina koja se primećuje u osmočlanom skupu svih aksioma Bulove algebre - ako + i * i 0 i 1 zamene mesta, dobiće se opet aksioma Bulove algebre. Zbog toga će i skup teorema Bulove algebre biti dualan: ako se dokaže neka teorema, time je njoj dualna teorema automatski dokazana - ne treba je dokazivati
Zašto B4 nije pogrešna, iako su 0 i 1 ‘‘zamenili mesta’’?
Greška je u tome što se algebra tumači kao grupa (polje realnih brojeva). Pogledaj B2 (distribuciju, koja važi u oba smera) Ona takođe ‘‘nema smisla’’, ali stvar je u tome što ovo nisu ‘‘prava sabiranja i oduzimanja’’. Još bolji savet: tumači sve preko teorije skupova (ili iskazne algebre)
Kako se definiše iskazna Bulova algebra?
({tačno, netačno}, i, ili, negacija, netačno, tačno)
Kako se definiše Bulova algebra skupova?
Uređena šestorka
(partitivni skup od A, unija, presek, komplement, prazan skup, skup A)
Kako glase aksiome iskazne Bulove algebre?
B1 (komutativnost) :
a i b = b i a
a ili b = b ili a
B2 (distributivnost):
a i (b ili c) = (a i b) ili (a i c)
a ili (b i c) = (a ili b) i (a ili c)
B3 (neutral):
a i tačno = a
a ili netačno = a
B4 (inverz):
a i (ne)a = netačno
a ili (ne)a = tačno
Kako da zapamtim: da li je ‘i’ + ili je ‘ili’ + ? Odnosno, da li je unija + ili je presek + …?
Unija je sabiranje! Presek je množenje
(ne pitaj me zašto)
Kako glase aksiome Bulove algebre u algebri skupova?
B1 (komutativnost)
X U Y = Y U X
B2 (distributivnost)
X unija (Y presek Z) = (X unija Y) presek (X unija Z)
X presek (Y unija Z) = (X presek Y) unija (X presek Z)
B3 (neutral)
X unija prazan skup = X
X presek ceo skup A = X
B4 (inverz)
X unija X^c = A
X presek X^c = prazan skup
Kako glase aksiome Bulove algebre delitelja
B1 (komutativnost) : nzd(a,b) = nzd(b,a) (isto za nzs)
B2 (distributivnost): a*(a+b) =
… Dopuni!
Kako se dokazuju aksiome Bulove algebre delitelja broja?
Ako je, npr. Bulova algebra delitelja broja 30, onda ćemo 30 predstaviti u obliku p1^a1 * p2^a2 …P_n ^a_n tj. faktorišemo. I onda nzd i nzs se predstavljaju preko funkcija min i max (vidi vežbe)
Koje su osnovne teoreme Bulove algebre?
Idempotentnost, ograničenost, apsorpcija, asocijatovnost, Demorganovi zakoni
(+teoremice: 4.8, 4.10, 4.11 msm da je to to)
Kako glasi zakon idempotencije?
a+a=a odnosno aa=a
Kako se dokazuje idempotentnost?
Kako glasi zakon apsorbcije?
a+ab=a odnosno a(a+b)=a
Kako se dokazuje zakon apsorbcije?
Koji je smisao idempotentnosti?
Binarne operacije a i a daju a:
a+a=a i aa=a
Koji je smisao zakona apsorbcije?
Jedna operacija ‘‘apsorbuje’’ drugu:
a+ab=a i a*(a+b)=a
Kako glasi teorema 4.8?
a+a’b=a+b i a(a’+b)=ab
Koji je smisao teoreme 4.8?
Srodna je sa apsorbcijom…čudna teorema. Jeste kao apsorbcija u smislu da ‘a’ menja ‘a i b’ u ‘a’, ali u ovom slučaju menja “a’ i b” u ‘a i b’. Zapamti je takvom kakva jeste.
a+a’b=a+b
a(a’+b)=ab
Kako se dokazuje teorema 4.8?
Kako glasi zakon asocijativnosti?
(a+b)+c = a+(b+c)
(ab)c = a(bc)
Kako se dokazuje zakon asocijativnosti?
Koji je smisao zakona asocijativnosti?
Ja kažem: zagrade nisu bitne. Korektniji odgovor bio bi da redosled operacija nije bitan
Kako glasi teorema 4.10?
Sistem jednačina a+x=1 i a*x=0 po nepoznatoj x, ima jedinstveno rešenje za sve vrednosti parametra a iz skupa B
Kako se dokazuje teorema 4.10?
(Sistem jednačina a+x=1 i a*x=0 po nepoznatoj x, ima jedinstveno rešenje za sve vrednosti parametra a iz skupa B)
Koji je smisao teoreme 4.10?
(Sistem jednačina a+x=1 i a*x=0 po nepoznatoj x, ima jedinstveno rešenje za sve vrednosti parametra a iz skupa b)
Jedinstvenost inverza!
Kako glasi teorema 4.11?
0’=1 i 1’=0
Koji je smisao teoreme 4.11?
Neutrali su inverzi jedan drugom
Kako se dokazuje teorema 4.11?
Upotrebljavajući teoremu 4.10…
Da li je u Bulovoj algebri funkcija f(x)=x’ bijektivna?
Da, vidi dokaz teoreme 4.12
Kako glasi teorema 4.12?
(a’)’=a
Kako se zovu funkcije za koje važi f(f(x))=x?
Involucije
Da li je uslov da funkcija bude involucija da bude bijektivna?
Da
Koji je smisao teoreme 4.12?
Inverz inverza elementa je taj element
Kako se dokazuje teorema 4.12?
Kako glase Demorganovi zakoni?
(a+b)’=a’b’ i (ab)’=a’+b’
Kako se dokazuju Demorganovi zakoni?
Kako glase uopštenja Demorganovih zakona?
(a1+a2+…a_n)=a1’a2’…a_n’
i
(a1a2…a_n)’=a1’+a2’+…a_n’
Koji je smisao Demorganovih zakona?
Inverz zbira je proizvod inverza.
Takođe, inverz proizvoda je zbir inverza
Šta je podalgebra?
Algebra čiji je skup (‘‘osnova’’) podskup ‘‘nadalgebre’’, a operacije nad njim su restrikcije originalnih funkcija
Šta znači zatvorenost?
Za svaka dva elementa, rezultat operacija nad njima mora pripadati istom skupu i inverz svakog elementa pripada skupu
Koji je smisao teoreme 4.15?
To je tvrđenje ekvivalentno definiciji Bulove podalgebre. Kaže da je C podalgebra Bulove algebre B ako je C podskup od B i obe operacije definisane nad B su zatvorene i u skupu C
Da li je moguće da u Bulovoj podalgebri ne važi zatvorenost?
Nikako
Kako glasi teorema 4.15?
Bulova algebra C = (C, +, ,’ , 0,1) jeste podalgebra Bulove algebre B = (B, +,,’, 0,1) akko je C podskup od B, i operacije iz C su restrikcije operacija iz B.
Kako se dokazuje teorema 4.15?
Šta je ona binarna relacija ‘‘iskrivljeno manje jednako’’?
Kako se matematički definiše ‘‘iskrivljeno manje-jednako’’?
(Za svako x iz A)(postoji y iz B) x __<__y <=> x+y=y
Da li je ‘‘iskrivljeno manje jednako’’ relacija ekvivalencije?
Ne
Da li je ‘‘iskrivljeno manje-jednako’’ relacija poretka?
Da
Koliko elemenata ima podalgebra?
2^n
