Matematica discreta - Relazioni

Ogni volta che si discute di set, la relazione tra gli elementi dei set è la cosa successiva che viene fuori. Relations può esistere tra oggetti dello stesso insieme o tra oggetti di due o più insiemi.

Definizione e proprietà

Una relazione binaria R dall'insieme x alla y (scritta come $ xRy $ o $ R (x, y) $) è un sottoinsieme del prodotto cartesiano $ x \ times y $. Se la coppia ordinata di G è invertita, cambia anche la relazione.

Generalmente una relazione n-ary R tra gli insiemi $ A_1, \ dots \ e \ A_n $ è un sottoinsieme del prodotto n-ary $ A_1 \ times \ dots \ times A_n $. La cardinalità minima di una relazione R è zero e in questo caso il massimo è $ n ^ 2 $.

Una relazione binaria R su un singolo insieme A è un sottoinsieme di $ A \ volte A $.

Per due insiemi distinti, A e B, aventi rispettivamente cardinalità m e n , la cardinalità massima di una relazione R da A a B è mn .

Dominio e intervallo

Se ci sono due insiemi A e B e la relazione R ha una coppia di ordini (x, y), allora -

  • Il domaindi R, Dom (R), è l'insieme $ \ lbrace x \: | \: (x, y) \ in R \: per \: alcuni \: y \: in \: B \ rbrace $

  • Il range di R, Ran (R), è l'insieme $ \ lbrace y \: | \: (x, y) \ in R \: per \: some \: x \: in \: A \ rbrace $

Esempi

Siano $ A = \ lbrace 1, 2, 9 \ rbrace $ e $ B = \ lbrace 1, 3, 7 \ rbrace $

  • Caso 1 - Se la relazione R è 'uguale a' allora $ R = \ lbrace (1, 1), (3, 3) \ rbrace $

    Dom (R) = $ \ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace $

  • Caso 2 - Se la relazione R è 'minore di' allora $ R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace $

    Dom (R) = $ \ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace $

  • Caso 3 - Se la relazione R è 'maggiore di' allora $ R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace $

    Dom (R) = $ \ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace $

Rappresentazione delle relazioni utilizzando il grafico

Una relazione può essere rappresentata utilizzando un grafico orientato.

Il numero di vertici nel grafo è uguale al numero di elementi nell'insieme da cui è stata definita la relazione. Per ogni coppia ordinata (x, y) nella relazione R, ci sarà un arco diretto dal vertice "x" al vertice "y". Se c'è una coppia ordinata (x, x), ci sarà un ciclo automatico sul vertice 'x'.

Supponiamo che ci sia una relazione $ R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace $ sul set $ S = \ lbrace 1, 2, 3 \ rbrace $, può essere rappresentato dal grafico seguente -

Tipi di relazioni

  • Il Empty Relation tra gli insiemi X e Y, o su E, c'è l'insieme vuoto $ \ emptyset $

  • Il Full Relation tra gli insiemi X e Y è l'insieme $ X \ volte Y $

  • Il Identity Relationsul set X è il set $ \ lbrace (x, x) | x \ in X \ rbraccia $

  • La relazione inversa R 'di una relazione R è definita come - $ R' = \ lbrace (b, a) | (a, b) \ in R \ rbrace $

    Example - Se $ R = \ lbrace (1, 2), (2, 3) \ rbrace $ allora $ R '$ sarà $ \ lbrace (2, 1), (3, 2) \ rbrace $

  • Viene chiamata una relazione R sull'insieme A. Reflexive se $ \ forall a \ in A $ è correlato a (aRa vale)

    Example - La relazione $ R = \ lbrace (a, a), (b, b) \ rbrace $ sull'insieme $ X = \ lbrace a, b \ rbrace $ è riflessiva.

  • Viene chiamata una relazione R sull'insieme A. Irreflexive se nessun $ a \ in A $ è correlato a (aRa non vale).

    Example - La relazione $ R = \ lbrace (a, b), (b, a) \ rbrace $ sull'insieme $ X = \ lbrace a, b \ rbrace $ non ha riflessi.

  • Viene chiamata una relazione R sull'insieme A. Symmetric se $ xRy $ implica $ yRx $, $ \ forall x \ in A $ e $ \ forall y \ in A $.

    Example - La relazione $ R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace $ sul set $ A = \ lbrace 1, 2, 3 \ rbrace $ è simmetrico.

  • Viene chiamata una relazione R sull'insieme A. Anti-Symmetric se $ xRy $ e $ yRx $ implica $ x = y \: \ forall x \ in A $ e $ \ forall y \ in A $.

    Example - La relazione $ R = \ lbrace (x, y) \ a N | \: x \ leq y \ rbrace $ è antisimmetrica poiché $ x \ leq y $ e $ y \ leq x $ implica $ x = y $ .

  • Viene chiamata una relazione R sull'insieme A. Transitive se $ xRy $ e $ yRz $ implica $ xRz, \ forall x, y, z \ in A $.

    Example - La relazione $ R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace $ sull'insieme $ A = \ lbrace 1, 2, 3 \ rbrace $ è transitiva.

  • Una relazione è un Equivalence Relation se è riflessivo, simmetrico e transitivo.

    Example - La relazione $ R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \ rbrace $ sull'insieme $ A = \ lbrace 1, 2, 3 \ rbrace $ è una relazione di equivalenza poiché è riflessiva, simmetrica e transitiva.