Navoiy davlat pedagogika instituti fizika matematika fakulteti

Predikatlar hisobining keltirib chiqarish qoidalari

2.1. Xulosa chiqarish qoidasi .

Agar ℑ , ℑ Þ ℬ formulalar keltirib chiqariluvchi formulalar bo‘lsa, u holda ℬ ham keltirib chiqariluvchi formuladir. Bu qoida mulohazalar hisobidagidek

ℑ , ℑ Þ ℬ

ℬ

ko‘rinishda belgilanad ( BU KASR BELGISI EMAS )

2.2. O‘zgaruvi mulohazani o‘rniga qo‘o`yish qoidasi .

Predikatlar hisobining keltirib chiqariluvchi ℑ ( A ) formulasida A o‘zgaruvchi mulohaza qatnashsin.

ℬ – predikatlar hisobining ixtiyoriy formulasi bo‘lib, ℬ ning erkin o‘zgaruvchilari ℑ dagi bog‘li= o‘zgaruvchilardan farqli harflar bilan ; ℬ ning bog‘liq o‘zgaruvchilari ℑ ning erkin o‘zgaruvchilaridan farqli harflari bilan belgilangan bo‘lsin. Undan tashqari A mulohaza birorta kvantorning ta’sir doirasida yotgan bo‘lsa, bu kvantorlar bilan bog‘langan harf ℬ formulada qatnashmasin. Bu holda A o‘zgaruvchi mulohaza ℑ formulaning =aerida qatnashgan bo‘lsa, o`sha joylarda A mulohazani ℬ formula bilan almashtirsak, hosil bo‘lgan ifoda predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad Bu qoida qisqacha

ℑ ( A )

ℑ ( ℬ ) ko‘rinishda belgilanad

2.3 – misol. ℑ ( A ) formula

"x $u ( R ( x, u, z ) Ú A ) Ù ù A

ko‘rinishda bo‘lsin. U holda A o`rniga $x ℬ ( x ) yoki "u ℬ ( u )

formulalarni qo‘yib bo‘lmaydi, chunki A ", $ kvantorlarining ta’sir sohasida joylashgan. A o‘rniga $t ℬ ( t ) formulani qo‘yish mumkin, chunki hosil bo‘lgan

"x "y ( P ( x, y, z ) Ú $t ℬ ( t ) Ù ù ( $t ℬ ( t ))

ifoda yana formula bo‘lad

2.4. O‘zgaruvchi predikatni o‘rniga qo‘yish qoidasi .

Bu almashtirish natijasida ham hosil bo‘lgan ifoda formula bo‘lishini ta’minlashimiz lozim.

Predikatlar hisobining keltirib chiqariluvchi ℑ ( F ) formulasida n o‘zgaruvchili F predikat qatnashsin.

ℬ ( t₁, . . , t_n ) – predikatlar hisobining n ta erkin t₁ . . , t_n o‘zgaruvchili formulasi bo‘lsin. ℬ ning bog‘li= o‘zgaruvchilari ℑ ning erkin o‘zgaruvchilaridan, ℬ ning erkin o‘zgaruvchilari ℑning bog‘li= o‘zgaruvchilaridan farqli harflar bilan belgilangan bo‘lsin. Undan tashqari agar F ℑ dagi birorta harfni bog‘lagan kvantorning ta’sir sohasida bo‘lsa, o‘sha harf ℬ formulada qatnashmasin. U holda agar ℑ ( F ) formulada barcha F ( x₁, . . . , x_n ) qatnashgan joylarda

ℬ ( t₁, . . . , t_n ) formulaning t₁ . . , t_n o‘zgaruvchilarini mos ravishda x₁, . . . , x_n larga almashtirib qo‘yib chiqamiz.

Natijada hosil bo‘lgan ifoda predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad

YUQoridagi shartlarning buzilishini o‘zgaruvchilarning kolliziyasi deyilad

2.5 – misol. $x "u $z ( F ( x, y ) Ú ù F ( x, z )) formulada / ni $u "v ( G ( u, t₁) Ù G ( v, t₂ )) bilan almashtirish talab qilinsin.

2.4 dagi shartlar bajarilishini ko`rish qiyin emas. Bundan almashtirish natijasida

$x "u $z (( $u "v ( G ( u, x ) Ù G ( v, y ) Úù $u "v ( G ( u, x ) Ù

Ù G ( v, z )) formula hosil bo‘lad

2.6 – misol. A Ú $x G ( x ) formulada A ni / ( x ) bilan almashtirsak, / ( x ) Ú $x G ( x ) ifoda hosil bo‘lad Bu formula emas, chunki o‘zgaruvchi mulohazani almashtirish qoidasidagi shartlar buzilgani ko‘rinib turibd

Erkin o‘zgaruvchi predmetlarni almashtirish qoidas

