Кукон давлат педагогика институти

17-мавзу: ФОРМУЛАРНИНГ УМУМЫИЙМАТЛИЛИГИ ВА БАЖАРУВЧИЛИГИ МАСАЛАСИ ЕЧИМИНИНГ МУАММОЛАРИ.

Режа.

1. 
   Масаланинг ыщйилиши ва унинг умумий холда ечиб бщлмаслиги.
   
2. 
   Чекли тщпламларда формула учун масаланинг хал этилиши.
   
3. 
   Чексиз тщпламда бажарилувчи, лекин хеч ыандай чекли тщпламда бажарилмайдигин формула мисоли.
   
4. 
   Бир щринли предикат щзгарувчилари ыатнашган формулалар учун масаланинг хал этилиши.
   
5. 
   -формула ва -формулалар учун масаланинг хал ыилиниши.
   

Таянч иборалар.

Бажарувчилик, умумыийматлик, масаланинг хал этилиши муаммолари, умумий алгоритм, чексиз тщпламда бажарилувчан, 2ⁿ элементлар тщплами, ёпиы формула, -формула,-формула.

Мулохазалар алгебрасида формулаларнинг бажарувчанлиги, айнан ростлик ёки айнан ёльонини аниылаш учун аниы бир алгоритм кщрсатиб щтилган эди. Яни бунинг учун берилган формулаларга мос келган ротслик жадвалини тузиб, олинар эди ва бу жадвалнинг охириги устунига ыараб ъулоса чиыарилар эди. Предикатлар логикасидаги формулалар учун эса бундай масалаларни умумий ъолда хал этиш учун аниы бир алгоритмни кщрсатиб бщлмайди. Бундай хулосаларни 1936 йили Америкалик математик А. Чёрч исботлаб щтган. Шунга ыарамасдан хусусий ъолларда баoзи бир кщринишдаги формулалар учун бу масалани хал этиш мумкин. Шулардан баoзиларини кщриб щтамиз.

Агар предикатлар логикасидаги формулалар чекли тщпламда ыаралаётган бщлса, у ъолда предикат щзгарувчилари щрнига шу тщпламда аниыланган конкрет предикатларни ыщйишимиз мумкин.Чекли тщпламда кванторли амалларни  ва  га алмаштиришимиз мумкин бщлгандагина сабабли бундай формулалар учун бажарувчанлик ва умумыийматлик масаласи мулохазалар алгебрасида ыандайдир формула учун бу масалани хал этишга олиб келади. Мулохазалар алгебраси учун бу масала хал этилади.

Мисол: (у)(х)(Р(х,у)Р(у,у)) {а,в} тщпламда бажарувчанлигини текширамиз. Маoлумки {а,в} тщпламда  ёки  мантиыий амалларга алмаштиришимиз мумкин.

