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

31-70 бетлер.

§2. Ten’ ku’shli formulalar ha’m wolardi’n’ tiykarg’i’ qa’siyetleri. Qosarli’q (yekilik) ni’zami’

Ten’ ku’shli formulalar. Ten’ ku’shli keltirilgen formula. Qosarli ’q (yekilik) ni’zami’. Qosarli’q ni’zami’ haqqi’ndag’i’ teoremalar

ani ’qlama. Yeger ayti’mlar algebrasi’ni’n’

U (A₁ ,A₂,...., A_n)

ha’m

B (A₁, A₂,...., A_n)

formulalari’ propozicional wo’zgeriwshilerdin’ ma’nislerinin’ barli’q naborlari’nda bir qi’yli’ ma’nisti qabi’l yetetug’i’n bolsa, bul formulalar ten’ ku’shli formulalar delinedi ha’m wol U = B ko’rnisinde jazi’ladi’.

1-mi ’sal.

U(A, B, C) ⇔ (A ⇒ B) ^ C

ha’m

B(A, B, C) ⇔ (A ∨B) ^ C

formulalari’ ten’ ku’shli formulalar yekenligin ko’rsetemiz:

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

0

0

0

1

1

1

0

0

Yeger U ha’m B formulalar ten’ ku’shli bolsa, wol jag’dayda U ⇒ B ha’ m B ⇒ U lar BR formula boli’wi’ za’ru’r ha’m jeterli. Kerisinshe, qanday da bir U ha’m B (bir qi’yli’ propozicional wo’zgeriwshilerge iye bolg’an) formulalar ushi’n U ⇒ B ha’m B ⇒ U lar BR formulalar bolsa, wol jag’dayda U = B boladi’.

A ~ B

ha’m

(A ⇒ B) ^ (B ⇒ A)

formulalar ten’ ku’shli formulalar yekenligin ko’rseteyik:

A	B	A ⇒ B	B ⇒ A	A ~ B	(A ⇒ B) ^ (B ^⇒A)
1	1	1	1	1	1
1	0	0	1	0	0
0	1	1	0	0	0
0	0	1	1	1	1

Solay yetip, bul ten’ ku’shliliklerden ko’rinip turg’anday-aq, U ≡ B boli’wi’ ushi’n U ~B formula BR formula boli’wi’ kerek yeken. Ten’ ku’shlilik qatnasi’ ekvivalent qatnas boladi’, yag’ni’y bul qatnas:

1. 
   U ≡ U -refleksivlik.
   
2. 
   Yeger U ≡ B bolsa, onda B ≡ U boladi’-simmetriyali’ ha’m de
   
3. 
   Yeger U ≡ B ha’m B ≡ G bolsa, wonda U ≡ G boladi’- tranzitivlik qa’siyetlerge iye.
   

Teorema-1. U(B)- ayti’mlar algebrasi’ni’n’ bazi’bir formulasi’, B woni’n’ u’les formulasi’ bolsi’n. Yeger B ≡ G bolsa, wonda

U (B) ≡ U (G)

boladi’.

Da’lilleniwi. B ≡ G bolg’ani’ ushi’n B ha’m G formulalarda qatnasqan propozicional wo’zgeriwshilerdin’ ma’nislerinin’ barli’q naborlari’nda bir qi’yli’ ma’nislerge yerisedi. B ha’m G formulalardi’n’ ma’nisleri 1 yamasa 0 bolg’ani’ ushi’n wol

U (1) ≡ U (1)

yamasa

U(0) ≡ U(0)

payda boladi’. Bul bolsa

U(B) ≡ U(G)

yekenin ko’rsetedi’.

Teorema-2.

U (4,...., An) - B( 4,...., A„),

Aj, A2,...., An

ha’m

B (Aj, A2,...., An)

lar U ha’m B formulalari’ni’n’ ha’r birinde qatnasqan barli’q propozicional wo’zgeriwshiler, al

Gj, G2,...., Gn

ler bolsa, qa’legen formulalar bolsi’n. Bul jag’dayda

U (Gj,...., Gn ) = B(Gj,...., Gn)

boladi’; bunda ha’r bir At(i = 1, n) propozicional wo’zgeriwshi berilgen ten’ ku’shlilikte neshe jerde qatnasqan bolsa, sonsha jerde sa’ykes Gi formula menen almasti’ri’ladi’.

Da ’lilleniwi.

U (Aj,...., An) - B( Aj,...., An)

ten’ ku’shlilikte qatnasqan ha’r bir propozicional wo’zgeriwshi j yamasa 0 ma’nis qabi’l yetedi. Gt (i = j, n) formula da wo’zinde qatnasqan propozicional wo’zgeriwshilerdin’ ma’nislerinin’ barli’q naborlari’nda j yamasa 0 ma’nis qabi’l yetedi. Gt (i = 1, n) formula qurami’nda qatnasqan propozicional wo’zgeriwshiler

Bj, B2 , ..., Bk

bolsi’n.

(aJ,a2,...., ak )

bul propozicional wo’zgeriwshilerdin’ ma’nislerinin’ naborlari’nan biri ha’m de

(e в2,...., Pn Д

Gi, 02,...., Gn

formulalami’n’ (a1,a2,....,ak) nabordag’i’ ma’nisler nabori’ bolsi’n. Uzi’nli’g’i’ n bolg’an (Д,P2,....,Pn) nabor

A1, A2,...., An

propozicional wo’zgeriwshiler qabi’l yetetug’i’n ma’nislerinin’

naborlari’ arasi’nda bar boladi’. U ha’m B formulalar 2n nabordi’n’ ha’r birinde bir qi’yli’ ma’niske iye bolg’anli’g’i’ ushi’n wolar (Д, P2,...., Pn) nabori’nda da bir qi’yli’ ma’nis qabi’l yetedi.

Joqari’da da’lillengen teoremalardan to’mendegishe na’tiyjeler kelip shi’g’adi’.

Yeger

Ui - b

ha’m

U2 - B2

bolsa, wol jag’dayda

U1 v U2 - B1 v B2;

U1 л U2 - B1 л B2;

U1 ^ U2 - B1 ^ B2;

U1 ~ U2 - B1 ~ B2;

U1 - B1 (yamasa U2 - B2).

ani ’qlama. Yeger U formulasi’ni’n’ qurami’nda tek konyunkciya, dizyunkciya ha’m biykarlaw a’melleri qatnasqan boli’p, biykarlaw a’meli propozicional wo’zgeriwshilerge g’ana tiyisli bolsa, wol jag’dayda bunday formula keltirilgen formula delinedi.

2-mi ’sal. A л B v A л C v A л B keltirilgen formula boladi’, biraq

(A ^ B) л B v C

keltirilgen formula yemes, sebebi bul formulada implikaciya a’meli qatnasi’wi’ menen birgelikte biykarlaw a’meli quramali’ formula

A ^ B g’a tiyisli boladi’.

Teorema-3. Ayti’mlar algebrasi’ni’n’ ha’r bir U formulasi’ yaki wo’zi keltirilgen formula, yaki woni’ wog’an ten’ ku’shli keltirilgen formula menen almasti’ri’w mu’mkin.

Bul teoremani’ da’lillew ushi’n ayti’mlar algebrasi’ni’n’ ten’ ku’shlilikleri menen tani’si’p shi’g’ami’z. Ayti’mlar algebrasi’ni’n’ ten’ ku’shlilikleri to’mendegiler:

I.	A = A
II.	A v B = B v A
III.	A л B = B л A
IV.	(A v B) v C = A v (B v C)
V.	(A л B) л C = A л (B л C)
VI.	A л (B v C) = (A л B) v (A л C)
VII.	A v (B л C) = (A v B) л (A v C)
VIII.	A v A = A
IX.	A л A = A
X.	A л (A v B) = A
XI.	A v A л B = A
XII.	(A v B) = A л B
XIII.	(A л B) = A v B
XIV.	A v A = 1
XV.	A л A = 0
XVI.	a) A v 1 = 1, b) A л 1 = A, c) A v
	d) A л 0 = 0.
XVII.	A ^ B = B ^ A.

Bul ten’ ku’shliliklerdin’ wori’nli’ yekenligin shi’nli’q kestesi ja’rdeminde an’sat g’ana tekserip ko’riw mu’mkin. Ma’selen, XIII ten’ ku’shlilik ushi’n shi’nli’q kestesin keltireyik:

A	B	A	B	A л B	(A л B)	A v B
1	1	0	0	1	0	0
1	0	0	1	0	1	1
0	1	1	0	0	1	1
0	0	1	1	0	1	1

II-XI, XIV-XVI ten’ ku’shliliklerdi payda yetiwshi formulalar keltirilgen formulalar yekenligi ani’q (propozicional wo’zgeriwshiler ha’m logikali’q konstantalar keltirilgen formula yesaplanadi’).

Bunnan ti’sqari’,

A ^ B = A v B (1)

ten’ ku’shliligi wori’nli’ yekenligin shi’nli’q kestesin du’zip ko’rsetiw qi’yi’n yemes. Joqari’da

A ~ B = (A ^ B) л (B ^ A)

