Structuri discrete - Curs3: Relații

83
Curs 3: Relat , ii; Propriet˘ at , i; Operat , ii Structuri discrete (F.02.O.13) Radu Dumbr˘ aveanu Universitatea de Stat “A. Russo” din B˘ alt , i Facultatea de S , tiint , e Reale Aceast˘ a prezentare este pus˘ a la dispozit ¸ie sub Licent ¸a Atribuire - Distribuire-ˆ ın-condit ¸ii-identice 3.0 Ne-adaptat˘ a (CC BY-SA 3.0) 2013 R. Dumbr˘ aveanu (USARB) Curs 3: Relat , ii; Propriet˘ at , i; Operat , ii 2013 1 / 28

description

Structuri discrete - Curs3: Relații

Transcript of Structuri discrete - Curs3: Relații

Page 1: Structuri discrete - Curs3: Relații

Curs 3: Relat, ii; Proprietat, i; Operat, iiStructuri discrete (F.02.O.13)

Radu Dumbraveanu

Universitatea de Stat “A. Russo” din Balt, iFacultatea de S, tiint,e Reale

Aceasta prezentare este pusa la dispozitie sub Licenta Atribuire -Distribuire-ın-conditii-identice 3.0 Ne-adaptata (CC BY-SA 3.0)

2013

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 1 / 28

Page 2: Structuri discrete - Curs3: Relații

Produs cartezian

Definit, ieFiind date doua mult, imi A s, i B vom numi produs cartezian s, i vom notaprin A× B, mult, imea tuturor perechilor ordonate de elemente din A s, i Bdefinita astfel:

A× B = {(a, b) : a ∈ A, b ∈ B}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 2 / 28

Page 3: Structuri discrete - Curs3: Relații

Produs cartezian

Fiind data o a treia mult, ime C putem construi urmatoarele produsecarteziene:

(A× B)× C = {((a, b), c) : a ∈ A, b ∈ B, c ∈ C}

A× (B × C ) = {(a, (b, c)) : a ∈ A, b ∈ B, c ∈ C}

A× B × C = {(a, b, c) : a ∈ A, b ∈ B, c ∈ C}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 3 / 28

Page 4: Structuri discrete - Curs3: Relații

Produs cartezian

Fiind data o a treia mult, ime C putem construi urmatoarele produsecarteziene:

(A× B)× C = {((a, b), c) : a ∈ A, b ∈ B, c ∈ C}

A× (B × C ) = {(a, (b, c)) : a ∈ A, b ∈ B, c ∈ C}

A× B × C = {(a, b, c) : a ∈ A, b ∈ B, c ∈ C}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 3 / 28

Page 5: Structuri discrete - Curs3: Relații

Produs cartezian

Fiind data o a treia mult, ime C putem construi urmatoarele produsecarteziene:

(A× B)× C = {((a, b), c) : a ∈ A, b ∈ B, c ∈ C}

A× (B × C ) = {(a, (b, c)) : a ∈ A, b ∈ B, c ∈ C}

A× B × C = {(a, b, c) : a ∈ A, b ∈ B, c ∈ C}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 3 / 28

Page 6: Structuri discrete - Curs3: Relații

Produs cartezian

Fiind data o a treia mult, ime C putem construi urmatoarele produsecarteziene:

(A× B)× C = {((a, b), c) : a ∈ A, b ∈ B, c ∈ C}

A× (B × C ) = {(a, (b, c)) : a ∈ A, b ∈ B, c ∈ C}

A× B × C = {(a, b, c) : a ∈ A, b ∈ B, c ∈ C}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 3 / 28

Page 7: Structuri discrete - Curs3: Relații

Produs cartezian

Elementele produslui cartezian de forma A1 ×A2 × ...×An se numescn-upluri ordonate.

Mult, imile A1, A2, ..., An se numesc factorii produsului cartezian, iarelementele a1, a2,...,an se numesc coordonatele (sau proiect, iile)elementului (a1, a2, ..., an).

In cazul cınd A1 = A2 = ... = An = A putem nota A1 ×A2 × ...×An cuAn .

Adica, A2 = A×A; A3 = A×A×A; An = A×A× ...×A︸ ︷︷ ︸n

.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 4 / 28

Page 8: Structuri discrete - Curs3: Relații

Produs cartezian

Elementele produslui cartezian de forma A1 ×A2 × ...×An se numescn-upluri ordonate.

Mult, imile A1, A2, ..., An se numesc factorii produsului cartezian, iarelementele a1, a2,...,an se numesc coordonatele (sau proiect, iile)elementului (a1, a2, ..., an).

In cazul cınd A1 = A2 = ... = An = A putem nota A1 ×A2 × ...×An cuAn .

Adica, A2 = A×A; A3 = A×A×A; An = A×A× ...×A︸ ︷︷ ︸n

.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 4 / 28

Page 9: Structuri discrete - Curs3: Relații

Produs cartezian

Elementele produslui cartezian de forma A1 ×A2 × ...×An se numescn-upluri ordonate.

Mult, imile A1, A2, ..., An se numesc factorii produsului cartezian, iarelementele a1, a2,...,an se numesc coordonatele (sau proiect, iile)elementului (a1, a2, ..., an).

In cazul cınd A1 = A2 = ... = An = A putem nota A1 ×A2 × ...×An cuAn .

Adica, A2 = A×A; A3 = A×A×A; An = A×A× ...×A︸ ︷︷ ︸n

.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 4 / 28

Page 10: Structuri discrete - Curs3: Relații

Produs cartezian

Elementele produslui cartezian de forma A1 ×A2 × ...×An se numescn-upluri ordonate.

Mult, imile A1, A2, ..., An se numesc factorii produsului cartezian, iarelementele a1, a2,...,an se numesc coordonatele (sau proiect, iile)elementului (a1, a2, ..., an).

In cazul cınd A1 = A2 = ... = An = A putem nota A1 ×A2 × ...×An cuAn .

Adica, A2 = A×A; A3 = A×A×A; An = A×A× ...×A︸ ︷︷ ︸n

.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 4 / 28

Page 11: Structuri discrete - Curs3: Relații

Produs cartezian; Submult, imi; Exemple

Fie A = {A,B,C ,D}, B = {1, 2, 3, 4}.

A B C D

1

2

3

4

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 5 / 28

Page 12: Structuri discrete - Curs3: Relații

Produs cartezian; Submult, imi; Exemple

Fie A = {A,B,C ,D}, B = {1, 2, 3, 4}.

A B C D

1

2

3

4

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 5 / 28

Page 13: Structuri discrete - Curs3: Relații

Produs cartezian; Submult, imi; Exemple

Fie A = {A,B,C ,D}, B = {1, 2, 3, 4}.

A B C D

1

2

3

4

C = {(A, 4), (B, 3), (C , 2), (D, 1)} ⊆ A× B.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 5 / 28

Page 14: Structuri discrete - Curs3: Relații

Produs cartezian; Submult, imi; Exemple

Fie A = {A,B,C ,D}, B = {1, 2, 3, 4}.

A B C D

1

2

3

4

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 5 / 28

Page 15: Structuri discrete - Curs3: Relații

Produs cartezian; Submult, imi; Exemple

x

y

Z× Z sau Z2

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 6 / 28

Page 16: Structuri discrete - Curs3: Relații

Relat, ii binare

O relat, ie binara este o submult, ime a unui produs cartezian de formaA× B.

Din acest motiv mai spunem ca avem o relat, ie binara de la A la B.

O relat, ie ternara ıntre mult, imile A, B s, i C este o submult, ime aA× B × C .

De exemplu,

I {(0, 1), (1, 0)} ⊆ Z2;I {(0, 0, 1), (0, 1, 0), (1, 0, 0)} ⊆ Z3;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 7 / 28

Page 17: Structuri discrete - Curs3: Relații

Relat, ii binare

O relat, ie binara este o submult, ime a unui produs cartezian de formaA× B.

Din acest motiv mai spunem ca avem o relat, ie binara de la A la B.

O relat, ie ternara ıntre mult, imile A, B s, i C este o submult, ime aA× B × C .

De exemplu,

I {(0, 1), (1, 0)} ⊆ Z2;I {(0, 0, 1), (0, 1, 0), (1, 0, 0)} ⊆ Z3;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 7 / 28

Page 18: Structuri discrete - Curs3: Relații

Relat, ii binare

O relat, ie binara este o submult, ime a unui produs cartezian de formaA× B.

Din acest motiv mai spunem ca avem o relat, ie binara de la A la B.

O relat, ie ternara ıntre mult, imile A, B s, i C este o submult, ime aA× B × C .

De exemplu,

I {(0, 1), (1, 0)} ⊆ Z2;I {(0, 0, 1), (0, 1, 0), (1, 0, 0)} ⊆ Z3;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 7 / 28

Page 19: Structuri discrete - Curs3: Relații

Relat, ii binare

O relat, ie binara este o submult, ime a unui produs cartezian de formaA× B.

Din acest motiv mai spunem ca avem o relat, ie binara de la A la B.

O relat, ie ternara ıntre mult, imile A, B s, i C este o submult, ime aA× B × C .

De exemplu,

I {(0, 1), (1, 0)} ⊆ Z2;I {(0, 0, 1), (0, 1, 0), (1, 0, 0)} ⊆ Z3;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 7 / 28

Page 20: Structuri discrete - Curs3: Relații

Relat, ii n-are

Definit, ieO relat, ie n-ara ıntre mult, imile A1, A2, ..., An este o structura ordonata deforma ρ = (A1,A2, ...,An ,R) unde R ⊆ A1 ×A2 × ...An . Mult, imea R senumes, te graficul relat, iei ρ.

In particular, daca A1 = A2 = ... = An = A spunem ca avem o relat, ien-ara omogena pe A.

Daca R = A1 ×A2 × ...×An relat, ia se numes, te universala.

Daca R = ∅ - relat, ie vida.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 8 / 28

Page 21: Structuri discrete - Curs3: Relații

Relat, ii n-are

Definit, ieO relat, ie n-ara ıntre mult, imile A1, A2, ..., An este o structura ordonata deforma ρ = (A1,A2, ...,An ,R) unde R ⊆ A1 ×A2 × ...An . Mult, imea R senumes, te graficul relat, iei ρ.

In particular, daca A1 = A2 = ... = An = A spunem ca avem o relat, ien-ara omogena pe A.

Daca R = A1 ×A2 × ...×An relat, ia se numes, te universala.

Daca R = ∅ - relat, ie vida.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 8 / 28

Page 22: Structuri discrete - Curs3: Relații

Relat, ii n-are

Definit, ieO relat, ie n-ara ıntre mult, imile A1, A2, ..., An este o structura ordonata deforma ρ = (A1,A2, ...,An ,R) unde R ⊆ A1 ×A2 × ...An . Mult, imea R senumes, te graficul relat, iei ρ.

In particular, daca A1 = A2 = ... = An = A spunem ca avem o relat, ien-ara omogena pe A.

Daca R = A1 ×A2 × ...×An relat, ia se numes, te universala.

Daca R = ∅ - relat, ie vida.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 8 / 28

Page 23: Structuri discrete - Curs3: Relații

Relat, ii n-are

Definit, ieO relat, ie n-ara ıntre mult, imile A1, A2, ..., An este o structura ordonata deforma ρ = (A1,A2, ...,An ,R) unde R ⊆ A1 ×A2 × ...An . Mult, imea R senumes, te graficul relat, iei ρ.

In particular, daca A1 = A2 = ... = An = A spunem ca avem o relat, ien-ara omogena pe A.

Daca R = A1 ×A2 × ...×An relat, ia se numes, te universala.

Daca R = ∅ - relat, ie vida.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 8 / 28

Page 24: Structuri discrete - Curs3: Relații

Relat, ii binare

Daca ρ = (A,B,R) atunci ınscierea aρb este echivalenta cu (a, b) ∈ R.

De exemplu, fie A = {0, 1, 2} atunci relat, ia “<” este(A,A, {(0, 1), (0, 2)}).

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 9 / 28

Page 25: Structuri discrete - Curs3: Relații

Relat, ii binare

Daca ρ = (A,B,R) atunci ınscierea aρb este echivalenta cu (a, b) ∈ R.

De exemplu, fie A = {0, 1, 2} atunci relat, ia “<” este(A,A, {(0, 1), (0, 2)}).

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 9 / 28

Page 26: Structuri discrete - Curs3: Relații

Imaginea directa; Imaginea inversa

Domeniul relat, iei dom(ρ) = {a ∈ A : ∃b ∈ B ıncıt (a, b) ∈ R}.

Codomeniul relat, iei codom(ρ) = {b ∈ B : ∃a ∈ A ıncıt (a, b) ∈ R}.

Imaginea directa a mult, imii X ⊆ A prin relat, ia ρ esteρ(X) = {b ∈ B : ∃a ∈ X , aρb}.

Imaginea inversa a mult, imii Y ⊆ B prin relat, ia ρ esteρ−1(Y ) = {a ∈ A : ∃b ∈ Y , aρb}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 10 / 28

Page 27: Structuri discrete - Curs3: Relații

Imaginea directa; Imaginea inversa

Domeniul relat, iei dom(ρ) = {a ∈ A : ∃b ∈ B ıncıt (a, b) ∈ R}.

Codomeniul relat, iei codom(ρ) = {b ∈ B : ∃a ∈ A ıncıt (a, b) ∈ R}.

Imaginea directa a mult, imii X ⊆ A prin relat, ia ρ esteρ(X) = {b ∈ B : ∃a ∈ X , aρb}.

Imaginea inversa a mult, imii Y ⊆ B prin relat, ia ρ esteρ−1(Y ) = {a ∈ A : ∃b ∈ Y , aρb}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 10 / 28

Page 28: Structuri discrete - Curs3: Relații

Imaginea directa; Imaginea inversa

Domeniul relat, iei dom(ρ) = {a ∈ A : ∃b ∈ B ıncıt (a, b) ∈ R}.

Codomeniul relat, iei codom(ρ) = {b ∈ B : ∃a ∈ A ıncıt (a, b) ∈ R}.

Imaginea directa a mult, imii X ⊆ A prin relat, ia ρ esteρ(X) = {b ∈ B : ∃a ∈ X , aρb}.

Imaginea inversa a mult, imii Y ⊆ B prin relat, ia ρ esteρ−1(Y ) = {a ∈ A : ∃b ∈ Y , aρb}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 10 / 28

Page 29: Structuri discrete - Curs3: Relații

Imaginea directa; Imaginea inversa

Domeniul relat, iei dom(ρ) = {a ∈ A : ∃b ∈ B ıncıt (a, b) ∈ R}.

Codomeniul relat, iei codom(ρ) = {b ∈ B : ∃a ∈ A ıncıt (a, b) ∈ R}.

Imaginea directa a mult, imii X ⊆ A prin relat, ia ρ esteρ(X) = {b ∈ B : ∃a ∈ X , aρb}.

Imaginea inversa a mult, imii Y ⊆ B prin relat, ia ρ esteρ−1(Y ) = {a ∈ A : ∃b ∈ Y , aρb}

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 10 / 28

Page 30: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 31: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 32: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 33: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 34: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 35: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 36: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 37: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {a, b, c, d} s, i B = {1, 2, 3, 4}.

Fie R = {(a, 1), (a, 2), (b, 4)} s, i ρ = (A,B,R).

Atunci ρ({a}) = {1, 2};

ρ({a, b}) = {1, 2, 4};

ρ({c, d}) = ∅;

ρ−1({1}) = {a};

ρ−1({1, 4}) = {a, b};

ρ−1({3}) = ∅.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 11 / 28

Page 38: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {Student1,Student2,Student3,Student4} s, iB = {Curs1,Curs2, ...,Curs∞}.

Fie R = {(Student1,Curs2), (Student2,Curs2), (Student2,Curs4), (Student3,Curs1)} s, i ρ = (A,B,R).

Utilizat, i diagrame.

Atunci

ρ({Student1,Student2}) = {Curs2};

ρ({Student4}) = ∅;

ρ−1({Curs1,Curs2,Curs4}) = {Student1,Student2,Student3};

ρ−1({Curs3}) = ∅;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 12 / 28

Page 39: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {Student1,Student2,Student3,Student4} s, iB = {Curs1,Curs2, ...,Curs∞}.

Fie R = {(Student1,Curs2), (Student2,Curs2), (Student2,Curs4), (Student3,Curs1)} s, i ρ = (A,B,R).

