Navoiy davlat pedagogika instituti fizika matematika fakulteti

3. Hosilaviy keltirib chiqarish qoidalar Ba`zi tavtologiyalar isbot Predikatlar hisobining zidsizligi va to’lalig Matematik nazariyalar. Formal arifmetika.

Teng kuchli formulalar

3.1 - ta’rif. Predikatlar algebrasining ℳ to’plamida aniqangan ℑ va ℬ formulalari berilgan bo‘lsin. Agar ℳ to’plamning har bir elementi uchun ℑ va ℬ lar bir xil qiymat qabul qilsalar, u holda ℑ va ℬ formulalar ℳ to’plajda teng kuchli formulalar deyiladi

3.2 - ta’rif. Predikatlar algebrasining o‘zlari aniqangan har qanday sohada teng kuchli bo‘lgan formulalari teng kuchli formulalar deyiladi

ℑ va ℬ teng kuchli formulalar ℑ ≡ ℬ ko‘rinishda belgilanad

Mulohazalar algebrasidagi barcha tengkuchliliklar predikatlar algebrasining tengkuchliliklari bo‘lishi ravshan. Faqat predikatlar algebrasiga hos teng kuchli formulalardan asosiylari quyidagilardir :

1. ù ( "x P ( x )) º $x ù P ( x ).

2. ù ( $x P ( x )) º "x ù P ( x ).

3. "x P ( x ) Ù "x Q ( x ) º "x ( P ( x ) Ù Q ( x )).

4. A Ù "x P ( x ) º "x ( A Ù P ( x )).

5. B Ú "x P ( x ) º "x ( B Ú P ( x )).

6. C Þ "x P ( x ) º "x ( C Þ P ( x )).

7. "x ( P ( x ) Þ C ) º $x P ( x ) Þ C.

8. $x ( P ( x ) Ú Q ( x )) º $x P ( x ) Ú $x Q ( x ).

9. $x ( A Ú P ( x )) º A Ú $x P ( x ).

10. $x( A Ù P ( x )) º A Ù $x P ( x ).

11. $x P ( x ) Ù $y Q ( y ) º $x $y ( P ( x ) Ù Q ( u )).

12. $x ( C Þ P ( x )) º C Þ $x P ( x ).

13. $x ( P ( x ) Þ C ) º "x P ( x ) Þ C.

Tengkuchliliklarda A , V , S lar o‘zgaruvchi mulohazalar;

P, Q lar o‘zgaruvchi predikat simvollaridir.

3- tengkuchlilikni isbotlaylik. Agar R ( x ) va Q ( x ) predikatlar bir vaqtda aynan rost bo‘lsalar, u holda

R ( x ) Ù Q ( x ) predikat ham aynan rost bo’ladi Bundan esa

"x R ( x ), "x Q ( x ), "x ( R ( x ) Ù Q ( x ))

mulohazalarning rost qiymat qabul qilishi kelib chiqadi

Ya’ni bu holda tengkuchlilikning ikkala tomoni «rost» qiymat qabul qilad

Faraz qilamiz berilgan R ( x ) va Q ( x ) predikatlarning kamida bittasi masalan, R ( x ) aynan rost bo‘lmasin. U holda

R ( x ) Ù Q ( x ) predikat ham aynan rost bo‘lmaydi, bundan esa

"x R ( x ), "x R ( x ) Ù "x Q ( x ), "x ( R ( x ) Ù Q ( x ))

mulohazalar yolg‘on bo’ladi Ya’ni bu holda ham tengkuchlilikning ikkala tomoni bir xil (yolg‘on) qiymat qabul qilad

3 - tengkuchlilik isbotlandi

6- tengkuchlilikni isbotlaylik.

S o‘zgaruvchili mulohaza « yolg‘on » qiymat qabul qilsin. U holda S Þ R ( x ) predikat aynan rost bo’lad va bundan

S Þ "x R ( x ) va "x ( S Þ R ( x ))

mulohazalarning rostligi kelib chiqadi Ya’ni, bu holda tengkuchlilikning ikkala tomoni bir xil qiymat qabul qilad

Endi S o‘zgaruvchili mulohaza « rost » qiymat qabul qilsin. Agar bunda o‘zgaruvchili predikat R ( x ) aynan rost bo‘lsa, u holda S Þ R ( x ) predikat ham aynan rost bo’ladi Bundan esa

"x R ( x ) , S Þ "x R ( x ), "x ( S Þ R ( x ))

mulohazalarning rost ekanligi kelib chiqadi Ya’ni, bu holatda ham 60 - tengkuchlilikning ikkala tomoni bir ùil qiymat qabul qilad

Va nihoyat, R ( x ) predikat aynan rost bo‘lmasa, u holda

S Þ R ( x ) predikat ham aynan rost bo‘lmayd Bundan esa

"x R ( x ), S Þ "x R ( x ), "x ( S Þ R ( x ))

mulohazalarning yolg‘onligi kelib chiqadi Demak, bu yerda ham tengkuchlilikning ikkala qismi bir xil qiymat qabul qilad

Takrorlash uchun savollar :

1. Predikatlar algebrasining formulasi ta’rifini ayting.

2. Predikatlar algebrasining teng kuchli formulalari deb qanday formulalarga aytilad ?

3. Predikatlar algebrasidagi tengkuchliliklar qanday isbotlanadi ?

M a sh q l a r :

1. quyidagi predikatlar teng kuchli bo’ladgan to’plamni aniqlang :

1) « x 3 ga karrali » , « x 7 ga karrali ».

2) « x – parallelogramm », « x to’rtburchakning diagonallari teng » .

3) « x – tub son » , « x – juft son » .

4) « x2 – x – 2 q 0 » , « x3 + 1 q 0 » .

2. YuQorida keltirilgan tengkuchliliklarni isbotlang.

4.1 - ta’rif. Predikatlar algebrasida inkor amali faqat elementar formulalar oldida kelib, kon’yunktsiya, diz’yunktsiya, kvantor amallaridan boshqa hech qanday amal qatnashmagan formula normal forma ( formula ) deyiladi

4.2 - 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 tegishl bo‘lishi uchun

ù ( Á Ù Â ) º ù Á Ú ù Â , ù ( Á Ú Â ) º ù Á Ù ù Â ,

ù ( "x R ( x )) º $x ù R ( x ) , ù ( $x R ( x ) º "x ù R ( x )

tengkuchliliklardan foydalanish yetarli

4.3 - 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

4.4 - teorema. Predikatlar algebrasining ixtiyoriy formulasi yo keltirilgan normal forma yo unga teng kuchli keltirilgan normal forma mavjud.

Bu teoremaning isbotini 4.2 – teoremadan va 3-§ da keltirilgan asosiy tengkuchliliklardan keltirib chiqarish mumkin.

Takrorlash uchun savollar :

1. Predikatlar algebrasining normal formasi deb nimaga aytilad ?

2. Predikatlar algebrasining ixtiyoriy formulasiga teng kuchli normal forma mavjudligini isbotlang.

3. Keltirilgan normal forma ta’rifini ayting.

4. 4.4 – teoremani isbotlang.

M a sh q l a r :

Teng kuchli almashtirishlar yordamida quyidagi formulalarni keltirilgan normal formaga aylantiring :

$x ( A ( x ) Þ "u ( V ( u ))).

ù ( "x A ( x ) Þ $u V ( u )).

$x ( "u A ( u ) Þ V ( x )) Ù ù ( "u $x ( V ( x ) Þ A ( u ))).

ù ("x A ( x ) Ú $x( V ( x ) Þ S ( x ))).

Teng kuchli almashtirishlar yordamida quyidagi formulalarni preneksli normal formalarga aylantiring :

"u A ( x, u ) Þ V ( x, x ).

"u A ( u, z ) Þ $x B ( x, t, z ).

$x A ( x, y, z ) Þ ù ( "x B ( x, y )).

"x ( A ( x ) Þ B ( x )) Þ ( $x A ( x ) Þ $y B ( y )).

5 . Predikatlar algebrasida

echilish muammos

5.1 - ta’rif. Predikatlar algebrasining ℑ formulasiga kirgan o‘zgaruvchi predmetlar x1, x2, . . . , xn larning to’plamidan olingan, hech bo‘lmaganda bitta qiymattizimi a1, a2, . . . , an lar uchun ℑ formula rost qiymat qabul qilsa, u holda ℑ formula ℳ to’plamda bajariluvchi deyiladi

5.2 - ta’rif. Predikatlar algebrasining kamida bitta to’plamida bajariluvchi formulasi predikatlar algebrasining bajariluvchi formulasi deyiladi

5.3 – ta’rif. Agar predikatlar algebrasining ℑ formulasi, formula tarkibiga kirgan barcha o‘zgaruvchi predmetlarning ℳ to’plamidagi ixtiyoriy qiymatuchun rost qiymat qabul qilsa, bunday formula ℳ to’plamda aynan rost formula deyiladi

5.4 - ta’rif. Har qanday to’plamda aynan rost bo‘lgan formula umumqiymatli formula deyiladi

5.5 - ta’rif. Umumqiymatli formula logik qonuni deyiladi

5.6 - ta’rif. Agar predikatlar algebrasining ℑ formulasi, formula tarkibiga kirgan barcha o‘zgaruvchi predmetlarning ℳ to’plamidan olingan ixtiyoriy qiymatuchun yolg‘on qiymat qabul qilsa. Bu formula ℳ to’plamda aynan yolg‘on formula deyiladi

5.7 - ta’rif. Har qanday to’plamda aynan yolg‘on bo‘lgan formula aynan yolg‘on formula deyiladi

5.8 - misol. $x R ( x, u ) – formula bajariluvchi formuladir. Haqiqatdan, R ( x, u ) – natural sonlar to’plamida aniqangan “ u ∶ x ” predikat bo‘lsin, u holda

R ( 1, u ) q 1. Demak, $x R ( x, u ) q 1.

5.9 - misol . $x $u R ( x, u ) – predikat bajariluvchi predikatdir. Haqiqatdan, R ( x, u ) – predikat natural sonlar to‘plamida aniqangan « x > u » predikati bo‘lsin, u holda

R ( 5, 1 ) q 1. Demak, $x $u R ( x, u ) q 1.

5.10 - misol. R ( x ) Ú ù R ( x ) – predikat umumqiymatli predikatdir.

5.11 - misol. R ( x ) Ù ù R ( x ) – predikat aynan yolg‘on predikatdir.

Predikatlar algebrasining ixtiyoriy formulasi bajariluvchi yoki bajariluvchi emasligini aniqab beradigan samarali usul mavjud bo‘lish yoki bo‘lmasligini aniqash masalasi predikatlar algebrasi uchun yechilish muammosi deyiladi

Formula bajariluvchiligi masalasini hal qilsak formula aynan rost yoki aynan yolg‘onligi ham hal qilinad

haqiqatdan, agar ℑ formula aynan rost bo‘lsa ù ℑ formula bajariluvchi bo‘la olmayd Demak, ℑ va ù ℑ formulalarning bajariluvchi yo bajariluvchi emasligini aniqash natijasida ℑ ning aynan rost bo‘lish bo‘lmasligi ma’lum bo’ladi

Takrorlash uchun savollar :

Predikatlar algebrasining biror bir to’plamda bajariluvchi (aynan rost, aynan yolg‘on) formulasiga ta’rif bering.

Predikatlar algebrasining bajariluvchi

(umumqiymatli, aynan yolg‘on) formulasi deb qanday formulaga aytilad ?

M a sh q l a r :

Natural sonlar to’plamida qaralayotgan quyidagi predikatli formulalarning qaysilari bajariluvchi ( aynan rost, aynan yolg‘on ) ekanligini aniqlang :

$x "u (ù ( u > x ) Û $x ( ù $u ( u > x ));

$x "u (( u > x ) Ú ù ( u > 0 )) Û $x "u ( u > 0 Þ u > x);

ù ( "x $u $z ( x < y Ù z2 > y ) Û "x $y ( x < y Ù

Ù $z ( z2 > y )).

quyidagi formulalarning bajariluvchi ekanligini isbotlang :

$x $y ( A ( x ) Ù ù A ( y ));

$x "u ( V ( x, u ) Þ "z C ( x, y, z ));

A ( x ) Þ "y A ( y );

"x ( A ( x ) Ú B ( x )) Þ ( "x A ( x ) Ú "x B ( x )).

4. quyidagi formulalarning umumqiymatli ekanligini isbotlang :

$x "u V ( x, u ) Þ "u $x V ( x, u );

"x ( A ( x ) Þ V ( x )) Þ ( "x A ( x ) Þ "x V ( x ));

"x ( A ( x ) Þ V ( x )) Þ ( $x A ( x ) Þ $x V ( x ));

$x ( A ( x ) Þ V ( x )) Û ( "x A ( x ) Þ "x V ( x )).