Бетлер. Ten’ ku’shli formulalar ha’m wolardi’n’ tiykarg’i’ qa’siyetleri. Qosarli’q (yekilik) ni’zami’

U qa’legen formula bolsi’n.

1-qa’dem. Yeger U keltirilmegen formula bolsa, wonda wog’an 3.3­-

teoremasi’n qollani’p, wondag’i’ implikaciya a’melleri jog’ati’ladi’; payda bolg’an formulada tek g’ana biykarlaw, konyunkciya ha’m dizyunkciya a’melleri qatnasqan boladi’.

2-qa’dem. Yeger payda bolg’an formulada biykarlaw quramali’ formula aldi’nda qatnasqan bolsa, wonda woni’ I, XII ha’m XIII ten; ku’shlilikler ja’rdeminde sonday ko’riniske tu’rlendiremiz, payda bolg’an formulada biykarlaw tek g’ana propozicional wo’zgeriwshilerge tiyisli boladi’.

3-qa’dem. 2-qa’demnen son’ payda bolg’an formulani’ VI-VII ten’ ku’shlilikler ja’rdeminde sonday ko’riniske tu’rlendiriwimiz kerek, taza payda bolg’an formulada konyunkciya dizyunkciyadan aldi’n wori’nlansi’n, yag’ni’y natiyjede DNF payda bolsi’n.

4-qa’dem. Yeger payda bolg’an DNF da bir neshe birqi’yli’ elementar konyukciyalar qatnasqan bolsa, wolardi’n’ birewin qaldi’ri’p, qalg’anlari’ taslap jiberiledi (VIII ten’ ku’shlilikke tiykarlani’p).

5-qa’dem. 4-qa’demnen keyin payda bolg’an DNF da qatnasqan bazi’bir elementar konyukciyada propozicional wo’zgeriwshi ha’m woni’n’ biykarlamasi’ qatnasqan bolsa, bunday elementar konyunkciya taslap jiberiledi (sebebi bunday elementar konyukciya BJ formula boli’p, XV ha’m XVII ten’ ku’shliliklerine tiykarlani’p woni’ taslap jiberiledi).

6-qa’dem. Yelementar konyukciyada bazi’bir propozicional wo’zgeriwshinin’ wo’zi yamasa woni’n’ biykarlamasi’ bir neshe ma’rtebe qatnasqan bolsa, bul jag’dayda wolardan tek g’ana birewi qaldi’ri’li’p, qalg’anlari’ taslap jiberiledi (IX ten’ ku’shlilikke tiykarlani’p). Bul qa’demnen keyin payda bolg’an DNF da barli’q elementar konyunkciyalar tuwri’ elementar konyukciyalardan ibarat boladi’.

7-qa’dem. Yeger payda bolg’an DNF da toli’q yemes elementar konyunkciya qatnasqan bolsa, woni’ toli’q elementar konyukciyag’a aylandi’ri’w ushi’n to’mendegi ko’riniste tu’rlendiriw wori’nlanadi’:

…. ….

Toli’q yemes elementar konyunkciya bolsi’n. Bul jag’dayda wol tuwri’ elementar konyukciyani’ wog’an ten’ ku’shli

…. (A₁∨ A₁ ) ….

formula menen almasti’ri’w mu’mkin. Yeger jetispeytug’i’n propozicional wo’zgeriwshi bir neshe bolsa, wonda elementar konyukciyani’ bir neshe

A ∨ ko’rinisindegi konyuktiv ag’za menen tolti’ri’w kerek.

7-qa’demnen son’ payda bolg’an DNF da ja’ne birqi’yli’ elementar konyukciyalar payda boli’wi’ mu’mkin. Bul jag’dayda wog’an ja’ne 4- qa’dem qollani’ladi’. Bul algoritmdi qollang’anda, a’lbette, kerekli wori’nda II-V ten’ ku’shliliklerinen paydalani’ladi’

6-mi’sal.

(A ∨ ) ^ C⇒ (∨ ∨ B) ^ C

formulani’n’ JDNF si’n jazi’n’.

Berilgen formula keltirilmegen bolg’ani’ ushi’n wondag’i’ implikaciyani’ dizyunkciya ha’m biykarlaw menen almasti’rami’z:

(A ∨ ) ^ C ⇒ ( ∨ B) ^ C = ( ∨ ( ∨ B) ^ C.

Na’tiyjede payda bolg’an formulada - a’meli quramali’ formula (A ∨ ) ^ C aldi’nda qatnasqan. Soni’n’ ushi’n wog’an de Morgan ten’ ku’shlilikleri ha’m qos biykarlaw ten’ ku’shliliklerin qollanami’z:

( ∨ ( ∨ B) ^ C =

= ( ∨ ( ∨ B) ^ C =

= ∨ ^ ∨ ( ∨ B) ^ C =

= ∨ ^ ∨ ( ∨ B) ^ C .

Bul keltirilgen formulada dizyunkciya konyukciyadan aldi’n wori’nlanatug’i’n ag’za bar; soni’n’ ushi’n distributivlik ten’ ku’shliligin qollansaq, to’mendegi DNF payda boladi’:

∨ ^ ∨ ( ∨ B) ^ C =

= ∨ ^ ∨ ^C∨ B) ^ C .

Mi’na DNF da qatnasqan barli’q elementar konyunkciyalar tuwri’ elementar konyukciyalar bolsa da, biraq toli’q elementar konyunkciyalar yemes. Soni’n’ ushi’n to’mendegi ko’rinistegi tu’rlendiriw wori’nlanadi’:

∨B ni’

∧ B ∧ (C ∨ )

menen, C di’

(A ∨ ) ∧ (B ∧ ) ∨ С

menen, ^ C ni’

^ (B ∨ ) ^ C

menen B л C ni’ bolsa

(A v A) л B л C

menen almasti’rami’z. Bunnan, na’tiyjede ten’ ku’shli formula payda boladi’:

A л B v C v A л C v B л C = A л B л (C v C) v (A v A) л

л (B v B ) л C v A л (B v B ) л C v (A v A ) л B л C.

Kelip shi’qqan formulag’a ja’ne distributivlik qa’siyetti qollansaq:

A л B л (C v C) v (A v A) л (B v B) л C v A л (B v B) л

л C v (A v A) л B л C = A л B л C v A л B л C v A л

л B л C v A л B л C v A л B л C v A л B л C v A л B л

л C v A л B л C v A л B л C v A л B л C ten’ ku’shliligine iye bolami’z. Bundag’i’ birqi’yli’ elementar konyukciyalardi’ taslap jibersek, wonda tomendegi aqi’rg’i’ na’tiyjege kelemiz:

(A v B) л C ^ (A v B) л C = A л B л C v A л B л N v A л B л л N v A л B л C v A л B л N v A л B л C v A л B л N.

(4)

Ten’ ku’shliliktin’ won’ ta’repi berilgen formulani’n’ JDNF nan ibarat. Usi’ JDNF ni’ formulani’n’ shi’nli’q kestesi menen sali’sti’rayi’q:

A	B	C	A	B	A v B	A v B	(A v B) л N	(A v B) л С	(A v B) л С ^ ^ (A v B) л C
1	1	1	0	0	1	1	1	1	1
1	1	0	0	0	1	1	0	0	1
1	0	1	0	1	1	0	1	0	0
1	0	0	0	1	1	0	0	0	1

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

Bul kesteden ko’rinip turg’anday-aq: berilgen formula propozicional wo’zgeriwshilerdin’ ma’nislerinin’

(1, 1, 1), (1, 1, 0), (1, 0, 0), (0, 1, 1), (0, 1, 0), (0, 0, 1) ha’m (1, 1, 0) lerde 1 (ras) qabi’l yetedi.

teoremag’a tiykarlani’p berilgen formula to’mendegi JDNF g’a ten’ ku’shli boladi’:

AlBlCl v AlBlC0 v AlB0C0 v A0BlCl v A0BlC0 v

v A0B0Cl v A0B°C0.

ge tiykarlani’p son’g’i’ an’latpani’ to’mendegi ko’riniste jazi’w mu’mkin:

ABC v ABC v ABC v ABC v ABC v ABC v ABC

yamasa

A л B л C v A л B л C v A л B л C v A л B л C v

v A л B л C v A л B л C v A л B л C, yag’ni’y na’tiyjede (4) nin’ won’ ta’repi payda boladi’. Berilgen formulani’n’ jeti nabori’nda 1 ma’nisine, bir nabori’nda bolsa 0 ma’nisine iye, yag’ni’y, wol BR formula yemes. (4) den ko’rinip turg’anday-aq, berilgen formulani’n’ JDNF si’na jeti toli’q elementar konyukciya kiredi. Demek, tekserilip ati’rg’an U(Aj,....,An) formula

BR formula bolsa, woni’n’ JDNF si’na 2n toli’q elementar konyunkciya kiredi. Solay yetip, ayti’mlar algebrasi’ni’n’ U(A1,....,An) formulasi’ BR formula ma yaki joqpa yekenligin

ani’qlaw ushi’n woni’ JDNF g’a jayi’p, bul JDNF dagi’ toli’q elementar konyunkciyalar sani’n sanaw kerek: toli’q elementar konyunkciyalar

sani’ 5 = 2n bolsa, berilgen formula BR formula, 0 < 5 < 2n bolg’anda wori’nlani’wshi’ formula boladi’. Yeger 5 = 0 bolsa, bul jag’dayda berilgan formula BJ formula bolatug’i’nli’g’i’ kelip shi’g’adi’.

mi ’sal. Ayti’mlar algebrasi’ni’n’ tiykarg’i’ ten’ ku’shli formulalari’nan paydalani’p, to’mendegi formulani’n’ DNF (dizyunktiv normal forma) si’n, KNF (konyuktiv normal forma) si’n ha’m de

woni’n’ JDNF (jetilisken dizyunktiv normal forma) si’n, JKNF (jetilisken konyunktiv normal forma) si’n

A = a(bc ^ ab) formulani’n’ JDNF si’n jazi’n’.

Bul formula keltirilmegen bolg’ani’ ushi’n wondag’i’ implikatciya a’melin dizyunkciya ha’m biykarlaw menen almasti’rami’z:

A = a(bc ^ ab) = a(bc v ab) = a(b v c v ab) = ab v ac v ab = DNF A

Berilgen A = a (bc ^ ab) formulasi’ni’n’ JDNF (JKNF) ni tabi’w

ushi’n x v x = 1 , x л 1 = x ha’m de x v x v x v v x = x

ayti’mlar algebrasi’ni’n’ ten’ ku’shli formulalari’nan paydalani’p, to’mendegige iye bolami’z:

A = DNF A = ab v ac v ab = ab(c v c) v ac(b v b) v ab(c v c) = abc v abc v abc v v abc v abc v abc = abc v abc v abc v abc = JDNF A

Joqari’dag’i’ formulani’n’ konyuktiv normal formasi’n ani’qlaymi’z:

A = a(bc ^ ab) = ab v ac v ab = a(b v c v b) = a((b v b) v c) = a(1 v c) =

= a x 1 = a = KNF A

A = KNF A = a = a v (b л b) = (a v b) л (a v b) = ((a v b) v (c л c)) л ((a v b) v v (c л c)) = (a v b v c) л (a v b v c) л (a v b v c) л (a v b v c) = JKNF A Demek, berilgen A = a(bc ^ ab) formulasi’ ushi’n

JDNF A = abc v abc v abc v abc

JKNF A = (a v b v c) л (a v b v c) л (a v b v c) л (a v b v c) boladi’ yeken.

Yendi, bul A = a(bc ^ ab) formulasi’ni’n’ JDNF ha’m JKNF si’n shi’nli’q kestesi arqali’ sali’sti’ri’p tabi’w ma’selesin qarayi’q. Bul jag’dayda, berilgen formulada a, b ha’m c tu’rindegi u’sh ayti’mli’q wo’zgeriwshi bar, yag’ni’y n = 3. Bunnan, shi’nli’q kestesindegi jollari’ni’n’ sani’ 23 = 8 ge ten’ bolatug’i’nli’g’i’ kelip shi’g’adi’.

S

(1)

(2)

TDNF A ni’ tabi’wda Aa 2 . TKNF A ni’ tabi’wda Ba ■


| yeger a = 1 bolsa, A, [yeger a = 0 bolsa, A.

yeger a = 1 bolsa, B yeger a = 0 bolsa, B.

hi’nli’q kestesine qarap, TDNF (TKNF) ni’ tabi’w ushi’n son’g’i’ bag’anada 1 lerdi (Olerdi) alami’z ha’m wolardi’n’ aralari’na konyukciya (dizyunkciya) qoyi’p, ha’r bir ayti’mli’q wo’zgeriwshi yamasa woni’n’ biykarlamasi’ qatnasqan skobkalarda an’latpalar payda boladi’ ha’m de woni’ konyukciya (dizyunkciya) menen baylani’sti’rami’z. Bunda TDNF (TKNF) qarali’p ati’rg’an bolsa, onda propozicional wo’zgeriwshilerinin’ naborlari’nda 1 bolsa (0 bolsa) wo’zi, al 0 bolsa (1 bolsa) woni’n’ biykarlamalari’n alami’z. Mi’na :

Wonda berilgen formulani’n’ ma’nisler kestesi to’mendegi ko’riniske iye :

a	b	c	b л c	a л b	bc ^ ab	A = a (bc ^ ab)
1	1	1	1	1	1	1
1	1	0	0	1	1	1
1	0	1	0	0	1	1
1	0	0	0	0	1	1
0	1	1	1	0	0	0
0	1	0	0	0	1	0
0	0	1	0	0	1	0
0	0	0	0	0	1	0

Bul kesteden ko’rinip turg’anday-aq: berilgen formula propozicional wo’zgeriwshilerdin’

ma’nislerinin’ (1, 1, 1), (1, 1, 0), (1, 0, 1) ha’m (1,0,0) to’rt wori’nda 1 ma’nisine, to’rt wori’nda (0 1, 1), (0, 1, 0) , (0, 0, 1) ha’m (0,0,0) bolsa 0 ma’nisine iye, yag’ni’y, wol BR formula yemes.

teoremag’a tiykarlani’p berilgen formula to’mendegi JDNF g’a ten’ ku’shli boladi’: alblcl v alblc0 v alb0c1 v alb0c0

(1) ge tiykarlani’p son’g’i’ an’latpani’ to’mendegi ko’riniste jazi’w

mu’mkin:

JDNF A = abc v abc v abc v abc

teoremag’a tiykarlani’p berilgen formula to’mendegi JKNF g’a ten’ ku’shli boladi’:

(a0 v b1 v c1) л (a0 v b1 v c0) л (a0 v b0 v c1) л (a0 v b0 v c0) ge tiykarlani’p son’g’i’ an’latpani’ to’mendegi ko’riniste jazi’w mu’mkin:

JKNF A = (a v b v c) л (a v b v c) л (a v b v c) л (a v b v c) boladi’.

Dara jag’dayda, A = a(bc ^ ab) formulasi’ni’n’ JKNF si’n tabi’w ushi’n JDNF A ni’n’ biykarlamasi’n ani’qlap, wog’an qosarli’q ni’zami’n paydalanami’z:

JDNF A = abcvabcvabcvabc

JDNF A = abc v abc v abc v abc

Sonda, berilgen formulani’n’ jetilisken konyuktiv normal formasi’

JKNF A = (a v b v c) л (a v b v c) л (a v b v c) л (a v b v c) tu’rine iye boladi’.

Joqari’dag’i’ 1-5 ani’qlamalarda «konyukciya» so’zin «dizyunkciya» so’zi menen, «dizyunkciya» so’zin «konyukciya» so’zi menen almasti’rsaq, wol jag’dayda «elementar dizyunkciya», «toli’q elementar dizyunkciya», «jetilisken konyuktiv normal forma (JKNF)» tu’sinikleri payda boladi’.

Sorawlar ha’m shi’ni’g’i’wlar

Formulalardi’n’ normal formasi’ dep nege aytami’z?

Formulalardi’n’ dizyunktiv ha’m konyunktiv normal formalari’n an’lati’n’.

Formulalardi’n’ toli’q dizyunktiv ha’m konyunktiv normal formalarg’a keltiriw algoritimin du’zin’.

To’mendegi formulalardi’ KNF ko’rinisine keltirin’.

x л (x ^ y)

(xy ^ x) ^ (xy ^ y)

(x ^ y) ^ (y ^ x)

(x v z) ^ y л z

(x v y ^ x л z) ^ (x ^ x) v y л z

(ab ^ bc) ^ ((a ^ b) ^ (c ^ b))

n) (a ^ c) ^ (b ^ a)

w) (a ^ b ) ^ (bc ^ ac)

Joqari’da keltirilgen formulalardi’ DNF ko’rinisine keltirin’.

To’mendegi formulalardi’ DNF ko’rinisine keltirin’ birdeyine jalg’an yamasa jalg’an yemesligin ani’qlan’.

1

a)	xy o x v xy
b)	(x o y) л (xy v xy)
c)	xy ^ (x ^ y)
d)	xy ^ (x ^ y)
n)	x v y ^ z
k)	(x ^ z)(y ^ z) ^ (x ^ y)

ha’m 3 ma’selelerde keltirilgen formulalardi’ JDNF ha’m JKNF ko’rinisine keltirin’.

Shi’nli’q kestesinen f(x, y, z), f2 (x,y, z), f (x,y, z),

f4(x,y, z), f5(x,y, z), f6(x,y, z) funkciyalardi’ an’lati’wshi’ formu­lalardi’ tabi’n’ ha’m wolardi’ a’piwayi’lasti’ri’n’:

x	У	z	fi( x, y, z)	f 2 (^ У, z)	f3( x ^ z	f4(y> z)=	f 5 (x, y, z )	f6( x y, z)
1	1	1	0	1	1	1	0	1
1	1	0	1	1	1	0	1	0
1	0	1	1	0	0	1	0	0
1	0	0	1	0	0	1	1	1
0	1	1	0	0	0	0	1	0
0	1	0	0	1	1	0	0	1
0	0	1	1	0	1	1	1	1
0	0	0	0	0	0	0	0	1

To’mendegi qi’sqa normal formadag’i’ formulalardi’n’ shi’nli’q kestesin du’zin’ ha’m wolardi’ a’piwayi’lasti’ri’n’.

a) xy v xy v xy v) (x v y)(x v y)(x v y)

s) xyz v xyz v xyz k) (x v y v z)(x v y v z)(x v y v z) .

Bir, уеki ha’m u’sh argumentli ha’r qanday birdeyine ras bolg’an funkciyalardi’n’ JDNF ko’rinisin tabi’n’.