Formulario Matematica discreta

F

FUNZION DEF.

I Siano A e B due insiemi: una funzione da A in B è una RELAZIONE (vedi

relazione) f: AB con la seguente proprietà: ogni elemento del dominio

(A) ha un’immagine in B e questa è UNICA

L’immagine di a∈A si indica con f(a)

Una funzione si dice INIETTIVA se elementi distinti del dominio hanno

immagini distinte

Una funzione si dice SURIETTIVA se ogni elemento del codominio è

immagine di qualcosa

Una funzione si dice BIETTIVA se è sia iniettiva che suriettiva

COMPOSIZIONE DI FUNZIONI

Siano g: xy e f:yz due funzioni la loro composizione è f ◦ g: xz |

(f◦g)(x) = f(g(x))

Esempio: f(x)= x^2 g(x)=2x+1

- f◦g=f(g(x))=f(2x+1)=(2x+1)^2

- g◦f=g(f(x))=g(x^2)=2x^2+1

Una funzione è invertibile se è biettiva

G

GRUPPI Un’operazione binaria su un insieme S è una funzione *: SxS -> S.

Questa funzione manda la coppia (a,b) in un elemento di S che

indicheremo con a*b e chiameremo prodotto di a per b. Un insieme

S è dotato di un’operazione * chiamata Magma o Gruppoide e si

indica con (S,*)

Le proprietà di un magma sono:

- Associativa e Commutativa

- Elemento neutro: a * e = a. Esiste un solo elemento neutro

- Inverso: a * b = e

Associati El. Inverso Commutat

(G,*) va neutro iva

(Z,+) SI SI (0) SI SI

(è

l’opposto)

(Z,-) NO NO NO NO

(Z, SI SI (1) NO SI

⋅ )

(Q ,

/{0} SI SI (1) SI SI

⋅ )

(Q ,

>0 NO NO NO NO

÷)

(P , SI SI ( NO SI

(s)

Monoidi ∪ ∅ )

)

(P , (S)

SI SI NO SI

(s)

∩ )

(Z , 0

SI SI SI

SI ( (è

n

+) l’opposto)

)

(Z , 1

SI NO SI

SI (

n

⋅ ) )

(S ,◦) SI SI (id) SI NO

n

Gruppi Un Monoide è un insieme M dotato di un’operazione associativa * e di

un elemento neutro e. Si dice abeliano se è anche commutativo.

Sono monoidi commutativi (Z,+) , (Z,⋅) , (Q/{0},⋅) , (P(s),∪) , (P(s),∩) ,

(Zn,+) e (Zn, ⋅).

Mentre (Sn,◦) è un monoide non abeliano.

Sottoinsiemi -1 0

Passaggio in notazione additiva: ⋅ + ; e 0 ; a -a ; a =e

   

chiusi a n

0 =0 ; a n⋅a



Consideriamo (M * , e ) e (M * , e ): il loro prodotto cartesiano

1, 1 1 2, 2 2

M xM diventa un monoide con operazione (a ,a )*(b ,b ) := (a * b ,

1 2 1 2 1 2 1 1 1

a * b ). L’elemento neutro è la coppia (e ,e ) e il monoide ottenuto si

2 2 2 1 2

chiama PRODOTTO DIRETTO DI MONOIDI

Un gruppo è un particolare monoide (G,*,e) con la proprietà che ogni

elemento di G ha un inverso. Esempio: (Z,+) , (Q,+) , (R,+) ,(Q/

{0},⋅) , (Zn,+) sono gruppi abeliani, mentre (Sn,◦) è un gruppo non

Sottogruppi abeliano.

In un gruppo vale la legge di cancellazione a sinistra e in modo

analogo a destra.

Es: g*a = g*b a=b ; a*g=b*g a=b

 

Un sottoinsieme chiuso S’ di un magma (S,*) è un sottoinsieme di S

' ' ' ' '

tale che .

∀ ∈ ∈

∗y

x , y S , x S '

Es: verificare se l’insieme S’= {id,(123),(132)} è sottoinsieme chiuso

di (S , ◦)

3

◦ id (12 (13 Tutti gli elementi ottenuti sono in S’

3) 2) quindi S’ è sottoinsieme chiuso di (S ,

3

id id (12 (13 ◦)

3) 2)

(12 (12 (13 id

3) 3) 2)

(13 (13 id (12

2) 2) 3)

Un sottogruppo di un gruppo (G,*,e) è un sottoinsieme H di G tale

che:

- H è sottoinsieme chiuso di (G,*)

∈

- e H

∈

-1

- x H

Sottogruppi Consideriamo un monoide (M,*,e), possiamo definire l’insieme degli

di (Z,+) ∈ ∃b ∈

x

elementi invertibili di M: M := {a M | M, a*b = e = b*a}

Consideriamo un sottoinsieme H di un gruppo (G,*,e) allora:

∅ ∀ ∈ + -1

H è sottogruppo di (G,*,e) H e

≠ x . y H , x y



∈ H σ τ σ a

Es: consideriamo =(154) e =(23) in S . Definiamo H:={

5

∈

τ b

⋅ | a,b Z }

Omomorfism Dimostrare che H è sottogruppo di S

i 5: ∈

Definiamo l’insieme degli interi multipli di n: nZ:={na | a n }

Dimostrare che nZ è sottogruppo di Z:

∈

1) n = n⋅1 nZ nZ ≠∅



∈

2) Prendo x,y nZ -> esistono s,t appartenenti a Z tali che

x=ns e y=nt

Isomorfismi ∈

x-y = ns – nt = n(s-t) nZ. Allora nZ è sottogruppo di Z



Immagine e ∃ ∈

Se H è sottogruppo di (Z,+) allora n N tale che H=nZ

controimma

gine Consideriamo due gruppi (G ,* ,e ) e (G * ,e ). Un omomorfismo da

1 1 1 2, 2 2 ∋

G in G è una funzione f:G ->G tale che per ogni a,b G

1 2 1 2 1,

f(a* b)=f(a)* f(b)

1 2

Iniezione e Esempi:

suriezione -f:GG; f(g)=e: f(a*b)=e; f(a)*f(b)= e*e=e -> f(a*b)=f(a)*f(b)

n n

-f:GG; f(g)=g : f(a*b)=(a*b) =a*b*…*a*b=a*a*…*b*b:

n n

f(a*b)=(a*…*a)*(b*…*b)=a *b =f(a)*f(b)

z a+b a b

-f:ZG; f(z)=g : f(a+b)=g =g *g =f(a)*f(b)

Gruppi ciclici TEOREMA: Se f: (G ,* ,e )(G ,* ,e ) è omomorfismo, allora:

1 1 1 2 2 2

- manda l’elemento neutro nell’elemento neutro, cioè: f(e ) =

1

e 2

- manda l’inverso nell’inverso, cioè

-1 1-1

f(g ) = f(g )

1

Esercizio: verficare se f:ZZ, f(z)=2z+3 è omomorfismo:

Ordine o

periodo di Se fosse om. f(0)=0. Poiché f(0)=2⋅0+3 è diverso da 0, f non è

un elemento omomorfismo

Esercizio: verificare se f:RR, f( r) =|r| è omomorfismo:

f(0)=|0|=0 quindi ok

Teorema Se fosse om. f(-r)=-f(r). Poichè f(-r)=|-r|=r e -f( r)= -|r| allora f non è

cinese del omomorfismo

resto OSSERVAZIONE: se f: G è omomorfismo allora Im(f) è

G

1 2

sottogruppo di G 2

Un isomorfismo f:G è un omomorfismo biettivo

G

1 2

Considero una funzione f:AB e i sottoinsiemi A’ incluso in A e B’

incluso in B

Omomorfism L’immagine di A’ tramite f è f(A’):={f(a’)| a’ in A’}, cioè l’insieme

i e gruppi delle immagini degli elementi di A’. Quando A’=A si indica con Im(f)

ciclici = f(A) = {f(a) | a in A}

controimmagine -1

La di B’ tramite f è f (B’):={a in A | f(a) in B’}, cioè

l’insieme delle controimmagini degli elementi di B’.

f: G è SURIETTIVA se e solo se Im(f)=G

G

1 2 2

f: G è INIETTIVA se e solo se Ker(f)=e

G

1 2 1

∈

-1

Il nucleo Kernel è Ker(f) = f ({e }) = {g G | f(g )=e }

2 1 1 1 2 n

Tra gli esempi di omomorfismi abbiamo visto f:ZG, f(n)=g .

∈ ∈

n

Im(f)={f(n) | n Z} = {g | n Z } è l’insieme delle potenze di

g in G. Questo particolare sottogruppo è detto “sottogruppo di G

generato da g” ∃ ∋G

g

G è un gruppo ciclico se ha un elemento particolare cioè se

tale che <g> = G

Se un gruppo non è abeliano allora non può essere ciclico

n

Se il gruppo è in notazione additiva sostituiamo g con n⋅g

-I generatori del gruppo (Zn,+) sono gli elementi

Es: determinare i generatori di (Z ,+)

4

4x

Sono gli elementi di Z :

4x

Z : { [a] | MCD(a,4)=1 } = {[1][2][3][4]} = {[1][3]} *ho tolto quelli

non coprimi con 4

O(g) = |<g>|

Consideriamo due gruppo G e G e due loro elementi g e g Allora:

1 2 1 2.

O((g ,g )) = mcm (O(g ),O(g ))

1 2 1 2

Z xZ è ciclico MCD(a,b)=1



a b

Es: dire se Z xZ è ciclico

4 6

Sol: MCD(2,6)=2 quindi non è ciclico

Es: dire se Z xZ è ciclico

3 4

Sol: MCD(3,4)=1 quindi è ciclico.

I suoi generatori sono le coppie ordinare (g ,g ) dove:

1 2

∈ ∈

3x

g Z = { [a] | a Z, MCD(a,3)=1 } = { [1] [2] [3] }

1 ∈ ∈

4x

g Z = { [a] | a Z, MCD(a,4)=1 } = { [1] [2] [3] [4] }

2

I generatori sono quindi ( ) , ( , ) , ( , ) , ( , )

1́ , 1́ 1́ 3́ 2́ 1́ 2́ 3́

Se <g> è un gruppo finito e n=O(g) allora f:Zn<g> definita

k

ponendo f( )=g è un isomorfismo. Per dimostrare ciò bisogna:

ḱ

1) Verificare se f è ben definita, cioè è una funzione

á á á

Basta dimostrare che ( = -> f( )=f( )), cioè (

b́ b́

a b

= -> g =g )

b́ á ≡

Se = allora a b cioè n|b-a. -> esiste t tale che b-

b́ n

a=tn, cioè b=tn+a

b tn+a tn a n t a t a a

g = g =g *g =(g ) *g =e *g = g -> f è una funzione

2) Verificare se f è omomorfismo

´

á á

a+b a b

f( + ) = f( ) = g = g * g = f( ) * f( ) ->

b́ a+b b́

f è omomorfismo

3) Verificare se f è iniettiva

á á á á

a

Ker(f) = { |f( )=e } = { |g =e} = { |O(g)/a } =

á

{ tali che n divide a} = { }

0́

Quindi ker(f)={ } -> f è iniettiva

0́

4) Verificare se f è suriettiva

á á a

Im(f) = { f( ) | in Zn} : {g | a in Zn} = <g> <-

codominio

Quindi Im(f)=<g> -> f è suriettiva

f è un omomorfismo biettivo, cioè un ISOMORFISMO



Esempi:

Dire se f:Z definita ponendo f([a] )=[a] è omomorfismo

Z

8 12 8 12

1 – Devo vedere se [a] =[b] -> f([a] )=f([b] ) cioè [a] =[b] .

8 8 8 8 12 12

Per farlo verifico se [a] =[b] <-> 8|b-a implica che [a] =[b] <->

8 8 12 12

12|b-a

Non è vero perché per esempio a=0 e b=8: 8 divide 8 ma 12 non

divide 8, quindi f non è una funzione e di conseguenza non può

essere omomorfismo

Dire se f:Z definita ponendo f([a]) =[6a] è omomorfismo e

Z

8 12 8 12

iniettiva

1 – Devo verificare se [a] =[b] implica che [6a] =[6b]

8 8 12 12

[a] =[b] <-> 8|b-a ; [6a] =[6b] <-> 2|b-a ; è funzione perché 8|b-

8 8 12 12

a implica che 2|b-a

2 – Verifico se è omomorfismo:

f([a] +[b] ) = f([a+b] ) = [6(a+b)] = [6a] +[6b] = f([a] +f([b] ) ->

8 8 8 12 12 12 8 8

f è omomorfismo

3 – Verifico s è iniettiva

Ker(f) = { [a] | f([a] )= [0] } = { [a] | [6a] = [0] } = { [a] tali

8 8 12 8 12 12 8

che 12/(6a-0) } =

= { [a] tali che 2/a } = { , , , } . Visto che Ker(f)

Ó 2́ 4́ 6́

8

≠ {0} f non è iniettiva a

Dire se f:Z definita ponendo f( )= dove =(1 2 3)

á &sigma