(у)(х)(Р(х,у)Р(у,у))(х)(Р(х,а)Р(а,а)) (х)(Р(х,в)Р(в,в))((Р(а,а)Р(а,а))(Р(в,а)Р(а,а)) (х)(Р(а,в)Р(в,в))(Р(в,в)Р(в,в)).

Предикатлар логикасидаги берилган формула провард натижада Р(а,а), Р(в,а), Р(а,в), Р(в,в) пропозиционал щзгарувчиларга боьлиы бщлган формулага айланди, яoни мулохазалар алгебрасидаги формулага айланди. Агар уларнинг мос равишда х,у,z,v орыали белгиласак, формула [(хх)(ух)(zv)(vv) ухzv] кщринишга келади. Унинг ростлик жадвалини тузиб, тавтология эмаслигига амин бщламиз. Бироы бу формула бажарилувчи. Демак предикатлар логикасидаги дастлабки берилган формула умумыийматли эмас экан, бироы бу формула икки элементли тщпламда бажарилувчи экан. Хозир чексиз тщпламда бажарилувчи бщлиб, хеч ыандай чекли тщплмда бажарилмайдиган формулага мисол келтирамиз, бу мисол орыали ыуйдаги ъулосага келамиз. Предикатлар логикасидаги формуланинг бирор тщпламда бажарилувчанлик эканлигидан бошыа тщаламда ъам бажарилувчи эканлигини хулоса ыилиб бщлмайди. Мана щша формула: (х)(у)(Р(х,у)(х)(Р(х,у)(х)(у)(z)[((Р(х,у)Р(у,z))Р(х,z)] бу формула щзига хос ыуйдаги хоссани билдиради, яoни икки щринли Р(х,у) предикат учун норефлексивлик (конoюкциянинг иккинчи хади) ъамда транзитивлик хоссаси (конoюкциянинг учинчи хади) эканлигини кщрсатиб беради. Ёпиы формула ихтиёрий икки щринли предикат ыщйсак мулохазага айланади. Бу формула (х)(у)(Р(х,у)(х)(Р(х,у)(х)(у)(z)[((Р(х,у)Р(у,z))Р(х,z)] ёпиы формуладир. Шунинг учун икки щзгарувчили Р(х,у) предикат щзгарувчиси щрнига бирор тщпламда аниыланган конкрет предикатни ыщйсак, натижада мулохаза хосил ыиламиз.

Р(х,у): “х<у” десак, у ъолда (х)(у)(х<у)(х)(хх)(х)(у)(z)((х<у)(у

Юыоридаги берилган формуланинг хеч ыандай чекли тщпламда бажарилувчи эмаслигини кщрсатамиз. Фараз ыилайлик, ыандайдир М тщпламда аниыланган конкрет А(х,у) предикат топилиб, (х)(у)(А(х,у))(х)(А(х,х)(х)(у)(z)((А(х,у)А(у,z))А(х,z) бажарилувчи бщлсин.Бу эса бу конoюкциядан хар бир мулохаза рост эканлигини кщрсатади,яoни (х)(у)(А(х,у))=1 (1)

(х)(А(х,х)=1 (2)

(х)(у)(z)((А(х,у)А(у,z))А(х,z)=1 (3)

Бу эса ыуйдагини англатади. Агар М тщпламда ыандайдир а₁М элементини лосак, у ъолда бир мулохазага асосан а₂М топилиб

А(а₁ ,а₂) мулохаза рост бщлади. Худди шу каби шундай а₃М топилиб, А(а₂ ,а₃) мулохаза рост бщлади ва ъ.к.

М тщпламда элементлар чекли бщлиб ъаммаси бир-биридан щзаро фары ыилмаслиги мумкин. Фараз ыилайлик, а_р= а_р+q бщлсин, у ъолда (3) мулохазага кщра (а_р,а_р+1), А(а_р+1, а_р+2)….А(а_р+q+1,а_р+q) эканлигидан А(а_р,а_р+1) нинг ростлиги келиб чиыади, яoни А(а_р,а_р) ростлиги келиб чиыади. Лекин (2) мулохазага кщра А(а_р,а_р) рост бщлиши керак. Бу эса ыарама-ыаршилик. Демак берилган формула хеч ыандай чекли тщпламда бажарилувчи эмаслигини кщрсатади. Агар формулада бир щринли предикат щзларувчилари ыатнашаётган бщлса, у ъолда юыоридаги масалаларнинг самарали хал ыилиш мумкин. Бу ыуйдаги теорема ва унинг натижасида ифодаланади.

Теорема: Агар предикатлар логикасидаги формулада фаыат бир щринли предикат щзгарувчилари ыатнашган бщлиб, у чексиз тщпламда бажарилувчи бщлса, у ъолда бу формула икки элементлар сони 2ⁿ ортиы бщлмайдиган чекли тщпламда бажарилувчидир, бу ерда n-бу формулага кирувчи турлича предикат щзгарувчилар сонидир.

Натижа: Агар F(Р₁, Р₂,…, Р_n) формуладан бир щринли Р₁, Р₂,…, Р_n предикат щзгарувчилари ыатнашиб, ёпиы бщлса, ъамда бу формула элементлар сони 2ⁿ та бщлган тщпламда айнан рост бщлса, у ъолда бу формула умумыийматлидир.

Шундай ыилиб бир щринли предикат щзгарувчилари ыатнашган формулада умумыийматлик масалаларини хал этилиши бу формуланинг чекли тщпламда айнан рост эканлигини кщрсатишга келтирилар экан. Чекли тщпламларда бу масаланинг хал этилиши эса мулохазалар алгебрасидаги формулалар учун бу масала хал этишга келтирилади. Демак бир щринли предикат щзгарувчилари ыатнашган формулаларда бу масалани хал этиш мумкин.

Таoриф: Ихтиёрий формула деганда (х₁),(х₂),…,(х_к) F(Р₁, Р₂,…, Р_к) кщринишдаги формула тушинилади, яoни бу айлантирилган нормал форма кщринишдаги формулаларда фаыат умумыийматлик квантори ыатнашади ъолос. Бу ерда Р_i= (х₁,х₂,…,х_к) (i=). Шундай формула деганда эса, (х₁),(х₂),…,(х_к) F(Р₁, Р₂,…, Р_к) кщринишдаги формула тушинилади, яoни бу айлантирилган нормал форма кщринишдаги формулалардан фаыат шандай квантор ыатнашади холос. Ихтиёрий формулалар ва шундай формулалар учун умумыийматлиликни хал этиш мумкин, яoни ыуйдаги теорема щринлидир:

Теорема: Ихтиёрий формула умумыийматлилиги бщлишлиги учун бу формуланинг чекли тщпламда айнан рост бщлишлиги зарур ва етарлидир.

Шундай формулалар умумыийматлилиги булишлиги учун бир элеиентли тщпламда айнан рост бщлишлиги зарур ва етарли.

Назорат учун саволлар.
1. Формулалар учун умумыийматлилик ва бажарувчанлик масаласи деганда нимани тушунасиз?

2. Чекли тщпламларда умумыийматлилик ва бажарувчанлик масаласи ыандай ъал этилади?

3. Чексиз тщпламда бажарилувчи ва ъеч ыандай чекли тщпламда бажарилмайдиган формулага мисол келтиринг.

4. Бир щринли предикат щзгарувчилар ыатнашган формулаларда бажарилувчанлик масаласи ыандай ъал этилиши мумкин?

5. Ёпиы формула учун бу масала ыандай ъол этилади.

6.  - формула деганда нимани тушунасиз?

7.  - формула деганда нимани тушунасиз?

8.  - формулалар учун бажарилувчанлик масаласи ыандай ъал этилади?

9.  - формулалар учун бажарилувчанлик масаласи ыандай ъал этилади?
18-мавзу: ПРЕДИКАТЛАР ЛОГИКАСИНИ ЛОГИК-МАТЕМАТИК АМАЛИЁТГА ЪАМДА ПРЕДИКАТЛАРНИНГ ФОРМАЛ ЪИСОБГА ЫЩЛЛАНИШИ.

Режа.

1.Турли ибораларни предикатлар логикаси тилида ёзиш.

2.Предикатлар логикаси ва мулоъазалар логикасини солиштириш.

3.Математик теоремаларни ыурилиши.

4.Теоремаларни исботлаш усуллари.

5. Предикатлар логикаси ва тщпламлар алгебраси.

6. Предикатларнинг формал ъисоби ъаыида.

Таянч иборалар.

Предикатлар логикаси тили, фикирлаш процесси, умумтасдиыловчи фикирлаш, умумий инкор ыилинувчи фикирлар, ыисман тасдиыловчи фикирлаш, ыисман инкор ыилинувчи фикирлаш, силогизмлар, исботлаш усуллари, тщпламлар назарияси тушинчалари, аксиомалар системаси, хулосалаш, теорема, зиддиатсиз, боьлиы бщлмаган, тщла.
Предикатлар логикаси назарияси мулоъазалар алгебраси назариясига щхшагани билан мулоъазалар алгебрасидаги хар ыандай тушинча ёки тасдиыларни предикатлар логикасида хар доим ъам умумлаштириб бщлмайди.Бу шу пайтгача предикатлар логикасида логик келтириб чиыарилганлик тушинчасигача яыинлашиб келдик. Логик келтириб чиыарилганлик предикатлар логикасида ъам деярли мулоъазалар алгебрасидагидек таoрифланади. Бироы предикатлар логикасидаги формулалар тузилишига кщра мураккаброы бщлганлиги учун бу ердаги исботлар жуда ъам мураккаброы бщлган эoтиборни жалб ыилади ва натижада нозикроы бщлган ъулосаларга келинади. Амалиётдан предикатлар логикаси ыщлланилиши асосан турли хил теоремаларни исботлаш доирасида бщлади. Логик келтириб чиыарилганликназарияси предикатлар логикасида ва унинг тадбиыларида щрганиш жуда ъам кщпроы ваыт талаб этади. Шунинг учун биз логик хулосалаш назариясини баoзи бир мисолларда кщрсатиб шу орыали унинг мазмунини кщрсатиб берамиз.

Кванторларни белгилар орыали математикада учрайдиган таoриф ва теоремаларни ёзиб олиш ыулайроы ва бунинг натижасида ёзилган иборани идрок ыилиш бироз осонроы кечади.

Сщз ифодаси билан берилган математик ифодаларни кванторли белгилар ва предикатлар ёрдамида ъамда логик амаллар ёрдамида предикатлар логикасидаги формулалар кщринишида ифодалаш мумкин. Бу эса айтилган ибора устида аниы ва равшан фикр юритишга ёрдам беради. Буни баoзи бир мисолларда кщриб щтамиз.

Мисол (Кетма-кетлик лимити таoрифи):

“ а сони {а_n} сонли кетма-кетликнинг лимити дейилади, агар хар ыандай >0 учун n₀ натурал сон топиладики, n₀ дан катта бщлган хар ыандай n натурал сон учун а_n-а< щринли бщлсин.”

а=а_n()[>0(n₀)(n₀N(n)(n>n₀а_n-а<))]

Бу ерда чегараланган квантор амалларни ъисобга олсак, бу ёзув ыуйдаги кщринишни олади: