11-§. Predikat tushunchasi. Predikatlar ustida mantiqiy amallar. Umumiylik va mavjudlik kvantorlari Predikat tushunchasi

13.8-misol. formulaning aynan yolg‘on formula ekanligini ko‘rsatamiz. o‘rinli va formula aynan yolg‘on formula bo‘lgani uchun ham aynan yolg‘on formuladir.


Mustaqil bajarish uchun muammoli masala va topshiriqlar

1. 
   Quyidagi teng kuchliliklarning to‘g‘riligini isbot qiling:
   

a) ; b) ;
d) ; e) ;
f) ;
g) ;
h) ;
i) ;
j) ;
k) ;
l) .

2. 
   Quyida keltirilgan formulalarni normal shaklga keltiring.
   

a) ;
b) ;
d) ;
e) ;
f) ;
g) ;
h) ;
i) ;
j) ;
k) ;
l) ;
m) ;
n) ;
o) ;
p) ;
q) ;
r) .


14-§. Pridikatlar mantiqida yechilish muammosi. Xususiy hollarda formulaning umumqiymatliligini aniqlash algoritmlari.


Yechilish muammosi. Predikatlar mantiqida yechilish muammosi mulohazalar algebrasida qanday qo‘yilgan bo‘lsa, xuddi shunday qo‘yiladi: predikatlar mantiqining istalgan formulasi yo umumqiymatli, yo bajariluvchi, yoki aynan yolg‘on (bajarilmas) formula ekanligini aniqlab beruvchi algoritm mavjudmi yoki yo‘qmi? Bu masala yechilish muammosi deb ataladi. Agar bunday algoritm mavjud bo‘lsa edi, u (xuddi mulohazalar algebrasidagidek) predikatlar mantiqidagi istalgan formulani aynan chinligini aniqlab beruvchi kriteriyga keltirilgan bo‘lar edi.
1936 yilda AQShlik olim A. Chyorch predikatlar mantiqining yechilish muammosi umumiy holda algoritmik yechilmasligini isbotladi, ya’ni predikatlar mantiqining istalgan formulasi qaysi formulalar (umumqiymatli, bajariluvchi yoki bajarilmas) sinfiga kirishini aniqlab beradigan algoritm mavjud emasligini isbotladi.
Yechilish muammosi predikatlar mantiqi uchun ijobiy hal etilmasada, predikatlar mantiqi formulalarining ba’zi sohalari uchun bu muammo ijobiy hal bo‘lishi mumkin. Quyida shunday sohalardan ba’zilarini o‘rganamiz.