Mavzu: Mukammal normal shakllar. Konyunktiv va dizyunktiv normal shakllar

Mavzu: Mulohazalar hisobi.mulohazalar hisobi formulasi tushunchasi.
Mulohazalar hisobi aksiomatik mantiqiy sistema bo`lib,mulohazalar algebrasi esa uning interpretasiyasidir (talqinidir).
Berilgan aksiomalar sistemasi negizida (asosida) qurilgan aksiomatik nazariya deb, shu aksiomalarsistemasiga tayanib isbotlanuvchi barcha teoremalar to`plamiga aytiladi.
Aksiomatik nazariya formal va formalmas nazariyalarga bo`linadi.
Formalmas aksiomatik nazariya nazariy-to`plamiy mazmun bilan to`ldirilgan bo`lib, keltirib chiqarishtushunchasi aniq berilmagan va bu nazariya asosan fikr mazmuniga suyanadi.
Aksiomatik nazariya uchun quyidagi shartlar bajarilgan bo`lsa, u holda formal aksiomatik nazariya aniqlangan hisoblanadi:

5. 
   nazariyaning tili berilgan;
   
6. 
   formula tushunchasi aniqlangan;
   
7. 
   aksiomalar deb ataladigan formulalar to`plami berilgan;
   
8. 
   bu nazariyada keltirib chiqarish qoidasi aniqlangan.
   

Har qanday hisobning tavsifi bu hisobning simvollari tavsifidan, formulalar va keltirib chiqarish formulalar tavsifidan iborat.
Mulohazalar hisobida uch katogoriyali simvollardan iborat alfavit qabul qilinadi:
Birinchi katagoriya simvollari: x,y,z,…,x₁,x₂,…. Bu simvollarni o`zgaruvchilar deb ataymiz.
Ikkinchi katagoriya simvollari: ,,, .Bular mantiqiy bog`lovchilardir.
Uchinchi katagoriyaga qavs deb ataladigan (,) simvol kiritiladi.
Mulohazalar hisobida boshqa simvollar yo`q.
Mulohazalar hisobinig formulasi deb mulohazalar hisobi alfaviti simvollarining ma`lum bir ketma-ketligiga aytiladi.
Formulalarni belgilash uchun lotin alfavitining bosh harflaridan foydalanamiz.Bu harflar mulohazalar hisobinning simvollari qatoriga kirmaydi.Ular faqatgina formulalarning shartli belgilari bo`lib xizmat qiladi.
Mulohazalar hisobida formula tushunchasi quyidagicha aniqlanadi:
1) har qanday x,y,z,… o`zgaruvchilarning istalgan biri formuladir;
2) agar A va B ning har biri formula bo`lsa, u holda lar ham formuladir;
3) boshqa hech qanday simvollar satri formula bo`la olmaydi.
O`zgaruvchilarni elementar formulalar deb ataymiz.
Mulohazalar hisobida isbotlanuvchi formulalar sinfini ajrataylik. Isbotlanuvchi formulalar formulalar ta`rifiga o`xshash ta`riflanadi. Avval dastlabki isbotlanuvchi formulalar(aksiomalar), undan keyin esa keltirib chiqarish qoidasi aniqlanadi.Keltirib chiqarish qoidasi orqali bor isbotlanuvchi formulalardan yangi isbotlanuvchi formulalar hosil qilinadi.
Dastlabki isbotlanuvchi formulalardan keltirib chiqarish qoidasini qo`llash yo`li bilan yangi isbotlanuvchi formulalarni hosil qilish shu formulalarni aksiomalardan keltirib chiqarish deb ataladi.
Endi mulohazalar hisobi uchun L formal aksiomalar nazariyasini kiritamiz.

3. 
   - , , (,) L ning simvollari va A_i butun musbat indekslar bilan uning harflari bo`ladi. – va  simvollar uning primitiv bog`lovchilari, A_i harflari esa propozisional harflar deyiladi.
   
4. 
   (a) Barcha propozisional harflar formulalardir.
   

