Matematica Discreta Lezione del giorno 23 novembre 2010 Insieme vuoto

Matematica Discreta

Lezione del giorno 23 novembre 2010 Insieme vuoto

Può accadere che un insieme sia descritto in modo implicito mediante un predicato che è falso per ogni valore della variabile. Per esempio:

A = { x / x è un intero positivo minore di 1/2 }

In tale caso l’insieme ottenuto è un insieme privo di elementi, detto insieme vuoto, e indicato con il simbolo .

Sottoinsiemi di un insieme.

Dati gli insiemi A, B, diremo che A è sottoinsieme di B (oppure che A è contenuto in B, o anche che A è incluso in B) e scriveremo AB, se ogni elemento di A è anche elemento di B.

Se A non è sottoinsieme di B, esisterà almeno un elemento di A che non appartiene a B.

Se gli insiemi sono descritti in modo esplicito, per verificare se AB basta verificare che ogni elemento nell’elenco di A compaia anche nell’elenco di B.

Per esempio se B = {1,3,4,5,6,8}, A = {6, 5, 3}, C = {8, 4, 2} si ha AB (ogni elemento 6, 5, 3 dell’elenco di A appare nell’elenco di B), ma si ha anche che C non è sottoinsieme di B (l’elemento 2 dell’elenco di C non appare nell’elenco di B).

Se gli insiemi sono invece descritti in modo implicito, mediante predicati:

A = { x / P(x) } B = { x / Q(x) }

allora verificare che AB equivale a dimostrare l’implicazione P  Q (perché affermare che ogni elemento di A è elemento di B equivale ad affermare che ogni valore di x che rende vero P rende vero anche Q).

Due insiemi A, B sono uguali se contengono gli stessi elementi: questo equivale ad affermare che ogni elemento di A è anche elemento di B e che viceversa ogni elemento di B è anche elemento di A. Quindi l’eguaglianza di insiemi A=B equivale alla “doppia inclusione” AB e BA .

Se gli insiemi sono descritti in modo esplicito, per verificare se A=B basta verificare che gli elenchi degli elementi di A e B siano lo stesso elenco (anche se gli elementi sono elencati in ordine diverso).

Per esempio se A = {1,3,4,5,6,8}, B = {4,8,6,5,3,1} allora si ha A=B.

Se gli insiemi sono descritti in modo implicito, mediante predicati:

A = { x / P(x) } B = { x / Q(x) }

allora verificare che A=B equivale a dimostrare vera sia l’implicazione P  Q che l’implicazione inversa Q  P, quindi l’eguaglianza di insiemi A=B corrisponde all’equivalenza dei predicati:

P  Q .

Per ogni insieme A, è ovvio che A è sottoinsieme di sé stesso:

AA

Se BA e se BA, si dice anche che B è contenuto propriamente in A e si scrive BA.

Per convenzione l’insieme vuoto  si considera sottoinsieme di qualunque insieme A.

Poiché, dato un insieme A qualunque, si ha sempre A e AA, i due sottoinsiemi , A sono detti sottoinsiemi banali o impropri dell’insieme A.

In particolare, fissato un arbitrario insieme A, possiamo costruire l’insieme delle parti di A (indicato con il simbolo P(A)), i cui elementi sono tutti i possibili sottoinsiemi di A.

Per esempio se A = {a, b, c}, l’insieme delle parti di A è l’insieme:

P(A) = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A }.

Si può notare che A contiene 3 elementi e P(A) contiene 8=2³ elementi: dimostreremo in seguito che ciò non è casuale.

Se A è un insieme fissato, possiamo descrivere in forma implicita un sottoinsieme B di A nel modo seguente:

B = { xA / P(x) } (dove P(x) è un predicato)

intendendo che gli elementi del sottoinsieme B sono tutti e soli gli elementi di A che rendono vero P(x).

Per esempio, se A = { x / x è intero positivo pari }, e se descriviamo in modo implicito il seguente sottoinsieme di A:

B = { xA / x<10 }

in modo esplicito si ha B = {2,4,6,8}.

Operazioni fra insiemi.

Sono procedimenti che, dati alcuni insiemi (operandi), costruiscono un nuovo insieme (risultato) i cui elementi dipendono dagli elementi degli insiemi operandi.

1) Unione di insiemi:

Dati gli insiemi A,B, si chiama insieme unione di A e B (indicato con AB) l’insieme degli elementi che appartengono ad almeno uno degli insiemi A,B.

Se A,B sono descritti in modo esplicito, AB è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono nell’elenco di A o nell’elenco di B o in ambedue (questi ultimi elencati 1 sola volta per evitare ripetizioni dello stesso elemento).

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora AB={1,2,3,4,5,6,8,9}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora AB è descritto in modo implicito dal predicato disgiunzione logica PvQ: infatti gli elementi di AB (valori che rendono vero la disgiunzione PvQ) saranno gli elementi che appartengono ad A (valori che rendono vero P) oppure gli elementi che appartengono a B (valori che rendono vero Q).

Proprietà evidenti dell’unione sono le seguenti:

