Matematica Discreta Lezione del giorno 24 novembre 2009

Matematica Discreta

Lezione del giorno 24 novembre 2009

Useremo i seguenti simboli per indicare gli insiemi numerici più comuni:

N è l’insieme dei numeri interi >0, detti anche numeri naturali:

N = { x / x è intero positivo } = {1,2,3,4,5….}

Z è l’insieme dei numeri interi relativi (cioè dei numeri interi positivi, negativi e lo zero):

Z = { x / x è intero positivo, negativo o nullo } = {0,1,-1,2,-2,3,-3,…..}

Q è l’insieme dei numeri razionali relativi (ossia delle frazioni aventi come numeratore e denominatore 2 numeri interi relativi, e con il denominatore non nullo):

Q = { x / x = a/b, con a,bZ, e con b0 }

R è l’insieme dei numeri reali relativi (cioè dei numeri reali positivi, negativi e lo zero): per una definizione formale di “numero reale” si rimanda al corso di Analisi; per i nostri scopi basta conoscere l’usuale rappresentazione “decimale” di un numero reale, con una “parte intera” ed una

“parte decimale” dopo la virgola.

Si ha ovviamente la catena di inclusioni seguente:

N  Z  Q  R

Un asterisco sul simbolo indicherà che dall’insieme è escluso lo 0 (per es. Q* è l’insieme dei numeri razionali relativi non nulli, cioè solo positivi o negativi); un segno + sul simbolo indicherà che dell’insieme sono considerati solo i positivi (per es. Q

è l’insieme dei numeri razionali positivi) Prodotto cartesiano

Se a,b sono 2 elementi (di natura arbitraria, nello stesso insieme o in insiemi diversi ed anche possibilmente coincidenti fra loro) la coppia ordinata (a,b) con primo elemento a e con secondo elemento b è per definizione una struttura in cui si tiene conto sia degli elementi a,b che dell’ordine in cui sono elencati. Dunque 2 coppie ordinate (a,b), (c,d) sono considerate uguali solo quando a=c e b=d

Notare che la coppia ordinata (a,b) è un concetto diverso dall’insieme {a,b} perché si ha per esempio (1,2)(2,1) (come coppie ordinate) , mentre invece come insiemi si ha {1,2}={2,1}.

Notare anche che nella coppia ordinata (a,b) è anche permesso che sia a=b.

Dati 2 insiemi A,B si chiama prodotto cartesiano AxB l’insieme che contiene tutte le possibili coppie ordinate (a,b) dove il primo elemento a varia nell’insieme A, ed il secondo elemento b varia nell’insieme B.

Esempio: se A={3,a,5}, {a,5,2} allora

AxB={(3,a),(3,5),(3,2),(a,a),(a,5),(a,2),(5,a),(5,5),(5,2)}.

Relazioni fra insiemi

Dati gli insieme A,B, si chiama relazione dall’insieme A all’insieme B un qualunque sottoinsieme

R del prodotto cartesiano AxB (quindi R è un insieme di alcune coppie (a,b) con il primo elemento

in A e il secondo in B). Se una coppia (a,b) (con aA, bB) appartiene ad R, diremo che

l’elemento aA è associato nella relazione R all’elemento bB e scriveremo il simbolo aRb ; se

invece la coppia (a,b) non appartiene ad R diremo che l’elemento aA non è associato nella

relazione R all’elemento bB e scriveremo il simbolo aRb con una sbarra che taglia la R.

Esempio: se A={1,2,3,6}, B={2,3,5} e se la relazione da A a B è il seguente sottoinsieme di AxB:

R = {(1,2), (1,3), (2,3), (6,2)}

Allora 1R2 (quindi l’elemento 1 è associato nella relazione R all’elemento 2); inoltre si ha anche 1R3, 2R3, 6R2; ma l’elemento 1A non è per esempio associato all’elemento 5B perché la coppia (1,5) non appartiene ad R.

Come si vede dall’esempio, in una relazione R da A a B un elemento di A può essere associato a più di un elemento di B, oppure non essere associato a nessun elemento di B.

Dati 2 insiemi A,B, una relazione R dall’insieme A all’insieme B può essere descritta in vari modi:

1) esplicito: si elencano tutte le coppie che formano il sottoinsieme R del prodotto cartesiano AxB (questo modo è stato usato nell’esempio precedente). E’ ovvio che tale modo esplicito è esauriente solo quando R è formato da un numero finito di coppie.

2) implicito: si fissa un predicato P(x,y) in 2 variabili (in cui la variabile x ha come universo A, la variabile y ha come universo B) e si conviene che un elemento a A è associato nella relazione R ad un elemento bB (in simboli aRb) solo quando la proposizione logica P(a,b) è vera (dove ricordiamo che P(a,b) è la proposizione ottenuta dal predicato P(x,y) sostituendo x con il valore a, y con il valore b).

In pratica il predicato P(x,y) fornisce la “regola” con cui stabilire quali elementi di A e quali elementi di B sono associati nella relazione R.

Esempio: se A={1,2,3,6}, B={2,3,5} e se la relazione R da A a B è descritta in modo implicito dal predicato P(x,y)=”x<y” allora un elemento aA è associato nella relazione R ad un elemento bB quando a<b. In tale esempio la rappresentazione esplicita della relazione R è il seguente sottoinsieme del prodotto cartesiano AxB:

R={(1,2),(1,3),(1,5),(2,3),(2,5),(3,5)}.

3) grafico: si rappresentano A,B con i diagrammi di Eulero-Venn, e si conviene di unire con una freccia un elemento aA con un elemento bB solo quando aRb, cioè solo quando l’elemento aA è associato nella relazione R all’elemento B.

Esempio: la rappresentazione grafica della relazione R nell’esempio precedente è la seguente:

R

A B

4) matriciale: si costruisce una “tabella” (detta matrice) formata da caselle disposte in righe e colonne, in cui si fanno corrispondere ad ogni riga un elemento di A, ad ogni colonna un elemento di B, e si pone in ogni casella il valore 1 se l’elemento corrispondente alla riga della casella è associato nella relazione R all’elemento della colonna della casella; si pone invece nella casella il valore 0 in caso contrario.

1 2 3 6

2

3

5

Esempio: per la relazione R dell’esempio precedente si ottiene la seguente rappresentazione matriciale (in cui la matrice ha 4 righe e 3 colonne, con le righe che ordinatamente corrispondono agli elementi 1,2,3,6, le colonne agli elementi 2,3,5):

1 1 1

0 1 1

0 0 1

0 0 0