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. "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.