Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh

Reja:

1. 
   Masalaning qo‘yilishi.
   

2. Diz’yunktiv normal shaklni soddalashtirish va tupikli DNSh.

3. 
   Minimallashtirish masalasining geometrik tarzda qo‘yilishi.
   

4. Joiz (ruxsat etilgan) kon’yunksiyalar.

5. 
   Qisqartirilgan diz’yunktiv normal shakl.
   

1. Masalaning qo‘yilishi

1. 
   Mantiq algebrasining funksiyalarini minimallashtirish muammosining dolzarbligi. Xalq xo‘jaligi uchun muhim amaliy ahamiyatga ega bo‘lgan ko‘pchilik masalalarni hal qilishda mantiq algebrasidan foydalanish mumkin. Quyida shunday masalalardan biri mantiq algebrasining funksiyalarini minimallashtirish muammosi sifatida qaralgan.
   

1.1-t a ’ r i f . Ushbu

^{K  x1  x2 ... xr} (   bo‘lganda i  i
) (1)

i₁ i₂ i_r  
ifoda elementar kon’yunksiya deb ataladi. r son elementar kon’yunksiyaning rangi deyiladi. Konstanta 1 ni rangi 0 ga teng bo‘lgan elementar kon’yunksiya deb hisoblaymiz.
1.2-t a ’ r i f . Ushbu

s

i
D   K (i 
i1
j bo'lganda K_i  K _j )
(2)

ifoda diz’yunktiv normal shakl (DNSh) deb ataladi, bu yerda bo‘lgan eyementar kon’yunksiya.
K_i – rangi i ga teng

Ma’lumki, D diz’yunktiv normal shakl mantiq algebrasining ma’lum bir
f (x₁, x₂ ,..., x_n ) funksiyasini realizatsiya qiladi va mantiq algebrasining berilgan
funksiyasi bir nechta DNSh ko‘rinishida ifodalanishi mumkin. Mantiq algebrasining

har qanday
f (x₁, x₂ ,..., x_n )
( f  0)
funksiyasini DNSh ko‘rinishiga keltirish

mumkinligini, ya’ni


D  f (x₁, x₂ ,..., x_n )

(3)

Bunday DNSh sifatida f funksiyaning mukammal diz’yunktiv normal shaklini (MDNSh) olish mumkin, ya’ni

D   x^1 x^{ 2} ...x^{ n} . (4)
(₁ , ₂ ,..., _n ) ^{1 2 n}
f (₁ , ₂ ,..., _n )1

1.1-m i s o l .

f (x₁ , x₂ , x₃ )
funksiya 1.1-chinlik jadvali bilan berilgan bo‘lsin.

1.1-jadval
x1	x2	x3	f (x1 , x2 , x3 )	x1	x2	x3	f (x1 , x2 , x3 )
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 holda
f (x₁ , x₂ , x₃ )
funksiya


D₁  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃

(5)

MDNSh ko‘rinishida ifodalanishi mumkin.
Ikkinchi tarafdan, shu funksiyaning o‘zini

DNSh ko‘rinishida ham ifodalash mumkin.

D₂  x₂ x₃  x₁
(6)

Agar
D₁ bilan D₂
ko‘rinishlarini taqqoslasak, u holda
D₁ ifodasida 15ta

o‘zgaruvchi simvollari va 5ta elementar kon’yunksiyalar qatnashayotganligini, D₂
ifodasida esa, 3ta o‘zgaruvchi simvollari va 2ta elementar kon’yunksiyalar

qatnashayotganligini ko‘ramiz. Demak,
D₂ formula o‘zgaruvchilar simvoli

(elementar kon’yunksiyalar) soniga nisbatan formula hisoblanadi.
D₁ DNShga qaraganda soddaroq

Agar
D₁ va D₂
ko‘rinishdagi funksiyani:

1. 
   kontaktli sxema orqali realizatsiya qilsak, u holda
   

D₁ DNShni realizatsiya

qilish uchun 15ta kontakt, D₂
qilinadi;
DNShni realizatsiya qilish uchun esa 3ta kontakt talab

2. 
   nol taktli funksional elementlardan yasalgan sxema orqali realizatsiya
   

qilsak, u holda
D₁ ni realizatsiya qilish uchun 21 dona funksional element va
D₂ ni

realizatsiya qilish uchun 4 dona funksional element sarf bo‘ladi;
d) bir taktli funksional elementlardan yasalgan ko‘p taktli to‘g‘ri sxema orqali

realizatsiya qilish talab qilinsa, u holda
D₁ ni realizatsiya qilish uchun 33 dona

funksional element, shu jumladan, 12 dona ushlab turish elementi va
D₂ ni

realizatsiya qilish uchun 6 dona, shu jumladan, 2 dona ushlab turish elementi kerak bo‘ladi.

Demak,
D₁ DNShni realizatsiya qiladigan sxemaning (qanday sxema

bo‘lishidan qat’iy nazar) tannarxi
D₂ DNShni realizatsiya qiladigan sxemaning

tannarxidan ancha qimmat (ortiq) turadi. ■
1.1-misoldan ko‘rinib turibdiki, mantiq algebrasining funksiyalarini minimallashtirish muammosi ko‘pchilik hollarda (jumladan, xalq xo‘jaligi uchun) katta amaliy ahamiyatga egadir.

