Md5

Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Rozdział 1
Funkcje boolowskie
1.1 Algebra Boole a
Przykł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, � a
oznaczana przez:
�

lub
i określona przez tabele:
� �
p q p+q
0 0 0
0 1 1
1 0 1
1 1 1
Koniunkcja (lub iloczyn) jest druga operacja dwuargumentow�, oznaczana przez:
� � a �

lub
i określona przez tabele:
� �

p q
0 0 0
0 1 0
1 0 0
1 1 1
3
4 Rozdział 1. Funkcje boolowskie
Podobnie 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 �

lub
i określona przez tabele:
� �

p
0 1
1 0

Algebre 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 5

p q
0 0 0
0 1 0
1 0 1
1 1 1

Ponieważ 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ś zbioru

z operacjami określonymi w nastepujacy sposób:
� �

jest sum� mnogościow�
a a

jest iloczynem

jest 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 do

zbioru , to należy także do sumy . Jeżeli zaś nie należy do , to nie należy

takż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 q
0 0 0
0 1 1
1 0 1
1 1 0

Operacja ta jest nazywana alternatyw� wykluczajaca, ponieważ w logice zdaniowej
a � �

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 boolowskie
Podobnie 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 za
pomoca 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ówne
< mniejsze
> wieksze
�
<> różne
<= mniejsze lub równe
>= wieksze lub równe
�
1.3. Funkcje boolowskie 7
Wyraż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<=x) and (x<=10),

(010).
gdziebjest zmienna typu boolean, ax zmienna liczbow�
� � a.
Wyrażenia boolowskie wystepuja w jezyku Pascal w instrukcjach warunkowych lub
� � �
w petlach while i repeat.
�
1.3 Funkcje boolowskie
Funkcje boolowskie zmiennych to funkcje:

gdzie . Mamy cztery funkcje boolowskie jednej zmiennej:

funkcje stała równa 0,
� � �

identyczność ,

negacje ,
�

funkcje stała równa 1.
� � �
Wartości tych funkcji zestawiono w tabeli:

x
0 0 0 1 1
1 0 1 0 1
8 Rozdział 1. Funkcje boolowskie

Sa to wszystkie funkcje boolowskie jednej zmiennej, ponieważ sa to funkcje ze zbioru
� �

w zbiór , a takich funkcji jest:

Funkcji boolowskich dwóch zmiennych jest:

Ich wartości zestawiono w tabeli:

x y
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 ciag wartości każdej z tych funkcji czytany od góry do dołu stanowi zapis
�
binarny jej numeru. Przyjrzyjmy sie bliżej tym funkcjom:
�

jest funkcja stała równa 0,
� � �

jest funkcja stała równa 1,
� � �

jest koniunkcja,
�

jest alternatyw�
a,

jest xorem,

jest implikacja z do ,
�

jest implikacja z do ,
�

jest równoważnościa,
�

jest rzutem na pierwsza współrzedna,
� � �

� � �
jest rzutem na druga współrzedna,

� �
jest negacja drugiej współrzednej,

jest negacja pierwszej współrzednej,
� �

jest zaprzeczeniem koniunkcji, tak zwany nand,

jest zaprzeczeniem alternatywy, tak zwany nor,

jest zaprzeczeniem implikacji z do ,

jest zaprzeczeniem implikacji z do .

1.3. Funkcje boolowskie 9
Jak widać, każda z tych funkcji można przedstawić za pomoca koniunkcji, alternatywy i
� �
negacji.
Funkcji boolowskich trzech zmiennych jest:

nie bedziemy ich wszystkich wypisywać.
�
Nasuwa sie pytanie, czy każda funkcje zmiennych można przedstawić za pomoca
� � � �
koniunkcji, alternatywy i negacji. Odpowiedz jest pozytywna. Najpierw przykład. Roz-
patrzmy funkcje boolowska 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
Rozważmy wyrażenie:

Przyjmuje ono wartość 1 tylko dla jednego wektora , czyli dla podstawienia

, , . Podobnie, wyrażenie przyjmuje wartość 1 tylko dla wektora ,

wyrażenie tylko dla , a wyrażenie tylko dla . Suma tych

wyrażeń:

(1.1)

przyjmuje wartość 1 tylko dla wektorów , , , , czyli jest

równoważna naszej funkcji . Wyrażenie (1.1) jest w tak zwanej dysjunkcyjnej postaci
normalnej (DNF).

Funkcje można też opisać w innej formie. Rozważmy wyrażenie:
�

Przyjmuje ono wartość 0 tylko dla jednego wektora , czyli dla podstawienia

, , . Podobnie, wyrażenie przyjmuje wartość 0 tylko dla wektora

, wyrażenie tylko dla , a wyrażenie tylko

dla . Iloczyn tych wyrażeń:

przyjmuje wartość zero tylko dla wektorów , , , i , czy-

li jest równoważny funkcji . Jest to tak zwana koniunkcyjna postać normalna (CNF)

funkcji .
10 Rozdział 1. Funkcje boolowskie
Metode te można uogólnić na funkcje zmiennych. Wprowadzimy oznaczenie:
� �

Dla dowolnego wektora , niech oznacza -ta współrzedna wektora .
� � �
Rozważmy teraz wyrażenie:

Zauważmy, że jest równe 1 tylko wtedy, gdy podstawimy , dla każdego

, czyli dla . Widać z tego, że:

Jest to dysjunkcyjna postać normalna (DNF) funkcji (sumowanie oznacza tutaj alternatyw�
e).
Aby otrzymać postać koniukcyjna, zaczynamy od wyrażenia:
�

Zauważmy, że jest równe 0 tylko wtedy, gdy podstawimy: , dla każdego

, czyli dla . Widać z tego, że:

Jest to koniunkcyjna postać normalna (CNF) funkcji .
1.4 Sieci boolowskie
Najpierw przykład. Na rysunku 1.1 przedstawiono pewna sieć boolowska. Jest to graf
� �
skierowany z sześcioma wierzchołkami (bramkami) i piecioma kraw� łaczacymi
� edziami � �
niektóre bramki. W tym i nastepnych przykładach przyjmujemy, że kraw� sa skiero-
� edzie �

wane od góry do dołu. Bramki maja etykiety. Jedna etykietowana jest stała , dwie ety-
� �

kietowane sa zmiennymi i , a trzy etykietowane sa operatorami logicznymi, , i .
� �

Bramki oznaczone stałymi lub zmiennymi sa bramkami wejściowymi i żadne kraw�
� edzie

nie prowadza do nich. Bramka ma jedna kraw� wchodzaca, a bramki i po dwie.
� � edz � �
Bramka jest bramka wyjściow� bo nie wychodzi z niej żadna kraw� Z każda bramka
� a, edz. � �

w sieci możemy zwiazać wyrażenie boolowskie. W przypadku bramki etykietowanej stała
� �

lub zmienna, tym wyrażeniem jest ta stała lub ta zmienna. Z bramka zwiazane jest wy-
� � �

rażenie , z bramka wyrażenie , a z bramka wyrażenie .
� �
Ogólnie, sieć boolowska to graf składajacy sie z wierzchołków, nazywanych bramka-
� �
mi, i skierowanych kraw� łaczacych niektóre bramki. Każda bramka ma swoja etykiete,
edzi � � � �

która może być stała 1 lub 0, zmienna lub operator boolowski. W naszych rozważaniach
�

ograniczymy sie do czterech operatorów: , , i , ale można rozważać sieci z innym
�
zbiorem operatorów. Do bramek oznaczonych stałymi lub zmiennymi nie prowadza żadne
�
1.4. Sieci boolowskie 11
Rysunek 1.1: Przykład sieci boolowskiej

kraw� sa to bramki wejściowe. Bramki oznaczone przez maja po jednej kraw�
edzie, � � edzi
wejściowej, a bramki z pozostałymi operatorami maja po dwie kraw� wchodzace. W
� edzie �
sieci boolowskiej nie może być cyklu, czyli ciagu kraw�
� edzi

takiego że , i dla każdego spełniajacego warunek w sieci istnieje
�

kraw� od wierzchołka do wierzchołka . Wierzchołek, z którego nie wychodza
edz �
żadne kraw� nazywamy wyjściowym. W sieci może być kilka bramek wyjściowych.
edzie,
Z każda bramka w sieci możemy zwiazać wyrażenie boolowskie . Robimy to
� � �
przez indukcje ze wzgledu na strukture sieci:
� � �

Najpierw przypisujemy wyrażenia bramkom wejściowym. W tym wypadku wyra-
żeniem tym jest etykieta bramki : stała lub zmienna.

Jeżeli bramka jest etykietowana negacja i dochodzi do niej kraw� od bramki
� edz

oraz bramka ma już przypisane wyrażenie , to bramce przypisujemy

wyrażenie .

Jeżeli etykieta bramki jest operator dwuargumentowy , to do prowadza kraw�
� � edzie

od dwóch bramek, i . Jeżeli przypisano już wyrażenia i bramkom

i , to bramce przypisujemy wyrażenie .
Liczbe wszystkich bramek w sieci nazywamy kosztem sieci, a długość najdłuższej ścieżki
�

w sieci nazywamy głebokościa sieci. Jeżeli w sieci istnieje bramka wyjściowa , to mo-
� �
żemy powiedzieć, że sieć oblicza wyrażenie . Z faktu, że każda funkcje boolowska
� � �
można przedstawić w postaci normalnej, wynika, że każda funkcje boolowska można
� � �

przedstawić za pomoca sieci. Jednak konstrukcja sieci dla funkcji boolowskiej poprzez
�
wyznaczanie postaci normalnej zazwyczaj prowadzi do sieci o dużym koszcie (liczbie
bramek). Poniżej omówiono przykłady sieci o stosunkowo małym koszcie.
12 Rozdział 1. Funkcje boolowskie
1.4.1 Suma (alternatywa) kilku zmiennych
Rysunek 1.2: Sieć boolowska obliczajaca alternatyw� ośmiu zmiennych
� e

Na rysunku 1.2 przedstawiono sieć obliczajaca alternatyw� ośmiu zmiennych:
� � e

Głebokość tej sieci wynosi 3.
�
Podobnie można skonstruować sieć liczaca alternatyw� zmiennych, gdzie jest
� � e

jakaś potega dwójki. Głebokość takiej sieci wynosi . Oczywiście tak samo możemy
� � � �
zbudować sieć dla uogólnionej koniunkcji lub operatora .
1.4.2 Funkcje progowe
Funkcja

gdy liczba jedynek wśród jest

równa lub wieksza od
�

w przeciwnym wypadku,

jest funkcja progow� o zmiennych z progiem . B� zakładać, że .
� a edziemy
Sieci funkcji progowych dwóch zmiennych sa proste, ponieważ:
�

Przedstawiono je na rysunku 1.3.
1.4. Sieci boolowskie 13
Rysunek 1.3: Sieci funkcji progowych dwóch zmiennych

Przypuśćmy, że mamy już sieci funkcji progowych zmiennych. Za ich pomoca
�

możemy skonstruować funkcje progowe zmiennych (rysunek 1.4). Zrobimy to
posługujac sie nastepujacymi zależnościami:
� � � �

Jeżeli , to:

Jeżeli zestawimy równolegle sieci funkcji progowych, tak jak zrobiono to na rysun-
ku 1.5, to otrzymamy sieć sortujaca. Sieć ta bierze na wejściu ciag czterech bitów:
� � �

i zwraca na wyjściu te same bity w porzadku nierosnacym:
� �

Na przykład gdy na wejściu bedzie ciag , wówczas na wyjściu pojawi sie ciag
� � � �

.
1.4.3 Sumator
Zastanówmy sie teraz, jak skonstruować sumator, czyli sieć, która bedzie dodawać dwie
� �
liczby -bitowe:

oraz

i da w wyniku bitów sumy:

14 Rozdział 1. Funkcje boolowskie

Rysunek 1.4: Sieć funkcji progowej

Na wejściu sumatora mamy bitów pierwszej liczby, , ... , , oraz bitów drugiej

liczby, , ... , , a na wyjściu bitów sumy arytmetycznej , ... , . Nasz sumator

naśladuje szkolne dodawanie opisane w rozdziale o arytmetyce. Najpierw dodaje bity i

i oblicza ostatni bit sumy oraz przeniesienie , które ma być dodane do nastepnego
�

bitu. Potem dla kolejnych pozycji od do dodaje bity , oraz przeniesienie

z poprzedniej pozycji i oblicza -ty bit sumy oraz przeniesienie do nastepnej
�
pozycji.

Na rysunku 1.6 przedstawiono sieć HA (ang. half adder półsumator), która ma na

wejściu dwa bity, i , a na wyjściu bit sumy oraz bit przeniesienia

.

Na rysunku 1.7 przedstawiono sieć FA (ang. full adder), która ma na wejściu trzy

bity, , oraz , a na wyj ściu bit sumy oraz bit przeniesienia

.

Na rysunku 1.8 przedstawiono schemat konstrukcji sumatora dla . Podobnie

można skonstruować sumator dla dowolnego . Taki sumator bedzie zawierał
�
1.5. Operacje boolowskie na wektorach 15
Rysunek 1.5: Schemat sieci sortujacej
�

bramek i miał głebokość .
�
1.5 Operacje boolowskie na wektorach
Operacje boolowskie można wykonywać także na ciagach bitów określonej długości, czy-
�
li na elementach zbioru

Dla dwóch ciagów:
�

oraz
operacje koniunkcji, alternatywy, xor i negacji wykonywane sa po współrzednych:
� �

Jeżeli wektor oznaczymy przez 0, a wektor złożony z samych jedy-
zerowy

nek przez 1, to zachodza wszystkie tożsamości lematu1.1 oraz tożsamo-
�
ści (a) (e) z lematu 1.2. Nie jest natomiast na ogół spełniona własność (e) lematu 1.2,
16 Rozdział 1. Funkcje boolowskie
Rysunek 1.6: Sieć obliczajaca HA (półsumator)
�

ponieważ jeżeli , to z działaniami i nie jest ciałem (nie ma elementu prze-

ciwnego do ). Zbiór jest przestrzenia liniow� nad ciałem , z jako
� a
dodawaniem oraz mnożeniem przez skalar zdefiniowanym przez:

(tutaj zero po lewej stronie jest zerem z ciała, a zero po prawej stronie jest
wektorem zerowym),

.
1.5.1 Operacje na wektorach w jezyku Pascal
�
W jezyku Pascal (i w wielu innych językach) operacje boolowskie:and, or, xor,
�
neg, można stosować do liczb typu integer lub innych typów całkowitych (byte, shor-
tint, word lub longint). Liczba traktowana jest wtedy jako ciag bitów jej przedstawienia
�
binarnego. Na przykład:
13 and 6=4
ponieważ 13 jest reprezentowane przez:

6 przez:

oraz:
(0000 0000 0000 1101)and(0000 0000 0000 0110) =(0000 0000 0000 0100),
a ten ostatni ciag reprezentuje 4 w typie integer. Podobnie zachodzi:
�
13 or 6=15; 13 xor 6=11; not 0=-1.
1.5. Operacje boolowskie na wektorach 17
Rysunek 1.7: Sieć obliczajaca FA
�

1.5.2 Reprezentacja zbioru

Ciagi bitów z moga służyć do reprezentacji podzbiorów zbioru
� �

Ciag należy traktować jako funkcje charakterystyczna pewnego podzbioru.
� � �
Wtedy operacje boolowskie na ciagach odpowiadaja operacjom na zbiorach. Alternaty-
� �
wa odpowiada sumie zbiorów, koniunkcja cześci wspólnej, a negacja uzupełnieniu zbio-
�
ru. Operacja xor odpowiada różnicy symetrycznej. Taka reprezentacja ma dwie zalety.
Zajmuje mało pamieci i operacje na zbiorach sa wykonywane bardzo szybko, ponieważ
� �
operacje boolowskie sa operacjami niskiego poziomu.
�
Na przykład jeżeli chcemy reprezentować w pamieci komputera ułożenie kamieni w
�
grze w warcaby na 64-polowej szachownicy, to wystarcza dwie liczby typu longint (po 32
�
bity). W jednej liczbie reprezentujemy położenie czarnych, a w drugiej położenie białych
kamieni (w grze w warcaby kamienie moga leżeć tylko na 32 czarnych polach).
�
1.5.3 Szyfrowanie w systemie one-pad
Operacje boolowskie na wektorach można wykorzystać do szyfrowania. W systemie szy-

