030 031

30

Działania zdefiniowane w dwuelementowej algebrze Boole'a, zarótO podstawowe jak i złożone, nazywamy funkcjami logicznymi. Wymienione tożsamości (?)    ? (© pozwalają upraszczać wyrażenia opisujące wieloargumento-

we funkcje logiczne, ułatwiając Ich analizę.

Przykład 1.19

Uprościć funkcję logiczną daną wyrażeniem

f(x,y,z) = xz + xyz + yz + Xyz.

Korzystając z tożsamości o numerach wypisanych między znakami równości, realizujemy następujący ciąg przekształceń

f(x,y,z) = (lj)    =    xz • xyz • yz + xyz =

@ ©    =    (* + *)(x ♦ y + ®)(y + ź)    + iyź =

(?) = [x(x+yt-ź) + ź(x+y+z}](y+ź)+ xyz =

(?) ©    =    [«+^+*(x+x+y+*)] (y+z)    +    xyź    =

®0 d)    =    [xy + z(1+y+z)](y+ź) ♦    xyź    =

© ©    =    (xy+z)(y+z) +    s

© © w z+xyy + xyź =@© © © = ź+xy7 =

© © = * #

Inną, oprócz wyrażeń, formą zapisu funkcji logicznej jest tablica,w której) wszystkim możliwym wartościom argumentów przyporządkowuje się odpowiednie wartości funkcji.

Przykład 1.20

Funkcję f = xylw + xzw + xw + y przedstawić w tablicy.

Tworząc tablice dla poszczególnych składników funkcji i sumując je logicznie, otrzymujemy tablicę jak na rys. 1.17.

Zadanie takie można wykonać znacznie szybciej, wpisując jedynki odpowiadające kolejnym składnikom do jednej tablicy 1 uzupełniając ją zerami.

1.3.2. Ważniejsze funkcje logiczne

jest wzorem

ii,    " * ■'; ....... -

W dwuelementowej algebrze Boole'a zarówno zmienne, jak i ich funkcje przyjmują tylko dwie wartości, toteż liczba różnych funkcji logicznych o skończonej liczbie argumentów jest skończona. Można zatem zapytać - ile jest różnych funkcji logicznych n zmiennych?

liczba różnych ciągów zerojedynkowych o długości n, czyli liczba wariacji z powtórzeniami (tzw. próbek) n, spośród 2 elementów, wynosi 2^a. Poszczególne funkcje różnią się położeniem zer i jedynek na 2^a pozycjach, czyli są próbkami 2ⁿ spośród 2 elementów. Tak więc, liczba 1^ n-argumentowych funkcji logicznych dar

Na rys. 1.18 zilustrowano ten problem dla n = 2 i podano wartości 1^ dla n = 1:5.

*1*1	(i	fi		K,		_
1 «	0	t		i	i
1 1	0	o		1	i	1 (
i a	0	0		i	i	I 3 i
1 \	0	1		i	k	( 5 5 3 (

S Wi H t 1 1 1 (

"’¹ l*.K

Rys. 1.18. Liczba n-argumentowych funkcji logicznych

	i w*	33 1S 5 o.	ILOCZYN	i i C	i	j	i 95	i 1	i
■■	C* LU dl EU El
* »			*1		x®y	*»y	x-y	D	<
• 1	i	«	T	i	i	t	t	1	1
• 1	i	i	i	i	i	a	1	•	i
t 1	i	a	i	i	i	i	0	1	t
< t	i	i	i	a	a	i	1	1	i i

Rys. 1.19. Ważniejsze funkcje dwunrguo.ontov.o

nazwy

Analogicznie do trzech funkcji podstawowych, niektóre inne (głównie dwuargumentowe) otrzymały swoje symbole i nazwy. ".ńż/.lejsze z alca zostawione są na rys. 1.19. W podanej tam tabeli zami. czczono również