+ All Categories
Home > Documents > c2lmc6 logica

c2lmc6 logica

Date post: 06-Dec-2015
Category:
Upload: popescu-mircea
View: 273 times
Download: 1 times
Share this document with a friend
Description:
c2lmc6 logicac2lmc6 logica
41
Logic˘ a matematic˘ si computat ¸ional˘ a Cursul II Claudia MURES ¸AN [email protected] Universitatea din Bucure¸ sti Facultatea de Matematic˘ si Informatic˘ a Bucure¸ sti 2011-2012, semestrul I Claudia MURES ¸AN (Universitatea din Bucure¸ sti) Curs II logic˘ a matematic˘ si computat ¸ional˘ a 2011-2012, semestrul I 1 / 41
Transcript
Page 1: c2lmc6 logica

Logica matematica si computationalaCursul II

Claudia [email protected]

Universitatea din BucurestiFacultatea de Matematica si Informatica

Bucuresti

2011-2012, semestrul I

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 1 / 41

Page 2: c2lmc6 logica

1 Multimi si functii

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 2 / 41

Page 3: c2lmc6 logica

Multimi si functii

Continuam recapitularea din sectiunea “Multimi si functii“.

Amintim din primul curs si primul seminar faptul ca are sens sa ne referim laobiecte (elemente, multimi, clase) arbitrare, pentru care nu specificam undomeniu al valorilor.

Amintim din primul seminar urmatoarea metoda de a demonstra ca douamultimi A si B satisfac incluziunea A ⊆ B: A ⊆ B ddaca, pentru oriceelement x , are loc implicatia x ∈ A ⇒ x ∈ B.

Amintim din primul seminar urmatoarea metoda de a demonstra ca douamultimi A si B sunt egale, provenita din faptul ca egalitatea de multimi esteechivalenta cu dubla incluziune ıntre ele si din metoda descrisa imediat maisus pentru demonstrarea incluziunii ıntre doua multimi: A = B ddaca, pentruorice element x , are loc echivalenta x ∈ A ⇔ x ∈ B.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 3 / 41

Page 4: c2lmc6 logica

Multimi si functii

Notatie

Alaturarea de simboluri ∃! semnifica “exista un unic“, “exista si este unic“.

Notatie

Vom nota cu ∅ multimea vida, adica multimea fara elemente. Pastram notatiilecunoscute ∪, ∩ si \ pentru reuniunea, intersectia si respectiv diferenta de multimi.De asemenea, pastram notatiile ⊆, (, ⊇ si ) pentru incluziunile si incluziunilestricte dintre multimi ın fiecare sens. Vom mai nota incluziunile stricte si cu ⊂ sirespectiv ⊃, dar numai atunci cand precizarea ca este vorba de o incluziune strictasi nu poate avea loc egalitatea de multimi nu ne foloseste ın cele prezentate.

RemarcaEste evident faptul ca singura submultime a multimii vide este multimea vida.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 4 / 41

Page 5: c2lmc6 logica

Multimi si functii

Notatie

Pentru orice elemente a si b, notam cu (a, b) perechea ordonata formata din a sib.

Definitie

Pentru orice multimi A si B, se defineste produsul cartezian dintre A si B (numitsi produsul direct dintre A si B) ca fiind multimea {(a, b) | a ∈ A, b ∈ B}, notataA× B.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 5 / 41

Page 6: c2lmc6 logica

Multimi si functii

Remarca

Se demonstreaza usor ca, pentru orice multime A, A× ∅ = ∅ × A = ∅.De asemenea, se demonstreaza usor ca produsul cartezian este distributiv fata dereuniunea, intersectia si diferenta de multimi, adica, pentru orice multimi A, B siC , au loc egalitatile:

A× (B ∪ C ) = (A× B) ∪ (A× C ) si (B ∪ C )× A = (B × A) ∪ (C × A)

A× (B ∩ C ) = (A× B) ∩ (A× C ) si (B ∩ C )× A = (B × A) ∩ (C × A)

A× (B \ C ) = (A× B) \ (A× C ) si (B \ C )× A = (B × A) \ (C × A)

Aveti ca tema pentru acasa demonstrarea tuturor acestor egalitati.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 6 / 41

Page 7: c2lmc6 logica

Multimi si functii

Definitie

Fie A si B multimi oarecare. Se numeste functie de la A la B un tripletf := (A,G ,B), unde G ⊆ A× B, a. ı., pentru orice a ∈ A, exista un unic b ∈ B,cu proprietatea ca (a, b) ∈ G .Formal: (∀a ∈ A)(∃!b ∈ B)(a, b) ∈ G .

Faptul ca f este o functie de la A la B se noteaza cu f : A → B sau Af→ B.

Multimea A se numeste domeniul functiei f , B se numeste codomeniul saudomeniul valorilor lui f , iar G se numeste graficul lui f .Pentru fiecare a ∈ A, unicul b ∈ B cu proprietatea ca (a, b) ∈ G se noteaza cuf (a) si se numeste valoarea functiei f ın punctul a.

Exemplu

Care dintre urmatoarele corespondente este o functie de la A la B?f

rrA

rrrB

ZZ~

g

rrA

rrrB

ZZ~XXz

h

rrA

rrrB

ZZ~XXz

��:

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 7 / 41

Page 8: c2lmc6 logica

Multimi si functii

Remarca

Amintim din primul curs si primul seminar ca, oricare ar fi propozitiile (i. e.proprietatile, enunturile, afirmatiile) p si q:

implicatia p ⇒ q este echivalenta cu “non p sau q“, asadar:

implicatia p ⇒ q este adevarata ddaca p e falsa sau q e adevarata

implicatia p ⇒ q este falsa ddaca p e adevarata si q e falsa

Intr-adevar, echivalenta ıntre p ⇒ q si “non p sau q“ se arata foarte usor:implicatia directa (p ⇒ q implica “non p sau q“) se demonstreaza observandca, daca are loc p ⇒ q, atunci, cand “non p“ e falsa, adica p e adevarata,rezulta ca e adevarata si q, asadar, ori de cate ori p ⇒ q este adevarata,rezulta ca si “non p sau q“ este adevarata; implicatia inversa (“non p sau q“implica p ⇒ q) rezulta din faptul ca, daca “non p sau q“ este adevarata,atunci, cand p este adevarata si deci “non p“ este falsa, rezulta ca esteadevarata q, prin urmare implicatia p ⇒ q este adevarata.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 8 / 41

Page 9: c2lmc6 logica

Multimi si functii

Remarca

Fie B o multime oarecare (poate fi vida si poate fi nevida). Atunci exista ounica functie f : ∅ → B.Intr-adevar, o functie f : ∅ → B trebuie sa fie un triplet f = (∅,G ,B), cuG ⊆ ∅ × B = ∅, deci G = ∅. Asadar, exista cel mult o functie f : ∅ → B, anumef = (∅, ∅,B) este unica posibilitate. Sa aratam ca acest triplet satisface definitiafunctiei:

(∀a ∈ ∅)(∃!b ∈ B)(a, b) ∈ ∅, i. e.:

(∀a)[a ∈ ∅ ⇒ (∃!b)(b ∈ B si (a, b) ∈ ∅)].

Pentru orice element a, proprietatea a ∈ ∅ este falsa, asadar, pentru orice elementa, implicatia [a ∈ ∅ ⇒ . . .] este adevarata. Iar acest lucru ınseamna exact faptulca ıntreaga proprietate (∀a)[a ∈ ∅ ⇒ . . .] este adevarata, deci f este functie. Prinurmare, exista o unica functie f : ∅ → B, anume f = (∅, ∅,B).

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 9 / 41

Page 10: c2lmc6 logica

Multimi si functii

Remarca

Fie A o multime nevida. Atunci nu exista nicio functie f : A → ∅.Intr-adevar, o functie f : A → ∅ trebuie sa fie un triplet f = (A,G , ∅), cuG ⊆ A×∅ = ∅, deci G = ∅. Asadar, daca ar exista o functie f : A → ∅, atunci amavea neaparat f = (A, ∅, ∅). Sa vedem daca acest triplet verifica definitia functiei:

(∀a ∈ A)(∃!b ∈ ∅)(a, b) ∈ ∅, i. e.:

(∀a)[a ∈ A ⇒ [[(∃b)(b ∈ ∅ si (a, b) ∈ ∅)] si

[(∀c)(∀d)((c ∈ ∅ si d ∈ ∅ si (a, c) ∈ ∅ si (a, d) ∈ ∅) ⇒ c = d)]]].

Oricare ar fi elementul b, proprietatea b ∈ ∅ este falsa, deci, oricare ar fielementele a si b, conjunctia (b ∈ ∅ si (a, b) ∈ ∅) este falsa, deci, oricare ar fielementul a, proprietatea (∃b)(b ∈ ∅ si (a, b) ∈ ∅) este falsa, asadar, oricare ar fielementul a, conjunctia care succede mai sus implicatiei avand ca antecedent pea ∈ A este falsa. In schimb, ıntrucat A este nevida, rezulta ca proprietatea a ∈ Aeste adevarata pentru macar un element a. Prin urmare, implicatia [a ∈ A ⇒ . . .]de mai sus este falsa pentru cel putin un element a, ceea ce ınseamna ca ıntreagaproprietate (∀a)[a ∈ A ⇒ . . .] este falsa, si deci f nu este functie.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 10 / 41

Page 11: c2lmc6 logica

Multimi si functii

Definitie

Pentru orice multimi A si B, orice functie f : A → B si orice submultimi X ⊆ A siY ⊆ B, se definesc:

imaginea lui X prin f sau imaginea directa a lui X prin f , notata f (X ), estesubmultimea lui B: f (X ) = {f (x) | x ∈ X} ⊆ B

f (A) = {f (a) | a ∈ A} ⊆ B se mai noteaza cu Im(f ) si se numeste imaginealui f

preimaginea lui Y prin f sau imaginea inversa a lui Y prin f , notata f −1(Y )(f ∗(Y ) ın unele carti, pentru a o deosebi de imaginea lui Y prin inversa f −1

a lui f , care exista numai atunci cand f este inversabila, adica numai atuncicand f este bijectiva, pe cand preimaginea unei submultimi a codomeniuluipoate fi definita pentru orice functie), este submultimea lui A:f −1(Y ) = {x ∈ A | f (x) ∈ Y } ⊆ A

Remarca

Evident, cu notatiile de mai sus, f −1(B) = A.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 11 / 41

Page 12: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

Definitie

Pentru orice multimi A si B, notam cu A∆B diferenta simetrica a lui A si B,anume: A∆B = (A \ B) ∪ (B \ A).

Notatie

Pentru orice multime T , vom nota cu P(T ) multimea partilor lui T , i. e.multimea submultimilor lui T : P(T ) = {X | X ⊆ T}.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 12 / 41

Page 13: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

Tehnica de demonstratie pentru incluziunea sau egalitatea de multimi, amintita laınceputul acestui curs, poate fi adaptata la cazul particular al submultimilor uneimultimi date T , astfel:

pentru stabilirea incluziunii ıntre doua submultimi A si B ale lui T , ın loc dea se demonstra ca, pentru orice element x , x ∈ A ⇒ x ∈ B, este suficient sase demonstreze ca, pentru orice element x ∈ T , x ∈ A ⇒ x ∈ B, ceea ce,conform metodei din cazul general, ınseamna ca A∩T ⊆ B ∩T , dar, ıntrucatA,B ∈ P(T ), avem ca A ∩ T = A si B ∩ T = B, si rezulta ca A ⊆ B;

pentru a stabili egalitatea a doua submultimi A si B ale lui T , ın loc de a sedemonstra ca, pentru orice element x , x ∈ A ⇔ x ∈ B, este suficient sa searate ca: pentru orice x ∈ T , x ∈ A ⇔ x ∈ B, ceea ce, conform varianteidemonstratiei din cazul general, arata ca: A ∩ T = B ∩ T ; dar, ıntrucatA,B ∈ P(T ), au loc: A ∩ T = A si B ∩ T = B, de unde rezulta ca A = B.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 13 / 41

Page 14: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimiDefinitie

Fie T o multime nevida arbitrara, fixata. Pentru orice A ∈ P(T ), definim functiacaracteristica a lui A (raportat la T): χA : T → {0, 1}, pentru orice x ∈ T ,

χA(x) =

{0, daca x /∈ A,

1, daca x ∈ A.

Observatie

In definitia de mai sus pentru functiile caracteristice ale submultimilor uneimultimi T , am folosit notatia (consacrata) χA pentru functia caracteristica aunei submultimi A a lui T , care sugereaza faptul ca aceasta functie ar depindenumai de A. Motivul pentru care nu se ataseaza la aceasta notatie si indicele T ,pentru a arata faptul evident ca aceasta functie depinde si de T , este ca, ın moduzual, se considera multimea totala T ca fiind fixata atunci cand lucram cufunctiile caracteristice ale partilor sale.

Remarca

In cele ce urmeaza vom considera codomeniul functiilor caracteristice {0, 1} ⊂ N(sau {0, 1} ⊂ Z, sau {0, 1} ⊂ R), iar operatiile aritmetice care vor fi efectuate vorfi operatiile uzuale de pe N (sau Z, sau R).

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 14 / 41

Page 15: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

Observatie

Pastram notatiile din definitia anterioara.Probabil ca functiile caracteristice au mai fost ıntalnite pana acum, cel putin ıncazul particular cand multimea totala T este finita: T = {x1, x2, . . . , xn}, cun ∈ N∗ = N \ {0}. In acest caz, pentru orice A ∈ P(T ), functia caracteristica χA

poate fi data prin vectorul valorilor sale: (χA(x1), χA(x2), . . . , χA(xn)); acestvector de valori din multimea {0, 1} se numeste vectorul caracteristic al lui A sipoate fi reprezentat printr-un numar scris ın baza 2.Dupa cum se stie, vectorii caracteristici (generati, de exemplu, ca numere ın binar,de la 0 la 11 . . . 1) pot fi folositi la generarea submultimilor multimii finite T :fiecare A ∈ P(T ) este egala cu multimea elementelor xi cu proprietatea ca, ınvectorul caracteristic al lui A, pe pozitia i apare 1.Ca o anticipare a similaritatilor dintre calculul cardinalelor pentru multimi finite siexpresiile functiilor caracteristice din propozitia urmatoare, este interesant deobservat ca, ın cazul particular finit prezentat mai sus, fiecare A ∈ P(T ) este, de

asemenea, finita, si are cardinalul: |A| =∑x∈T

χA(x) =n∑

i=1

χA(xi ).

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 15 / 41

Page 16: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

Propozitie (Proprietatile functiilor caracteristice)

Fie T o multime nevida arbitrara, fixata. Pentru orice A ∈ P(T ), notam cu χA

functia caracteristica a lui A (raportat la T). Mai notam functiile constante:0 : T → {0, 1} si 1 : T → {0, 1}, pentru orice x ∈ T, 0(x) = 0 si 1(x) = 1.Atunci au loc proprietatile:

1 χ∅ = 0 si χT = 1

2 pentru orice A ∈ P(T ), A = χ−1A ({1})

3 pentru orice A,B ∈ P(T ), are loc echivalenta: A ⊆ B ddaca χA ≤ χB

(punctual, i. e.: pentru orice x ∈ T, χA(x) ≤ χB(x))

4 pentru orice A,B ∈ P(T ), are loc echivalenta: A = B ddaca χA = χB

5 pentru orice A,B ∈ P(T ), χA∩B = χA · χB

6 pentru orice A ∈ P(T ), χA = χ2A

7 pentru orice A,B ∈ P(T ), χA∪B = χA + χB − χA · χB

8 pentru orice A,B ∈ P(T ), χA\B = χA − χA · χB

9 pentru orice A ∈ P(T ), χT\A = 1− χA

10 χA∆B = χA + χB − 2 · χA · χB

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 16 / 41

Page 17: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

Demonstratie: Pentru ınceput, amintim ca egalitatea a doua functii cu acelasidomeniu si acelasi codomeniu semnifica egalitatea punctuala, i. e. ın fiecarepunct, de exemplu, la punctul (4): χA = χB ddaca (prin definitia egalitatii defunctii), pentru orice x ∈ T , χA(x) = χB(x) (ıntocmai ca la punctul (3), unde amexplicitat inegalitatea ≤ ıntre doua functii cu acelasi domeniu si acelasicodomeniu).De asemenea, functiile de la punctele (5)–(10), date prin operatii aplicatefunctiilor χA si χB , sunt definite punctual, ca orice operatii asupra unor functii cuacelasi domeniu si acelasi codomeniu, operatii care se pot defini ıntre elementelecodomeniului respectiv: de exemplu, la punctul (8), functiaχA − χA · χB : T → {0, 1} se defineste prin: pentru orice x ∈ T ,(χA − χA · χB)(x) := χA(x)− χA(x) · χB(x).

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 17 / 41

Page 18: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

(1) Din faptul ca orice x ∈ T satisface: x /∈ ∅ si x ∈ T .(2) Fie x ∈ T . Avem: x ∈ A ddaca χA(x) = 1 ddaca x ∈ χ−1

A ({1}). AsadarA = χ−1

A ({1}).(3) Are loc: A ⊆ B ddaca (∀x ∈ T )(x ∈ A ⇒ x ∈ B) ddaca(∀x ∈ T )(χA(x) = 1 ⇒ χB(x) = 1) ddaca (∀x ∈ T )χA(x) ≤ χB(x) ddacaχA ≤ χB (amintim ca domeniul valorilor lui χA si χB este {0, 1}).(4) Putem folosi punctul (3): A = B ddaca [A ⊆ B si B ⊆ A] ddaca [χA ≤ χB siχB ≤ χA] ddaca χA = χB .Sau putem folosi punctul (2): A = B ddaca χ−1

A ({1}) = χ−1B ({1}) ddaca

χA = χB (amintim ca domeniul valorilor lui χA si χB este multimea cu douaelemente {0, 1}).(5) Fie x ∈ T , arbitrar, fixat. Distingem patru cazuri:

x /∈ A si x /∈ B (deci x /∈ A ∩ B)x /∈ A si x ∈ B (deci x /∈ A ∩ B)x ∈ A si x /∈ B (deci x /∈ A ∩ B)x ∈ A si x ∈ B (deci x ∈ A ∩ B)

In primul dintre aceste cazuri, χA∩B(x) = 0 = 0 · 0 = χA(x) · χB(x). La fel seanalizeaza celelalte trei cazuri, si rezulta ca χA∩B(x) = χA(x) · χB(x) pentru oricex ∈ T , i. e. χA∩B = χA · χB .

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 18 / 41

Page 19: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

(6) Aplicand (5) cazului particular A = B, obtinem: χA = χA∩A = χA · χA = χ2A.

Sau putem aplica faptul ca fiecare dintre elementele 0 si 1 este egal cu patratulsau, iar codomeniul lui χA este {0, 1}.(7) Analog demonstratiei pentru punctul (5).(8) Analog demonstratiei pentru fiecare dintre punctele (5) si (7).(9) Conform punctelor (8) si (1), χT\A = χT − χT · χA = 1− 1 · χA = 1− χA.(Este clar ca 1 · χA = χA. Se putea folosi, ca alternativa, si punctul (5), pentru adeduce: χT · χA = χT∩A = χA.)(10) Putem calcula, conform punctelor (7), (8), (5) si (1):χA∆B = χ(A\B)∪(B\A) = χA\B + χB\A − χA\B · χB\A =χA − χA · χB + χB − χA · χB − χ(A\B)∩(B\A) = χA + χB − 2 · χA · χB − χ∅ =χA + χB − 2 · χA · χB − 0 = χA + χB − 2 · χA · χB . Am aplicat faptul ca oriceelement al intersectiei (A \ B) ∩ (B \ A) simultan apartine lui A si nu apartine luiA (si simultan apartine lui B si nu apartine lui B); sigur ca nu exista un astfel deelement, asadar acea intersectie este vida.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 19 / 41

Page 20: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

Remarca

Punctul (5) al propozitiei precedente poate fi demonstrat folosind faptul cafunctiile χA∩B si χA · χB au drept codomeniu multimea cu doua elemente{0, 1} si observand ca orice x ∈ T satisface: χA∩B(x) = 1 ddaca x ∈ A ∩ Bddaca x ∈ A si x ∈ B ddaca χA(x) = 1 si χB(x) = 1 ddacaχA(x) · χB(x) = 1 ddaca (χA · χB)(x) = 1.

De asemenea, punctul (8) al propozitiei precedente poate fi demonstratfolosind faptul ca functiile care intervin ın acea egalitate au codomeniul{0, 1} si observand ca orice x ∈ T satisface: χA\B(x) = 1 ddaca x ∈ A \ Bddaca x ∈ A si x /∈ B ddaca χA(x) = 1 si χB(x) = 0 ddaca χA(x) = 1 siχA(x) · χB(x) = 0 ddaca χA(x)− χA(x) · χB(x) = 1 ddaca(χA − χA · χB)(x) = 1.

Remarca

Punctele (3) si (4) ale propozitiei precedente ne ofera posibilitatea de a demonstraincluziunea si egalitatea de multimi folosind functia caracteristica a multimilorrespective.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 20 / 41

Page 21: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimi

Remarca

A se observa ca, ın propozitia anterioara, conform punctelor (5), (7) si (8), au loc,pentru orice A,B ∈ P(T ):

χA∪B = χA + χB − χA∩B

χA\B = χA − χA∩B

De asemenea, pentru orice α, β ∈ {0, 1} (care este domeniul valorilor functiilorcaracteristice), au loc:

α · β = min{α, β}α + β − α · β = α + β −min{α, β} = max{α, β}

Aceste egalitati pot fi demonstrate, de exemplu, prin ınlocuirea fiecaruia dintreelementele α si β cu fiecare dintre valorile 0 si 1 ın fiecare egalitate.Din egalitatile de mai sus si punctele (5) si (7) ale propozitiei precedente rezultaca, pentru orice A,B ∈ P(T ), au loc:

χA∩B = min{χA, χB}χA∪B = max{χA, χB}

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 21 / 41

Page 22: c2lmc6 logica

Functia caracteristica a unei submultimi a unei multimiTeme pentru acasa: Sa se demonstreze, folosind functia caracteristica (nuconteaza fata de ce multime totala T ; se poate lua orice multime nevida T careinclude multimile care intra ın discutie, de exemplu se poate lua T egala cureuniunea acelor multimi, reunita cu o multime nevida, de exemplu {0}, pentru aavea siguranta ca T e nevida):

asociativitatea diferentei simetrice: pentru orice multimi A, B, C ,A∆(B∆C ) = (A∆B)∆C (indicatie: prin calcul, folosind propozitiaprecedenta, se obtine χA∆(B∆C) = χ(A∆B)∆C , ceea ce este echivalent cuegalitatea A∆(B∆C ) = (A∆B)∆C care trebuie demonstrata; la fel se poateproceda mai jos)distributivitatea lui ∪ fata de ∩: pentru orice multimi A, B, C ,A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )distributivitatea lui ∩ fata de ∪: pentru orice multimi A, B, C ,A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )idempotenta operatiei de trecere la complementara: pentru orice multime Tsi orice A ∈ P(T ), T \ (T \ A) = Alegile lui de Morgan pentru ∪ si ∩: pentru orice multime T si orice

A,B ∈ P(T ),

{T \ (A ∪ B) = (T \ A) ∩ (T \ B)

T \ (A ∩ B) = (T \ A) ∪ (T \ B)

alte rezultate demonstrate ın primul seminarClaudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 22 / 41

Page 23: c2lmc6 logica

Multimi si functii

Definitie

Fie A si B multimi si f : A → B o functie. f se zice:

injectiva ddaca are loc oricare dintre urmatoarele conditii echivalente:

pentru orice b ∈ B, exista cel mult un a ∈ A, astfel ıncat f (a) = bpentru orice a1, a2 ∈ A, daca a1 6= a2, atunci f (a1) 6= f (a2)pentru orice a1, a2 ∈ A, daca f (a1) = f (a2), atunci a1 = a2

surjectiva ddaca are loc oricare dintre urmatoarele conditii echivalente:

pentru orice b ∈ B, exista cel putin un a ∈ A, astfel ıncat f (a) = bf (A) = B

bijectiva ddaca are loc oricare dintre urmatoarele conditii echivalente:

f este simultan injectiva si surjectivapentru orice b ∈ B, exista exact un a ∈ A, astfel ıncat f (a) = b (formal:(∀b ∈ B)(∃!a ∈ A)f (a) = b)

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 23 / 41

Page 24: c2lmc6 logica

Functia caracteristica

Definitie

Doua multimi A si B se zic cardinal echivalente ddaca exista o functie bijectiva dela A la B, fapt notat prin: A ∼= B.

Notatie

Pentru orice multimi A si B, se noteaza cu BA multimea functiilor de la A la B:BA = {f | f : A → B}.

Propozitie

Pentru orice multime nevida T , P(T ) ∼= {0, 1}T .

Demonstratie: Consideram aplicatiaf : P(T ) → {0, 1}T = {ϕ | ϕ : T → {0, 1}}, definita prin: pentru oriceA ∈ P(T ), f (A) = χA (functia caracteristica a lui A raportat la T ).

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 24 / 41

Page 25: c2lmc6 logica

Functia caracteristica

Conform punctului (4) al propozitiei continand proprietatile functiei caracteristice,pentru orice A,B ∈ P(T ), avem:

daca A = B, atunci χA = χB , adica f (A) = f (B), deci f e bine definita (i.e. este functie, adica asociaza unui element din domeniul ei, P(T ), un unicelement din codomeniul ei, {0, 1}T )

si reciproc: daca f (A) = f (B), adica χA = χB , atunci A = B, deci f esteinjectiva.

Fie ϕ ∈ {0, 1}T , i. e. ϕ : T → {0, 1}. Fie A = ϕ−1({1}) = {a ∈ T | ϕ(a) = 1}.Atunci χA ∈ {0, 1}T are proprietatea ca, pentru orice x ∈ T : χA(x) = 1 ddacax ∈ A = ϕ−1({1}) ddaca ϕ(x) = 1. Cum χA si ϕ au ca domeniu al valorilormultimea cu doua elemente {0, 1}, rezulta ca ϕ = χA = f (A), deci f este sisurjectiva.Am demonstrat ca f : P(T ) → {0, 1}T este o bijectie, deci P(T ) ∼= {0, 1}T .

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 25 / 41

Page 26: c2lmc6 logica

Familii arbitrare de multimi

Ce este un sir de numere reale indexat de N? Un sir (xn)n∈N ⊂ R este ofunctie f : N → R. Pentru orice n ∈ N, se noteaza xn := f (n) ∈ R.

Ce este o familie arbitrara de numere reale? Fie I o multime arbitrara. Ceeste o familie de numere reale indexata de I? O familie (xi )i∈I ⊆ R este ofunctie f : I → R. Pentru orice i ∈ I , se noteaza xi := f (i) ∈ R. Elementelemultimii I se numesc indicii familiei (xi )i∈I .

Data o multime arbitrara M:

ce este un sir de elemente ale lui M indexat de N?

ce este o familie arbitrara de elemente ale lui M?

Inlocuind mai sus pe R cu M, se obtin definitiile acestor notiuni.

Ce este un sir de multimi indexat de N?

Ce este o familie arbitrara de multimi?

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 26 / 41

Page 27: c2lmc6 logica

Familii arbitrare de multimi

Definitie

Fie T o multime arbitrara. Se numeste sir de submultimi ale lui T indexat de N ofunctie f : N → P(T ). Pentru fiecare n ∈ N, se noteaza An := f (n) ∈ P(T ), iarsirul de submultimi ale lui T se noteaza cu (An)n∈N. Scriem (An)n∈N ⊆ P(T ) cusemnificatia ca, pentru fiecare n ∈ N, An ∈ P(T ).

Definitie

Fie T si I doua multimi arbitrare. Se numeste familie de submultimi ale lui Tindexata de I o functie f : I → P(T ). Pentru fiecare i ∈ I , se noteazaAi := f (i) ∈ P(T ), iar familia de submultimi ale lui T se noteaza cu (Ai )i∈I .Scriem (Ai )i∈I ⊆ P(T ) cu semnificatia ca, pentru fiecare i ∈ I , Ai ∈ P(T ).Elementele multimii I se numesc indicii familiei (Ai )i∈I .

Putem generaliza definitiile anterioare la siruri de multimi oarecare si familii demultimi oarecare, nu neaparat parti ale unei multimi precizate, dar vom aveanevoie de acea definitie mai cuprinzatoare a notiunii de functie, care permite uneifunctii f definite pe N, respectiv pe I , sa aiba drept codomeniu o clasa (nuneaparat o multime), anume clasa tuturor multimilor ın acest caz.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 27 / 41

Page 28: c2lmc6 logica

Operatii cu familii arbitrare de multimi

Definitie

Fie I o multime arbitrara si (Ai )i∈I o familie de multimi (parti ale unei multimi Tsau multimi arbitrare) indexata de I .Se definesc urmatoarele operatii:

reuniunea familiei (Ai )i∈I este multimea notata⋃i∈I

Ai si definita prin:

⋃i∈I

Ai = {x | (∃i ∈ I )x ∈ Ai}

intersectia familiei (Ai )i∈I este multimea notata⋂i∈I

Ai si definita prin:

⋂i∈I

Ai = {x | (∀i ∈ I )x ∈ Ai}

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 28 / 41

Page 29: c2lmc6 logica

Operatii cu familii arbitrare de multimi

Definitie

produsul cartezian al familiei (Ai )i∈I (numit si produsul direct al familiei

(Ai )i∈I ) este multimea notata∏i∈I

Ai si definita prin:

∏i∈I

Ai = {(ai )i∈I ⊆⋃i∈I

Ai | (∀i ∈ I )ai ∈ Ai},

sau, altfel scris (cu definitia unei familii de elemente exemplificate mai sus pefamilii de numere reale):∏

i∈I

Ai = {f | f : I →⋃i∈I

Ai , (∀i ∈ I )f (i) ∈ Ai}.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 29 / 41

Page 30: c2lmc6 logica

Operatii cu familii arbitrare de multimiExemplu

Fie T si I doua multimi nevide si (Ai )i∈I ⊆ P(T ) o familie de parti ale lui Tindexata de I . Sa demonstram urmatoarele egalitati satisfacute de functiilecaracteristice raportat la T :

χ⋃i∈I Ai

= max{χAi | i ∈ I}χ⋂

i∈I Ai= min{χAi | i ∈ I}

Sa notam cu F := max{χAi | i ∈ I} : T → {0, 1}, definita, desigur, punctual:pentru orice x ∈ T , F (x) = max{χAi (x) | i ∈ I}. Observam ca maximul uneifamilii de elemente din multimea {0, 1} este egal cu 1 ddaca exista macar unelement egal cu 1 ın acea familie. Pentru orice x ∈ T , avem: χ⋃

i∈I Ai(x) = 1

ddaca x ∈⋃i∈I

Ai ddaca (∃i ∈ I )x ∈ Ai ddaca (∃i ∈ I )χAi (x) = 1 ddaca

max{χAi (x) | i ∈ I} = 1 ddaca F (x) = 1. Rezulta ca χ⋃i∈I Ai

= F , ıntrucat

codomeniul acestor doua functii este multimea cu doua elemente {0, 1}.Aveti demonstrarea celei de–a doua egalitati ca tema. Indicatie: observati caminimul unei familii de elemente din multimea {0, 1} este egal cu 1 ddaca toateelementele acelei familii sunt egale cu 1, si rescrieti demonstratia de mai susınlocuind ın ea maximul cu minimul, ∃ cu ∀ si reuniunea cu intersectia.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 30 / 41

Page 31: c2lmc6 logica

Numere cardinale

Amintim ca spunem ca doua multimi A si B sunt cardinal echivalente, si scriemA ∼= B, ddaca exista o bijectie f : A → B.

Definitie

Pentru orice multime A, se numeste cardinalul lui A sau numarul cardinal al lui Aclasa tuturor multimilor B cu A ∼= B, notata |A|.

Este simplu de demonstrat, folosind operatii cu bijectii pe care le consideramcunoscute din gimnaziu si liceu, ca:

pentru orice multime A, A ∼= A, deci A ∈ |A|pentru orice multimi A si B, daca A ∼= B, atunci B ∼= A si |A| = |B|, i. e.orice multime C satisface A ∼= C ddaca satisface B ∼= C

pentru orice multimi A si B, daca A � B, atunci nu exista nicio multime Ccu proprietatile: C ∈ |A| (i. e. A ∼= C ) si C ∈ |B| (i. e. B ∼= C )

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 31 / 41

Page 32: c2lmc6 logica

Numere cardinale

Definitie

Pentru orice multimi A si B, notam cu:

|A| ≤ |B| faptul ca exista o injectie j : A → B

|A| < |B| faptul ca |A| ≤ |B| si |A| 6= |B|, i. e. exista o injectie j : A → B,dar nu exista nicio bijectie f : A → B

Teorema (Cantor)

Pentru orice multime X , |X | < |P(X )|.

Demonstratie: Daca X = ∅, atunci se poate verifica faptul ca unica functief : X = ∅ → P(X ) = P(∅) = {∅}, anume f = (∅, ∅, {∅}), este injectie, dar nueste surjectie, deci nu este bijectie.Pentru cele ce urmeaza, sa presupunem ca X 6= ∅.Definim j : X → P(X ), pentru orice x ∈ X , j(x) = {x} ∈ P(X ). Functia j estebine definita si injectiva, pentru ca, oricare ar fi x , y ∈ X cu j(x) = j(y), i. e.{x} = {y}, rezulta x = y (deoarece doua multimi coincid ddaca au aceleasielemente). Asadar |X | ≤ |P(X )|.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 32 / 41

Page 33: c2lmc6 logica

Numere cardinale

Sa presupunem prin absurd ca exista o surjectie g : X → P(X ). Deci, pentru oricex ∈ X , g(x) ∈ P(X ), i. e. g(x) ⊆ X . Sa notamA := {x ∈ X | x /∈ g(x)} ∈ P(X ). g este surjectiva, prin urmare exista unelement x0 ∈ X a. ı. g(x0) = A.Paradox: x0 ∈ g(x0) = A sau x0 /∈ g(x0) = A?Daca x0 ∈ g(x0) = A = {x ∈ X | x /∈ g(x)}, rezulta ca x0 /∈ g(x0).Daca x0 /∈ g(x0) = A = {x ∈ X | x /∈ g(x)}, rezulta ca x0 ∈ A = g(x0).Am obtinut o contradictie (ın fiecare situatie posibila), prin urmare presupunereafacuta este falsa, adica nu exista nicio surjectie g : X → P(X ), deci nu existanicio bijectie f : X → P(X ), asadar X � P(X ), deci |X | 6= |P(X )|.Asadar |X | < |P(X )|.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 33 / 41

Page 34: c2lmc6 logica

Numere cardinale

Numerele naturale pot fi construite cu ajutorul cardinalelor (al numerelorcardinale), ıntr–un mod care nu este fundamental diferit de constructiamentionata ın primul curs:

0 := |∅|,1 := |{∅}|,2 := |{∅, {∅}}|,3 := |{∅, {∅}, {∅, {∅}}}|,...

Mereu se considera multimea avand drept elemente toate multimile de la pasiianteriori.Multimea numerelor naturale, N, este o multime infinita, si este o multimenumarabila.

Ce este o multime numarabila?

Ce este o multime infinita?

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 34 / 41

Page 35: c2lmc6 logica

Numere cardinale

Notatie

Cardinalul multimii numerelor naturale se noteaza cu ℵ0, pronuntat “alef 0“:ℵ0 := |N|.

Definitie

O multime X se zice numarabila ddaca |X | = ℵ0, i. e. ddaca X ∼= N.

Definitie

O multime X se zice infinita:

1 ın sens Dedekind, ddaca exista S ( X a. ı. S ∼= X

2 ın sens Cantor, ddaca exista S ⊆ X , a. ı. S este numarabila

3 ın sens obisnuit, ddaca, pentru orice n ∈ N, X � {1, 2, . . . , n}

TeoremaCele trei definitii de mai sus ale multimilor infinite sunt echivalente.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 35 / 41

Page 36: c2lmc6 logica

Numere cardinale

Observatie

Pentru demonstratia teoremei anterioare, a se vedea finalul primului capitol alcartii: D. Busneag, D. Piciu, Lectii de algebra, Editura Universitaria Craiova,2002. Aceasta demonstratie nu face parte din materia pentru examen.

Desigur, o multime finita este, prin definitie, o multime care nu este infinita,adica, ın conformitate cu definitia de mai sus a multimilor infinite ın sens obisnuit,o multime finita este o multime X cu proprietatea ca X ∼= {1, 2, . . . , n} pentru unanumit n ∈ N. (Desigur, am folosit licenta de scriere (conventia):{1, 2, . . . , n} = ∅ pentru n = 0.)

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 36 / 41

Page 37: c2lmc6 logica

Numere cardinale

Definitia multimilor infinite ın sens Cantor arata ca ℵ0 (i. e. cardinalul multimilornumarabile) este cel mai mic cardinal infinit, unde cardinal infinit (sau cardinaltransfinit) ınseamna cardinal al unei multimi infinite. In particular, N este omultime infinita, si orice multime numarabila este o multime infinita.

Definitie

O multime cel mult numarabila este o multime finita sau numarabila (adica avandcardinalul mai mic sau egal cu ℵ0).

N este o multime infinita, deci, conform definitiei multimilor infinite ın sensDedekind, poate fi pusa ın bijectie cu o submultime proprie (i. e. stricta, i. e.diferita de ıntreaga multime N) a sa.

Exemplu

Un hotel are o infinitate de camere, numerotate cu numerele naturale, si toatecamerele sale sunt ocupate. Cum poate fi cazat un nou turist ın acel hotel?Solutie: mutam ocupantul camerei 0 ın camera 1, pe cel al camerei 1 ın camera 2,pe cel al camerei 2 ın camera 3 s. a. m. d.. Iar noul turist este cazat ın camera 0.“Morala:“ cum punem pe N ın bijectie cu N∗ := N \ {0}? Definim f : N → N∗,pentru orice n ∈ N, f (n) = n + 1. f este o bijectie.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 37 / 41

Page 38: c2lmc6 logica

Numere cardinale

Exemplu

Un hotel are o infinitate de camere, numerotate cu numerele naturale, si toatecamerele sale sunt ocupate. Cum pot fi cazati un milion de noi turisti ın acelhotel?Solutie: mutam ocupantul camerei 0 ın camera 1.000.000, pe cel al camerei 1 ıncamera 1.000.001, pe cel al camerei 2 ın camera 1.000.002 s. a. m. d.. Iar noiituristi sunt cazati ın camerele 0, 1, 2, . . . , 999.999.“Morala:“ cum punem pe N ın bijectie cuN \ 0, 999.999 = {n ∈ N | n ≥ 1.000.000}? Definim g : N → N \ 0, 999.999,pentru orice n ∈ N, g(n) = n + 1.000.000. g este o bijectie.

Remarca

Multimea Z a numerelor ıntregi este numarabila. Intr-adevar, functia h : Z → N,

definita prin: pentru orice x ∈ Z, h(x) =

{2x , daca x ≥ 0,

−2x − 1, daca x < 0,este o bijectie.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 38 / 41

Page 39: c2lmc6 logica

Numere cardinale

RemarcaMultimea Q a numerelor rationale este numarabila, fapt care poate fi demonstratprintr-o mare varietate de procedee, cum ar fi: punand mai ıntai pe Q ∩ [0,∞) ın

bijectie cu cu Q ∩ [0, 1) prin x x

x + 1, apoi pe Q ∩ [0, 1) ın bijectie cu N prin

asezarea elementelor lui Q ∩ [0, 1) ın sirul0

1,0

2,1

2,0

3,1

3,2

3, . . . ,

0

n,1

n,2

n, . . . ,

n − 1

n,

0

n + 1, . . . si eliminarea duplicatelor din

acest sir, iar pasii de pana acum conduc, prin compunere de bijectii, la existentaunei bijectii π : Q ∩ [0,∞) → N cu π(0) = 0 (deciπ |Q∩(0,∞): Q ∩ (0,∞) → N∗ = N \ {0} este, la randul ei, o bijectie), ceea cepermite obtinerea unei bijectii f : Q → N, definite prin: pentru orice x ∈ Q,

f (x) =

{2π(x), daca x ≥ 0,

2π(−x)− 1, daca x < 0.A se vedea alte metode de a construi o

bijectie ıntre Q si N ın primul capitol al cartii: D. Busneag, D. Piciu, Lectii dealgebra, Editura Universitaria Craiova, 2002.

Observatie

Demonstrarea faptului ca Q ∼= N nu face parte din materia pentru examen.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 39 / 41

Page 40: c2lmc6 logica

Numere cardinale

Remarca

Multimea R a numerelor reale nu este numarabila (sigur ca este infinita, ın bazadefinitiei lui Cantor pentru multimile infinite, deoarece include pe N). Acest faptpoate fi aratat, de exemplu, prin procedeul diagonal al lui Cantor: saconsideram o functie arbitrara f : N → R si, pentru fiecare n ∈ N, sa scriem pef (n) ca fractie zecimala: f (n) = [f (n)] + 0, an,1an,2an,3 . . . an,nan,n+1 . . . an,k . . .,unde [f (n)] este partea ıntreaga a lui f (n) si an,1, an,2, an,3, . . . sunt cifrele zecimalede dupa virgula ale lui f (n). Sa consideram un numar real b, cu scrierea ca fractiezecimala: b = 0, b1b2b3 . . . bn . . ., cu cifrele zecimale b1, b2, b3, . . . , bn, . . . si cuproprietatea ca, pentru orice n ∈ N, bn /∈ {0, an,n, 9} (eliminam pe 0 si 9 pentru aevita cazul dat de egalitatea 1 = 0, (9) = 0, 9999 . . ., usor verificabila prinexprimarea cu fractii a acestor numere). Atunci, pentru orice n ∈ N, b 6= f (n),pentru ca au a n−a zecimala diferita, ceea ce arata ca f nu este surjectiva. Decinu exista nicio surjectie de la N la R, asadar nu exista nicio bijectie ıntre N si R.

Remarca

Se poate arata ca R ∼= P(N).

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 40 / 41

Page 41: c2lmc6 logica

Numere cardinale

Este |R| primul cardinal infinit nenumarabil?

Definitie

|R| se numeste puterea continuumului.

Ipoteza continuumului: Nu exista niciun cardinal C cu proprietatea caℵ0 = |N| < C < |R|. (Adica |R| este primul cardinal infinit nenumarabil.)

S-a demonstrat ca:

ipoteza continuumului este o proprietate independenta de sistemeleconsacrate de axiome pentru teoria multimilor (Zermelo–Fraenkel, vonNeumann–Bernays–Godel etc.), i. e. nu poate fi nici demonstrata, niciinfirmata pornind de la axiomele din aceste sisteme.

Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 41 / 41


Recommended