Бетлер. Ten’ ku’shli formulalar ha’m wolardi’n’ tiykarg’i’ qa’siyetleri. Qosarli’q (yekilik) ni’zami’

§4. Ayti’mlar algebrasi’ni’n’ funkciyalari’. Bul algebrasi’.

Funkciyalardi’n’ toli’q sistemalari’.

Ayti’mlar algebrasi’ni’n ’ funkciyalari’. Bul algebrasi’.

Funkciyalardi’n’ toli’q sistemalari’ Logikali’q a ’mellerdin ’ toli’q sistemasi’. Term tu ’sinigi

10. Ayti’mlar algebrasi’ni’n’ funkciyalari’. Bizge belgili, logikali’q a’meller ayti’mlar algebrasi’ ko’z-qarasi’nan shi’nli’q kestesi menen toli’q xarakterlenedi. Yegerde funkciyani’n’ keste ko’rinisinde beriliwin yesapqa alsaq, wonda ayti’mlar algebrasi’nda da funkciya tu’sinigini’n’ bar yekenligin bilemiz.

ani’qlama. Ayti’mlar algebrasi’ni’n’ xl3 x2,..., xn argumenti f ( xi,x2,...,xn) funkciyasi’

dep, 0 ha’m 1 ma’nisti qabi’l yetiwshi funkciyag’a ayti’ladi’ ha’m woni’n’ x1,x2,...,xn argumentleri de 0 ha’m 1 ma’nisti qabi’l yetedi. Bul jag’daydaf ( x1,x2,...,xn) funkciyasi’ wo’zi’ni’n’ shi’nli’q kestesi menen beriledi.

x1	x2	x3		xn-1	xn	f (xl, x2,..., xn )
0	0	0		0	0	f (0,0,...,0,0)
1	0	0		0	0	f (1,0,...,0,0)
1	1	1		1	0	f (1,1,...,1,0)
1	1	1		1	0	f (1,1,...,1,1)

Bul kestenin’ ha’r bir qatari’nda da’slep wo’zgeriwshilerinin’ (a1,a2,...,an) leri ha’m usi’ ma’nisler ha’m usi’ ma’nisler qatari’nda f funkciyani’n’ f (a1,a2,...,an)ma’nisi beriledi.n wo’zgeriwshi ushi’n ma’nisler qatari’ni’n’ sani’ 2nge ha’m funkciyalari’ni’n’ sani’

2П

22 ge ten’ boladi’.

A
f = 1,

f2 = X V У,

f3 = У ^ * f4 = X ^ У,


f10 = У,

fii = У,

f 12 = * V У,


f14 = * ^ У, f15 = * * У,

fi6 = 0.

yti’mlar algebrasi’ni’n’ tiykarg’i’ elementar f = f (x, у) funkciyalari’ to’mendegilerden ibirat:

*	У	f,	f2	f3	f4	f5	f6	fl	f.	f9	/10	fn	f12	f13	fu	f15	f16
1	1	1	1	1	1	0	1	1	0	0	0	1	0	0	0	1	0
1	0	1	1	1	0	1	1	0	0	1	1	0	0	0	1	0	0
0	1	1	1	0	1	1	0	0	1	1	0	1	0	1	0	0	0
0	0	1	0	1	1	1	0	1	1	0	1	0	1	0	0	0	0

f5 = * * У, f6 = *, f7 = X ^ У, f8 = *

f9 = * ^ У,

f13 = У ^ *

Yeger f (0,0,0,.,.,0)=0 bolsa, wonda f ( Xj,x2,...,xn) funkciyag’a 0 saqlawshi’ funkciya dep ayti’ladi’. Yegerde f (1,1,1,... ,1)=1 bolsa, wonda f (Xj,x2,...,xn) funkciyag’a 1 saqlawshi’ funkciya dep

ataymi’z. n argumentli 0 saqlawshi’ funkciyalardi’n’ sani’ 2 “ ge

2« 1

ha’m de 1 saqlawshi’ funkciyalardi’n’ sani’ 2 “ ge ten’ boladi’.

57

Ayti’mlar algebrasi’ndag’i’ n argumentli 0 saqlawshi’ funkciyalardi’n’ ko’pligin P0 ha’m 1 saqlawshi’ funkciyalardi’n’ ko’pligin P1 arqali’ belgileymiz.

