Matematica Discreta I Lezione del giorno 12 ottobre 2007 Complementare Nel caso particolare in cui l’insieme B sia sottoinsieme dell’insieme A, la differenza A-B è detta complementare di A in B e indicata con

Matematica Discreta I

Lezione del giorno 12 ottobre 2007 Complementare

Nel caso particolare in cui l’insieme B sia sottoinsieme dell’insieme A, la differenza A-B è detta complementare di A in B e indicata con

A.

Le proprietà principali del complementare sono espresse dalle leggi di DeMorgan:

se B,C sono sottoinsiemi dell’insieme A (notare che anche BC, BC sono sottoinsiemi di A e si possono considerare i 4 complementari

B,

C,

(BC),

(BC)) si ha

(BC)=

B

C

(BC)=

B

C

Tali eguaglianze si verificano facilmente sui diagrammi di Eulero-Venn..

Prodotto cartesiano

Se a,b sono 2 elementi (di natura arbitraria) anche possibilmente coincidenti fra loro, la coppia ordinata (a,b) con primo elemento a, secondo elemento b è una struttura in cui si tiene conto sia degli elementi a,b che dell’ordine in cui sono elencati.

Dunque la coppia ordinata (a,b) si distingue dall’insieme {a,b} sia perché può avvenire che a=b, sia perché (se a,b sono diversi) si ha (a,b)(b,a) (mentre invece {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)}.

Relazioni fra insiemi

Con una definizione formalmente poco precisa si può dire che una relazione dall’insieme A all’insieme B è una “regola” che permette di associare fra loro elementi di A con elementi di B.

Più formalmente, 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.

Spesso una relazione R da A a B viene descritta da un predicato P(x,y) in 2 variabili (in cui la variabile x assume valori in A, la variabile y assume valori in B): il predicato fornisce la “regola”

con cui gli elementi di A sono associati agli elementi di B, nel senso che, dati un elemento aA, e un elemento bB, si intende che aRb (quindi che l’elemento aA è associato nella relazione R all’elemento bB) solo quando P(a,b) è vero (dove ricordiamo che P(a,b) è la proposizione ottenuta sostituendo x con a, y con b).

Esempio: se A={1,2,3,6}, B={2,3,5} e se la relazione R da A a B è descritta dal predicato P(x,y)=”x<y” (in pratica un elemento aA è associato nella relazione R ad un elemento bB quando a<b), allora il sottoinsieme R del prodotto cartesiano AxB non è altro che:

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

Da questo esempio si può notare che, data una relazione R da A a B, può avvenire che un elemento di A non sia associato a nessun elemento di B (per es. il 6A) oppure che un elemento di A sia associato a più di un elemento di B (per es. il 2A).

Se A,B sono insiemi con un numero finito di elementi, una relazione R da A a B si può rappresentare graficamente rappresentando ogni elemento degli insiemi come punto del piano e unendo con una freccia un elemento aA con un elemento bB solo quando aRb.

Esempio: nell’esempio precedente si ottiene la seguente rappresentazione grafica

R

A B

Si può anche usare la rappresentazione matriciale: se A contiene n elementi e se B contiene m elementi, si costruisce una “tabella” (matrice) con n righe ed m 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 un valore 1 oppure 0 a secondo se l’elemento della riga della casella è o no associato nella relazione R all’elemento della colonna della casella.

Esempio: nell’esempio precedente si ottiene la seguente rappresentazione matriciale (in cui la matrice ha 4 righe e 4 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

Funzioni

Dati gli insiemi A,B, una funzione da A a B è una relazione da A a B tale che ogni elemento di A è associato ad uno e un solo elemento di B.

L’insieme A è detto dominio della funzione, l’insieme B codominio.

Esempio: se A= {1,2,-2,3}, B={1,3,4,9}, e se la relazione da A a B è descritta dal predicato P(x,y)=”x

=y” (quindi in pratica un elemento di A è associato ad un elemento di B se il quadrato del primo è uguale al secondo) allora si ottiene una funzione da A a B in quanto il sottoinsieme R del prodotto cartesiano AxB è R={(1,1),(2,4),(-2,4),(3,9)} e si nota che ogni elemento di A è associato ad uno e un solo elemento di B.

1 2 3 6

2

3

5

Spesso una funzione da A a B è indicata col simbolo f: A  B. Dato un elemento a del dominio A, l’unico elemento b del codominio B che è associato all’elemento a è detto corrispondente o immagine di a, ed è indicato con il simbolo f(a).

Nel caso di funzioni fra insiemi numerici, talvolta una funzione f: A  B è definita scrivendo un’espressione del tipo f(x)=….. dove i puntini contengono una formula algebrica nella variabile x, intendendo con ciò che, dato un elemento aA, il corrispondente b=f(a)B si ottiene sostituendo nella formula la variabile con il valore a, e calcolando il risultato. Naturalmente non tutte le formule producono funzioni da A a B.

Esempio: se A è l’insieme degli interi positivi, negativi o nulli e B quello degli interi positivi, la formula f(x)=x

+1 definisce una funzione da A a B (perché ad ogni intero a, positivo, negativo o nullo, è associato un unico intero positivo f(a)=a

+1). Invece se A è l’insieme degli interi positivi e B quello dei razionali positivi, f(x)=1/(x-2) non definisce una funzione da A a B (perché l’intero positivo 2 non ha corrispondente f(2) in B).

Se la relazione è rappresentata graficamente (con le frecce), essa è una funzione quando da ogni elemento del dominio A parte una e una sola freccia verso il codominio B.

Se la relazione è rappresentata con una matrice, essa è una funzione quando ogni riga contiene un

solo valore=1 (e tutti gli altri =0).