mavzu. Predikatlar algebrasi formulalarining normal formalari ta’rif
ta’rif. Agar predikatlar algebrasining formulasida erkli o‘zgaruvchilar qatnashmasa, bunday formula yopiq formula deyiladi. 2 - misol
Yüklə 30,35 Kb.
|
1 2
5-Mavzu. Predikatlar algebrasi formulalarining normal formalari.| 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. Yüklə 30,35 Kb. Dostları ilə paylaş:
|
1 2