7-ma'ruza. Sun’iy intellektda mantiqiy xulosalashlar Reja

3. Birinchi tartibli predikatlar mantiqi

Mulohazalar mantiqida faktlarni belgilashda "1" yoki "0" ("ha" yoki "yo’q") qiymatlar qabul qiluvchi va strukturalarga ega bo’lmagan harflar(ism yoki identifikator)dan foydalaladi. Predikatlar mantiqida faktlar n-joyli mantiqiy funksiyalar-predikatlar bilan belgilanadi. Bu erda F-predikat (funktor) va -predikatning argumentlari. Predikatlar nomi atomlar deb ham ataladi. Argumentlar atomlar yoki funksiylar bo’lishi mumkin. Bu erda f-funksiya nomi, -xuddi predikatlar argumentlari kabi predmet soha o’zgaruvchilari yoki o’zgarmaslari hisoblanadi. Predikatni izohlash (boshqacha aytganda, aniqlashtirish) natijasida funktorlar va argumentlar predmet sohadan (qatorlar, sonlar, strukturalar va h.k.) o’zgarmas qiymatlar qabul qiladi. Bunda predmet sohani (dasturlar ba bilimlar bazalarini yaratish) tavsiflash bosqichini va masalani echish (bilimlar bazalarini to’g’rilash yo’ki to’ldirish maqsadida dasturlarni bajarish) bosqichini izohlashning farqiga borish kerak. Bundan keyin biz predikatlar bilan ishlashda birinchi bosqichdagi izohlashlar natijalarini, ya’ni ba’zi predmet sohani tavsiflashni e’tiborga olamiz [1,4].

(n > 1)-joyli predikatdan bilimlar injeneriyasida n ta mohiyatlar (obyektlar)-predikar argumentlarni bir-biri bilan ozaro bo’g’laydigan n-joyli munosabatlarni tasvirlash uchun foydalaniladi.
Misol. Ota ("Farrux", "Zarrux Farruxovich") predikat "Farrux" va "Zarrux Farruxovich" mohiyatlar qarindoshlik munosabatlari bilan bog’langanligini anglatadi, chunonchi, Farrux Zarruxning otasi yoki Zarrux Farruxning o’g’li hisoblanadi.
Misol. Kompyuter (xotira, klaviatura, protsessor, monitor) predikat kompyuterning tarkibiy qismlari "компьютер" tushunchasi-munosabati bilan bir-biri bilan bo’g’langanligini anglataadi.
(п=1)-joyli predikat predikat nomi bilan belgilangan obyektning argumenti yoki xarakteristikasini belgilovchi mohiyat (obyekt) xususiyatini ifodalaydi.
Misol. G’ishtli (uy), baho (5), ko’cha ("Amir Temur"), tug’ilgan kun ("20 noyabr 1958 y."), Imtihon ("Sun’iy intellekt").
(n=0)- joyli predikat (argumentlarsiz) barcha predmet sohaga taalluqli hodisa, belgi yoki xususiyatni anglatishi mumkin. Masalan, "ishning tugashi", "darsning boshlanishi", "daryoning oqishi", "soatning yurishi".
Misol. Ifoda

predmet sohadagi barcha x,y,z qiymatlar uchun quyidagi tasdiqni bildiradi
"Agar x ning otasi- y va onasi-z bo’lsa, u holda y va z – x ning ota-onasi bo’ladi;
Misol. Ifoda

mavjud x qiymatlar uchun quyidagi tasdiqni bildiradi: injener lavozimida ishlayotgan kamida bitta talaba mavjud.
Ozod o’zgaruvchilardan farqli ravishda kvantorlarda qatnashayotgan o’zgaruvchilar bog’langan o’zgaruvchilar deyiladi. Masalan,

Ifodada х – bog’langan o’zgaruvchi, y – ozod o’zgaruvchi.
1- tartibli mantiqiy predikatlarning yuqori tartibli predikatlardan farqi shundaki, ularda predikatlar argumenti sifatida ifodalardan (formulalardan)foydalanish ta’qiqlanadi.
Predikatlar mantiqida masalani echish ma’lum tasdiqlar (formulalar) yoki aksiomalardan foydalanib formulalar yoki predikatlar korinishidagi maqsadli tasdiqlarni isbotlashga keltiriladi.
1960-yillarning oxirida predikatlar mantiqida Robinson tomonidan "teskaridan" isbotlashga asoslangan rezolyutsiyalar usuli taklif qilindi. Bunga ko’ra maqsadli tasdiq инвертируется va aksiomalar to’plamiga qo’shiladi, ushbu yo’l bilan hosil qilingan tasdiqlar to’plamining birgalikdamasligi (qarama-qarshi ekanligi) isbotlanadi. Rezolyutsiyalar usuli bilan isbotlashni bajarish uchun tasdiqlar to’plami ustuda ba’zi almashtirishlarni bajarish talab etiladi, xususan, ular takomil konyunktiv normal shaklga (TKNSh) keltiriladi.
Formulalarni EHMda engil ifodalanadigan TKNSh ga keltirish quyidagi bosqichlardan iborat [1, 4]:
1. Implikatsiyalar qatnashgan formulalarni inkor va dizyunksiy qatnashadigan formulalarga hamda kvantorli formulalar ustida kelgan inkorlardan kvantor amallarini ozod qilish tengkuchliliklari yordamida almashtirishlar amalga oshiriladi:





