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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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