Guruh talabasi tojiddinov azizbek laboratoriyaishi № Mavzu

Chinlik jadvaliva Bul algebrasi

Ikkita x va yo’zgaruvchilarning elementar mantiqiy funktsiyalarini ko’raylik. 3.2-jadval.

Funktsiya	x, y argumentli funktsiya qiymati					Funktsiya belgisi		Funktsiya nomi
	00	01	10	11
f0	0	0	0	0	0		doimo yolg’on
f1	0	0	0	1	xy		konyunktsiya
f2	0	0	1	0			y bo’yicha tahqiq
f3	0	0	1	1	x		x doimohaqiqiy
f4	0	1	0	0	y		x bo’yicha tahqiq
f5	0	1	0	1	y		y doimo haqiqiy
f6	0	1	1	0	xy		x va y ni 2 ning moduli bo’yicha qo’shish
f7	0	1	1	1	xy		dizyunktsiya
f8	1	0	0	0	xy		Pirs strelkasi
f9	1	0	0	1	xy		teng qiymatlilik
f10	1	0	1	0			y doimo yolg’on
f11	1	0	1	1	xy		implikatsiya
f12	1	1	0	0			x doimo yolg’on
f13	1	1	0	1	yy		implikatsiya
f14	1	1	1	0	x/y		SHeffer shtrixi
f15	1	1	1	1	1		doimo haqiqiy

Laboratoriyaishi № 4.
Mavzu:To’liq aniqlangan Bul funktsiyalari Karno kartalar yordamida mantiqiy funksiyalarni minimallashtirish


Ishning maqsadi va vazmuni: Mantiq funksiyalarini Kvayn usuli yordamida minimallashtirish.
Nazariy qism.
Biror mantiqiy algebra funktsiyasini amalga oshiruvchi mantiqiy sxemani qurishdan avval bu funktsiyani minimallashtirishga urinib ko`rish lozim. Ko`pincha DNSHda berilgan mantiqiy funktsiyalar minimallashtiriladi. Asosiy maqsad –minimalDNSHni olishdir.Mantiqiy algebra funktsiyasining minimal DNSHda barcha diz’yunktiv hadlardagi o`zgaruvchilar va ularning inkorlari sonlarining yig`indisi bu funktsiyaning barcha ekvivalentidagiga nisbatan kam bo`ladi.
Minimallashtirish, ya’ni berilgan mantiqiy funktsiya uchun eng sodda ifodani topish, turli usullar bo`yicha amalga oshiriladi. Quyida ba’zilari bilan tanishib chiqamiz.
Kvayn usuli. Ushbu usul minimallashtiriluvchi mantiqiy funktsiyaning MDNSHda berilishiga asoslanadi. Minimallashtirish ikkita bosqichda amalga oshiriladi.
Birinchi bosqichda MDNSHdan qisqartirilgan DNSHga o`tiladi. Bunda dastlabki mantiqiy funktsiyaning barcha kon’yunktsiyalari juftlari o`zaro taqqoslanadi. Agar AxvaAx kabi kon’yunktsiyalar uchrasa, ular orasida biriktirish amalga oshiriladi:
AxAx= AxAx A
Natijada A(n-1) darajali kon’yunktsiya olinadi. AxvaAx kon’yunktsiyalari esa dastlabki ifodada qolib, MDNSHning boshqa hadlari bilan taqqoslanadi. Dastlabki MDNSHning biriktirish bajarilgan n-darajali kon’yunktsiyalari belgilanadi. Natijada (n-1) darajali elementar kon’yunktsiyalar guruhi van darajali belgilanmagan kon’yunktsiyalar hosil bo`ladi. Belgilanmagan kon’yunktsiyalar oddiy implikantlar hisoblanib, keyinchalik qisqartirilgan DNSHga qo`shiladi. So`ngra tavsiflangan muolaja olingan (n-1) darajali elementar kon’yunktsiyalar guruhiga qo`llaniladi, natijada (n-r) darajali elementar kon’yunktsiyalar guruhi va (n-1) darajali belgilanmagan kon’yunktsiyalar (oddiy implikantlar) olinadi va h. Bosqich yangidan olingan r-darajali (1r n) elementar kon’yunktsiyalar bir-biri bilan birikmay qolgandagina, ya’ni r-darajali oddiy implikantaga aylangandagina tugaydi. Birinchi bosqich bajarilishi natijasida barcha oddiy implikantlarni o`z ichiga oluvchi DNSHning qisqartirilgan yozuvi olinadi.
Misol. Quyidagi mantiqiy funktsiyaning qisqartirilgan DNSHi olinishi talab qilinsin:
(1)
Yechish. Biriktirish amali 1-4, 1-6, 2-3, 2-7, 3-4, 3-8, 5-6, 5-8, 7-8 kon’yunktsiyalari orasida amalga oshiriladi. Dastlabki MDNSHning barcha kon’yunktsiyalari biriktirishda qatnashadi va (1) dagidek tagiga chiziladi. Natijada dastlabki (1) mantiqiy funktsiya quyidagicha yozilishi mumkin:
Olingan ifodada 3-9 va 4-6 kon’yunktsiyalar juftlarini tagiga chizib, ular orasida biriktirish amalini bajaramiz. Natijada dastlabki (1) mantiqiy funktsiyaning qisqartirilgan DNSH olinadi:

Minimallashtirishni bevosita o`zgartirish usuli. Minimallashtirishning ikkinchi bosqichida qisqartirilgan DNSHdan tupik DNSHga o`tiladi va ularning ichidan minimal DNSH tanlab olinadi. Tupik DNSH qisqartirilgan DNSHdan ortiqcha oddiy implikantlarini aniqlab chiqarib tashlash yo`li bilan olinadi. Ortiqcha oddiy implikantlar deganda mantiqiy funktsiya qiymatining o`zgarishiga olib kelmaydigan qisqartirilgan DNSHning chiqarib tashlangan hadlari tushuniladi. Tupik DNSHni olish uchun implikant jadvali (matritsasi) tuziladi. Jadvalning qatorlari qisqartirilgan DNSHning oddiy implikantlari bilan belgilansa, ustunlari dastlabki mantiqiy funktsiya MDNSHning mintermlari bilan belgilanadi. Qatorda har bir oddiy implikanta qarshisiga u 1 qiymatini qabul qiluvchi naborlar tagi  belgisi bilan belgilanadi; mos mintermlar ushbu oddiy implikanta bilan singdiriladi (qoplanadi).
4.1-jadval (1)ning imlikanta jadvali hisoblanadi.
4.1-jadval.

Oddiy implikantlarning umumiy sonidan implikantlari mantiqiy funktsiyaning birlik qiymatlarini qoplovchi qismini ajratib olish zarur; qolgan implikantlar ortiqcha hisoblanadi.
Tupik shakllarni shakllantirish va minimal qoplanishni tanlash mantiqiy funktsiyaning birlik qiymatlarini qoplovchi majburiy oddiy implikantlarni aniqlashdan boshlanadi.