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

Sorawlar hám shınıǵıwlar
1.Keltirilgen formula dep nege aytamız?

2.Qosarlıq nızamı degen ne?

3.Qosarlı nızamı haqqındaǵı teoremanıń saldarın dálilleń.

3-tema. Jetilisken dizyunktiv normal forma (JDNF) hám jetilisken konyunktiv normal forma (JKNF). Qosarlıq principi hám qosarlıq nızamı.

Reje:

1. Normal formalar. Tolıq elementar dizyunkciya hám konyunkciyalar.

2. Dizyunktiv normal forma.DNF.Jetilisken dizyunktiv hám konyunktiv normal forma.JDNF, JKNF

Matematikalıq logikada teń kúshli túrlendiriwler orınlap, aytımlar algebrasınıń formulaların hár qıylı kóriniste jazıw múmkin. Máselen, formulanı yamasa kórinislerınde jaza alamız.

Logika algebrasınıń kontakt hám rele-kontaktli sxemalar, diskret texnikada qollanıwlarında hám matematikalıq logikanıń basqa máselelerinde formulalardıń normal formaları úlken áhmietke iye.

Tómendegi belgilewdi kiritemiz:

(1)

1-anıqlama. propozicional ózgeriwshiler hám 0 lerden dúzilgenn nabor bolsa, onda formula elementar konyunkciya delinedi (bunda propozicional ózgeriwshiler tákirarlanǵan bolıwı da múmkin).

Biz, bul paragrafda formulanı qısqasha kórnisinde jazamız.

1-mısal.

formulalar elementar konyunkciyalardan ibarat.

2-anıqlama. Elementar konyukciyalardıń hár qanday dizyunkciyası dizyunktiv normal forma (DNF) delinedi.

2-mısal.

formula 3.1-mısalında keltirilgen elementar konyukciyalardan dúzilgen DNF boladı.

3-anıqlama. Eger elementar konyukciyaǵa hár bir propozicional ózgeriwshi (biykarlaw belgisi qatnasqanlıǵın da itibarǵa alsaq) bir márteden artıq kirmegen bolsa, bunday elementar konyunkciya tuwrı elementar konyukciya delinedi.

3-mısal.

formulalar tuwrı elementar konyukciyalar boladı. Joqarıdaǵı 3.2-mısalda keltirilgen formulanıń dáslepki уeki aǵzası tuwrı elementar konyukciya boladı.

4-anıqlama. propozicional ózgeriwshilerden dúzilgen tuwrı elementar konyukciyadaǵı hár bir propozicional ózgeriwshi bul konyukciyaǵa tek bir mártebe kirgen bolsa, bunday elementar konyukciya ózgeriwshilerine qarata tolıq elementar konyukciya delinedi.

4-mısal. Elementar konyunkciyalar ózgeriwshilerden dúzilgen bolsın. Bul jaǵdayda formulalar tolıq elementar konyunkciyalar boladı.

5-anıqlama. Quramında bir qıylı elementar konyukciyalar bolmaǵan hám de barlıq elementar konyukciyalar ózgeriwshilerine qarata tuwrı hám tolıq bolǵan DNF ózgeriwshilerine qarata jetilisken dizyunktiv normal forma (JDNF) delinedi.

5-mısal.

formula ózgeriwshilerine qarata JDNF boladı.

Teorema-1. Aytımlar algebrasınıń BJ formula bolmaǵan qálegen formulası birden-bir JDNF ǵa teń kúshli boladı.

Dálilleniwi. – aytımlar algebrasınıń qálegen BJ formula bolmaǵan formulası bolsın. Demek, orınlanıwshı formula bolıp, ol propozicional ózgeriwshilerdiń mánisleriniń hesh bolmaǵanda bir ǵana naborında 1 mánisin qabıl etedi. formulani rasqa aylandırıwshı naborlar kópligi bolsın:

bunda boladı. Tómendegi DNF nı qarayıq:

(2)

Bul DNF nıń ádette JDNF ekenligi anıq, sebebi nıń elementleri hár qıylı naborlardan ibarat. Sonda

ekenligin kórsetiwimiz kerek. Meyli

bolsın. Bul jaǵdayda

boladı ( kópliginiń tańlanıwına tiykarlanıp). Endi

formulanıń

nabordaǵı mánisin yesaplayıq. (2) degi JDNF quramında

tolıq elementar konyukciya qatnasqan bolıp nıń nabordaǵı mánisin yesaplawda

aǵza payda boladı. (1) ge tiykarlanıp 1¹ =1 hám de boladı, sebebi . Demek, qanday bolıwına qaramastan (qattıу názer)

hám de

ibarat.

ge tiykarlanıp

boladı. Solay etip, ǵa tiyisli naborlarda berilgen formulası da, 1 mánisin qabıl qıladı eken.

bolǵan qálegen nabor bolsın. Bul jaǵdayda ol nabor ǵa kiriwshi qálegen nabordan hesh bolmaǵanda bir elementi menen parıq qıladı (bul naborlar tártiplengen naborlar ekenligin yesletip ótemiz). nıń  naborındaǵı mánisin yesaplawda payda bolatuǵın ańlatpada qatnasqan qálegen

(3)

aǵza da hesh bolmaǵanda bir ǵana ushın boladı. (1) ge tiykarlanıp hám bolǵanı ushın (3) ańlatpanıń mánisi 0 ge teń boladı. Bunnan

ekenligi kelip shıǵadı. bolǵanı ushın

demek, ǵa kirmegen naborlarda hám formulalar 0 mánisine iye eken. Solay etip, yaǵnıy formula (2) JDNF ǵa teń kúshli ekenligi kelip shıǵadı. formula birden-bir usılda JDNF ǵa jayılatuǵınlıǵı anıq, sebebi formula formulanıń mánisin 1 ge aylandırıwshı barlıq naborlar járdeminde jalǵız usılda ǵana payda etiledi.

Natiyje. Teń kúshli formulalar birqıylı JDNF ǵa iye.

Aytımlar algebrasınıń hár bir formulası yaki ózi keltirilgen formula, yaki onı oǵan teń kúshli keltirilgen formula menen almastırıw múmkin degen teoremaǵa tiykarlanıp, aytımlar algebrasınıń qálegen formulasınıń ózi keltirilgen formula boladı yamasa onı teń kúshli túrlendiriwler járdeminde keltirilgen formula kórnisine alıp keliw múmkin.

Biz, tómende hár qanday keltirilgen formulanı JDNF ǵa jayılıw algoritmin keltiremiz.

qálegen formula bolsın.

1-qádem. Eger keltirilmegen formula bolsa, onda oǵan 3.3-teoremasın qollanıp, ondaǵı implikaciya ámelleri joǵatıladı; payda bolǵan formulada tek ǵana biykarlaw, konyunkciya hám dizyunkciya ámelleri qatnasqan boladı.

2-qádem. Eger payda bolǵan formulada biykarlaw quramalı formula aldında qatnasqan bolsa, onda onı I, XII hám XIII teń kúshlilikler járdeminde sonday kóriniske túrlendiremiz, payda bolǵan formulada biykarlaw tek ǵana propozicional ózgeriwshilerge tiyisli boladı.

3-qádem. 2-qádemnen soń payda bolǵan formulanı VI-VII teń kúshlilikler járdeminde sonday kóriniske túrlendiriwimiz kerek, taza payda bolǵan formulada konyunkciya dizyunkciyadan aldın orınlansın, yaǵnıy natiyjede DNF payda bolsın.

4-qádem. Eger payda bolǵan DNF da bir neshe birqıylı elementar konyukciyalar qatnasqan bolsa, olardıń birewin qaldırıp, qalǵanları taslap jiberiledi (VIII teń kúshlilikke tiykarlanıp).

5-qádem. 4-qádemnen keyin payda bolǵan DNF da qatnasqan bazıbir elementar konyukciyada propozicional ózgeriwshi hám onıń biykarlaması qatnasqan bolsa, bunday elementar konyunkciya taslap jiberiledi (sebebi bunday elementar konyukciya BJ formula bolıp, XV hám XVII teń kúshliliklerine tiykarlanıp onı taslap jiberiledi).

6-qádem. Yеlementar konyukciyada bazıbir propozicional ózgeriwshiniń ózi yamasa onıń biykarlaması bir neshe mártebe qatnasqan bolsa, bul jaǵdayda olardan tek ǵana birewi qaldırılıp, qalǵanları taslap jiberiledi (IX teń kúshlilikke tiykarlanıp). Bul qádemnen keyin payda bolǵan DNF da barlıq elementar konyunkciyalar tuwrı elementar konyukciyalardan ibarat boladı.

7-qádem. Eger payda bolǵan DNF da tolıq emes elementar konyunkciya qatnasqan bolsa, onı tolıq elementar konyukciyaǵa aylandırıw ushın tómendegi kóriniste túrlendiriw orınlanadı:

Tolıq emes elementar konyunkciya bolsın. Bul jaǵdayda ol tuwrı elementar konyukciyanı oǵan teń kúshli

formula menen almastırıw múmkin. Eger jetispeytuǵın propozicional ózgeriwshi bir neshe bolsa, onda elementar konyukciyanı bir neshe kórinisindegi konyuktiv aǵza menen toltırıw kerek.

7-qádemnen soń payda bolǵan DNF da jáne birqıylı elementar konyukciyalar payda bolıwı múmkin. Bul jaǵdayda oǵan jáne 4-qádem qollanıladı. Bul algoritmdi qollanǵanda, álbette, kerekli orında II-V teń kúshliliklerinen paydalanıladı

6-mısal.

formulanıń JDNF sın jazıń.

Berilgen formula keltirilmegen bolǵanı ushın ondaǵı implikaciyanı dizyunkciya hám biykarlaw menen almastıramız:

Nátiyjede payda bolǵan formulada  ámeli quramalı formula aldında qatnasqan. Sonıń ushın oǵan de Morgan teń kúshlilikleri hám qos biykarlaw teń kúshliliklerin qollanamız:

Bul keltirilgen formulada dizyunkciya konyukciyadan aldın orınlanatuǵın aǵza bar; sonıń ushın distributivlik teń kúshliligin qollansaq, tómendegi DNF payda boladı:

Mına DNF da qatnasqan barlıq elementar konyunkciyalar tuwrı elementar konyukciyalar bolsa da, biraq tolıq elementar konyunkciyalar emes. Sonıń ushın tómendegi kórinistegi túrlendiriw orınlanadı:

nı

menen, dı

menen, nı

menen nı bolsa

menen almastıramız. Bunnan, nátiyjede teń kúshli formula payda boladı:

Kelip shıqqan formulaǵa jáne distributivlik qásietti qollansaq:

teń kúshliligine iye bolamız. Bundaǵı birqıylı elementar konyukciyalardı taslap jibersek, onda tomendegi aqırǵı nátiyjege kelemiz:

(4)

Teń kúshliliktiń oń tárepi berilgen formulanıń JDNF nan ibarat. Usı JDNF nı formulanıń shınlıq kestesi menen salıstırayıq:

1 1 1 1 0 0 0 0	1 1 0 0 1 1 0 0	1 0 1 0 1 0 1 0	0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	1 1 1 1 0 0 1 1	1 1 0 0 1 1 1 1	1 0 1 0 0 0 1 0	1 0 0 0 1 0 1 0	1 1 0 1 1 1 1 1

Bul kesteden kórinip turǵanday-aq: berilgen formula propozicional ózgeriwshilerdiń mánisleriniń

(1, 1, 1), (1, 1, 0), (1, 0, 0), (0, 1, 1), (0, 1, 0), (0, 0, 1)

hám (1, 1, 0) lerde 1 (ras) qabıl уetedi.

1-teoremaǵa tiykarlanıp berilgen formula tómendegi JDNF ǵa teń kúshli boladı:

(1) ge tiykarlanıp sońǵı ańlatpanı tómendegi kóriniste jazıw múmkin:

yamasa

yaǵnıy nátiyjede (4) niń oń tárepi payda boladı. Berilgen formulanıń jeti naborında 1 mánisine, bir naborında bolsa 0 mánisine iye, yaǵnıy, ol BR formula emes. (4) den kórinip turǵanday-aq, berilgen formulanıń JDNF sına jeti tolıq elementar konyukciya kiredi. Demek, tekserilip atırǵan formula BR formula bolsa, onıń JDNF sına tolıq elementar konyunkciya kiredi. Solay уetip, aytımlar algebrasınıń formulası BR formula ma yaki joqpa ekenligin anıqlaw ushın onı JDNF ǵa jayıp, bul JDNF dagı tolıq elementar konyunkciyalar sanın sanaw kerek: tolıq elementar konyunkciyalar sanı bolsa, berilgen formula BR formula, bolǵanda orınlanıwshı formula boladı. Eger bolsa, bul jaǵdayda berilgan formula BJ formula bolatuǵınlıǵı kelip shıǵadı.