wori’nli’ yekenligi ko’rsetilgen yedi. implikaciyani’ biykarlaw ha’m dizyunkciya menen almasti’ri’w mu’mkin yekenliginen to’mendegi ten’ ku’shlilikti payda yetemiz:

A ~ B = (A v B) л (A v B). (2)

Demek,

A ~ B

ha’m

A ^ B

formulalar keltirilgen formulalar menen almasti’ri’li’wi’ mu’mkin yeken. I, XII, XIII ten’ ku’shlilikler qos biykarlaw ha’m de dizyunkciya ha’m konyunkciyalardi’n’ biykarlamalari’n qalay keltirilgen formulalar menen almasti’ri’w mu’mkin yekenligin ko’rsetedi.

Yendi 3-teoremani’n’ da’lilleniwin keltiremiz. Yeger U formulani’n’ wo’zi keltirilgen formula bolsa, wol jag’dayda teorema da’lillengen boladi’.

Yeger U formula qurami’nda implikaciya ha’m ekvivalensiya a’melleri qatnasqan bolsa, wolardi’ (1) ha’m (2) ten’ ku’shlilikler ja’rdeminde almasti’ri’w mu’mkin; formula qurami’nda B ko’rinisindegi u’les formula qatnasqan bolsa, woni’ B menen, ( B v G) yamasa (B л G) ko’rnisindegi u’les formula qatnasqan bolsa, wolardi’ sa’ykes tu’rde

B л G

ha’m

B v G

formulalar menen almasti’ri’w mu’mkin. Bul protsesti jeterli ma’rtebe ta’kirarlap, aqi’ri’nda U formulag’a ten’ ku’shli bolg’an keltirilgen formulag’a iye bolami’z.

Solay yetip, 3-teoremag’a tiykarlani’p ayti’mlar algebrasi’ni’n’ ha’r bir formulasi’n tiykarg’i’ ha’m basqa ten’ ku’shlilikler ja’rdeminde almasti’ri’p, wolarg’a ten’ ku’shli bolg’an formulalar payda yetiw mu’mkin. Bunday tu’rlendiriwler bazi’bir ma’selelerdi sheshiwde ken’ ko’lemde qollani’ladi’. Biz, yendi formulalardi’ tu’rlendiriwge baylani’sli’ mi’sallar keltiremiz.

mi ’sal.

(A v B ) л C ^ (A л B v C ) formulani’ tu’rlendirin’ ha’m a’piwayi’lasti’ri’n’.

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

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

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

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

= A v B v B v C = A v 1 v C = 1 Demek, berilgen formula BR formula yeken. Meyli

U (Ai, A2,...., An)

ayti’mlar algebrasi’ni’n’ bazi’bir keltirilgen formulasi’ bolsi’n, yag’ni’y bul formulada tek g’ana л, v ha’m - a’melleri qatnasqan bolsi’n. Aldi’n’g’i’ paragrafda ayti’mlar algebrasi’ni’n’ qa’legen formulasi’n keltirilgen formula ko’rinisinde ten’ ku’shli tu’rlendiriwler ja’rdeminde keltiriw mu’mkinligi da’lillengen yedi. Soni’n’ ushi’n joqari’dag’i’ U(A1, ...., An) formulani’ ayti’mlar algebrasi’ni’n’ qa’legen formulasi’

dep qarawi’mi’z mu’mkin.

ani’qlama. Yeger

U(A,, ...., An) (3)

ha’m

U *( A,,...., An)

formulalari’ bir-birinen v ni’ л g’a, л ni’ bolsa v g’a tu’rlendiriw ja’rdeminde payda yetilse, wol jag’dayda bunday formulalar wo’z-ara qosarli’ formulalar delinedi.

mi ’sal.

A л B v A v C

formulasi’

(A v B) л A л C

formulag’a qosarli’ boladi’.

Teorema-4.

U (A., A2,...., An)

ha’m

U *( A., A2,...., An) formulalari’ wo’z-ara qosarli’ boli’p,

A^ A2 ,...., An

ler wolardi’n’ qurami’na kirgen barli’q propozicional wo’zgeriwshiler bolsa, wonda bul jag’dayda

U (A!, A2,...., An) - U *(Д, A2,...., An) (4) boladi’.

Teoremani’ da’lillewden aldi’n formulani’n’ rangi tu’sinigin kiritemiz.

ani ’qlama. U formulag’a kirgen barli’q logikali’q a’meller sani’ usi’ formulani’n’ rangi delinedi ha’m r(U) menen belgilenedi; bunda propozcional wo’zgeriwshilerdin’ rangi 0 ge ten’ dep yesaplanadi’.

