Rozdział Elementy teorii algebr Boole’a



Pobieranie 270.33 Kb.
Strona2/2
Data29.10.2017
Rozmiar270.33 Kb.
1   2
§5. Zastosowania

Skupimy uwagę wyłącznie na niektórych zastosowaniach teorii algebr Boole’a w informatyce (szerokie zastosowania w logice, również w logice pierwszego rzędu, np. w dowodzie tzw. twierdzenia o pełności metodą algebraiczną Rasiowej-Sikorskiego, wykraczają poza ramy tego kursu). Mamy na myśli tzw. układy cyfrowe zwane czasem układami logicznymi, wykonujące operacje na tzw. słowach dwójkowych, czyli n-wyrazowych ciągach zer i jedynek. Zero 0 i jedynka 1 - jedyne dwie cyfry dwójkowego zapisu liczb, zwane bitami, reprezentują tu stany wejściowe i wyjściowe układu cyfrowego: 0 - brak sygnału, 1 - istnienie sygnału. Układ cyfrowy można w ogólności scharakteryzować przy pomocy schematu, w którym stany wejściowe określone są n-wyrazowym ciągiem zer i jedynek (x1,x2,...,xn), zaś jedyny stan wyjściowy - to zero bądź jedynka, oznaczone tu jako f(x1,x2,...,xn):





Wyjściowy stan układu jest wartością funkcji f, przekształcającej zbiór wszystkich n-wyrazowych ciągów elementów zbioru {0,1} w zbiór {0,1}, na argumencie (x1,x2,...,xn), będącym ciągiem n stanów wejściowych. Jest jasne, iż układ cyfrowy reprezentowany jest formalnie w postaci funkcji f. Zatem wiedza na temat takich funkcji może być zastosowana dla układów cyfrowych.


Rozważmy 2-elementową algebrę Boole’a: ({0,1},,,,0,1). Przypominamy określenie jej operacji:
0  0 = 0  1 = 1  0 = 0, 1  1 = 1,

0  0 = 0, 0  1 = 1  0 = 1  1 = 1,

1 = 0, 0 = 1.
Traktujemy tę algebrę jako możliwą interpretację dla języka pierwszego rzędu wyznaczonego przez stałe nazwowe: 0,1 oraz symbole funkcyjne: , , . Jak widać, wizualnie nie odróżniamy tu obiektów od ich nazw (tzn. stanów od stałych nazwowych oraz operacji od symboli funkcyjnych). W ten sposób dowolny term domknięty t tego języka, wizualnie może nie być odróżniany od obiektu |t| nazywanego tym termem - obiektu ze zbioru {0,1}, który jest wartością waluacji | | dla tej interpretacji, jaką jest 2-elementowa algebra Boole’a (por. §3, rozdział 1). Na przykład napis: (0  1)  (1  0), można by postrzegać jako term domknięty, bądź jako wartość waluacji na tym termie, tzn. jako obiekt 0. W dalszym ciągu tam tylko, gdzie niezbędna jest precyzja, będziemy odróżniać term domknięty od wartości waluacji na nim.

Dla zupełnie dowolnego termu t, (tzn. niekoniecznie domkniętego), którego wszystkie zmienne nazwowe należą do zbioru {x1,x2,...,xn} oraz dowolnych a1,a2,...,an  {0,1}, oznaczmy symbolem t[x1/a1, x2/a2, ..., xn/an] term domknięty powstały z t przez zastąpienie zmiennej x1 (jeżeli występuje w t) stałą a1, zmiennej x2 (jeżeli występuje w t) stałą a2 itd.



Definicja. Powiemy, że funkcja f : {0,1}{1,2,...,n} → {0,1} (dla ustalonego dowolnego n = 1,2, ...), tzn. funkcja f przekształcająca zbiór wszystkich n-wyrazowych ciągów elementów ze zbioru {0,1} w zbiór {0,1}, jest definiowalna w 2-elementowej algebrze Boole’a, gdy istnieje taki term t, że dla dowolnych a1, a2, ..., an  {0,1}: f(|a1|,|a2|,...,|an|) = |t[x1/a1, x2/a2, ..., xn/an]| (tutaj obiekty a1, a2, ..., an traktowane są jednoznacznie jako stałe nazwowe; naturalnie jeśli nie obawiamy się konfuzji, czy wieloznaczności, ostatnią równość możemy zapisać w postaci: f(a1,a2,...,an) = t[x1/a1, x2/a2, ..., xn/an], gdzie po lewej stronie równości, a1,a2,...,an są elementami 2-elementowej algebry Boole’a, zaś po prawej stronie, a1,a2,...,an są stałymi nazwowymi, przy czym nie odróżniamy wtedy termu od wartości waluacji na tym termie).

Okazuje się, że prawdziwe jest następujące



Twierdzenie (o definiowalności). Dla dowolnego n = 1,2,... każda funkcja f : {0,1}{1,2,...,n} → {0,1} jest definiowalna w 2-elementowej algebrze Boole’a.

Dowód: Ustalmy dowolne naturalne n  1 oraz rozważmy dowolną funkcję f : {0,1}{1,2,...,n} → {0,1}. Dziedzina funkcji f jest oczywiście zbiorem 2n-elementowym. Niech wśród 2n ciągów należących do dziedziny, ciągi: (b11,b21,...,bn1), (b12,b22,...,bn2), ..., (b1i,b2i,...,bni), dla pewnego 1  i  2n, będą wszystkimi elementami dziedziny, na których funkcja f przyjmuje wartość 1. Następnie, dla dowolnej zmiennej nazwowej x, wprowadźmy oznaczenie: 0x = x, oraz 1x = x. Analogicznie, oznaczmy dla stałej nazwowej a  {0,1} w miejsce zmiennej x: 0a = a, 1a = a. Niech x1, x2,..., xn będą różnymi zmiennymi nazwowymi. Wykazujemy, że poszukiwany term t ma następującą postać:
(b11x1b21x2  ....  bn1xn)  (b12x1b22x2  ....  bn2xn)  ...  (b1ix1b2ix2  ....  bnixn),
tzn. że dla dowolnych a1, a2, ..., an  {0,1}, f(a1,a2,...,an) =

(b11a1b21a2  ....  bn1an)  (b12a1b22a2  ....  bn2an)  ...  (b1ia1 b2ia2  ....  bnian).


Rzeczywiście, zauważmy najpierw, że dla każdego j = 1,2,...,i zachodzi:
(*) b1ja1 b2ja2  ....  bnjan = 1 wtw b1j = a1 oraz b2j = a2 oraz ... oraz bnj = an wtw (b1j,b2j,...,bnj) = (a1,a2,...,an).
Wówczas, gdy ciąg (a1,a2,...,an) jest taki, że f(a1,a2,...,an) = 0, to ciąg ten jest różny od każdego z ciągów, na których funkcja f przyjmuje wartość 1, zatem różny od każdego z ciągów (b1j,b2j,...,bnj), j = 1,2,...,i, czyli według (*), dla każdego j = 1,2,...,i zachodzi: b1ja1 b2ja2  ....  bnjan = 0. To oznacza, iż (b11a1b21a2  ....  bn1an)  (b12a1b22a2  ....  bn2an)  ...  (b1ia1 b2ia2  ....  bnian) = 0. Rozważmy drugi możliwy przypadek, gdy ciąg (a1,a2,...,an) jest taki, że f(a1,a2,...,an) = 1. Wtedy dla pewnego j = 1,2,...,i: (a1,a2,...,an) = (b1j,b2j,...,bnj). Zatem zgodnie z (*), otrzymujemy: b1ja1 b2ja2  ....  bnjan = 1 i w konsekwencji: (b11a1b21a2  ....  bn1an)  (b12a1b22a2  ....  bn2an)  ...  (b1ia1 b2ia2  ....  bnian) = 1, co prawie kończy dowód. Pozostaje bowiem jeszcze do rozważenia przypadek stałej funkcji f, która na żadnym n-wyrazowym ciągu nie przyjmuje wartości 1, tzn. dla dowolnych a1, a2, ..., an  {0,1), f(a1,a2,...,an) = 0. Naturalnie, taka funkcja jest również definiowalna w 2-elementowej algebrze Boole’a, mianowicie poszukiwanym termem t jest teraz stała nazwowa: 0 lub, jak kto woli, np. term postaci: x1  x1. 

Przykład. Rozważmy n = 3 i funkcję f : {0,1}{1,2,3} → {0,1} określoną następująco: f(0,0,1) = f(0,1,0) = f(1,0,0) = f(1,1,1) = 1, na pozostałych czterech 3-wyrazowych ciągach funkcja f przyjmuje wartość 0. Wówczas term konstruowany w dowodzie twierdzenia o definiowalności, ma dla funkcji f postać: (x1  x2 x3)  (x1 x2 x3)  (x1  x2 x3)  (x1 x2 x3).

Jak wynika z dowodu twierdzenia o definiowalności, każdą funkcję f : {0,1}{1,2,...,n} → {0,1} można wyrazić przy użyciu operacji , , . Naturalnie same te operacje są również tego typu funkcjami:  oraz  są dwiema z szesnastu różnych funkcji przekształcających zbiór ciągów {0,1}{1,2} w zbiór {0,1}, zaś operacja: , jest jedną z czterech różnych funkcji przekształcających zbiór {0,1} (ciągów 1-wyrazowych) w zbiór {0,1}. Ponieważ dzięki prawom De Morgana i Tw.5 funkcję  można wyrazić przez operacje ,: x1x2 = (x1  x2), jak również funkcję  można wyrazić przez operacje: ,: x1x2 = (x1  x2), więc w rezultacie każda funkcję f : {0,1}{1,2,...,n} → {0,1} można wyrazić jedynie przy użyciu zestawu operacji: ,, bądź ,. Co więcej, jak wynika to z Tw.10(1),(2),(3), każdą z operacji ,, można wyrazić przy użyciu jednej tylko operacji: Sheffera /, bądź binegacji \. Oznacza to, iż każdą funkcję f : {0,1}{1,2,...,n} → {0,1} można wyrazić jedynie przy użyciu operacji Sheffera, bądź jedynie przy użyciu operacji binegacji.


Operacje podstawowe, a więc te z funkcji f : {0,1}{1,2,...,n} → {0,1}, przy użyciu których definiuje się inne funkcje, reprezentują układy cyfrowe zwane bramkami. Schematy bramek reprezentowanych przez funkcje , , , /, \,  są odpowiednio postaci:







Rysując odpowiednie kombinacje tych schematów otrzymuje się schemat układu reprezentowanego przez daną funkcję f : {0,1}{1,2,...,n} → {0,1}. Na przykład schemat układu reprezentowanego przez funkcję f z przykładu powyżej, zapisany przy użyciu schematów dla bramek reprezentowanych przez operacje ,, jest dość skomplikowany:




Jednakże schemat układu reprezentowanego przez tę funkcję narysowany przy użyciu schematu bramki reprezentowanej przez operację różnicy symetrycznej  jest znacznie

prostszy:


Naturalnie, wcześniej należy wykazać, że dla dowolnych a1, a2, a3  {0,1), f(a1,a2,a3) = a3 (a1a2), tzn. że (a1  a2 a3)  (a1 a2 a3)  (a1  a2 a3)  (a1 a2 a3) = a3 (a1a2), co pozostawiamy Czytelnikowi.


Funkcja f z naszego przykładu związana jest z regułą „piśmiennego” dodawania liczb w systemie dwójkowym. Zanim ów związek przedstawimy, dodajmy na przykład do siebie liczby 7 i 5 zapisane w systemie dwójkowym, a więc 111 + 101:
111

+101

1100
Dodając dwie jedynki oznaczające jedności w obu liczbach otrzymujemy liczbę jedności: 0 oraz liczbę dwójek: 1, tzn. cyfra 1 jest cyfrą przeniesienia. Dodajemy ją do jedynki oznaczającej liczbę dwójek w liczbie 111 oraz do 0 oznaczającego liczbę dwójek w liczbie 101, otrzymując 0 jako liczbę dwójek i 1 jako liczbę czwórek, tzn. 1 jest teraz cyfrą przeniesienia. Dodajemy ją z kolei do jedynki oznaczającej liczbę czwórek w liczbie 111 oraz do jedynki oznaczającej liczbę czwórek w liczbie 101, otrzymując jedną czwórkę i jedną ósemkę. Zauważmy, że przy każdym prócz pierwszego, dodawaniu dwóch cyfr oznaczających liczby jedności, bądź dwójek, bądź czwórek w liczbach 111, 101 dodawaliśmy do nich cyfrę przeniesienia była ona bowiem jedynką. Gdyby była zerem, też byśmy ja dodali, naturalnie bez zmiany wyniku. Możemy uznać, ze również w pierwszym dodawaniu cyfr (oznaczających liczby jedności w liczbach 111, 101) dodawaliśmy również cyfrę przeniesienia, tyle że równą 0.


Na podstawie tego przykładu znaleźliśmy wszystkie osiem możliwości dodawania do siebie dwóch cyfr dwójkowych oraz dwójkowej cyfry przeniesienia. Przedstawiamy je poniżej, dwie pierwsze cyfry, patrząc od lewej do prawej, to cyfry „piśmiennie” dodawane do siebie, trzecia cyfra – to cyfra przeniesienia, wynik tego dodawania to cyfra, którą zapisuje się pod kreską dodawania „piśmiennego”:
0 + 0 + 0 = 0 = f(0,0,0),

0 + 0 + 1 = 1 = f(0,0,1),

0 + 1 + 0 = 1 = f(0,1,0),

1 + 0 + 0 = 1 = f(1,0,0),

1 + 1 + 0 = 0 = f(1,1,0),

1 + 0 + 1 = 0 = f(1,0,1),

0 + 1 + 1 = 0 = f(0,1,1),

1 + 1 + 1 = 1 = f(1,1,1).


Widać, że dla dowolnych a1, a2, a3  {0,1), f(a1,a2,a3) jest cyfrą zapisywaną pod kreską dodawania, o ile a1, a2 są cyframi dodawanymi do siebie (występującymi w liczbach w systemie dwójkowym) oraz a3 jest cyfrą przeniesienia.


Ćwiczenia



  1. Dowieść, że aksjomaty absorpcji (Ax4): x  (x y) = x, x  (x y) = x, oraz aksjomaty (Ax6) x  1 = x, x  0 = x, implikują aksjomaty idempotencji (Ax1): x x = x, x x = x.




  1. Udowodnić prawo De Morgana: (x y) = x  y, korzystając z Tw.4: xy (x y = 0 oraz x y = 1)  y = x, oraz odpowiednich aksjomatów teorii algebr Boole’a.




  1. Dowieść twierdzenia teorii algebr Boole’a: xy (x y  y  x), gdzie  jest relacją porządku boolowskiego.




  1. Dowieść następujących twierdzeń teorii algebr Boole’a:

  1. x  (y z) = (x y)  z,

  2. x  (y z) = (x y)  (x z).




  1. Wykazać, że w dowolnej kracie z elementem najmniejszym: 0 oraz największym: 1, uzupełnieniem elementu 1 jest 0 oraz uzupełnieniem elementu 0 jest 1.




  1. Wykazać, że w dowolnej kracie <A, > z elementem najmniejszym: 0 oraz największym: 1, dla dowolnych a,b A, jeżeli b jest uzupełnieniem elementu a oraz istnieje uzupełnienie elementu b, to jest nim element a.




  1. Dowieść, że w dowolnej kracie <A, >, jeżeli dla pewnego a A istnieje relatywne pseudo-uzupełnienie elementu a względem a, to jest ono elementem największym w <A, >.




  1. Wykazać, że dla dowolnych elementów a,b algebry Boole’a (D,,,,0,1) element a b jest relatywnym pseudo-uzupełnieniem elementu a względem elementu b (z definicji, a b = a b).




  1. Narysować schemat układu cyfrowego realizującego funkcję f : {0,1}{1,2} → {0,1} określoną następująco: f(0,0) = f(0,1) = 1, f(1,0) = f(1,1) = 0, jedynie przy użyciu bramki realizującej funkcję binegacji \ (tzw. bramka NOR).




  1. Określić funkcję g: {0,1}{1,2,3} → {0,1} reprezentującą wszystkie osiem możliwości „dodawania” do siebie dwóch cyfr dwójkowych oraz cyfry przeniesienia, dającego jako wynik cyfrę przeniesienia. Narysować schemat układu realizującego tę funkcję, jedynie przy użyciu bramki reprezentowanej przez operację Sheffera / (tzw. bramka NAND).






Pobieranie 270.33 Kb.

Share with your friends:
1   2




©operacji.org 2020
wyślij wiadomość

    Strona główna