Elemente de logica matematica si de teoria multimilor [PDF]

Zitiervorschau

GR. C. MOISIL

Elemente de logică matematică şi de teoria mulţimilor

J

00

�-------

EDITURA ŞTIINŢIFICĂ. BUCUREŞTI

1968

Prefaţă

Evolutia tu lburătoare a stiintelor matematice în "\'re­ murile no�stre are un prim �spect stra �iu. Apariţ.ia unor ştiinţe cu nume ca Logică matematică, Biologie mate­ matică, Economie matematică, Psihologie matematică, Teoria matematică a învăţării şi Lingvistică matematică arată că domeniul de aplicare al acestor ştiinţe matema­ tice s-a lărgit considerabil. înainte aveam o Fizi( ă ma­ tematică, căreia îi corespundea tehnica clasică. Noilor domenii matematizate le corespund noi domenii ale teh­ nicii, care toate întrebuinţează calcul"atoarele digitale: programarea automată, bionica, automatele cu auto­ instruire" traducerea automată. în al doilea rînd matematica de azi se ridică la un grad de abstracţie neîntîlnit înainte. Natura elementelor despre care se enunţau teoremele puncte, drepte, sau cercuri, numere sau vectori, nu mal apare azi în mate­ matică; elementele sînt implicit caracterizate prin sistemul de axiome. în al treilea rînd caracterul de cantitativ 81 mate­ maticilor a evoluat către caracterul de structural. în fine punctul de plecare al unei expuneri mate­ matice e mai spre început decît cel al matematicilor cla­ sice. Matematica nu evoluează de la axiome la teoreme, de la acestea la aplicaţii. Mersul ei este mult mai între­ ţesut cu răsfrîngeri şi cu anticipări. Două, trei secole analiza matematică a fundat desco­ peririle astronomiei, mecanicii corpurilor rigide şi ale mecanicii corpurilor deformabile, ale opticii şi electromag5

netismului. În acelaşi timp matematicienii meditau asu­ pra fundamentelor acestei analize convergenţa seriilor, continuitatea functiilor, existenta ariei şi cea a planului tangent, derivabilitatea integralelor şi integrabilitatea derivatelor. Normal, cursurile unei universităţi pleacă azi de la notiunea naivă de multime si de la notiunea naivă de " nu � ăr natural. În volumul de faţă plecăm de la noţiunea naivă de mulţime, dar nu pentru a merge înainte: aritmetica trans­ finită, topologia, algebra, algebra topologică, analiza funcţională, ci pentru a merge înapoi. Teoria naivă a mulţimilor din capitolul I şi IV, în care proprietăţ.ile se citesc pe figuri e dublată în capi­ tolul II de o teorie in că si mai naivă a reIa tii10r binare. Sper că cititorlll nu va fi dezorientat nici de abundenţa materiei nici de subtilităţile ce apar în acest studiu şi, de asemenea, sper că el îşi va pune problema: aceste proprietăţi nu trebuie ele oare să fie demonstrate? Capitolul V arRtă că nu trebuie să fie demonstra�e decît unele din el " celelalte proprietăţi deducîndu-se imediat; acestea sînt axiomele algebreI)}' booleene. Că mul�imile şi relaţiile formează algebre booleene, acest lucru e dovedit în Capitolul VI, presupunînd dove­ dite anume proprietăţi ale logicii predicatelor; acestea se pot demonstra cînd sînt admise anume proprietăţi ale logicii propoziţiilor. Acestea sînt demonstrate în ca­ pitellll VII. Iată mersul înapoi, către mai spre început. Noliunea de funcţie ar fi putut fi de la început sub­ sumată celei de relaţie. Am preferat, avînd în vedere importanţa pi, să-i dedirăm un capitol special, capitolul III. încadrăm algebric mai spre sfîrşit, la pp. 167 sqq, teoria relaţiilor binare în teoria matricelor cu ele­ mente într-o algebră booleană iar la pp. 169 sqq în teoria grafurilor şi (( mplexelor unidimensionale. ,

•

Logica matematică se întrebuinţează. . Am yrut, în capitolul VIII, să dăm cîteva din aplicaţiile ei. Primul paragraf expune teoria clasificării dichotomir,e, s uh forma algebric ă. 6

Grupul din Bucureşti a dat o mare dezvoltare cercetă­ rilor de teoria algebrică a circuitelor de comutaţie. Pentru acest motiv, acestor cercetări le-am făcut loc în al doilea paragraf al acestui capitol VIII. Al treilea paragraf arată cum un domeniu al Econo­ miei matematice , mult studiat în ţara noastră: progra­ marea pseudo booleană, e legat de logica matematică. Lingvistica matematică are o frumoasă dezvoltare în Republica So ialistă România, graţie lui Solomon Marcus; în ultimul paragraf al capitolului se arată legăturile între lingvistica matematică şi logica matematică. _

•

Cartea a fost scrisă din amintiri; de acum 34 ani am început să predau, uneori sistematic, deseori nesistematic capitole şi paragrafe de logică matemati'că şi de teoria mlll­ ţimilor. De atunci mi-au rămas în minte pagini pe (;1ir-e le-am transeris �i din Fundamenta M athematicae si · din volumele lui W. Siel'pinski, St. Banach şi &. K.uratowski: înciepărt aţii mei profesori. Din lecturile mele de atunci n-a rămas decît o singură dovadă: propriotă[jle dato­ rate studentului meu de pe vremea aceea, C. Trufinesc'l*, date la pp. 95- 96 şi 108-1 11 ale acestui volum. Erau pe atunci şi logica matematică şi teoria mulţi­ milor capitole înfricoşătoare de care oamenii de bine te îndemnau să nu te apropii. Azi public acest volum pen­ tru tinerii matematicieni, pentru ingineri, pentru studenţi, pentru profesorii de licee şi elevii din ultimele clase. Cred că o să le folosească. Gr. C. M.

G 1·u.lie 1967

*

Su.r le theoreme

de iVI.

Banach, in "Comp les rendus de l' Aca­

demie des sciences de Roumanie",

t.I , 1936.

7

Algebra mulţimilor

Ideea de multime o considerăm ca înteleasă de OrI­ ' cine ca şi ideea e'xprimată prin propoziţia : individul a este un element al multimii IX. ' Această propoziţie o vom scrie a

E

a,

unde semnu l " E " este semnul relaţiei de apartenenţă. De asemenea, vom scrie

în loc de: individul a nu este element al multimii IX. Ideea de mulţime se întregeşte prin conceptul de mul­ ţimi egale IX

=�,

adică de multimi care au aceleasi elemente. Aceasta este ' o definiţie a egalităţii dintre mulţimi. Nu vom defini egalitatea între indivizi a

=

b,

a şi b fiind indi.vizi, ci o vom lua ca idee primitivă. Vom observa că

=

dacă

a

dacă

a =

b şi

a

E

� şi a E

a, li. ,

atunci b E atunci

a

IX;

E �.

tNCLUZIUNEA

Dacă

, � sînt două mulţimi, spunem că mulţimea este cuprinsă în mulţimea � '" şi scnem li.

dacă orice element al lui

a

C�,

li.

este şi element al lui

Fig.

(f.

� (fig.1).

1

în loc de li. C �, putem scrie ş i � => li. , ceea ce se -citeşte "mulţimea � cuprinde mulţ.imea lI.", sau "mu�­ timea � este o supramulţime a mulţimii lI.". Dacă li. n u este submulţime a lui �' scriem lI.ct � sau

13 1J

.

c , :;P,E �, C,�,ct.,:b, li (e paralel cu), I (divide). . în mod obişnuit, dacă R este· o· relaţie, aRb "Înseamnă

=, =1= ,
=) =1=

= ,

=

ziunea

lor). Se ded uc e

=>

-. :;p,

< =>

=> C (egalitatea

că

implicaţia

-.

claselor

relati ilor

>, < = > =f=., imp lică inclu­

=>

este refle};iră

(2.1 )

şi tranzitiră,

( 2.2 ) dacă R => S şi S => T , atunci R => T. Conjuncţia relaţiilor Dacă S şi T sînt două relaţ ii, numim conj·uncţi a lor

şi notăm cu

S&T

relaţia dintre a ŞI b, definită prm: a(8&T)b,

înseamnă a8b

şi a T b.

Exemple

rentl'u numere = es te -< & >- ; > este >- & =1= ; < este -< & =1= ; pentru mulţimi este C &:J. Este vizibil că =

(2.3)

8&T =) 8, ) T,

8&T

=

căci dacă avem şi a8 T şi a Tb, atunci avem a8b ŞI la fel avem aTb, dacă R

> 8 şi R =9 T,

=

atunci R

� 8&T,

(2.4)

căci din aRb deducem a81! ŞI a 1'b.

Echivalenţa relaţiilor Dacă

avem

R � 8 şi 89 R,

spuorm că al'e loc echivalenta reIat iilor R şi 8 (sau Il şi ,"; sînt echivalente) şi notăm Il (=) 8. Este

\'izibil că c,�hivnle!l!a

1

e1.:lţiilor es te

re(le:x:i(!â:

R (=)

R,

( 2.5 )

8( )

R

( 2.6)

simrtrică dacâ ŞI

R ( ) S, alunci =

=

lranâti(!ă daci'i

R (=) S .)"i S (=) T, atunci R (=) T.

(2.7)

Demonstra ţ iile (a exerci�ill. Avînd cefinită echi\'alen/a, pl'tem pune în evidenţă unr:e proprietăţi nle conjunc iei. 38

Proprietăţi ale conjuncţ/:ci.

Conjuncţia relaţiilor este idempolenlcl:

R&R (=) R,

(2.8)

R&S S&R

(2.9)

comuiati",ă : şi asociati"'tl: R&(S&T) (=) (R&S)&7'.

exercq�u;

Demonstratiile ca

(2.10)

de exemplu,

a[R.&(S&T)]b, Înseamnă aHb �i a(S & T)b, Dar a(S & T)b lnscamJli'i aSb şi a Tb, de ci ar H &(8-& T)Jb înseamnă aRb şi aSb şi aTb. Deoarece a[. (R&S)&TJI! înseamnă a(H &S)b şi a Tii, ial' a (R &S)b inseamnă aRh şi aSb, deducem că I/[(H &8) & Tjb inseamnă aRb şi aSb, şi aTb. Deci a[R&(S&T)Jb �i a[(R&S)&T]b inseamnă a m î n ­ două acelaşi lucru, �i a n l l me aHb şi aSb şi a 'l'b. De(�i dacă a[ll&(S&T)]b, aLunei a[(R&S)&T]b, deri R&(S&T) => (R&S)&T şi (R&S) &1' � R&(S&T), cleei teorema.

Negaţia. unei reia ţii

l'\llInim

n

dilltre a �i b

egaţi a liii Il şi not,)m defiJliLii a�Lfel a H. li

înseamnă a nu esle în

el a ( i n 11.

ClI

negaţia reIat ir,i ::::::

est

r

E:"J.:emple :

el]

J'( (sali

It) relaţia

b. c

>- ,

nega! ia rf�la�iei :;.... esLe -< ,

negatia relatiei -< esle

>

negaţia relatiei:::> este

< .

negatia relatiei

E esLe �

nega! ia re la t i e i � c,,;Le E 34

negaţia relaţiei este =1= , negaţia relaţiei =1= este = =

Disjuncţia relaţiilor Fiind date relaţiile S, T numim disjuncţia lor şi notăm cu SV T

relaţia dintre a şi b definită astfel: a(SV T ) b,

înseamnă: măcar una din relaţiile aSb sau aTb este adevărată. Exemple:

V Proprietăţ i ale disfuncţiei S => S V T, T:::;:. SV T, dacă S => R ş i T � R , at�mci S V T => R , RV R (=). R , S V T (=) T V S , RV (SV T ) (=) ( RV S )V T

(2. 1 1 ) (2. 12) (2.13 ) (2. 14 ) (2.15 )

2.13, 2. 14 , 2 .15 sînt legile de idempotenţă, de comiIta­

tivitate şi de asociativitate ale disjuncţiei. Propr ietăţi ale d isj uncţiei şi conjuncţiei

40

R & (RV S) (=) R,

(2.16)

R V (R &S) (=) R,

(2.17 )

R &(SV T ) (=) ( R &S) V ( R& T),

(2. 18)

RV (S & T ) (=> > ,

=

=

11. 1) II � II, 12. I I => I Demonstraţiile ca exerciţiu. Proprietăţile produsului*

(2.19) (R.S) . T (=)R .(S. T), căci a[(R . S) TJb înseamnă cI există un y cu a(R.S)y şi yTb, deci c1 există un x cu a Rx şi xSy, deci că există x şi y cu aRx, xSy, y Tb, deci că există un x cu aRx şi x(S.T)b, deci a[R.(S.T)Jb, deci (R.S) T =) R.(S.T). Analog ară Ulm că: R.(S.T) ) (R.S). T, (2.20) R.(S V T) (=) (R.S) V (R.T). Dacă a[R.(S V T)Jb, atunci există un x CI aRx şi .x(S V T)b, deci xSb sau m,sC1r xTb. Deci se prezintă unul măcar din următoarele cazuri: sau 1) aRx şi xSb san măC9r 2) aRx şi .xTb. Deci: 1) a(R.S)b sau măcar 2) a(R. T)b deci R.(S V T) � (R.S) V (R.T). Analoga[(R. S)V (R.T)]b dă: 1) a(R.S)b, deci există un x w a Rx şi xSb sau măcar 2) a (R. T)b, dECi există un y cu aRy ŞI yTb, deci în f'mîndouă cazurile există un Z .care dă in acelaşi timp aRz prEc�lm şi uDul din caznrile zSb sau măcarzTb, deci ziS V T)b, deci a[R. (S V T)]b, deci (R.S) V (R. T) ) R(S V T) (2.21) (R V S). T (=) (R.T) V (S.T), •

=

=

R.(S&T) (R&S). T *

42

Vezi p. 197.

)

=

=)

(R.S)&(R. T), (R.T)&(S. T).

(2.22) (2.23)

Transpusa unei relaţii R este relaţia R - adeseori

notată R

-

defi nită pri n: xRy Înseamnă y Rx.

Propr ietăţi ale transpusei

Îi (=) R, R&s (=) ii&8,

(2.2/1)

RV S (=) RV S ,

(2.26)

----

-

(2.25 )

-

dacă S (=) R , atunci S (=)

R,

(2.27)

RS ( ) S El

( 2.28)

=

Demonstraţiile ca exerciţill. ExercItII

1. Care est.e transpusa relaţiei:< , , :;;;,. , = , '::, C. j, !I ,1 sint analo�ele proprieti\tilor -1.1-1. [9, 1.33-1.36 1.37-1.41, 1.43-1.123 penl.ru rel aţii.

2. Care

3. Se noteazii

R' (=) R,

R"+l(=) RR".

Să se arate că Rm R" (=) Rm+".

Obserpaţii 1. Analoga mulţimii vide este relaţia vidă, care este relaţia R pentl'u care, oricare ar fi x,y nu avem xRy; analo!!il mul ţimii to­ tale este relaţia totală R, aslfel c;1 xRy este valabilă, oricare ar fi x şi y. . 2. O relatie R este definit:i 1"lr,' elementele a dOllă multimi 0:, (3; Cll alte cu ' vin le rela�ia a NI! are sens cînd a CI. şi (3 •dar nu are sens nici dacă a�(3, nici dacii b�(3. De pild;l relaţia < b are sens cînd si b sînt numere reale dar nu ar-e sens cind a c un . număr complex' sau cînd e un vec · tor.

E

a

bE

a

b

Vom n Ilmi p e o: domeninl relaţiei R şi pe � codomeniul acestei relaţii; relaţia aRb nn va avea sens decît dacă In cazul relaţiei" < " domeniul o: şi codo­ a E o: şi b E�. meniul � sint identice, o: =�, şi anume si nt mulţimea numerelor reale. în cazul relaţiilor" E " şi �" propcziţia a E p. nu are sens decît dacă a este un individ şi fL este o mulţime (vezi şi C ap . IV) deci dOfI).eniile relaliilor " E " şi �" sînt mu lţi m ea 1 a tLlturor indivizilor, in timp ce codomeniile lor sînt mulţimea tuturor submulţimilor lui I. "

"

RELATIA DE I DENT ITATE

R elaţia de identitat e se bucură de următoarele prop rietăţi : a ) reflexif'itatea : oricare ar fi x avem x = x �) simetria : ori care ar fi x şi y, dacă x = y, atunci y = x ; ) tranzitif' itatea : oricare ar fi x, y, z, y dacă x = y şi Y = z, atunci x = a) compatibilitatea : dacă x = x*,

alunci

, y = Y*

ŞL

x Ry

(3.1 ) (3.2) z

;

(3.3 ) (3.4 )

R y*.

x*

P ropriet atea � s e scri e : rv

P roprietatea y dă:

(=) =

=

-�

= .

Proprietatea a d ă p entru ori ce relaţie --'-- R =) R, R = =) R, = R = =) R,

c ăci a( R) b înseamnă că există z cu a = z, zRb, deci înseamnă aRb ; dacă aRb, atunci a = a, aRb dec i R => = R. An�J og în celelalte cazuri. R elaţia de egalit ate* între mulţimi a fo st d efi nită la p. ' 9: a = � î nseamnă că a şi � au acel eaşi ele mente. P entru această relaţie propriefăţile d e reflexivitate (oc şi a au aceleaşi elemente, ceea: ce est e o tautol ogie), de si­ metri e (d ac ă a şi � a u a celeaşi elem ente, atunci � şi a. au aceleaş i elemente), de tranziti vitate (dac ă· a şi � au ace­ leaşi el eme nt e şi dacă 13 şi y au ace le aş i elemente, atunci a şi y au acele aş i el emente) şi de compatibilit ate (dac ă =

'" Vezi p. 1 9 7 .

44

şi IX * au ac eleaşi elemente şi dac ă � şi � * au acele aşi el emente, atunci orice relaţie satisfăcută de oc şi � este satisfăcută de oc * şi � *) sînt consecinţe ale definiţiei date. Vom obs erva că echi valenţa rel aţiilor joacă î n al­ gebra relaţiilor ace laşi rol pe ca re- l 'j oacă e gali tate a mul· timilor î n algebra multi mil or. , Pr oprietăţi le de re fle' xivitate, d e . si metrie: şi de tran­ zitivitate ale relaţiei (=) între relaţii au fost puse î n evi­ denţă la p. .3 8. O proprietate de compatibi-li tate ar fi enunţ ată sub forma.: Dacă R (=) S, atunci ori ce proprietate a lui R es te . o pr opri et�te a lui S ; despr e o astfel de p ropoziţi e v:om vorbi Ia p. '17 5 ., oc

REL ATII' DE: P:REORDIHE

O

re laţi e

R

este numită reflexi�'ă dacă ori care ar

fi· x

xRx,

deci, d acă = =9

R.

O relati ' e R es te numită tranziti(Jă dacă di n aRb şi bRe deducem aRc. O relaţie de preordine es te o re laţi e refl exivă ŞI tran­ zi tivă; pe ntru o as tfel de relaţie avem:

R 2 ( ) R, =

căci dacă aR2b, atunci e xistă un z cu aRz şi zRb şi atunci di n cauza tranzitivităţii, aRb , deci R 2 ) R. D ar dacă aRb din cauza refle xivi tăţii aRa, deci exis tă un z şi anume z = a cu aRz şi zRb, de ci R ) R2, deci =

=

R2 ( ) R. =

Reciproc, dacă R 2 ( ) R, atunci R 2 =? R, de ci dacă aRb şi bRe exi stă un z, şi an ume z = b, astfel ca aRz ş i zRe, de ci aRze, de ci aRc, deci R este' tr anzi tivă. =

45

Deci relaţiile de preordine R se pot caracteriza pnn (4. 1) =9 R , R 2 R, (4. 2) =

Exemple : C , ::> , -- , I I

,

I

RELAT I I DE ECH IVALENTĂ

o rela ti ' dacă ' e E este nu mi tă re latie de ech iva len tă este reflexivă, sime tri că şi tranzit ivă. Exemple de relaţii de echivalenţă II , == (mod m) pentr u în­ tregii pozitivi , negativ i şi nuli , relaţi a de egali tate pentr'l triunghiuri, rel aţ ia de similitudine pent ru triunghiuri sau alte figuri , rel ati a d e e chival enţă pent ru segmente (A B ---- CD însea mnă că A BCD este un paralel ogram, even­ tual dege nerat, fig. 36 a,b, c,d). Relaţia de e chivalenţ ă afin ă pentru tri unghi uri sau alte figuri plane este o relaţi e de e ch ivalen ţă (fiecărui pun cL A din planu l P î i corespunde pu nct ul A' din pla­ nul P, astfel ca A 'D' . . . să provi nă d i n A B . . . p rintr- o trans­ formare afi nă). Relat' iile de e chivalen tă fi ind relatii ' de preordine simetri ce, pot fi caracteri� aLe prin "'> E , (4. 1) =

E ( R V ) 2 (=) ( R V ) (=) R 2 V ) V ( = ) 2 (=) R 2 V R V R V = Dar (R ) V (R 2 R2 9 R, ieci ( R "' ) =) R V = =) R A . Arătăm că RA e � � antisimetrică : ( R A ) (=) R V = R V = (=) R V = (=) R V = =

=

=

=

=

---

�

-

=

(=) R A

Dacă R e rela �ia -< sau > , atunci R V e relaţia < sau > ; d acă R e relaţia < sau > R" e relaţia -< s au >Oricare ar fi relaţia R, afJem RV R"

A () A R , =

v

(=) R V ,

R V V (=) R V R " A (=) R A , 50

căci R V A (=) R V V = (=) ( R & -+ ) V = (=>( R V ) & ) ( -+ V = ) (=) R V = (=) R A ; R A V (=) R A & =F (=)( R V -+ (=) ( R & =F ) V ( = & -+ ) (=) R & -+ (=) R ; R (=) R & -+ (=) ( R & -+ ) & -+ (=) R & ( +- & -+ ) (=) (=) R & -+ (=) R V ; R "' "' (=> R " V (=) ( R V = ) V (=) (=) R V ( = V = )(=> R V = (=) R /' . =

=

v

v v

v

=

PRODUS CARTEZIAN Fie CY.' ; CY." , două mulţimi şi fie CY. mulţimea cu a' E CY.', a" E CY." Vom scrie

(a',a")

(X

şi

CI.

=

(X

'

x

p erechilor

" (X

vom" spune că CI.: este produsul cartezIan al mulţ!milor CI. " D e exemplu ( fig. 39)

. ŞI

(x

'

=

{ a' , b', c' }

CY." = {h", le" } avem CI. =

{ (a' , h " ) , (b' , h "), ( c'h"), ( a ',

k"), (b' , k"), ( c' , k ")}.

{

rf.." Fig. 3 9

(a', k")

(tI', k")

(ii', fi ") -----, al

( b: n")

k', ,

fi'

I I

I

I

(e', k") (c ', I�II)

CI b' '" '-' ---.,-------'

(/... '

. Tot astfel avem produ se carteziene în fig. 40 şi 41 . Prin definiţie (a', b' ) ( an , b" ) înseamnă a' a" şi h' b" Prin definiţie 2 (X = CY. X CY.. =

=

=

5 1.

0:' F ig. qO

�--

7

jA. 'xp"

fo"

/

Fig. � l

)).'

Proprietăţi ale produsului cartezian IX

X (� U y)

(rx. X �) U ( rx. X y ) ,

=

(2.29)

( rx. U � ) X Y = (rx. X y ) U (� X y) ,

(2.30)

rx. X (� n y) = ( rx.

X

y) ,

(2.31)

( rx. n�) X y = (rx.

X

y) .

( 2.32)

�) n ( rx.

y) n (�

X X

Exerciţii l. ., X Clt = " 2. eL X 0 = 0 . 3 . Dacă CIt :::/::. 0 ş i � =/= " atunci CIt x � =/= 0 . 4. Este egalitatea CIt x � = � x CIt . adevărată ?

,

Ce este o submulţime a lui rx. X � ? Ea este o mul­ ţime de perechi ( a ,b) cu a E rx. şi b E �. Fie p C rx. X � ; vom scrie a R b, dacă şi numai dacă (a,b) E p . In acest mod : submulţimile lui rx. X � coresp und relaţiilor R între ele­ mentele lui CY. şi ale lui �. 52

Vom numi fL R submulţimea fL R C cx X � a tuturor perechilor ( a,b ) E fL R care sînt în relaţia R a R b . Exemple. 1. Mulţimea !1 a elementelor lui cx X cx ce corespund relaţiei = este formată din perechile ( a,a) cu a Ecx . .& este numită diagonala lui cx X cx (fig. 42 ) ,

Fig. '�2

Il

---- ---- -- (b, b)

a

- - -- (a. a) I I I I

I I I I I I I I I I

a

b

2. Mulţimea fLR C fLs , dacă şi numai d acă R =) S, căci dacă a R b, atunci (a,b) E fL R şi dacă fLR C fLs, atunci ( a,b ) E fL s, deci a S b. 3. Mulţimile fLR = fLs, dacă şi numai dacă R (=) S , căci fLR fLs înseamnă fLR C fL s şi fis C fLR, deci R =9 S şi S =) R, deci R (=) S. 4 . fLR& S = fL R n lis , căci, (a,b) 6 fLR&S înseamnă a(R &S) b, deci a R b şi a S b, deci ( a, b ) E fL R şi ( a, b) E fL s, deci (a, b ) E fL R n fL s· 5 . fLRVS = fLR U I!s, căci (a , b ) E fLRV S înseamnă a(R V S)b, deci a R b sau măcar a S b, deci ( a, b ) E fL R san măcar (a, b ) E [.Ls, deci ( a, b) E fLR U fLs · =

6 . fL;{ =

fL:R'

Exercitii 1.

Dacă

cx

C � şi

Y

C 8 , atunci cx

2. (cx

X

�) - (y

X

8)

X =

Y

C� X 8.

( (cx - y) X t3) U ( cx X ([3 - 8 ) ). 53

RELAT I I n . ARE

Toate elementele unei mulţimi cx au o proprietate comună, şi anume aceea de a aparţine acelei mulţimi ; propoziţia a E cx este o proprietate A a lui a ; a spune 1. a aparţine clasei cx , ceea ce se scrie a E cx ; 2. a are proprietatea A , ceea ce vom scrie A (a) , este acelasi lucru. Dacă �,b sînt În relaţia R,a R b, vom scrie R( a, b ) . A (x) şi R(x,y) sînt funcţii care au ca variabile pe x şi pe y, şi care, dacă a sau a şi b sînt indivizi, au ca valoare propoziţiile A(a), R(a,b ).

Putem concepe relaţii între 3,4 . . . ,n indivizi, care vor fi numite relaţii sau atribute sau predica te : tel'nare, quater­ nare, . . . , n-are. R( x,y) este un predicat sau o relaţie binară, A (x) un predicat monar sau unar. Exemple de relaţii ternare. Relaţia S(a,b,c), cînd a + b = = c, şi relaţia P(a,b,c) cînd a b = c. Relaţia de ordine ciolică, cînd a,b,c sînt. în această or­ dine în sensul direct pe cerc (fig. 43 ) Relaţia de separaţie liniară a este între b şi c (fig . 44). Relaţia a ::= b (mod. c) . Exemple de relaţii cuaternare Relaţi a � = !:. definită d

prin bd =1= O :şi ad = bc.

0. , '" o

Fig. 4 3

•

/;

a

c

Fig. 44

Relaţia de ech idistanţă ( fig. 45) a- b = c - d Relaţia de separaţie ciclică (fig. 46) bd separă pe ac.

54

Proprietatea de compatibilitate ( 304) de la po 44 se ex­

tinde astfel

c ..

8

.

h

D acă R este

•

c

o

•

d

Figo 45

I " .i.

Figo

46

\

rel aţ,i e n-ară ŞI dacă

al an

=

=

bl,

bn ,

a tunci dacă al' 0 0 0 ' an sînt în relaţia bl, b" vor fi în relaţia R o 0 ' 0 '

a

R,

atunci ŞI

III Funcţii

DEFINITIA N O T I UN I I DE FUNCŢ I E

Spunem că f' este o funcţie cu argumentul în mul­ ţimea D şi cu valorile în mulţimea C Şl scriem f'

D

�

C

dacă f este o corespondenţă care face ca fiecărui x E D să-i corespundă un y E C ; scriem această corespondenţă f( x} = y.

Numim : D domeniul funcţiei f ; C - codomeniul funcţiei f; CD multime a functiilor cu domeniul D Ş I co­ domeniul C ; este deci echivalent. a scrie -

sau f E CD, x variabila independentă sau argumentul lui f; variabila dependent.ă ; y f(x ) - valoarea funcţ.iei f pentru valoarea x a argu­

ment.ului :

x

�

� f'(x) .

Vom lua ca primitivă ideea exprimată de propoziţi a : dăm �aloa/'ea c �a/'iab ilei x ( *) în care cE IX , IX fiind domeniul de yariaţie al v ariabileqx. S6

Se spune de obicei luăm

x =

c

( * *)

d ar trebuie observat că aICI semnul " = nu are acelasi 1 + 4. Intr-adevă;, inţeles ca în egalitatea 2 + 3 proprietatea de simetrie a egalităţii ne permite ca, din 2 + 3 = 1 + 4 să deducem că 1 + 4 = 2 + 3 ; din con-o tra, din " dăm lui x valoarea 3" nu putem deduce "dăm lui 3 valoarea x " . Uneori propoziţia ( * ) este scrisă =

x

=

( * * * ).

c

Vom sublinia faptul că nu intră în definiţia noţiunii de funcţie procedeul prin care din c căpătăm pe {(c) . D acă domeniul este finit atunci {(x) poate fi dată de· un t abel sau de un desen. De pildă, graful din figura 4 7" ne defineşte o funcţie care este d ată de tabloul ( * * * * ), .cu domeniul x

= ( al'

a2,

aa,

a4, a5, a6

)

ŞI codom eniul a,

� e,�

a,.

•

. 6,

•

57

Dacă domeniul este şirul numerelor naturale, un pro­ ·c edeu important de a defini o funcţie este definiţia re­ -curentă {( x) esLe definită prin sis �emul de egalităţi {(O) fIn + 1 )

=

=

a ( ** )

y[n,f(n)]

Dacă domeniul este multimea numerelor reale sau ·complexe, un procedeu impo;tanL de a defini o funcţie este de a o defini ca funcţie generată de o expreSIe, cum .ar fi

]f x 2

-

sin x,

i,

�: {(x)d x ,

�(x) .

o tabelă, de exemplu o tablă de logaritmi, defineş t e .() functie d e o variabilă c e ia u n număr finit d e valori ( intrările tabelei), care se extinde la o altă funcţie de o variabilă reală prin diferite procedee de interpolare ; o .aceeaşi tabelă d efineşte mai multe func ţii după proce­ -d eul de interpolare intrebuinţat. D acă o funcţie ne este dată, ne sint d ate domeniul :şi codomeniul său. De pildă funcţia { cu domeniul X = ( al' a2, a3 , a4, a5, a6) , cu codomeniul ( b l b 2 , b,), b4cb5) 'şi cu corespondenţa dată de tabloul ( *** *) de la p . 5 7 este altă funcţie decît funeţia f* cu acelaşi domeniu X şi cu codo­ meniul Y * {(a;) (i = 1, (bl, b2, b3) in care { * (ai) 2, 3, 4, 5, 6) ; { şi ( * nu sînt funcţii identice, dar sînt :funcţii egale. =

,

=

=

Aşadar, avem douEl relaţii Între funcţ.ii : IX

) egalitatea f = g definită mai sus prin

7.. '

•

domeniul lui {

(J.. " ((.re) lui ( şi g.

=

ger)

=

domeniul lui g

pentru orice x î n domeniul comun al

�) identitatea definită prin :58

W

(X"

{= g W' codomeniul lui şi �"

{

=

co domeniul lu i g, deci prin ,z' ,

ExerclJiI (Y

x

Z) x

(zy ) x

=

ZX

=

x

'yx

x

Zx ,

Y.

Dacă c e ste un element 'dat şi dacă

{D.C

D

--?

C E C,

funcţ.ia

C

care oricărui :r E D face să-i corespundă· elementul d at c, este numită funcţia constantă c . Evident, dacă. D' =1= D"

{D'.c =1= {D". Numim funcţia care

iD E D D

c·

sau

� D D -4 D, oricărui x ED face să-i i D (x) x ,

corespundă acelaşi

x:

=

l· D

este numită funcţia identică.

Restricţia şi extensiunea unei funcţii. Valoarea f( x ) a funcţiei { este definită numai pentru x ED. Fie E C D ; numim restricţia lui { la E funcţia definită pe E c D care pe E ia aceleaşi v alori cu { ; o no t ăm fi E -

(tE : E

este definită prin : pentru

x

-4

C

E E, ft d.rc)

=

{( x) .

Invers, dacă g este o fun cţi e definită pe mulţimea E, f{ : E --? C 59

şi dacă D :J E� o funcţie f este numită f pe E

extensinnea

D

�

C

lui g, d acă g este restricţia lui

Funcţia caracteristică a unei mulţimi. Funcţia ca­ racteristică fA(X) a mulţimii A este definită prin

fA ( X)

=

J \

1 dacă x °

dacă

x

e

A

�A

Deoarece x E D, fA (X) are sens dacă A C D. Funcţia fD (X) este constanta 1 ; funcţia f(lJ (x) este constanta O. 1 . fA n B (x)

=

fA (x) f8 (x)

căci fA(X) fB(X) = 1, dacă şi numai d acă f.i(X) = fa(x) = = 1 , deci dacă şi numai dacă :r E A şi x E B, adică x E A n Bt adică fAna (x) = 1 . 2 . fD-A ( x)

=

1 - fA (x)

1, atunci x E D - A , deci x � A , deci căci dacă fD_ A ( x) fA( X) = 0, deci 1 - fA ( X) = 1, i ar dacă fD_ A ( x ) = O, atunci x � D - A ; d ar x este o valoare a variabilei in­ dependente a lui fD-A , deci x € D şi x E A , deci fA ( X) 1 , deci 1 - fAx) O. =

=

=

=

3 . fAu a(x) = fA( ·1::) + fa (x) - fA ( x )fa( x ) .

D acă fA u a( X) = 0, atunci x � A U B, deci x � A şi x � B, deci = fa (x) = 0 , deci fA( X ) + fa (x) - f A ( x) fa(x) = O . D acă fAUB(X) = 1 , atunci x E A U B ; trei cazuri sînt po­ sibile, deo arece * A U B = ( A [1 B) U ( A - B ) U ( E - A ) . D acă

fA(X)

*Demonstraţia Ga exerciţiu : (A n B) U (A nB) U (BnA ) = (A n B) U (A n B) U (AnB) U (Bn A) = (A n B) U (AnB) U ( BnA)U(BnA) = [An ( BUB)] U [Bn (AUĂ)] = A U B

=

60

.x E A n B, atunci x E A şi X E B, deci fA(X ) fs (x ) 1, deci fA ( X ) + fs (x) - fA(X) fs (x) 1. D acă x E A - B, atunci .T E A, ş i x � B , deci fA(X) 1 , fs( x) = 0, fA(X) + fB (x) ­ - fA (X) fB ( X) 1 ; analog, d acă x E B - A . Deci în toate cazurile fAUS (x) fA ( X ) + fs (x) - fA. (x) fs (x) . 4 . fAUB (X) == fA (X) + fB ( X ) + fA ( X ) fB(X) ( mod. 2). 5. fA-S(X ) = fA ( X) - fA (x) fs( x) . 6 . fA+s (x) = fA(X) + fs (.T) (mod. 2) . 7. fA+S( X ) =fA.(x) + f�(x) + 1 (mod. 2) . 8. fA T s( x ) fA(X ) fsex ) !+ fA(X ) + fs(x) + 1 (mod.2). 9. fAI s (x) == f A(x) fs (x) + 1 (mod. 2 ) Deoarece fiecare submultime A a lui D este caracte­ =

=

=

=

=

=

-=

rizată de funcţia ei caracteristică fA : D � ( 0, 1 )

mulţimea (0, 1 ) , avînd două elemente, v a fi notată aici cu 2 şi mulţimea submulţimilor lui D cu 2 D :

A E 2D

echiiialează cu

A

C D.

Extinderea unei functii la o functie de submulţimile . . domeniului

Fie vom defini funcţia prin : dacă

A E 2D, ((A )

f f

D

�

C,

A

=

f : 2D

deci

A

�

2c

C D, atunci

(;, {y I y = f( x ) ,x

E A} tuturor valorilor f( x )

f (A ) este mulţimea cînd x E A . 1 . f( A U B) f (A ) U '{(B) căci y E; j (A U B) Înseamnă y f(x) , x E A U B ; dacă x E A , f(x) E f( A ) , deci f(x) E f( A ) U f(B) ; analog,

deci

=

=

dacă

,x E

B, deci

A

f(A

U B) C

A

f (A)

U

A

f(B). 61

D acă y E deci y E

((A), atunci y

flA

U B) deci

=

f(x) cu

:r

((A) C flA

E A , deci x E A U B, U

B) ; analog pentru

{(A) U{(B) C ((A U B). A C B, atunci ((A) C ;( B ) .

y E R E) ; deci 2.

Dacă

3. ((A n B) C (( A ) n (( B). 4. . ( ( B). B) �

hA

e

((A)

-

-

5. Dacă X este domeniul lui f atunci mulţimea f( X) cuprinsă în cpdomeniul oricărei funcl,ii g cu g f. =

SUR)ECTI I

În definiţia funcţiei f

D -'? C

nu este inclnsă condiţia ca f(.'E) sa p arcurgă întreg codo­ meniul C ; este posibil ca pentru un anume element Yo E e ecuaţia f ( x) Yo să nu aibă soluţie. Avem : =

f( D) C

C,

f( D) =1=

C.

d ar putem avea : Spunem că f este o surj ecţie dacă f(D)

=

e,

deci d acă oricare ar fi Yo E e, există cel puţin un Xo E D cu {( xc) = Yo' Funcţia iD este o swjecţie. Funcţiile constante nu sînt surjecţii decît dacă codome­ niul nu are decît un element.

y 62

Funcţia pseudoinversă. D acă vom considera ecuaţ,i a f(x), atunci vom numi f*(y) mulţimea tuturor e18-

=

mentelOl' x cu fI x) = y. Funcţia f * are ca domeniu pe f(D) şi ca valori submulţimi f *(Y) CD. f * f(D) � 2 D• Este natural să presupunem f(D) supunem că f este o surj ecţie şi deci f * : e � 2D .

l

Vom extinde pe f * la

x

t::

r

e, deci să pre­

*

2c � 2 D,

f*

deci

=

*( 111 ) înseamnă că x E f * (y) cu Y {(x)

=

y cu Y

E

E

iVI,

deci

111, deci. {(x) E 111 .

Exercilii 1.

f* ( M U N) =

f * (M) U f *

(N) ,

? * ( M U N) Înseamnă f(x) E M U N ; dacă f(x) E M, atunci f* (M) U f* (N), deci f* (M U N) C E f * (M) U f * (N) fie x E f * (M), C f * (M) U f * (N ) . D acă căci x E

x E f * (M), deci x E

x

deci ((x) E M, deci f(x) E M U N, deci x E f* (.IV U N)

deci

f * (M) C f * (M U N) ; analog' r" IN) C f * (MUN), deci f * ( M) U U f * (N) C f * (M U N) , deci teorema. 2.

Dacă M C N, ah.rl\;'

3.

f *(M n N)

=

{ ""

(M) C f

* (N) .

f * (M) n f * ( N ) .

într-adevăr x E f * (M n N) înseamnă fIx) E M n N, deci f(x)

E

f* (N) , deci x E f * (M) n f* (N) . Dacă x E r* (M)n

E M, f (x) E N, deci x E f * (M) şi x E n f * (N) , deci f * ( M n N) Cf * (M) n A

n f * (N) , atunci x

E

A

A

f * (M) , deci ((x) E M şi x E t * (N) ,

( (x) E N, deci ( (x) E M

n

N, deci x Ef * (M n N) , deci

n f * (N) Cf * ( iU n N), deci teorema.

deci

f * (M) 63

4.

Dacă

f: X

A C X,

Y

�

B C Y,

i = flA , :atunci

g· (B)

=

A

n

r o (B) .

II N)ECT I I

Vom spune c ă

{

D -'? C

,este o injecţie, dacă pentru x =1= y avem {(x) =1= t(y),deci ,dacă din {(x) {( y) se deduce x = y. Deci ecuaţia {( x ) = Yo are cel mult o soluţie. D acă { este o inj ecţie, atunci incluziunile 3 , 4 de l a p . 62 s e pot întări : =

3.

? (A

n

B)

4.

? (A -

B)

=

? ( A ) n f ( B) ? (A ) - f (B) y E ? ( A ) " n ? ( B) ,

=

într-adevăr, dacă

? (A ), {(x ") , x " E

a tunci y E

A şi y E ? ( B), deci y {(x") , deci x' = x" E A n B, deci y E E { ( A n B ) , deci { (A ) n { ( B ) C { (A n B). Tot astfel, dacă y E f ( A - B), atunci y {(x ' ) , x' E A - B, deci x' E A , x' It: B, deci y E ? ( A ) ; dacă y E f (B), {(x"), deci x' x" E Y = {(x") cu x " E B ; d ar {(x') A n B contrar lui x' Jt: B, deci y It: ? (B), deci y E ( ( A ) - ? ( B), deci ? (A - B) C f (A.) - ? ( B) . d eci y = {(x') , E B, deci {(x' ) A

x'

=

=

E A

A

A

=

=

64

=

Functia identică este o injectie. Funct il:le constante nu sînt il�jectii ' decît dacă domeniul are un ; �ngur element. Exercitii Dacă ( este o inj ecţie, atunci : Din ((A) C (( B) deducem A C B .

Incluziunea ca funcţie. Fie A c B. Vom defini funcţia i'A : A -7 .B prm

1 . domeniul lui �,A este A ; 2. i'A ( x)

=

x.

Bineînţeles, dacă A = B a tunci (-1 este funcţie iden­ tică. Dacă însă A C B, dar A +- E, atunci il A este res­ tricţia funcţiei i dentice. Vom considera pe il A ca o funcţie cu domeniul A şi codomeniul B. iJA este

o

injecţie.

Adeseori i,.4. va fi numită injecţia canonică a lui A

în B -::J A .

II I )Eql l

o

funcţie {: D

-7

C

este o bijecţ,ie, d acă este o injecţie şi o surj ecţie in ace­ laşi timp. Deoarece { este o surjecţie, ecuaţia {(x) y are cel pu ţin o soluţie pentru orice y E C, deci { *(y) =1= 0 pentru orice y E C ; dacă .'C ' E { *(y), X" E{ *(y), avem (( x') {(x" ) = y, deci, deoarece { este şi o inj ecţie, x' = x " ; deci f* (y) are cel mult un element, deci dacă { este o bijecţie f *(y) are un singur element ( * (y) {x }. Vom defini =

=

=


EN

=

A

A

(lEM

A

f (nor.) c n f(or.) ; (lEM

(lEM

A

A

f * ( Uor.) = U f *(or.) ; ilEM

IXEM

"

f * (nOI:) = n f * ( a:) . (lEM

(lEM

�) ;

n (or. X �) ;

ilEM I'>EN

f ( UOI:) = U f (or.) ; IXEM

X

'"

f este funcţia definită la p. 61 (extinderea lui f la o funcţie de submulţimile domeniului lui f ). 10. D acă f este o injecţie

'"

-"

f ( na) = n f (a) aEM

LEG I L E LUI M O R G A N

infinită :

aEM

pentru reuniunea ŞI intersecţia na

=

U�

(5.17)

U a = n�

(5. 18)

aEM

aEM

asM

aEM

extind formulele 1 .40 şi 1.41. Demonstraţia lui (5. 1 7 ) şi (5.18) nu este gr ea

:

x E n oc aEM

înseamnă că x � n a, deci că x nu aparţine tuturor mulaE M

ţimilor a, deci că măcar uneia nu-i aparţine, deci că există măcar o a E M cu x e IX . Aceasta înseamnă că există măcar o a E M cu x E OC, deci că xE U �. La fel pentru a aEM

demonstra p e (5. 18) observăm că X E U a înseamnă că aEM

deci că nu există nici o a E M cu x E a, deci că

X e U IX, OIEM

pentru orice IX E M avem x e oc, deci că p entru orice IX E M avem X E oc, deci că x E n �. aEM

Exerciţii

1. Dacă

,, ==

" e o relaţie de echivalenţă a = U �. �Ea/==

2. D acă 6 este un endomorfism al mulţimii X

:

6 : X -+ X, vom numi

...

Ne (X) = n 6" ( X). n�O

Avem 2.1.

6 (Ne (X) ) = Ne (X), 95

2 . 2 . dacă e

e o

surj ecţie a mulţimii ACX, atunci ACNe (A).

2 . 3 . Ne (A n B ) = Ne(A ) n Ne ( B ) . 2.4. dacă ACB, atunci Ne ( A l CNo (B ) .

PARTITI I

o mulţime P de submulţimi ale lui 1 formează o p ar­ tiţie a lui 1, dacă sînt îndeplinite următoarele condiţii :

1.

U IX

=

C1E P

1.

2. Dacă IX E P, � E P, IX -=I= � , atunci IXn �

=

0.

Clasele de echiralenţă în raport cu o relaţie de echira lenţă formează o partiţie, căci două clase de echivalenţă diferite sînt disj uncte şi, pe de altă p arte, dacă a este un element a E â şi â E IJ -=, avem 1 U â. =

dEI/=

Dacă P este o partiţie, relaţia a - b , definită prin şi b ap arţi1} aceleiaşi mulţimi a lui P, este o relaţie de echiralenţă. I ntr-adevăr, această relaţie e reflexivă şi si­ metrică ; de asemenea, dacă a :- b şi b == c, atunci a şi b, b şi c aparţin aceleiaşi mulţimi a partiţiei, deci a şi c aparţin aceleiaşi mulţimi a partiţiei, deci a c. a

-

PRODUS CARTEZIAN I N F I N IT

Fie IXI ,

•••

, IXn n mulţimi nevide. Produsul cartezian IXI X

a

X IXn

fost definit recurent (p. 79) prin (IXI X

X

IXn_1) X IXn .

Putem să-i d ăm o altă definitie : Deoarece IXI X IX2 este m �lţimea perechilor (al' a2) cu al E IXI, a2 E IX2, iar IXI X IX2 X IXa este mulţimea tri96

pIetelor (al' a2, aa ) cu al E ocl, a 2 E p în logica p ropoziţiilor : aceasta este un şir de expresii Q;l,·

Q;n, 159

care fiecare �i sau este una din formele ()(, �, y (ce intră în definit.ia demonstratiei de la p. 1 58) san oste una din ipotez�le 5)1'· 5)s . '

în

Exemplu :

5)1 este expresia p, .\12 este expresia p � q, Q;1 este expresia p, Q;2 este expresia p � q, �3 este expresia (p � q) � (p � 1)) , Q;4 este expresia p q, Q;s este expresia q. Q;1 ' (;f2 sînt SJl' 5)2' iar CE3 este axioma 7.6 ; Q';4 provine O) dacă ş,i numai dacă următoarele condiţii sînt îndeplinite : a.1) în Li există o fabrică ( Y i = 1 ) ; 1( 2) oricare ar fi localitatea L I! (h =1= i) în care există o fabrică, costul transportului de la LI! l a Cj este mai mare decît costul transportului de la L i la Ci ; �) dacă se transportă marfă de l a Li la Ci , atunci se transportă întreaga cantitate necesară centrului Ci' In tabelul de mai jos se indică, pentru fiecare centru Ci ' localităţile Li în ordinea crescătoare a costurilor trans­ porturilor de la Li la Ci : CI Ls , L4' LI ' C2 : LI ' L2 ' L4' Ca : L z, Ls, L4' C4 : L3' L4' L2'

L2 '

Ls , LI , LI '

Putem acum traduc e cu usurintă IX ) şi �) , . conditiile . prin relaţiile de mai jos : ( 8) Xn = l OYIY3Y4, X12 = 12YI' XIS = 8YIY2YaY4 , X14 = l O YIYaY4Y2' X21 = 10Y2YaY4YlJ X2Z = 1 2yzY1, X2 S = 8yz, X24 = l O Y2Y3Y4, X31 = 10ys, X32 = 12YaYI?iz'ih Xss = 8YaYz , XM = 10Ya, X41 = 10Y4Ys, X42 = 12Y4YIY2, X4S = 8Y4 Y2Ya, X44 = 10Y4YS' De exemplu, condiţia IX) arată că X2 1 > O dacă şi nu­ mai dacă Y2 = 1, dar Ys = Y4 = YI = O , adică dacă şi numai dacă Y2Ya iJ4YI = 1 . Ţinînd seama şi dp. B), deducem 188

1, liLullCi x21 1 0, iar dacă Y2YsV4Yl O ; aceste două condiţii sînt echiva­ lente tocmai cu egalitatea X21 1 0 Y217sY4Yl . în mod analog se demonstrează şi celelalte relat.ii (8) . Ţinînd seama de ( 8), f u ncţ. i a (3 ) devine

c ă dacă Y ZYSY41Î1 =

=

0 , atunci X21

=,

=

=

( 9 ) g( Yl' Y 2 ' Ys, Y4 ) = 1 0 ,7Yl + 6 , 7Y2 + 9 , 5ys + 3 , 5Y4 + + 7YIYSY4 + 1 7YIY2 YS'ii4 + 1 0 YzYaY4Yl + 8,4.Y2Yl + + 5Yz1Nil4 + 1 0,8YsYl:Y2 Y4 + 4.,8YaY2 + 8Y4 YS+ 9 ,6Y4YIY2+ + 6,4.Y4 YzYS·

Pe de altă parte, fiecare din con diţ,iile (5) este echi­ valentă cu următoarea : (1 0 )

YIY2Ya 'i 4 = O .

( Intr - a dev ăr , se vede uşor că expresiile ( 8) ale variabi­ lelor xl l , . , X44 satisfac relaţiile ( 5 ) dacă şi numai d acă cel puţin una din variabilele Y i este egală cu 1). In rezumat, p robl e ma dată revine la a găsi minimele funcţiei ( 9) , cu condiţiile restrictive (7) şi (10 ). O astfel de problemă poartă numele de problemă de programare pseudo-booleană , fiindcă funcţia de minimi­ zat ( 9 ) este o funcţie cu valori reale de variabilele Yl , Y2' Ys, Y4, care iau numai valorile ° şi 1 . APL ICAT I I Î N L I N GVIST I C A MATE MAT l C Ă *

Fie V o mulţime finită şi nevidă (numită �ocab ular) de elemente numite cu�inte. Orice sir finit ai cărui termeni sînt cuvinte este o frază pe V ci colecţie de fraze pe V e ste un limbaj pe V. Fiind date două fraze f a1a2, · an şi g b1b2 • • b"" definim operaţia de compunere a aces tor două fraze h fg a1a2 a"b1b2• • •. bm• Ope­ raţia de compunere a f razelor esLe a s ociativă ( { fg)h f(gh» , (Iar nu este comutativă, cu alte cuvinte, în general, fg -=1= -=1= gf. Lungimea u nei fraze f a1a2• an este, prin defi•

=

.

=

=

=

•

•

•

=

=

*

Acest paragraf a fost alcătu i t

•

•

de S o l o mon I\I arcus.

189,

nitie numărul n al termenilor ei. Se consideră şi fraza ()idă, de lungime egală cu zero. Fiind dat un limbaj L pe vocabularul V şi fiind date două fraze f şi g pe V, spunem că f domină pe g şi scriem * f � g dacă, oricare ar fi frazele u şi (! pe V, din uf() E L rezultă ug() E L. Este evident că relaţia de dominare de­ pinde de L. Această relaţie este reflexlvă şi tranzitivă.

Notînd cu V* limbajul universal pe V (adică mulţi­ mea tuturor frazelor pe V), putem deci spune că relaţia de dominare este o relaţie de preordine în Y*. Este uşor de văzut că relaţia � nu este antisimetrică, deci nu este, în general, o relaţ,ie de ordine în Y*. Spunem că două fraze f şi g se domină reciproc şi scriem f � g dacă avem f � g şi g � f. Relaţia de domi­ nare reciprocă este o relaţie de echivalenţă în ,V*. Dacă V este vocabularul limbii române iar L este co­ lecţia frazelor româneşti corecte, atunci frumos � subţire, dar subţire nu domină pe frumos ; într-adevăr, fraza am o carte subţire este corectă, în timp ce fraz a am o carte fru­ mos nu este corectă. Este însă usor de văzut că avem ' frumos � urît.

Semnificaţia lingvistică a relaţiei � este următoarea : dacă a E V, b E V şi a � b, atunci oricare valoare morfo­ logică a lui a este o valoare morfologică a lui b. De exem­ plu, valorile morfologice ale lui frumos sînt : adjecti() , singular, masculin şi fiecare dintre acestea este şi o va­ loare morfologică a lui subţire. însă acest din urmă adjec­ tiv posedă şi valoarea morfologică de feminin, care nu aparţine lui frumos. Semnificaţia lingvistică a relaţiei � este următoarea : clasele de echivalenţă în raport cu relaţia de dominare reciprocă sînt aşa-numitele clase de distribuţie conside­ rate în lingvistică, clasa de distribuţie a unei fraze f fiind totalitatea frazelor care apar exact În aceleaşi ambianţe ca şi f. Mai precis, numind context pe V orice pereche or­ donată < U, () > de fraze pe V şi convenind să spunem că contextul < U,() > acceptă fraza f dacă uf() E L, clasa .., Cititorul nu va confunda semnul ,, --->- " al implicaţiei (v. pp. 27, 121) cu semnul al dominaţiei din acest paragraf. , , --->-

1 90

"

de distribuţie a frazei f este totalitatea frazelor care sînt acceptate exact de aceleaşi contexte ca şi f. Fie LI C L. Spunem că LI este un sublimbaj al lui L. Fiind date două fraze x şi y, spunem că x domină pe y în raport cu LI şi scriem x -+ y LI

dacă pentru ol'ice pereche de fraze u şi � astfel încît ux� ELI avem uy� E LI' Spunem despre perechea ordonată de fraze ( x,y) că este LI -ereditară prin dominare dacă are lo c una dintre următoarele două situaţii : 10 x � y şi x r:: y ; 20 x nu domină pe y. D acă orice pereche ordonată de fraze este LI-eredi­ tară prin dominare, spunem că LI este un sublimbaj ere­ ditar prin dominare. Se poate arăta că subIimbajele ere­ ditare prin dominare alcătuiesc o algebră booleană de multimi. Spunem despre sublimbaj ul LI că este ereditar prin dZlblă dominare dacă pentru orice pereche ordonată de fraze (x,y) pentru care x � y avem x -+ y şi y X . Se Ll

--->-

LI

poate arăta că sublimbajele ereditare prin dublă domi­ nare alcătuiesc o algebră booleană de mulţimi. Fie P o partiţie a vocabularului V. Să notăm cu P(x) acel termen al p artiţiei P care conţine cuvîntul x. Se defineşte astfel o aplicaţie a lui V în P. Această apli­ c aţie este o surj ecţie, dar nu este o injecţie decît în cazul în care partiţia P este partiţia unitate (adică P ( x) {x} pentru orice x E V). I n cazul i n care L este o limbă na­ turală iar P este partiţia după flexiune (de exemplu P (verde) { verde, verzi . . }) aplicaţia considerată asociază fiecărui cuvînt totalitatea formelor sale flexionare. Această aplicaţie este o bijecţie numai în cazul lim­ bilor amorfe (cum sînt chineza şi vietnameza), limbi lip­ site de morfologie (deci în care nu există flexiune). O altă p artiţie interesantă a vocabularului V este aceea care fiecărui cuvînt x îi asociază totalitatea cuvintelor care aparţin aceleiaşi clase de distribuţie ca şi x. Această =

=

.

1 91

partiţie se notează de obicei c"" S şi se numeşte partiţia in familii. Fie din nou un limbaj L pe V şi o partiţie P a lui V. 'Şirul P( XI ) P( X2). • • P( xn), unde X1 X2 • Xn este o frază -pe V, este, prin definiţie, P - imaginea frazei X1 X2 • • • Xn prin partiţia P. Un şir P1P2• • Pn de termeni ai parti­ -ţiei P este marcat dacă el este P - imaginea a cel puţin unei fraze din L . Doi termeni Pi şi Pj se zic P-echiva­ lenţi dacă pentru orice pereche ��1 şi �2 de P-imagini :şirurile �l Pi�';,2 şi �1 Pj'1,2 sînt amîndouă marcate sau Pj. .amîndouă nemarcate. Scriem în acest caz că Pi B p Denumirea de P-echivalenţă este îndreptăţită, deoarece se verifică uşor că această relaţ,ie este reflexivă, simetrică .şi tranzitivă în mulţimea termenilor partiţiei P. Să :punem P(y ) P'(X) U •

=

P( !I) (.,) P

iVlulţ,imile P' ( x) determină o nouă partiţie a vocabularu­ lui V ; aceasta este partiţia dericmtă din P şi se notează ·cu P'. Următoarele două exemple arată semnificaţia lin­ :gvistică importantă a noţiunii de derivată a unei partiţii. Dacă P este parti ţia unitate a lui V, atunci P' este tocmai partiţia lui V în familii, despre care s-a vorbit mai sus. Dacă P este partiţia lui V după flexiune (deci P(casă) {casă, casa, casei, caselor, case, casele }, P(frumos) {frumos, frumoasă, frumoşi, frumoase , . . . } , etc . ) , atunci P' -este partiţia lui V în părţi de vorbire ( P'( casă) mulţi­ mea substantivelor, P'( frumos) mulţimea adj ectivelor calificative , etc.). D eci P' defineşte aici o surjecţie a voca­ bularului V pe mulţimea termenilor parti(.iei P'. Fie L un limbaj pe V şi fie P o partiţie a lui V (par­ tiţie pe care, pentru sugestivitatea noţ.iunilor, o gîndim -ca partiţia lui V după flexiune). Vom defini în V o rela­ ţie binară y după cum urmează ay b dacă, pentru orice .a' E P(a) şi p entru orice b' E P(b) , are loc cel puţin una din relaţiile : P(a) n S(b') -=1= (/) ; P(b) n S(a') -=1= 0. Spunem de­ ;spre cuvintele a şi b că au acelaşi gen grmnatical. Astfel, .dacă L este colecţia frazelor româneşti corecte, avem pom =

=

=

=

'1 9 2

munţi, carte y griidinii şi scaune y caiet. Relaţia este re­ flexivă şi simetrică în V, dar nu este, în general, tranzi­ tivă. Există însă o clasă importantă de limbaje pentru care y este o relaţie tranzitivă, deci o relaţie de echiva­ lenţă. Acestea sînt limbajele pentru care relaţia S ( x) n n P(y) -=1= 0 implică relaţia S(y) n P(x) -=1= 0 (x,y E V). Aceasta este situaţia în limbi ca franceza, italiana şi spaniola, dacă facem abstractie de substantivele defective de nu­ măr (deci cărora le lipsesc formele de singular sau cele de plural). y

•

Un sunet al unei limbi naturale este o multime finită de trăsături articulatorii (adică relative la mo d ul de ar­ ticulare a sunetului respectiv) . Astfel, în limb a română, {ocluziv, surd, bilabial }, F =- {fricativ , surd, labi o­ P dental }, R = { vibrativ, neutru, mediopalatal }. Fiind date două sunete A şi B concepute ca mulţimi de trăsă­ turi articulatorii, perechea ordonată * (A I B) se numeşte opoziţia dintre A şi B. Mulţimea A n B se numeşte baza opoziţiei iar mulţimile A - B şi B - A se numesc mulţi­ mile diferenţiale ale opoziţiei . Diferenţa simetrică A + B se numeşte caracteristica opoziţiei. Opoziţia (A I B) este : pri()ati(!ă în fa(!oarea lui A , dacă A n B = B, A - B -=1= @ şi B - A = @ ; pri()ati(!ă în fa(!oarea lui B dacă A n B = = A, A - B 0, B - A -=1= 0 ; pri()ati(!ă dacă este privativă în favoarea lui A sau în favoarea lui B ; opo­ ziţie zero , dacă A n B A = B, A - B = B - A = 0 ; echipolentă, dacă A - B -=1= 0 -=1= B - A , A n B -=1= 0 ; A -=1= 0, B - A = disjun cti()ă, dacă A n B = 0, A - B = B -=1= 0. Astfel, opoziţia dintre sunetele român"eşti P şi B este echipolentă, deoarece B = {ocluziv, sonor, bi­ labial }, deci P n B = {ocluziv, bilabial } =1= @, P - B = = {surd } -=1= 0 -=1= {sonor } = B - P ; opoziţia dintre sune­ tele româneşti S şi R este disjunctivă, deoarece S {fricativ, surd, dental } şi R = {vibrativ, neutru, medio­ palatal }. =

=

=

=

=

=

* N oiăm cu (A / B) pentru a respecta scrierea obişnuită in lingvistica matema tică, perechea numită obişnuit (A , B) . 1 3 - 085

193

Două opoziţii (A I /BI) şi ( A 2 /B2) se zic p roporţionale dacă ele au aceleaşi mulţimi diferenţiale, cu alte cuvinte dacă Al - BI = A 2 - B2 şi BI - A l = B2 - A 2• Se arată uşor că relaţia de proporţionalitate este o relaţie de echivalenţă în mulţimea opoziţiilor ; clasele de echi­ valenţă corespunzătoare se numesc clase de proporţionali­ tate. Astfel, în limba română opoziţia dintre sunetele S şi Z este proporţ.ională cu opoziţia dintre sunetele T şi D , S= deoarece avem S - Z T - D = {surd }, Z = D - T {sonor }. Două opo ziţii ( A I /BI) şi (A2/B2) se zic omogene dacă ele au aceeaşi bază, cu alte cuvinte dacă A l n BI A2 n n B2' Se arată uşor că relaţia de omogeneitate între două opoziţii este o relaţie de echivalenţă ; clasele de echi­ valenţă corespunzătoare se numesc clase de omogeneitate. î n limba germană, opoziţia dintre sunetele D şi B este omogenă cu opoziţia dintre D şi e, baza cQmună a aces­ tor opoziţii fiind constituită dintr-un singur element : ocIu­ ziunea slabă. O opo ziţie care nu este proporţională cu nici o altă opo­ ziţie se numeşte o poziţie izolată. Astfel, opoziţia dintre con­ soana românească L şi semiconsoana românească notată Y este izolată, deoarece nu există în limba română o consoană laterală aIta decît L , după cnm nu există o consoană anteropalatală alta decît Y. În limb a germană, opo ziţia dintre conso anele P si S este de asemenea izolată. O opoziţie care nu 'este omo genă cu nici o altă opo ziţie este prin definiţie singulară. în limba română, opoziţia dintre conso anele K şi e este singulară, deoarece K = {oclu­ ziv, surd , velar }, e {ocluziv, sonor, velar }, K ne = {ocluziv, veI ar } şi nu există nici o altă opoziţie între sy­ nete româneşti, a cărei bază să fie {ocluziv, velar }. In limb a germană, opoziţia dintre conso anele T şi D este sin­ gulară, deoarece acestea sint singurele ocluzive dentale . =

-

=

=

=

•

Fie un yocabular V , un limbaj L pe V şi o mulţime gj de elemente numite semnificatii. Sistemul de obiecte < V, L , gj > constituie un sup ; rt biplan. Orice rel aţie binară p cu domeniu l L şi codomeniul & constituie, 194

structură semantică pe suportul hiplan e st e deci o parte a produsului cartezian L X 63. Sistemul de obiecte < V, L, �, p > constituie un limbaj semantic. Într-un astfel de limb aj , două fra z e x şi y din L sînt sinonime d acă (Ez) [(xpz ) & (ypz)]. Numărul cardinal al mulţimii acelor t cu ( xpt) &(ypt) este ordinul de sinonimi e al cuplului de fra z e < x, y >. D acă x şi y sînt sinonime, dar lS(z/xpz) =f= lS(t,ypt) spunem că x şi y sînt parţial sinonime. Două fra z e sinonime care nu sînt parţial sinonime se numesc total sinonime. Două semnifica­ ţii s şi t sînt omonime d acă (Ex)[(xps)&(xpt ) ] . Numărul c ardinal al mulţimii acelor z cu (zps) &(zpt) este, prin definiţie, ordinu l de omonimie al cupl ului < s, t > . D ac ă semnifi­ c aţiile s şi t sînt omonime, dar 1S(.x/xps) =f= IS(Ylypt), spunem că f) şi t sînt parţial omonime. D ou ă semnificaţii omo ­ nime s şi t, astfel încît lS(x/xps) If.(y/ypt), sînt total dmo­

prin definiţie,
; p

=

nime.

Un limb,aj semantic < V, L, g" p > pentru care, oricare ar fi x E L mulţimea lS(s/xps) conţine cel mult un element este un limb aj fără orrtonimie. Se poate arăta că, într-un astfel de limbaj , mulţimea semnificaţiilor s pentru c are lS(z/zps ) =f=. 0 este cel mult numărabilă. Spunem despre un limbaj fără omonimie că este un limbaj ştiinţific dacă următoarele două condiţii sînt În­ deplinite IZ) Relaţia p este definită pe întregul limbaj L ( adică (Es)(xps) pentru orice x EL) ; �) Oricare ar fi semnificaţia s E �, mulţimea lS(x/xps) est e infinită. Condiţia ce revine la a spune că relaţia p este o funcţie L -l> i\\. Notînd această funcţie cu f, se poate sRune că un limbaj semantic este un limbaj ştiinţific dacă şi numai dacă el este de forma < V, L � , f > , unde f este o funcţie L -l> 63 şi fiecare mulţime de nivel nevidă a lui f este infinită. Fiind dat un suport biplan < V, L, & > , pentru c a să existe o aplicaţie f : L -l> 63 astfel încît < V, L, �, f > s ă fie un lImbaj ştiinţific este ne­ c esar şi suficient ca limbajul L să fie infinit. D acă mulţi­ mile L şi 63 sînt infinite, atunci există o funcţie f : L -l> S 195

care ia o infinitate de valori şi pentru care sistemul < V, L, .35, f > este un limbaj ştiinţific. Un limbaj semantic < V, L, 63, p > este lipsit de siTlţlnimie dacă pentru x, y E L, x =F y avem 0. �(slxps) n fO(tly pt ) Numim limbaj liric orice limbaj semantic lipsit de sinonimie, în care fiecare mulţime fO(slxjJs) (cu x E L) este de puterea continuului. adică echipotentă cu mulţ,imea numerelor reale. =

Addenda

' 1 . Produsul relaţiilor nu este comuLativ. 2. Termenii "relaţie de indentitate" şi "relaţie de ega, litate " sînt Întrebuinţ.aţi cu acelaşi înţeles.

3. D acă gof = koh spunem că diagrama x

f

-----

----- -+ y

h Z+ e

comutatiCJă.

g --

--

k

+ -+ Jtl'

Teze a l e I09 i c i i propoz i ţ i i lor

6.4. 6.5. 6.6. 6.7. 6.8.

P -+ P

(p & q) ...... P ( p & q) -+ q P -> ( p V q) q -+ ( p V a) 6 . 9 . [ p & (q V r )] -+ [ (p & q ) V ( p & 1')] 6 . 1 0 . [(p V q) & (p V 1')] -+ [p V (q & 1")] 6 . 1 1 . (p � q) -> [ (1' & p) � (1" & q) ] 6 . 1 2 . (p � q) ...... r (p & 8 ) � (q & 8) ] 6 . 1 3 . (p � q) ...... [ (1' V p) � (1' V q) } 6 . 1 4 . (p � q) -> [ (p V 8) � -+ (q V s) ] 6 . 1 5. [(p & (1 p ) ) V q ] -> q 6 . 1 6 . P ...... [p & (q V 1 q)] 6.29. [ (p -> q) & (q -+ I')J -+ (p -+ 1') 6.35. [ (p � q ) & (8 � t) �, (p & 8) � (q & 1)] 6.36. [ (p � q) & (8 � t) -> [ (p V 8) � (q V t) ] 6. 37. [(p � q) & (8 � t)] -> [ (p ...... 8) � (q -+ t) ] 6.38. (p � q) ...... [ (q -+ 1') � (p -+ 1') ] 6 . 3 9 . (p � q) [ (8 -+ q) � (8 -7- p)] 6.4.0. [ (p -> q) & (q -+ p)] ...... (p � q) 6 . 4 1 . (p � q) ...... [ (p -+ q) & (q ->- p)J 6.42. (p � q) H [ (p -+ q) & ( q ...... p )] 6.43. [ (p -+ q) & (p -+ r) J -,.. [ (p -.,. (q & r)] 6.4.4.. [(p -+ 1' ) & (q -> 1')] -+ r (p V q) -+ 1')] 6.45. (p -+ q) ...... (1 q ->- '1 p) 6.4.6 . P � 1 1 P 6 .4. 7 . P V l p '> �

6.4.8. 1 (p & 1 p)

129 129 '1 29

129

129 131 131 132 132 132 132 133 133 137 HO

'14.0 140 141 '14 1 141 141 141 '143 14.3 144. 1 4 4. 14.5 '145 199

P a g.

6 . 1,, 9. [ (p ->- q) & (p -->- 1 q )] -->- ( 1 p ) 6 . 50. [(p -+ q) & (1 p -+ q ) ] -+ q

145 145

•

7.4. 7.5. 7.6. 7.7. 7.8.

P --> - (q -+ p ) (p -+ (q -> r ) ) �� ((p ( p � q) -+ (p -+ q)

7.13. 7.14. 7.15. 7.-1 6 .

q)

-+

(p

-+

r))

> p) � q ) -+ ( q -+ q) - :>- ( (q > p ) -+ ( p � q )) & q) - -->- p ( identic cu 6.5. ) & q) -+ q (identic cu 6 . 8 . ) -+ q ) -+ ( (p -+ 1") -->- (p -)- (q & r ) ) ) P -+ (p V q) ( identică c u 6 . 7 . ) q -+ (p V q) (identică cu 6 . 8 . ) (p -+ r ) � ( (q -� r) -> ( (p V q ) -+ ,.)) ( p -->- q) -+ (1 q -+ 1 p) (identică cu 6.45) p � 1 1 P (identică cu 6.4.6 )

(p (p 7 . 9 . (p 7. 10 . (p 7 . 1 1 . (p 7.12.

-+

-

-

157 157 157 15/ 157 157 157 1 57 157 157 158 158 158

Teze a l e teo r i e i m " l ţ i m i ior şi ale l og i cei pra d i ca te l o r mona r e

a) Definiţii 6.1 * [ x E (cx n (3 ) ] � [ (x E cx ) & (x E (3 )] 6.2.* [ x E (cx U (3)] � [(x E cx) V (x E (3) 6 . 3 . * ( x E a ) H 1 ( x E cx) 6 :1 7° (cx C (3) H (x) [ (x E cx) -o- (x E r�)] 6 . 1 8° (cx = (3) H (x) [(x E cx ) � (x E (3)] 6 . 1 9° ( x) ( x E 1) 6.51° l (Ex) (x E e )

125

125 1 25 135 135 136

147

b) Tezele 6.4.* (p . 1 2 9) , . . . e lco care provin din tezele logicei pro­ poziţiilor 6.4., e Le. , înlocuind variabilele propoziţionale p, q . . . prin etc. x E cx,

e) Tezele 6.4° (p. 1 3 6 )

etc. care provin din tezele 6 . 4 * (p . 1 3 6) de tipul b prin principiul g"eneralizării. 200

d) Teze de tipul b se obţin şi înlocuind în teze ale log'iCii pr,pp �§t " ziţiilor 6 . 4 (p . 129) etc. p e p , q . . . prin P(x) , Q (x) , . . . pentr rt a: obţine teze de forma 6.4 * P(x) � P (x) . e) Teze de tipul c se obţin şi din tezele de tipul d prin principiul generaIizării, de exemplu din 6 . 4 * pe ( x) [ P ( x) -+ p( x) ]. f) Alte teze ale teoriei mulţimilor şi logicei predicatelor ll1onare : P ag.

6.30. 6.31. 6.32. 6.52. 6.53. 6.54. 6.55. 6.56.

6.57. 6.60. 6.61.

{ (x) [P(x) � Q(.r.)]} -r { [ (x) P(x)] ...,. [ (x) Q ( x)] } { (x) [ P(x) & Q(.ct) ] } � { [(x ) P(x ) ] & [ (x) Q (x)]} { (x) [ P(x) � Q(x ) ] } � ( « (x) P(x)] � [ (x) Q (x) ] } [1 (x)p ] - [ (Ex) (1 p)] [1 (Ex)p] � [ (x) (1 p) ] [ (Ex)p] _ [1 (x) (1 p) [(x)p] � (1 (Ex) (1 p) ] [( x)p] V [ (Ex) (1 p)] [ (Ex)p ] V [(x) (1 p)] 1 [ (x)p & (E.ct ) (1 p)l 1 [(Ex)p & (x) ( 1 p)]

13S 13& 139 H7

booleene

113

g) A x iomele

algebl'elor

I. 1 . O( C O( 1.2. dacă O( C (3 şi (3 C y atunci O( C y 1 . 3 . dacă O( C (3 şi (3 C CI. atunci CI. = (3 I L L O( n (3 C CI. II. 2 . O( n (3 C (3 1 1 .3. dacă y C CI. şi y C (3 atunci y C CI. n (3 1 1 . 4 . O( C CY. U (3 11.5. (3 C CI. U [3 1 1 . 6. dacă O( C y şi (3 C y atunci O( U (3 C Y II U . O( n ((3 U y ) C (O( n (3 ) U ( O( n y) JIU . O( U ((3 n y ) :::J (O( U (3) n ( O( U y) IV.1 (O( n cx:) U (3 C (3 IY.2. (O( U Ci ) n (3 :::J (3

147 147

H7

147

147

1 !>7

'14 7

129-

HO' H1

129-1 30' 1 2 9-13() H2 12 9-1 3(} 12 9-1 3 (1 143 1 3 '1 133 133: 1 3/,

Alte teze

dacă O( C (3 atunci � C li O( U Ci = I O( n iY. = 0

143 145 14&

;101

dacă dacă

ex

ex

C � şi ex C - atu nci G( = 0 1 C � şi ii C � atunci � =

Teze a l e I � g i cl i r e l a ţ I I l or b i n a r e a ) Definiţii

tl:1 ** [ x(R & S)y] � [ (xRy) & (x S y)] 6.2.** [x(R V S)y] � [(x R y ) V ( :t S .li )] tl . 3 . * * (x R y) � l (X R .li) (x S .li) ] tl . 1 700 ( R 09 S) � { (x) (y) [ (x R y) tl . 1 800 (R (=) S) � { (x) (y) [ ( x R y) � (xSy)]

1 26 1 2 7. 127

'> �

etc. care provin din teze ale logicei b ) Tezele 6.4*'� (p . 129 ) propoziţiilol' 6.4, . . . e tc. inlocuind variab ilele propoziţionale p prin xRy , . . . c ) Teze de tip ul 6. 400

(x) (y) [ (xRy) -)- (x R y)]

care provin din te z e de tipul b: (x R y) -o- (xRy) aplicînd de două ()fi principiul g-eneralizării pentru a obţine

(y) [( x R y)

-+

(xRy)]

(x) (y) [ (x R y)

-+

(xRy)]

d) Alte teze ale logicei relaţiilor binare [(x) (y) R (x, .li)] � [ (y) (.r) R ( x , y) ]

[ (Ex) (Ey) R (x, .li)] � [ (Ey) (Ex) R (x, y)] (x îi y) � (.li R x)

Teze a l e l o g i c i i pred i ca te l o r cu i d en t i t a te

7.25. 7.26. 7.27. 7.28. 7.29. 7 . 30. 202

a =a (a = b ) -+ [P(a) -+ P(b)] a) (a = b) -.... (b e) �'> (a = e)] (a = b) -+ [ ( b (oc) [(x E x) -;. (y E- ex)] -+ (x = .II ) .li) (p) [ Pix) -.,. P(yll -)- (x =

=

=

1 64 164 165 165 166 166

Indice de

E: 9 ,

semne

1 ', 9

(=) 38, H9 & 37, 1 23, 148, 152 V 40, 1 2 4 , 1-(.8, 1.52 1 ! H , l!t8, 152

g: 9 , J J 9

C 1 0 , 1 1 :\ , 14 9

U 1 1 , 1 l:3 , H . 9 n J.'i, H 3 , 1 '. 'J n, n , U, U,

CX E0 aEI u E 0 O 1 8 , 1 ·', ')

aE[

lOt" 101

� 1 , l'r9 {a} 19 :2 ':; : 27

-1 -

T .1. =.>

......

1 18

!.i t;

Jf :1 9

' 1 2 � , 1 '. 9

f (II ,

l'

�9

�

1'* 1 :2 1 ,

:, 7 , 1 ·\ 9 ') 1 ') 1 ', 8 , --,

1 f, 8 , I ,, :l

;) G

fM liO

:1 t

:2 7 ,

o

57

N'-I'---+

:29

:;0

=-o

X 51

I

- 23,

4 -'< , 197

=

:

L:' 3

f*

:i t]

Ii I r, �l

li:)

i / ) 'j �) i/ .11 f i ;,

�; (.I·l : J'(Y))

lG?

20]

I n d i ce de c u vi nte

A , ju decăţi arislotelice în A 34 (A), axioma (A) ( legea de ab­ sorbţie) 1 1 4 , 1 1 5 absorbţie, legile d e a pen iru multimi 2 3 - legile d e a pentru relaţii 40 - axioma ( A ) 1 1 4 , !li5 abstracţie, definiţie prin a 47 adevăr, valoarea logică a 1 5 1 , 1 52

adjuncţiei, regula a 1 2 6 afirmative, judecăţi particulare a (în I) 36 - - universale a (în A) 34 algebre booleene 1 'J 2 - - axiomele a. b. 1 1 3 - - multimile formează o a'b ' 113

- - relatiile a.

formează

b 11? orice a . b

o

- e o latice 1 1 5 antisime tl'ică, relatie Il � 9 - relatie strict Il 49 - inchlziunea multimilor e a 1 0 - implicaţia relaţiilor e a 3 8 apartenenţă, relaţie de Il 9 aristotelică, forma a a judecăţilor 34, 3 6 asociativitatea - conjuncţia relaţiilor e a 39 - disj uncţia relaţiilor e Il 40 - intersecţia infini tă a multimilor e a 93 , mulţimilor e Il 1 6 - produsul cartesian e Il 7 9 - produsul relaţiilor e a 42 204

reuniunea infinită a multi. milor e a 88 - reuniunea multimilor e a 1 2 - suprapune rea ftmcţiiIor e a 67 axioma (A) 1 1 4 axiomele algebrelor booleene 1 1 3 logicii pre dicatelor 1 6 1 ......:.. logicii predicatelol' c u iden­ titate 1 64 - - propoziţiilor 1 5 7 �

Banach ( teorema lui B) bijecţii 65 binare, relaţii b 3 7 , 1 4 9 bo oleene ( vezi algebre b)

107

caracteristică, funcţie c a unei m ulţimi 60 cartesian, p rodus c a două. multimi 5 1 - produs c a l mai multor mulţimi 7 8 , 9 6 - - legea de asociativitate 7 9 - - a l unei infinităţi de multimi 97 - - axioma lui Zermelo 9 9 categorie 1 7 6 Church, fu nc ţia lui c ::l 3 ciclu 1 7 0 ciclu frontieră 1 7 0 cît, mu lţimea c t.. 7 - funcţii şi rel aţii în mulţimea c

84

clase de echivalen 'tii -'06 tez.ele logicii propoziţii1Qr''1:�',! cociclu '1 7 1 dem�nstraţie, în logic'a · pre� cociclu cofron tieră '1 7 l dlcatelor 1 61 codomeniul unei functii 56 - - - predicatelor cu iden­ ' - unei relatii O tita lea 1 6 4 - - - propoziţiilor 1 5 8 cofrontieră i 7'1 comp atibilitate v., 55 - din ipoteze în logica propozitiilor 1 5 9 complementara unei mulţimi 2 3 depe�dentă, variabilă II 5(; complex -1 70 desch is, drum d 1 7 1 compoziţie ( vezi legi de e) diag'onala unui produs carte­ comutativitatea sian 53 - conjuncţiei relaţiilor 3 9 diferenţa a două mulţimi 25 - disjuncţiei relaţiilOl' ',o - simetrică a două multimi 29 - in tersectiei multimilor 1 5 - dilema, principiul !l 128 - reuniunii multil�ilor 1 1 directă, suma d a două mul­ conex, graf C 1 7 1 timi 7 0 conjuncţia propoziţiilor 1 2 3 disjuncte, mulţimi !l '1 7 - relatiilor 3 7 disj un cţ.ia (:onr!iţională a două - - asociativitatea e i 3 9 multimi 33 - - co mu lativitatea e i 3 9 - pro poziţiilor 1 2/. - - legile disf.ributive 40 - relatiilor 40 - - legile de idempotenţă 3 9 - - alte proprie tăţi ale e · r asociativitatea !l . r 40 4 0 , 42 - - comu tativitlltea d . l' /.0 - - legile distributive ale !l l' constantă, funcţie c 59 40 contradicţie, pri ncipiul c 2 4 , -- -- idl'll1 poten ţa d . r 40 lt, 5 - alte proprietăţi ale d r 40, coom ologie, grupul de c 171 {, 2 cuantor, existenţial H 6 , H9 distributivitatea, legile de d - u n iversal 1 3 4 , 149 - ale disjun cţiei şi conjunc ţiei relatiilor 40 - ale 'i ntersecţiei şi reuniunii mulţimilor 22 deductivă, schemă !l valabilă - ale intersectiei si reuniunii 156 infinite de ' mulţimi 100 definiţie prin abstracţie 4 7 - ale produsului cartesian 52 - semantică a schemelor vala­ - ale produsului relaţiilor 4.2 bile ale logicii prepoziţiilor domeniul unei functii 5 6 156 - unei relatii 43 - - a tezelor logicii propo­ duală, suma d a două 'mulţimi 2 9 ziţiilor 1 54 dublei negaţii, principiul !l . n . - sintactică a schemelor vala­ 2 4 , 144 bile ale logicii propoziţiilor drum deschis 1 71 1 60 - inchis 1 71 - - a tezelor logicii predi­ catelor 1 6 1 - - a tezelor logicii propo­ ziţiilor 1 5 9 E, ju decăţi aristo lelice în E 34 echivalenţa (sau suma duală) echivalente definitiilor sintac­ tică 'şi semantică pentru a două mulţimi 2 9 '

205

trecerea de la echivalen ţă la implicaţie şi de la impli­ caţie la echivalenţă 1 2 7 î n logica }Jropoziţiilor 1 22 relatiilor 38 - reflexivitatea e · ( 38 - simetria e · 1 " 38 38 - transitivitale e . clase de e 46 relatii de e 46 - - e generate de o funcţie 73 - silogism ipo tetic cu e 127 echivalenţa între definitia sin­ tactică şi definiţia semantică În logica prop oziţiilor 1 60 egalitatea, relaţia de e (de identitaLe ) 4 4 , 197 - - e între multimi 9 , 44 - - - - - reflexivitate V, - - - - - simetrie 44 - - - - - - transitivitat.e !,.4 - - e în Lre functii 58 reflexi- - - vitatea simetria transitivitate excluderea tertiu lui (vezi prin­ cipiul e t)' existenţial, cuauLorul e H6, 1 4 9 exponenţială, legea e pentru produsul cartesian 81 expresie în logica predicatel or '

161

- - logica predîcatclor c u identitatea 1 64 - - logica propoziţiilor 151 extinderea unei funcţii 60 - unei functii de elemente la o funcţie de mulţimi 61

fro ntieră '1 7 0 functie 5 6 - ckracLerist.icţ( a unei mul-i timi 60 constant�( 59 cu d omeniul şi codomeniul firi. i L 7 " , 7 5 206

- iden tică 59 - - e o bijecţie - - - - injecţie 65 - - - surjecţie 62 - majoritară 32 - în multimea cî t 84 - de mai' multe variabile 81 - lui Peirce 31 - lui Sheffer 30 selectivă 99 - codomeniul unei f 56 - domeniul unei 1 56 - egalitatea a două funcţii 58 - extensiunea unei f 59 - extinderea unei f de element la o f de multime 61 - identi tatea a două f 58 - restrictia unei f 59 - supra punerea a două f 66 - - leg'ea de asociativitate a ei 67 - valoarea unei f 56 funcţională, relaţie 7 7

generalizare, demonstraţie prin ' g

136

graf 1 69 - conex 1 7 1 - tare conex 1 7 1 grupul ciclurilor 1 7 0 - - frontieră 1 7 0 - cociclurilor 1 7 1 cofrontieră 1 7 1 d e coomologie 1 7 1 lanturilor 1 7 0 omologie 1 7' 1

Horn 1 7 6

1

judecăţi aristotelice î n 1 36 dempotenţa eonjuncţiei relatiilor 39 - disjuncţiei relaţiilor 40 - intersectiei multimilor 1 6 - reuniunii mulţimilor 1 4

identică, funcţia i 5 9 iden tita te, iden L i laIc f u n e Liilor 58 - relaţia de identitate (de egalitat e) , l,. 4 . 1 64, 197 - - - compatibilitatea 4/. reflexivi tatea

44,

1 65

sime t ria 4.4., 1 6 5 transitivitatea

ind iscernabilitatea 1 6 6 , - logica p redica t el o r şi a iden­ tităţii 1 6 4 imp licaţia prop oziţiilor 1 2 2 - - trecerea de la im plicaţie la echivalenţă şi de la echi­ valenţă la imp licaţie 1 2 7 - relatiilor 3 7 - - reflexivitatea 37 - - lransitivitatea 3/ incidenţă, matrice de i 1 '/ 0 independenţă var iabilA i 5 6 indexată, mulţime i 7 7 inclilziunea multimilor 1 0 - an tisime tria io - reflexivitatea 1 0 - transitivitatea 10 - ca injecţie canonică 65 . indivizi, relaţii între indivizi şi mulţimi , 1 4 9 infinilă, in tersecţie i 9 1 - produs cartesian i 96 - reuniune i 8 7 injecţie 6 4 - incluziunea ca inj ecţie 65 ipotetic, silogismul i 1 2 7 , 1 5 5 ipoteze, demons traţie din i 1 5 9 lanţ, 1 7 0 latice 1 1 4 legi d e compo ziţie '1 1 2 - - Între mulţimi - - - d ,ferenta 25 - - - - - d i ffr enta s i rn , trică (suma) 2 9 - - - - - echivalenta ' (su ma duală) 29 .- - - - - in tersecţia .

15

- - - - - "nici" , funcţia Il 31 - - - - - Peirc.(> functia lui p 31 - - - - - � euniunea 1 1 - - - - - reziduatia 27 - - - - - suma (diferenta . simetr'ică) 2 9 - - -- - suma duală (echivalenţa) 29 - - - - - SheIfer, f u n c ţia lui s 30 legi cre compo z i t ie) in tre prepo ziţii (vezi propoziţii) leg'i de compoziţie în tre relaţii - - -' - - conjuncţia 37 - - - - - - disjuncţia 40 - - - - - produsul 41 proprietăţile legilor de c.om­ p oziţie - - - -- asodat.ivi tat(>a (vezi a) - - - - comu tativi late

(vezi

e)

- - - -- idempotenţe ( vezi i) p rop rietăţi le perechilor de legi de compoziţiI" - - - - - absorbţia 2 3 , 40,

114,

l. p . i

1 64

115

- - - - - - distributivitate 23, 40, 1 1 3 logica predica telor - - axiomele l. p 1 6 1 - - demonstratia î n l. p 1 6 1 - - expresii in l. p 1 6 1 - - teze in 1. p de finiţia sin� L aclică 1 6 1 logica predicatelor cu identitate - - - - axiomele 1. p . i 1 6 4 în - - - - demonstratia . - - - - expresii în 1 . 1 64

'

p, i

- - - - teze în l. p. i 1 6 4 logica predica telor cu variabile libere 1 50 logica propoziţiilor - - axiomele 1 , P 1 57 - - demonstraţia În l. p 1 5 8 - - demonstraţia din ipoteze în I. p , 1 5 9 - - expresii în 1.11 . 1 5 1 - - scheme valabile, definiţia semantică 1 5 6 201

- - teze, d e f i niţia 154

[ 60

seman t i c ă

definitia sin tactică 1 5 7 hiva len ţ a d e fi ni ţ iilor

ec

matrice asociali'l unei relatii 1 6 7 modus poneus 1 2 6, 1 5 1;, J 5 8 -"'lorga n, legile lui 1\1 pentru in tersectie si reu n iu n i ele ' multimi' 24 - - � pentru inler�eciie şi re u n iu n i infinite de multimi . 95

mulţimi 9, 1f, 9 - multime alomiC'ă :20 - cît . 47 - de m u l ţ imi 8 5 - cu nn singur (, le m e n !' - indexată

77

J9

- t o tală 21 -- tipuri de mulţimi ( vezi ti p uri) subm ultimile u nei multimi formeazii o D Igeb rii boo­ leană ! J :1

negaţia propoziţiilor 124 negative, judecăţi particular (în O) 3 6 - - universal II (în E ) 3 !.

Ob 1 7 6 O , judecăţi aristo telice în O 36 ordine, relaţia de ordine partială 49 - relatia de ordine parţială strictă 50

partiţii 96 particulare judecăţi I' afirmative (în 1) 3 6 - judecăţi p negative (în O ) 3 6 Peirce , funcţia lui p 3 1

208

predica t e ,

l ogi ca

predicateloJ'

(vezi log'ica predicatelor)

- - - cu variabile libcl'e (vezi log'iea predicatelor cu variabile libere) preordine, rela ţia de preordine !I 5

- --- - --- reflexivi ta Lea -- --- - --- lramitivitalea

po nens, ( vezi modus p) p rincipiul contradicţiei 2 !o. ,

45

45

1 45 - dilemei I 2 B -- club Ipi negaţii 2 4 , 144 - exrlllelerii tertiului 2!" llo 5 - generalizării '! 3 6 --- silogismului ipo tetic 1 27 produs car t esi a n (vezi carte sian) produs cartesian infini t (\"ezi ca r t es i a n) produs de relaj.ii (vezi le gi de compoziţie între relaţii) propoziţii, co nju nc ţie 1 2 3 --- disj uncţio 1 2 4 - ech ivalentă 1 2 2 - impl i caţie 1 2- 1 - logica propoziţiilor (vezi logica propoziţiilor) - negaţie 1 2 !, - valoarea log'ică a unei prop oziţii 1 52 - de. teoria multimilor 1 3 6 - - d e teoria reiaţiilor binare '136 - - de teoria multimilor si . relatiilor binare 1 3 6' - pl'opoziţională, variabilă ])1'0po ziţională 1li8 prop rietăţi ale legilor de compo­ ziţie între mulţimi (vezi legi de compoziţie între mulţimi) ale legilor de comp oziţie între relaţii (vezi legi de compo­ ziţie între relaţii) ale mu lţ i milor 166 - ale relaţiilor - an tisimetria 49 compatibilitatea 44, 55

ireflexivitatea 49 - - - de a fi relatie funcţională 7 7 •

- - - reflexivitate 44, 45, 46, 49 - - - simetria 44, 46 - - - stricta antisimetrie 49 - - - transitivitate 44, 45 46, 49 reflexivitatea 44, 45, 46, 49 - echivalenţei relaţiilor 38 - identitătii 164 - implicaţiei relaţiilor 37 - incluziunii mulţimilor 10 relaţii antisirnetrice 10, 49 - bi nare 3 7 - - conjuncţia r b 3 7 - - de echivalenţă 4 6 - - - - generate de o funcţie 73 - - de identitate (de egali­ tate ) 44, 1 64, 197 - - de ordine p arţială 49 - - de ordine parţială strictă 50 - - de preordine 45 - - disjuncţia r · b 40 - - echivalenţa r ' b 38 - - functionale 77 - - implicaţia r b 37 - - negaţia unei r b 39 - - produsul . a două r . b 41 - - proprietăţile r . b (v. proprietăţile relaţiilor) - tn multimea cît 84 - între indivizi 37 - între indivizi şi mulţimi - - apartenenţa 9 - neapartenenţa 9 - Intre legi de compoziţie - - absorbţia 23 - - distribu tivitatea 22 - Intre multimi - disjuncţia 1 7 - - incluziunea 10 - Intre relaţii - - - echivalenţa 38 - - - implicaţia 3 7 - pro p rietăţile legilor d e compOZiţie între relaţii (v. - proprietăţile legilor de compoziţie) .

.

1 4 -585

-

cuaternare 54 n-are, 54 reflexive 1 0, 3 7 , 3 8 , 44, 45, strict antisimetrice 49 simetrice 1 0 , 38, 44, 46 ternare 54 transitive 10, 37, 38, 44, 45, 46, 49 restricţia unei funcţii 59 resturi 48, 120 reuniunea multimilor 1 1 - - asociativi't atea 1 2 - - comutativitatea 1 1 - - idempotenţa 1 4 reuniunea infinită 8 7 - - asociativitatea 8 8 reziduaţia 2 7

scheme deductive valabile, defi­ niţia semantică 156 selectivă, funcţie s 99 semantică (v . definiţia semantică) Sheffer, funcţia lui s 30 simetrică, (v. relaţie s) simetria echivalenţei relaţiilor 38 - idendităţii 44 - relaţiilor de echivalenţă 46 simplex O-dimensional 170 - 1-dimesional 1 70 sintactică (v:: definiţia sintactică) suma directă a două mul�imi 70 suma 29 suma duală 2 9 suprapunerea funcţmor 66 - asociativitatea s .I'. 67 strict antisimetrică 49 surjecţie 62

teze ale logicii propoziţiilor, definitia semantică 1 54 - - -' - definitia sintactică 1 57 - - - predicatelor, definiţia sintactică 1 6 1 •

2(19

- - - cu identitate, defi niţia sintactic" 1 6 !l transpuea unei relaţii !l3 - proprietăţile transpo zitiei !l3 tram;itivitatea echiva len tei re' Ia ţiilor 3 8 - ident ităţi i 44, 1 6 5 - implicaţiei relaţiilor 3 7 - inclm;iunii mulţimilor 1 0 reIa tiilor d e echivalentă 46 de preordine !l5 ' - de ordine !l9 -

-

universale, judecăţi 34

- - u

u

afirmative

negative 3!l

valoarea funcţiei 56 logică 1 5 2 variabila dependentă 5 6 - independentă 56 -

Zermelo, axiomul lui

Z

99

Tabla d e materii

l'refaţă

5

1. Algebra m u lţimi l o r

9

Incluziunea Reuniunea

10 11

Infersectla

15

M u l ti mea v i d ă , m u l t i mea fof a l ă , mul t i mi c u un s i n gur e l emenf

17

Mulţimi disjuncte Mulţimea vidă ş i mulţimile cu u n element Mulţimea totală

17

leg i l e

de

disfr ibufivifate şi de absorb t i e

18

21 22

Legile de distributivitate Legile de absorbţie

22 23

Comp l e m enfera unei m u l t i m i

23

Exercit i i

25

Diferenţa Reziduaţia Suma (diferenţa simetrică) Suma duală sau echivalenţa Funcţia lui Sheffer Funcţia "nici" Funcţia majoritară Disjuncţia condiţionată

25 27 '19 9

32 33

Forma ari s to te lică a j udecătl lor

33

O 1

I I . Algebra relaţl i l o r

37

R e l a f i i b i nare

37

Implicaţia relaţiilor Conjuncţia relaţiilor

37

37

�11

Echivalenţa relaţiilor Negaţia unei relaţii Disjuncţia relaţiilor Produsul relaţiilor Transpusa unei relaţii

38 39 40 41 43

Relafia de identi tate Relafii de echI v a l entă

44 45 46

Clase de echivalenţă

46

Relafli de ordine Produs cartez I an Rel ati i n - are

!l9 51 54

III. FuncţII

56

D e finitia notIunii de tunctle

56

R e l afii d e preordine

59 Restricţia şi extensiunea unei funcţii 60 Funcţia caracteristică a unei mulţimi Extinderea unei funcţii l a o funcţie d e submulţimile domeniului 61 Surj ectli

62

Funcţia pseudoinversă

62

I n j ecfil

64

Incluz unea ca funcţie

65

B l j ecfii

65

Suprapunerea a do u ă funct i i

66

Alte proprietăţi ale funcţiilor Relaţia de echivalenţă generată de o funcţie

70 73

Functii cu domeniul sau cu codo menIul II nlt

7 !l

Funcţii cu domeniul finit Funcţii cu domeniul şi codo meniul finit

74 75

Şiruri

76

Mulţimi indexate

77

Relati i functionale Produsul cartezi an a l mai mult or m u l ti m I

77 78

Funcţii de mai multe variabile

81

212

Proprl etăti diverse Functii şi relat i i tn multlmea ctt

' I V. Mu l t i mi d e mu l t i m i Reuniune infinită, I ntersectle I n fi nită Partltil Produs cartezian Infinit

82 84 85 87 91 96 96

Legile de idem p otenţă

99 100 103

Proprletăti a l e endomo r li s m e l or

10ii

Observaţii

1 06

Teorema l u i Banach

107 112 119

Axioma lui Zermelo Legile distributive

V. Ai gebre booleene A l gebra booleană .\} Z

VI. Red ucerea a l gebrei m u l t i m i l or , 1 a algebrei relati i l or la log i ca pred l cate l.pr

Cuantorul existential

121 121 126 129 13ii H6

VII. Ana l iza J u decăt l l o r din capitolele preceden te

H8

A l fabetul uti l i z a t

Teoria tipur i l o r

H8 1 51 157 161 16ii 167 167 169 1'7 2

V I I I . Âpl l cati l l e logi c I I matemati ce

178

Apl icati i l a teoria clas i ficării

178 182 186 189

I m p l icatla, conjuncfi a , echivalenfa, d i sjuncfle şI negati a Tipuri de demonstra tii Dem onstrati i folosind teoreme a l e logicii propoz i t i i l or Cuantorul universal

Definifla semantică a tezelor tn logica propoz itli lor Definitia sintactică a tezelor tn logica propozlfil lor Defl n l tia si ntact ică a teze lor tn lo gica pred icatelor I d entitetea Mu ltimaa e l eQ'l entelor ce au o proprietate dată Rel afll binare tntr- o mulfi m e finl/ă Teoria grafuri l or

Aplicatii l a circuitele c u contacte A plicati i tn Economia matematică A p licatII t n Lingvistica matem atică

213

Adden da

i97

Teze il i e logi c i i propoz i t i i lor

199

Te'ze ale teoriei multi m i l o r şi a l e logicii p r e d lcat e lor monare Teze al e logicii

re latIIlor bi na r e

Teze a l e logicii pred icate l or cu I ndice d e semne I nd ice de cuvinte

i dentitata

200 202

202

203

20