Relazioni ed applicazioni

Relazioni

A → B è falsa solamente se A vera e B falsa

Se fa freddo mi ammalo

Def

Il prodotto cartesiano degli insiemi A₁, ..., A_n

A₁ x ... x A_n = {(a₁, ..., a_n) : a₁∈A₁, a₂∈A₂, ..., a_n∈A_n}

Es: A = {1, 2, 3} B = {0, _, []} A x B = {(1, 0), (1, _), (2, 0), (2, [])}

Quindi (0, 1) ∉ A x B

Oss: La coppia ordinata (a, b) ∈ A, b∈B la definisco {a, {a, b}}

Def

Una relazione su A₁, ..., A_n è un sottoinsieme:

R ⊆ A₁ x ... x A_n

Si dice una relazione n-aria su A₁ ... A_n.

Casi che ci interessano:

• Relazione 1-aria : R ⊆ A₁

Es A₁ = ℤ

R = {x∈ℤ : x pari} ⊆ ℤ

• Relazioni binarie: R ⊆ A₁ x A₂

Es A₁ = {a, b, c, d} A₂ = {casa, moto, macchina, cell}

R = {(a, CA), (a, MO), (b, MO), (c, CA), (c, MA), (d, cell)} ⊆ A₁ x A₂

R = "la persona x∈A₁ possiede y∈A₂"

Oss: A volte scriviamo (a, CA) ∈ R come a R CA

1. R ⊆ S ⇔ R ⇔ S se ∀ (a, b) ∈ R ⇒ (a, b) ∈ S
2. R = S
3. R ⊆ S e S ⊆ R

Operazioni

1. Unione/Intersezione: R, S ⊆ A₁ x A₂ R∪S = { (a, b) : (a, b) ∈ R ∪ (a, b) ∈ S }
2. Prodotto di relazioni R ⊆ A₁ x A₂ S ⊆ A₂ x A₃ la relaz R・S ⊆ A₁ x A₃R・S = { (a, c) ∈ A₁ x A₃ : ∃ b ∈ A₂ t.c. (a, b) ∈ R e (b, c) ∈ S }

Metodo di rappresentazione

R ⊆ A₁ x A₂ dove A₁, A₂ sono finiti

• Elencano gl elem di R   R = { (a₁, b₂), (o₂, b₂),... }

Grato d'adicenza

Vertici sono A₁ ∪ A₂ e disegno una freccia

a∈A₁   b∈A₂ se (a, b)∈R

Es A₁ = { 1, 2, 3 }   A₂ = { b, c, d } R = { (1, b), (1, d), (3, d) }

Grato d'adic. di R

M_R = ( ^bcd₁₂₃₃ ) | 1 0 1 || 0 0 1 |

Matrice di adiacenza

Numer gli elementi   A_n = { a₁,...,a_n }   A₂ = { b₁,...,b_m }

Allora   M_R ∈ M_nxm { 0, 1 }   Def (H_R)_ij = {1 se (a_i, b_j) ∈ R0 altrimenti}

Es A = { o₁, o₂, o₃ }   B = { x₁, x₂ }

R ha grafo

Allora M_R =

o₁ x₁ o₂ x₂ | 1 0 || 1 0 |

Metodi di rapp. e operazioni

R = o₁ x₁ ← o₂ x₂

T = o₁ x₂ o₃ x₂

Rut = o₁ x₁

PanTo = o₂ x₃

INSIEME: I_A ∈ R

3) SIMMETRIA: ∀ a, b ∈ A ((a,b) ∈ R ⇒ (b,a) ∈ R)

GRAFO:

MATIRICE: (M_R)_i.j = 1 ⇔ (M_R)_j.i = 1 ^T

LA MAT. È SIMMETRICA (M_R = M ^T _R)

INSIEMISTICO: R^-1 = R ⇔ R = R^-1)

ES/OSS: R = I_A È SIMMETRICA, R= ∅ È SIMMETRICA,

R^-1 R

NON È SIMM.

4) ANTISIMMETRICA

∀ a,b ∈ A ((a,b) ∈ R e (b,a) ∈ R ⇒ a = b)

GRAFO: "LE UNICHE DOPPIE FRECCE SONO I CAPPI"

ES

INSIEMISTICO: R ∩ R^-1 ⊆ I_A

R²

5) TRANSITIVITÀ:

GRAFO:

INSIEMISTICO: R² ⊆ R

DIM: R² ⊆ R ⇒ R TRANS: SIANO (a,b) ∈ R e (b,c) ∈ R

(a,c) ∈ R ∅

R TRANS:=> R² ⊆ R; (a,c)∈R² ⇒ ∃b∈A (a,b)∈R e (b,c)∈R

MA R E TRANS. x a,p , QUINDI (a,c) ∈ R

MATIRCE: CALCOLATE M_R² E VERIFICATE CHE SE (M²_R)_i.j ≠ 0 ⇒ (M ^R)_i.j ≠ 0

ES. ∅ È TRANS., I_A È TRANS., LA RELA. UNIVERS. A × A

Chius. Rifl. + Simm. + Trans.

Dovete sempre prima chiud. Simm e poi transitivare, altrimenti perdo la transitività!

Esempio

1. SImmetrica
2. Transitiva di H
3. Transitiva:

Relazioni d'equivalenza

• Rx A si dice d'equivalenza se é rifl. + simm + trans.

Oss: Dalla prec. prop. (nel punto 7) esiste sempre la chiusura d'equivalenza di una relazione R:

Esempio

Oss: la chiusura d'equivalenza è facilissima: basta completare aggiungendo tutte le frecce alle componenti connesse (clique)

Oss: se S T AKA d'equivalenza, allora S ∩ T sono d'equivalenza mentre in generale S ∪ T, S \ T non sono d'equivalenza.

Esempi

1. L'uguaglianza su A \ I_A = {(a, a): a∈A} è d'equivalenza
2. τ = {triangoli nel piano euclideo} S∈τ×τ t₁≅t₂ se t₁ e t₂ sono simili

4) Importante in Informatica Teoria.

Fissate un insieme Σ detto alfabeto, fissate su Σ un ordine totale ≤* es Σ = {a, b, c}   a ≤ b ≤ c   sa Σ⁺ l'insieme di stringhe/parole su Σ = {x₁... x_n : x_i ∈ Σ} es a, ab, abbc, abbca, ...Definiamo ≤^st su Σ⁺ w₁ ≤^st w₂ se |w₁| ≤ |w₂| e nel caso |w₁|=|w₂|w₁ ≤ w₂ secondo l'usuale ordine alfabetico. Per esempio:abc ≤ aobcabc < bca_{prima lettera diversa e b ≤ c}

(Σ⁺, ≤^st) si chiama shortlex - È un ordine totale.

La chiusura d'ordine ("la più piccola" relazione rifl+trans+antisimm che contiene una data relazione R) in generale non esiste, poichè R può non essere antisimmetrica.

Proposizione: R ⊆ A x A allora la chiusura d'ordine di R esiste se

1. R è antisimmetrica;
2. La chiusura R^Rtt rifl+trans. di R, questa è ancora antisimmetrica,

In questo caso ≤ = R^Rtt è la chiusura d'ordine di R.

1) Esempi R=

1 → 2 1 → 3 2 2 3 R^Rtt 3 3

Ώ  >?

La chiusura d'ordine di R non esiste, dato che con rel T &sub2; R non sarà mai antisimmetrica.

Α?   <1 2 3>

‹ 2 3  ●  2

R R R^tt Esempi?

ABb

Ϊ32

⌗

DIAGRAMMA DI HASSE DI UN POSET

Dato (A, ≤) poset, diciamo che b copre a se a ≤ b e non esiste alcun c ∈ A c ≠ a, b t.c. a ≤ c ≤ b. In questo caso a < b

I^o Probl. lo risolvo se f è iniettiva

f: A → B funzione

Prop: sono equivalenti

• ∀ a, b ∈ A f(a) = f(b) ⇒ a = b
• ∀ a, b ∈ A a ≠ b ⇒ f(a) ≠ f(b)
• ∀ b ∈ B |f^-1({b})| ≤ 1
• Se A, B sono finiti la matrice M_f ogni colonna ha al più un "1"
• f ha una inversa destra cioè ∃ una funzione d: B → A t.c. f ∙ d = I_A

Verficate f ∙ d = I_A

Esempio

f: IN → IN

f(x) = 2x ∀ x ∈ IN

• y ∈ f(A) "è pari"
• y ∉ f(A) "è dispari"

d(y) = { y/2, 1 }

Il II^o Probl. lo risolvo se f è suriettiva

Prop. sono equivalenti:

• ∀ b ∈ B ∃ a ∈ A f(a) = b;
• ∀ b ∈ B |f^-1({b})| ≥ 1;
• f(A) = B
• Se f: A → B con A e B finiti, la matr. d'adiac. M_f ha la proprietà che ogni colonna ha almeno un "1"
• f ha una inversa sinistra cioè ∃ s: B → A t.c. s ∙ f = I_B