Utilizat, i diagrame.

Atunci

ρ({Student1,Student2}) = {Curs2};

ρ({Student4}) = ∅;

ρ−1({Curs1,Curs2,Curs4}) = {Student1,Student2,Student3};

ρ−1({Curs3}) = ∅;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 12 / 28

Page 40: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {Student1,Student2,Student3,Student4} s, iB = {Curs1,Curs2, ...,Curs∞}.

Fie R = {(Student1,Curs2), (Student2,Curs2), (Student2,Curs4), (Student3,Curs1)} s, i ρ = (A,B,R).

Utilizat, i diagrame.

Atunci

ρ({Student1,Student2}) = {Curs2};

ρ({Student4}) = ∅;

ρ−1({Curs1,Curs2,Curs4}) = {Student1,Student2,Student3};

ρ−1({Curs3}) = ∅;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 12 / 28

Page 41: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {Student1,Student2,Student3,Student4} s, iB = {Curs1,Curs2, ...,Curs∞}.

Fie R = {(Student1,Curs2), (Student2,Curs2), (Student2,Curs4), (Student3,Curs1)} s, i ρ = (A,B,R).

Utilizat, i diagrame.

Atunci

ρ({Student1,Student2}) = {Curs2};

ρ({Student4}) = ∅;

ρ−1({Curs1,Curs2,Curs4}) = {Student1,Student2,Student3};

ρ−1({Curs3}) = ∅;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 12 / 28

Page 42: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {Student1,Student2,Student3,Student4} s, iB = {Curs1,Curs2, ...,Curs∞}.

Fie R = {(Student1,Curs2), (Student2,Curs2), (Student2,Curs4), (Student3,Curs1)} s, i ρ = (A,B,R).

Utilizat, i diagrame.

Atunci

ρ({Student1,Student2}) = {Curs2};

ρ({Student4}) = ∅;

ρ−1({Curs1,Curs2,Curs4}) = {Student1,Student2,Student3};

ρ−1({Curs3}) = ∅;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 12 / 28

Page 43: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {Student1,Student2,Student3,Student4} s, iB = {Curs1,Curs2, ...,Curs∞}.

Fie R = {(Student1,Curs2), (Student2,Curs2), (Student2,Curs4), (Student3,Curs1)} s, i ρ = (A,B,R).

Utilizat, i diagrame.

Atunci

ρ({Student1,Student2}) = {Curs2};

ρ({Student4}) = ∅;

ρ−1({Curs1,Curs2,Curs4}) = {Student1,Student2,Student3};

ρ−1({Curs3}) = ∅;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 12 / 28

Page 44: Structuri discrete - Curs3: Relații

Imaginea directa s, i inversa; Exemple

Fie A = {Student1,Student2,Student3,Student4} s, iB = {Curs1,Curs2, ...,Curs∞}.

Fie R = {(Student1,Curs2), (Student2,Curs2), (Student2,Curs4), (Student3,Curs1)} s, i ρ = (A,B,R).

Utilizat, i diagrame.

Atunci

ρ({Student1,Student2}) = {Curs2};

ρ({Student4}) = ∅;

ρ−1({Curs1,Curs2,Curs4}) = {Student1,Student2,Student3};

ρ−1({Curs3}) = ∅;

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 12 / 28

Page 45: Structuri discrete - Curs3: Relații

Relat, ii binare

Relat, ia ρ este surjectiva daca ρ(A) = B.

Relat, ia ρ este totala daca ρ−1(B) = A.

Relat, ia este injectiva daca pentru orice a ∈ A este cel mult un elementb ∈ B ıncıt (a, b) ∈ R.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 13 / 28

Page 46: Structuri discrete - Curs3: Relații

Relat, ii binare

Relat, ia ρ este surjectiva daca ρ(A) = B.

Relat, ia ρ este totala daca ρ−1(B) = A.

Relat, ia este injectiva daca pentru orice a ∈ A este cel mult un elementb ∈ B ıncıt (a, b) ∈ R.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 13 / 28

Page 47: Structuri discrete - Curs3: Relații

Relat, ii binare

Relat, ia ρ este surjectiva daca ρ(A) = B.

Relat, ia ρ este totala daca ρ−1(B) = A.

Relat, ia este injectiva daca pentru orice a ∈ A este cel mult un elementb ∈ B ıncıt (a, b) ∈ R.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 13 / 28

Page 48: Structuri discrete - Curs3: Relații

Relat, ii binare omogene

Fie o relat, ie binara omogena ρ = (A,A,R); ın acest caz putem folosiexpresiile:

“ρ relat, ie binara pe mult, imea A”

“A este ınzestrata cu o relat, ie binara“

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 14 / 28

Page 49: Structuri discrete - Curs3: Relații

Reprezentarea relat, iilor binare omogene; Matrice binare

Fie R = {(a, a), (a, b), (b, b), (c, b)} definita pe A = {a, b, c};

Matricea binara (imaginar pe rınduri s, i pe coloane scriet, i elementelemult, imii a)

Aρ =

1 1 00 1 00 1 0

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 15 / 28

Page 50: Structuri discrete - Curs3: Relații

Reprezentarea relat, iilor binare omogene; Matrice binare

Fie R = {(a, a), (a, b), (b, b), (c, b)} definita pe A = {a, b, c};

Graful orientat

a

b

c

d

bucle

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 16 / 28

Page 51: Structuri discrete - Curs3: Relații

Reprezentarea relat, iilor binare omogene; Matrice binare

Fie R = {(a, a), (a, b), (b, b), (c, b)} definita pe A = {a, b, c};

Graful orientat

a

b

c

d

bucle

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 16 / 28

Page 52: Structuri discrete - Curs3: Relații

Proprietat, i; Reflexivitate

Relat, ia ρ = (A,A,R) se numes, te reflexiva daca pentru orice a ∈ A avem(a, a) ∈ R (sau aρa).

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 17 / 28

Page 53: Structuri discrete - Curs3: Relații

Reflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”≤“.

1 1 1 10 1 1 10 0 1 10 0 0 1

Diagonala principala este 1.

0

1

2

3

Toate vırfurile au bucle.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 18 / 28

Page 54: Structuri discrete - Curs3: Relații

Reflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”≤“.

1 1 1 10 1 1 10 0 1 10 0 0 1

Diagonala principala este 1.

0

1

2

3

Toate vırfurile au bucle.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 18 / 28

Page 55: Structuri discrete - Curs3: Relații

Reflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”≤“.

1 1 1 10 1 1 10 0 1 10 0 0 1

Diagonala principala este 1.

0

1

2

3

Toate vırfurile au bucle.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 18 / 28

Page 56: Structuri discrete - Curs3: Relații

Reflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”≤“.

1 1 1 10 1 1 10 0 1 10 0 0 1

Diagonala principala este 1.

0

1

2

3

Toate vırfurile au bucle.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 18 / 28

Page 57: Structuri discrete - Curs3: Relații

Reflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”≤“.

1 1 1 10 1 1 10 0 1 10 0 0 1

Diagonala principala este 1.

0

1

2

3

Toate vırfurile au bucle.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 18 / 28

Page 58: Structuri discrete - Curs3: Relații

Proprietat, i; Antireflexivitate

Relat, ia ρ = (A,A,R) se numes, te antireflexiva daca pentru orice a ∈ Aavem (a, a) /∈ R.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 19 / 28

Page 59: Structuri discrete - Curs3: Relații

Antireflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”<“.

0 1 1 10 0 1 10 0 0 10 0 0 0

Diagonala principala este 0

0

1

2

3

Nu sınt bucle

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 20 / 28

Page 60: Structuri discrete - Curs3: Relații

Antireflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”<“.

0 1 1 10 0 1 10 0 0 10 0 0 0

Diagonala principala este 0

0

1

2

3

Nu sınt bucle

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 20 / 28

Page 61: Structuri discrete - Curs3: Relații

Antireflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”<“.

0 1 1 10 0 1 10 0 0 10 0 0 0

Diagonala principala este 0

0

1

2

3

Nu sınt bucle

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 20 / 28

Page 62: Structuri discrete - Curs3: Relații

Antireflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”<“.

0 1 1 10 0 1 10 0 0 10 0 0 0

Diagonala principala este 0

0

1

2

3

Nu sınt bucle

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 20 / 28

Page 63: Structuri discrete - Curs3: Relații

Antireflexivitate

Fie A = {0, 1, 2, 3} s, i ρ=”<“.

0 1 1 10 0 1 10 0 0 10 0 0 0

Diagonala principala este 0

0

1

2

3

Nu sınt bucle

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 20 / 28

Page 64: Structuri discrete - Curs3: Relații

Proprietat, i; Simetrie

Relat, ia ρ = (A,A,R) se numes, te simetrica daca pentru orice (a, b) ∈ Ravem (b, a) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (2, 3), (0, 2), (2, 0)}.

Construit, i matricea acestei relat, ii.

Construit, i matricea transpusa.

Matricea relat, iei este simetrica.

Construit, i graful orientat.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 21 / 28

Page 65: Structuri discrete - Curs3: Relații

Proprietat, i; Simetrie

Relat, ia ρ = (A,A,R) se numes, te simetrica daca pentru orice (a, b) ∈ Ravem (b, a) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (2, 3), (0, 2), (2, 0)}.

Construit, i matricea acestei relat, ii.

Construit, i matricea transpusa.

Matricea relat, iei este simetrica.

Construit, i graful orientat.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 21 / 28

Page 66: Structuri discrete - Curs3: Relații

Proprietat, i; Simetrie

Relat, ia ρ = (A,A,R) se numes, te simetrica daca pentru orice (a, b) ∈ Ravem (b, a) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (2, 3), (0, 2), (2, 0)}.

Construit, i matricea acestei relat, ii.

Construit, i matricea transpusa.

Matricea relat, iei este simetrica.

Construit, i graful orientat.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 21 / 28

Page 67: Structuri discrete - Curs3: Relații

Proprietat, i; Simetrie

Relat, ia ρ = (A,A,R) se numes, te simetrica daca pentru orice (a, b) ∈ Ravem (b, a) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (2, 3), (0, 2), (2, 0)}.

Construit, i matricea acestei relat, ii.

Construit, i matricea transpusa.

Matricea relat, iei este simetrica.

Construit, i graful orientat.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 21 / 28

Page 68: Structuri discrete - Curs3: Relații

Proprietat, i; Simetrie

Relat, ia ρ = (A,A,R) se numes, te simetrica daca pentru orice (a, b) ∈ Ravem (b, a) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (2, 3), (0, 2), (2, 0)}.

Construit, i matricea acestei relat, ii.

Construit, i matricea transpusa.

Matricea relat, iei este simetrica.

Construit, i graful orientat.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 21 / 28

Page 69: Structuri discrete - Curs3: Relații

Proprietat, i; Simetrie

Relat, ia ρ = (A,A,R) se numes, te simetrica daca pentru orice (a, b) ∈ Ravem (b, a) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (2, 3), (0, 2), (2, 0)}.

Construit, i matricea acestei relat, ii.

Construit, i matricea transpusa.

Matricea relat, iei este simetrica.

Construit, i graful orientat.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 21 / 28

Page 70: Structuri discrete - Curs3: Relații

Proprietat, i; Asimetrie

Relat, ia ρ = (A,A,R) se numes, te asimetrica daca pentru orice (a, b) ∈ Ravem (b, a) /∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (2, 3), (0, 2)}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 22 / 28

Page 71: Structuri discrete - Curs3: Relații

Proprietat, i; Asimetrie

Relat, ia ρ = (A,A,R) se numes, te asimetrica daca pentru orice (a, b) ∈ Ravem (b, a) /∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (2, 3), (0, 2)}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 22 / 28

Page 72: Structuri discrete - Curs3: Relații

Proprietat, i; Antisimetrie

Relat, ia ρ = (A,A,R) se numes, te antisimetrica daca pentru orice(a, b) ∈ R avem (b, a) /∈ R cu except, ia cazurilor cınd a = b.

Relat, ia antisimetrica este o relat, ie asimetrica cu cel put, in o pereche deformatul (a, a).

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (0, 2)}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 23 / 28

Page 73: Structuri discrete - Curs3: Relații

Proprietat, i; Antisimetrie

Relat, ia ρ = (A,A,R) se numes, te antisimetrica daca pentru orice(a, b) ∈ R avem (b, a) /∈ R cu except, ia cazurilor cınd a = b.

Relat, ia antisimetrica este o relat, ie asimetrica cu cel put, in o pereche deformatul (a, a).

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (0, 2)}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 23 / 28

Page 74: Structuri discrete - Curs3: Relații

Proprietat, i; Antisimetrie

Relat, ia ρ = (A,A,R) se numes, te antisimetrica daca pentru orice(a, b) ∈ R avem (b, a) /∈ R cu except, ia cazurilor cınd a = b.

Relat, ia antisimetrica este o relat, ie asimetrica cu cel put, in o pereche deformatul (a, a).

De exemplu, A = {0, 1, 2, 3} s, i R = {(3, 2), (1, 1), (0, 2)}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 23 / 28

Page 75: Structuri discrete - Curs3: Relații

Proprietat, i; Tranzitivitate

Relat, ia ρ = (A,A,R) se numes, te tranzitiva daca pentru orice(a, b), (b, c) ∈ R avem (a, c) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(2, 1), (3, 2), (3, 1)}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 24 / 28

Page 76: Structuri discrete - Curs3: Relații

Proprietat, i; Tranzitivitate

Relat, ia ρ = (A,A,R) se numes, te tranzitiva daca pentru orice(a, b), (b, c) ∈ R avem (a, c) ∈ R.

De exemplu, A = {0, 1, 2, 3} s, i R = {(2, 1), (3, 2), (3, 1)}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 24 / 28

Page 77: Structuri discrete - Curs3: Relații

Operat, ii; Reuniunea

Fie relat, iile ρ1 = (A,A,R) s, i ρ2 = (A,A,R2) atunci

ρ1 ∪ ρ2 = {(a, b) ∈ A2 : (a, b) ∈ R1 sau (a, b) ∈ R2}.

Aρ1 ⊕Aρ2 : aij OR bij

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 25 / 28

Page 78: Structuri discrete - Curs3: Relații

Operat, ii; Reuniunea

Fie relat, iile ρ1 = (A,A,R) s, i ρ2 = (A,A,R2) atunci

ρ1 ∪ ρ2 = {(a, b) ∈ A2 : (a, b) ∈ R1 sau (a, b) ∈ R2}.

Aρ1 ⊕Aρ2 : aij OR bij

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 25 / 28

Page 79: Structuri discrete - Curs3: Relații

Operat, ii; Intersect, ia

Fie relat, iile ρ1 = (A,A,R) s, i ρ2 = (A,A,R2) atunci

ρ1 ∩ ρ2 = {(a, b) ∈ A2 : (a, b) ∈ R1 s, i (a, b) ∈ R2}.

Aρ1 �Aρ2 : aij AND bij

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 26 / 28

Page 80: Structuri discrete - Curs3: Relații

Operat, ii; Intersect, ia

Fie relat, iile ρ1 = (A,A,R) s, i ρ2 = (A,A,R2) atunci

ρ1 ∩ ρ2 = {(a, b) ∈ A2 : (a, b) ∈ R1 s, i (a, b) ∈ R2}.

Aρ1 �Aρ2 : aij AND bij

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 26 / 28

Page 81: Structuri discrete - Curs3: Relații

Operat, ii; Compunerea

Fie relat, iile ρ1 = (A,A,R) s, i ρ2 = (A,A,R2) atunci

ρ1 ◦ ρ2 = {(a, b) ∈ A2 : (a, c) ∈ R1 s, i (c, b) ∈ R2}.

Aρ1Aρ2

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 27 / 28

Page 82: Structuri discrete - Curs3: Relații

Operat, ii; Compunerea

Fie relat, iile ρ1 = (A,A,R) s, i ρ2 = (A,A,R2) atunci

ρ1 ◦ ρ2 = {(a, b) ∈ A2 : (a, c) ∈ R1 s, i (c, b) ∈ R2}.

Aρ1Aρ2

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 27 / 28

Page 83: Structuri discrete - Curs3: Relații

Operat, ii; Inversarea

Fie relat, i ρ = (A,A,R) atunci

ρ−1 = {(a, b) ∈ A2 : (b, a) ∈ R}.

R. Dumbraveanu (USARB) Curs 3: Relat,ii; Proprietat,i; Operat,ii 2013 28 / 28