|
Toshkent axborot texnologiyalari universiteti
Radio va mobil aloqa fakulteti 810-20 gurux
talabasi Sayfiyev Fayozjonning Diskret tuzilmalar
fanidan yozgan Mustaqil ishisi
Toshkent 2021
Predikatlar algebrasi, mulohazalar hisobi formulasi
1 - ta’rif. Predikatlar algebrasida inkor amali faqat elementar formulalar oldida kelib, kon’yunksiya, diz’yunksiya, kvantor amallaridan boshqa hech qanday amal qatnashmagan formula normal forma ( formula ) deyiladi.
1 - teorema. Predikatlar algebrasining ixtiyoriy formulasi yo normal forma, yo unga teng kuchli normal forma mavjud.
Isbot. Haqiqatdan, agar formulada Þ , Û amallari qatnashsa, ularda
Á Þ Â º ù Á Ú Â , Á Û Â º (ù Á Ú Â ) Ù ( Á Ú ù Â )
tengkuchliliklardan foydalanib Þ , Û amallarni ù , Ù , Ú amallari bilan almashtiramiz. Inkor amali faqat elementar formulalargagina tegishli bo‘lishi uchun
ù ( Á Ù Â ) º ù Á Ú ù Â , ù ( Á Ú Â ) º ù Á Ù ù Â ,
ù ( "x R ( x )) º $x ù R ( x ) , ù ( $x R ( x ) º "x ù R ( x )
tengkuchliliklardan foydalanish etarli.
2 - ta’rif. Predikatlar algebrasining normal formasida kvantorlar qatnashmasa yoki hamma kvantorlar barcha amallardan avval kelsa, bunday forma keltirilgan normal forma yoki preniksli normal forma deyiladi.
2 - teorema. Predikatlar algebrasining ixtiyoriy formulasi yo keltirilgan normal forma yo unga teng kuchli keltirilgan normal forma mavjud.
XX asrning 40 – yillarida algoritm tushunchasiga aniq ta’rif berilganidan so`ng echilish muammosini hal qilish imkoni hosil bo‘ldi. 1936 yilda amerikalik matematik A.CHyorch predikatlar algebrasi uchun echilish muammosi umumiy holda ijobiy hal qilinmasligini isbot qilgan.
Echilish muammosi chekli sohalar uchun ijobiy hal qilinishi ravshan. Ha=iqatdan, agar ℑ (x1, . . . , xn) formula ℳ to`plamning elementlarini x1, . . . , xn o‘zgaruvchi predmetlar o`rniga qo‘yib chiqib, ℑ formulaning qiymatlarini tekshirib chiqamiz. Bu jarayon chekli qadamda yakunlanadi. Kvantor amallarini esa kon’yunksiya, diz’yunksiya amallari bilan almashtirish mumkin.
1 - misol. "x $u ( R ( x, u, z ) Ú Q ( x )) formula
ℳ = { a, b } to`plamda bajariluvchi bo‘lish bo‘lmasligini aniqash uchun avval formula ko‘rinishini asosiy tengkuchliliklar yordamida o‘zgartiramiz :"x $u ( R ( x, u, z ) Ú Q ( x )) º "x ( P ( x, a, z ) Ú Q ( x ) Ú
Ú R ( x, b, z )) º ( P ( a, a, z ) Ú Q ( a ) Ú P ( a, b, z )) Ù
Ú ( P ( b, a, z ) Ú Q ( b ) Ú P ( b, b, z )).
Hosil bo‘lgan formulada z o`rniga a va b qiymatlarni ketma-ket qo‘yib berilgan formulaning bajariluvchi bo‘lish- bo‘lmasligini aniqash mumkin.
3 - ta’rif. Agar predikatlar algebrasining formulasida erkli o‘zgaruvchilar qatnashmasa, bunday formula yopiq formula deyiladi.
2 - misol. "x "u $z ( P ( x, y ) Ú R ( x, z )) – formula yopi= formuladir.
III.6.4 - ta’rif. Agar predikatlar algebrasining
ℑ ( x1, . . . , xn ) formulasida x1, . . . ,xn – erkli predmet o‘zgaruvchilar qatnashgan bo‘lsa, u holda
" x1 " x2. . . " xn ℑ ( x1, . . . ,xn ) – formula ℑ ( x1, . . . ,xn )
formulaning umumiylik (kvantori orqali) yopi\i,
$ x1 $ x2 . . .$ xn ℑ ( x1, . . . ,xn ) esa berilgan formulaning mavjudlik (kvantori orqali) yopi\i, ikkala $ ," kvantorlar yordamida hosil qilingan yopiq formula - berilgan formulaning aralash yopig‘i deyiladi.
3 - misol. $x R ( x, u, z ) formula berilgan bo‘lsin. U holda "u "z $x R ( x, u, z ) berilgan formulaning umumiylik yopi\i, $u $z $x R ( x, u, z ) – mavjudlik yopi\i,
"u $z $x R ( x, u, z ) – aralash yopig‘i bo‘ladi.
3 – teorema. Predikatlar algebrasining yopiq, normal formasida faqat n ta mavjudlik kvantori qatnashib, umumiylik kvantorlari qatnashmagan bo‘lsin. Agar bu formula ixtiyoriy bir elementli to`plamda rost qiymat qabul qilsa, u holda u umumqiymatli formuladir.
Isbot. Teorema shartiga asosan olingan formula quyidagi ko‘rinishda bo‘lsin :
ℬ = $x1. . . $xn ℑ ( U1, . . . ,Up ; P1, . . . , Pq ; . . .
Q1, . . . , Qt ) ( 1 ).
ℬ formulada Y1,Y2, . . . , Yp – o‘zgaruvchi mulohazalar ;
P1,P2, . . . , Pq – bir o‘rinli predikatlar simvollari va h.k.
Q1, Q2, . . . , Qt - m – o‘rinli predikatlar simvollari;
ℑ - teorema shartiga ko`ra kvantorsiz formuladir.
Teorema shartiga ko`ra ℬ formula ixtiyoriy bir elementli ℳ = { a } to`plamda aynan rost. YA’ni
ℑ ( U1, . . . ,Ur ; R1( a ) , . . . , Rq ( a ) ; Q1( a, . . . , a ), . . .
Qt( a, . . . , a ) ) = 1.
Faraz qilaylik ( 1 ) formula umumqiymatli formula bo‘lmasin. U holda shunday ℳ1 soha, U10, . . . , Ur0 – mulohazalar,
R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 - ℳ1 sohada aniqangan
predikatlar mavjud bo‘lib, ( 1 ) formula « yolg‘on»
qiymat qabul qilsin. YA’ni :
$x1. . . $xn ( ℑ ( U10, . . . , Ur0; R10, . . . , Rq0; . . .
Q10 , . . . , Qt0 )) = 0 ( 3 ).
U holda ù ( $x1. . . $xn ( ℑ ( U10, . . . , Ur0; R10, . . . , Rq0; . . . ;
Q10, . . . , Qt0 ))) = "x1. . . "xn ( ù ( ℑ ( U10, . . . , Ur0;
R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 ))) = 1 .
Demak, ù ( ℑ ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ;
Q10, . . . , Qt0 )) – formula o‘zgaruvchi predikatlarning ℳ1
to‘plamdagi barcha qiymatuchun aynan rost bo‘ladi.
Xususan, ixtiyoriy ℳ1 = { x0 } – bir elementli to`plam uchun
ℑ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 ) = 0 .
Bu esa teorema shartiga zid.
4 – teorema. Predikatlar algebrasining yopiq, keltirilgan normal formulasida faqat n ta umumiylik kvantori qatnashib, mavjudlik kvantorlari qatnashmasin. Agar bu formula elementlari soni n tadan ko‘p bo‘lmagan har qanday to`plamda aynan rost formula bo‘lsa, u holda u umumqiymatli formuladir.
Do'stlaringiz bilan baham: |
