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

4-mısal.

formulanıń barlıq naborlardaǵı mánislerin shınlıq kestesi járdeminde yesaplań.

Bul formulanıń úles formulaları tómendegishe boladı:

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 1 1 0 0 1 1	1 1 1 1 0 0 1 1	1 0 1 0 0 0 0 0	1 0 1 0 0 0 1 0	1 1 1 1 1 1 0 1

5-anıqlama. Eger aytımlar algebrasınıń

formulası propozicional ózgeriwshilerdiń mánisleriniń barlıq naborlarında 1 mánisin qabıl уetse (ras bolsa), bunday formula birdeyine ras formula (qısqasha BR formula), yamasa logikalıq nızam delinedi.

5-mısal.

formulasınıń logikalıq nızam ekenin kórsetiw qıyın emes.

6-anıqlama. Egeraytımlar algebrasınıń

formulası propozicional ózgeriwshilerdiń mánisleriniń barlıq naborlarında 0 mánis qabıl etse (jalǵan bolsa) bunday formula birdeyine jalǵan formula (qısqasha BJ formula) delinedi.

6-mısal. formulası BJ formula ekenligin kórsetemiz:

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

7-anıqlama. Eger aytımlar algebrasınıń

formulası propozicional ózgeriwshilerdiń mánisleriniń hesh bolmaǵanda bir naborında 1 mánisin qabıl etse, bunday formula orınlanıwshı formula delinedi.

4-mısalda keltirilgen formula orınlanıwshı ekenligi anıq.

4, 5, 6.–anıqlamalardan kórinip turǵanday-aq, BR formulanıń biykarlaması BJ formula hám kerisinshe, BJ formulanıń biykarlaması BR formula boladı. Bunnan tısqarı, hár qanday BR formula orınlanıwshı formula bolatuǵınlıǵı kelip shıǵadı.

7-mısal. formulasınıń birdeyine jalǵan formula ekenin kórsetiń.

Sheshiw.

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

Demek, birdeyine jalǵan formula eken.

8-mısal. formulasınıń orınla­nıwshı formula ekenin kórsetiń. Sheshiliwi.

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

Demek, orınlanıwshı formula eken.

Sorawlar hám shınıǵıwlar
1.Tómendegi gáplerdiń arasınan qaysıları aytım bolatuǵının anıqlań.

a)	Saat neshe ?
b)	Qálegen adamnıń ájaǵası boladı;
c)	Tomat sokini ishiń!
d)	Nókis-Qaqalpaqstannıń paytaxtı;
e)
f)	Hesh bir adam 1000 kg artıq уemes;
k)	Ay Marstıń joldası;
l)	;
m)

2. Aytım dep nege aytamız?.

3. Aytımlar ústinde logikalıq operaciyalarǵa mısallar keltiriń?
2-tema. Ulıwmamánisli hám orınlanıwshı formulalar. Ulıwmamánisli formulalar payda etiw qaǵıydaları. Aytımlar algebrasınıń funkciyaları.

Reje:

1. Teń kúshli formulalar.

2. Teń kúshli keltirilgen formula.

3. Qosarlıq (ekilik) nızamı. Qosarlıq nızamı haqqındaǵı teoremalar
1- anıqlama. Eger aytımlar algebrasınıń

hám

formulaları propozicional ózgeriwshilerdiń mánisleriniń barlıq naborlarında bir qıylı mánisti qabıl etetuǵın bolsa, bul formulalar teń kúshli formulalar delinedi hám ol kórnisinde jazıladı.

1-mısal.

hám

formulaları teń kúshli formulalar ekenligin kórsetemiz:

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	1 1 0 0 1 1 1 1	1 1 0 0 1 1 1 1	1 0 0 0 1 0 1 0	1 0 0 0 1 0 1 0

Eger hám formulalar teń kúshli bolsa, ol jaǵdayda  hám  lar BR formula bolıwı zárúr hám jeterli. Kerisinshe, qanday da bir hám (bir qıylı propozicional ózgeriwshilerge iye bolǵan) formulalar ushın  hám  lar BR formulalar bolsa, ol jaǵdayda  boladı.

hám

formulalar teń kúshli formulalar ekenligin kórseteyik:

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

Solay etip, bul teń kúshliliklerden kórinip turǵanday-aq,  bolıwı ushın  formula BR formula bolıwı kerek eken. Teń kúshlilik qatnası ekvivalent qatnas boladı, yaǵnıy bul qatnas:

1. -refleksivlik.

2. Eger  bolsa, onda  boladı-simmetriyalı hám de

3. Eger  hám bolsa, onda boladı-tranzitivlik qásietlerge iye.

Teorema-1. - aytımlar algebrasınıń bazıbir formulası, onıń úles formulası bolsın. Eger bolsa, onda

boladı.

