Che materia stai cercando?

Algebra e geometria - relazioni e classi di equivalenza

Appunti di Algebra e geometria per l’esame della professoressa Gerla. Gli argomenti trattati sono i seguenti: relazioni e classi di equivalenza, relazione binaria su A che si chiama relazione d'equivalenza, se è riflessiva, simmetrica e transitiva, classe di equivalenza.

Esame di Algebra e Geometria docente Prof. B. Gerla

Anteprima

ESTRATTO DOCUMENTO

Bi⊆ A

Bi≠∅

Bi∩Bj B1∩B3=∅ B2∩ B3=∅

≠∅ B1∪B2∪B3={a,b,c,d}=A

U Bi = A Es.

a b {a,b}∩{c,d}=∅ {a,b}∪{c,d}=A

F1 = {{a,b}, {c,d}}

C d F2 = {{a,b},{b,c},{d}} non è una partizione

{a,b}∩{b,c}={b}≠∅

F3 = {{a,b}, {c}} non è una partizione {a,b}∪{c}≠ A

Def. Se R è una relazione d'equivalenza su A

insieme QUOZIENTE x }

A/R = { [x]r | è l'insieme delle classi d'equivalenza di elementi di A

∈A

Proprietà A/R è una partizione di A

Es. A= {a,b,c,d}

R1 = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,a)} R è una relazione d'equivalenza

[a]r = {a,b} [b]r = {b,a] [c]r = {c} [d]r = {d} (Classi di equivalenza)

x }={[a]r, [b]r, [c]r, [d]r} = { {a,b}, {c}, {d} }

A/R = {[x]r | ∈A

A/R è una partizione di A

Es.

A = persone in questa aula

R = {(x,y) | x e y stesso colore degli occhi} Relazioni d'equivalenza

[x]r = { y tali che x e y hanno lo stesso colore degli occhi }

A/R = {{occhi marroni},{occhi verdi}, {occhi azzurri}}

A/R è una partizione di A

Es.

x R1 y se x e y avranno lo stesso voto a questo esame

[x]r = {y ha lo stesso voto di x}

A/R = {{studenti con 18}, {studenti 19} ….. {30}, {30 e lode}}

n∈ℕ}

Es. R1 = {(n,n) | [n]r = {n}

n∈ℕ}={{n} | n∈ℕ}

/ R1 = {[n]r1 | è una partizione di

ℕ ℕ

in ogni blocco c'è solo un elemento

Es. A= persone in questa aula

R = {(x,y) | x e y sono fidanzati} R⊆ A x A)

R relazioni d'equivalenza su A (

A| xRy }

[x]r = { y classe d'equivalenza di x

∈ x }

A/R = {[x]r | insieme quoziente è una partizione di A

∈A

P insieme delle parole di 4 lettere scelte tra a,b,c

bacc aaba abbc cabb

R⊆ P x P u R v se e solo se u e v hanno lo stesso numero di lettere a

R = { (u,v) | u e v hanno lo stesso numero di a }

aaba R acaa #(a,u)

abca !R aaca

#(a,u) = # (a,v) //il cancelletto serve per abbreviare, gli elementi hanno lo stesso numero di a

u∈ P

R è riflessiva #(a,u) = #(a,u)

∀ u , v P

R è simmetrica #(a,u) = #(a,v) allora #(a,v) = #(a,u)

∀ ∈

u , v , w∈P

R è transitiva se #(a,u) = #(a,v) e #(a,v) = #(a,w) allora #(a,u) = #(a,w)

[abbc]r = { abbc, abbb, babc, accc, cacb, bbac, …. } tutte le parole con una lettera a (insieme di

equivalenza, insieme delle classi di equivalenza)

[aabc]r = { parole con 2 lettere a } = {aabc, baac, caab, caba, … }

[aaab]r = { parole con 3 lettere a }

Quanti elementi ha P/R ?

[aaaa]r = {aaaa} |P/R| = 5

[bcbc]r ci sono 5 classi d'equivalenza diverse tra loro

Es. ℕ

R = {(x,y) | x+y } 2 R 4 1 R 5 2 !R 5

∈2ℕ

R relazione d'equivalenza 2ℕ 2x

riflessiva x R x x+x VERO

∈ ∈2 ℕ

• 2ℕ => y x∈2 => y R x

simmetrica x R y allora x + y VERO

∈ + ℕ

• 2ℕ e y z 2

transitiva x+y ∈ + ∈ ℕ

2R4 4R6 => 2R6

1R5 5R3 => 1R3

2

Nota che se x+y allora o x e y sono pari

∈ ℕ oppure x e y sono dispari

Se x R y e y R z allora o x,y,z sono pari oppure x,y,z sono dispari

=> x R z. Quindi R è una relazione d'equivalenza

[1]r = {1,3,5,7,9,....} = 2 + 1 (insieme dei numeri dispari)

[2]r = {0,2,4,6,8,...} = 2 numeri pari

[5]r = [1]r = [3]r = …

[4]r = [2]r = …

N/R = {[1]r, [2]r}

è una partizione di ℕ

{2 +1, 2 }

ℕ ℕ , {a}, {b}, {c}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}

Es. A = {a,b,c} P(A) = { ∅

R su P(A) R = { (x,y) | |x| = |y| } è una relazione d'equivalenza

r=∅ [{a}] ={a},{b},{c}} [{a,b}] = {{a,b},{b,c},{a,c}}

[∅]

[{a,b,c}] = {{a,b,c}} P(A)/R = {[ ],[{a}],[{(a,b)}], [{a,b,c}]}

è una partizione di P(A)

Es. A = {a,b,c,d}

F = {{a,b},{c},{d}} è una partizione di A


PAGINE

7

PESO

111.83 KB

AUTORE

koganzjo

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
A.A.: 2014-2015

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher koganzjo di informazioni apprese con la frequenza delle lezioni di Algebra e Geometria e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Insubria Como Varese - Uninsubria o del prof Gerla Brunella.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Algebra e geometria

Algebra e Geometria - Appunti
Appunto
Algebra e geometria - algoritmi sui numeri interi
Appunto
Algebra e geometria - anelli e matrici
Appunto
Algebra e geometria - applicazioni lineari
Appunto