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 = {0, 1},
z trzema operacjami: alternatywÄ…, koniunkcjÄ… i negacjÄ….
Alternatywa, którą będziemy też nazywać po prostu sumą, jest operacją dwuargumen-
towÄ…, oznaczanÄ… przez:
p + q lub p (" q,
i określoną przez tabelę:
p q p+q
0 0 0
0 1 1
1 0 1
1 1 1
Koniunkcja (lub iloczyn) jest drugÄ… operacjÄ… dwuargumentowÄ…, oznaczanÄ… przez:
p · q lub p '" q,
i określoną przez tabelę:
p q p · q
0 0 0
0 1 0
1 0 0
1 1 1
3
4 Rozdział 1. Funkcje boolowskie
Podobnie jak w arytmetyce, kropkę będziemy opuszczać, jeżeli nie będzie to prowadzić
do niejednoznaczności.
Operacje alternatywy i koniunkcji można też zdefiniować za pomocą następujących
wzorów:
p + q = max{p, q}, p · q = min{p, q}.
Negacja jest operacjÄ… jednoargumentowÄ…, oznaczanÄ… przez:
Źp lub p,
Å»
i określoną przez tabelę:
p Źp
0 1
1 0
Algebrę B = {0, 1} możemy interpretować jako logikę zdaniową. Zmienne są zdaniami,
które mogą przyjmować wartości prawda lub fałsz. Jeżeli oznaczymy prawdę przez 1 i
fałsz przez 0, to powyżej zdefiniowane operacje odpowiadają znanym operacjom z logiki
zdań.
Lemat 1.1 Operacje alternatywy, koniunkcji i negacji spełniają w algebrze B = {0, 1}
następujące tożsamości:
(a) p + q = q + p, pq = qp (alternatywa i koniunkcja sÄ… przemienne),
(b) p + (q + r) = (p + q) + r, (pq)r = p(qr) (alternatywa i koniunkcja sÄ…
Å‚Ä…czne),
(c) (p + q)r = pr + qr (alternatywa jest rozdzielna względem koniunkcji),
(d) (pq) + r = (p + r)(q + r) (koniunkcja jest rozdzielna względem alternatywy),
(e) p + 0 = p, p · 0 = 0, p + 1 = 1, p · 1 = 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 powyższych tożsamości polegają na sprawdzeniu, że zachodzą one
dla każdego możliwego podstawienia za zmienne wartości 1 lub 0. Na przykład, udowod-
nimy tożsamość:
p + pq = p.
Wszystkie możliwe podstawienia zebrane są w tabeli:
1.1. Algebra Boole a 5
p q p + pq
0 0 0
0 1 0
1 0 1
1 1 1
Ponieważ trzecia kolumna jest identyczna z pierwszą, więc równość p + pq = p jest
prawdziwa dla każdego podstawienia, czyli jest tożsamością.
1.1.1 Algebra podzbiorów
Innym przykładem algebry Boole a jest zbiór 2X wszystkich podzbiorów jakiegoś zbioru
X z operacjami określonymi w następujący sposób:
" A + B jest sumą mnogościową A *" B
" A · B jest iloczynem A )" B
" ŹA jest uzupełnieniem zbioru, ŹA = X - A,
" 1 jest całym zbiorem X,
" 0 jest zbiorem pustym ".
Wszystkie równości z Lematu 1.1 są tożsamościami w algebrze podzbiorów 2X, to zna-
czy są spełnione przy dowolnym podstawieniu podzbiorów za zmienne p, q i r. Na przy-
kÅ‚ad dla dowolnych podzbiorów A, B ‚" X zachodzi A + AB = A. RzeczywiÅ›cie, jeżeli
element x należy do zbioru A, to należy także do sumy A+AB. Jeżeli zaś x nie należy do
A, to nie należy także do iloczynu AB, a więc x nie należy do żadnego składnika sumy
A + AB, czyli nie należy do A + AB. Tak więc zbiory A i A + AB zawierają dokładnie
te same elementy, a więc są równe.
1.1.2 Alternatywa wykluczajÄ…ca, xor
Oprócz trzech podstawowych, w algebrze Boole a definiuje się inne operacje. Dla nas
ważna będzie operacja xor (ang. exclusive or) albo alternatywa wykluczająca. xor jest
operacjÄ… dwuargumentowÄ…, oznaczanÄ… przez:
p •" q
i określoną przez tabelę:
p q p •" q
0 0 0
0 1 1
1 0 1
1 1 0
6 Rozdział 1. Funkcje boolowskie
Operacja ta jest nazywana alternatywą wykluczającą, ponieważ w logice zdaniowej
zdanie p •" q jest prawdziwe, jeżeli albo p, albo q jest prawdziwe, ale nie jest prawdziwe,
gdy p i q naraz są prawdziwe. Operację xor można zdefiniować poprzez alternatywę,
koniunkcjÄ™ i negacjÄ™:
p •" q = pq + pq.
Å» Å»
W algebrze podzbiorów operacja xor jest różnicą symetryczną
A •" B = (A - B) *" (B - A).
Lemat 1.2 Następujące równości są tożsamościami w algebrze B = {0, 1} oraz w alge-
brze podzbiorów 2X:
(a) p •" q = q •" p (przemienność xora),
(b) (p •" q) •" r = p •" (q •" r) (Å‚Ä…czność xora),
(c) (p •" q)r = pr •" qr (xor jest rozdzielne wzglÄ™dem koniunkcji),
(d) x •" 0 = x, x •" 1 = x, x •" x = 0, x •" x = 1,
Å» Å»
(e) Jeżeli x •" y = 0, to x = y.
A
Ä…czność operacji •" pozwala opuszczać nawiasy w wyrażeniach typu (q •" q) •" r bez
powodowania niejednoznaczności.
1.2 Wyrażenia boolowskie
Podobnie jak wyrażenia arytmetyczne, możemy budować wyrażenia boolowskie. Wyra-
żeniami boolowskimi są stałe 0 i 1 oraz zmienne boolowskie x, y, z,... Bardziej złożone
wyrażenia można budować za pomocą operatorów boolowskich i nawiasów. Jeżeli U i W
są dwoma wyrażeniami boolowskimi, to wyrażeniami boolowskimi są także następujące
wyrażenia:
U + W, U · W, U •" W, ŹU, (U).
Przykład 1.3 Przykładami wyrażeń boolowskich są:
((x + Źy) · (Źx + 1) + z) + Źy
(1 •" x) · (y + 0)
xy + yz + xz,
gdzie x, y oraz z sÄ… zmiennym boolowskimi.
Jeżeli w wyrażeniu boolowskim za zmienne podstawimy wartości 0 lub 1, to całe wyra-
żenie przyjmie jakąś wartość, 0 lub 1.
Przykład 1.4 W poniższej tabeli zebrano wartości wyrażenia
xy + yz + xz
dla wszystkich możliwych podstawień
1.2. Wyrażenia boolowskie 7
x y z xy + yz + xz
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Jak widać wyrażenie U(x, y, z) = xy + yz + xz opisuje funkcję, która każdemu wek-
torowi z {0, 1}3 przypisuje wartość ze zbioru {0, 1}. Podobnie dowolne inne wyraże-
nie boolowskie W (x1, . . . , xn) ze zmiennymi x1, . . . , xn opisuje funkcję, która każdemu
wektorowi z {0, 1}n przypisuje wartość ze zbioru {0, 1}.
Wyrażenie boolowskie W (x1, . . . , xn) może też być rozpatrywane w algebrze pod-
zbiorów 2X. Wtedy za zmienne podstawiamy podzbiory X i wartość wyrażenia też jest
podzbiorem X.
Przykład 1.5 Niech X = {1, 2, 3, 4, 5} i niech W (x, y, z) = xy + yz + xz będzie
wyrażeniem boolowskim. Po podstawieniu x = {1, 4, 5}, y = {1, 2, 4} oraz z = {3, 4}
wyrażenie otrzyma wartość W (x, y, z) = {1, 4}.
1.2.1 Wyrażenia boolowskie w języku Pascal
W języku Pascal wyrażeniami boolowskimi są stałe true i false oraz zmienne ty-
puboolean. Wyrażenia boolowskie można też budować z wyrażeń arytmetycznych za
pomocą tak zwanych operatorów relacyjnych. Jeżeli U i W są dwoma wyrażeniami aryt-
metycznymi, to wyrażeniem boolowskim jest wyrażenie:
U op W,
gdzieopoznacza dowolny operator relacyjny. Operatory relacyjne sÄ… zestawione w tabeli:
operator znaczenie
= równe
< mniejsze
> większe
<> różne
<= mniejsze lub równe
>= większe lub równe
Wyrażenia boolowskie można także budować za pomocą operatorów boolowskich i na-
wiasów. JeżeliUiWsą dwoma wyrażeniami boolowskimi, to wyrażeniami boolowskimi
są także następujące wyrażenia:
" U or W (suma lub alternatywa),
" U and W (koniunkcja),
8 Rozdział 1. Funkcje boolowskie
" not W (negacja),
" U xor W (exclusive or lub alternatywa wykluczajÄ…ca),
" (U) (wyrażenieUwzięte w nawias).
Przykładami wyrażeń boolowskich w języku Pascal są:
" true or b,
" b and not(x>=0),
" (0<=x) and (x<=10),
" (010).
gdziebjest zmiennÄ… typu boolean, ax zmiennÄ… liczbowÄ….
Wyrażenia boolowskie występują w języku Pascal w instrukcjach warunkowych lub
w pętlach while i repeat.
1.3 Funkcje boolowskie
Funkcja boolowska n zmiennych to dowolna funkcja typu
f : Bn B,
gdzie B = {0, 1}. Funkcja f każdemy ciągowi argumentów (x1, . . . , xn) " Bn przypi-
suje wartość f(x1, . . . , xn) " B. Na przykład tabela
x y z f(x, y, z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
opisuje funkcję boolowską, która przyjmuje wartości 0 dla wektorów (0, 0, 0), (0, 1, 0)
oraz (0, 1, 1) oraz wartość 1 dla wszystkich innych wektorów. W podrozdziale o wyra-
żeniach boolowskich pokazaliśmy, że funkcje boolowskie mogą być opisane za pomocą
wyrażeń boolowskich. Na przykład funkcja f(x, y, z) z powyższej tabeli może być opi-
sana przez wyrażenie
f(x, y, z) = xy + z.
1.3. Funkcje boolowskie 9
1.3.1 Funkcje boolowskie jednej zmiennej
Mamy cztery funkcje boolowskie jednej zmiennej:
" funkcję stałą f0 równą 0,
" identyczność f1,
" negacjÄ™ f2,
" funkcję stałą f3 równą 1.
Wartości tych funkcji zestawiono w tabeli:
x f0(x) f1(x) f2(x) f3(x)
0 0 0 1 1
1 0 1 0 1
Są to wszystkie funkcje boolowskie jednej zmiennej, ponieważ są to funkcje ze zbioru B
w zbiór B, a takich funkcji jest:
|B||B| = 22 = 4.
1.3.2 Funkcje boolowskie dwóch zmiennych
Funkcji boolowskich dwóch zmiennych jest:
2
22 = 24 = 16.
Ich wartości zestawiono w tabeli:
x y f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Zauważmy, że ciąg wartości każdej z tych funkcji czytany od góry do dołu stanowi zapis
binarny jej numeru. Przyjrzyjmy się bliżej tym funkcjom:
" f0 = 0 jest funkcją stałą równą 0,
" f15 = 1 jest funkcją stałą równą 1,
" f1(x, y) = xy jest koniunkcjÄ…,
" f7(x, y) = x + y jest alternatywÄ…,
" f6(x, y) = x •" y = xy + xy jest xorem,
Å» Å»
10 Rozdział 1. Funkcje boolowskie
" f13(x, y) = (x Ò! y) = y + x jest implikacjÄ… z x do y,
Å»
" f11(x, y) = (y Ò! x) = x + y jest implikacjÄ… z y do x,
Å»
" f9(x, y) = (x Ô! y) = Ź(x •" y) = xy + xy jest równoważnoÅ›ciÄ…,
ŻŻ
" f3(x, y) = x jest rzutem na pierwszą współrzędną,
" f5(x, y) = y jest rzutem na drugą współrzędną,
" f10(x, y) = Źy jest negacją drugiej współrzędnej,
" f12(x, y) = Źx jest negacją pierwszej współrzędnej,
" f14(x, y) = Ź(xy) jest zaprzeczeniem koniunkcji, tak zwany nand,
" f8(x, y) = Ź(x + y) jest zaprzeczeniem alternatywy, tak zwany nor,
" f2(x, y) = Ź(x Ò! y) = xy jest zaprzeczeniem implikacji z x do y,
Å»
" f4(x, y) = Ź(y Ò! x) = xy jest zaprzeczeniem implikacji z y do x.
Å»
Jak widać, każdą z tych funkcji można przedstawić za pomocą koniunkcji, alternatywy i
negacji.
1.3.3 Alternatywa i koniunkcja n zmiennych
Alternatywa n zmiennych
n
OR(x1, . . . , xn) = xi = x1 + · · · + xn
i=1
przyjmuje wartość 0 tylko wtedy, wszystkie zmienne od x1 do xn przyjmują wartość 0.
Koniunkcja n zmiennych
n
AND(x1, . . . , xn) = xi = x1 · · · · · xn
i=1
przyjmuje wartość 1 tylko wtedy, wszystkie zmienne od x1 do xn przyjmują wartość 1.
1.3.4 Funkcja progowa
Funkcja
Å„Å‚
1, gdy liczba jedynek wśród x1, . . . , xn jest
òÅ‚
n
Tk (x1, . . . , xn) = równa lub większa od k,
ół
0, w przeciwnym wypadku,
1.3. Funkcje boolowskie 11
jest funkcją progową o n zmiennych z progiem k. Będziemy zakładać, że 1 d" k d" n.
n
Mówiąc inaczej wartość funkcji progowej Tk (x1, . . . , xn) osiąga wartość 1, jeżeli liczba
jedynek wśród (wartości) argumentów x1, ..., xn osiągnie lub przekroczy próg k.
Funkcji progowe dwóch zmiennych są proste.
2 2
T1 (x, y) = x + y, T2 (x, y) = x · y.
Proste też są funkcje progowe trzech zmiennych
3 3 3
T1 (x, y, z) = x + y + z, T2 (x, y, z) = xy + yz + xz, T3 (x, y, z) = x · y · z.
Przypuśćmy, że mamy już wyrażenia dla funkcji progowych n zmiennych. Za ich
pomocą możemy skonstruować wyrażenia dla funkcji progowych n + 1 zmiennych.
n+1
n+1
Tn+1 (x1, . . . , xn, xn+1) = xi,
i=1
n+1
n+1
T1 (x1, . . . , xn, xn+1) = xi.
i=1
Jeżeli 1 < k d" n, to:
n+1 n n
Tk (x1, . . . , xn, xn+1) = Tk (x1, . . . , xn) + Tk-1(x1, . . . , xn) · xn+1.
Ostatnia równość wyraża prosty fakt, że próg k jest osiągnięty wśród zmiennych x1, ...,
xn, xn+1, jeżeli jest osiągnięty wśród zmiennych x1, ..., xn lub jeżeli xn+1 = 1 i wśród
zmiennych x1, ..., xn jest co najmniej k - 1 jedynek.
1.3.5 Postacie normalne funkcji boolowskich
Nasuwa się pytanie, czy każdą funkcję n zmiennych można przedstawić za pomocą ko-
niunkcji, alternatywy i negacji. Odpowiedz
jest pozytywna. Najpierw przykład. Rozpa-
trzmy funkcjÄ™ boolowskÄ… trzech zmiennych:
x y z f(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
12 Rozdział 1. Funkcje boolowskie
Rozważmy wyrażenie:
xyz.
ŻŻ
Przyjmuje ono wartość 1 tylko dla jednego wektora (0, 0, 1), czyli dla podstawienia x =
0, y = 0, z = 1. Podobnie, wyrażenie xyz przyjmuje wartość 1 tylko dla wektora (0, 1, 1),
Å»
wyrażenie xyz  tylko dla (1, 0, 0), a wyrażenie xyz  tylko dla (1, 0, 1). Suma tych
ŻŻ Ż
wyrażeń:
xyz + xyz + xyz + xyz (1.1)
ŻŻ Ż ŻŻ Ż
przyjmuje wartość 1 tylko dla wektorów (0, 0, 1), (0, 1, 1),(1, 0, 0), (1, 0, 1), czyli jest
równoważna naszej funkcji f. Wyrażenie (1.1) jest w tak zwanej dysjunkcyjnej postaci
normalnej (DNF).
Funkcję f można też opisać w innej formie. Rozważmy wyrażenie:
x + y + z.
Przyjmuje ono wartość 0 tylko dla jednego wektora (0, 0, 0), czyli dla podstawienia x =
0, y = 0, z = 0. Podobnie, wyrażenie (x + y + z) przyjmuje wartość 0 tylko dla wektora
Å»
(0, 1, 0), wyrażenie (x + y + z)  tylko dla (1, 1, 0), a wyrażenie (x + y + z)  tylko
Å» Å» Å» Å» Å»
dla (1, 1, 1). Iloczyn tych wyrażeń:
(x + y + z)(x + y + z)(x + y + z)(x + y + z),
Å» Å» Å» Å» Å» Å»
przyjmuje wartość zero tylko dla wektorów (0, 0, 0), (0, 1, 0), (1, 1, 0), i (1, 1, 1), czy-
li jest równoważny funkcji f. Jest to tak zwana koniunkcyjna postać normalna (CNF)
funkcji f.
Metodę tę można uogólnić na funkcje n zmiennych. Wprowadzimy oznaczenie:
x1 = x x0 = x.
Å»
Dla dowolnego wektora a " {0, 1}n, niech a(i) oznacza i-tą współrzędną wektora a.
Rozważmy teraz wyrażenie:
ma(x) = xa(1) · xa(2) . . . xa(n).
1 2 n
Zauważmy, że ma(x) jest równe 1 tylko wtedy, gdy podstawimy xi = a(i), dla każdego
i, czyli dla x = a. Widać z tego, że:
f(x) = ma(x).
-1
a"f (1)
Jest to dysjunkcyjna postać normalna (DNF) funkcji f (sumowanie oznacza tutaj alterna-
tywę). Aby otrzymać postać koniukcyjną, zaczynamy od wyrażenia:
sa(x) = xŹa(1) + xŹa(2) + · · · + xŹa(n).
1 2 n
Zauważmy, że sa(x) jest równe 0 tylko wtedy, gdy podstawimy: xi = a(i), dla każdego
i, czyli dla x = a. Widać z tego, że:
f(x) = sa(x).
-1
a"f (0)
Jest to koniunkcyjna postać normalna (CNF) funkcji f.
1.4. Wielowartościowe funkcje boolowskie 13
1.4 Wielowartościowe funkcje boolowskie
Możemy też rozpatrywać wielowartościowe funkcje boolowskie, które ciągom bitów przy-
pisują ciągi bitów, czyli funkcje typu
f : Bn Bm.
Ciągowi argumentów x1, . . . , xn funkcja f przypisuje ciąg wartości
(f1(x1, . . . , xn), . . . , fm(x1, . . . , xn)),
gdzie f1,..., fm są jednowartościowymi funkcjami boolowskimi. Wielowartościowe funk-
cje boolowskie można traktować jak ciągi jednowartościowych funkcji. Przykładem wie-
lowartościowej funkcji boolowskiej jest funkcja sortująca
3 3 3
S(x, y, z) = (T1 (x, y, z), T2 (x, y, z), T3 (x, y, z)).
Wartości tej funkcji zestawione są w następującej tabeli:
x y z S(x, y, z)
0 0 0 000
0 0 1 100
0 1 0 100
0 1 1 110
1 0 0 100
1 0 1 110
1 1 0 110
1 1 1 111
Jak widać funkcja S sortuje ciąg wejściowy ustawiając go w porządku nierosnącym.
1.5 Sieci boolowskie
Najpierw przykład. Na rysunku 1.1 przedstawiono pewną sieć boolowską. Jest to graf
skierowany z sześcioma wierzchołkami (bramkami) i pięcioma krawędziami łączącymi
niektóre bramki. W tym i następnych przykładach przyjmujemy, że krawędzie są skiero-
wane od góry do dołu. Bramki mają etykiety. Jedna etykietowana jest stałą 1, dwie ety-
kietowane są zmiennymi x i y, a trzy etykietowane są operatorami logicznymi, '", (" i Ź.
Bramki oznaczone stałymi lub zmiennymi są bramkami wejściowymi i żadne krawędzie
nie prowadzą do nich. Bramka Ź ma jedną krawędz
wchodzÄ…cÄ…, a bramki (" i '" po dwie.
Bramka (" jest bramką wyjściową, bo nie wychodzi z niej żadna krawędz
. Z każdą bram-
ką w sieci możemy związać wyrażenie boolowskie. W przypadku bramki etykietowanej
stałą lub zmienną, tym wyrażeniem jest ta stała lub ta zmienna. Z bramką '" związane jest
wyrażenie x '" 1, z bramką Ź wyrażenie Źy, a z bramką (" wyrażenie (1 '" x) (" Źy.
Sieć oblicza funkcję boolowską. Najpierw podstawiamy wartości 0 lub 1 za zmienne
wejściowe, na przykład niech x = 0 i y = 1. W pierwszym kroku, obliczają swoje
14 Rozdział 1. Funkcje boolowskie
Rysunek 1.1: Przykład sieci boolowskiej
y
x
1
Ź
'"
("
wartości bramki z etykietami '" i Ź. Bramka '" daje wartość 0 '" 1 = 0, a bramka Ź
wartość Ź1 = 0. W drugim kroku swoją wartość oblicza bramka wyjściowa 0 (" 0 = 0 i
jest to wartość, którą zwraca cała sieć dla wejścia x = 0 oraz y = 1. Oczywiście funkcja
obliczana przez tą sieć jest opisana przez wyrażenie (1 '" x) (" Źy przypisane bramce
wyjściowej.
Ogólnie, sieć boolowska to acykliczny (bez cykli) graf skierowany, którego wierz-
chołki nazywamy bramkami. Każda bramka ma swoją etykietę, którą może być stała 1
lub 0, zmienna lub operator boolowski. W naszych rozważaniach ograniczymy się do
czterech operatorów: '", (", Ź i •", ale można rozważać sieci z innym zbiorem operato-
rów. Do bramek oznaczonych stałymi lub zmiennymi nie prowadzą żadne krawędzie, są
to bramki wejściowe. Bramki oznaczone przez Ź mają po jednej krawędzi wejściowej, a
bramki z pozostałymi operatorami mają po dwie krawędzie wchodzące. Wierzchołek, z
którego nie wychodzą żadne krawędzie, nazywamy wyjściowym. W sieci może być kilka
bramek wyjściowych.
Z każdą bramką u w sieci możemy związać wyrażenie boolowskie W (u). Robimy to
przez indukcję ze względu na strukturę sieci:
" Najpierw przypisujemy wyrażenia bramkom wejściowym. W tym wypadku wyra-
żeniem tym jest etykieta bramki u: stała lub zmienna.
" Jeżeli bramka u jest etykietowana negacją Ź i dochodzi do niej krawędz
od bramki
v oraz bramka v ma już przypisane wyrażenie W (v), to bramce u przypisujemy
wyrażenie W (u) = ŹW (v).
" Jeżeli etykietą bramki u jest operator dwuargumentowy op, to do u prowadzą kra-
wędzie od dwóch bramek, v i w. Jeżeli przypisano już wyrażenia W (v) i W (w)
bramkom v i w, to bramce u przypisujemy wyrażenie W (u) = W (v) op W (w).
Liczbę wszystkich bramek w sieci nazywamy kosztem sieci, a długość najdłuższej
ścieżki w sieci nazywamy głębokością sieci. Z każdą bramką wyjściową u, związana jest
funkcja opisana przez wyrażenia W (u) i możemy powiedzieć, że sieć oblicza wyrażenie
1.5. Sieci boolowskie 15
W (u). Z faktu, że każdą funkcję boolowską można przedstawić w postaci normalnej wy-
nika, że każdą funkcję boolowską można przedstawić za pomocą sieci. Jednak konstruk-
cja sieci dla funkcji boolowskiej f poprzez wyznaczanie postaci normalnej zazwyczaj
prowadzi do sieci o dużym koszcie (liczbie bramek).
1.5.1 Sieć dla alternatywy kilku zmiennych
Rysunek 1.2: Sieć boolowska obliczająca alternatywę ośmiu zmiennych
x1 x2 x3 x4 x5 x6 x7 x8
(" (" (" ("
(" ("
("
Na rysunku 1.2 przedstawiono sieć obliczającą alternatywę ośmiu zmiennych:
8
f(x1, . . . , x8) = xi = x1 + x2 + . . . + x8.
i=1
Głębokość tej sieci wynosi 3. Podobnie można skonstruować sieć liczącą alternatywę
n zmiennych, gdzie n jest jakąś potęgą dwójki. Głębokość takiej sieci wynosi log2 n.
Analogicznie możemy zbudować sieć dla koniunkcji lub operatora •".
1.5.2 Sumator
Zastanówmy się teraz, jak skonstruować sumator, czyli sieć, która będzie dodawać dwie
liczby n-bitowe:
x = (xn-1 . . . x1x0)2 oraz y = (yn-1 . . . y1y0)2,
i da w wyniku n + 1 bitów sumy:
s = x + y = (sn . . . s1s0)2.
16 Rozdział 1. Funkcje boolowskie
Rysunek 1.3: Sieć obliczająca HA (półsumator)
x0 y0
'" •"
c0 s0
Rysunek 1.4: Sieć obliczająca FA
xi yi ci-1
'" •"
(" '" •"
ci si
1.5. Sieci boolowskie 17
Na wejściu sumatora mamy n bitów pierwszej liczby, xn-1, ... , x0, oraz n bitów drugiej
liczby, yn-1, ... , y0, a na wyjściu n+1 bitów sumy arytmetycznej sn, ... ,s0. Nasz sumator
naśladuje szkolne dodawanie opisane w rozdziale o arytmetyce. Najpierw dodaje bity x0 i
y0 i oblicza ostatni bit sumy s0 oraz przeniesienie c0, które ma być dodane do następnego
bitu. Potem dla kolejnych pozycji i od 1 do n - 1 dodaje bity xi, yi oraz przeniesienie
ci-1 z poprzedniej pozycji i oblicza i-ty bit sumy si oraz przeniesienie ci do następnej
pozycji. Na rysunku 1.3 przedstawiono sieć HA (ang. half adder  półsumator), która ma
na wejÅ›ciu dwa bity, x0 i y0, a na wyjÅ›ciu  bit sumy s0 = x0 •" y0 oraz bit przeniesienia
c0 = x0'"y0. Na rysunku 1.4 przedstawiono sieć FA (ang. full adder), która ma na wejściu
trzy bity, xi, yi oraz ci-1, a na wyjÅ›ciu bit sumy si = xi •"yi •"ci-1 oraz bit przeniesienia
ci = xi '" yi (" (xi •" yi) '" ci-1.
Rysunek 1.5: Schemat sumatora
y3 x3 y2 x2 y1 x1 y0 x0
HA
c0
FA
c1
FA
c2
c3 FA
s4 s3 s2 s1 s0
Na rysunku 1.5 przedstawiono schemat konstrukcji sumatora dla n = 4. Podobnie
można skonstruować sumator dla dowolnego n. Taki sumator będzie zawierał 5n - 3
bramek i miał głębokość 2n - 1.
18 Rozdział 1. Funkcje boolowskie
1.6 Operacje boolowskie na wektorach
Operacje boolowskie można wykonywać także na ciągach bitów określonej długości, czy-
li na elementach zbioru
Bn = {0, 1}n.
Dla dwóch ciągów:
x = (x1, x2, . . . , xn) oraz y = (y1, y2, . . . , yn),
operacje koniunkcji, alternatywy, xor i negacji wykonywane są po współrzędnych:
x · y = (x1 · y1, x2 · y2, . . . , xn · yn),
x + y = (x1 + y1, x2 + y2, . . . , xn + yn),
x •" y = (x1 •" y1, x2 •" y2, . . . , xn •" yn),
Źx = (Źx1, Źx2, . . . , Źxn).
Możemy też obliczać bardziej złożone wyrażenia na ciągach bitów. Na przykład
0 · x + y · z = (0 · x1 + y1 · z1, . . . , 0 · xn + yn · zn),
gdzie z jest wektorem z = (z1, . . . , zn). Niezbyt formalnie można powiedzieć, że war-
tość wyrażenia 0 · x + y · z jest obliczane równolegle i niezależnie na każdej współ-
rzędnej. Podobnie dla dowolnego wyrażenia W (x1, x2, . . . , xk) zmienne x1, x2,...,xk
mogą być traktowane jak ciągi zmiennych x1 = (x1, . . . , xn), x2 = (x1, . . . , xn),...,
1 1 2 2
xk = (x1, . . . , xn). Mamy wtedy
k k
W (x1, x2, . . . , xk) = (W (x1, x1 . . . , x1), W (x2, x2 . . . , x2), . . . , W (xn, xn . . . , xn)).
1 2 k 1 2 k 1 2 k
Jeżeli wektor zerowy (0, 0, . . . , 0) oznaczymy przez 0, a wektor złożony z samych jedy-
nek (1, 1, . . . , 1)  przez 1, to zachodzą wszystkie tożsamości z lemat.ow 1.1 oraz 1.2.
1.6.1 Reprezentacja zbioru
Ciągi bitów z Bn = {0, 1}n mogą służyć do reprezentacji podzbiorów zbioru
{1, 2, . . . , n}.
Ciąg x " {0, 1}n należy traktować jako funkcję charakterystyczną pewnego podzbioru.
Wtedy operacje boolowskie na ciÄ…gach odpowiadajÄ… operacjom na zbiorach. Alternatywa
odpowiada sumie zbiorów, koniunkcja części wspólnej, a negacja uzupełnieniu zbioru.
Operacja xor odpowiada różnicy symetrycznej.
Podobnie dla dowolnego wyrażenia W (x1, . . . , xk) za zmienne x1,...,xk możemy
podstawiać podzbiory A1,...,Ak otrzymując podzbiór W (A1, . . . , Ak) lub ciągi reprezen-
tujÄ…ce funkcje charakterystyczne tych zbiorów Ç1,...,Çk otrzymujÄ…c ciÄ…g W (Ç1, . . . , Çk),
który jest funkcją charakterystyczną zbioru W (A1, . . . , Ak).
1.6. Operacje boolowskie na wektorach 19
PrzykÅ‚ad 1.6 Niech X = {1, 2, 3, 4, 5} oraz niech W (x, y, z) = x · 1 + y · (Źz). Jeżeli
za zmienne podstawimy podzbiory x = {3, 5}, y = {1, 2, 4, 5} oraz z = {2, 3, 5}. to
wartość wyrażenia będzie zbiorem W (x, y, z) = {1, 3, 4, 5}.
Jeżeli za zmienne podstawimy funkcje charakterystyczne tych samych podzbiorów
x = (0, 0, 1, 0, 1), y = (1, 1, 0, 1, 1) oraz z = (0, 1, 1, 0, 1), to wartość wyrażenia
będzie ciągiem W (x, y, z) = (1, 0, 1, 1, 1), który jest funkcją charakterystyczną zbioru
{1, 3, 4, 5}.
Przykład 1.7 W grupie 8 studentów są uprawiający koszykówkę, siatkówkę lub pływanie.
Niech ciÄ…g K = (1100 1010) reprezentuje koszykarzy, ciÄ…g S = (1010 0011) siatkarzy,
a ciąg P = (1010 0011) pływaków. Wtedy ciąg
" K · S · P = (1000 0010) reprezentuje studentów, którzy uprawiajÄ… wszystkie trzy
sporty,
" Ź(K + S + P ) = (0001 0100) studentów, którzy nie uprawiają żadnego sportu,
" K · (ŹS) · (ŹP ) = (0100 1000) studentów, którzy uprawiajÄ… tylko koszykówkÄ™,
" K · S + S · P + K · P = (1010 0011) studentów, którzy uprawiajÄ… co najmniej
dwie dyscypliny sportu.
3
Przypominamy, że wyrażenie K · S + S · P + K · P opisuje funkcjÄ™ progowÄ… T2 .
1.6.2 Operacje na wektorach w języku Pascal
W języku Pascal operacje boolowskie: and, or, xor, neg, można stosować do
liczb typu integer lub innych typów całkowitych (byte, shortint, word lub longint). Liczba
traktowana jest wtedy jako ciąg bitów jej przedstawienia binarnego. Na przykład:
13 and 6=4
ponieważ 13 jest reprezentowane przez:
(0000000000001101),
6 przez:
(0000000000000110)
oraz:
(0000 0000 0000 1101)and(0000 0000 0000 0110) =(0000 0000 0000 0100),
a ten ostatni ciÄ…g reprezentuje 4 w typie integer. Podobnie zachodzi:
13 or 6=15; 13 xor 6=11; not 0=-1.
1.6.3 Operacje na wektorach w języku C
W języku C operacje boolowskie na liczbach typów całkowitych wyglądają następująco
" x|y jest alternatywÄ…,
20 Rozdział 1. Funkcje boolowskie
" x&y jest koniunkcjÄ…,
" xĆy jest ksorem,
" Üx jest negacjÄ….
W języku C można zażądać, aby liczba była wydrukowana w systemie ósemkowym lub
szesnastkowym.
1.6.4 Flagi
Przypuśćmy, że pewien program sprawdza kilka, powiedzmy trzy, warunki i chcemy ze-
brać informacje, które z tych warunków są spełnione. Można to zrobić za pomocą operacji
boolowskich na liczbach całkowitych. W tym celu deklarujemy zmiennąxtypu całkowi-
tego a następnie
" x:=0;
" Sprawdzamy pierwszy warunek i jeżeli jest spełniony, to za pomocą podstawienia
x:=x or 1 zmieniamy ostatni bit x.
" Sprawdzamy drugi warunek i jeżeli jest spełniony, to za pomocą podstawienia
x:=x or 2 zmieniamy drugi od końca bit x.
" Sprawdzamy trzeci warunek i jeżeli jest spełniony, to za pomocą podstawienia
x:=x or 4 zmieniamy pierwszy bit x.
Po tych operacjach zmienna x reprezentuje zbiór spełnionych warunów. Jeżeli x=0 to
żaden warunek nie jest spełniony. Jeżeli x=7 to wszystkie są spełnione. Jeżeli x and
2=2, to spełniony jest drugi warunek.
1.6.5 Reprezentacja ustawienia bierek w grze w szachy
W programach grających w szachy ustawienie bierek (figur i pionków) często jest prze-
chowywane w postacie tak zwanych map bitów, czyli ciągów 64-bitowych. Taka mapa
reprezentuje zbiór pozycji na szachownicy. Rozważmy, na przykład, problem, jak stwier-
dzić, czy biały skoczek może w jednym ruchu zaatakować jednocześnie czarnego króla i
hetmana. Dla każdej z 64 pozycji na szachownicyvprzechowujemy w tablicyRSk[v],
gdzie w jednym ruchu może skoczyć skoczek, który stoi na pozycjiv. NiechCKoznacza
pozycję czarnego króla,CH- czarnego hetmana, aBS1iBS2pozycje białych skoczków.
Teraz mapa
RSk[CK] and RSk[CH]
reprezentuje zbiór pozycji, z których skoczek może szachować jednocześnie króla i het-
mana. Jeżeli mapaBBreprezentuje pozycje białych bierek, to
RSk[CK] and RSk[CH] and (not BB)
reprezentuje, które z tych pozycji nie są zajęte przez białe bierki. Aby stwierdzić, czy
białe mogą w jednym ruchu skoczka zaatakować króla i hetmana należy sprawdzić, czy
zbiór
1.6. Operacje boolowskie na wektorach 21
RSk[CK] and RSk[CH] and (not BB) and (RSk[BS1] or RSk[BS2])
jest niepusty. Taka reprezentacja ma dwie zalety. Zajmuje mało pamięci i wykorzystuje
bardzo szybkie operacje niskiego poziomu.
1.6.6 Szyfrowanie w systemie one-pad
Operacje boolowskie na wektorach można wykorzystać do szyfrowania. W systemie szy-
frowania  one-pad wiadomość x i klucz k są ciągami bitów x, k " {0, 1}n (Jeżeli wia-
domość jest ciągiem znaków, to kodujemy każdy znak jako 8 bitów i cały ciąg może być
traktowany jako ciąg bitów). Zaszyfrowana wiadomość ma postać:
y = C(k, x) = x •" k.
Zauważmy, że deszyfrować można według tego samego wzoru:
D(k, y) = y •" k,
ponieważ
y •" k = (x •" k) •" k = x •" (k •" k) = x •" 0 = x,
System one-pad można stosować w następujący sposób: Najpierw przesyła się bez-
pieczną pocztą (na przykład kurierską) zapasy kluczy, na przykład notesy z kartkami,
gdzie każda strona zawiera jeden klucz. Następnie szyfrowane depesze mogą być prze-
syłane mniej bezpiecznymi kanałami. Trzeba tylko przestrzegać zasady, że jedna kartka
może być użyta tylko raz (stąd angielska nazwa systemu). Same klucze powinny być lo-
sowane, aby przeciwnik nie mógł ich odgadnąć.
Zaletą tego systemu jest to, że jest on absolutnie bezpieczny. Zróbmy następujący
eksperyment. Przypuśćmy, że ktoś ma zaszyfrowaną wiadomość y i chce ją odszyfrować
przez odgadnięcie samej wiadomości x. Zastanówmy się, dla jakich ciągów x istnieje
klucz k, taki że x •" k = y, czyli inaczej, jakie wiadomoÅ›ci mogÄ… być zaszyfrowane w
y. Okazuje siÄ™, że dla każdego ciÄ…gu x " {0, 1}n istnieje klucz k, taki że x •" k = y.
Wystarczy wziąć k = x •" y. Mamy wtedy:
C(k, x) = x •" k = x •" (x •" y) = (x •" x) •" y = 0 •" y = y.
Wadą tego systemu jest to, że klucze muszą być tej samej długości co sama wiadomość i
muszą być trzymane w sekrecie. Powoduje to kłopoty z przesyłaniem i przechowywaniem
kluczy.
A
amiąc szyfry często korzysta się z faktu, że wiadomości, lub ich fragmenty, wystę-
pują z różną częstością (prawdopodobieństwem). Przypuśćmy dla prostoty, że szyfrujemy
pojedyncze znaki i niech {0, 1}8 będzie zbiorem wiadomości (kody ASCII). Dla normal-
nych tekstów (listów) rozkład częstości poszczególnych znaków jest bardzo niejednostaj-
ny. Kody jednych liter występują dużo cześciej, niż innych, a pewne znaki nie występu-
ją wcale. Gdybyśmy teraz zastosowali jakiś prymitywny sposób kodowania bez klucza,
gdzie każdy znak x zawsze jest szyfrowany za pomocą D(x), to w zaszyfrowanej wia-
domości rozkład częstości będzie podobny. Najczęściej występujący znak w wiadomości
22 Rozdział 1. Funkcje boolowskie
zaszyfrowanej odpowiada najczęściej występującemu znakowi w tekście, itd. Można to
wykorzystać przy łamaniu szyfrów.
Jak zaraz zobaczymy w przypadku szyfrów one-pad tak nie jest. Znaki w zaszyfrowa-
nej wiadomości posiadają rozkład
jednostajny, tak jakbyśmy losowali kolejne znaki i dlatego analiza statystyczna jest
tutaj bezużyteczna.
Niech X = {0, 1}n będzie zbiorem wiadomości z dowolnym rozkładem prawdopo-
dobieństwa, a K = {0, 1}n zbiorem kluczy z jednostajnym rozkładem prawdopodobień-
stwa. Losujemy wiadomość x " X i klucz k " K i obliczamy wiadomość y = x " k "
{0, 1}n. Niech Ax oznacza zdarzenie, że wylosowano wiadomość x, Kk, że wylosowano
klucz k, a Cy zdarzenie, że otrzymano zaszyfrowaną wiadomość y. Zgodnie ze wzorem
na prawdopodobieństwo całkowite mamy
P (Cy) = P (Cy|Ax) · P (Ax),
x"{0,1}n
P (Cy|Ax) jest prawdopodobieństwem warunkowym, że zaszyfrowaną wiadomością bę-
dzie y pod warunkiem, że zaszyfrowano wiadomość x. Jak pokazaliśmy wyżej tylko dla
1
jednego klucza k = x " y, y = x " k. Dlatego P (Cy|Ax) = oraz
2n
1 1
P (Cy) = P (Ax) = .
2n 2n
x"{0,1}n
1.7 Funkcja parzystości (parity)
Zdefiniujmy funkcję boolowską parzystości (parity):
P ar : {0, 1}n {0, 1},
n
P ar(x) = xi = x1 •" x2 •" . . . •" xn.
i=1
Funkcja P ar jest addytywna, to znaczy:
P ar(x •" y) = P ar(x) •" P ar(y),
co wynika z faktu, że operacja •" jest Å‚Ä…czna i przemienna.
P ar(x) jest równa 1, jeżeli liczba jedynek w ciągu x jest nieparzysta, oraz jest równa
0, jeżeli w ciągu x liczba jedynek jest parzysta. Jeżeli będziemy utożsamiać wektor x ze
zbiorem, to P ar(x) jest równe parzystości mocy zbioru x.
Twierdzenie 1.8 P ar(x) = 1 dla dokładnie połowy wejść. To znaczy:
|{x " {0, 1}n : P ar(x) = 1}| = 2n-1.
1.8. Odciski, zabezpieczanie danych 23
Pierwszy dowód. Twierdzenie wynika z faktu, że dokładnie połowa podzbiorów zbioru
{1, 2, . . . , n} jest nieparzystej mocy.
Drugi dowód. Wez
my wektor:
s = (1, 0, . . . , 0),
który ma jedynkę tylko na pierwszej współrzędnej. Zdefiniujemy teraz funkcję h:
h(x) = x •" s.
Funkcja h łączy elementy zbioru {0, 1}n w pary, ponieważ jeżeli h(x) = y, to h(y) = x.
Rzeczywiście:
h(y) = y •" s = (x •" s) •" s = x •" (s •" s) = x •" 0 = x.
Ponadto:
P ar(x) •" P ar(y) = P ar(x •" y) = P ar(x •" x •" s) = P ar(s) = 1,
a stąd wynika, że dla każdej pary x, y = h(x) dokładnie jedna z dwóch liczb P ar(x),
P ar(y) jest jedynką, czyli dla dokładnie połowy x " {0, 1}n, P ar(x) = 0.
1.8 Odciski, zabezpieczanie danych
Funkcja P ar jest wykorzystywana do kontroli, czy dane nie zostały przekłamane pod-
czas przesyłania lub przechowywania. Przypuśćmy, że Małgosia chce przesłać Jasiowi
wiadomość x " {0, 1}n i chce choć trochę zabezpieczyć x przed przekłamaniem. Wtedy
Małgosia wysyła x razem z bitem P ar(x)  jego odciskiem. Odcisk wiadomości ma
pełnić podobną rolę co odcisk palca u człowieka, ma pomóc w identykikacji. Przypuść-
my teraz, że Jaś dostał wiadomość y z odciskiem P ar(x). Dla prostoty zakładamy, że
odcisk P ar(x) nie został przekłamany, na przykład Małgosia i Jaś mogą się umówić, że
przesyłają sobie tylko takie wiadomości x, dla których P ar(x) = 0. Aby sprawdzić, czy
wiadomość nie została przekłamana, Jaś oblicza P ar(y) i porównuje go z P ar(x). Jeżeli
P ar(x) = P ar(y), to Jaś ma pewność, że x = y. Jeżeli P ar(x) = P ar(y), to Jaś przyj-

muje, że x = y, choć w tym przypadku nie może mieć pewności. Zauważmy, że jeżeli x
i y różniÄ… siÄ™ tylko na jednym bicie, to x •" y ma tylko jednÄ… jedynkÄ™, wiÄ™c:
P ar(x •" y) = 1.
Z drugiej strony:
P ar(x •" y) = P ar(x) •" P ar(y),
z czego wynika:
P ar(x) = P ar(y).

Tak więc jeżeli w przesyłanych danych zostanie zmieniony (przekłamany) jeden bit, bę-
dzie można to wykryć porównując P ar(x) z P ar(y).
24 Rozdział 1. Funkcje boolowskie
Jest to bardzo stary system kontroli danych. Działa on dobrze, jeżeli przekłamania są
przypadkowe i prawdopodobieństwo przekłamania dwóch bitów jest dużo mniejsze niż
prawdopodobieństwo przekłamania jednego bitu. Funkcja P ar jest jednak zbyt prosta,
aby zabezpieczyć dane przed złośliwym przekłamywaniem. Wystarczy bowiem zawsze
przekłamywać parzystą liczbę bitów, aby rzecz się nie wykryła.
Pokażemy teraz bardziej złożony sposób zabezpieczania danych przed przekłama-
niem. Dla dowolnego wektora r " {0, 1}n zdefiniujmy funkcję parzystości z parame-
trem:
P arr : {0, 1}n {0, 1},
n
P arr(x) = P ar(x · r) = xiri.
i=1
Funkcja P arr oblicza parzystość liczby bitów wektora x, ale liczone są tylko bity na po-
zycjach wyznaczonych przez jedynki wektora r, inaczej  P arr(x) to parzystość prze-
kroju x i r.
Funkcja P arr jest addytywna:
P arr(x •" y) = P ar((x •" y) · r) = P ar(x · r •" y · r)
= P ar(x · r) •" P ar(y · r) = P arr(x) •" P arr(y).
Twierdzenie 1.9 Jeżeli x = 0, to dla dokładnie połowy r " {0, 1}n zachodzi P arr(x) =

0.
Dowód. Ponieważ x = 0, więc istnieje wektor s z jedną jedynką, taki że:

x · s = s.
Wektor s powinien mieć jedynkę na pozycji, na której x też ma jedynkę. Podobnie jak w
dowodzie twierdzenia 1.8, możemy teraz określić funkcję:
h(r) = r •" s,
która  zlepia wektory z {0, 1}n w pary. Ponadto mamy:
h(r) · x = (r •" s) · x = r · x •" s · x = r · x •" s.
Z tego wynika, że:
P arh(r)(x) = P ar(h(r) · x) = P ar(r · x •" s)
= P ar(r · x) •" P ar(s) = P arr(x) •" 1,
a stąd  że dla każdej pary, r, h(r), dokładnie jedna z dwóch liczb P arr(x), P arh(r)(x)
jest jedynkÄ….
1.9. Zadania 25
Wykorzystując funkcje P arr, można zbudować lepszy system zabezpieczania da-
nych. Na początku Małgosia i Jaś zaopatrują się w ciąg wylosowanych kluczy:
r1, r2, . . . , rs " {0, 1}n.
Klucze te powinny być trzymane w sekrecie. Jeżeli teraz Małgosia chce przesłać Jasio-
wi wiadomość x, to bierze kolejny klucz r z ciągu r1, r2, . . . , rs i wysyła x razem z
odciskiem P arr(x). Jaś po odebraniu wiadomości y razem z odciskiem P arr(x) (tak
jak poprzednio zakładamy, że P arr(x) nie jest przekłamywane) porównuje P arr(x) i
P arr(y).
Jeżeli x = y, to dla każdego r:
P arr(x) = P arr(y).
Jeżeli zaÅ› x = y, to x •" y = 0 i dla poÅ‚owy wektorów r mamy:

P arr(x) •" P arr(y) = P arr(x •" y) = 1,
a więc dla połowy wektorów r mamy:
P arr(x) = P arr(y).

1
Tak więc z prawdopodobieństwem Jaś wykryje, że x = y.

2
Aby zwiększyć to prawdopodobieństwo można brać kilka kolejnych kluczy r1, . . . , rk.
Wtedy w przypadku, gdy x = y, prawdopodobieństwo, że dla każdego i = 0, . . . , k, bę-

dzie P arr (x) = P arr (y), jest równe 2-k.
i i
1.9 Zadania
1. Które z poniższych równości są tożsamościami w algebrze B = {0, 1}:
a) p + qr = q + pr; b) (p + q)r = p + qr; c) (r •" q)r = r •" qr;
d) (p + q)r = pr(q + r) + qr; e) (p •" q) •" p = p •" q?
Które z tych równości są tożsamościami w algebrze 2X?
2. Udowodnij lematy 1.1 i 1.2.
3. Przedstaw za pomocÄ… tabeli funkcje: a) g(p, q, r) = (p •" q)r; b) h(x, y, z) =
(x + Źy) · (y + Źz); c) f(u, v, w, x) = uv + wx.
4. Napisz wyrażenia dla wszystkich funkcji progowych czterech zmiennych.
5. Jaki zbiór przedstawia wyrażenie W (x, y, z) = xy + xz + yz, jeżeli podstawimy
x = {1, 2, 5}, y = {1, 3, 4}, z = {2, 3, 5}?
6. Niech X będzie zbiorem studentów, K podzbiorem studentów grających w koszy-
kówkę, S studentów grających w siatkówkę, P uprawiających pływanie. Przedstaw
wyrażenie boolowskie opisujęce następuące podzbiory:
26 Rozdział 1. Funkcje boolowskie
" studentów uprawiających tylko jedną dyscyplinę sportu,
" studentów uprawiających dokładnie dwie dyscypliny sportu,
" koszykarzy, którzy nie pływają.
7. Udowodnij, że wszystkie funkcje boolowskie dwóch zmiennych można przedsta-
wić za pomocą: a) dwóch operatorów, koniunkcji i negacji (lub alternatywy i ne-
gacji); b) jednego operatora nand (lub nor).
8. Ile jest funkcji boolowskich typu f : Bn B?
9. Które funkcje f : B2 B spełniają równanie xf(x, y) = yf(x, y)?
Wskazówka. Rozważ wyrażenie xf(x, y) •" yf(x, y).
10. Funkcja f : B3 B przyjmuje wartość 1 tylko dla wektorów (1, 0, 0), (0, 1, 0)
oraz (0, 0, 1). Przedstaw funkcjÄ™ f w postaciach normalnych (dysjunkcyjnej i ko-
niunkcyjnej).
11. Narysuj sieć boolowską dla funkcji z poprzedniego zadania.
12. Zaprojektuj sieć, która:
" odejmuje od siebie dwie liczby w postaci dwójkowej.
" mnoży dwie liczby dwubitowe.
" dla wejścia x1, x2, x3 zlicza liczbę jedynek i przedstawią ją w postaci dwój-
kowej.
" traktuje wejście x1, x0 jako liczbę w postaci dwójkowej i daje na wyjściu
y1, y2, y3 tyle jedynek ile wynosi liczba (x1x0)2.
13. Jaki ciąg przedstawia wyrażenie W (x, y, z) = xy + xz + yz, jeżeli podstawimy
x = (0, 1, 0, 1, 1, 0, 0), y = (1, 1, 1, 1, 0, 0, 0), z = (0, 1, 1, 1, 0, 1, 0)?
14. Oblicz wartość wyrażeń x or y, x and y, not x, x xor y:
a) jeżeli zmiennexiysą typu shortint i przyjmują wartości: x=6, y=-3,
b) jeżeli zmiennexiysą typu byte i przyjmują wartości: x=6, y=3.
15. Dany jest wektor x = (0, 1, 1). Dla jakich wektorów r " B3, P arr(x) = 1?
16. Dane są dwa wektory: x = (0, 1, 0) oraz y = (0, 0, 1). Dla jakich wektorów r "
B3, P arr(x) = P arr(y)?

1.10. Problemy 27
1.10 Problemy
1.10.1 Gra w kamienie
Rozważmy następującą grę. Mamy trzy kupki kamyków. Gracze po kolei zabierają ka-
mienie z kupek, przy czym wolno brać kamienie tylko z jednej kupki i oczywiście jakieś
kamienie trzeba zabrać. Wygrywa gracz, który zabiera ostatnie kamienie.
Gra ta posiada prostÄ… strategiÄ™ wygrywajÄ…cÄ…. Niech x, y i z oznaczajÄ… liczby kamieni
w poszczególnych kupkach. Wtedy układ kamieni x, y, z jest:
" wygrywajÄ…cy, jeżeli x •" y •" z = 0

" przegrywajÄ…cy, jeżeli x •" y •" z = 0.
Jeżeli początkowy układ jest wygrywający, to gracz zaczynający grę wygra, jeżeli zawsze
przekaże przeciwnikowi układ przegrywający.
Udowodnij, że
" W żadnym układzie przegrywającym nie można wygrać w jednym ruchu.
" Każdy układ przegrywający po wykonaniu dowolnego ruchu staje się wygrywający.
" Każdy układ wygrywający można doprowadzić za pomocą jednego ruchu do ukła-
du przegrywajÄ…cego.
Wskazówka. Wez
my wygrywajÄ…cy ukÅ‚ad x, y, z. Niech r = x •" y •" z = 0 i niech i bÄ™dzie

najwyższym bitem, na którym r ma jedykę. Wtedy jedna z liczb, powiedzmy x, też ma
jedynkÄ™ na pozycji i i zachodzi x •" r < x, oraz (x •" r) •" y •" z = 0.
Czy podobną stategię można stosować, jeżeli jest więcej kupek kamieni?
1.10.2 Tożsamości w algebrze podzbiorów
Udowodnij
Twierdzenie 1.10 Równość pomiędzy dwoma wyrażeniami
U(x1, . . . , xk) = V (x1, . . . , xk)
jest tożsamością w algebrze podzbiorów 2X wtedy i tylko wtedy, gdy jest tożsamością w
algebrze {0, 1}.
Z tego wynika, że aby sprawdzić tożsamość, wystarczy sprawdzić, czy zachodzi ona
dla podstawień zbioru pustego " lub całego zbioru X za zmienne.
Wskazówki: Po pierwsze, zauważmy, że równość U(x1, . . . , xk) = V (x1, . . . , xk) jest
równoważna równoÅ›ci U(x1, . . . , xk) •" V (x1, . . . , xk) = 0. Możemy, wiÄ™c ograniczyć
rozważania do równości
W (x1, . . . , xk) = 0 (1.2)
28 Rozdział 1. Funkcje boolowskie
Jeżeli podstawimy za zmienne ciągi x1 = (x1, . . . , xn), ... , xk = (x1, . . . , xn), to otrzy-
1 1 k k
mamy
W (x1, . . . , xk) = (W (x1, . . . , x1), ... , W (xn, . . . , xn)).
1 k 1 k
ale dla każdej współrzędnej i, zachodzi
W (xi , . . . , xi ) = 0,
1 k
ponieważ równość (1.2) jest tożsamością w algebrze {0, 1}, a zmienne xi , . . . , xi "
1 k
{0, 1}.
1.10.3 Postać normalna
Udowodnij, że dla każdej funkcji funkcji f : Bn B istnieje dokładnie jeden wektor:
a = (aA)A‚"{1,...,n},
taki że:
f(x) = aA · xi.
A‚"{1,...,n} i"A
1.10.4 Sieci funkcji progowych i sortujÄ…cych
Zaprojektuj funkcje progowe czterech zmiennych
Rysunek 1.6: Schemat sieci sortujÄ…cej
x1 x2 x3 x4
4 4 4 4
T1 T2 T3 T4
y1 y2 y3 y4
4 4 4 4
Rysunek 1.6 pokazuje jak z sieci funkcji progowych T1 , T2 , T3 , T4 skonstruować
sieć sortującą. Przeanalizuj zachowanie tej sieci.