Formulalar. ASOSIY TENG KUCHLI formulalar. Normal formalar. Mulohazalar hisobini qurish. Teng kuchli almashtirishlar. Normal formalar. Mulohazalar algebrasi


Download 51.02 Kb.
Sana26.11.2020
Hajmi51.02 Kb.
#152077
Bog'liq
1 мавзу


1 – MA`RUZA . FORMULALAR. ASOSIY TENG KUCHLI FORMULALAR. NORMAL FORMALAR. MULOHAZALAR HISOBINI QURISH. TENG KUCHLI ALMASHTIRISHLAR. NORMAL FORMALAR.

1. Mulohazalar algebrasi.Mulohazalar ustida mantiq amallari.

I.1.1 – ta’rif. Rost yoki yolg‘onligini bir qiymatli aniqash mumkin bo‘lgan darak gap mulohaza deyiladi.

« sayin – daraxt », « Negrlar – oq tanli odamlar »,

« 5 > 2 », « Bugun – 5 – may » kabi gaplar mulohazalarga misol bo‘la oladilar. Lekin щar qanday gap ham mulohaza bo‘la olmaydi, masalan, « YAshasin O‘zbekiston yoshlari! », « Sen nechanchi kursda o‘qiysan? » kabi gaplar mulohazalar emas, chunki ular darak gaplar emas.

Demak, biror bir gap mulohaza bo‘lishi uchun, u albatta darak gap bo‘lishi va rost yoki yolg‘onligi bir qiymatli aniqlanishi shart.

Ûzbek tilidagi barcha mulohazalar to‘plamini ℳ orqali belgilaylik. ℳ to‘plamning elementlarini lotin alifbosining bosmacha, indeksli yoki indekssiz bosh щarflari bilan belgilashga kelishib olamiz. YA’ni A , V , S , . . . , A 1,

A 2 , . . . , A n - mulohazalardir. A mulohaza rost bo‘lsa, unga 1 ni, yolg‘on bo‘lsa, 0 ni mosqo`yamiz.

I.1.2 – ta’rif. A va V mulohazalarning kon’yunksiyasi deb, A va V mulohazalar rost bo‘lgandagina rost, qolgan hollarda yolg‘on bo‘ladigan A V mulohazaga aytiladi.

Mulohazalar kon’yunksiyasi mantiqiy ko‘paytirish deb ham ataladi va A · V yoki A & V kabi belgilanishi mumkin.

I.1.3 - ta’rif. A va V mulohazalar diz’yunksiyasi deb, A va V mulohazalarning ikkalasi ham yolg‘on bo‘lgandagina yolg‘on, qolgan hollarda rost bo‘ladigan A Ú V mulohazaga aytiladi.

Mulohazalar diz’yunksiyasi mantiqiy qo‘shish deb ham yuritiladi va A + V kabi belgilanishi ham mumkin.

I.1.4 - ta’rif. A mulohaza rost bo‘lganda yolg‘on, yolg‘on bo‘lganda rost bo‘ladigan ù A mulohaza A mulohazaning inkori deyiladi.

A mulohazaning inkori `A orqali belgilanishi ham mumkin.

Mulohazalar ustida bajariladigan amallar rostlik jadvali deb ataladigan jadvallar yordamida ham berilishi mumkin. YUQorida ta’riflangan amallar rostlik jadvali quyidagi ko‘rinishda bo‘ladi :


A

V

A Ù V

A Ú V

ù A

1

1

1

1

0

1

0

0

1

0

0

1

0

1

1

0

0

0

0

1

Bundan tashqari yana bir qancha amallar, ya’ni :

Þ - implikatsiya yoki mantiqiy xulosa,

Û yoki ~- ekvivalensiya yoki mantiqiy teng kuchlilik,

ï - SHefer shtrixi,

¯ - Pirs strelkasi,

Å - qat’iy diz’yunksiya, ya’ni 2 modul bo‘yicha qo‘shish amallari quyidagi jadval orqali beriladi:



A

V

A Þ V

A Û V

A ô V

A ¯ V

A Å V

1

1

1

1

0

0

0

1

0

0

0

1

0

1

0

1

1

0

1

0

1

0

0

1

1

1

1

0

I.2. Mulohazalar algebrasi. Mulhozalar algebrasi alfaviti, formula tushunchasi.

I.2.1 - ta’rif. < M , ù , Ù , Ú ,Þ , Û > - universal algebra mulohazalar algebrasi deyiladi.

Mulohazalar algebrasini qisqacha MA deb belgilaymiz.

MA ning alfaviti quyidagilardan iborat :

A , V , S , . . . – mulohazalarni belgilash uchun ishlatiladigan xarflar;

ù , Ù , Ú , Þ , Û - mantiq amallarini belgilash uchun ishlatiladigan belgilar;

( , ) - chap va o‘ng qavslar .

Mulohazalar algebrasining asosiy tushunchalaridan biri formula tushunchasidir. Unga induktiv ta’rif beramiz.

I.2.2 - ta’rif. 1). Xar bir mulohaza formuladir.



2). Agar Á va  lar formulalar bo‘lsa, u holda

( ù Á) , ( Á Ù Â ) , ( Á Ú Â ) , ( Á Þ Â ) , ( Á Û Â ) lar ham formulalardir.

3). 1) va 2) lar yordamida щosil qilingan ifodalargina formulalardir.

Masalan, A , V , S lar 1) ga asosan formulalar; ( ù V ),

( A Þ ( ù V )), ( ( ( A Þ ( ù V )) Þ A ) Ù S ) lar 2) ga asosan formulalardir.

Formulalarning tarkibidagi qavslarni kamaytirish ma=sadida mantiq amallarining bajarilish tartibini

ù , Ù , Ú , Þ , Û deb belgilab olamiz. Demak, qavslar bo‘lmaganda avval ù , keyin Ù va щ.k. amallar bajariladi. Bundan tashqari tash=i qavslarni ham extiyoj bo‘lmaganda tashlab yuboramiz. Bunday ûzgartirishlardan keyin

( ( A Ù V ) Ú ( (ù A ) Þ S ) ) formulani A Ù V Ú (ù A Þ S ) ko‘rinishda ¸zishimiz mumkin bo‘ladi.

I.2.3 - ta’rif. Formulada qatnashgan mantiq amallari soni formulaning rangi deyiladi.

YUQorida keltirilgan formulaning rangi 4 ga teng.

I.2.4 - ta’rif. 1. Á formula - mulohaza bo‘lsa , uning formulaosti faqat uning ûzidan iborat.


  1. Agar formulaning ko‘rinishi Á *  dan iborat bo‘lsa, u holda uning formulaostilari Á ,  , Á *  , hamda Á va  larning barcha formulaostilaridan iborat bo‘ladi. Bu erda * - Ù , Ú , Þ , Û amallaridan biri.

  2. Agar formulaning ko‘rinishi ù Á bo‘lsa, uning formulaostilari Á formula, Á formulaning barcha formulaostilari va ù Á ning ûzidan iborat.

  3. Boshqa formulaostilari yo‘q.

Teng kuchli formulalar. Tavtologiya – mantiq qonunii.

I.3.1 - ta’rif. MA ning Á va  formulalari berilgan bo‘lib, bu formulalar tarkibiga kirgan barcha mulohazalar A1 ,. . ., Am - lardan iborat bo‘lsin. Agar A1 , . . . , A m mulohazalarning barcha qiymatlar tizimlari ( i1, . . . , im ) lar uchun Á va  formulalar bir щil qiymatlar qabul qilsalar, u holda, bu formulalar teng kuchli formulalar deyiladi.

Á va  formulalarning teng kuchliligi Á º  ko‘rinishda ifodalanadi.

I.3.2 - ta’rif. Mulohazalar algebrasining



Á( A1,. . . , An) formulasi A1 ,. . . , An mulohazalarning barcha qiymattizimi ( i1, . . . , in) uchun 1 qiymat qabul qilsa, aynan rost formula yoki tavtologiya yoki mantiq qonunii deyiladi.

Aynan rost formulani qisqacha AR deb belgilaymiz.

I.3.3 - ta’rif. MA ning Á ( A 1, . . . , A n ) formulasi

A1 ,. . . , An mulohazalarning barcha qiymattizimi

( i1 , . . . , in ) lar uchun 0 qiymat qabul qilsa, aynan yolg‘on yoki ziddiyat deyiladi

I.3.4 - ta’rif. Agar mulohazalar algebrasining



Á (A1 , . . . , An) formulasi A1 , . . . , An larning kamida bitta ( i1 , . . . , in ) qiymattizimida 1 ga teng qiymat qabul qilsa, u holda bu formula bajariluvchi formula deyiladi.

I.3.5 - teorema. Mulohazalar algebrasining Á va  formulalari teng kuchli formulalar bo‘lishi uchun, Á Û Â formula aynan rost formula bo‘lishi zarur va etarli.



Isbot. Á º  bo‘lsin. U holda Á va  formulalarga kirgan barcha propozitsional o‘zgaruvchilarning barcha qiymattizimlarida Á va  formulalar bir xil qiymatlar qabul qiladilar. YA’ni, Á Û Â = 1 bo‘ladi.

Aksincha, Á Û Â = 1 bo‘lsa, Á = 1 bo‘lganda  = 1 va

Á = 0 bo‘lganda  = 0 bo‘ladi.

I.3.6. Asosiy teng kuchli formulalar.



  1. A Ù A º A (kon’yunksiyaning idempotentlik qonunii).

  2. A Ú A º A (diz’yunksiyaning idempotentlik qonunii).

  3. A Ù 1 º A .

  4. A Ú 1 º 1.

  5. A Ù 0 º 0 .

  6. A Ú 0 º A .

  7. A Ú ù A º 1 – uchinchisini inkor qilish qonunii.

  8. A Ù ù A º 0 - ziddiyatga keltirish qonunii.

  9. ù ( ù A ) º A - qo‘sh inkor qonunii.

  10. A Ù ( V Ú A ) º A .

  11. A Ú ( V Ù A ) º A .

  12. A Û V º ( A Þ V ) Ù ( V Þ A ).

  13. A Þ V º ù A Ú V .

  14. ù ( A Ù V ) º ù A Ú ù V .

  15. ù ( A Ú V ) º ù A Ù ù V .

  16. A Ù V º ù ( ù A Ù ù V ).

  17. A Ú V º ù ( ù A Ù ù V ).

  18. A Ù V º V Ù A – kon’yunksiyaning kommutativlik qonunii.

  19. A Ú V º V Ú A – diz’yunksiyaning kommutativlik qonunii.

  20. A Ù ( V Ú S ) º ( A Ù V ) Ú ( A Ù S ) - Ù ning Ú ga nisbatan distributivlik qonunii.

  21. A Ú ( V Ù S ) º ( A Ú V ) Ù ( A Ú S ) - Ú ning Ù ga nisbatan distributivlik qonunii.

  22. A Ù ( V Ù S ) º ( A Ù V ) Ù S – kon’yunksiyaning assotsiativlik qonunii.

  23. A Ú ( V Ú S ) º ( A Ú V ) Ú S – diz’yunksiyaning assotsiativlik qonunii.



Normal formalar. Mukammal diz’yunktiv normal forma ( MDNF ), mukammal kon’yunktiv normal forma

( MKNF ).

Á1, Á2, . . . , Án ( n³ 1 ) mulohazalar algebrasining formulalari bo‘lsin, u holda (. . .( ( Á1 Ù Á2 ) Ù Á3 ). . . Án ) –formula Á1, Á2 , . . . , Án – formulalarning kon’yunksiyasi deyiladi va ( Á1 Ù . . . Ù Án ) orqali belgilanadi.

(. . .( ( Á1 Ú Á2 ) Ú Á3 ) . . . Án ) – formula esa Á1 , Á2 , . . . , Án - formulalarning diz’yunksiyasi deyiladi va ( Á1 Ú . . . Ú Án) orqali belgilanadi.

I.7.1 - ta’rif. Propozitsional o‘zgaruvchiyoki ularning inkorlaridan tuzilgan iùtiyoriy kon’yunksiya



(diz’yunksiya) elementar kon’yunksiya (diz’yunksiya) deyiladi.

I.7.2 - ta’rif. Elementar kon’yunksiyalarning ixtiyoriy diz’yunksiyasi - diz’yunktiv normal forma



(DNF), elementar diz’yunksiyalarning ixtiyoriy kon’yunksiyasi - kon’yunktiv normal forma (KNF) deyiladi.

I.7.3 - misol. X1, X2, X3 – propozitsional o‘zgaruvchiberilgan bo‘lsin, u holda ( X1 Ù X2 ) Ú X3 – DNF ga,

( X1Ú X2 ) Ù ( X1Ú X3 ) – KNF ga misol bo‘ladi.

I.7.4 - ta’rif. Á formula X1, X2 ,. . . ,Xn – propozitsional o‘zgaruvchilardan tuzilgan elementar kon’yunksiya bo‘lsin. Agar har bir propozitsional o‘zgaruvchi, inkori ham ùisoblanganda, Á da bir martadan ortiqqatnashmasa Á - tû\ri, kamida bir marta qatnashsa , Á - to‘liq, faqat bir marta qatnashsa, Á - mukammal elementar kon’yunksiya deyiladi.

To‘g‘ri va to‘liq elementar kon’yunksiya mukammal elementar kon’yunksiya bo‘lishi ravshan.

I.7.5 - misol. X1, X2 , X3 –propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda ù X1 Ù X2 – to‘g‘ri, X1 Ù X2 Ù X3 Ù

Ù ù X1 Ù ù X2 - tûliq, X1 Ù ù X2 Ù X3 – mukammal elementar kon’yunksiyalardir.

I.7.6 - ta’rif. Á - formula X1, . . . ,Xn – o‘zgaruvchilardan tuzilgan elementar diz’yunksiya bo‘lsin. Agar har bir propozitsional o‘zgaruvchi, inkori ham ùisoblanganda, Á - formulada bir martadan ortiq qatnashmasa, tzg‘ri, kamida bir marta qatnashsa, to‘liq, faqat bir marta qatnashsa, mukammal elementar diz’yunksiya deyiladi.

I.7.7 - misol. X1 , X2 , X3 - propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda X1 Ú ù X2 – tû\ri,

ù X1 Ú X2 Ú ù X3 Ú ù X1 – tûliq, X1 Ú ù X2 Ú X3 – mukammal elementar diz’yunksiyalardir.

I.7.8 - ta’rif. Turli mukammal elementar kon’yunksiya

( diz’yunksiya ) lardan tuzilgan diz’yunksiya ( kon’yunksiya ) mukammal diz’yunktiv ( kon’yunktiv ) normal forma MDNF ( MKNF ) deyiladi.

I.7.9 - misol. X1, X2, X3 – propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda

( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) Ú ( ù X1 Ù X2 Ù X3 ) - MNDF ; ( X1 Ú ù X2 Ú X3 ) Ù ( X1 Ú X2 Ú X3 ) – MKNF bo‘ladi.

I.7.10 -ta’rif. Mulohazalar algebrasining Á formulasiga teng kuchli DNF ( KNF, MDNF, MKNF ) Á - formulaning DNF ( KNF, MDNF, MKNF ) si deyiladi.

I.7.11 - teorema. Mulohazalar algebrasining ixtiyoriy formasining DNF ( KNF ) si mavjud.

I.7.12 - teorema. Mulohazalar algebrasining ixtiyoriy Á formulasining MDNF ( MKNF ) i mavjud.

I.7.14 - misol. X1 Ù ( X2 Ú X3 ) formulaning MDNF ini toping. Avval X1 Ù ( X2 Ú X3 ) ning DNF ini topaylik. I.3.6 dagi 20 - tengkuchlilikka asosan :

X1 Ù ( X2 Ú X3 ) º ( X1 Ù X2 ) Ú ( X1 Ù X3 ) .

X1 Ù X2 va X1 Ù X3 – larning MDNF larini I.3.6 da keltirilgan tengkuchliliklar yordamida topamiz.

X1 Ù X2 º X1 Ù X2 Ù 1 º X1 Ù X2 Ù ( X3 Ú ù X3 ) º

º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) .

X1 Ù X3 º X1 Ù 1 Ù X3 º X1 Ù ( X2 Ú ù X2 ) Ù X3 º

º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) . Bundan,

( X1 Ù X2 ) Ú ( X1 Ù X3 ) º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù

Ù X2 Ùù X3 ) Ú ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) º

( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 )-

MDNF. Demak, X1 Ù ( X2 Ú X3 ) – formulaning MDNF i

( X1 Ù X2 Ù X3 )Ú ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) – formuladan iborat ekan.



Muloxazalar hisobi

Mulohazalar hisobi (MH) aksiomatik nazariya bo‘lib, mulohaza tushunchasiga hech qanday mazmun berilmaydi. Mulohazalarni odatdagidek lotin alifbosining bosh harflari bilan belgilaymiz. Mulohazalarga qo‘yiladigan talab bitta, u ham bo‘lsa, mulohazalar hisobining aksiomalarni qanoatlantirishi kerak. Mulohazalar algebrasini mulohazalar hisobining interpretatsiyalaridan biri sifatida qarash mumkin.



Mulohazalar hisobida .formula tushunchasi.

Mulohazalar hisobini qurish uchun avval uning alfaviti, ya’ni MH da ishlatiladigan belgilar sanab chiqiladi, sûngra shu belgilarning ketma-ketligidan tuzilgan so‘z – formula tushunchasi va niùoyat, keltirib chiqariluvchi formulalar ta’riflanadi.

MH ning alfaviti uchta tur belgilardan iborat :


  1. A , V , S , . . . , X , U, Z , . . . – o‘zgaruvchi mulohazalar.

  2. ù , & , Ú , Þ - mantiqiy bog‘lovchilar.

  3. ( , ) - chap va o‘ng qavslar.

MH da boshqa belgilar yo‘q.

II.1.1 - ta’rif. 1. Har bir o‘zgaruvchi mulohaza formuladir.



2. Agar ℑ va ℬ lar formula lar bo‘lsa, u holda (ù ℑ),

(ℑ & ℬ ) , ( ℑ Ú ℬ ) , ( ℑ Þ ℬ ) – lar ham formuladir.

3. Boshqa usulda formula hosil qilib bo‘lmaydi.

O‘zgaruvchi mulohazalarni elementar formulalar deb ataymiz.

Mulohazalar hisobida formulaosti tushunchasi mulohazalar algebrasidagidek kiritiladi. qavslarni tashlab yuborish tartibi ham mulohazalar algebrasidagidek. SHu sababli, bular ustida to‘xtalib o‘tmaymiz.



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 :

I1. A Þ ( V Þ A ) .

I2. ( A Þ ( B Þ C )) Þ (( A Þ B ) Þ ( A Þ C )).

II guruù aksiomalari :

II1. A & B Þ A .

II2. A & B Þ B .

II3. ( A Þ B ) Þ (( A Þ C ) Þ ( A Þ B & C )).

III guruù aksiomalari :

III1. A Þ A Ú B .

III2. B Þ A Ú B .

III3. ( A Þ C ) Þ (( B Þ C ) Þ ( A Ú B Þ C )) .

IY guruù aksiomalari :

IY1. ( A Þ B ) Þ ( ù B Þ ù A ) .

IY2. A Þ ù ù A .

IY3. ù ù 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 ℑ1, ℑ2, . . . , ℑ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 I1 aksioma;

( A Þ (V Þ A )) Þ (( A Þ V ) Þ (A Þ A ))- formula I2 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 ⊢ ℑ Þ ℛ.

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.

II.2.7 - teorema. ⊢ ℱ Þ ù ù ℑ.



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

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

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

4. ù ℛ Þ ù ù A.



  1. ℱ Þ ù ù A .

  2. ℱ Þ ù ù ℑ .

Download 51.02 Kb.

Do'stlaringiz bilan baham:



Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling