PREDIKAT TUSHUNCHASI. PREDIKATLAR USTIDA MANTIQIY AMALLAR

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. 

1. 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.