Mavzu: predikatlar mantiqi formulasining normal shakli. Bajaruvchi va umumqiymatli formulalar

BUXORO DAVLAT UNIVERSITETI

FIZIKA-MATEMATIKA FAKULTETI MATEMATIKA YO’NALISHI

068 -GURUH TALABASI QURBONOVA GULHAYONING


KURS ISHI
DISKRET MATEMATIKA VA MATEMATIK MANTIQ FANIDAN

MAVZU: PREDIKATLAR MANTIQI FORMULASINING NORMAL SHAKLI. BAJARUVCHI VA UMUMQIYMATLI FORMULALAR

Topshirdi:___________________

Qabul qildi:__________________

Buxoro -2020
REJA:

1. 
   KIRISH
   
2. 
   ASOSIY QISM
   
   1. 
      Predikatlar haqida tushuncha.
      
   2. 
      Predikatlar mantiqi Formulasining normal shakli.
      
   3. 
      Bajariluvchi va umumqiymatli formulalar.
      
   4. 
      Bajaruvchi va umumqiymatli formulalarga doir misollar
      
3. 
   FOYDALANGAN ADABIYOTLAR
   
4. 
   XULOSA
   

1.KIRISH

Predikatlar ustida mantiqiy amallar, umumiylik va mavjudlik kvantorlari. predikatlar mantiqining formulasi va uning qiymati, predikatlar mantiqining teng kiichli formulalari, predikatlar mantiqi formulasining normal shakli, bajariluvchi va umumqiymatli formulalar, yechilish muammosi, xususiy hollarda formulaninyn tmum- qiymatliligini topish algoritmlari, predikatlar mantiqining mateniatikaqa tadbiqi, aksiomatik predikatlar hisobi haqida ma’lumotlar keltiriladi.

Predikat tushunchasi. Mantiq algebrasida mulohaxalar faqatgina chin yoki yolg‘‹in qiymat qabul qilishi nuqtai nazaridan qaralib, mulohazalarning tuzilishiga ham, hattoki, mazmuniga ham e’tibor berilmaydi. Ammo fanda va arnaliyotda mulohazalarning tuzil ishi va mazmunidan kelib chiqadigan xulosalardan (natijalardan) foydalaniladi. Masalan, «Har qanday romb parallclogrammdir; ABCD — romb; demak, ABCD — parallelogramm».

Asos (shart) va xulosa mulohazalar mantiqining elementar mulohazalari bo‘ladi va ulami bu mantiq nuqtai nazaridan bo‘linmas, bir butun deb va ularning ichki tuzilishini hisobga olmasdan qaraladi. Shtinday qilib, iuantiq 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 eleinentar mulohazani subyekt va predikat qismlarga bo‘ladi.

Subyekt — bu mulohazada biror narsa haqida nimanidir tasdiqlaydi;

predikat — bu subyektni tasdiqlash.

Masalan, «5 — tub son» mulohazada «5» — subyekt, «tub son» — predikat. Bu mulohazada «5» «tub son bo‘1ish» xususiyatiga ega ekanligi tasdiqlanadi

2.1 PREDIKAT HAQIDA TUSHUNCHA
Mantiq algebrasida mulohazalar faqatgina chin yoki yolg‘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 {1, 0} to‘plam bo‘ladi.

1- t a ’ r i f . M to‘plamda aniqlangan va to‘plamdan qiymat qabul qiluvchi bir argumentli Ρ(x) funksiya bir joyli (bir o‘rinli) predikat deb ataladi.

M to‘plamni Ρ(x) predikatning aniqlanish sohasi deb aytamiz.

Ρ(x) predikat chin qiymat qabul qiluvchi hamma x M elementlar to‘plamiga Ρ(x) predikatning chinlik to‘plami deb ataladi, ya’ni Ρ(x) predikatning chinlik to‘plami I_P {x : x M , P(x) 1} to‘plamdir.

2- t a ’ r i f . Agar M to‘plamda aniqlangan Ρ(x) predikat uchun I _P M

( I _P ) 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 Ρ(x, y) funksiyani ifodalaydi. Bu funksiya Z Z to‘plamda aniqlangan va qiymatlar sohasi to‘plam bo‘ladi.

3- t a ’ r i f . M M₁ M ₂ to‘plamda aniqlangan va to‘plamdan qiymat oluvchi ikki argumentli Ρ(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 Ρ(x) va Q(x) predikatlarning kon’yunksiyasi deb, faqat va faqat x M qiymatlarda aniqlangan hamda Ρ(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 u Ρ(x) Q(x) kabi belgilanadi.

5- t a ’ r i f . Berilgan M to‘plamda aniqlangan Ρ(x) va Q(x) predikatlarning diz’yunksiyasi deb, faqat va faqatgina x M qiymatlarda aniqlangan hamda Ρ(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 Ρ(x) Q(x) kabi belgilanadi.

Ρ(x) Q(x) predikatning chinlik sohasi I _P I_Q to‘plamdan iborat bo‘ladi.

6- t a ’ r i f . Agar hamma x M qiymatlarda Ρ(x) predikat chin qiymat qabulqilganda yolg‘on qiymat va x M ning barcha qiymatlarida Ρ(x) predikat yolg‘on qiymat qabul qilganda chin qiymat qabul qiluvchi predikatga Ρ(x) predikatning inkori deb ataladi va u Ρ (x) kabi belgilanadi.

Bu ta’rifdan I _P M \ I _P CI _P kelib chiqadi.

7- t a ’ r i f . Faqat va faqatgina x M lar uchun bir vaqtda Ρ(x) chin qiymat va Q(x) yolg‘on qiymat qabul qilganda yolg‘on qiymat qabul qilib, qolgan hamma hollarda chin qiymat qabul qiladigan Ρ(x) Q(x) predikat Ρ(x) va Q(x) predikatlarning implikasiyasi deb ataladi.

Har bir tayinlangan x M uchun

Ρ(x) Q(x) Ρ (x) Q(x)

teng kuchlilik to‘g‘ri bo‘lganligidan I _PQ I _P I_Q CI _P I_Q o‘rinlidir.

Quyidagi formulaning chinlik to’plamini tuzing:

A(x) B(x) C(x)

Quyidagicha belgilash kiritamiz:

1-ish.
2x 3(x 1) 1;.

2x 3x 3 1;.

- x -4

x4

I _{A( x)} (;4); I _{A( x)} [4; ). ,
2-ish.

2 ^{x 1} (4x ² 4x 1) 0; 2 ^{x 1} (2x 1)² 0;

2x 1 0


I _{B( x)} (0.5; ), I _{B( x)} (;0.5]


2.2. PREDIKATLAR MANTIQI FORMULASINING NORMAL SHAKLI. PREDIKATLAR USTIDA MANTIQIY AMALLAR

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.

1-ta’rif. Berilgan to‘plamda aniqlangan va predikatlarning kon’yunksiyasi deb, faqat va faqat x M qiymatlarda aniqlangan

hamda va lar bir vaqtda chin qiymat qabul qilgandagina chin qiymat qabul qilib, qolgan barcha hollarda yolg‘on qiymat qabul qiluvchi yangi predikatga aytiladi va u Ρ(x) Q(x) kabi belgilanadi.

Ρ(x) Q(x) predikatning chinlik sohasi I _P I_Q to‘plamdan, ya’ni va predikatlar chinlik sohalarining umumiy qismidan iborat bo‘ladi.

2-ta’rif. Berilgan M to‘plamda aniqlangan Ρ(x) va Q(x) predikatlarning diz’yunksiyasi deb, faqat va faqatgina x M qiymatlarda aniqlangan hamda Ρ(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 Ρ(x) Q(x) kabi belgilanadi.

Ρ(x) Q(x) predikatning chinlik sohasi I _P I_Q to‘plamdan iborat bo‘ladi.

3-ta’rif. Agar hamma x M qiymatlarda Ρ(x) predikat chin qiymat qabul

qilganda yolg‘on qiymat va x M ning barcha qiymatlarida Ρ(x) predikat yolg‘on qiymat qabul qilganda chin qiymat qabul qiluvchi predikatga Ρ(x) predikatning inkori deb ataladi va u Ρ (x) kabi belgilanadi.

Bu ta’rifdan I _P M \ I_P CI _P kelib chiqadi.

4-ta’rif. Faqat va faqatgina x M lar uchun bir vaqtda Ρ(x) chin qiymat va Q(x) ;yolg‘on qiymat qabul qilganda yolg‘on qiymat qabul qilib, qolgan hamma hollarda chin qiymat qabul qiladigan Ρ(x) Q(x) predikat Ρ(x) va Q(x) predikatlarning implikasiyasi deb ataladi:
Predikatlar mantiqi formulasining normal shakli

5-ta’rif. Agar predikatlar mantiqi formulasi ifodasida faqat inkor,

kon’yunksiya, diz’yunksiya ( , , ) amallari va kvantorli amallar ( , ) qatnashib, inkor amali elementar formulalarga (predmet o‘zgaruvchilar va o‘zgaruvchi predikatlarga) tegishli bo‘lsa, bunday formula deyarli normal shaklda deyiladi

1-teorema . Predikatlar mantiqining har qanday formulasini normal shaklga keltirish mumkin.

Quyidagi teng kuchli formulalardan foydalandim:

1. xA(x) x A(x) . (a)

2. xA(x) x A(x) . (b)

3. xA(x) x A(x) . (c)

4. xA(x) x A(x) . (d)

5. x xy x (e) 6. x y x y (g)

Quyidagi formulalarni deyarli normal shaklga keltiring:
x( A(x) xC(x)) x(C(x) A(x));
1-ish.

Formula deyarli normal shaklga keltirildi.