7-mısal. Aytımlar algebrasınıń tiykarǵı teń kúshli formulalarınan paydalanıp, tómendegi formulanıń DNF (dizyunktiv normal forma) sın, KNF (konyuktiv normal forma) sın hám de onıń JDNF (jetilisken dizyunktiv normal forma) sın, JKNF (jetilisken konyunktiv normal forma) sın

formulanıń JDNF sın jazıń.

Bul formula keltirilmegen bolǵanı ushın ondaǵı implikatciya ámelin dizyunkciya hám biykarlaw menen almastıramız:

Berilgen formulasınıń JDNF (JKNF) ni tabıw ushın , hám de aytımlar algebrasınıń teń kúshli formulalarınan paydalanıp, tómendegige iye bolamız:

Joqarıdaǵı formulanıń konyuktiv normal formasın anıqlaymız:

Demek, berilgen formulası ushın

boladı eken.

Endi, bul formulasınıń JDNF hám JKNF sın shınlıq kestesi arqalı salıstırıp tabıw máselesin qarayıq. Bul jaǵdayda, berilgen formulada hám túrindegi úsh aytımlıq ózgeriwshi bar, yaǵnıy . Bunnan, shınlıq kestesindegi jollarınıń sanı ge teń bolatuǵınlıǵı kelip shıǵadı. Shınlıq kestesine qarap, TDNF (TKNF) nı tabıw ushın sońǵı baǵanada lerdi (lerdi) alamız hám olardıń aralarına konyukciya (dizyunkciya) qoyıp, hár bir aytımlıq ózgeriwshi yamasa onıń biykarlaması qatnasqan skobkalarda ańlatpalar payda boladı hám de onı konyukciya (dizyunkciya) menen baylanıstıramız. Bunda TDNF (TKNF) qaralıp atırǵan bolsa, onda propozicional ózgeriwshileriniń naborlarında bolsa ( bolsa) ózi, al bolsa ( bolsa) onıń biykarlamaların alamız. Mına :

1. TDNF nı tabıwda (1)

. TKNF nı tabıwda (2)

Onda berilgen formulanıń mánisler kestesi tómendegi kóriniske iye :

1 1 1 1 0 0 0 0	1 1 0 0 1 1 0 0	1 0 1 0 1 0 1 0	1 0 0 0 1 0 0 0	1 1 0 0 0 0 0 0	1 1 1 1 0 1 1 1	1 1 1 1 0 0 0 0

Bul kesteden kórinip turǵanday-aq: berilgen formula propozicional ózgeriwshilerdiń

mánisleriniń (1, 1, 1), (1, 1, 0), (1, 0, 1) hám (1,0,0) tórt orında 1 mánisine, tórt orında (0 1, 1), (0, 1, 0) , (0, 0, 1) hám (0,0,0) bolsa 0 mánisine iye, yaǵnıy, ol BR formula уemes.

1-teoremaǵa tiykarlanıp berilgen formula tómendegi JDNF ǵa teń kúshli boladı:

(1) ge tiykarlanıp sońǵı ańlatpanı tómendegi kóriniste jazıw múmkin:

1-teoremaǵa tiykarlanıp berilgen formula tómendegi JKNF ǵa teń kúshli boladı:

ge tiykarlanıp sońǵı ańlatpanı tómendegi kóriniste jazıw múmkin:

boladı.

Dara jaǵdayda, formulasınıń sın tabıw ushın nıń biykarlamasın anıqlap, oǵan qosarlıq nızamın paydalanamız:

Sonda, berilgen formulanıń jetilisken konyuktiv normal forması

túrine iye boladı.

Joqarıdaǵı 1–5 anıqlamalarda «konyukciya» sózin «dizyunkciya» sózi menen, «dizyunkciya» sózin «konyukciya» sózi menen almastırsaq, ol jaǵdayda «elementar dizyunkciya», «tolıq elementar dizyunkciya», «jetilisken konyuktiv normal forma ()» túsinikleri payda boladı.