Matematica Discreta
Lezione del giorno 12 novembre 2010 Implicazione logica
Dati due predicati P, Q, nelle stesse variabili, diremo che P implica Q (oppure: da P segue Q, o ancora: se P allora Q) quando tutti i valori delle variabili che rendono vero P rendono vero anche Q.
In questo caso scriveremo il simbolo PQ
Per esempio se sono dati i seguenti predicati (con universo = numeri interi positivi):
P(x) = “x<4”
Q(x) = “x+3<9”
allora è vero che P implica Q perché i valori della x che rendono vero P sono esattamente x=1,2,3 e si verifica facilmente che essi rendono vero anche Q.
Spesso però i valori delle variabili che rendono vero P sono in numero infinito, e in tal caso non è possibile, come nell’esempio precedente, verificare singolarmente che ciascuno di essi rende vero anche Q.
In tal caso si ricorre a una dimostrazione logico-deduttiva: si suppone di avere un valore generico (ma non precisato) delle variabili che rende vero P (ipotesi), e attraverso delle deduzioni logiche (passaggi della dimostrazione) giustificate da conoscenze acquisite in precedenza, si cerca di dimostrare che tale valore delle variabili rende vero anche Q (tesi).
Per esempio se sono dati i seguenti predicati (con universo = numeri interi positivi):
P(x) = “x>7”
Q(x) = “x+5>8”
per dimostrare che PQ si potrebbe procedere operando i seguenti passaggi:
1) supponiamo che x sia un valore che renda vero P (ipotesi) quindi che x sia un intero positivo tale che x>7
2) applicando la proprietà delle diseguaglianze che permette di sommare ad ambo i membri lo stesso numero ottenendo una diseguaglianza ancora valida si ha x+5>12
3) da x+5>12 e 12>8 si ottiene x+5>8 (applicando la cosiddetta “proprietà transitiva”
dell’ordinamento dei numeri interi positivi) quindi x rende vero anche Q (tesi) Se non è vero che un predicato P implica un predicato Q, diremo che P non implica Q.
E’ ovvio che se si vuole verificare che un predicato P non implica un predicato Q, allora non si deve procedere con una dimostrazione, ma bensì cercare almeno un valore delle variabili che renda vero P ma renda falso Q.
Nell’esempio precedente:
P(x) = “x>7”
Q(x) = “x+5>8”
abbiamo già dimostrato che si ha PQ. Tuttavia non è vero che QP, in quanto è possibile esibire valori di x che rendo vero Q ma falso P (per es. x=5).
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 universo = 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 in effetti PQ).
Per esempio se sono dati i seguenti predicati (con universo=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 logica, si può concludere che in effetti PQ .
