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ə 9,05 Kb.
səhifə2/2
tarix14.12.2023
ölçüsü9,05 Kb.
#177794
1   2
5-Mavzu. Predikatlar algebrasi formulalarining normal formalari.-fayllar.org

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, . . . ,xnerkli 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, . . . , Ur0mulohazalar,
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.
http://fayllar.org
Yüklə 9,05 Kb.

Dostları ilə paylaş:
1   2




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin