Appunti di Metodi matematici per l'informatica

T

= M

M −1 R

R

Possiamo inoltre facilmente dedurre che

⇐⇒

R simmetrica M = M

−1 R

R

0.4.3 Composizione di relazioni

⊆ · ⊆ · ◦ ⇐⇒ ∃ ∧ ∃

R A B, S B C =⇒ R S = (a, c) (a, b) (b, c)

◦

Nei casi di R R parliamo di iterazione

Composizione di relazioni come prodotto fra matrici

·

M = M M

R,S R S

Dove si usano la somma ed il prodotto booleano

Associatività ◦ ◦ ◦ ◦

R (S D) = (R S) D

In quanto la moltiplicazione fra matrici è associativa, possiamo dedurre che lo

è anche la composizione di relazioni in quanto operazioni equivalenti

Commutatività ◦ ◦ ̸ ◦ ◦

R S D = R D S

Come prima, possiamo dedurlo dal fatto che il prodotto fra matrici non è com-

mutativo

0.4.4 Relazioni transitive

⊆ · ⇐⇒

R A A transitiva

∈ ∧

(∀a, b, c A, aRb bRc =⇒ aRc)

15

Chiusura transitiva T

E’ detta chiusura transitiva di R la più piccola relazione transitiva R

tale che: T T T

⊆ ∧ ∧ ⊆ ⊆

R R R transitiva R S, S transitiva =⇒ R S

Cammino ⊆ · ∃x

R A A, , x , ... t.c. aRx Rx R...Rb

0 1 0 1

⇐⇒ ∃ → ≥

cammino a b di lunghezza l 1

0.4.5 Relazione di equivalenza

ˆ ∀a ∈ ∃aRa

Riflessiva: A

ˆ ∀a, ∈

Simmetrica: b A, aRb =⇒ bRa

ˆ ∀a, ∈ ∧

Transitiva: b, c A, aRb bRc =⇒ aRc

Classi di equivalenza

∈

Preso a A, possiamo definire l’insieme

{b ∈ |

[a] = A aRb}

R

. Questo insieme è detto classe di equivalenza Possiamo inoltre dire che:

ˆ ∀a ∈ ̸ ∅

per la riflessività, A [a] =

R

ˆ ∀a, ∈ ∩ ∅ ∨

per la simmetria e la transitività, b A [a] [b] = [a] = [b]

R R R R

Partizioni {C | ∈

Una partizione di un insieme A è la famiglia i I} tali che

i

ˆ ⊆

C A

i

ˆ ̸ ∅

C =

i

ˆ ∀a ∈ ∈ ∈

A∃i I t.c. a C i

ˆ ∀i, ∈ ̸ ∩ ∅

j I, i = j =⇒ C C =

i j

ˆ S C = A

i

i∈I

Possiamo quindi dire che

{C | ∈ ⇐⇒ ∃i ∈ ∈

i I} partizione A, R (A) , (aRb I t.c. a, b C ) =⇒ R (A) relazione di equivalenza

i i

16

0.4.6 Relazioni d’ordine ≤

Relazione binaria che gode di alcune proprietà della relazione (N)

Relazione d’ordine totale

ˆ ∀a ∈ ∃aRa

Riflessiva: A

ˆ ∀a, ∈ ∧

Anti-simmetrica: b A, aRb bRa =⇒ a = b

ˆ ∀a, ∈ ∧

Transitiva: b, c A, aRb bRc =⇒ aRc

ˆ ∀a, ∈ ≤ ∨ ≤

Totale: b A, a b b a. Se questa proprietà non sussiste si parla

di ordine parziale

∅ e una qualunque R (∅) sono relazioni d’ordine.

Cicli ∀R (A) ordine =⇒ lunghezza massimo ciclo = 1

Dimostrazione

Ipotizziamo per assurdo che esista un ciclo di lunghezza > 1, ovvero tale che

∀i, ̸ ̸

a Ra R...Ra , t.c. j i = j =⇒ a = a

1 2 1 i j ∀i ̸

Per transitività ripetuta abbiamo che a Ra , ma anche che a Ra , = 1.

1 i i 1

Per antisimmetria ciò implica che a = a , ovvero che tutti gli elementi del ciclo

i 1

sono lo stesso elemento. Ne consegue che il ciclo si può ridurre a a Ra , di

1 1

lunghezza 1.

Minimo e massimo di un ordine

∈ ∀b ∈

a A t.c. A∃aRb/bRa =⇒ a è minimo/massimo di R (A)

Non è garantita l’esistenza di questi elementi.

Minimali e massimale di un ordine

∈ ∀b ∈ ̸

E’ detto minimale a R (A) t.c. A, b = a, ∄bRa.

∈ ∀b ∈ ̸

Analogamente, è detto massimale a R (A) t.c. A, b = a, ∄aRb

∀R ∃a ∈ ∧ ∃b ∈

Inoltre, (A) , A finito A minimale A massimale

Dimostrazione

Prendiamo il percorso P più lungo a Ra R...Ra , dove a minimale.

1 2 n 1

∃a ∈ ∈

Se A, a / P , non può valere aRa , in quanto esisterebbe il percorso

1

aRa Ra R...Ra , di lunghezza maggiore di P , impossibile per ipotesi.

1 2 n

∃a ∈ ∈

Se invece A, a P ne consegue che esiste un ciclo in P , impossibile in

quanto siamo in un ordine parziale.

Ne segue che a è il minimale di R (A)

1 17

Immersioni tra ordini

Tutti gli ordini sono inclusioni insiemistiche, ovvero:

∗ ∗

≤ ≤

(X) ordine parziale , (X ) ordine parziale

∗ ∗

∃f → ≤ ⇐⇒ ≤

=⇒ : X X iniettiva t.c. (x y f (x) f (y))

Immersione nell’insieme potenza

∃ ≤ ∃ ⊆

(X) =⇒ immersione (P (X))

Dimostrazione

Definiamo → P {z ∈ | ≤

f : X (X) , f (x) = X z x}

Verifichiamo l’iniettività per assurdo:

∀x, ∈ ̸ ≤ ≤

y X, y = x, f (x) = f (y) , x x, y y

∈ ∧ ∈ ∈ ∧ ∈

=⇒ x f (x) y f (y) =⇒ x f (y) y f (x)

≤ ∧ ≤

=⇒ x y y x =⇒ y = x per anti-simmetria

=⇒ contraddizione

≤ ⊆

Verifichiamo che x y =⇒ f (x) f (y): ⊆

x = y =⇒ f (x) = f (y) =⇒ f (x) f (y)

∈ ∈

x < y =⇒ x f (y) , y / f (x)

∀z ∈ ≤ ∈

Inoltre, per transitività f (x) , z x < y =⇒ z < y =⇒ z f (y)

∀z ∈ ∈ ∧ ∈ ∧ ∈

=⇒ f (x) , z f (y) x f (y) y / f (x)

⊂

=⇒ f (x) f (y)

Verifichiamo anche l’implicazione opposta:

∈ ⊆ ∈ ≤

x f (x) , f (x) f (y) =⇒ x f (y) =⇒ x y

Estensioni totali di ordini parziali

{a },

A = , ..., a R (A) ordine parziale =⇒

1 n

∗ ∗

∃R ⊆

(A) ordine totale t.c. R R

⇓

∀a, ∈

b A, R (A) ordine parziale, ∄aRb

′ ′

∃R ⊇ ∃aR

=⇒ (A) R t.c. b

18

Dimostrazione per casi

∈ × {x ∈ | ≤ {y ∈ | ≥

(a, b) A A, X = A xRa}(x a), Y = A bRx}(x b)

′ ∪ ×

R = R (X Y )

∈ ∧ ∩ ∅

=⇒ X t.c. xRa bRx =⇒ X Y =

∄aRb ∄x ′

R riflessiva =⇒ R riflessiva

Dimostriamo l’antisimmetria: ′ ′

∀x ∈ ∈ ∃xR ∧ ∃yR

Ipotizziamo X, y Y y x

∨ ∈ × ∧ ∨ ∈ ×

=⇒ (xRy (x, y) X Y ) (yRx (y, x) X Y )

Ne consegue per casi:

∈ ∩

(x, y) , (y, x) =⇒ x X Y =⇒ impossibile

∈ ∈ ∩

(x, y) , yRx =⇒ xRa =⇒ yRa =⇒ y X =⇒ y X Y =⇒ impossibile

∈ ∈ ∩

xRy, (y, x) =⇒ bRx =⇒ bRy =⇒ y Y =⇒ y X Y =⇒ impossibile

xRy, yRx =⇒ y = x per antisimmetria

Dimostriamo la transitività: ′ ′

∀x, ∈ ∃xR ∧ ∃yR

Ipotizziamo y, z X, y z

∨ ∈ × ∧ ∨ ∈ ×

=⇒ (xRy (x, y) X Y ) (yRz (y, z) X Y )

Ne consegue per casi:

∈ ∧ ∈ ∈ ∩ ⇐⇒

(x, y) , (y, z) =⇒ y X y Y =⇒ y X Y impossibile ′

∈ ∈ ∈ ×

(x, y) , yRz =⇒ y Y =⇒ bRy =⇒ bRz =⇒ z Y =⇒ (x, z) X Y =⇒ xR z ′

∈ ∃yRa ∈ ∈ ×

xRy, (y, z) =⇒ y X =⇒ =⇒ xRa =⇒ x X =⇒ (x, z) X Y =⇒ xR z

′

xRy, yRz =⇒ xRz =⇒ xR z

Dimostrazione per induzione

Consideriamo il problema nel caso A = a. Banale il fatto che R parziale sia

anche totale. ∃a, ∈

Consideriamo ora un generico caso A = a , ..., a , dove abbiamo che b A

1 n

∧

t.c. ∄aRb ∄bRa.

∃a ∈

Sappiamo che A minimale di R, ed escludiamolo da A. Nell’insieme

R (A\{a}) abbiamo due casi:

ˆ R (A\{a}) totale: basta definire un nuovo ordine

∪ {aRx ∀x ∈

R = R (A\{a}) R (A\{a})}

T

ˆ R (A\{a}) parziale: ripetiamo lo stesso procedimento definito sopra finchè

})

non trovaimo un R (A\{a , ..., a totale.

i i

1 n

Sappiamo che suddetto caso esiste in quanto al limite si arriva a un caso

dove A = a che sappiamo essere totale. −

Di conseguenza, per un qualunque n sappiamo risolvere il caso n 1, ed avendo

−

risolto n 1 sappiamo risolvere n 19

Sottosuccessioni ∃S ⇐⇒ ∃j ∈ ∀j

A, [i, i + #S] t.c. S = A

A j−i j

Sottosuccessioni monotone ed ordini totali

∀n ≥ {a } ∃S {a }

1, A = , ..., a t.c. R (A) ordine totale =⇒ = , ..., a monotona

2

1 A i i+n+1

n +1

Dimostrazione

Ipotizziamo per assurdo che questa successione non esista.

2 {a }

Consideriamo f : 1, n + 1 [1, n] , f (x) = ℓ S = , ..., a monotona

max A i x

2

n +1 ∃{i }

= n resto 1 =⇒ < ... < i t.c. f (i ) = ... = f (i ) = l

Dato che 1 n+1 1 n+1

n

Consideriamo quindi gli elementi a , ..., a che sappiamo avere lo stesso ℓ .

i i max

1 n+1

Preso una qualunque coppia adiacente a , a , abbiamo due casi:

i i

k k+1

ˆ {S }

a < a =⇒ S = < a =⇒ k < (k + 1) =⇒ impossibile

i i A A i

ai ai

k k+1 k+1

k k

ˆ a > a

i i

k k+1

Ne consegue che ∗ ∗

∀k ∈ ∃S {x }

[1, n + 1) =⇒ a > a =⇒ = > ... > x =⇒ #S = n+1 =⇒ contraddizione

i i i i

1 n+1

k k+1

Ergo l’ipotesi è falsa 20

0.5 Induzione

L’idea base del principio di induzione è dimostrare che

∀n ∈ ⊆

P (n) X N

E’ composta da due parti fondamentali:

ˆ ∃n ∈

Caso base: dimostrare che N t.c. P (n) Solitamente n = 0 o 1

0 0

ˆ ∀n ∈ ≥

Passo induttivo: dimostrare che N, n n , P (n) =⇒ P (n + 1).

0

L’ipotesi P (n) è detta ipotesi induttiva

0.5.1 Principio di Induzione: versione insiemistica

⊆

X N

∈

n X

0

∀n ∈ ≥ ∈ ∈

N, n n , n X =⇒ n + 1 X

0 − {0, − ⊂ − {0, −

=⇒ N ..., n 1} X =⇒ X = N ..., n 1}

0 0

0.5.2 Dimostrazione col Principio del Minimo Numero

Il principio del minimo numero ci dice che

∀X ⊆ ̸ ∅ ∃m ∈

N, X = =⇒ X

Prendiamo le condizioni della versione insiemistica, ed ipotizziamo per assurdo

che l’induzione insiemistica non sia valida, ovvero che

− {0, − − ̸ ∅

A = N ..., n 1} X, A =

0

∃m ∈ ∈

Per il principio del minimo numero A > n in quanto n X, ov