mi ’sal.

r (A л B v A v C) = 5 Sebebi bul formulag’a 5 logikali’q a’mel

(л, -, v,-v)

lar qatnasqan.

Teoremani ’n’ da’lilleniwi. Yeger r(U) = 0 bolsa, wonda U*(Д, A2,...., An) - - A, - U(Д, I2,...., An) yaki As ti As menen almasti’rsaq (s = 1, 2,....n),

A - U*(A1, A2,...., An) - U(A., A2,...., An)

payda boladi’.

Aytayi’q, rangi r < n bolg’an barli’q formulalar ushi’n (4) ori’nli’ bolsi’n. Bul jag’dayda rangi m bolg’an U formula ushi’n da (4) qatnasi’ wori’nli’ yekenligin ko’rsetemiz. U keltirilgen formula

bolg’anli’g’i’ ushi’n wol to’mendegi ko’riniske iye boli’wi’ mu’mkin:

в

B л G

B v G • r(B) < m ha’m r(G) < m bolg’anli’qtan, pikirimizge tiykarlani’p

в (Д, Д,...., An) ш B *(Д, Д,...., An), (5) G(Д, Д,...., An)ш G *(Ai, A2,...., An). (6)

bolatug’i’nli’g’i’ kelip shi’g’adi’.

B

bolg’an

unnan, B л G ha’m B v G formulalarg’a qosarli’ formulalar sa’ykes tu’rde B * v G * ha’m B * л G * boladi’.

h

U = B л G U = B v G U ш B v G

a’m

bolg’anli’qtan

ha’m

U ш B л G

yekenligi kelip shi’g’adi’. (5) ha’m (6) ni’ yesapqa alsaq, 2.1- teoremani’n’ na’tiyjesine tiykarlani’p

U (Ai,...., An) ш B *( Ai,...., An) v G *( Ai,...., An),

U (Ai,...., An) ш B *( Ai,...., An) л G *( Ai,...., An) qatnaslari’n payda yetemiz, yag’ni’y 2) ha’m 3) jag’daylar ushi’n U(Ai,...., An) ш U*(Ai,...., An) (7)

kelip shi’g’adi’.

Yendi U = B bolsi’n. Bul jag’dayda

U*(Ai,...., An) ш (B (A,...., An))* шB *(Ai,...., An). r(B) < m bolg’ani’ ushi’n, pikirimizge tiykarlani’p B (Ai,...., An) ш B *(Ai,...., An)

boladi’.

Demek,

U *( Ai,...., A„) ш-( B (Ai,...., An)) ш B( Ai,...., An)

yamasa

_ U *(4,...., An)- B(4,...., An)

boladi’. U - B bolg’anli’g’i’ ushi’n (7) ge tiykarlani’p U (A;,...., An) - U *( 4,...., An) yekenligi kelip shi’g’adi’ .

teoremag’a tiykarlani’p qosarli’q (yekilik) ni’zami’ dep atali’wshi’ teoremani’ da’lillew mu’mkin.

Teorema-5. YegerU - B bolsa, wonda U* - B * boladi’.

Da ’lilleniwi. 4-teoremaga tiykarlani’p:

U (A;,...., An) - U *( A;,...., An),

B (A;,...., An) - B *( Д,...., An)

yamasa

U(Ai,...., An) - U *(Д,...., An), m

B (4,...., An) - B *( 4,...., An)

boladi’.

Ten’ ku’shlilik ani’qlamasi’na ko’re U ha’m B formulalari’ propozcional wo’zgeriwshilerdin’ ma’nislerinin’ barli’q naborlari’nda bir qi’yli’ ma’nislerge iye bolg’anli’g’i’ ushi’n

u ( a;,...., a„ ) - b( a;,...., a„ )

da wori’nli’ boladi’. Bul jag’dayda

U(A;,...., An ) - B(A;,...., An ) (9)

yekenligi kelip shi’g’adi’.

(8) ha’m (9) dan U* - B * bolatug’i’nli’g’i’n ko’riwge boladi’.

ani ’qlama. YegerU(A;,...., An) formulasi’ ushi’n

U (A;,...., An ) - U (A;,...., An ) - U *( A;,...., An )

wori’nli’ bolsa, wonda bunday formula wo’z-wo’zine qosarli’ formula delinedi.

mi ’sal.

U(A, B, C) = A л B v A л C v B л C formulasi’ wo’z-wo’zine qosarli’ formula boladi’. Haqi’yqati’nda da, bul formulasi’na qosarli’ to’mendegi