Dálilleniwi. bolǵanı ushın hám formulalarda qatnasqan propozicional ózgeriwshilerdiń mánisleriniń barlıq naborlarında bir qıylı mánislerge yerisedi. hám formulalardıń mánisleri 1 yamasa 0 bolǵanı ushın ol

yamasa

payda boladı. Bul bolsa

ekenin kórsetedı.

Teorema-2.

hám

lar hám formulalarınıń hár birinde qatnasqan barlıq propozicional ózgeriwshiler, al

ler bolsa, qálegen formulalar bolsın. Bul jaǵdayda

boladı; bunda hár bir propozicional ózgeriwshi berilgen teń kúshlilikte neshe jerde qatnasqan bolsa, sonsha jerde sáykes formula menen almastırıladı.

Dálilleniwi.

teń kúshlilikte qatnasqan hár bir propozicional ózgeriwshi 1 yamasa 0 mánis qabıl etedi. formula da ózinde qatnasqan propozicional ózgeriwshilerdiń mánisleriniń barlıq naborlarında 1 yamasa 0 mánis qabıl etedi. formula quramında qatnasqan propozicional ózgeriwshiler

bolsın.

bul propozicional ózgeriwshilerdiń mánisleriniń naborlarınan biri hám de

,

formulalarnıń nabordaǵı mánisler naborı bolsın. Uzınlıǵı bolǵan nabor

propozicional ózgeriwshiler qabıl etetuǵın mánisleriniń naborları arasında bar boladı. hám formulalar nabordıń hár birinde bir qıylı mániske iye bolǵanlıǵı ushın olar naborında da bir qıylı mánis qabıl etedi.

Joqarıda dálillengen teoremalardan tómendegishe nátiyjeler kelip shıǵadı.

Eger

hám

bolsa, ol jaǵdayda

1)

2)

3)

4)

5) (yamasa ).

2-anıqlama. Eger formulasınıń quramında tek konyunkciya, dizyunkciya hám biykarlaw ámelleri qatnasqan bolıp, biykarlaw ámeli propozicional ózgeriwshilerge ǵana tiyisli bolsa, ol jaǵdayda bunday formula keltirilgen formula delinedi.

2-mısal.

keltirilgen formula boladı, biraq

keltirilgen formula emes, sebebi bul formulada implikaciya ámeli qatnasıwı menen birgelikte biykarlaw ámeli quramalı formula ǵa tiyisli boladı.

Teorema-3. 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.

Bul teoremanı dálillew ushın aytımlar algebrasınıń teń kúshlilikleri menen tanısıp shıǵamız. Aytımlar algebrasınıń teń kúshlilikleri tómendegiler:

I.
II.
III.
IV.
V.
VI.
VII.
VIII.
IX.
X.
XI.
XII.
XIII.
XIV.
XV.
XVI.	a) , b) , c) , d)
XVII.

Bul teń kúshliliklerdiń orınlı ekenligin shınlıq kestesi járdeminde ańsat ǵana tekserip kóriw múmkin. Máselen, XIII teń kúshlilik ushın shınlıq kestesin keltireyik:

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

II-XI, XIV-XVI teń kúshliliklerdi payda уetiwshi formulalar keltirilgen formulalar ekenligi anıq (propozicional ózgeriwshiler hám logikalıq konstantalar keltirilgen formula yesaplanadı).

Bunnan tısqarı,

(1)

teń kúshliligi orınlı ekenligin shınlıq kestesin dúzip kórsetiw qıyın emes. Joqarıda

orınlı ekenligi kórsetilgen уedi. İmplikaciyanı biykarlaw hám dizyunkciya menen almastırıw múmkin ekenliginen tómendegi teń kúshlilikti payda etemiz:

(2)

Demek,

hám

formulalar keltirilgen formulalar menen almastırılıwı múmkin eken. I, XII, XIII teń kúshlilikler qos biykarlaw hám de dizyunkciya hám konyunkciyalardıń biykarlamaların qalay keltirilgen formulalar menen almastırıw múmkin ekenligin kórsetedi.

Endi 3-teoremanıń dálilleniwin keltiremiz. Eger formulanıń ózi keltirilgen formula bolsa, ol jaǵdayda teorema dálillengen boladı.

Eger formula quramında implikaciya hám ekvivalensiya ámelleri qatnasqan bolsa, olardı (1) hám (2) teń kúshlilikler járdeminde almastırıw múmkin; formula quramında kórinisindegi úles formula qatnasqan bolsa, onı menen, yamasa kórnisindegi úles formula qatnasqan bolsa, olardı sáykes túrde

hám

formulalar menen almastırıw múmkin. Bul protsesti jeterli mártebe tákirarlap, aqırında formulaǵa teń kúshli bolǵan keltirilgen formulaǵa iye bolamız.

