Matematica Discreta
Lezione del giorno 16 ottobre 2009
Tutti i Teoremi matematici sono in pratica espressi sotto forma di implicazione fra 2 predicati.
Per esempio il famoso Teorema geometrico:
la somma delle ampiezze degli angoli interni di un triangolo è 180°
non è altro che l’implicazione PQ dove i predicati P,Q sono i seguenti:
P(x)=”x è un triangolo”
Q(x)=” la somma delle ampiezze degli angoli interni di x è 180°”
(con campo di variabilità = poligoni nel piano).
Dimostrazione per assurdo
Abbiamo già illustrato una tecnica per dimostrare vera un’implicazione PQ fra 2 predicati: si suppone di avere fissato un valore generico (ma non precisato) delle variabili che rende vero P (ipotesi), e attraverso dei passaggi intermedi (giustificati da conoscenze acquisite in precedenza) si cerca di dimostrare che tale valore rende vero anche Q (tesi).
La tecnica dimostrativa illustrata sopra è detta anche diretta. Vi è però anche una diversa tecnica dimostrativa, detta per assurdo: per dimostrare vera l’implicazione 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 intermedi (sempre opportunamente giustificati) si cerca di pervenire ad una contraddizione logica (se tale contraddizione viene raggiunta, si può concludere che in effetti non esiste un valore delle variabili che renda vero P e falso Q, e che dunque PQ).
Per esempio se sono dati i seguenti predicati (con campo di variabilità=numeri interi positivi):
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 della dimostrazione per assurdo si potrebbe procedere operando i seguenti passaggi:
1) supponiamo (per assurdo) che esista un valore della variabile x che renda vero P ma falso Q, quindi x sia pari, ma x+1 non sia dispari, cioè x+1 sia pari
2) applicando la definizione di numero pari, si ha x=2z, x+1=2t, dove z,t sono opportuni numeri interi positivi
3) sottraendo la prima eguaglianza dalla seconda eguaglianza, si ha 1=2t-2z
4) applicando la proprietà distributiva della differenza rispetto al prodotto si ha 1=2(t-z) e si ottiene che 1 è multiplo di 2 (contraddizione logica).
Avendo ottenuto una contraddizione, si può concludere che in effetti PQ . Teoria degli insiemi
Studieremo la teoria “ingenua” degli insiemi (in contrapposizione alla cosiddetta teoria
“assiomatica”), 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, ed anche natura diversa fra loro:
potremmo per esempio costruire un insieme che ha come elementi il numero 5, la città di Milano e il concetto astratto di bontà.
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.