U *( A, B, C) = (A v B) л (A v C) л (B v C)

formula boladi’. Bug’an ten’ ku’shli tu’rlendiriwlerdi qollansaq, wonda U * (A, B, C) = (A v B) л (A v C) л (B v C) = (A v A л B v A л

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

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

л C v B л C = U (A, B, C) bolatug’i’nli’g’i’ kelip shi’g’adi’.

mi ’sal. (x v у) л (x v у) = х formulasi’ni’n’ ten’ ku’shli formula yekenin ko’ rsetin’.

Sheshiw 1-jol : (x v у) л (x v у) = x v (у л у) = x v 0 = x boladi’.

jol: Ma’nisler kestesi arqali’ to’mendegishe boladi’.

x	у	у	x v у	x v у	A( x; у)
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 x = A(x; у) ten’ ku’shli formula yeken.

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

Keltirilgen formula dep nege aytami’z?

Qosarli’q ni’zami’ degen ne?

Qosarli’ ni’zami’ haqqi’ndag’i’ teoremani’n’ saldari’n da’lillen’.

To’mendegi formulalar ushi’n shi’nli’q kestesin du’zin’.

x
(x v у )^(x л у v x ^ у)

(xt v x2)л x3

5. To’mendegi formulalardi’n’ qaysi’lari’ BR ha’m BJ ani’qlan’.

j v x2

(x ^ у)^ (X ^ у)

((р л q) ^ q)^(q ^ p)

(x ^ z) ^ ((у ^ z) ^ (x v у ^ z))

’ x v y ^ x л y

(x ^ y) ^ (y ^ x)

P ^ (P2 ^ Pl)

k) p ^ (Pl ^ P2 )

((P л q) ^ q) ^ (q ^ P)

m) ((p л q) ^ q) ^ (q ^ p)

To’mendegi ten’lik wori’nli’ bolatug’i’n x ha’m о tin’ logikali’q ma’nisin ani’qlan’.

(l ^ x) ^ у = 0

x v у = x

S

1)	P ^ P 4)	р v (р о	р )	7)	(р	р)
2)	р v р 5)	(р v р )^	(р л р)	8)	р	о р
3)	(p ^ р)v р 6)	р ^ р		9)	р	v(p о
8.	(x ^ y) tin’ ma’nisi	1 ge ten’.To’mendegilerdin’			ma’	nisi
haqqi	’nda ne ayti’w mu’mkin?

hi’nli’q kestesin du’zbesten BR yamasa BJ formula yekenligin ani’qlan’.

z ^ (x ^ y)

x ^ y ^ y

(x ^ y) ^ z

Yeger (x v a)v (x v a) = b bolsa, wonda x ti’ tabi’n’.

Meyli F - birdeyine jalg’an formula bolsi’n.Sondax л y ^ F = x ^ y bolatug’i’ni’n da’lillen’.

x ^ y = y ^ x formulasi’ni’n’ ten kushli formula yekeninin ko’rsetin’.

12. Mi’na А(х, у, z) = (x — у)л (y — z) — (z — x) formulasi’ni’n’

B(х, у, z) = х v z formulasi’na ekvivalent yekenligin ko’rsetin’

Formulani’ a’piwayi’lasti’ri’n’

А(х,у,z) = (x — у)л z —— (x — z)

A(X, у) = (x о у) л(х v у))

A( x) = (x —— x) —— x

A( x, у) = (x — у )v(x — у)— x

Ten kushli formula yekeninin ko’rsetin’.

x — (у — z) = x л у — z

x v (у л x) = x v у

xy v zt = (x v z )(у v z )(x v t )(у v t)

To’mendegi formulag’a keltirilgen formulani’ tabi’n’. a) В( х, у) = x — (x v у) л (x — у) — x

К
b) x л (x — у) — у)

16. Qosarli’ formulani’ jazi’n’. х л у — (z v у — z)

= a л c v (a v ь)л (b v c) formulasi’na

М = (a v Ь)л (b v c) qosarli’ formula yekenin ko’rsetin’.

A(a, b, c) = (a v е)л(л л b v b л c) formulasi’ ushi’n qosarli’ formula wori’nli’ yekenin ko’rsetin’.

Birdeyine ras yamasa jalg’an formula yekenin da’lillen’.

(x — у) л (x — у) — x

x л (x — у) л (x — у)

x v x — у л у

(x — ((у — z)) — ((x — у) — (x — z))

(z —— x) —— ((z —— у) —— (z —— x л у))

(x — z) — (у — z) — ((x v у) — z)))

k) (x — (у — z)) — (x л у — z)

n) (x л у — z) — (x — (у — z)) .