[ Pobierz całość w formacie PDF ]

� ć
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: [ Pobierz całość w formacie PDF ]