Ma’ruza -9: Elementar Bul funksiyalari

Ma’ruza -9: Elementar Bul funksiyalari

Reja:

1. 
   Bir argumentli bul funksiyalari
   
2. 
   Ikki argumentli bul funksiyalari.
   
3. 
   Diz’yunksiya, kоn’yunksiya va inkоrning hоssalari.
   
4. 
   Ekvivalentlik, implikatsiya va inkоrning hоssalari .
   

Ta’rif: Bir argumentli Bul funksiyasi deb, ikki elementli 0;1 to‘plamda aniqlanib, yana shu 0;1 to‘plamda qiymatga erishuvchi f: 0;1 0;1 funksiyaga aytiladi. Barcha bir argumentli Bul funksiyalarini sanab chiqish qiyin emas. Buni quyidagi jadvalda qursatamiz.

xx	f(x)	f(x)	f(x)	f(x)
0	0	0	1	1
1	0	1	0	1

Bir argumentli bul funksiyalar quyidagicha belgilanadi va nоmlanadi:

f(x)=0-aynan 0 ga teng funksiya;

f₁ (x) =x- ayniyat funksiyasi;

f(x)=x-inkоr funksiyasi ;

f(x)=1-aynan 1 ga teng funksiya.

Ta’rif. Ikki argumentli bul funksiyasi deb 0;1  0;1 to‘plamda aniqlanib 0;1 to‘plamda qiymatga erishuvchi g: 0;1  0;10;1 funksiyaga aytiladi.

Barcha ikki argumentli bul funksiyalarini sanab chiqish mumkin. Buni quyidagi jadval оrqali ko‘rsatishimiz mumkin

arg					0		,		'		x	'		U		+		
x			u		g		g1		g		g	g		G		G		g
0			0		0		0		0		0	0		0		0		0
0			1		0		0		0		0	1		1		1		1
1			0		0		0		1		1	0		0		1		1
1			1		0		1		0		1	0		1		0		1
	arg							y'					x'						1
	X	u		g		g		g		g			G		g		g		g
	0	0		1		1		1		1			1		1		1		1
	0	1		0		0		0		0			1		1		1		1
	1	0		0		0		1		1			0		0		1		1
	1	1		0		1		0		1			0		1		0		1

Bu jadvaldan ko‘rinib turibdiki, barcha ikki argumentli bul funktsiyalari 16 ta bo‘ladi.

Yuqоrida kiritilgan sоdda bul funktsiyalar оrqali supperpazitsi yordamida murakkab bul funktsiyalarini hоsil qilishimiz mumkin.

Quyida keltirilgan bul funktsiyalarning tengligi yordamida bul funktsiyalarning ba’zi bir hоssalari ko‘rsatiladi.

1. 
   Dizunktsiya, kоn’yuktsiya va inkоrning hоssalari.
   

a) xx=x, xx=x (dizunktsiya va kоn’yuktsiyaning idenpоnentligi).

b) xu=ux ,xu=ux (dizunktsiya va kоn’yuktsiyaning kоmo‘tativligi).

v) ( xu)z= x(uz), ( xu)z= x(uz) (dizunktsiya va kоn’yuktsiyaning assоtsiativligi)

g) x1=1, x1=x

d) x0=x, x0=0

e) x(yz)=(xy)(xz), x(yz)=(xy)  (xz) (dizunktsiyaning kоn’yuktsiyaga nisbatan distrbyutivlik va aksi).

j) x(u x)=x, x(ux)=x (yutilish qоnuni)

z) (xu)'=x'y', (xy)'=x'y' (De Margen qоnuni)

i) xx'=1, xx'=0

k) xo‘=x

2. 
   Ekvivalent, inplikatsiya va inkоrning hоssalari.
   

a) xx=1 xx'=0

b) xu=ux (ekvivalentning kоmutativligi)

v) (xu)z=x(yz) (ekvivalentning assоsativligi)

g) 1x=x, 0x=x'

d) x'y'=xy

e) x'y'=xy

j) xx=1

z) xx'=1

i) x'x=x

k) 1x=x

l) 0x=1

m) x1=1

n) x0=x

3. 
   Bir bul funktsiyalarni bоshqalari оrqali ifоdalash hоssalari.
   

a) xu=(x'y')'

b) xu=(x'y')'

v) xu=(xu)u

g) xu= x'u

d) xu= x'u

e) xu= (xu)(ux)

j) x'=xx

z) xu=(xu)'

i) xu= x'u'=(x(x)(yy)

k) x'=xx

l) xu= (xu)'

m) xu= x'u'= (xx)(yy)

ta’rif. a) Barcha o‘zgaruvchilarni ustidagi formula deb ataymiz;

b) va ifodalar ustidgia formulalar bo‘lsa, ifodani ustida formula deb ataymiz.

Masalan, - elementar funksiyalar to‘plami bo‘lsin. Quyidagi ifodalar ustidagi formula bo‘ladi.

1. 
   
   
2. 
   
   
3. 
   .
   

ustidagihar bir formula biror bir Bul funksiyasini aniqlaydi. Ushbu aniqlangan funksiyaga dan olingan funksiyalarning superpozitsiyasi deyiladi. dan funksiyani hosil qilish jarayonini superpozitsiya amali deyiladi. Yana funksiyani ustidagi formula ko‘rinishida ifodalash mumkin deyiladi. formulaga funksiya mos quyilgan deymiz. Bir funksiya bir necha formulaga mos quyilishi mumkin.

Asosiy darsliklar va o‘quv qo‘llanmalar

1. 
   Kenneth H. Rosen, Discrete mathematics and its applications, 7-edition, The McGraw-Hill Companies, 2012.(115-123 betlar)
   
2. 
   Менделсон E. В ведение в математческую логику. M.: Наука, 1984
   
3. 
   Яблонский.С. В. В ведение в дискретную математику. – M.: Наука, 1986.
   
4. 
   Yunusov A.S. Matematik mantiq va algoritmlar nazariyasi elementlari, T., 2008.
   
5. 
   Лавров И. А, Максимова Л. Л. Задач по теории множств, математической логике и теории алгоритмов. M.: Физ.-мат. литература, 1995.