1) dato un insieme A si ha AA=A (idempotenza)

2) dati 2 insiemi A,B si ha AB=BA (proprietà commutativa)

3) dati 3 insiemi A,B,C si ha (AB)C= A(BC) (proprietà associativa).

Le proprietà 1) e 2) seguono immediatamente dalla definizione di unione. Per la 3) basta notare che sia (AB)C che A(BC) coincidono con l’insieme degli elementi che appartengono ad almeno uno fra i 3 insiemi A,B,C.

2) Intersezione di insiemi:

Dati gli insiemi A,B, si chiama insieme intersezione di A e B (indicato con AB) l’insieme degli elementi che appartengono ad ambedue gli insiemi A,B.

Se A,B non hanno elementi in comune si ha AB= e si dice che A,B sono disgiunti.

Se A,B sono descritti in modo esplicito, AB è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono sia nell’elenco di A che nell’elenco di B.

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora AB={5,6}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora AB è descritto in modo implicito dal predicato congiunzione logica PQ.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

AB = { x / x è intero positivo dispari e x è intero >12 } (quindi AB contiene tutti gli interi dispari da 13 in poi).

Proprietà evidenti dell’intersezione sono le seguenti:

1) dato un insieme A si ha AA=A (idempotenza)

2) dati 2 insiemi A,B si ha AB=BA (proprietà commutativa)

3) dati 3 insiemi A,B,C si ha (AB)C=A(BC) (proprietà associativa) (per questa terza proprietà basta notare che sia (AB)C che A(BC) coincidono con l’insieme degli elementi che appartengono a tutti e 3 gli insiemi A,B,C)

Le proprietà 1) e 2) seguono immediatamente dalla definizione di intersezione. Per la 3) basta notare che sia (AB)C che A(BC) coincidono con l’insieme degli elementi che appartengono a tutti e 3 gli insiemi A,B,C.

3) Differenza di insiemi:

Dati gli insiemi A,B, si chiama insieme differenza A meno B (indicato con A-B) l’insieme degli elementi che appartengono ad A ma non appartengono a B.

Se A,B sono descritti in modo esplicito, A-B è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono nell’elenco di A ma non nell’elenco di B.

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora A-B={1,2,3,4} mentre B-A={8,9}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora A-B è descritto in modo implicito dal predicato P^Q congiunzione logica di P e della negazione di Q.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

A-B = { x / x è intero positivo dispari ed x è intero ≤12 } = {1,3,5,7,9,11}

mentre:

B-A = { x / x è intero >12 ed x è intero positivo pari}= {14,16,18,20,…..}

(quindi B-A contiene tutti gli interi pari da 14 in poi).

Dall’esempio precedente si deduce che in generale A-BB-A (dunque l’operazione differenza non soddisfa la proprietà commutativa).

4) Complementare di un sottoinsieme in un inseme:

Dati gli insiemi A,B e nel caso particolare in cui l’insieme B sia sottoinsieme dell’insieme A, la differenza A-B è detta complementare di B in A e indicata con B^c: dunque il complementare di B in A ha come elementi tutti gli elementi di A che non appartengono a B.

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, C^c, (BC)^c, (BC)^c) si ha

(BC)^c=B^cC^c (BC)^c=B^cC^c

Le dimostrazione di ognuna di queste 2 proprietà comporta la dimostrazione di una doppia inclusione. Per esempio per dimostrare la prima proprietà, si devono dimostrare le 2 inclusioni:

(BC)^cB^cC^c B^cC^c(BC)^c

Dimostriamo la prima delle 2 inclusioni (la dimostrazione della seconda é analoga): se x è un elemento generico di (BC)^c, allora, per definizione di complementare, si ha xA ma xBC, e per definizione di unione si ha xB e xC, dunque xA e xB e simultaneamente xA e xC, ossia xB^c e simultaneamente xC^c, e si può concludere che xB^cC^c.

Per concludere la trattazione delle operazioni fra insiemi, notiamo che valgono le seguenti proprietà distributive di unione e intersezione:

dati gli insiemi A,B,C si ha A(BC)=(AB)(AC) e A(BC)=(AB)(AC).

Esse si dimostrano facilmente con le doppie inclusioni.

Diagrammi di Eulero-Venn.

Sono rappresentazioni grafiche di un insieme, in cui gli elementi si rappresentano come punti del piano all’interno di una curva chiusa (spesso una circonferenza).

Esempio di diagramma di Eulero-Venn che rappresenta l’insieme A={1,2,3,4,5}:

Si possono rappresentare con tali diagrammi anche i risultati delle operazioni fra insiemi: unione, intersezione e differenza.

Per esempio per rappresentare l’intersezione AB:

A B

(l’insieme A è rappresentato con linee orizzontali, l’insieme B con righe verticali: l’insieme intersezione AB sarà rappresentato dalla quadrettatura).

Le proprietà già enunciate per le operazione fra insiemi si possono facilmente verificare graficamente sui diagrammi di Eulero-Venn..

1 2 3 4 5