[ Pobierz całość w formacie PDF ]
.��Matematyka DyskretnaAndrzej Szepietowski25 czerwca 2002 roku Rozdział 1Funkcje boolowskie1.1 Algebra Boole aPrzykładem algebry Boole a jest zbiór dwuelementowy:z trzema operacjami: alternatyw� koniunkcja i negacja.a, � �Alternatywa, która bedziemy też nazywać po prostu sum� jest operacja dwuargumentow�,� � a, � aoznaczana przez:�lubi określona przez tabele:� �p q p+q0 0 00 1 11 0 11 1 1Koniunkcja (lub iloczyn) jest druga operacja dwuargumentow�, oznaczana przez:� � a �lubi określona przez tabele:� �p q0 0 00 1 01 0 01 1 13 4 Rozdział 1.Funkcje boolowskiePodobnie jak w arytmetyce, kropke bedziemy opuszczać, jeżeli nie bedzie to prowadzić� � �do niejednoznaczności.Operacje alternatywy i koniunkcji można też zdefiniować za pomoca nastepujacych� � �wzorów:Negacja jest operacja jednoargumentow�, oznaczana przez:� a �lubi określona przez tabele:� �p0 11 0Algebre możemy interpretować jako logike zdaniow� Zmienne sa zdaniami,� � a.�które moga przyjmować wartości prawda lub fałsz.Jeżeli oznaczymy prawde przez i� �fałsz przez , to powyżej zdefiniowane operacje odpowiadaja znanym operacjom z logiki�zdań.Lemat 1.1 Operacje alternatywy, koniunkcji i negacji spełniaja nastepujace tożsamości:� � �(a) (alternatywa i koniunkcja sa przemienne),�(b) (alternatywa i koniunkcja sa�łaczne),�(c) (alternatywa jest rozdzielna wzgledem koniunkcji),�(d) (koniunkcja jest rozdzielna wzgledem alternatywy),�(e) , , , ,(f) , , , ,(g) , (prawa pochłaniania),(h) , (prawa de Morgana),(i) (prawo podwójnego przeczenia).Najprostsze dowody powyższych tożsamości polegaja na sprawdzeniu, że zachodza one� �dla każdego możliwego podstawienia za zmienne wartości 1 lub 0.Na przykład, udowod-nimy tożsamość:Wszystkie możliwe podstawienia zebrane sa w tabeli:� 1.1.Algebra Boole a 5p q0 0 00 1 01 0 11 1 1Ponieważ trzecia kolumna jest identyczna z pierwsza, wiec równość jest� �prawdziwa dla każdego podstawienia, czyli jest tożsamościa.�Innym przykładem algebry Boole a jest zbiór wszystkich podzbiorów jakiegoś zbioruz operacjami określonymi w nastepujacy sposób:� �jest sum� mnogościow�a ajest iloczynemjest uzupełnieniem zbioru, ,1 jest zbiorem ,0 jest zbiorem pustym.Także te operacje spełniaja tożsamości z lematu 1.1.�Udowodnimy, dla przykładu, tożsamość.Jeżeli element należy dozbioru , to należy także do sumy.Jeżeli zaś nie należy do , to nie należytakże do iloczynu , a wiec nie należy do żadnego składnika sumy , czyli nie�należy do.Tak wiec zbiory i zawieraja dokładnie te same elementy,� �a wiec sa równe.� �Oprócz trzech podstawowych, w algebrze Boole a definiuje sie inne operacje.Dla nas�ważna bedzie operacja xor (ang.exclusive or) albo alternatywa wykluczajaca.xor jest� �operacja dwuargumentow�, oznaczana przez:� a �i określona przez tabele:� �p q0 0 00 1 11 0 11 1 0Operacja ta jest nazywana alternatyw� wykluczajaca, ponieważ w logice zdanioweja � �zdanie jest prawdziwe, jeżeli albo , albo jest prawdziwe, ale nie jest prawdziwe,gdy i naraz sa prawdziwe.Operacja ma nastepujace własności:� � �Lemat 1.2(a) (jest przemienna), 6 Rozdział 1.Funkcje boolowskie(b) (jest łaczna),�(c) (xor jest rozdzielne wzgledem koniunkcji),�(d) , , , ,(e) Jeżeli , to.(f) zbiór z działaniami xor i koniunkcji tworzy ciało.Aaczność operacji zapewnia, że możemy opuszczać nawiasy w wyrażeniach typu�, bez spowodowania niejednoznaczności.Operacje xor można zdefiniować poprzez alternatyw� koniunkcje i negacje:� e, � �W algebrze podzbiorów operacja xor odpowiada różnicy symetrycznej:1.2 Wyrażenia boolowskiePodobnie jak wyrażenia arytmetyczne, możemy budować wyrażenia boolowskie.Wyra-żeniami boolowskimi sa stałe i oraz zmienne boolowskie (typu boolean).Bardziej�złożone wyrażenia można budować za pomoca operatorów boolowskich i nawiasów.Je-�żeli i sa dwoma wyrażeniami boolowskimi, to wyrażeniami boolowskimi sa także� �nastepujace wyrażenia:� �1.2.1 Wyrażenia boolowskie w jezyku Pascal�W jezyku Pascal wyrażeniami boolowskimi sa stałe true i false oraz zmienne ty-� �puboolean.Wyrażenia boolowskie można też budować z wyrażeń arytmetycznych zapomoca tak zwanych operatorów relacyjnych.Jeżeli U i W sa dwoma wyrażeniami aryt-� �metycznymi, to wyrażeniem boolowskim jest wyrażenie:U op W,gdzieopoznacza dowolny operator relacyjny.Operatory relacyjne sa zestawione w tabeli:�operator znaczenie= równewieksze�różne= wieksze lub równe� 1.3.Funkcje boolowskie 7Wyrażenia boolowskie można także budować za pomoca operatorów boolowskich i na-�wiasów.JeżeliUiWsa dwoma wyrażeniami boolowskimi, to wyrażeniami boolowskimi�sa także nastepujace wyrażenia:� � �U or W (suma lub alternatywa),U and W (koniunkcja),not W (negacja),U xor W (exclusive or lub alternatywa wykluczajaca),�(U) (wyrażenieUwziete w nawias).�Przykładami wyrażeń boolowskich w jezyku Pascal sa:� �true or b,b and not(x>=0),(0
[ Pobierz całość w formacie PDF ]