Matematica Discreta Lezione del giorno 21 ottobre 2009

Matematica Discreta

Lezione del giorno 21 ottobre 2009

Abbiamo definito, dati 2 insiemi qualunque A,B, la loro unione AB.

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 gli 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 ad 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 non hanno elementi in comune si ha ovviamente A-B=A, B-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}

(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: 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,

(BC),

(BC)) si ha

(BC)=

B

C

(BC)=

B

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)

B

C

B

C

(BC)

Dimostriamo la prima delle 2 inclusioni (la dimostrazione della seconda é analoga): se x è un elemento generico di

(B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 e simultaneamente x

C, e si può concludere che x

B

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:

1 2 3

4 5

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 verificare graficamente sui

diagrammi di Eulero-Venn..