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₂Xj + x,jX₂Xj + x₁x₂x_J =    ZNPS

(x₁+x₂+xj)(x₁+x₂+x^)(x₁+x₂+xj) (x₁+x₂+xj)(x₁+x₂+xj) Zif PI    14

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

f(x₁,x₂,...,x_n) = stu = niD

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(x₁,x₂,x₃) =2 (2,3,4) = n(0.1.5.6,7)

Dodatkowo zauważmy, że

?(x_n,x₂,x₃) =2 (0,1,5,6,7) = [”](2,3,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 (doa”t care), oznaczane zazwyczaj przez x.

Odpowiedni zapis ma postać

f (^x^ ,x₂, • • • 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 (

TTTT

10 11

0    1 o x 0 111 10 0 0 10 11

1    i o x i i 1 x

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., ’© x₂) —— *2^x3 ^m0^^na zapisać w postaci (sprawdź!)

f = x^x₂ + x^x₂Xj    NPS

= (x₁+x₂)(x₁+x₂)(x₂+x₅) = (x₁+x₂)(x₁-t-x₂)(x₁+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].