fbool.pdf

Matematyka dyskretna

Funkcje boolowskie

Andrzej Szepietowski

1 Algebra Boole'a

Przykladem algebry Boole'a jest zbior dwuelementowy:

B =f0; 1g;

z trzema operacjami: alternatywa, koniunkcja i negacja.

Alternatywa, ktora bedziemy tez nazywac po prostu suma, jest operacja dwuargumentowa,

oznaczana przez:

p + q

lub p_q;

i okreslona przez tabele:

p q p+q

0 0

0 1

1 0

1 1

Koniunkcja (lub iloczyn) jest druga operacja dwuargumentowa, oznaczana przez:

lub p^q;

i okreslona przez tabele:

p q pq

0 0 0

0 1 0

1 0 0

1 1 1

Podobnie jak w arytmetyce, kropke bedziemy opuszczac, jezeli nie bedzie to prowadzic do niejed-

noznacznosci.

Operacje alternatywy i koniunkcji mozna tez zdeniowac za pomoca nastepujacych wzorow:

p + q = maxfp; qg; pq = minfp; qg:

Negacja jest operacja jednoargumentowa, oznaczana przez:

lub

i okreslona przez tabele:

p :p

Algebre B =f0; 1gmozemy interpretowac jako logike zdaniowa. Zmienne sa zdaniami, ktore moga

przyjmowac wartosci prawda lub falsz. Jezeli oznaczymy prawde przez 1 i falsz przez 0, to powyzej

zdeniowane operacje odpowiadaja znanym operacjom z logiki zdan.

Operacje alternatywy, koniunkcji i negacji spelniaja nastepujace tozsamosci:

(1) p + q = q + p;

pq = qp

(alternatywa i koniunkcja sa przemienne),

(2) p + (q + r) = (p + q) + r;

(pq)r = p(qr)

(alternatywa i koniunkcja sa laczne),

(3) (p + q)r = pr + qr

(alternatywa jest rozdzielna wzgledem koniunkcji),

(4) (pq) + r = (p + r)(q + r)

(koniunkcja jest rozdzielna wzgledem alternatywy),

(5) p + 0 = p,

p0 = 0,

p + 1 = 1,

p1 = p,

(6) p + p = p,

p +:p = 1,

pp = p,

p:p = 0,

(7) p + (pq) = p,

p(p + q) = p

(prawa pochlaniania),

(8):(p + q) =:p:q, :(pq) =:p +:q

