Matematica Discreta I
Lezione del giorno 8 ottobre 2007
La tecnica dimostrativa illustrata sopra è diretta. Vi è anche una tecnica dimostrativa per assurdo:
per dimostrare che PQ si suppone (per assurdo) che sia dato un valore delle variabili che renda vero P ma falso Q (quindi si suppone per assurdo vera l’ipotesi e falsa la tesi) e attraverso dei passaggi logici si cerca di pervenire ad una contraddizione logica: se è così, si può concludere che in effetti non esiste un valore delle variabili che renda vero P ma falso Q, dunque PQ.
Per esempio se sono dati i seguenti predicati (con campo di variabilità x=numero intero positivo):
P(x) = “x è pari”
Q(x) = “x+1 è dispari”
(dove “pari” significa multiplo di 2, e “dispari” significa non pari), per dimostrare che PQ con la tecnica per assurdo si potrebbe procedere operando i seguenti passaggi:
1) supponiamo (per assurdo) che x sia un valore che renda vero P ma falso Q, quindi x sia un intero positivo pari ma x+1 non sia dispari, cioè x+1 sia pari
2) applicando la definizione di pari, si ha x=2z, x+1=2t, dove z,t sono opportuni numeri interi positivi
3) sostituendo il valore x=2z nella seconda eguaglianza, si ha 2z+1=2t 4) sottraendo ad ambo i membri dell’eguaglianza il numero 2z si ha 1=2t-2z
5) applicando la proprietà distributiva della somma rispetto al prodotto si ha 1=2(t-z) e si ottiene che 1 è multiplo di 2 (contraddizione logica).
Insiemistica
Esporremo la teoria “ingenua” degli insiemi, in cui il concetto di insieme si considera primitivo, ossia non si definisce, intendendo immediatamente evidente il concetto di insieme come sinonimo di raccolta, collezione di elementi.
Gli elementi di un insieme possono avere natura arbitraria.
Se A è un insieme ed x un suo elemento, diremo che x appartiene ad A e scriveremo xA. Se invece x non è elemento dell’insieme A, diremo che x non appartiene ad A e scriveremo xA.
Un insieme può essere descritto in modo esplicito, elencando tutti i suoi elementi.
Per esempio possiamo costruire il seguente insieme di nome A:
A ={3, 5, 7, 9}
contenente i 4 numeri interi elencati fra parentesi.
Un insieme si distinguerà solo per gli elementi che contiene, che si considerano sempre distinti senza ripetizioni, e non per l’ordine in cui sono elencati.
Quindi lo stesso insieme A dell’esempio precedente può essere descritto in modo esplicito anche da A ={5, 9, 7, 3}.
Nel modo esplicito per verificare se xA basta verificare se x compare nell’elenco degli elementi di A: nell’esempio precedente si ha 7A, ma 8A.
Ovviamente tale modo esplicito di descrivere un insieme è esauriente solo nel caso di insiemi che contengano un numero finito di elementi.
Un insieme può essere descritto anche in modo implicito, indicando le proprietà che caratterizzano i suoi elementi.
Per esempio possiamo costruire il seguente insieme di nome B:
B = { x / x è un intero positivo pari }
(si legge: “B è l’insieme di tutti gli x tali che x è un intero positivo pari”; il simbolo / può talvolta essere sostituito dal simbolo :) .
In generale le proprietà caratterizzanti un insieme sono descritte in modo implicito mediante un predicato:
B = { x / P(x) }
dove si intende che gli elementi di B sono esattamente tutti i valori della variabile x che rendono vero il predicato P(x).
Nell’esempio:
B = { x / x è un intero positivo pari }
il predicato è appunto “x è un intero positivo pari” e si ha per esempio 6A, ma 9A.
Se il predicato che descrive in modo implicito l’insieme è falso per ogni valore della variabile, si ottiene un insieme privo di elementi, detto insieme vuoto, e indicato con .
Per esempio:
{ x / x è intero >5 e <3 } = .
Sottoinsiemi di un insieme.
Dati gli insiemi A, B, diremo che B è contenuto in A, oppure che B è sottoinsieme di A, e scriveremo BA, se ogni elemento di B è anche elemento di A.
Per convenzione consideriamo l’insieme vuoto sottoinsieme di qualunque insieme.
E’ anche ovvio che ogni insieme A è sottoinsieme di sé stesso.
Se B non è contenuto in A, scriveremo BA.
Se gli insiemi sono descritti in modo esplicito, per verificare se BA basta verificare che ogni elemento nell’elenco di B compaia anche nell’elenco di A.
Per esempio se A = {1,3,4,5,6,8}, B = {6, 5, 3}, C = {8, 4, 2} si ha BA, ma CA.
Se gli insiemi sono descritti in modo implicito, mediante predicati:
A = { x / P(x) } B = { x / Q(x) }
allora verificare che BA equivale a dimostrare vera l’implicazione Q P (perché ogni valore di x che rende vero Q dovrà rendere vero anche P, se ogni elemento di B è elemento di A).
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” AB e BA .
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 Q P che l’implicazione inversa P Q, quindi in questo caso l’eguaglianza di insiemi A=B corrisponde all’equivalenza dei predicati: P Q .
Poiché, dato un insieme A qualunque, si ha sempre A e AA, i due sottoinsiemi , A sono detti sottoinsiemi banali dell’insieme A. Per indicare che un sottoinsieme B dell’insieme A è diverso da A spesso si usa il simbolo BA.
Essendo arbitraria la natura degli elementi di un insieme, possiamo anche considerare insiemi i cui elementi sono a loro volta degli insiemi.
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=23 elementi: dimostreremo in seguito che ciò non è casuale.