(b) Agar va lar formulalar bo`lsa, u holda ( ) va ( ) lar ham formula bo`ladi. Shunday qilib, L nazariyadagi barcha formulalar propozisional A_i harflardan - , bog`lovchilari yordamida tuzilgan propozisional ifodalardan iborat.
(3) L nazariyada lar qanday formulalar bo`lmasin, quyidagi formulalar L nazariyada aksiomalar bo`ladi:
(A1) ;
(A2) ;
(A3) .

4. 
   Yagona keltirib chiqarish qoidasi bo`lib “modus ponens” qoidasi xizmat qiladi: Agar va mulohazalar hisobining isbotlanuvchi formulalari bo`lsa, u holda ham isbotlanuvchi formula bo`ladi.BU qoidani qisqacha MP orqali belgilaymiz.
   

L nazariyadagi cheksiz aksiomalar to`plami shu uchtagina (A1),(A2),(A3) aksiomalar asosida beriladi, har biri cheksiz aksiomalar to`plamini hosil qiladi. Har bir formulani aksioma yoki yo`qligini oson tekshirish mumkin, demak, L effektiv aksiomatik nazariya. Biz oldimizga shunday maqsad qo`yamizki: L nazariyalar sistemasini shunday quraylikki, undagi barcha teoremalar sinfi tavtalogiyalar sinfi bilan ustma-ust tushsin.
Qolgan bog`lovchilarni quyidagi ta`riflar orqali kiritamiz:
(D1) ifodalaydi;
(D2) ifodalaydi;
(D3) ifodalaydi.
(D1) ta`rifning ma`nosi shuki, formulalar qanday bo`lmasin uchun belgilash bo`lib xizmat qiladi.
Lemma 1. Ixtiyiriy formula uchun  ekanligi isbotlansin.
Isboti. L da formulani keltirib chiqaramiz.
(1)
( (A2) aksioma sxemasida o`rniga qo`yish)
(2) ((A1) aksioma sxemasida)
(3) ( (1), (2) dan MP bo`yicha)
(4) ( (A1) aksioma sxemasida)
(5) ( (3), (4) dan MP bo`yicha)
Matematik keltirib chiqarishlarda ko`p hollarda biror B tasdiqni isbotlashda boshqa bir A tasqiqni to`g`riligini faraz qilishdan foydalaniladi.Shunday xulosaga kelinadi “ agar A bo`lsa , u holda B” L sistemada bu usul quyidagi teorema orqali asoslanadi.
Deduksiya teoremasi. Agar Г – formulalar to`plamu, - formulalar va Г, A B bo`lsa, u holda Г A  B bo`ladi. Xususan, agar A B bo`lsa, u holda  A  B bo`ladi.
N a t i j a .
(i) 
(ii) 
Isboti. (i)
(a) gipoteza
(b) gipoteza
(c) gipoteza
(d) (a),(b), MP
(e) (b),(d), MP
Shunday qilib,  Bundan, deduksiya teoremasiga ko`ra , 
L e m m a .Ixtiyoriy formulalar uchun quyidagi formulalar L da teorema bo`ladi:
(a) ; (e) ;
(b) ; (f) ;
(c) ; (g) .
(d) ;
I s b o t i .
(a)  .
1. (A3) aksioma sxemasi
2. Lemma 1.
3. 1 , 2 , natija (ii)
4. (A1) aksioma sxemasi
5. 3 , 4 , natija (i)

(b)  .

1. (A3) aksioma sxemasi
2. yuqorida isbotlangan , (a) punkt
3. 1 , 2 , MP
4. (A1) aksioma sxemasi
5. 3 , 4 , natija (i)
(c)  .
1. gipoteza
2. gipoteza
3. (A1) aksioma sxemasi
4. (A1) aksioma sxemasi
5. 2, 3 , MP
6 1, 4, MP
7. (A3) aksioma sxemasi
8. 6 , 7 , MP
9. 5 , 8 MP
Shunday qilib, 1-9 ga ko`ra  . Bundan, deduksiya teoremasiga ko`ra  , bu teoremani yana bir marta qo`llab  hosil qilamiz.