I kirish II. Asosiy qism matematik mantiq funksiyalarining minimallashtirish muammosi masalasining qo‘yilishi

2-ta’rif. da (2)

ifodaga dizyunktiv normal shakl (DNSH) deb aytiladi. Bu yerda - rangi ga teng bo‘lgan eementar konyunktsiya.

Ma’lumki, dizyunktiv normal shakl ma’lum bir mantiq algebrasining funksiyasini realizatsiya etadi. Mantiq algebrasining har qanday funksiyasini DNSH ko‘rinishiga keltirish mumkinligini,

ya’ni

(3)

Bunday DNSH sifatida f funksiyaning mukammal dizyunktiv normal shaklini (MDNSH) olish mumkin, ya’ni

. .... . (4)



1-misol. funksiya quyidagi chinlik jadvali bilan berilgan bo‘lsin.

1-jadval

0 0 0	1	1 0 0	1
0 0 1	0	1 0 1	1
0 1 0	0	1 1 0	1
0 1 1	0	1 1 1	1

U vaqtda bu funksiyani quyidagi MDNSH ko‘rinishida ifodalash mumkin

.

Ikkinchi tarafdan, shu funksiyaning o‘zini

(6)

DNSH ko‘rinishida ham ifodalash mumkin.

Ushbu misol ko‘rsatayaptiki, bitta mantiq algebrasining funksiyasini bir nechta DNSH ko‘rinishida ifodalash mumkin.

Agarda bilan ko‘rinishlarini taqqoslasak, u holda ifodasida 15 o‘zgaruvchilar simvoli va 5 elementar konyunktsiya qatnashayotganligini; ifodasida bo‘lsa, 3 o‘zgaruvchilar simvoli va 2 elementar konyunktsiya qatnashayotganligini ko‘ramiz. Demak, formula o‘zgaruvchilar simvoli (elementar konyunktsiyalar) soniga nisbatan ga qaraganda soddaroq formula hisoblanadi.

Agarda va ko‘rinishlardagi funksiyani:

a) kontaktli sxema orqali realizatsiya etsak, u holda ni realizatsiya etish uchun 15 ta kontakt va ni realizatsiya etish uchun- 3 ta kontakt talab etiladi;

b) nultaktli funksional elementlardan yasalgan sxema orqali realizatsiya etsak, u vaqtda ni realizatsiya etish uchun 21 dona funksional element va ni realizatsiya etish uchun - 4 dona funksional element sarf bo‘ladi;

v) birtaktli funksional elementlardan yasalgan ko‘ptaktli to‘g‘ri sxema orqali realizatsiya etish talab etilsa, u holda ni realizatsiya etish uchun 33 funksional element, shu jumladan, 12 ta ushlab turish elementi va ni realizatsiya etish uchun - 6 ta, shu jumladan, 2 ta ushlab turish elementi kerak bo‘ladi (bu mulohazalarning chinligini isbotlashni o‘quvchiga havola etamiz).

Demak, ni realizatsiya etadigan sxemaning (qanday sxema bo‘lishidan qat’iy nazar) tannarxi ni realizatsiya etadigan sxemaning tannarxidan ancha qimmat (ustun) turadi.

Shuning uchun ham mantiq algebrasining funksiyalarini minimallashtirish muammosi (xalq xo‘jaligi uchun) katta amaliy ahamiyatga egadir.

Bu masalani hal etish uchun DNSH ni “murakkabligini” ifodalovchi soddalik indeksini kiritamiz.

funksional uchun qo‘yidagi aksiomalarning bajarilishini talab qilamiz: