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<sub>1</sub>. . . $x<sub>n</sub> ℑ ( U<sub>1</sub>, . . . ,U<sub>p</sub> ; P<sub>1</sub>, . . . , P<sub>q</sub> ; . . .
Q<sub>1</sub>, . . . , Q<sub>t</sub> ) ( 1 ).
ℬ formulada Y<sub>1</sub>,Y<sub>2</sub>, . . . , Y<sub>p</sub> – o‘zgaruvchi mulohazalar ;
P<sub>1</sub>,P<sub>2</sub>, . . . , P<sub>q</sub> – bir o‘rinli predikatlar simvollari va h.k.
Q<sub>1</sub>, Q<sub>2</sub>, . . . , Q<sub>t</sub> - 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.
http://fayllar.org