algebra boola

[ Pobierz całość w formacie PDF ]
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
0 1
1
1 0
1
1 1
1
Koniunkcja
(lub iloczyn) jest drug a operacj a dwuargumentow a, oznaczan a przez:
pq
lub
p^q;
i okreslon a przez tabele:
p q
pq
0 0
0
0 1
0
1 0
0
1 1
3
1
4
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 zdefiniowa c za pomoc a nastepuj acych
wzorów:
p + q = maxfp; qg;
pq = minfp; qg:
Negacja
jest operacj a jednoargumentow a, oznaczan a przez:
:p
lub
p;
i okreslon a przez tabele:
p
:p
0
1
1
0
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 zdefiniowane 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),
(c)
(p + q)r = pr + qr
(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
5
p q
p + pq
0 0
0
0 1
0
1 0
1
1 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 definiuje 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:
pq
i okreslon a przez tabele:
p q
pq
0 0
0
0 1
1
1 0
1
1 1
0
[ Pobierz całość w formacie PDF ]