Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja

3 - misol. Tarkibida faqat bitta asosiy mantiqiy amal qatnashgan formulalarning mukammal normal sakllari (MKNShlari va MDNShlari) 1- jadvalda keltirilgan.

1- jadval
Amal	MKNSh	MDNSh
x	x	x
x  y	(x  y)  (x  y)  (x  y)	x  y
x  y	x  y	(x  y)  (x  y)  (x  y)
x  y	x  y	(x  y)  (x  y)  (x  y)
x  y	(x  y)  (x  y)	(x  y)  (x  y)

Yuqoridagi tasdiqning to‘g‘riligini tekshirish o‘quvchiga havola qilinadi.
1- jadvaldan ko‘rinib turubdiki, x formulaning MKNShi ham, MDNShi ham uning o‘zidan iborat; x  y formulaning MKNShida uchta ( x  y , x  y va x  y ) diz’yunktiv konstituyentlar bor,
uning MDNShi esa bitta kon’yunktiv konstituyentdan (shu formulaning o‘zidan) iborat; va hokazo. ■
1- teorema. Elementar mulohazalarning tavtologiyadan farqli ixtiyoriy formulasini MKNShga keltirish mumkin.
Teoremaning quyidagi konstruktiv i sboti tavtologiyadan farqli ixtiyoriy mantiqiy formulani
MKNShga keltirish algoritmi sifatida ishlatilishi mumkin.

• Berilgan formulani KNShga keltiramiz.

Buning uchun formulani faqat kon’yunksiya, diz’yunksiya va inkor mantiqiy amallari orqali ifodalaymiz (bunda inkor amali faqatgina o‘zgaruvchilarga nisbatan qo‘llanilgan bo‘lishi kerak). Formulani KNShga keltirish jarayonida, vaziyatga qarab, zarur qoida va qonunlardan foydalangan holda mumkin bo‘lgan soddalashtirishlarni bajaramiz.

• Agar KNSh ifodasida bittadan ko‘p bir xil elementar diz’yunksiyalar topilsa, u holda A  A  A teng kuchlilikdan foydalanib, ulardan faqat bittasini berilgan formulaning ifodasida qoldiramiz.
• Agar KNSh ifodasidagi barcha elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalar

bo‘lsa, u holda algoritmning 4- bandiga o‘tamiz, aks holda barcha elementar diz’yunksiyalarni to‘g‘ri elementar diz’yunksiyalarga aylantiramiz.
Buning uchun, vaziyatga qarab, quyidagi ikki jarayon qo‘llanilishi mumkin:

• agar biror elementar diz’yunksiya ifodasida birorta o‘zgaruvchi o‘zining inkori bilan birgalikda qatnashgan bo‘lsa, u holda x  x  J , A  J  A va J  A  A teng kuchliliklarga asosan bu elementar kon’yunksiyani KNSh ifodasidan olib tashlaymiz;
• agar qandaydir elementar diz’yunksiya ifodasida biror o‘zgaruvchi bir necha marta qatnashgan (barcha hollarda yo inkor ishorasi ostida yoki barcha hollarda inkor ishorasi ostida emas) bo‘lsa, u holda x  x  x teng kuchlilikka asosan ulardan faqatgina bittasini elementar diz’yunksiya ifodasida qoldiramiz.

Natijada, barcha elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalarga aylanadi.
4. Agar KNSh ifodasidagi barcha elementar diz’yunksiyalar to‘liq elementar diz’yunksiyalar bo‘lsa, u holda algoritmning 6- bandiga o‘tamiz, aks holda barcha elementar diz’yunksiyalarni to‘liq

elementar diz’yunksiyalarga aylantiramiz. Agar KNShdagi biror elementar diz’yunksiya to‘liq elementar diz’yunksiya bo‘lmasa, ya’ni biror diz’yunktiv had ifodasidagi elementar mulohazalardan ba’zilari (yoki ularning inkorlari) topilmasa, u holda bunday elementar diz’yunksiyani quyidagi usul yordamida to‘liq elementar diz’yunksiya holiga keltiramiz.
Masalan, tarkibida a, b, c,..., u, y,..., z elementar mulohazalalar ishtirok etgan, tavtologiyadan
farqli, F  a  b  c  ...  u  y  ...  z elementar diz’yunksiya ifodasida faqat x o‘zgaruvchi
yoki uning inkori x yo‘q deb faraz qilaylik. U holda x  x  J va A  J  A teng kuchliliklardan foydalanib F elementar diz’yunksiyani ikkita to‘liq elementar diz’yunksiyalar kon’yunksiyasiga keltiramiz:
F  (a  b  c  ...  u  y  ...  z)  (x  x) 
 (a  b  c  ...  u  x  y  ...  z) 
 (a  b  c  ...  u  x  y  ...  z).
Agar biror elementar diz’yunksiya ifodasida mta o‘zgaruvchilar qatnashmayotgan bo‘lsa, u holda bu jarayonni har bir o‘zgaruvchi uchun (ya’ni, m marta) yoki mta o‘zgaruvchilar uchun birdaniga qo‘llash natijasida bitta to‘liq bo‘lmagan elementar diz’yunksiya o‘rnida unga teng kuchli 2m ta to‘liq elementar diz’yunksiyalar kon’yunksiyalariga ega bo‘lamiz.

• Agar 4- band bajarilishi natijasida KNSh ifodasida bir xil elementar diz’yunksiyalar paydo bo‘lsa, u holda algoritmning 2- bandiga o‘tamiz.
• Algoritm tugadi.

Demak, formulani MKNShga keltirish algoritmini qo‘llash natijasida berilgan KNSh ifodasida bir xil elementar diz’yunksiyalar qatnashmaydi va barcha elementar diz’yunksiyalar to‘g‘ri va to‘liq bo‘ladi. 1- ta’rifga asosan bunday KNSh MKNShdir. ■