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 A₂ ... x A_n = { (a₁, ..., a_n) : a_i ∈ A_i, i ∈ [1,n] }

Es A = {1, 1, 2} B = {2, 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_m è un sottoinsieme:

• R ⊆ A₁ x ... x A_m

R si dice una relazione n-aria su A₁, ... A_m.

Casi che ci interessano:

1. Relazione 1-aria: R ⊆ A₁

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

1. Relazioni binarie: R ⊆ A₁ x A₂

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

• R = {(a, casa), (a, moto), (b, moto), (c, casa), (c, macchina), (d, cell)}
• R = "La persona x ∈ A₁ possiede y ∈ A₂"

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

1. R, S ⊆ A x B
2. R ⊆ S se ∀ (a, b) ∈ R => (a, b) ∈ S
3. R = S
4. R ⊆ S e S ⊆ R

Relazioni

A ⇒ B è falsa solamente se A vera e B falsaSe fa freddo mi ammalo

Def

Il prodotto cartesiano degli insiemi A₁, ..., Aₙ,A₁ x A₂ x ... x Aₙ = { (a₁, ..., aₙ) : a₁ ∈ A₁, a₂ ∈ A₂, ..., aₙ ∈ Aₙ }

Es A={1, 2} 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ₙ è un sottoinsieme:R ⊆ A₁ x ... x Aₙ

R si dice una relazione n-aria su A₁, ..., Aₙ.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₁ ⊆ A x B 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 rela R · S ≤ A₁ x A₃

   R · S = {(a, c) ∈ A₁ x A₃ : ∃ b ∈ A₂ t.c. (a, b) ∈ R e (b, c) ∈ S}

METODI DI RAPPRESENTAZIONE

R ≤ A₁ x A₂ DOVE A₁, A₂ SONO FINITI

1. ELENCANDO GLI ELEM. DI R

   R = {(a₁, b₁), (a₂, b₂), ....}

2. GRAFO D'ADIACENZA:

   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₁)}

   GRAFO D'AD. DI R

   • 1 → b₁
   • c₂ → 2
   • d₃ → 3

   =M_R = (1 0 1) (0 0 0) (1 0 1)

3. MATRICE D'ADIACENZA

   NUMERO GLI ELEMENTI A_n = {o₁, ..., o_n}

   A₂ = {b₁, ..., b_m}

   ALLORA M_R ∈ M_{n x m} ({0, 1}) DEF

   (M_R)_ij = {1 se (a_i, b_j) ∈ R 0 altrimenti}

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

   R HA GRAFO o₁ → x₁ o₂ → x₁ o₃ → x₂