Aytimlar algebrasinin' tiykarg'i ten' kushlilikleri Reje

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 ueki 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ıu 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. Yelementar 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 uetedi.
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 uetip, 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 uemes.
1-teoremaǵa tiykarlanıp berilgen formula tómendegi JDNF ǵa teń kúshli boladı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.

Ádebiyat
Abduazizov A.A. Theoretical Phonetics of Modern English. T.,2007
2. Arnold I.V. ―The English word‖. M.1973.
3. Blokh M.Ya. A Cours e in Theoretical English Grammar. M.2002
4. Buranov J. Usupov U. Iriskulov M. Sadikov A. The Grammatical
Structure of English, Uzbek and Russian. T.1986
5. Buranov J., Muminov. O. ―A Practical Course in English
lexicology‖.T.1992.
6. Fries Ch. American English Grammar. NY.1958
7. Ilyish B.A. The Structure of Modern English. L.1971
8. Iriskulov M., Kuldashev A. Theoretical Grammar of the English Language.
T.2008
9. Iriskulov M.T., Shatunova A.S. English Phonetics. T., 2006
10. Sokolova M.A. English Phonetics. A Theoretical Course. M., 2004
11. Abduraimova B. va boshqalar. Ingliz tili amaliy grammatikasi.
T.2006
12. Anikin G.V. Mixalskaya N.P. «Ingliz adabiѐti tarixi».
M.,1985.
13. Baqoeva M., Muratova E., Ochilova M. Ingliz adabiѐti. T. :2010
14. Barxudarov L.S. Struktura prostogo predlojeniya
sovremennogo angliyskogo yazıka. M.1996
15. BoboxonovaT.A.Ingliztilistilistikasi.T.:Wqituvchi,1995.
16. Bwronov J.B. Ingliz va wzbek tillari qiѐsiy grammatikasi.
T.1973
17. Buranov J. Sravnitelnaya tipologiya angliyskogo i
tyurkskix yazıkov. M., Vısshaya shkola1983.
18. GalperinI.R.Stilistikasovremennogoangliyskogoyazıka.M.:Vısshayashk
ola,2004.