frowania one-pad wiadomość i klucz sa ciagami bitów (Jeżeli wia-
� �
domość jest ciagiem znaków, to kodujemy każdy znak jako 8 bitów i cały ciag może być
� �
traktowany jako ciąg bitów). Zaszyfrowana wiadomość ma postać:

18 Rozdział 1. Funkcje boolowskie
Rysunek 1.8: Schemat sumatora

HA

FA

FA

FA

Zauważmy, że deszyfrować można według tego samego wzoru:

ponieważ

gdzie 0 reprezentuje wektor zerowy. Zaleta tego systemu jest to, że jest on absolutnie bez-
�
pieczny. Zróbmy nastepujacy eksperyment. Przypuśćmy, że ktoś ma zaszyfrowana wia-
� � �

domość i chce ja odszyfrować przez odgadniecie samej wiadomości . Zastanówmy sie,
� � �

dla jakich ciagów istnieje klucz , taki że , czyli inaczej, jakie wiadomości
�

moga być zaszyfrowane w . Okazuje sie, dla każdego ciagu istnieje klucz
� � że �

, taki że . Wystarczy wziać . Mamy wtedy:
�

1.6. Funkcja parzystości (parity) 19
Wada tego systemu jest to, że klucze musza być tej samej długości co sama wiadomość i
� �
musza być trzymane w sekrecie. Powoduje to kłopoty z przesyłaniem i przechowywaniem
�
kluczy.
System one-pad można stosować w nastepujacy sposób: Najpierw przesyła sie bezpieczna
� � � �
poczta (na przykład kurierska) zapasy kluczy, na przykład notesy z kartkami, gdzie każda
� �
strona zawiera jeden klucz. Nastepnie szyfrowane depesze moga być przesyłane mniej
� �
bezpiecznymi kanałami. Trzeba tylko przestrzegać zasady, że jedna kartka może być uży-
ta tylko raz (stad angielska nazwa systemu). Same klucze powinny być losowane, aby
�
przeciwnik nie mógł ich odgadnać.
�
Aamiac szyfry czesto korzysta sie z faktu, że wiadomości, lub ich fragmenty, wystepuja
� � � � �
z różna czestościa (prawdopodobieństwem). Przypuśćmy dla prostoty, że szyfrujemy po-
� � �

jedyncze znaki i niech bedzie zbiorem wiadomości (kody ASCII). Dla normal-
�
nych tekstów (listów) rozkład czestości poszczególnych znaków jest bardzo niejednostaj-
�
ny. Kody jednych liter wystepuja dużo cześciej, niż innych, a pewne znaki nie wystepuja
� � � �

wcale. Gdybyśmy teraz zastosowali jakiś prymitywny sposób kodowania bez klucza,

gdzie każdy znak zawsze jest szyfrowany za pomoca , to w zaszyfrowanej wia-
�
domości rozkład czestości bedzie podobny (przepermutowany). Najcześciej wystepujacy
� � � � �
znak w wiadomości zaszyfrowanej odpowiada najcześciej wystepujacemu 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 zaszyfro-
wanej wiadomości posiadaja rozkład jednostajny, tak jakbyśmy losowali kolejne znaki i
�
dlatego analiza statystyczna jest tutaj bezużyteczna.

Niech bedzie zbiorem wiadomości z dowolnym rozkładem prawdopo-
�

dobieństwa, a zbiorem kluczy z jednostajnym rozkładem prawdopodobień-

stwa. Losujemy wiadomość i klucz i obliczamy wiadomość

. Niech oznacza zdarzenie, że wylosowano wiadomość , , że wylosowano

klucz , a zdarzenie, że otrzymano zaszyfrowana wiadomość . Zgodnie ze wzorem
�
na prawdopodobieństwo całkowite mamy

ale bo tylko dla jednego klucza , . Dlatego

1.6 Funkcja parzystości (parity)
Zdefiniujmy funkcje boolowska parzystości (parity):
� �

20 Rozdział 1. Funkcje boolowskie

Funkcja jest addytywna, to znaczy:

�
co wynika z faktu, że operacja jest łaczna i przemienna.

jest równa 1, jeżeli liczba jedynek w ciagu jest nieparzysta, oraz jest równa
�

0, jeżeli w ciagu liczba jedynek jest parzysta. Jeżeli bedziemy utożsamiać wektor ze
� �

zbiorem, to jest równe parzystości mocy zbioru .

Twierdzenie 1.3 dla dokładnie połowy wejść. To znaczy:

Pierwszy dowód. Twierdzenie wynika z faktu, że dokładnie połowa podzbiorów zbioru

jest nieparzystej mocy.
Drugi dowód. Wezmy wektor:

który ma jedynke tylko na pierwszej współrzednej. Zdefiniujemy teraz funkcje :
� � �

Funkcja łaczy elementy ze zbioru w pary, ponieważ jeżeli , to
�
. Rzeczywiście:

Ponadto:

a stad wynika, że dla każdej pary , dokładnie jedna z dwóch liczb ,
�

jest jedynka, czyli dla dokładnie połowy ,
�
1.7 Zabezpieczanie danych

Funkcja jest wykorzystywana do kontroli, czy dane nie zostały przekłamane podczas
przesyłania lub przechowywania. Przypuśćmy, że Małgosia chce przesłać Jasiowi wiado-

mość i chce choć � zabezpieczyć przed przekłamaniem. Wtedy Mał-
troche

gosia wysyła razem z bitem jego podpisem. Przypuśćmy teraz, że Jaś dostał

wiadomość z podpisem . Dla prostoty zakładamy, że podpis nie został

przekłamany, na przykład Małgosia i Jaś moga sie umówić, że przesyłaja sobie tylko ta-
� � �

kie wiadomości , dla których . Aby sprawdzić, czy wiadomo została
ść nie

przekłamana, Jaś oblicza i z . Jeżeli , to
porównuje go

Jaś ma pewność, że . Jeżeli , to Jaś przyjmuje, że , choć
1.7. Zabezpieczanie danych 21

w tym przypadku nie może mieć pewności. Zauważmy, że jeżeli i różnia sie tylko na
� �

jednym bicie, to ma tylko jedna jedynke, wiec:
� � �

Z drugiej strony:

z czego wynika:

Tak wiec jeżeli w przesyłanych zostanie zmieniony (przekłamany) jeden bit, bedzie
� danych �

można to wykryć porównujac z .
�
Jest to bardzo stary system kontroli danych. Działa on dobrze, jeżeli przekłamania sa
�

przypadkowe i prawdopodobieństwo przekłamania dwóch bitów jest dużo mniejsze niż

prawdopodobieństwo przekłamania jednego bitu. Funkcja jest jednak zbyt prosta,
aby zabezpieczyć dane przed złośliwym przekłamywaniem. Wystarczy bowiem zawsze
przekłamywać parzysta liczbe bitów, aby rzecz sie nie wykryła.
� � �

Pokażemy teraz bardziej złożony zabezpieczania danych przed przekłama-
sposób

niem. Dla dowolnego wektora zdefiniujmy funkcje:
�

Funkcja oblicza parzystość liczby bitów wektora , ale liczone sa tylko bity na
�

pozycjach wyznaczonych przez wektor , inaczej to parzystość przekroju i

.

Funkcja jest addytywna:

Twierdzenie 1.4 Jeżeli oraz , to dla dokładnie połowy

zachodzi .

Dowód. Jeżeli , to istnieje wektor z jedna jedynka, taki że:
� �

Wektor powinien mieć jedynke na pozycji, na której też ma jedynke. Podobnie jak w
� �
dowodzie twierdzenia 1.3, możemy teraz określić funkcje:
�

która zlepia wektory z w pary. Ponadto mamy:

22 Rozdział 1. Funkcje boolowskie
Z tego wynika, że:

a stad że dla każdej pary, , , dokładnie jedna z dwóch liczb ,
�

jest jedynka.
�

Wykorzystujac funkcje , można zbudować lepszy system zabezpieczania da-
�
nych. Na poczatku Małgosia i Jaś zaopatruja sie w ciag wylosowanych kluczy:
� � � �

Klucze te powinny być trzymane w sekrecie. Jeżeli teraz Małgosia chce przesłać Jasio-

wi wiadomość , to bierze kolejny klucz z ciagu i wysyła razem z
�

podpisem . Jaś po odebraniu wiadomości razem z podpisem (tak

jak poprzednio zakładamy, że nie jest przekłamywane) porównuje i

.

Jeżeli , to dla każdego :

Jeżeli zaś , to i dla połowy wektorów mamy:

a wiec dla połowy wektorów mamy:
�

Tak wiec z prawdopodobieństwem jedna druga Jaś wykryje, że .
�

Aby zwiekszyć to prawdopodobieństwo można bra kilka kolejnych kluczy .
� ć

Wtedy prawdopodobie ństwo, że w przypadku, gdy , mamy ,

dla każdego , jest równe .
1.8 Zadania
1. Udowodnij lematy 1.1 i 1.2.
2. Udowodnij, że tożsamości lematu 1.1 sa tożsamościami w algebrze podzbiorów
�

zbioru .

3. Które z poniższych równości sa tożsamościami w algebrze :
�
a) p+qr=q+pr, b) (p+q)r=p+qr, c) (r+q)r=r+qr, d) (p+q)r=p(q+r)+qr.
4. Udowodnij, że wszystkie funkcje boolowskie dwóch zmiennych można przedsta-
wić za pomoca dwóch operatorów, koniunkcji i negacji (lub alternatywy i negacji).
�
1.9. Problemy 23
5. Udowodnij, że wszystkie funkcje boolowskie dwóch zmiennych można przedsta-
wić za pomoca jednego operatora nand (lub nor).
�

6. Ile funkcji spełnia równanie

7. Funkcja przyjmuje wartość 1 tylko dla wektorów ,

oraz . Przedstaw funkcje w postaciach normalnych (dysjunkcyjnej i ko-
�
niunkcyjnej).
8. Narysuj sieć boolowska dla funkcji z poprzedniego zadania.
�
9. Zaprojektuj sieć odejmujaca od siebie dwie liczby w postaci dwójkowej.
� �
10. Zaprojektuj sieć, która mnoży dwie liczby dwubitowe.
11. Opisz schemat sumatora dla liczb -bitowych, którego głebokość jest proporcjo-
�

nalna do .
12. Oblicz wartość wyrażeń x or y, x and y, not x, x xor y:
a) jeżeli zmiennexiysa typu shortint i przyjmuja wartości: x=6, y=-3,
� �
b) jeżeli zmiennexiysa typu byte i przyjmuja wartości: x=6, y=3.
� �

13. Dany jest wektor . Dla jakich wektorów , ?

�
14. Dane sa dwa wektory: oraz . Dla jakich wektorów

, .
1.9 Problemy
1.9.1 System one-pad

System one-pad może być stosowany do ciagów liter alfabetu łacińskiego. Wtedy utoż-
�
samiamy litery z liczbami od 0 do 25 i zamiast operacji stosujemy:

czyli reszte z dzielenia przez 26. Jak wyglada wtedy operacja deszyfrowania?
� �
Pokaż, że system one-pad z literami jest równie bezpieczny jak system z dwoma cyframi
0 i 1.
1.9.2 Zabezpieczanie
Zaproponuj zmiany w systemie podpisów opisanym pod koniec rozdziału, tak aby praw-
dopodobieństwo wykrycia błedu zwiekszyć do 0.75.
� �
24 Rozdział 1. Funkcje boolowskie
1.9.3 Postać normalna

Udowodnij, że dla każdej funkcji funkcji istnieje dokładnie jeden wektor:

taki że:

Wyszukiwarka

Podobne podstrony:
102537 MD5
MD5 license
function md5
WindowZ v2 Lite 10 Dokładny opis md5
[full]md5 pl
module md5
function md5 file
function md5 file
MD5 FLAC WAV

więcej podobnych podstron