032 033

C>32

angielskie, szczególnie rozpowszechnione w literaturze technicznej, oparte na spójnikach zdaniowych (patrz p. 1,3.4.1).

Dla liczby argumentów większej niż Z istnieją też inne funkcje o dużym znaczeniu praktycznym, np, większościowa (liajority), przyjmująca wartość 1, gdy większość argumentów równa jest 1, mniejszościowa (Minority), parzystości (Bven Parity), równa 1, gdy parzysta liczba argumentów równa jest 1, czy nleparzystości (Odd Parity),

1.3.3. Postacie kanoniczne funkcji logicznej

Każdą funkcję logiczną można zawsze rozłożyć na składniki, według, zasady*^ ,

rn x₁'f(1,x₂,...,x_a) ♦ Ej^fCO,^,...,^)    .(1.8)

Kontynuując ten rozkład aż do wyczerpania listy zmiennych uzyskujemy ostatecznie

f(x₁,*₂,...,^_l) sjŁjmg'... x_n-f(1,1,...,1) +

+ X^X₂ ... Xjj* f(0,1,...,1) ♦ •*. + Xjy3C^ »»    f(0,0,...,0)    (1.9)

Przyporządkowując każdemu pełnemu iloczynowi (zawierającemu wszystkie zmienne'z negacją.lub bez) liczbę binarną wg zasady

x_fc — 1,    5^—-O    (1.10)    |

możemy go oznaczyć symbolem 1^, gdzie indeks i reprezentuje wartość dziesiętną uzyskanej liczby binarnej (numer iloczynu). Np. pełnemu iloczynowi x₁5E₂Xj odpowiada liczba (101 )₂ = (5)^0* a więc należy go oznaczyć symbolem 1^*

Oznaczając również

f (próbka wartości zmiennych) =    _pr<M,_kl

(np. f(0ll);= aj); wzór (1.9) można, zapisać w postaci

2^ft-f

*(*-l*^x2»^,,T»*n)    *** ¹¹

Ponieważ a_Ł « {0,T| , więc sumowanie można przeprowadzać tylko po tych Indeksach 1, dla któryoh a_Ł = 1, eó symbolicznie zapisujemy w postaci

f(x₁.x₂,...,m_tt) = £ I_t    (1.11)

V:

Każdą funkcję .logiczną można więc przedstawić w postaci sumy pełnych iloczynów, odpowiadających — zgodnie z przyporządkowaniem (1.10)    - tym

•> Prawdziwość tego twierdzenia Łatwo sprawdzić podstawiając do obu. stron wzoru (1.8)

= 1 oraz    r 0.

próbkom wartości zmiennych, przy których-funkcja ta przyjmuje wartość 1. Takie przedstawienie jest Jedną z postaci kanonicznych funkcji logicznej 1 nazywa się zupełna normalna postacią sumacy.lna (ZNPS).

Inną po3tać kanoniczną uzyskuje 3ię w wyniku rozkładu funkcji logicznej na czynniki wg wzoru

f(x₁,x₂,...,x_|l) = [x₁+f(0,x₂.....x_n)][x₁+f(1,x₂.....x_Q)]    (1.12)

Kontynuując ten rozkład 1 stosując w każdym kroku aksjomat (§) otrzymujemy ostatecznie

t(x₁,x₂,...,x_a) = [x₁+x₂+...+x_n+f(0,0,...,0}]|jx₁+x₂+...+x_n+f(1_f0,..,q .] ..[x₁+x^+.;.+x_n+f(1,1,...,1)]    (1.13)

Przyporządkowując każdej pełnej sumie liczbę binarną wg zasady*^

x_k—0,    (1.14)

możemy Ją (tzn. sumę) oznaczyć symbolem S^, gdzie 1 reprezentuje wartość dziesiętną uzyskanej liczby binarnej (numer sumy). Np. pełnej sumie x₁+x₂+ij odpowiada liczba (010)₂ = (2)₁₀, a więo oznaczamy Ją symbolem Sg. Wzór (1.13) można teraz zapisać w postaci

f(x_1tx_?l...,x ) = fl (Sj+oijJ-s PI S_t    (1.15)

' ^c    i-o    a₄.o

Przedstawienie funkcji w postaci Iloczynu pełnych sum, odpowiadających -zgodnie z przyporządkowaniem (1.14) - tym próbkom wartości zmiennych,przy których funkcja ta przyjmuje wartość 0, nazywamy zupełna normalna postacią iloczynowa (ZNPI).

Przykład 1.21 .

Funkcję f = (x^ © x₂) —— *2^x3 P^I‘^z9<i^stawŁ<i ^w postaciach kanoniczny*

xtx,		*0	^xl*^x!			f
1	1	1	1	0	1	Os
1	0	f	1	ł	1	Os
0	1	•	1		«	1'
1	i	ł	1	1	1
i	0	0	1	0	1	1"
t	0	i	1	1	1	0'
1	1	0	•	0	1	0'
1	1	1	e	1	1	('

Rys. 1.20. Tablica funkcji z przykładu 1.21

Zwróćny uwagę, że przyporządkowanie to jest odwrotne do (1.10).