Predikatlar. Kvantorlar. Predikatlar algebrasining tili. Predikatlar hisobi. Formal arifmetika. Predikat tushunchasi. Predikatlar ustida amallar

Predikatlar algebrasining teng kuchli formulalari.

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

III.3.2 - ta’rif. Predikatlar algebrasining o‘zlari aniqangan щar qanday soщada teng kuchli bo‘lgan formulalari teng kuchli formulalar deyiladi.

ℑ va ℬ teng kuchli formulalar ℑ ≡ ℬ ko‘rinishda belgilanadi.

Mulohazalar algebrasidagi barcha tengkuchliliklar predikatlar algebrasining tengkuchliliklari bo‘lishi ravshan. Faqat predikatlar algebrasiga щos 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 va=tda 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 qiladi.

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

3⁰ - tengkuchlilik isbotlandi.

6⁰- tengkuchlilikni isbotlaylik.

S o‘zgaruvchili mulohaza « yolg‘on » qiymat qabul qilsin. U holda S Þ R ( x ) predikat aynan rost bo‘ladi 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 qiladi.

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 щolatda ham 6⁰ - tengkuchlilikning ikkala tomoni bir ùil qiymat qabul qiladi.

Va niщoyat, R ( x ) predikat aynan rost bo‘lmasa, u holda

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

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

mulohazalarning yolg‘onligi kelib chiqadi. Demak, bu erda ham tengkuchlilikning ikkala qismi bir xil qiymat qabul qiladi.