MAVZU: PREDIKAT TUSHUNCHASI. PREDIKATLAR USTIDA MANTIQIY AMALLAR Reja: 1. Predikat tushunchasi. 2. Predikatning inkori. 3. Konyuksiya va dizyunksiya. Predikat tushunchasi. Mantiq algebrasida mulohazalar faqatgina chin yokiyolg‘on qiymat qabul qilishi nuqtai nazaridan qaralib, mulohazalarning strukturasiga ham, hattoki, mazmuniga ham e’tibor berilmaydi. Ammo fanda va amaliyotda mulohazalarning strukturasi va mazmunidan kelib chiqadigan xulosalardan (natijalardan) foydalaniladi. Masalan, «Har qanday romb parallelogrammdir;ABCD– romb; demak, ABCD– parallelogramm». Asos (shart) va xulosa mulohazalar mantiqining elementar mulohazalari bo‘ladi va ularni bu mantiq nuqtai nazaridan bo‘linmas, bir butun deb va ularning ichki strukturasini hisobga olmasdan qaraladi. Shunday qilib, mantiq algebrasi mantiqning muhim qismi bo‘lishiga qaramasdan, ko‘pgina fikrlarni tahlil qilishga qodir (yetarli) emas. Shuning uchun ham mulohazalar mantiqini kengaytirish masalasi vujudga keldi, ya’ni elementar mulohazalarning ichki strukturasini ham tadqiq eta oladigan mantiqiy sistemani yaratish muammosi paydo bo‘ldi. Bunday sistema mulohazalar mantiqini o‘zining bir qismi sifatida butunlay o‘z ichiga oladigan predikatlar mantiqidir. Predikatlar mantiqi an’anaviy formal mantiq singari elementar mulohazani subyekt va predikat qismlarga bo‘ladi. Subyekt – bu mulohazada biror narsa haqida nimadir tasdiqlaydi; predikat– bu subyektni tasdiqlash. Masalan, «5 – tub son» mulohazada «5» – subyekt, «tub son» – predikat. Bu mulohazada «5» «tub son bo‘lish» xususiyatiga ega ekanligi tasdiqlanadi. Agar keltirilgan mulohazada ma’lum 5 sonini natural sonlar to‘plamidagi x o‘zgaruvchi bilan almashtirsak, u holda «x– tub son» ko‘rinishidagi mulohaza formasiga (shakliga) ega bo‘lamiz. X o‘zgaruvchining ba’zi qiymatlari (masalan, x=13, x=3, x=19) uchun bu forma chin mulohazalar va x o‘zgaruvchining boshqa qiymatlari (masalan, x=10, x=20) uchun bu forma yolg‘on mulohazalar beradi. Ravshanki, bu forma bir (x) argumentli funksiyani aniqlaydi va bu funksiyaning aniqlanish sohasi natural sonlar to‘plami (N) hamda qiymatlar sohasi ( 0 , 1) to‘plam bo‘ladi. 1- t a ’ r i f . M to‘plamda aniqlangan va ( 0 , 1) to‘plamdan qiymat qabul P(x) funksiya bir joyli (bir o‘rinli) predikat deb ataladi. M to‘plamni P(x) predikatning aniqlanish sohasi deb aytamiz.P(x) predikat chin qiymat qabul qiluvchi hamma x=M elementlar to‘plamiga P(x)predikatning chinlik to‘plami deb ataladi, ya’ni P(x) predikatning chinlik to‘plami 1p= (x:x=M ,P ( x )=1) to‘plamdir. 2- t a ’ r i f . Agar M to‘plamda aniqlangan P(x) predikat uchun Ip=M(Ip=Ø) bo‘lsa, u aynan chin (aynan yolg‘on) predikat deb ataladi. Endi ko‘p joyli predikat tushunchasini o‘rganamiz. Ko‘p joyli predikat predmetlar orasidagi munosabatni aniqlaydi.«Kichik» munosabati ikki predmet orasidagi binar munosabatni ifodalaydi . «x<y » (bu yerda x,y=Z) binar munosabat ikki argumentli P(x,y) funksiyani ifodalaydi. Bu funksiya Z x Z to‘plamda aniqlangan va qiymatlar sohasi (1,0) to‘plam bo‘ladi. 3- t a ’ r i f . M=M1x M2 to‘plamda aniqlangan va (1,0) to‘plamdan qiymat oluvchi ikki argumentli P(x,y) funksiya ikki joyli predikat deb ataladi. Predikatlar ustida mantiqiy amallar. Predikatlar ham mulohazalar singari faqatgina chin yoki yolg‘on (1 yoki 0) qiymat qabul qilganliklari tufayli ular ustida mulohazalar mantiqidagi hamma mantiqiy amallarni bajarish mumkin.Bir joyli predikatlar misolida mulohazalar mantiqidagi mantiqiy amallarning predikatlarga tatbiq etilishini ko‘raylik. 4- t a ’ r i f . Berilgan M to‘plamda aniqlangan P(x) va Q(x) predikatlarning kon’yunksiyasi deb, faqat va faqat x=M qiymatlarda aniqlangan hamda P(x) va Q(x)lar bir vaqtda chin qiymat qabul qilgandagina chin qiymat qabul qilib, qo lgan barcha hollarda yolg‘on qiymat qabul qiluvchi yangi predikatga aytiladi va u P(x)^Q(x) kabi belgilanadi. 5- t a ’ r i f . Berilgan M to‘plamda aniqlangan P(x) va Q(x) predikatlarning diz’yunksiyasi deb, faqat va faqatgina x=M qiymatlarda aniqlangan hamda P(x) va Q(x) predikatlar yolg‘on qiymat qabul qilganda yolg‘on qiymat qabul qilib, qolgan barcha hollarda chin qiymat qabul qiluvchi yangi predikatga aytiladi va u P(x) v Q(x) kabi belgilanadi. P(x)vQ(x) predikatning chinlik sohasi IpUIQ to‘plamdan iborat bo‘ladi. 6- t a ’ r i f . Agar hamma x=M qiymatlarda P(x) predikat chin qiymat qabul qilganda yolg‘on qiymat va x=M ning barcha qiymatlarida P(x) predikat yolg‘on qiymat qabul qilganda chin qiymat qabul qiluvchi predikatga P(x) predikatning inkori deb ataladi va u Ṗ(x) kabi belgilanadi. Bu ta’rifdan Ip=M\Ip=CIp kelib chiqadi. 7- t a ’ r i f . Faqat va faqatgina x=M lar uchun bir vaqtda P(x) chin qiymat va Q(x) yolg‘on qiymat qabul qilganda yolg‘on qiymat qabul qilib, qolgan hamma hollarda chin qiymat qabul qiladigan P(x)→Q(x) predikat P(x) va Q(x) predikatlarning implikasiyasi deb ataladi. Har bir tayinlangan x=M uchun P(x)→Q(x)=Ṗ(x)vQ(x) teng kuchlilik to‘g‘ri bo‘lganligidan IP→Q=IṖUIQ=CIPUIQ o‘rinlidir. Xulosa: Predikat tushunchasi, ularning chinlik to’plamini aniqlash o’rganildi. Predikat tushunchasi. Predikatlar ustida mantiqiy amallar Asos (shart) va xulosa mulohazalar mantiqining elementar mulohazalari bo'ladi va ularni bu mantiq nuqtai nazaridan bo‘linmas, bir butun deb va ularning ichki tuzilishini hisobga olmasdan qaraladi. Shunday qilib, mantiq algebrasi mantiqning muhim qismi bo‘lishiga qaramasdan, ko‘pgina fikrlarni tahlil qilishga qodir (yetarli) emas. Shuning uchun ham mulohazalar mantiqini kengaytirish masalasi vujudga keldi, ya’ni elementar mulohazalarning ichki tuzilishini ham tadqiq eta oladigan mantiqiy sistemani yaratish muammosi paydo bo‘ldi. Bunday sistema mulohazalar mantiqini o'zining bir qismi sifatida butunlay o ‘z ichiga oladigan predikatlar mantiqidir. Predikatlar mantiqi an’anaviy formal mantiq singari elementar mulohazani subyekt va predikat qismlarga bo‘ladi. Subyekt — bu mulohazada biror narsa haqida nimanidir tasdiqlaydi; predikat - bu subyektni tasdiqlash. 1- ta ’rif. M to'plamda aniqlangan va {1,0} to ’plamdan qiymat qabul qiluvchi bir argumentli P(x) funksiya bir joyli (bir o'rinli) predikat deb ataladi. M to ‘plamni P(x) predikatning aniqlanish sohasi deb aytamiz. P(x) predikat chin qiymat qabul qiluvchi hamma x € M elementlar to’plamiga P(x) predikatning chinlik to ‘plami deb ataladi, ya’ni P(x) predikatning chinlik to ‘plami Ip = {x: x e M,P(x) = 1} to‘plamdir. 2- ta ’rif. Agar M to 'plamda aniqlangan P(x) predikat uchun I,, — M ( I p = 0 ) bo‘Isa, u aynan chin (aynan yolg‘on) predikat deb ataladi. Endi ko‘p joyli predikat tushunchasini o‘rganamiz. Ko‘p joyli predikat predmetlar orasidagi munosabatni aniqlaydi. 3- ta’rif. M — M lx M 1 to'plamda aniqlangan va {1,0} to'plamdan qiymat oluvchi ikki argumentli P(x,y ) funksiya ikki joyli predikat deb ataladi. n joyli predikat ham shunga o ‘xshash aniqlanadi. Predikatlar ustida mantiqiy amallar Predikatlar ham mulohazalar singari faqatgina chin yoki yolg'on (1 yoki 0) qiymat qabul qilganliklari tufayli ular ustida mulohazalar mantiqidagi hamma mantiqiy amallarni bajarish mumkin. Bir joyli predikatlar misolida mulohazalar mantiqidagi mantiqiy amallarning predikatlarga tatbiq etilishini ko‘raylik. 4- ta ’rif. Berilgan M to'plamda aniqlangan P{x) va Q(x) predikatlaming kon’yunksiyasi deb, faqat va faqat x € M qiymatlarda aniqlangan hamda P(x) va Q(x) lar bir vaqtda chin qiymat qabul qilgandagina chin qiymat qabul qilib, qolgan barcha hollarda yolg'on qiymat qabul qiluvchi yangi predikatga aytiladi va и P(x) ^ Q(x) kabi belgilanadi. P(x) ^ Q(x) predikatning chinlik sohasi to'plamdan, ya’ni P ( x ) va Q(x) predikatlar chinlik sohalarining umumiy qismidan iborat bo'ladi. 5- ta ’rif. Berilgan M to'plamda aniqlangan P(x) va Q{x) predikatlarning diz’yunksiyasi deb, faqat va faqatgina x e M qiymatlarda aniqlangan hamda P(x) va Q{x) predikatlar yolg'on qiymat qabul qilganda yolg'on qiymat qabul qilib, qolgan barcha hollarda chin qiymat qabul qiluvchi yangi predikatga aytiladi va и P(x) v Q(x) kabi belgilanadi. P(x) v Q(x) predikatning chinlik sohasi to‘plamdan iborat bo’ladi. 6- ta’rif. Agar hamma x e M qiymatlarda P(x) predikat chin qiymat qabul qilganda yolg'on qiymat va x e M ning barcha qiymatlarida P(x) predikat yolg'on qiymat qabul qilganda chin qiymat qabul qiluvchi predikatga P(x) predikatning inkori deb ataladi va u P(x) kabi belgilanadi. 7- ta ’rif. Faqat va faqatgina x e M lar uchun bir vaqtda P(x) chin qiymat va Q( x ) yolg'on qiymat qabul qilganda yolg'on qiymat qabul qilib, qolgan hamma hollarda chin qiymat qabul qiladigan P(x) —> Q(x) predikat P(x) va Q(x) predikatlarning implikatsiyasi deb ataladi. Har bir tayinlangan x e M uchun P(x) —> Q(x) = P(x) v Q(x) teng kuchlilik to‘g‘ri bo’lganligidan o ‘rinlidir. ************ Mulohazalar hisobi aksiomalari. Deduksiya teoremasi. Mulohazalar hisobida uch kategoriyali simvollardan iborat iborat alfabit qabul qilinadi: Birinchi kategoriya simvollari: Bu simvollar o’zgaruvchi deb ataladi. Ikkinchi kategoriya simvollari: bular mantiqiy bog’lovchilar. Uchinchi kategoriya qavs deb ataladigan (,) simvoli kiritiladi. Mulohazalr hisobida boshqa simvollar yo’q. Mulohazalar hisobining aksiomalar tizimi XI aksiomadan iborat bo’lib ular to’rt guruhga bo’linadi. Birinchi guruh aksiomalari: Ikkinchi guruh aksiomalari Uchinchi guruh aksiomalari: To’rtinchi guruh aksiomalari: Deduksiya teoremasi. Keltirib chiqarish qoidasi H va W mulohazalar hisobining ikkita formulalar majmuasi bo’lsin. H,W orqali majmualarning yig’indisini (birlashmasini belgilaymiz, ya’ni H,W=H∪W. Agar W majmua bitta C formuladan iborat bo’lganda ham H∪{C} birlashmani H, C ko’rinishida yozamiz. Keltirb chiqarishning asosiy qoidalari: V. Deduksiya teoremasi: Umumlashgan deduksiya teoremasi: VI.Konyuksiya kiritish qoidasi: VII. Dizyunksiyani kiritish qoidasi: H, C formulalar majmuasining har qanday keltirib chiqarish uchun ning to’g’riligini matematik induksiya metodidan foydalanib isbot qilish mumkin. *********** Umumiylik va mavjudlik kvantorlari to‘plamda aniqlangan predikat berilgan bo‘lsin. Agar ni predikatning x argumenti o‘rniga qo‘ysak, u holda bu predikat mulohazaga aylanadi. Umumiylik kvantori. to‘plamda aniqlangan predikat berilgan bo‘lsin. Har qanday uchun chin va aks holda yolg‘on qiymat qabul qiluvchi mulohaza ifodasini shaklda yozamiz. Bu mulohaza endi ga bog’liq bo’lmay qoladi va u quyidagicha o’qiladi: “har qanday uchun chin “. simvol umumiylik kvantori deb ataladi. Aytilgan fikrlarni matematik ifodalar orqali quyidagicha yozish mumkin: predikat ni erkin (ozod) o’zgaruvchi mulohazada ni umumiylik bilan bog’langan o’zgaruvchi deb ataladi. Mavjudlik kvantori. predikat to’plamda aniqlangan bo’lsin. Hech bo’lmaganda bitta uchun predikat chin va aks holda yolg’on qiymat qabul qiluvchi mulohaza ifodasini shaklda yozamiz. Bu mulohaza ga bog’liq emas va uni quyidagicha o’qish mumkin: “shunday mavjudki, ”, ya’ni simvol mavjudlik kvantori deb ataladi. mulohazada o’zgaruvchi kvantori bilan bog’langan bo’ladi. Misol: natural sonlar to’plamida predikat berilgan bo’lsin: “ – tub son” . Kvantorlardan foydalanib ushbu predikatdan quyidagi mulohazalarni hosil qilish mumkin: – “ Hamma natural sonlar tub sonlar bo’ladi ” ; – “Shunday natural son mavjudki, u tub son bo’ladi” . Ravshanki, birinchi mulohazo yolg’on va ikkinchi mulohaza chindir. ********* Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari. Biror alfavit berilgan bo'lsin. Bu alfavitdagi hamma so‘zlar to'plamini S bilan va S to‘plamning qism to'plamini M bilan belgilaymiz. t a ’ r i f . Agar x so'zning M to'plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo'lsa, u holda M rekursiv to‘plain deb ataladi. 2- t a ’ r i f . Agar M to ‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo ‘Isa, и holda M effektiv rekursiv sanaluvchi to ‘plam deb ataladi. Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari. 1- t e o r e m a . Agar M va L effektiv rekursiv sanaluvchi to 'plamlar bo ‘Isa, и holda va ham effektiv rekursiv sanaluvchi to 'plam bo'ladi. M va L effektiv rekursiv sanaluvchi to'plamlar bo'lsin. U holda, 2- ta’rifga asosan, ularning har biri uchun alohida algoritm mavjudki, ular orqali mos ravishda M va L dagi hamma elementlami sanab chiqish mumkin. va L to'plamlaming effektiv sanaluvchi algoritmi M va L to'plamlaming effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi. 2 - teorema (Post teoremasi). M to ‘plamning о‘zi va to‘Idiruvchisi C M effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to ‘plam rekursivdir. I s b o t i . a) M to‘plam va uning C M to'ldiruvchisi effektiv rekursiv sanaluvchi bo'lsin. U holda, 2- ta’rifga asosan, bu to‘plamlaming elementlarini sanab chiqa oladigan A va В algoritmlar mavjud bo'ladi. U holda M va C M to'plamlaming elementlarini sanab chiqish paytidalarning ro'yxatida x element uchraydi. Demak, shunday С algoritmyuzaga keladiki, u orqali Jt element M to'plamga qarashlimi yoki qarashli emasmi degan muammoni hal qilish mumkin. Shunday qilib, M rekursiv to‘plam bo'ladi. b) M rekursiv to‘plam bo'lsin. U holda, 1- ta’rifga asosan, x bu to'plamning elementimi yoki elementi emasmi degan muammoni hal qiluvchi algoritm mavjud bo‘ladi. Bu algoritmdan foydalanib, M va C M to‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib, M va C M to‘plamlar elementlarini sanab chiquvchi ikkita A va В algoritmni hosil qilamiz. Demak, M va C M to‘plamlar effektiv rekursiv sanaluvchi to‘plamlar bo'ladi. 3- t e o r e m a . Rekursiv bo ‘Imagan effektiv rekursiv sanaluvchi natural sonlar to 'plami mavjud. I s b o t i . Effektiv rekursiv sanaluvchi ixtiyoriy U natural sonlar to‘plami berilgan bo'lsin. U to'plamning rekursiv emasligini isbotlash uchun, Post teoremasiga (2- teorema) ko'ra, uning C U to'ldiruvchisi effektiv rekursiv sanaluvchi emasligini isbotlash yetarli. - hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar bo isin. Demak, har qanday (m,n) uchun to‘plamni tiklash mumkin. Endi U to‘plamning hamma elementlarini sanab chiqadigan A algoritmni kiritaylik. Bu algoritm (m , n) raqamli qadamda ni hisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda A algoritm uni U to‘plamga kiritadi, ya’ni . Bundan ko‘rinib turibdiki, har qanday rekursiv sanaluvchi to‘plamdan C U to‘plam hech boimaganda bitta element bilan farq qiladi, chunki C U shunday n elementlardan iboratki, . Shuning uchun ham C U rekursiv sanaluvchi to‘plam emas. Demak, Post teoremasiga asosan U rekursiv to‘plam boim aydi. I z о h . Isbot qilingan bu teorema aslida Gyodelning formal arifme-tika toiiqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan. ************ 3.3. Bul funksiyalarining o’zgaruvchilar bo’yicha yoyilmasi. Mukammal diz’yunktiv normal shakl. Mukammal kon’yunktiv normal shakl. funksiyani quyidagicha: o’zgaruvchilari bo’yicha yoyilmasi distributivlik qonunini qo’llab qavslarni ochamiz . Ю ning ‐darajasi natija olinadi. Misol: o’zgaruvchilari bo’yicha yoyilmasini toping. Yoyilma koeffisiyentlarini topamiz: ; ; ; Yoyilma koeffisiyentlarini formulaga qo’yamiz: (0,0, Z)xy(zZ)Ъ funksiyani ta o’zgaruvchilari bo’yicha yoyilmasi quyidagicha: ‐Mukammaldiz’yunktiv normal shakl. (MDNSh) ‐ Mukammal kon’yunktiv normal shakl. (MKNSh) Muammoli masala va topshiriqlar: 3.3.1. Berilgan bul funksiyalarini a) o’zgaruvchisi bo’yicha yoyilmasini toping; b) o’zgaruvchilari bo’yicha yoyilmasini toping: 1) ; 2) ; 3) ; Foydalanilgan adabiyotlar: 1.Boshlang’ich matematika kursi asoslari. L.P.Stoylova, A.M.Pishkalo “O’qituvchi” nashriyoti. 1991. 2.Boshlang’ich matematika nazariyasi va metodikasi. E.E.Jumayev, Turon istiqbol nashriyoti. 2009. 3.www.Ziyonet.uz internet sayti.