Matematica Discreta I Lezione del giorno 10 ottobre 2007

Matematica Discreta I

Lezione del giorno 10 ottobre 2007

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 è l’insieme dei numeri interi positivi pari, si ha:

B = { xA / x<10 } = {2,4,6,8}.

Operazioni fra insiemi.

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 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.

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

AB = { x / x è intero positivo dispari o x è intero >12 }

(quindi AB contiene gli interi dispari 1,3,5,7,9,11 e tutti gli interi consecutivi da 13 in poi).

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

2) 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

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

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.

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 con una quadrettatura).

Proprietà delle operazioni fra insiemi.

1) Idempotenza:

Se A è un insieme qualunque si ha AA=A, AA=A (proprietà evidenti per definizione di unione e intersezione)

2) Proprietà commutativa:

Comunque presi gli insiemi A,B si ha AB=BA, AB=BA (idem) 3) Proprietà distributiva:

Comunque presi gli insiemi A,B,C si ha (AB)C=(AC)(BC), (AB)C=(AC)(BC) (queste ultime proprietà si possono verificare facilmente sui diagrammi di Eulero-Venn).

1 2 3

4 5