35636 Untitled Scanned 14

- 28 -

2.2/SYNTEZA FUNKCJI LOGICZNYCH

Zbiór funkcji, który umożliwia syntezę dowolnie złożonych funkcji logicznych, nazywa się systemem funkcjonalnie pełnym. Jeżeli wszystkie elementy tego zbioru są niezbędne, to system taki nazywa się minimalnym. Każdy inny system funkcjonalnie pełny jest nieminimalny.

Funkcje: alternatywa, koniunkcja i negacja tworzą tzw.podstawowy system funkcjonalnie pełny. Jest on systemem niemini-malnym. System ten jest podstawowym narzędziem syntezy funkcji.

Daną funkcję logiczną przećstawió można w postaci dowolnie wielu równoważnych wyrażeń logicznych. Dlatego też nie należy identyfikować funkcji logicznej z opisującymi ją wyrażeniami.

Szczególne znaczenie mają tzw. kanoniczne postacie funkcji: kanoniczna postać alternatywna i kanoniczna postać koniun-kcyjna. Do wyjaśnienia budowy postaci kanonicznych niezbędne jest wprowadzenie kilku pojęć.

Składnik jedności (pełny iloczyn) funkcji logicznej jest to koniunkcja, w której występują symbole wszystkich argumentów funkcji zanegowane lub niezanegowane. Iloczyn, w którym nie ma wszystkich argumentów nazywa się iloczynem elementarnym.

Czynnik zera (pełna suma) jest to suma wszystkich argumentów danej funkcji zanegowanych lub niezanegowanych. Suma, w której nie ma wszystkich argumentów funkcji nazywa się sumą elementarną.

W celu umożliwienia tworzenia symbolicznego zapisu funkcji przyjęto oznaczenia: dla składników jedności - K_i, dla czynników zera -    , przy czym składnik jedności K oznacza się indek

sem i jeżeli dla stanu argumentów o numerze i przyjmuje on wartość 1 (np. dla funkcji y = f(x^,x₀,x^,x^) przy i = 3 etan argumentów jest 0011, a więc    , bo 0-5-1*1 = 1).

Czynnik zera D oznacza się indeksem j Jeżeli dla stanu argumentów o numerze j przyjmuje on wartość 0 (np. dla funkcji y = f(x₁ ,x₂,x^,x₄ ) D^ = x₁ + x₂+ x^+ x^, bo 0 + 0 + T + 1 = 0).

Przykładowo, taki sposób oznaczeń składników Jedności i czynników zera w przypadku funkcji trój argumentowych podaje tablica 2.3.

Tablica 2.3

Składniki Jedności i czynniki zera Dj funkcji trójargumentowych

Nr Btanu

Stan argumentów ^X1 ^X2 ^X3

^Ki

^Dd

0

0

0

0

^Ko

O

^x1’^x2*^x3

^Do

a

^X1

+

^x2

+

^x3

• 1

0

0

1

*1

-

^X1*^x2*^x3

^D1

s

^X1

+

^x2

+

x3

2

0

1

0

k2

B

X^•Xg•x^

^D2

■

^X1

+

^x2

+

^x3

3

0

1

1

^K3

=

^xr^x2*^x3

^B3

3

^X1

+

x2

+

^x3

4

1

0

0

^K4

B

^X1*^x2*^x3

^D4

3

^31

+

X2

+

^x3

5

1

0

1

^K5

-

x1*x2*x^

^D5

3

^X1

+

x2

+

^x3

6

1

1

0

^K6

W

X1 *X2*X-J

s

^X1

+

x2

+

^x3

7

1

1

1

h

S

x^ * x2•x^

*7

^X1

+

x2

+

^x3

Wprowadzając oznaczenia wartości funkcji y = f• •• ^xn) przy kolejnych stanach argumentów:

y(0,0,...,0) = f_Q

y(0,0,...,U = f₁    (₂.1)

y(1,1.....1) = f₂n_-1

kanoniczną postaó alternatywną można zapisać Jako

y(x_1fx₂,...,x_n) = f₀-K₀ + f₁-K_l + ... f₂ⁿ»₁'^K2ⁿ_i    ^f2*²⁾

a kanoniczną postaó koniunkcyjną Jako

y(x.,,x₂,...,x_n)= (fę + Dq) * ( f ^ + D₁)..,^f₂n_₁ + D₂ⁿ-1^ ^²*^)

Słuszność zapisów (2.2) i (2.3) wykazać można podstaY/iejąc do obu stron kolejne stany argumentów. Na przykład, dle stanu argumentów 0,0,...,0 spośród wszystkich składników jedności jedynie K_Q = 1, a więc z (2.2) otrzymuje się