|
Deduksiya teoremasinin’ natiyjeleri. Amelde deduksiya teoremasinan kelip
shigatugin tomendegi natiyjelerden paydalaniw qolay boladi:
1 - natiyje. Eger H├ C →B va A nin’ erkin ozgeruiwshisine
kvantordi baylaw qagiydasin isletpesden keltirip shigarilgan formulalar bar
bolsa, ol hjagdayda H├C→ В .
2- natija. Eger A formula japiq ham H,A├B bolsa, ol jagdayda H ├ A → B.
Endi bolsa formal aksiomatik nazaryani an’latiwga oteyik.
Eger tomendegi shartler orinlansa, onday jagdayda L formal (aksiomatik) nazarya
aniqlangan esaplanadi:
(1) Sanaqli simvollar toplami L nazaryanin’ simvollari berilgen bolsa L
nazaryanin’ shekli simvollar izbe – izligi L din’ an’latpasi delinedi.
(2) L nazaryanin’ formulalari dep ataliwshi L din’ an’latpalari toplami berilgen
bolsa. (adetde, berilgen an’latpanin’ formula boliw bolmasligin aniqlawshi effektiv
jarayan beriledi).
(3) L nazaryanin’ aksiomalari dep ataliwshi formulalar birikpesi toplami
ajratilgan bolsa. (kop gana jag’daylarda L nazaryanin’ berilgen formulasi
aksioma bo‘liw yaki bolmasligin effektiv aniqlaw mumkin boladi; bul
jagdayda L di effektiv aksiomalastirilgan yaki aksiomatik nazarya delinedi).
(4) Formulalar arasinda keltirip shigariw qag’iydalari dep ataliwshi shekli
R1 ,R2 , …, Rn qatnaslar izbe - izligi berilgen bolsin. Har bir Ri ushin sonday
on’ putin j sani tabilip, j dana formulalardan ibarat har qanday toplam ushin
hamde qa’legen F formula ushin, berilgen j ta formulalar F formula menen
Ri qatnasda boladima, degen soraw effektiv juwmaqlaniwi kerek. Eger bul
sorawga awa dep juwap alinsa, ol jagdayda F formula berilgen j ta
formulalardin’ Ri qag’iydasi boyinsha natiyjesi delinedi.
Eger F1 ,F2 , …, Fn formulalar izbe - izligi berilgen bolip, har qanday i ushin
F formula yamasa aksioma bolsa, yamasa ozinen aldingi qanday da
formulalardin’ natiyjesi bolsa, ol jag’dayda berilgen formulalar izbe – izligi L
da keltirip shigariw delinedi.
Eger L da keltirip shigariw mumkin bolip, bul keltirip shigariwnin’ aqirgi
formulasi F formula menen ustpe-ust tusse, onday jag’dayda F formula L
nazaryanin’ teoremasi delinedi;
Bunday keltiri shigariw F formulanin’ keltirip shigariliwi delinedi. (Berilgen
nazaryaga qarata).
Ha’tte , effektiv aksiomalastirilgan L nazaryada da, teorema tusinigi effektiv
boliwi shart emes, sebebi uliwma alganda berilgen formulanin L da keltirip
shig’ariliwi bar ekenligin aniqlawshi effektiv algoritm bar bolmawi da mumkin.
Bunday algoritm bar bolgan nazaryani sheshiliwshi nazarya, bolmasa
sheshilmeytugin nazarya delinedi.
Biraz aldinga otip soni aytiw mumkin, aytimlarlar esabi ushin qurilgan L
formal aksiomatik nazariya sheshiliwshi nazariya, tar ma‘nidegi predikatlar esabi
nazariyasi bolsa sheshiilmeytugin nazarya boladi.
F formula L nazaryada formulalar toplami Г nin’ logikaliq natiyjesi (aytimlar
esabinda logikaliq natiyje) boliwi ushin sonday F1 ,F2 , …, Fn formulalar
izbe - izligi bar boliwi kerak, bunda F1 ,F2 , …, Fn formula F dan iborat bo‗lib,
qalegen i ushin Fi formula yamasa aksioma, yamasa Г toplamnin’ elementi,
yamasa qandayda bir keltirip shigariw qagiydasi arqali ozinen aldingi
formulalardin’ natiyjesi boliwi za’rur ham jeterli boladi. Bunday formulalar
izbe – izligi Г formulalar toplaminan F ni keltirip shig’ariliwi delinip, Г nin’
elementleri bolsa, keltirip shigariw gipotenuzalari delinedi.
Qolayliq ushin, « F formula Г formulalar toplamnin natiyjesi» degen tastiyiqdi
Г ├ F korinisde jazamiz.
Eger Г shekli toplam bolsa, yagniy Г ={ F1 ,F2 , …, Fn } bul jagdayda
{ F1 ,F2 , …, Fn }├ F jaziwdi F1 ,F2 , …, Fn ├ F korinisinde jazamiz. Eger
Г bos koplille ten’ bolsa, onday jag’dayda Г ├ F jaziw F formula L
da teorema bolganda ham tek usi awhalda gana orinli boladi. Adetde bos koplik
├ F jaziw ornina, ├ F korinisinde jaziladi. Sonday qilip ├ F jaziw « F
formula L da teorema boladi» degen tastiyiqdin’ qisqartirilgani boladi.
Aniqlangan ├ L - keltirip shig’ariliwinin’ bazi qa’siyetlarin korip oteyik.
1-qa’siyet. Eger
bolsa, ol jagdayda boladi.
Haqyiqatdan da, Г ├ F degende tomendegini tusinemiz: sonday eki izbe - izlik bar bolip , bunda formula Fn formula F dan ibarat bolip, qa’legen i ushin Fi formula yamasa aksioma yamasa Г nin’ elementi,
yamasa ozinen aldingi formulalardan bqandayda birewi keltirip shigariw
qagiydasi arqali payda qilinsa natiyjesi boladi.
Eger F1 ,F2 , …, Fn formulalar Г toplamga tiyisli bolsa,
bolgani ushin F1 ,F2 , …, Fn ler ge da tiyisli boladi.
Bul bolsa, ├ F ekanin bildiredi.
2-qa’siyet. Г ├ F boliwi ushin Г nin’ qanday da shekli qism toplami tabilip,
├ F boliwi za’rur ham jeterli boladi.
3-xossa. Eger ├ F bolip toplamnin’ qa’legen G elementi ushin Г ├ F
bolsa, bul jag’dayda Г ├ F boladi.
Ekinshi ham ushinshi qa’sietlerdin’ da’lilli da tap birinshi qa’sieyttegidey ├ nin’
aniqlamasinan kelip shigadi.
├ ning bul ushta qa’sietinen kelejekde ju’da kop ma’rta paydalanamiz.
Biz endi aytimlar esabinin’ L aksiomatik nazaryasin kiritemiz.
(1) L din’ simvollari sipatinda ˥ , →, (,) ham putin on’ indeksli Xi propozitsional hariplerdi alamiz:
X1 , X2 ,X3, ….
Bul jerde ˥ ham → lar primitiv baylawshilar delinedi. Aytimlar esabinin’
a’himiyetli tusinigi esaplangan formula tusinigin kiritemiz.
(2) (a) Barcha propozitsional haripler formulalar boladi:
(b) eger F ham G lar formulalar bolsa, onday jagdayda ˥F F→ G lar da
formulalar boladi.
(3) L nazaryanin’ H, G, F , formulalari qanday boliwinan qattiy nazer
to’mendegi formulalar L din’ aksiomalari boladi:
(4) Jalgiz keltirip shigariw qagiydasi bolip, ol da bolsa, modus ponens
qag’iydasi xizmet qiladi:
F ham F →G formulalardin’ natiyjesi G boladi. Bul qagiydani qisqasha MP
korinisinde belgileymiz.
Aytimlar algebrasindagiday qawslardi apiwayilastiriwga kelisip alayik.
L nazaryanin’ sheksiz aksiomalar toplami tek joqarridagi 3 dana aksiomalar
halin (A1) , (A2), (A3) arqali beriledi.
Har bir formulanin’ aksioma boliw yamasa bolmasligin an’sat gana tekseriw
mumkin ham sonin’ ushin L effektiv aksiomalastirilgan nazarya boladi.
Bizlerdin’ maqsetimiz L sistemani sonday quriwdan ibarat bolip, onda onin’
barliq teoremalar klassi aytimlar logikasin barliq tavtologiyalar kalssi menen
ustpe – ust tusiw.
Basqa baylanistiriwshilardi tomendegidey aniqlaymiz:
ekenin bildiredi.
Bul aniqlamalardin’ ma‘nisi, misali
( D1 ) de, F ham G formulalar qanday bolganda da ( F ^ G ) an’latpa ˥( F→ ˥G)
Formulanin’ qisqartirilgan an’latpasi ekenin bildiredi.
1-Lemma ├ ( F → F ), bul jerde F qa’legen formula boladi.
Da’lil L nazaryada F → F formulani keltirip shigariwdi uyrenemiz.
Sonday qilip, biz (1), (2), (3), (4), (5) formulalardan ibarat shekli izbe –
izlikdi qurdiq. Bunda har bir formula ya aksioma, yamasa ozinen aldingi
formulalardan MP qagiydasi boyinsha payda qilindi ham aqirgi formula teorema
ekanin da’lilleniwi kerek bolgan formula
bilan ustma-ust tushdi.
Paydalanilgan adebiyatlar:
1.H.To’rayev “ Matematik mantiq va diskret matematika”.
2.X.Allambergenov, N.Juzbaev, A.Allambergenova
“Diskret matematika ham matematikaliq logika tiykarlari”
3.H.To’rayev, I. Azizov
“Matematik mantiq va diskret matematika”
4. www.ziyo.uz www.arxiv.uz
Do'stlaringiz bilan baham: | 