Agar predikatlar hisobining keltirib chiqariluvchi ℑ formulasidagi erkin o‘zgaruvchi predmetlarni, shu o‘zgaruvchilar qaerda qatnashsa o`sha joylarning barchasida boshqa erkin o‘zgaruvchi predmetlar bilan almashtirib chiqsak, hosil bo‘lgan ifoda yana predikatlar hisobining keltirib chiqariluvi formulasi bo‘lad

2.8 – misol . $x ( G ( x ) Ù F ( y )) formula berilgan bo‘lsin. U holda u erkin o‘zgaruvchini YUqoridagi qoidaga binoan x dan farqli har qanday o‘zgaruvchi bilan almashtirish mumkin.

2.9 - misol . "x ( G ( x ) Ù F ( y )) Ù G ( y ) formulada u ni t bilan almashtirish mumkin. Natijada

"x (( G ( x ) Ù F ( t )) Ù G ( t ) – formula hosil bo‘lad Biz barcha u qatnashgan joylarda uni t ga almashtirganimizga e’tibor bering.

2.10. Bog‘liq o‘zgaruvchi predmetni almashtirish qoidas

Predikatlar hisobining keltirib chihariluvchi ℑ formulasida bog‘li= o‘zgaruvchi predmetlarni, shu o‘zgaruvchini bog‘lagan kvantorning ta’sir sohasiga tegishli hamma joylarda ℑ dagi barcha erkin o‘zgaruvchi predikatlardan farq qiladigan boshqa bog‘liq o‘zgaruvchi predmetlar bilan almashtirsak, hosil bo‘lgan ifoda predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad

2.11 – misol . ( "x F ( x ) Þ $x G ( x )) Þ G ( y ) formulada x ni t bilan almashtirib

( " t F ( t ) Þ $ t G ( t )) Þ G ( y ) – formulani hosil qilishimiz mumkin. Biz almashtirishni to‘g‘ri bajardik. Haqiqatdan ham, z ¹ u va " kvantorining ta’sir sohasiga tegishli joylardagina x ni z bilan almashtirdik.

2.12. Kvantorlar bilan bog‘lash qoidalari .

Agar ℑ Þ ℬ ( x ) predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lib, x o‘zgaruvchi ℑ da qatnashmasa ℑ Þ "x ℬ ( x ) predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad

Agar ℑ ( x ) Þ ℬ predikatlar hisobining keltirib chiqariluvchi formulalari bo‘lib, x o‘zgaruvchi ℬ da qatnashmasin. $ ℑ ( x ) Þ ℬ predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad

. Predikatlar hisobida keltirib chiqariluvchi formula tushunchasi

3.1 – ta’rif. 1. Predikatlar hisobining har bir aksiomasi keltirib chiqariluvchi formuladir.

2. Predikatlar hisobining keltirib chiqariluvchi formulalariga 2 bayon qilingan keltirib chiqarish qoidalari ni chekli marta qo‘llash natijasida hosil qilingan formulalar ham predikatlar hisobining keltirib chiqariluvchi formulalari bo‘lad

3. Boshqacha usulda keltirib chiqariluvchi formulalar hosil qilib bo‘lmayd Predikatlar hisobining zidsizligi

Aksiomatik nazariyada birorta formula va uning inkori keltirib chiqariluvchi bo‘lsa, bunday nazariya ziddiyatli nazariya, aks holda zidsiz nazariya deyilishi ma’lum.

4.1 – teorema. Predikatlar hisobi zidsiz nazariyadir.

Bu tasdiqni isbot qilish sxemasini beramiz.

Predikatlar hisobining har bir formulasiga mulohazalar hisobining formulasini quyidagi usulda mos qo‘yamiz :

Hamma formulalarni predikatlar algebrasining bir elementli { a } to`plamda aniqangan formulasi deb faraz qilamiz. U holda har bir predikatga mulohaza mos kelad Masalan, / ( x<sub>1</sub>, . . . ,x<sub>n</sub> ) – predikatga / ( a, . . . , a ) mulohaza mos kelad "x ℑ ( x ) , $x ℑ ( x ) formulalar o`rniga ℑ ( a ) formula hosil bo‘lad Predikatlar hisobining elementar formulalari o`rniga mulohazalar algebrasining elementar formulalari, predikatlar hisobining keltirib chiqarish qoidalari mulohazalar hisobining keltirib chiqarish qoidalari ga aylanad Natijada predikatlar hisobining keltirib chqariluvchi formulalari mulohazalar algebrasining aynan rost formulalariga aylanad SHunday qilib, predikatlar hisobi ziddiyatga ega bo‘lsa, u holda mulohazalar algebrasida bitta formulaning o`zi ham aynan rost, ham aynan yolg‘on formula bo‘lib qolar ed Buning esa bo‘lishi mumkin emas.