Predikatlar. Kvantorlar. Predikatlar algebrasining tili. Predikatlar hisobi. Formal arifmetika. Predikat tushunchasi. Predikatlar ustida amallar
Download 72.27 Kb.
|
2 мавзу
- Bu sahifa navigatsiya:
- Predikatlar algebrasining formulalari.
|
2 – MA`RUZA. PREDIKATLAR. KVANTORLAR. PREDIKATLAR ALGEBRASINING TILI. PREDIKATLAR HISOBI. FORMAL ARIFMETIKA. Predikat tushunchasi. Predikatlar ustida amallar. Predikatlar algebrasi mulohazalar algebrasini kengaytirish natijasida hosil qilingan bo‘lib, mulohazalar algebrasini ûz ichiga oladi. Predikatlar algebrasining asosiy tushunchasi – predikat tushunchasi bilan tanishib chiqaylik. Bizga birorta iùtiyoriy bo‘sh bo‘lmagan predmetlar to`plami ℳ berilgan bo‘lsin. ℳ to‘plamning ixtiyoriy « a » elementi o‘aqida aytilgan mulohazani R ( a ), R ( a ) rost yoki yolg‘on mulohaza bo‘lishi mumkin. Masalan, ℳ – natural sonlar to‘plamidan iborat bo‘lsin, R ( a ) – « a – tub son » - degen darak gap bo‘lsin. U holda R ( 1 ) – « 1 – tub son » - yolg‘on mulohaza, R ( 2 ) – « 2 – tub son » - rost mulohaza, R ( 3 ) – « 3 – tub son » - rost mulohaza, R ( 4 ) – « 4 - tub son » - yolg‘on mulohaza Ko‘rinib turibdiki, R ( a ) - a ning o‘rniga ℳ to‘plamning aniq elementlarini =ûyganimizda rost yoki yolg‘on mulohazalarga aylanar ekan. Xuddi shunday, ℳ to‘plamining ikkita elementi o‘aqida aytidlgan mulohaza R ( a, v ) ko‘rinishida belgilanishi mumkin va h.k. III.1.1 - ta’rif. Bo‘sh bo‘lmagan ℳ to‘plam berilgan bo‘lsin. R : ℳ n ® { 0, 1 }, n = 0, 1, . . . ko‘rinishdagi har qanday funksiya n ûrinli predikat deyiladi. n=0 bo‘lganda ℳ0 = { Æ } bo‘lib, R( Æ ) = 0 yoki R( Æ ) = 1 ko‘rinishdagi ajratilgan elementlar hosil bo‘ladi. Bu ajratilgan elementlarni yolg‘on yoki rost mulohaza deb tushunishimiz mumkin. SHunday qilib o ûrinli predikat – mulohazadir. Ikki ûrinli predikatga misol keltiraylik. Natural sonlar to‘plami N da berilgan R( a , v ) – « a son v soniga qoldi=siz bo‘linadi » - degan predikatni kûrib chiqaylik. Uning qiymatquyidagicha : R ( 1, 1 ) = 1, R ( 1, 2 ) = 0 , . . . , R ( 2, 1 ) = 1 R ( 2, 2 ) = 1, R ( 2, 3 ) = 0 , . . . , R ( 3, 1 ) = 1 va ù.k. Bir ûrinli predikatlar bilan to‘liqroq tanishib chiqamiz. Predikatlar ustida ham mulohazalar ustida bajarilgan amallarni kiritishimiz mumkin. ù , Ù , Ú , Þ , Û amallari bir ûrinli predikatlar uchun quyidagicha aniqanadi : ℳ to‘plamda aniqangan R va Q predikatlar berilgan bo‘lsin. U holda : ( ù R ) – R ning inkori ; ( R Ù Q ) – P va Q ning kon’yunksiyasi ; ( P Ú Q ) – P va Q ning diz’yunksiyasi ; ( P Þ Q ) – P va Q ning implikatsiyasi ; ( P Û Q ) – P va Q ning ekvivalensiyasi quyidagicha aniqanadi : (ù R ) (x) =ù ( R ( x )) , (R * Q ) ( a ) = R ( x ) * Q ( x ), bu erda * - Ù , Ú , Þ , Û amallardan biri. III.1.2 - misol. N – natural sonlar to‘plamida berilgan R ( x ) –“ x – tub son “, Q ( x ) – « x – to= son » - predikatlari berilgan bo‘lsin. U holda ( ù R ) ( x ) =ù ( R ( x )) – « x – tub son emas » degan predikatdir. x ning bir nechta qiymatlarida ù R predikatning qiymatlarini topamiz : ( ù R )( 3 ) = ù ( R( 3 )) =ù 1 = 0, ( ù R )( 4 ) = ù ( R( 4 )) =ù 0 = 1 ( Q Ù R ) (x) – « x – to= va tub son » - degan predikatni ham x ning bir nechta qiymatlarida rost yoki yolg‘on bo‘lishini kûramiz ( Q Ù P )( 1 ) = Q( 1 ) Ù P( 1 ) = 1 Ù 0 = 0, ( Q Ù P )( 2 ) = Q( 2 ) Ù P( 2 ) = 0 Ù 1 = 0, ( Q Ù P )( 3 ) = Q( 3 ) Ù P( 3 ) = 1 Ù 1 = 1. SHunga o‘xshash R Ú Q, P Þ Q, P Û Q predikatlarning mohiyatini tushunib olish qiyin emas. III.1.3 - ta’rif. ℳ to‘plamda aniqangan R(x) predikat berilgan bo‘lsin. U holda R(x) ni rost mulohazaga aylantiradigan x ning ℳ to‘plamga tegishli barcha qiymatlarini Er orqali belgilaymiz. Er - R( x ) ning rostlik soùasi deyiladi. Rostlik sohasi isboti qiyin bo‘lmagan quyidagi xossalarga ega: 10. E ù P = ℳ\ E P. 20. E P Ù Q = E P ìü E Q . 30. E P Ú Q = E P îþ E Q. 40. E P Þ Q = E ù P îþ E Q. Uchinchi xossaning isbotini ko‘rib chiqaylik. Haqiqatdan ham, agar x E P Ú Q bo‘lsa, u holda R ( x ) = 1 yoki Q ( x ) = 1 bo‘ladi. Birinchi holda x Î E R , ikkinchi holda x Î E Q ekanligidan x Î E R îþ E Q kelib chiqadi. Aksincha, x Î E R îþ E Q bo‘lsin. U holda, birlashmaning ta’rifiga ko`ra, x Î E R yoki x Î E Q ekanligi , ya’ni R ( x ) = 1 yoki Q ( x ) = 1 kelib chiqadi. Demak, R ( x ) Ú Q ( x )= 1 va x Î E R îþ E Q. Predikatlar ustida bajariladigan yana ikkita amal kiritamiz : III.I.4 - ta’rif. ℳ to`plamda aniqangan R ( x ) predikat berilgan bo‘lsin. Agar x ning ℳ to`plamdagi barcha qiymatlarida R ( x ) = 1 bo‘lsa, u holda "x R ( x ) – ifoda rost mulohaza, aks holda, ya’ni ℳ to`plamning kamida bitta x0 elementi uchun R ( x0 ) = 0 bo‘lsa, yolg‘on mulohazadir.
" - belgi, umumiylik kvantorining belgisi, $ - belgi, mavjudlik kvantorining belgisi. "x R ( x ) – « barcha x lar uchun R ( x ) bo‘ladi », $x R ( x ) – « shunday x topiladi-ki, R ( x ) bo‘ladi » deb o`qiladi. "x R ( x ) va $x R ( x ) ifodalardagi x o‘zgaruvchi " yoki $ kvantorlari orqali bog‘langan, yo bo‘lmasa, x o‘zgaruvchiga " yoki $ kvantori osilgan deyiladi. Predikatlar algebrasining formulalari. Predikatlar uchun quyida kiritiladigan barcha tushunchalar iщtiyoriy ℳ to`plam bilan bog‘liqBu to`plamni predmetlar to`plami deb ataymiz. Lotin alifbosining oxirrog‘idagi x, u, z, u, v, x1, x2 , . . . - lar o‘zgaruvchi predmetlarni, boshidagi щarflar a, b, c, a1, a2 , . . . - lar ℳ to`plamning ani= elementlarini bildiradi. Lotin alifbosining bosh щarflari A , V , S , . . . - orqali o‘zgaruvchi yoki o‘zgarmas mulohazalar belgilanadi. F ( x ), G ( x, y ), P ( x1, x2, . . . , xn ), . . . – ifodalar orqali predikatlarni belgilaymiz. Agar a, b – doimiy predmetlar, G – ikki o‘zgaruvchili predikat bo‘lsa, G ( a, b ) mulohaza bo‘lishi ravshan. A , V , S , . . . va F ( a ), G ( a, b ), . . . ko‘rinishdagi mulohazalar elementar mulohazalar deyiladi. Endi predikatlar algebrasining formulasi tushunchasini kiritamiz. Predikatlar algebrasida quyidagi simvollar ishlatiladi:
x0, x1, . . . , xn – predmet o‘zgaruvchilar. , , . . . , , . . . – predikatlar ( - n – o‘rinli predikat). ù , Ù , Ú , Þ , Û - mantiq amallari. " , $ - kvantorlar. ( , ) - qavslar. III.2.1 - ta’rif. 1. Щar qanday elementar mulohaza – formuladir. 2. Agar - ni – o‘rinli predikat, , . . . , - o‘zgaruvchi predmetlar yoki doimiy predmetlar bo‘lsin. U holda - formuladir. YUQoridagi 1,2 – punktlarda aniqangan formulalar elementar formulalar deyiladi. 3. Predikatlar algebrasining birida bog‘liq bo‘lgan predmet o‘zgaruvchi ikkinchisida erkin bo‘lmaydigan Á va  formulalar berilgan bo‘lsin. U holda Á Ù Â, Á Ú Â, Á Þ Â, Á Û Â ,ù Á ifodalar ham predikatlar algebrasining formulalaridir. 4. Predikatlar algebrasining x erkin o‘zgaruvchi qatnashgan A ( x ) formulasi berilgan bo‘lsin, u holda "x A ( x ), $ x A ( x ) ifodalar ham predikatlar algebrasining formulasidir. Predikatlar algebrasining 1 – 4 punktlarda sanab chiqilgan formulalardan boshqa formulalari yo‘q. III.2.2 - misol. , " x $ x, " x- ifodalar predikatlar algebrasining formulalaridir. Predikat simvolidagi indekslarni kerak bo‘lmagan hollarda tashlab yozishni kelishib olamiz. Masalan, o`rniga R ( x, y, z ) yozish mumkin. III.2.3 - misol . " x Q ( x, u ) Ú R ( x ) ifoda formula bo‘lmaydi, chunki, III.2.1 - ta’rifdagi 3 - punkt shartlari bajarilmagan. III.2.4 - misol . N0 = { 0, 1, 2, . . . } to`plam va N0´N0 da aniqangan P( x, y ) ⇌ “ x < y ” , Q( x, y ) ⇌ “ x2 + y2 = 5 “ predikatlar berilgan bo‘lsin. $x ( R( x, u ) Ù Q( x, u )) – predikatning qiymatlarini topaylik. Bu formula bir o‘zgaruvchili predikat bo‘lib, uning qiymatfaqat u ga bog‘liqMasalan, agar u = 0 bo‘lsa, $x ((« x < u ») Ù (« x2 + 02 = 5 »)) = 0 ; u = 1 bo‘lsa, $x ((« x < 1 ») Ù (« x2 + 12 = 5 »)) = 0; u = 2 bo‘lsa, $x ((« x < 2 ») Ù (« x2 + 22 = 5 »)) = 1 va щ.k[D2]. ( bu erda * «⇋» belgi « aynan shu » ma’nosini bildiradi ).
Download 72.27 Kb. Do'stlaringiz bilan baham: 
|