ani’qlama. f ha’m g lar ayti’mlar algebrasi’ni’n’ funkciyasi’ ha’m X1,x2,...,xn lar hesh bolmag’anda birewinin’ argumentleri bolsi’n. Yeger X1,x2,...,xn argumentlerinin’ ha’mme ma’nisleri qatari’ ushi’n f ha’m g funkciyalari’ni’n’ sa’ykes ma’nisleri birdey bolsa, wonda f ha’m g funkciyalar ten’ ku’shli funkciyalar dep ataladi’ ha’m f = g ko’rinisinde jazi’ladi’.

ani’qlama. Yegerde to’mendegi qatnas

f (x1, X2 ^.^ Xi-j,1, Xi+j ,..., Xn ) = f (X^ X2,..., Xi-1 ,0, Xi+1 ,..., Xn )

Wori’nlansa, wonda Xi argumentke f ( X1,X2,...,Xn) funkciyani’n’ wo’trik argumenti dep ataladi’. Yegerde

f (Xj, x2,..., Xi-1,1, X!+i ,..., Xn ) * f (X1, X2,..., X-1,0, X +l,..., Xn ) bo^

wonda Xi argumentke f ( X1,X2,...,Xn) funkciyani’n’ wo’trik yemes (a’hiymetli) argumenti dep ataladi’.

Mi’sali’. f (X,y) = X u (Xy) funkciya ushi’n wol wo’trik argument boladi’, sebebi f (1,0) = f (0,1)

Funkciyani’n’ argumentlerini’n’ qatari’na qa’legenshe wo’trik argument jazi’w mu’mkin.

Yendi ayti’mlar algebrasi’ni’n’ funkciyalari’ni’n’ superpozitsiyasi’ tu’sinigin kiriteyik.

ani’qlama. Ф = {Pl(Xu, , Х^Д Pm(Xm1, , Xmkm ) }

ayti’mlar algebrasi’ni’n’ funkciyalari’ni’n’ shekli sistemasi’ bolsi’n.

To’mendegi yeki usi’ldi’n’ birewi menen payda etilgen щ funkciyag’a Ф sistemadagi’ p1,...,pm funkciyalari’ni’n’ elementar superpozitsiyasi’ yamasa bir rangli superpozitsiyasi’ dep ayti’ladi’:

a) qandayda bir pp е Ф funkciyani’n’ Xji argumentin qayta ataw usi’li’, yag’ni’y

Pj (Xj1, X; 2 ,..., XJI-1, У, Xji+1,..., XJkl)

bul jerde wol, Xjk wo’zgeriwshilerinin’ birewi menen sa’ykes

keliwi mu’mkin.

qandayda bir cp. e Ф funkciyani’n’ bazi’bir x,( argumenti womi’na yekinshi bir (pe (xe1,..., xek) еФ funkciyani’ qoyi’w usi’li’, yag’ni’y

Vj (Xl — Xji-1) Pe(Xe1’--,Xek), ^ji^.^ X ]K)

Yeger Ф sistema funkciyalari’ni’n’ k rangli superpozitsiyalari’ klasi’ Ф(k) berilgen bolsa, wonda Ф(k+1) = (Ф(k ))(1) boladi’.

yeskertiw. 4-ani’qlamani’n’ a) bo’limine tiykarlani’p bir qi’yli’

shi’nli’q kestege iye boli’p, biraq wo’zgeriwshilerinin’ belgileniwi menen pari’q qi’latug’i’n funkciyalar bir-birinin’ superpoziciyasi’ boladi’.

yeskertiw. 4-ani’qlamani’n’ a) bo’limine tiykarlani’p bazi’bir xJi wo’zgeriwshini xjk (j k) menen qayta atasaq, na’tiyjede kem

wo’zgeriwshili fUnkciyag’a iye bolami’z. Bul jag’dayda xjl ha’m Xjk wo’zgeriwshiler birdey ten’lestiriledi dep ataymi’z. Ma’selen, x v y ha’m x л у funkciyalardag’i’ о ti о qayta atasaq, wonda x v x = x

ha’m x л x = 0 funkciyalari’n payda yetemiz.

5-ani’qlama. X, xy, x v y, x ^ y, x O- y, tiykarg’i’ elementar

