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

ЧЕГАРАЛАНГАН КВАНТОРЛАР.

Математика амалиётида куйдаги куринишдаги иборалар тез-тез учраб туриди: “Р хусусиятга эга булган хар кандай объект,Q хусусиятга хам эгадир.”, “Р хусусиятга эга булган объектлар ичида, Р хусусиятга эга бщлганлари хам мавжуд”. Бу ифодаларни биринчисини куйдагича ифодалаш мумкин: (Р(x))(Q(x)) Q(x). Бу ифодани эса кискача (Р(x))(Q(x)) куринишда ифодалаш мумкин ва “чегараланган умумийлик квантори оркали богланиш амали” дей илади.

Масалан: “Хар кандай х1 лар учун ln х0 уринлидир”.

(х)((х1) (ln х0))  ((х1))( ln х0)

Юкорида келтирилган иккинчи иборага маъно жихатдан куйдаги ибора тенг кучлидир: “Р ва Q хусусиятга эга булган объект мавжуд”. Буни эса куйдагича ифодалаш мумкин: (х)( Р(x)Q(x)). Кискача куриниши (P(х))(Q(x)) ва уни чегараланган мавжудлик квантори оркали богланиш деб аталади. (P(х))- чегараланган мавжудлик квантори.

Масалан: “квадрати –1 га тенг буладиган хакикий сон мавжуд”  (х)((хR)(х²=-1)).

Назорат учун саволлар.

1. Предикатлар логикаси формулаларида иштирок этувчи белгилар алфавитини кщрсатиб беринг.

2. Предикатлар логикаси формуласи таoрифини ифодаланг.

3. Элементар (атомар) формулалари деб нимага айтилади?

4. (x) (F) ва (x) (F) кщринишдаги формулаларда F нима деб аталади?

5. Ёпиы ъамда очиы формула таoрифини келтиринг.

6. Формуланинг М тщпламдаги интерпретацияси деганда нимани тушунасиз?

7. Предикатлар логикасидаги формулаларнинг классификациясини келтиринг.

8. Предикатлар логикасидаги тавтологиялар билан мулоъазалар алгебрасида тавтологиялар орасида ыандай боьланиш мавжуд?

9. Кванторли формулалар учун де Морган ыонунларини ифодаланг.

10. Бир кванторларни бошыа бир кванторлар орыали ифодалаш хоссаларини кщрсатиб беринг.

11. Кванторларни конoюнкция ва дизoюнкция орыали щтказиш хоссаларини кщрсатиб беринг.

12. Кванторли формулалар учун бошыа хоссаларни ъам кщрсатиб беринг.

15 Мавзу: Предикатлар логикаси формулалари.

Режа.

1. 
   Предикатлар логикасида формула тушунчаси.
   
2. 
   Предикатлор логикасидаги формулаларнинг классификацияси.
   
3. 
   Предикатлар логикасидаги тавтологиялар.
   

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

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

Юкоридаги таoрифдаги бир ва иккинчи пунктдаги формулалар элементар (атомар) формулалар дейилади. (((х)(Р(х))Q) (y)(Р(x,y)))- мураккаб хосил килинган формулалар. Бу формулаларда х узгарувчи биринчи кисмида богланган иккинчи кисмида эркин катнашаяпти. Шунинг учун бу формулани (((z)(Р(z))Q) (.....) куринишда ёзиш максадга мувофикдир.

Мулохазалар алгебрасидаги каби формулалардаги ташки кавсларни келишилган холда ташлаб кетиш хам мумкин.Формула таърифидаги 1,2,3,4 пунктларга асосан мулохазалар алгебрасидаги хар кандай формула предикатлар логикасида хам формула булишлиги келиб чикади. (х)(F) ёки (х)(F) куринишдаги формулаларда F формула (х) ёки (х) кванторларнинг таъсид доираси дейилади. Бунда иштирок этган узгарувчи, шу узгарувчи буйича кванторли амал таъсир доирасида иштирок этган булса, богланган булади.

Эркин узгарувчилар катнашмаган формулалар ёпик формулалар дейилади. Бирорта эркин узгарувчи катнашган формулалар эса, очик формулалар дейилади.

ПРЕДИКАТЛАР ЛОГИКАСИДАГИ ФОРМУЛАЛАРНИНГ КЛАССИФИКАЦИЯСИ.

Предикатлар логикасидаги формулаларди предикат узгарувчиси урнига бирор N тупламда аникланган конкрет предикатни олиб бориб куйсак, натижада шу N тупламда аникланган предикат хосил булади. Бунда агар берилган формула ёпик булса, у холда хосил килинган предикат нолъ уринли предикат яъни мулохазага айланади. Агар берилган формула очик булса, у холда хосил киланган предикат кандайдир предмет узгарувчиларига боглик булган конкрет предикатга айланади. Предикат узгарувчилар урнига M тупламдан кандайдир конкрет предикатни олиб бориб куйсак,натижада яна янги мулохаза хосил булади. Берилган мулохазани шундай усулларда мулохазага айлантиришни одатда формуланинг M тупламдаги интерпритацияси дейилади.

1мисол: (х)(у)(Р(х,у)) шу формулани интерпритациясини келтирамиз. M туплам сифатида барча эркаклар туплами.

Р(х,у) “х у нинг отаси”.

(х)(у)(Р(х,у))  “Ихтиёрий отаннг угли мавжуд”.

M туплам атролфида N- барча натурал сонлар тупламини оламиз. Р(х,у):(ху) (х)(у)( ху): “ихтиёрий натурал сондан катта булган натурал сон мавжуд”.

2 мисол: (z)(P(x,y,z))Q(x,y,z)) R формуланинг интерпретациясини келтиринг.

M сифатида N ни оламиз.

P(x,y,z): xy=z (z)((xy=z) ( x+y=z)) (2=4)

Q(x,y,z): x+y=z

R: 2=4 2=4 ёлгон. (z)((xy=z : x+y=z)) (2=4) ёлгон мулохаза.

Предикатлар логикасидаги формулалар учун уларни классификацияловчи куйдаги таърифларни келтирамиз:

ТАOРИФ: Предикатлар логикасидаги формулалар M тупламда бажарилувчи (инкор килинувчи) формула дейилади, агар бу формулада предикат узгарувчилар урнига шу N тупламда аникланган кандайдир предикатни куцганимизда , натижада бажарилувчи (инкор килинувчи) предикатга айланса. Бошкача килиб айтганда формула бажарилувчисиинкор килувчи дейилади, агар бу формуланинг M тупламдаги рост (ёлгон) интерпретацияси мавжуд булса.

ТАOРИФ: Предикатлар логикасидаги формула M тупламда айнан рост (айнан ёлгон) формула дейилади, агар ундаги предикат узгарувчилар урнига N тупламда аникланган ихтиёрий конкрет предикатни куйсак, хар доим рост (ёлгон) мулохаза хосил булади.

ТАOРИФ: Предикатлар логикасидаги формула умумкийматли ёки тавталогия деб аталади,агар ундаги предикат узгарувчилар урнига ихтиёрий тупламда аникланган ихтиёрий конкрет предикатни куйганимизда хар доим рост (ёлгон) мулохаза хосил булади.

Мисол: Р(х)(у)(Р(у)) формуланинг карама-карши эканлигини курсатинг.

А(х) предикатни куяйлик:  А(х) (у)(А(у)) ва аМ предикат киймат топиб,  А(а) (у)(А(у)) мулохаза рост булиши . Конюъкция рост булиши учун  А(а)- рост ва (у)(А(у))- рост булиши керар. Бундан эса бир вакитда А(а)-ёлгон, (у)(А(у))- рост булиши келиб чикади. Бу эса мумкин эмас.Чунки у=а булганда А(у) предикат ёлгон, яъни А(у)- ёлгон эканлигини курсатади.

Предикатлар логикасида мулохазалар алгебрасидаги каби тавтологияларни курсатиш ёки уларни хосил килиш коидаларини курсатишмухим масалалардан бри хисобланади. Мулохазалар алгебрасидатавтологияларни аниклаш учун умумий усул аникланган (яъни формулалар учун ростлик жадвали тузилади ва охриги устунга караб аникланади).

Предикатлар логикасида эса бундай умумий усул берилмаган. Хар бир берилган формулага алохида ёндашиб, узига хос булган усуллардан фойдаланиш мумкин холос.

Предикатлар логикасидаги мухим булган тавтологиялар билан танишамиз. Дастлаб, редикатлар логикасидаги энг оддий тавтологиялар мулохазалар алгебрасидаги тавтологиялардан хосил булишини курсатамиз.

Мулохазалар алгебрасидаги тавтологияларда уларга кирувчи хар бир пропорционал узгарувчилар урнига предикат узгарувчиларни алмаштириб ёзсак, натижада предикатлар логикасидаги тавтологиялар хосил булади. Мулохазалар алгебрасидаги тавтологияларга келтирилмайдиган тавтологияларни курсатиб утамиз.

16.1 Кванторлар учун де Морген конунлари.

а) (х)(Р(х))(х)(Р(х))

б) (х)(Р(х)) (х)(Р(х))

16.2 Бир кванторларни бошка кванторлар оркали белгилаш.

а) (х)(Р(х))(х)(Р(х))

б) (х)(Р(х))(х)(Р(х))

16.3 Кванторларни конъюкция ва дизъюнкция ичига киритиш.

а) (х)(Р(х)Q(х))((х)(Р(х)(х)(Q(х))).

б) (х)(Р(х)Q(х))((х)(Р(х))(х)(Q(х))).

в) (х)(Р(х)Q)((х)(Р(х))Q.

г) (х)(Р(х)Q)((х)(Р(х))Q.

16.4 Кванторларни имплекация ичига киритиш.

а) (х)(Р(х)Q) ((х)(Р(х))Q).

б) (х)(Р(х)Q)((х)(Р(х))Q).

в) (х)(Q(Р(х))(Q(х)(Р(х))).

г) (х)(Q(Р(х))(Q(х)(Р(х))).

16.5 Умумийлик кванторини йщыотиш ва мавжудлик кванторини киритиш.

а) (х)(Р(х)Р(у).

б) Р(у)(х)(Р(х)).

16.6 Кванторлар учун комутативлик ыонунлари.

а) (х)(у)(Р(х,у))(у)(х)(Р(х,у)).

б) (х)(у)(Р(х,у))(у)(х)(Р(х,у)).

в) (у)(х)(Р(х,у))(х)(у)(Р(х,у)).

Юыорида келтирилган тавтологияларда ыатнашган предикат щзгарувчилари нол щринли, бир щринли ъамда икки щринли, агар бу предикат щзгарувчилар щрнига кщп щринли предикат щзгарувчилар щрнига кщп щринли предикат щзгарувчиларни ыщйсак, бу формулалар айнан ростлигини саылаб ыоладими, йщыми?

Бу саволга ыуйдаги теорема жавоб беради:

Теорема: 16.1-16.6 тавтологияларда предикат щзгарувчиларни чекли сондаги ихтиёрий предмет щзгарувчиларига боьлиы деб олсак ъам бу формулалаор предикатлар логикаси тавтологиялари бщлиб ыолаверади.

16.1-16.6 гача бщлган формулаларда Р ва Q харифлар щрнига предикат логикасидаги ихтиёрий формуларни олиб келиб ыщйсак, хам натижада тавтологиялар хосил бщлади.

Назорат учун саволлар.
1. Предикатлар логикаси формулаларида иштирок этувчи белгилар алфавитини кщрсатиб беринг.

2. Предикатлар логикаси формуласи таoрифини ифодаланг.

3. Элементар (атомар) формулалари деб нимага айтилади?

4. (x) (F) ва (x) (F) кщринишдаги формулаларда F нима деб аталади?

5. Ёпиы ъамда очиы формула таoрифини келтиринг.

6. Формуланинг М тщпламдаги интерпретацияси деганда нимани тушунасиз?

7. Предикатлар логикасидаги формулаларнинг классификациясини келтиринг.

8. Предикатлар логикасидаги тавтологиялар билан мулоъазалар алгебрасида тавтологиялар орасида ыандай боьланиш мавжуд?

9. Кванторли формулалар учун де Морган ыонунларини ифодаланг.

10. Бир кванторларни бошыа бир кванторлар орыали ифодалаш хоссаларини кщрсатиб беринг.

11. Кванторларни конoюнкция ва дизoюнкция орыали щтказиш хоссаларини кщрсатиб беринг.

12. Кванторли формулалар учун бошыа хоссаларни ъам кщрсатиб беринг.

16-МАВЗУ: Формулаларни тенг кучли алмаштиришлар.

Режа.

1. 
   Формулалар тенг кучлилиги тушинчаси.
   
2. 
   Предикатлар логикасидаги формулалар учун келтирилган форма.
   
3. 
   Предикатлар логикасидаги формулалар учун айлантирилган (предворённая) нормал форма.
   

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

М тщпламда тенг кучли, тенг кучли, формулаларни тенг кучли алмаштириш, келтирилган форма, айлантирилган ёки предворённая нормал форма, кванторнинг таoсир доираси.

Предикатлар логикачидаги иккита F ва H формулалар M тщпламда тенг кучли дейилади, агар бу формулаларда иштирок этувчи предикат щзгарувчилари щрнига М тщпламда аниыланган ихтиёрий конкрет предикатни кщрганимизда натижада тенг кучли предикатлар ъосил бщлса. Агар иккита формула ихтиёрий тщпламда тенг кучли бщлса, бу формулани оддийгина ыилиб, тенг кучли формулалар дейилади ва мулоъазалар алгебрасидаги FH каби белгилаймиз. Тенг кучли бщлмаган формулаларга мисоллар.

(x)(Р(x)Q(x))(x)(Р(x))(x)Q(x))

Ъаыиыатдан ъам Р(х) ва Q(х) щзгарувчилар щрнига конкрет А(х) ва В(х) (N да аниыланган). Предикат щзгарувчиларини ыщямиз. Натижада N тщпламда аниыланган конкрет предикатлар ъосил бщлади.

Масалан: А(х): «х- жуфт сон» В(х): «х- тоы сон» десак, чап томонда турган формула ыуйидаги мулоъазага айланади: «ихтиёрий натурал сон ё жуфт сон, ё тоы сон». Маoлумки, бу мулоъаза ростдир. Щнг тосондаги мулоъаза ыуйидагича бщлади: «ъар ыандай натурал сон жуфт ёки ъар ыандай натурал сон тоы». Бу мулоъаза ёльондир. Тафтологиялар  F каби белгиланади. Юыоридаги таoрифлардан ва тафтологиялар таoрифидан ыуйидаги ъулоса келиб чиыади. F ва H формулалар фаыат ва фаыат шундагина тенг кучли формула бщлади, агар FH тафтология бщлса. Бу келтирилган ъулоса 16,1-16,6 гача бщлган формулалар билан тенг кучли бщлган формулалар ъосил ыилиш имкониятини яратади. Мулохазалар алгебрасидаги каби предикатлар логикасида хам формулалар тенг кучлилиги тушунчаси бир формуладан бошыа формулага тенг кучли алмаштириш имкониятини яратади. Буни одатда берилган формулани тенг кучли алмаштириш деб аталади. Тенг кучли алмаштиришлар ёрдамида формулаларни соддалаштириш ёки махсус бир кщринишга келтиришимиз мумкин.Бу ерда биз ёна мулохазалар алгебрасидаги тенг кучли алмаштиришлардан фойдаланишимиз мумкин. Тенг кучли алмаштиришлар ёрдамида формулаларни ыуйдагича махсус кщринишга келтиришимиз мумкин.

Таoриф: Предикатлар логикасидаги формулалар учун келтирилган форма деб, бу формулада тенг кучли бщлган шундай формулага айтиладики, бу ерда мантиыий амаллардан фаыат , ,  ыатнашган бщлади. Бу ерда  белгиси фаыат предикат щзгарувчиси ёки мулохазага таoсир этади холос.

Теорема: Предикатлар логикасидаги хар ыандай формула учун хар доим келтирилган форма мавжуд.

Тенг кучли алмаштиришлар ёрдамида формулаларни ыуйдагича кщриниши мавжуд.

Таoриф: Предикатлар логикасидаги формулалар учун айлантирилган (предворённая) нормал форма деб, берилган формулалар учун шундай нормал формулага айтиладики, бу формулада хамма кванторлар формулаларнинг бошланишида келиб, уларнинг таoсир доираси формуланинг охригача бщлса, (х₁,х₁)(х₂,х₂)….(х_m,х_m) (F(х₁,х₂,…,х_n)). К_i (I=). Ихтиёрий ёки шундай кванторлардан бири бщлиб F формуланинг щзида бирорта квантор ыатнашмайди.

Теорема: Предикатлар логикасидаги хар ыандай формула учун айлантирилган (предворённая) нормал форма мавжуд.
Назорат учун саволлар.

1. Предикатлар логикасидаги икки формуланинг тенг кучлилиги таoрифини ифодаланг.

2. Берилган формулани тенг кучли алмаштириш деганда нимани тушунасиз.

3. Предикатлар логикасидаги формула учун келтирилган форма тушунчасини таoрифланг.

4. Предикатлар логикасидаги формула учун тщла келтирилган ёки айлантирилган (“предваренная”) нормал форма деганда нимани тушунасиз?

5. Формулалар тенг кучлилигининг аломатларини кщрсатиб беринг.

6. предикатлар ыандай соъада тенг кучли?

7. Р(x,y,z)=(x) (F(x)G(y)(F(z)G(y))) формулани келтирилган кщринишда ифодаланг.

8. Р(x,y,z)=(x) (F(x,y)G(y,z)(xy) формулани тщла келтирилган нормал форма кщринишда ифодаланг.