Iv-bob. Predikatlar mantiqi

4-misol. tengkuchlilik o’rinli ekanligini ko’rsating.
Yechim. ,
.
Demak, keltirilgan tengkuchlilik o’rinli ekan.


4-§. Predikatlar mantiqi formulasining normal shakli. Bajariluvchi va umumqiymatli formulalar
Formulaning deyarli normal shakli. Formulaning normal shakli. Har qanday formulani normal shaklga keltirish. Bajariluvchi formulalar. Umumqiymatli formulalar.  Aynan chin formula. Aynan yolg’on formula. Mantiq qonuni. Umumqiymatli va bajariluvchi formulalar haqidagi teoremalar.


4.1. Predikatlar mantiqi formulasining normal shakli


1-ta’rif. Agar predikatlar mantiqi formulasi ifodasida faqat inkor, kon’yunksiya, diz’yunksiya amallari va kvantorli amallar qatnashib, inkor amali elementar formulalarga (predmet o’zgaruvchilar va o’zgaruvchi predikatlarga) tegishli bo’lsa, bunday formula deyarli normal shaklda deyiladi.
Ravshanki, predikatlar mantiqi va mulohazalar algebrasidagi asosiy tengkuchliliklardan foydalanib, predikatlar mantiqining har bir formulasini deyarli normal shaklga keltirish mumkin. Masalan,

formulani deyarli normal shaklga keltiraylik.


Demak,
.
Predikatlar mantiqining deyarli normal shakldagi formulalari orasida normal shakldagi formulalari muhim rol o’ynaydi.
Bu formulalarda kvantorli amallar yoki butunlay qatnashmaydi, yoki ular mulohazalar algebrasining hamma amallaridan keyin bajariladi, ya’ni normal shakldagi formula quyidagi ko’rinishda bo’ladi:
, ,
bunda simvoli o’rniga yoki kvantorlarning biri tushuniladi va formula ifodasida kvantorlar bo’lmaydi.
1-teorema. Predikatlar mantiqining har qanday formulasini normal shaklga keltirish mumkin.
Isbot. Formula deyarli normal shaklga keltirilgan deb hisoblaymiz va uni normal shaklga keltirish mumkinligini ko’rsatamiz.
Agar bu formula elementar formula bo’lsa, u holda uning ifodasida kvantorlar bo’lmaydi va, demak, u normal shakl ko’rinishida bo’ladi.
Endi faraz qilamizki, teorema ko’pi bilan amalni qamragan formula uchun to’g’ri bo’lsin va uni shu faraz asosida amalni qamragan formula uchun isbot qilamiz.
amalni o’z ichiga olgan formula va uning ko’rinishi shaklda bo’lsin. Bu yerda kvantorlarning birini ifodalaydi.
formula amalni o’z ichiga olganligi tufayli uni normal shaklga keltirilgan deb hisoblaymiz. U vaqtda formula ta’rifga asosan normal shaklda bo’ladi.
formula ko’rinishda bo’lsin, bunda formula normal shaklga keltirilgan va amalni o’z ichiga olgan deb hisoblanadi. U holda
va
tengkuchliliklardan foydalanib, inkor amalini predikatlar ustiga tushiramiz. Natijada formulani normal shaklga keltirgan bo’lamiz.
Endi formula ko’rinishda bo’lsin. Bu yerda va lar normal shaklga keltirilgan formulalar deb qaraladi.
formulada bog’langan predmet o’zgaruvchilarni shunday qayta nomlaymizki, va formulalardagi hamma bog’langan predmet o’zgaruvchilar har xil bo’lsin. U vaqtda va formulalarni quyidagi ko’rinishda yozish mumkin:
, ,
, .
va
tengkuchliliklardan foydalanib, formulani kvantor amallari ostiga kiritamiz, ya’ni formulani ushbu ko’rinishga keltiramiz:
.
So’ngra formulani

kvantor amallari ostiga kiritamiz. Natijada formulaning normal shaklini hosil qilamiz:
.
ko’rinishidagi formulani normal shaklga keltirishning isboti xuddi yuqorida kabi bo’ladi.
Agar formulani normal shaklga keltirish jarayonida yoki ko’rinishdagi ifodalarni ko’rishga to’g’ri kelsa, u holda
va
tengkuchliliklardan foydalanish kerak bo’ladi.