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

x

Def. Se R è una relazione d'equivalenza su A allora per ogni ∈A

y x R y }

[X]r = { è la CLASSE D'EQUIVALENZA di x

∈A|

NOTA [X]r A[X]r∈P A)

⊆ (

Es. A = {a,b,x} R = {(a,a),(b,b,),(c,c),(a,b),(b,a)}

R è relazione d'equivalenza (riflessiva, simmetrica e transitiva)

[A]r = {a,b} [B]r = {b,a} [C]r = {c}

Es. A = {a,b,c}

|P(A)| = 8 {a} R {b} {a,b} R {b,c}

x P(A)

R = {(X,Y) | |X| = |Y|} {a} !R {b,c} {b} !R {b,c}

⊆P(A) R è riflessiva x∈P A) |X|=|X|

∀ (

R è riflessiva x , y∈ P A) |X|=|Y| allora |Y|=|X|

∀ (

R è transitivo |X| = |Y| e |Y| = |Z| allora |X| = |Z|

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

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

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

∅ ∅

Def. Una partizione di un insieme A è una famiglia di Sottoinsiemi di A

i∈I Bi⊆ A

F = {Bi} Bi≠∅

Bi∩Bj ≠∅

Bi= A

∪i∈I

Bi è un blocco della partizione

blocchi disgiunti

– unione dei blocchi è A

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

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

B1 B2 B3

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 }


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