Navoiy davlat pedagogika instituti fizika matematika fakulteti

Keltirib chiqarish qoidalari .

1. O‘rniga qo‘yish qoidas

MH ning tarkibida A o‘zgaruvchi mulohaza qatnashgan

ℑ ( A ) , hamda iùtiyoriy ℬ formulalari berilgan bo‘lsin. Agar ℑ ( A ) mulohazalar hisobining keltirib chiqariluvchi (k.ch.) formulasi bo‘lsa, u holda ℑ ( ℬ ) formula ham mulohazalar hisobining keltirib chiqariluvchi formulasi bo’ladi

Bu qoida qisqacha sxematik ravishda

ℑ ( A )

ℑ ( ℬ )

ko‘rinishda belgilanad

2. Xulosa chiqarish ( Modus ponens –MR ) qoidas

Agar ℑ Þ ℬ va ℑ formulalar MH ning keltirib chiqariluvchi formulalari bo‘lsa, u holda ℬ formula ham MH ning keltirib chiqariluvchi formulasidir. Bu qoida qisqacha quyidagi ko‘rinishda belgilanadi : ℑ , ℑ Þ ℬ

ℬ .

2.3 - ta’rif. 1º. Har bir aksioma mulohazalar hisobining keltirib chiqariluvchi formulasidir.

2º. Mulohazalar hisobining keltirib chiqariluvchi formulasiga o‘rniga qo‘yish qoidasini qo‘llash natijasida hosil qilingan formula mulohazalar hisobining keltirib chiqariluvchi formulasidir.

3º. Mulohazalar hisobining keltirib chiqariluvchi formulalariga ùulosa chiqarish qoidasini qo‘lllash natijasida hosil qilingan formula mulohazalar hisobining keltirib chiqariluvchi formulasidir.

4º. Mulohazalar hisobining boshqa keltirib chiqariluvchi formulalari yo‘q.

2.4 - ta’rif. Agar formulalarning chekli ketma-ketligi ℑ1, ℑ2, . . . , ℑn da har bir ℑi ( i q1, n ) formula yo mulohazalar hisobining keltirib chiqariluvchi formulasi, yo ûzidan oldingi formulalardan o‘rniga qo‘yish yoki ùulosa chiqarish qoidalari yordamida hosil qilingan formulalar bo‘lsa, u holda bu ketma-ketlik oxirgi ℑn formulaning formal isboti , n esa isbotning uzunligi deyiladi

Mulohazalar hisobining aksiomalari isbotining uzunligi 1 ga teng isbotlanuvchi formulalar sifatida qaralishi mumkin. Mulohazalar hisobining isbot uzunligi birdan katta bo‘lgan isbotlanuvchi formulalarini teoremalar deb ataymiz.

«ℑ formula mulohazalar hisobining keltirib chiqariluvchi formulasi» degan jumlani qisqacha ⊢ ℑ belgi orqali ifodalaymiz.

2.5 - teorema. ⊢ A Þ A .

Isbot. quyidagi ketma-ketlikni qaraylik :

A Þ ( V Þ A ) .

( A Þ ( V Þ A )) Þ (( A Þ V ) Þ ( A Þ A )) .

( A Þ V ) Þ ( A Þ A ) .

( A Þ ( V Þ A )) Þ ( A Þ A ) .

A Þ A .

A Þ A .

Bu ketma-ketlik A Þ A formulaning formal isboti ekanligini ko‘rish qiyin emas. Haqiqatdan ham,

A Þ (V Þ A)- formula I1 aksioma;

( A Þ (V Þ A )) Þ (( A Þ V ) Þ (A Þ A ))- formula 2 aksiomadagi S ni A bilan almashtirish natijasida hosil qilingan;

( A Þ V ) Þ ( A Þ A ) formula 2 - formulaga MR qoidasini qo‘lllash natijasida hosil qilingan;

( A Þ ( V Þ A )) Þ ( A Þ A ) formula ûzidan oldingi formulada V ni V Þ A formula bilan almashtirish natijasida hosil qilingan;

A Þ A formula 4 – formulaga MR qoidasini qo‘lllash natijasida hosil qilingan;

A Þ A formula A ni A bilan almashtirish natijasida hosil qilingan.

Bundan keyin mulohazalar hisobining keltirib chiqariluvchi formulasini ℛ xarfi, ù ℛ ni ℱ xarfi bilan belgilab olamiz.

2.6 - teorema. ℑ mulohazalar hisobining iùtiyoriy formulasi bo‘lsin. U holda ℑ Þ ℛ mulohazalar hisobining keltirib chiqariluvchi formulasi bo’lad, ya’ni ⊢ ℑ Þ ℛ.

Isbot. 1. A Þ ( V Þ A ).

2. ℛ Þ ( V Þ ℛ ).

3. V Þ ℛ .

4. ℑ Þ ℛ.

Bu ketma - ketlik teoremaning formal isbotidir. Haqiqatdan ham, 1 - formula I1 aksioma. 2 - formula 1 -formuladan A ni ℛ bilan almashtirish natijasida hosil qilingan. 3 - formula 2 - formuladan MR qoida yordamida hosil qilingan. 4 - formula esa 3 - formulada V ni ℑ formula bilan almshtirish natijasida hosil qilingan.

2.7 - teorema. ⊢ ℱ Þ ù ù ℑ.

Isbot. 1. ( A Þ V ) Þ ( ù V Þ ù A ).

2. ( ù A Þ V ) Þ ( ù V Þ ù ù A ).

3. ( ù A Þ ℛ ) Þ ( ù ℛ Þ ù ù A ).

4. ù ℛ Þ ù ù A.

ℱ Þ ù ù A .

ℱ Þ ù ù ℑ .

Takrorlash uchun savollar :

Mulohazalar hisobining aksiomalarini ayting.

Keltirib chiqarish qoidalari ni keltiring.

Mulohazalar hisobining keltirib chiqariluvchi formulasiga ta’rif bering.

Formulaning formal isboti nima ?

Isbotning uzunligi qanday aniqanadi ?