Matematica Discreta Lezione del giorno 12 ottobre 2011

Matematica Discreta

Lezione del giorno 12 ottobre 2011

I simboli che useremo per indicare gli insiemi numerici più comuni saranno i seguenti:

N indicherà l’insieme dei numeri interi positivi (detti anche numeri naturali), Z indicherà l’insieme dei numeri interi relativi (ossia dei numeri interi positivi, negativi e lo zero), Q indicherà l’insieme dei numeri razionali (ossia delle frazioni in cui numeratore e denominatore sono numeri interi relativi, e il denominatore è diverso da 0), R indicherà l’insieme dei numeri reali (per una loro definizione formale si rinvia al corso di Analisi; per i nostri scopi basta conoscere la loro rappresentazione con una parte “intera” ed una parte “decimale” dopo la virgola).

Si hanno le seguenti inclusioni proprie di insiemi:

N  Z  Q  R

Un asterisco sul simbolo indicherà che dall’insieme è tolto lo 0: per esempio Z

indicherà l’insieme dei numeri interi relativi diversi da 0; un + sul simbolo indicherà che dell’insieme si considerano solo i numeri positivi: per esempio R

indicherà l’insieme dei numeri reali positivi (ovviamente Z

=N ).

Prodotto cartesiano di insiemi

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 insiemistica in cui si tiene conto sia degli elementi a,b che dell’ordine in cui sono elencati.

Dunque il concetto di coppia ordinata (a,b) è diverso da quello di insieme {a,b} perché si ha (a,b)(b,a), almeno quando ab (mentre invece come insiemi si ha {a,b}={b,a}).

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A, ed il secondo elemento b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)}.

Notiamo anche che se l’insieme A contiene un numero finito n di elementi e se l’insieme B contiene un numero finito m di elementi, allora il prodotto cartesiano AxB contiene esattamente un numero nm di coppie. Infatti dobbiamo accoppiare il primo elemento di A con tutti gli m elementi di B (ottenendo m coppie), poi il secondo elemento di A con tutti gli m elementi di B (ottenendo altre m coppie), e così via accoppiando ogni elemento di A con tutti gli m elementi di B (ottenendo ad ogni passaggio sempre m coppie): il numero totale di coppie che otteniamo è dunque una somma:

m+m+…….m

con n addendi (tanti addendi quanti sono gli elementi di A) ossia è effettivamente nm.

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 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 perché la coppia (1,5) appartiene ad R (quindi l’elemento 1A è associato all’elemento 2B), ma l’elemento 1A non è 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 A è l’universo della variabile, B è l’universo della variabile y) e si conviene che, dati un elemento aA e un elemento bB, si ha aRb (quindi l’elemento aA è associato nella relazione R all’elemento bB) 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 a, y con 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 fra di loro 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 proprio 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 1

2 3 6

2

3

5