2. O’zgaruvchilarni standartlashtirish yoki o’zgaruvchilarni ajratish amalga oshiriladi:
16.
17.
18.
19.
Bu erda y o’zgaruvchi B formulaga taalluqli emas deb qaraladi.
20.  X
bu erda y o’zgaruvchi A (x) va B (x) formulalarga taalluqli emas,



bu erda y o’zgaruvchi A (x) va B (x) formulalarga taalluqli emas.
Bu bosqichda har bir formulada bog’liq o’zgaruvchilar shunday qayta nomlanadiki, kvantorlar bilan bog’langan oz’garuvchilar har bir kvantor uchun yagona o’zgaruvchilarga aylanadi. Bu shunday fakt asosida amalga oshiriladiki, bunda bog’liq o’zgaruvchilar kvantor doirasida formulaning chinligini o’zgartimaydigan va formulada qatnashmagan boshqa o’zgaruvchiga almashtiriladi.
Masalan, ifoda
ifodaga almashtiriladi.
3. Mavjudlik kvantorlarini yo’qotish. Bu bosqichda mavjudlik kvantorlari g(x) deb ataladigan Skolema funksiyasi yoki argumentli predkatlarni o'tkazish (hisoblash), ya’ni o’zgaruvchi-argumentning aniqlanish sohasidagi o’zgarmaslar bilan almashtiriladi.
16-20 tengkuchliliklar predikatlar mantiqining ixtiyoriy formulasini quyidagi ko’rinishga almashtiradi:

bu erda ixtiyoriy Q_i- bu umumiylik kvantori yoki mavjudlik kvantori, – kvantorlarni saqlamovchi formula. Bunday ko’rinishdagi formulaga skolemli o’zgarmaslarni va funksiyalarni kiritish bilan barcha mavjudlik kvantorlarini yo’qotish mumkin. Buning uchun predikatlar mantiqining quyidagi qonunlaridan foydalanish mumkin:
21.
bu erda Q₁, …, Q_m- ixtiyoriy kvantorlar, a - o’zgarmas simvol formulaning boshida turgan ( ) ifodasiga mos keluvchi shunday o’zgarmaslar sifatida alfavitga kiritiladi va a - o’zgarmas simvol skolemli o’zgarmas deb ataladi.
22.
где , …, - ixtiyoriy kvantorlar, k-joyli funksionalli simvol f formulaning boshida turgan ifodasiga mos keluvchi shunday funksiya sifatida alfavitga kiritiladi va - funksiya skolemli fuksiya deb ataladi.
23. ∃xA(x)≡A(a), bu erda a - skolemli o’zgarmas.
Almashtirishlarga misollar:
Boshlang’ich formula Natijaviy formula



bu erda a va b – o’zgarmaslar. Skolema funksiyasi mavjudlik kvantori bilan bog’langan o’zgaruvchilarning aniqlanish sohasini boshqa o’zgaruvchilarning aniqlanish sohasiga akslantirishni amalga oshiradi.
4. Umumiylik kvantorlarini formulaning boshiga chiqarish.
16-23 qonunlar skolemli shakldagi ixtiyoriy predikatlar mantiqi formulalarini almashtirishni ta’minlaydi. Quyidagi ko’rinshdagi formula shunday ataladi

Bu erda A formula o’zida umuman kvantorlarni saqlamaydi, faqat o’zgaruvchilar, o’zgarmaslar, skolema o’zgarmaslari va funksiyalarni saqlaydi. A formula KNF dan iborat skolema shakli kauzal shakl deyiladi. Kauzal shakl quyidagi umumiy ko’rinishga ega:

Bu erda - diyunktlarni klauzalar yoki gaplar deb atashadi.
5. Umumiylik kvantorlarini yo’qotish. Agar formulada biror x o’zgaruvchi bo’lsa, u holda uning aniqlanish sohasidagi barcha qiymatlarida formular o’rinli degan nuqtai-nazaridan kvantorlarni olib tahlash orqali amalga oshiriladi.