34
Wypełniamy tabelę jak pokazano na rys. 1.20, z której na podstawie wzorów (1.10), (1.11) i (1.14), (1.15) otrzymujemy
f(x1,x2,Xj) = x1x2Xj + x,jX2Xj + x1x2xJ = ZNPS
(x1+x2+xj)(x1+x2+x^)(x1+x2+xj) (x1+x2+xj)(x1+x2+xj) Zif PI 14
Zależność pomiędzy obydwiema postaciami kanonicznymi najłatwiej uchwycić posługując się tzw. liczbową ZNPS Oraz ZNPI:
gdzie L jest listą oddzielonych przecinkami tych indeksów i, dla których = 1, zaś X Jest listą dopełniającą, zawierającą te i, dla których = 0.
Przykład 1.21 c.d.
Z tabeli lub wyznaczonych poprzednio ZNPS i ZNPI otrzymujemy natychmiast postać liczbową
f(x1,x2,x3) =2 (2,3,4) = n(0.1.5.6,7)
Dodatkowo zauważmy, że
Zwróćmy uwagę, że przy tym sposobie zapisu funkcji wymagane jest podanie listy argumentów. Np. zapis y = n (2,4,6) nie definiuje funkcji, gdyż nie ujawnia ani liczby, ani nazw i kolejności zmiennych.
Liczbowy zapis form kanonicznych jest szczególnie użyteczny w przypadku .funkcji nie w pełni określonych, tzn. takich, które są zadane tylko dla niektórych próbek wartości argumentów, a dla pozostałych mogą przyjmować wartości dow#lne (doa”t care), oznaczane zazwyczaj przez x.
Odpowiedni zapis ma postać
f (x^ ,x2, • • • iijj) =2](L, (L^)) = P] (lAl^, (L^)) gdzie L^ jest listą tych indeksów i, dla których = x.
Przykład 1.22 a b c (
10 11
0 1 o x 0 111 10 0 0 10 11
Rys. 1.21. Tablica funkcji z przykładu 1.22
Funkcję f(a,b,c) zadaną tabelą na rys. 1.21 zapisujemy w postaci:
f(a,b,c) = £ 0.3.5,(2,6,7))
lub
f(a,b,c) = fi (0,4,(2,6,7)) *4
Na zako^Łjenie zauważmy, że ZNPS i ZNPI są rozwlekłymi formami . .analitycznego opisu funkcji. Stosując tożsamości algebry Boole'a można z niektórych pełnych iloczynów lub sum usunąć jedną lub więcej zmiennych. Uzyskane w ten sposób sumy niepełnych iloczynów lub iloczyny niepełnych sum nazywane są, odpowiednio, normalną postacią sumy (NP3) i normalną postacią Iloczynu (NPI).
Przykład 1.21 c.d.
Zamiast podanych uprzednio ZNPS i ZNPI funkcję f = (x., ’© x2) —— *2x3 m0^na zapisać w postaci (sprawdź!)
f = x^x2 + x^x2Xj NPS
= (x1+x2)(x1+x2)(x2+x5) = (x1+x2)(x1-t-x2)(x1+Xj) NPI **
1.3.ą. Systemy funkcjonalnie pełne
Każdą funkcję logiczną można uzyskać w wyniku superpozycji innych funkcji. Szczególnie Interesujący jest problem znalezienia zespołu funkcji,za pomocą których można wyrazić wszystkie pozostałe. Zespół taki nazywamy system funkcjonalnie pełnym. Z definicji algebry Boole'a wynika, że podstawowy system funkcjonalnie pełny tworzą funkcje OR, AND, NOT. Metodyka przedstawiania dowolnych funkcji w tym systemie została omówiona w poprzednim punkcie (patrz przykład 1.21). Inne systemy funkcjonalnie pełne można wybrać posługując się odpowiednim twierdzeniem (£3] str. ś-1), lub sprawdzając, czy za ich pomocą można wyrazić funkcje tworzące system podstawowy. Tą ostatnią metodą można łatwo pokazać, że NAND i NOR są, każda z osobna, systemami funkcjonalnie pełnymi.
Przykład 1.23
Pokazać, że funkcja NOR jest systemem funkcjonalnie pełnym. Przedstawiając funkcję NOR w ZNPS mamy:
x ł y = x y
i stąd 1 | 1 =xx=x
(x ł x)l(y ł y) = xty = X s = xy
(x ( y)((x ł y) = xylxy = xy = x+y = x+y
Ponieważ za pomocą funkcji NOR można wyrazić sumę, iloczyn i-tregację.funkcja ta Jest systemem funkcjonalnie pełnym. #
1.3.5* Przykłady algebr Boole'a
Często podaje się trzy poniższe przykłady algebr Boole/a, ważne ze względów poznawczych. Dalsze przykłady można znaleźć np. w prac./ [21].