Predikatlar hisobida yechilish

1. 
   Predikatlar hisobida yechilish muammosi.
   

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 ushbu muammo mulohazalar algebrasi uchun oson yechilgan bo‘lsa, predikatlar mantiqi uchun bu muammoni yechish jarayonida katta qiyinchiliklar borligi aniqlandi. XX asrning 30- yillarida algoritm tushunchasiga aniq ta’rif berilgandan so‘ng mazkur muammo umumiy holda ijobiy hal etilishi mumkin emasligi, ya’ni izlangan algoritm mavjud emasligi aniqlandi. 1936 yilda 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.

2. 
   Predikatlar hisobida chekli sohalarda yechilish muammosi.
   

Chekli sohalarda yechilish muammosi. Yechilish muammosi chekli sohalarda ijobiy hal bo‘ladi. Haqiqatan ham, bu holda kvantorli amallarni kon’yunksiya va diz’yunksiya amallari bilan almashtirish mumkin. Natijada predikatlar mantiqi formulasi mulohazalar algebrasi formulasiga keltiriladi. Ma’lumki, mulohazalar algebrasi uchun yechilish muammosi ijobiy hal bo‘ladi.

Masalan,

xy[P(x, y)  P(x, x)]
formula
M  {a, b}
ikki elementli chekli sohada aniqlangan

bo‘lsin. U holda uni quyidagi ko‘rinishga keltirish mumkin:

xy[P(x, y)  P(x, x)]  x[P(x, a)  P(x, x)  P(x,b)] 

[P(a, a)  P(a, a)  P(a,b)][P(b, a)  P(b,b)  P(b,b)].

Hosil qilingan kon’yunktiv normal shakldagi formulaning har bir elementar diz’yunksiyasi ifodasida bitta mulohaza o‘zining inkori bilan birgalikda qatnashmoqda. Demak, mulohazalar algebrasining bu formulasi doimo chin qiymat qabul qiladi, ya’ni u aynan chindir.

3. 
   Tarkibida bir turdagi kvantor amali qatnashuvchi normal shakldagi formulalar uchun yechilish muammosi.
   
   1. 
      t a ’ r i f . Agar predikatlar mantiqi formulasi tarkibida erkin predmet o‘zgaruvchilar bo‘lmasa, u holda bunday formula yopiq formula deb ataladi.
      

2.