funkciyalardi’n’ superpoziciyasi’na formula dep aytami’z.

20. Bul algebrasi’. Konyunktsiya (x л y), dizyunkciya (x v y), x biykarlaw a’melleri ha’m 0.1 е M elementleri ani’qlan- g’an M ko’pliginde usi’ logikali’q a’meller ha’m 0,1 elementler ushi’n to’mendegi aksiomalar

X = X	(1)
II &	(2)
(xy) z = x(yz)	(3)
X v y = y v X	(4)
(X v y) v z = X v (y v z)	(5)
x(y v z) = xy v xz	(6)

x v yz = (x v y)(x v z)	(7)
x v y = x л y	(8)
x л y = x v y	(9)
x v x = x	(10)
x л x = x	(11)
1 л x = x	(12)
0 v x = x	(13)

wori’nlansa, bunday M ko’pligine Bul algebrasi’ dep ataladi’.

Bul algebrasi’na to’mendegi ko’plikler mi’sal bola aladi’:

M -qandayda bir ko’plik (ma’selen, tuwri’da jatqan tochkalar

ko’pligi yaki natural sanlar ko’pligi) ha’m цм -M nin’ ha’mme u’les ko’pliklerinen ibirat ko’plik bolsi’n. xy(x, y е цм ) arqali’ x ha’m y ko’pliklerinin’ x л y kesilispesin, x v y arqali’ x ha’m y ko’p-

liklerinin’ x v y birikpesin, x arqali’ x ko’pliginin’ M ko’pligine shekem x toli’qti’ri’wshi’si’n, 0 arqali’ 0 bos ko’plikti ha’m 1 arqali’ M ko’plikti belgilep alami’z. Wol jag’dayda /dM ko’plik Bul algebrasi’ boladi’, sebebi joqari’da ko’rsetilgen 13 aksioma wori’nlanadi’.

Ayti’mlar ko’pligi ushi’n л,v ha’m □amalleri ha’m de 0 ha’m 1 elementleri ani’qlang’anli’g’i’ ushi’n bul ko’plikti Bul algebrasi’ dep shama qi’li’wi’mi’z turg’an ga’p. Biraq buni’n’ ushi’n to’mendegi ani’qli’qti’ kiritiw kerek. A ha’m B ayti’mlar birdeyine ten’ boli’wi’ ushi’n A o- B ekvivalentlik absolyut ras boli’wi’ kerek. U’si’nday tu’sinik kiritilgen ayti’mlar ko’pligi Bul algebrasi’na mi’sal bola aladi’.

Sorawlar ha’m shi’ni’g’i’wlar

l.Logikali’q a’mellerdin’ ha’m formulalardi’n’ shi’nli’q oblasti’ dep

nege aytami’z?

Bul algebrasi’ni’n’ ani’qlamasi’n keltirin’.

Logika algebrasi’ni’n’ funkciyasi’ dep nege aytami’z?

Logikali’q a’mellerdin’ toli’q sistemasi’ qalay ani’qlanadi’?

^ sistema operatsiyalardi’n’ toli’q sistemasi’ dep nege aytami’z?

^ = (a,v, -} , = (л, ^3 = (v, -} sistemasi’ni’n’ toli’q

sistema bolatug’i’ni’n ko’rsetin’.

Sheffer shtrixi’ ha’m Pirs strelkasi’ toli’q sistema yekenligin ko’rsetin’.

To’mendegi berilgen formulalardi’n’ shi’nli’q oblasti’n tabi’n’:

A = xy v xy v xy; B = (x v y)(x v y)(x v y);

C = xyz v xyz v xyz ; E = xy o x v xy;

D = (x v y v z )(x v y v z)(x v y v z ); L = x v y — z

F = (x o y) a (xy v xy); J = x v y — (x o y);

= (x —— z) —— (y —— z) —— (x —— y).

Jalg’an ma’nis qabi’l yetiwshi (f (0,0,...,0) = 0) n argumentli ha’r qi’yli’ funkciyalardi’n’ sani’ neshew boladi’?

Ras ma’nis qabi’l yetiwshi (f (1,1,...,1) = 1) n argumentli ha’r qi’yli’ funkciyalardi’n’ sani’ neshew boladi’?