(prawa de'Morgana),

(9)::p = p

(prawo podwojnego przeczenia).

Najprostsze dowody powyzszych tozsamosci polegaja na sprawdzeniu, ze zachodza one dla kazdego

mozliwego podstawienia za zmienne wartosci 1 lub 0. Na przyklad, udowodnimy tozsamosc:

p + pq = p:

Wszystkie mozliwe podstawienia zebrane sa w tabeli:

p q p + pq

0 0

0 1

1 0

1 1

Poniewaz trzecia kolumna jest identyczna z pierwsza, wiec rownosc p + pq = p jest prawdziwa dla

kazdego podstawienia, czyli jest tozsamoscia.

Innym przykladem algebry Boole'a jest zbior wszystkich podzbiorow jakiegos zbioru X z oper-

acjami okreslonymi w nastepujacy sposob:

A + B jest suma mnogosciowa, A[B =fx2X : x2A lub x2Bg,

AB jest iloczynem lub czescia wspolna, A\B =fx2X : x2A i x2Bg,

:A jest uzupelnieniem zbioru,:A = XA =fx2X : x =2Ag,

1 jest zbiorem X,

0 jest zbiorem pustym;.

Takze te operacje spelniaja tozsamosci (1)|(9).

Udowodnimy, dla przykladu, te sama tozsamosc A + AB = A. Jezeli element x nalezy do zbioru

A, to nalezy takze do sumy A + AB. Jezeli zas x nie nalezy do A, to nie nalezy takze do iloczynu

AB, a wiec x nie nalezy do zadnego skladnika sumy A + AB, czyli nie nalezy do A + AB. Tak wiec

zbiory A i A + AB zawieraja dokladnie te same elementy, a wiec sa rowne.

Oprocz trzech podstawowych, w algebrze Boole'a deniuje sie inne operacje. Dla nas wazna

bedzie operacja xor (ang. exclusive or) albo alternatywa wykluczajaca. xor jest operacja dwuargu-

mentowa, oznaczana przez:

i okreslona przez tabele:

p q pq

0 0

0 1

1 0

1 1

Operacja ta jest nazywana alternatywa wykluczajaca, poniewaz w logice zdaniowej zdanie pq

jest prawdziwe, jezeli albo p, albo q jest prawdziwe, ale nie jest prawdziwe, gdy p i q naraz sa

prawdziwe. Operacja xor ma nastepujace wlasnosci:

(10) pq = qp

(jest przemienna),

(11) (pq)r = p(qr)

(jest laczna),

(12) (pq)r = prqr

(xor jest rozdzielne wzgledem koniunkcji),

(13) x0 = x,

x1 = x,

xx = 0,

xx = 1,

(14) zbior B =f0; 1gz dzialaniami xor i koniunkcji tworzy cialo.

Lacznosc operacjizapewnia, ze mozemy opuszczac nawiasy w wyrazeniach typu (qq)r, bez

spowodowania niejednoznacznosci.

Operacje xor mozna zdeniowac poprzez alternatywe, koniunkcje i negacje:

pq = pq + pq:

W algebrze podzbiorow operacja xor odpowiada roznicy symetrycznej:

AB = (AB)[(BA):

Roznica symetryczna AB zawiera te elementy, ktore naleza tylko do jednego ze zbiorow A lub

B (a nie naleza do przekroju). Roznica symetryczna trzech zbiorow:

ABC;

zawiera te elementy, ktore naleza do nieparzystej liczby zbiorow, czyli te, ktore naleza tylko do A,

plus te, ktore naleza tylko do B, plus te, ktore naleza tylko do C, plus te, ktore naleza do przekroju

A\B\C. Mozemy to uogolnic.

Twierdzenie 1 Roznica symetryczna n zbiorow:

A 1 A 2 : : :A n

zawiera te elementy, ktore naleza do nieparzystej liczby zbiorow sposrod A 1 , A 2 ; : : : ; A n .

Dowod przez indukcje ze wzgledu na n. Twierdzenie jest oczywiste dla n = 1 lub n = 2.

Zalozmy teraz, ze jest ono prawdziwe dla n i rozpatrzmy:

A 1 : : :A n A n+1 = (A 1 : : :A n )A n+1 :

Zbior ten zawiera te elementy, ktore naleza do (A 1 : : :A n ) i nie naleza do A n+1 , oraz te, ktore nie

naleza do (A 1 : : :A n ) i naleza do A n+1 . W pierwszym przypadku sa to elementy, ktore nie naleza

do A n+1 i naleza do jakiejs nieparzystej liczby zbiorow sposrod A 1 ; : : : ; A n . W drugim przypadku sa

to elementy, ktore naleza do A n+1 , a takze do pewnej parzystej liczby zbiorow sposrod A 1 ; : : : ; A n .

Razem mamy wszystkie elementy nalezace do nieparzystej liczby zbiorow sposrod A 1 ; : : : ; A n+1 .

2 Wyrazenia boolowskie

Podobnie jak wyrazenia arytmetyczne, mozemy budowac wyrazenia boolowskie. Wyrazeniami

boolowskimi sa stale 0 i 1 oraz zmienne boolowskie (typu boolean). Bardziej zlozone wyrazenia

mozna budowac za pomoca operatorow boolowskich i nawiasow. Jezeli U i W sa dwoma wyrazeniami

boolowskimi, to wyrazeniami boolowskimi sa takze nastepujace wyrazenia:

U + W;

UW; :U;

(U ):

3 Wyrazenia boolowskie w jezyku Pascal

W jezyku Pascal wyrazeniami boolowskimi sa stale true i false oraz zmienne typu boolean.

Wyrazenia boolowskie mozna tez budowac z wyrazen arytmetycznych za pomoca tak zwanych

operatorow relacyjnych. Jezeli U i W sa dwoma wyrazeniami arytmetycznymi, to wyrazeniem

boolowskimi jest wyrazenie:

U op W,

gdzie op oznacza dowolny operator relacyjny. Operatory relacyjne sa zestawione w tabeli:

operator znaczenie

rowne

mniejsze

wieksze

rozne

mniejsze lub rowne

wieksze lub rowne

Wyrazenia boolowskie mozna takze budowac za pomoca operatorow boolowskich i nawiasow. Jezeli

U i W sa dwoma wyrazeniami boolowskimi, to wyrazeniami boolowskimi sa takze nastepujace

wyrazenia:

U or W (suma lub alternatywa),

U and W (koniunkcja),

not W (negacja),

U xor W (exclusive or lub alternatywa wykluczajaca),

(U) (wyrazenie U wziete w nawias).

Przykladami wyrazen boolowskich w jezyku Pascal sa:

true or b,

b and not(x>=0),

(0<=x) and (x<=10),

(0<x) or (x>10).

gdzie b jest zmienna typu boolean, a x | zmienna liczbowa.

Przypomnijmy, ze wyrazenia boolowskie wystepuja w jezyku Pascal w instrukcjach warunk-

owych lub w petlach while i repeat.

4 Funkcje boolowskie

Funkcje boolowskie n zmiennych to funkcje:

f : B n !B;

gdzie B =f0; 1g. Mamy cztery funkcje boolowskie jednej zmiennej:

funkcje stala f 0 rowna 0,

identycznosc f 1 ,

negacje f 2 ,

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: