|
MAVZU. PREDIKATLAR ALGEBRASIGA KIRISH. PREDIKAT VA KVANTORLAR. PREDIKATLAR ALGEBRAS PREDIKATLAR ALGEBRASI FORMULAS
Predikatlar algebrasi mulohazalar algebrasini kengaytirish natijasida hosil qilingan bo‘lib, mulohazalar algebrasini ûz ichiga olad 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.
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 deyilad
n=0 bo‘lganda ℳ0 = { Æ } bo‘lib, R( Æ ) = 0 yoki R( Æ ) = 1 ko‘rinishdagi ajratilgan elementlar hosil bo‘lad 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 bir
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.
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 deyilad
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‘lad Birinchi holda x Î E R , ikkinchi holda
x Î E Q ekanligidan x Î E R îþ E Q kelib chiqad
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 chiqad Demak, R ( x ) Ú Q ( x )= 1 va x Î E R îþ E Q.
Predikatlar ustida bajariladigan yana ikkita amal kiritamiz :
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.
5 - ta’rif. $ x R ( x ) – ifoda x ning ℳ to`plamdagi kamida bitta x0 elementi uchun R ( x0 ) = 1 bo‘lganda rost, qolgan hollarda yolg‘on mulohazadir.
" - belgi, umumiylik kvantorining belgisi,
$ - belgi, mavjudlik kvantorining belgis
"x R ( x ) – « barcha x lar uchun R ( x ) bo‘ladi », $x R ( x ) –
« shunday x topiladi-ki, R ( x ) bo‘ladi » deb o`qilad
"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 deyilad
Do'stlaringiz bilan baham: | 
