Mavzu: formulalar. ASOSIY TENG KUCHLI formulalar. Mulohazalar algebrasining funksiyalari

II.2 . Keltirib chiqariluvchi formulalar.

Mulohazalar hisobini qurishning keyingi bosqichi isbotlanuvchi formulalarni ajratib olishdan iborat. Avval aksiomalarni bayon qilamiz, keyin aksiomalardan keltirib chiqariluvchi, ya’ni isbotlanuvchi formulalarni keltirib chiqarish qoidalari ni beramiz.

II.2.1. Mulohazalar hisobining aksiomalari.

Mulohazalar hisobining aksiomalari 4 ta guruhga bo‘lingan ro‘yxatdagi 11 aksiomadan iborat.

I guruù aksiomalari :

I₁. A Þ ( V Þ A ) .

I₂. ( A Þ ( B Þ C )) Þ (( A Þ B ) Þ ( A Þ C )).

II guruù aksiomalari :

II₁. A & B Þ A .

II₂. A & B Þ B .

II₃. ( A Þ B ) Þ (( A Þ C ) Þ ( A Þ B & C )).

III guruù aksiomalari :

III₁. A Þ A Ú B .

III₂. B Þ A Ú B .

III₃. ( A Þ C ) Þ (( B Þ C ) Þ ( A Ú B Þ C )) .

IY guruù aksiomalari :

IY₁. ( A Þ B ) Þ ( ù B Þ ù A ) .

IY₂. A Þ ù ù A .

IY_3. ù ù A Þ A .

II.2.2. Keltirib chiqarish qoidalari .

1. O‘rniga qo‘yish qoidasi.

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

2. Xulosa chiqarish ( Modus ponens –MR ) qoidasi.

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 : ℑ , ℑ Þ ℬ

ℬ .

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

II.2.4 - ta’rif. Agar formulalarning chekli ketma-ketligi ℑ₁, ℑ₂, . . . , ℑ_n da har bir ℑ_i ( i =1, 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 =aralishi 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.

II.2.5 - teorema. ⊢ A Þ A .

Isbot. quyidagi ketma-ketlikni =araylik :

1. A Þ ( V Þ A ) .

   
   

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

   
   

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

   
   

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

   
   

5. A Þ A .
   

6. A Þ A .
   

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

A Þ (V Þ A)- formula I₁ aksioma;

( A Þ (V Þ A )) Þ (( A Þ V ) Þ (A Þ A ))- formula I₂ 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.

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