5-Mavzu. Predikatlar algebrasi formulalarining normal formalari. 1 ta’rif

5-Mavzu.Predikatlar algebrasi formulalarining normal formalari.
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 ℑ (x₁, . . . , x_n) formula ℳ to`plamning elementlarini x<sub>1</sub>, . . . , x<sub>n</sub> 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

ℑ ( x₁, . . . , x_n ) formulasida x₁, . . . ,x_n – erkli predmet o‘zgaruvchilar qatnashgan bo‘lsa, u holda

" x₁ " x₂. . . " x_n ℑ ( x₁, . . . ,x_n ) – formula ℑ ( x₁, . . . ,x_n )

formulaning umumiylik (kvantori orqali) yopi\i,

$ x₁ $ x₂ . . .$ x_n ℑ ( x₁, . . . ,x_n ) 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 :

ℬ = $x₁. . . $x_n ℑ ( U₁, . . . ,U_p ; P₁, . . . , P_q ; . . .

Q₁, . . . , Q_t ) ( 1 ).

ℬ formulada Y₁,Y₂, . . . , Y_p – o‘zgaruvchi mulohazalar ;

P₁,P₂, . . . , P_q – bir o‘rinli predikatlar simvollari va h.k.

Q₁, Q₂, . . . , Q_t - 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

ℑ ( U₁, . . . ,U_r ; R₁( a ) , . . . , R_q ( a ) ; Q₁( a, . . . , a ), . . .

Q_t( a, . . . , a ) ) = 1.

Faraz qilaylik ( 1 ) formula umumqiymatli formula bo‘lmasin. U holda shunday ℳ₁ soha, U₁⁰, . . . , U_r⁰ – mulohazalar,

R₁⁰, . . . , R_q⁰ ; . . . ; Q₁⁰, . . . , Q_t⁰ - ℳ₁ sohada aniqangan

predikatlar mavjud bo‘lib, ( 1 ) formula « yolg‘on»

qiymat qabul qilsin. YA’ni :

$x₁. . . $x_n ( ℑ ( U₁⁰, . . . , U_r⁰; R₁⁰, . . . , R_q⁰; . . .

Q₁⁰ , . . . , Q_t⁰ )) = 0 ( 3 ).

U holda ù ( $x₁. . . $x_n ( ℑ ( U₁⁰, . . . , U_r⁰; R₁⁰, . . . , R_q⁰; . . . ;

Q₁⁰, . . . , Q_t⁰ ))) = "x₁. . . "x_n ( ù ( ℑ ( U₁⁰, . . . , U_r⁰;

R₁⁰, . . . , R_q⁰ ; . . . ; Q₁⁰, . . . , Q_t⁰ ))) = 1 .

Demak, ù ( ℑ ( U₁⁰, . . . , U_r⁰ ; R₁⁰, . . . , R_q⁰ ; . . . ;

Q₁⁰, . . . , Q_t⁰ )) – formula o‘zgaruvchi predikatlarning ℳ₁

to‘plamdagi barcha qiymatuchun aynan rost bo‘ladi.

Xususan, ixtiyoriy ℳ₁ = { x₀ } – bir elementli to`plam uchun

ℑ( U₁⁰, . . . , U_r⁰ ; R₁⁰, . . . , R_q⁰ ; . . . ; Q₁⁰, . . . , Q_t⁰ ) = 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.