Matematyka dyskretna 2004 - 05 Funkcje boolowskie.pdf - Matematyka dyskretna - Minnie_

Matematyka Dyskretna

Andrzej Szepietowski

25 marca 2004 roku

Rozdział 1

Funkcje boolowskie

1.1 Algebra Boole’a

Najprostszym przykładem algebry Boole’a jest zbiór dwuelementowy:

B =f0; 1g;

z trzema operacjami: alternatyw a, koniunkcj a i negacj a.

Alternatywa , któr a bedziemy tez nazywac po prostu sum a, jest operacj a dwuargumen-

tow a, oznaczan a przez:

p + q

lub

p_q;

i okreslon a przez tabele:

p q p+q

0 0

0 1

1 0

1 1

Koniunkcja (lub iloczyn) jest drug a operacj a dwuargumentow a, oznaczan a przez:

lub p^q;

i okreslon a przez tabele:

p q pq

0 0

0 1

1 0

1 1

Rozdział 1. Funkcje boolowskie

Podobnie jak w arytmetyce, kropke bedziemy opuszcza c, jezeli nie bedzie to prowadzic

do niejednoznacznosci.

Operacje alternatywy i koniunkcji mozna tez zdeﬁniowa c za pomoc a nastepuj acych

wzorów:

p + q = maxfp; qg;

pq = minfp; qg:

Negacja jest operacj a jednoargumentow a, oznaczan a przez:

lub

i okreslon a przez tabele:

p :p

Algebre B =f0; 1g mozemy interpretowac jako logike zdaniow a. Zmienne s a zdaniami,

które mog a przyjmowac wartosci prawda lub fałsz. Jezeli oznaczymy prawde przez 1 i

fałsz przez 0 , to powyzej zdeﬁniowane operacje odpowiadaj a znanym operacjom z logiki

zda n.

Lemat 1.1 Operacje alternatywy, koniunkcji i negacji spełniaj a w algebrze B =f0; 1g

nastepuj ace tozsamosci:

(a) p + q = q + p;

pq = qp

(alternatywa i koniunkcja s a przemienne),

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

(pq)r = p(qr)

(alternatywa i koniunkcja s a

ł aczne),

(alternatywa jest rozdzielna wzgledem koniunkcji),

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

(koniunkcja jest rozdzielna wzgledem alternatywy),

(e) p + 0 = p ,

p0 = 0 ,

p + 1 = 1 ,

p1 = p ,

(f) p + p = p ,

p +:p = 1 ,

pp = p ,

p:p = 0 ,

(g) p + (pq) = p ,

p(p + q) = p

(prawa pochłaniania),

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

(prawa de’Morgana),

(i) ::p = p

(prawo podwójnego przeczenia).

Najprostsze dowody powyzszych tozsamosci polegaj a na sprawdzeniu, ze zachodz a one

dla kazdego mozliwego podstawienia za zmienne wartosci 1 lub 0. Na przykład, udowod-

nimy tozsamosc:

p + pq = p:

Wszystkie mozliwe podstawienia zebrane s a w tabeli:

1.1. Algebra Boole’a

p q p + pq

0 0

0 1

1 0

1 1

Poniewaz trzecia kolumna jest identyczna z pierwsz a, wiec równosc p + pq = p jest

prawdziwa dla kazdego podstawienia, czyli jest tozsamosci a.

1.1.1 Algebra podzbiorów

Innym przykładem algebry Boole’a jest zbiór 2 X wszystkich podzbiorów jakiegos zbioru

X z operacjami okreslonymi w nastepuj acy sposób:

A + B jest sum a mnogosciow a A[B

AB jest iloczynem A\B

:A jest uzupełnieniem zbioru, :A = XA ,

1 jest całym zbiorem X ,

0 jest zbiorem pustym ; .

Wszystkie równosci z Lematu 1.1 s a tozsamosciami w algebrze podzbiorów 2 X , to zna-

czy s a spełnione przy dowolnym podstawieniu podzbiorów za zmienne p , q i r . Na przy-

kład dla dowolnych podzbiorów A , BX zachodzi A + AB = A . Rzeczywiscie, 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 składnika sumy

A + AB , czyli nie nalezy do A + AB . Tak wiec zbiory A i A + AB zawieraj a dokładnie

te same elementy, a wiec s a równe.

1.1.2 Alternatywa wykluczaj aca, xor

Oprócz trzech podstawowych, w algebrze Boole’a deﬁniuje sie inne operacje. Dla nas

wazna bedzie operacja xor (ang. exclusive or ) albo alternatywa wykluczaj aca. xor jest

operacj a dwuargumentow a, oznaczan a przez:

i okreslon a przez tabele:

p q pq

0 0

0 1

1 0

1 1

Matematyka dyskretna 2004 - 05 Funkcje boolowskie.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: