034 035

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(x₁,x₂,Xj) = x₁x₂x_J + x,,x₂Xj + x₁x₂Xj =    ZtfPS

(x₁+x₂+xj)(x₁+x₂+x^)(x₁+x_a+x₅)(x₁+x₂+x₅)(x₁+x₂+x^) ZIIPI    **

Zależność pomiędzy obydwiema postaciami kanonicznymi najłatwiej uchwycić posługując się tzw. liczbową ZNPS oraz ZNPI:

f(*₁.^x2^,”^,,xn^{) =} Z(^L) = nm

gdzie I> Jest listą oddzielonych przecinkami tych Indeksów i, dla    któ

rych 0^ = 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(x_1tx₂,x₃) =2 (2,3,4) = n (0,1,5,6,7)

Dodatkowo zauważmy, że

>x₂,Xj) ⁼ ^ (0,1,5,6,7) — f*](2,3,4)    $4

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 (don't care), oznaczane zazwyczaj przez x. Odpowiedni zapis ma postać

£(^x-l »^x2* * ’" ^,xn^ ⁼ 2] (^> (1^)) ⁼ fi    (Ift))

gdzie L^ jest listą tych indeksów i, dla których = x.

Przykład 1.22

a	b	C	f
•	a	0	0
l	0	i	1
a	1	a	X
•	1	ł	1
l	a	a	a
1	i	i	t
\	i	a	X
ł	i	1	X

Rys. 1.21. Tablioa funkcji z przykładu 1.22

Funkcję f(a,b,c) zadaną tabelą na rys. 1.21 zapisujemy w postaci:

f(a,b,c) = ^(1,3,5,(2,6,7))

lub

f(a,b,c) = fi (0,4,(2,6,7)) $4

Ha zakofrąąenie 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 (HP5) i normalną postacią iloczynu (NPI).

Przykład 1.21 c.d.

Zamiast podanych uprzednio ZNPS i ZNPI funkcję f ® (*.] ’© x₂) -— ^2*3 ^można tapłsać w postaci (sprawdź!)

f = x^x₂ +    NPS

= (x₁+x₂)(x₁ńi₂)(x₂+x^) = (x₁+x₂)(x₁+x₂)(J₁«ćj) ^N?I    **

1.3.4» Systemy funkcjonalnie pełne

Każdą funkcję logiczną możaa 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, te podstawowy system funkcjonalnie pełny tworzą funkcje OR, AND, HOT. 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. łl), lub sprawdzając, czy za ich pomocą można wyrazić funkcje tworzące system podstawowy. Tą ostatnią metodą można łatwo pokazać, że NAND 1 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    i    |    X    =    x X    =    x

(*ł    x)((y    ł    y)    =    xły    =    8    5 » xy

(x ł    y)t(x    ł    y)    =    xylxy    =    xy = x+y = x+y

Ponieważ za pomocą funkcji NOR można wyrazić sumę, iloczyn i-negację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 prt-.cy £21].