Bu masalani hal qilish uchun DNShning “murakkabligini” ifodalovchi
soddalik indeksi tushunchasini kiritamiz.
L(D)

L(D)
funksional uchun quyidagi aksiomalarning bajarilishini talab qilamiz.

1. 
   Manfiy emasligi haqidagi aksioma. Har qanday DNSh uchun L(D)  0 .
   
2. 
   Monotonligi haqidagi aksioma (ko‘paytmaga nisbatan). Agar
   

i
D  D¹  x^i K¹
bo‘lsa, u holda


L(D)  L(D¹  K¹) . (7)

3. 
   Qavariqligi haqidagi aksioma (qo‘shishga nisbatan). Agar D  D₁  D₂
   

va D₁  D₂  0
bo‘lsa, u holda


L(D)  L(D₁)  L(D₂ ) . (8)

4. 
   Invariantlik haqidagi aksioma (izomorfizmga nisbatan). Agar R¹ DNSh
   

R DNShdan o‘zgaruvchilarni qayta nomlash (aynan tenglashtirishsiz) usuli bilan
hosil qilingan bo‘lsa, u holda L(D¹ )  L(D).
Diz’yunktiv normal shakllar uchun soddalik indekslari deb ataluvchi quyidagi belgilashlarni kiritamiz.

1. 
   L_h (D)
   
2. 
   L_k (D)
   
3. 
   L_i (D)
   

• 
  berilgan D DNShdagi o‘zgaruvchilar harflarining soni.
  
• 
  berilgan D DNShdagi elementar kon’yunksiyalar soni.
  
• 
  berilgan D DNShdagi inkor (  ) simvollari soni.
  

L_h (D) ,
L_k (D) va
L_i (D)
indekslar yuqorida keltirilgan aksiomalarni

qanoatlantiradi.
1.2-m i s o l . 1.1-misoldagi


D₁ va D₂

DNShlar berilgan bo‘lsin. Ravshanki,

L_h (D₁)  15 va
^{Lh (D2 )  3} , ya’ni D₂
DNSh o‘zgaruvchilar harflarining soni indeksiga

nisbatan
D₁ DNShga qaraganda soddaroqdir.
D₁ va D₂
DNShlar uchun
L_k (D₁)  5 va

L_k (D₂ )  2
bo‘lgani uchun D₂
DNSh elementar kon’yunksiyalar soni indeksiga

nisbatan ham
D₁ DNShga qaraganda soddaroqdir.
L_i (D₁)  6 va
^L_i ^{(D2 )  2} , ya’ni D₂

DNSh inkor simvollari soni indeksi uchun ham
■
D₁ DNShga nisbatan soddaroq ekan.

Ma’lumki,
{x₁ , x₂
,..., x_n }
o‘zgaruvchilar to‘plamidan
³ⁿ ta elementar

kon’yunksiya tuzish mumkin (“bo‘sh” kon’yunksiyaga 1 konstanta mos qilib

qo‘yilgan). Bundan o‘z navbatida
{x₁ , x₂
,..., x_n }
to‘plam elementlaridan
2³n ta

diz’yunktiv normal shakl tuzish mumkinligi kelib chiqadi.

1.3-t a ’ r i f . Agar

f (x₁, x₂ ,..., x_n )
funksiyani realizatsiya qiluvchi DNSh
L(D)

indeksga nisbatan minimal bo‘lsa, u holda bunday DNSh L ga nisbatan minimal
DNSh, L_k indeksga nisbatan minimal bo‘lgan DNSh eng qisqa diz’yunktiv normal
shakl deb ataladi.

Bundan keyin L_h indeksga nisbatan minimal bo‘lgan DNShni minimal

diz’yunktiv shakl deb ataymiz.
1.3-m i s o l . 1.1-misoldagi


D₁ va D₂

DNShlarni tahlil qilamiz. D₂

DNSh

minimal DNShdir, chunki ushbu DNSh orqali ifodalangan
f (x₁ , x₂ , x₃ )
funksiyaning

x₁ , x₂ , x₃ argumentlari muhim (soxta emas) argumentlardir. Shuning uchun uni
uchtadan kam harf bilan ifodalash mumkin emas.

D₂
f (x₁ , x₂ , x₃ )
DNSh eng qisqa DNShdir, chunki ushbu DNSh bilan ifodalangan funksiya har qanday elementar kon’yunksiyadan farq qiladi.

D₂ DNSh L_i
indeksga nisbatan ham minimal DNShdir, chunki ushbu DNSh

bilan ifodalangan
f (x₁ , x₂ , x₃ )
funksiya
x₂ va
x₃ o‘zgaruvchilari bo‘yicha o‘suvchi

funksiya emas va demak, uni ikkita inkordan kam inkor qatnashgan DNSh ko‘rinishida ifodalash mumkin. ■
Shunday qilib, asosiy muammo matematik mantiqning ixtiyoriy f (x₁, x₂ ,..., x_n )
funksiyasi uchun L indeksga nisbatan minimal diz’yunktiv normal shaklni topishdan iboratdir. Bu muammo matematik mantiq funksiyalarini minimallashtirish muammosi deb ataladi.

2.