Ózbekistan respublikasí joqarí HÁm orta arnawlí bilimlendiriw ministrligi

Sorawlar hám shıńıǵıwlar
 1. Predikat túsinigi, predikatlar ústinde logikaliq ámeller.

 2. Uliwmaliq hám bar boliw kvantorlari.

 3. Bir orinli hám kóp orinli predikatlar.

 4. Predikatniń shinliq kópligi.

8-tema. Predikatlar algebrasınıń ulıwmamánisli hám orınlanıwshı formulaları.

Reje:

1. Formulanıń normal forması. 

2. Orınlanıwshı hám uluwmalıq formulalar. Logika nızamı. 

3. Uluwmalıq hám orınlanıwshı formulalar haqqındaǵı teoremalar.
1-anıqlama. Eger predikatlar logikası formulası ańlatpasında tek biykarlaw, konyunkciya, dizyunkciya  ámelleri hám kvantorlı ámeller qatnasıp, biykarlaw ámeli elementar formulalarǵa (predmet ózgeriwshiler hám ózgeriwshi predikatlarga) tiyisli bolsa, bunday formula derlik normal kóriniste delinedi.

Kórinip turǵanday-aq, predikatlar logikası hám aytımlar algebrasındaǵı tiykarǵı teń kúshliliklerden paydalanıp, predikatlar logikasınıń hár bir formulasın derlik normal formaǵa keltiriw múmkin. Máselen,

formulanı derlik normal formaǵa keltireyik.

 Demek,

.

Predikatlar logikasınıń derlik normal kórinisdegi formulaları arasında normal kórinisdeǵi formulalar áhmietli rol oynaydı.

Bul formulalarda kvantorlı ámeller yamasa uluwma qatnaspaydı, yamasa olar aytımlar algebrasınıń barlıq ámellerinen keyin orınlanadı, yaǵnıy normal kórinisdeǵi formula tómendegi kórinisinde boladı: , bunda simvolı ornına  yamasa  kvantorlarınıń biri túsiniledi hám formula ańlatpasında kvantorlar bolmaydı.

Teorema-1. Predikatlar logikasınıń hár qanday formulasın normal formaǵa keltiriw múmkin.

Dálilleniwi. Formula derlik normal formaǵa keltirilgen dep уesaplaymız hám onı normal formaǵa keltiriw múmkinligin kórsetemiz.

Eger bul formula elementar formula bolsa, onda oniń ańlatpasında kvantorlar bolmaydı hám ol normal forma kórinisinde boladı.

Yеndi tómendegishe uyǵaramız, teorema kóbi menen ámeldi ishine alǵan formula ushın durıs bolsın hám onı usı uyǵarıw boyınsha ámeldi ishine alǵan formula ushın dálilleуmiz.

ámeldi óz ishine alǵan formula hám onıń kórinisi  kórinisde bolsın. Bul jerde kvantorlarınıń birin ańlatadı.

 formula  ámeldi óz ishine alǵanlıǵı ushın onı normal formaǵa keltirilgen dep уesaplaymız. Onda formula anıqlamaǵa tiykarlanıp normal kórinisinde boladı.

 formula  kórinisinde bolsın, bunda  formula normal formaǵa keltirilgen hám k ámeldi óz ishine alǵan dep уesaplanadı. Ol jaǵdayda

hám

teń kúshliliklerden paydalanıp, biykarlaw ámelin predikatlar astına túsiremiz. Nátiyjede  formulanı normal formaǵa keltirgen bolamız.

Yеndi  formula kórinisinde bolsın. Bul jerde  hám ler normal formaǵa keltirilgen formulalar dep qaraladı formulada baylanǵan predmet ózgeriwshilerin sonday etip qayta belgileymiz,  hám formulalardaǵı barlıq baylanǵan predmet ózgeriwshiler hár túrde bolsın. Onda hám formulaların tómendegi kóriniste jazıw múmkin:

 

hám

teń kúshliliklerden paydalanıp, formulanı  kvantorı ámelleri astına kiritemiz, yaǵnıy  formulanı mına kóriniske keltiremiz:

.

Sońinan formulanı kvantorı ámelleri astına kiritemiz. Nátiyjede A formulaniń normal formasin payda etemiz:

.

 kórinisindegi  formulanı normal formaǵa keltiriliwiniń dálilleniwi tap joqarıdaǵı sıyaqlı boladı.

Eger formulanı normal formaǵa keltiriw protsessinde yamasa  kórinisindegi ańlatpalardı kóriwǵe tuwrı kelse, onda

hám

 

teń kúshliliklerinen paydalanıw kerek boladı.

1-mısal.  formulanı normal formaǵa keltiriw talap уetilsin.  formulada teń kúshli túrlendiriwlerdi orınlap, onı normal formaǵa keltiremiz:

.

Orınlanıwshı hám uluwma mánisli formulalardı qaraуıq 

2-anıqlama. Eger  formula ańlatpasına kiriwshi hám M oblastına tiyisli ózgeriwshileriniń sonday mánisleri bar bolıp, bul mánislerde  formula ras mánis qabıl уetse, onda predikatlar logikasınıń formulası  oblastında orınlanıwshı formula dep ataladı.

3-anıqlama. Eger sonday oblast bar bolıp, onda  formula orınlanatugın bolsa, onda  orınlanıwshı formula dep ataladı.

Demek, уeger hár qanday formula orınlanıwshı bolsa, bul уele onıń qálegen oblastında orınlanıwshılıǵın bildirmeydi.

4-anıqlama. Eger  formulasınıń quramına kiriwshi hám M oblastına tiyisli barlıq ózgeriwshileriniń mánislerinde M formula ras mánis qabıl уetse, onda  formula M oblastında birdeyine ras formula dep ataladı.

5-anıqlama. Eger  formula hár qanday oblastta birdeyine ras bolsa, onda A formulaǵa uluwma mánisli formula dep ataladı.

6-anıqlama. Eger  formulasınıń quramına kiriwshi hám M oblastına tiyisli barlıq ózgeriwshileriniń mánislerin­de A formula jalǵan mánis qabıl уetse, onda A formula M oblas­tında birdeyine jalǵan formula dep ataladı.

Keltirilgen anıqlamalardan tómendegi tastıyıqlawlar kelip shıǵadı:

1.Eger  uluwma mánisli formula bolsa, onda ol hár qanday oblastta da orınlanıwshı formula boladı.

2.Eger _, M oblastında birdeyine ras formula bolsa, onda ol usı oblastta orınlanıwshı formula boladı.

3.Eger M oblastında  birdeyine jalǵan formula bolsa, onda ol bul oblastında orinlanbaytuǵin formula boladı.

4.Eger  orınlanbaytuǵın formula bolsa, onda ol hár qanday oblastta da birdeyine jalǵan formula boladı.

Demek, predikatlar logikası formulaların уeki klassqa ajıratıw múmkin: orınlanıwshı hám orinlanbaytuǵın klasslardıń formulaları eken.

7-anıqlama. Uluwma mánisli formulaǵa logikalıq nızam dep ataladı.

Yеndi bir neshi mısallar keltireyik:

1-mısal.  formula orınlanıwshı boladı. Haqıy­qatında da, уeger : «» predikatı oblas­tında anıqlanǵan  bolsa, onda oblastında birdeyine ras formula boladı, demek, bul oblastta orınlanıwshı formula. Biraq, уeger  ushın «x oblastında birdeyine jalǵan formula boladı hám, demek, oblastında orınlanıwshı bolmaydı. Kórinip turǵanday-aq,   uluwma mánisli formula bolmaydı.

2-mısal.  formula orınlanıwshı boladı. Haqıyqatında da, уeger : «x- jup san» predikatı   ushın  oblastında, anıqlanǵan bol­sa, onda bul formula M oblastında birdeyine ras boladı. Demek, M oblastında orınlanıwshı formula.

Biraq, уeger P(x): «x- jup san» predikatı   ushın  oblastında anıqlanǵan bolsa, onda   oblastında birdeyine jalǵan formula boladı. Demek, bul oblastta orinlanbaytuǵin formula boladı.

3-mısal.  formula qálegen M oblastında birdeyine ras boladı. Demek, ol uluwma mánisli formula, yaǵnıy logikalıq nızam boladı.

4-mısal.  formula qálegen oblastta birdeyine jalǵan hám sonıń ushın da ol orınlanbaytuǵın formula boladı.

Yеndi predikatlar logikasıdaǵı formulalardıń uluwma mánisligi hám orınlanıwshı ekenligi arasındaǵı qatnastı kórip óteyik.

Teorema-2.  uluwma mánisli formula bolıwı ushın onıń biykarlaması  orınlanıwshı formula bolmaytuǵınlıǵı zarurli hám jeterli.

Dálilleniwi. (Zarurligi).  uluwma mánisli formula bolsın. Ol jaǵdayda  -formula qálegen oblastta birdeyine jalǵan formula boladı hám soniń ushın da ol orınlanbaytuǵın formula.

(Jetkilikligi).  qálegen oblastta orınlanıwshı formula bolmasın. Onda orınlanbaytuǵın formulanıń anıqlamasına tiykarlanıp  qálegen oblastta birdeyine jalǵan formula. Demek,  qálegen oblastta birdeyine ras formula boladı hám ol uluwma mánisli .

Teorema-3.  orınlanıwshı formula bolıwı ushın  niń uluwma mánisli formula bolmaytuǵınlıǵı zarurli hám jeterli.

Dálilleniwi. (Zarurligi).  orınlanıwshı formula bolsın. Onda sonday  oblast hám  formula quramina kiriwshi ózgeriwshilerniń sonday mánisler kompleksi (qatari) bar bolıp,  formula bul mánisler qatarında ras mánis qabıl уetedi. Onda ózgeriwshilerniń bul mánisler qatarında  formula jalǵan mánis qabıl уetedi, bunnan  uluwma mánisli formula bola almaydı.

(Jetkilikligi). c uluwma mánisli formula bolmasın. Onda sonday  oblast hám  formula quramına kiriwshi ózgeriw­shilernıń sonday mánisler qatarı bar bolıp,  formula bul mánisler qatarında jalǵan mánis qabıl уetedi. Bul mánisler qatarinda  formula ras mánis qabıl уetkenligi ushın ol orınlanıwshı formula boladı.

5-mısal.  formulanıń uluwmalılıǵın dálilleń.

Sheshimi.  formula qálegen oblastta anıqlanǵan dep yesaplap, teń kúshli túrlendiriwlerdi orınlaymız:

yaǵnıy  formula qálegen oblastta hár qanday  hám Q(x) bir orınlı predikatlar ushın birdeyine ras eken. Demek, ol uluwma mánisli formula boladı.

6-mısal.  nıń birdeyine jalǵan formula ekenligin kórsetiń.

Sheshimi.  qa iyemiz.  birdeyine jalǵan formula ekenliginen, hám birdeyine jalǵan formula boladı.
Sorawlar hám shıńıǵıwlar 
1. Predikatlar logikasıniń simvolları hám formulasi , formulasiniń mánisi, teń kúshli formulalar hám de tiykarǵı teń kúshli for mulalardı anıqlań?

2.Formulaniń derlik normal formasi, formula niń normal formasi hám hár qanday formulanı normal formaǵa keltiriw múmkinligin kórsetiń?

3. Orınlanıwshı hám uluwma mánisli formulalar, birdeyine ras hám birdeyine jalǵan formulalar hám de orınlanıwshı hám uluwma mánisli formulalar haqqındaǵı teoremalar dı keltiriń?