Solay etip, 3-teoremaǵa tiykarlanıp aytımlar algebrasınıń hár bir formulasın tiykarǵı hám basqa teń kúshlilikler járdeminde almastırıp, olarǵa teń kúshli bolǵan formulalar payda etiw múmkin. Bunday túrlendiriwler bazıbir máselelerdi sheshiwde keń kólemde qollanıladı. Biz, endi formulalardı túrlendiriwge baylanıslı mısallar keltiremiz.

3-mısal.

formulanı túrlendiriń hám ápiwayılastırıń.

Demek, berilgen formula BR formula eken. Meyli

aytımlar algebrasınıń bazıbir keltirilgen formulası bolsın, yaǵnıy bul formulada tek ǵana hám  ámelleri qatnasqan bolsın. Aldıńǵı paragrafda aytımlar algebrasınıń qálegen formulasın keltirilgen formula kórinisinde teń kúshli túrlendiriwler járdeminde keltiriw múmkinligi dálillengen yedi. Sonıń ushın joqarıdaǵı formulanı aytımlar algebrasınıń qálegen formulası dep qarawımız múmkin.

3-anıqlama. Eger

(3)

hám

formulaları bir-birinen  nı  ǵa,  nı bolsa  ǵa túrlendiriw járdeminde payda etilse, ol jaǵdayda bunday formulalar óz-ara qosarlı formulalar delinedi.

4-mısal.

formulası

formulaǵa qosarlı boladı.

Teorema-4.

hám

formulaları óz-ara qosarlı bolıp,

ler olardıń quramına kirgen barlıq propozicional ózgeriwshiler bolsa, onda bul jaǵdayda

(4) boladı.

Teoremanı dálillewden aldın formulanıń rangi túsinigin kiritemiz.

4-anıqlama. formulaǵa kirgen barlıq logikalıq ámeller sanı usı formulanıń rangi delinedi hám menen belgilenedi; bunda propozcional ózgeriwshilerdiń rangi 0 ge teń dep уesaplanadı.

5-mısal.

Sebebi bul formulaǵa 5 logikalıq ámel

lar qatnasqan.

Teoremanıń dálilleniwi. Eger bolsa, onda

yaki ti menen almastırsaq ,

payda boladı.

Aytayıq, rangi bolǵan barlıq formulalar ushın (4) orınlı bolsın. Bul jaǵdayda rangi bolǵan formula ushın da (4) qatnası orınlı ekenligin kórsetemiz. keltirilgen formula bolǵanlıǵı ushın ol tómendegi kóriniske iye bolıwı múmkin:

1)

2)

3) hám bolǵanlıqtan, pikirimizge tiykarlanıp

(5)

(6)

bolatuǵınlıǵı kelip shıǵadı.

Bunnan, hám formulalarǵa qosarlı bolǵan formulalar sáykes túrde hám boladı.

hám

bolǵanlıqtan

hám

ekenligi kelip shıǵadı. (5) hám (6) nı уesapqa alsaq, 2.1-teoremanıń nátiyjesine tiykarlanıp

qatnasların payda etemiz, yaǵnıy 2) hám 3) jaǵdaylar ushın

(7)

kelip shıǵadı.

Endi bolsın. Bul jaǵdayda

bolǵanı ushın, pikirimizge tiykarlanıp

boladı.

Demek,

yamasa

boladı. bolǵanlıǵı ushın (7) ge tiykarlanıp

ekenligi kelip shıǵadı .

4-teoremaǵa tiykarlanıp qosarlıq (ekilik) nızamı dep atalıwshı teoremanı dálillew múmkin.

Teorema-5. Eger bolsa, onda boladı.

Dálilleniwi. 4-teoremaga tiykarlanıp:

yamasa

(8)

boladı.

Teń kúshlilik anıqlamasına kóre hám formulaları propozcional ózgeriwshilerdiń mánisleriniń barlıq naborlarında bir qıylı mánislerge iye bolǵanlıǵı ushın

da orınlı boladı. Bul jaǵdayda

(9)

ekenligi kelip shıǵadı.

(8) hám (9) dan bolatuǵınlıǵın kóriwge boladı.

5-anıqlama. Eger formulası ushın

orınlı bolsa, onda bunday formula óz-ózine qosarlı formula delinedi.

6-mısal.

formulası óz-ózine qosarlı formula boladı. Haqıyqatında da, bul formulasına qosarlı tómendegi

formula boladı. Buǵan teń kúshli túrlendiriwlerdi qollansaq, onda

bolatuǵınlıǵı kelip shıǵadı.

7-mısal. formulasınıń teń kúshli formula ekenin kórsetiń.

Sheshiw 1-jol : boladı.

2-jol: Mánisler kestesi arqalı tómendegishe boladı.

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

Demek teń kúshli formula eken.