Fondamenti di informatica - Laurea triennale Informatica/Altri metodi di prova

Questi metodi di prova sono molto usati in matematica discreta e nella logica:

• dimostrazione per assurdo
• dimostrazione per contrapposizione
• dimostrazione per casi
• dimostrazione di equivalenze
• dimostrazioni di esistenza

Dimostrazione per assurdo

Per dimostrare un’implicazione del tipo p→q con una dimostrazione per assurdo, si assume che: p sia vera e che la conclusione sia falsa, cioè: ¬q sia vera. Poi si cerca di arrivare a una contraddizione, cioè a una proposizione del tipo: r∧¬r. Se assumendo p e ¬q si ottiene una contraddizione, allora ¬q non può essere vera, quindi q deve essere vera.

In pratica: p∧¬q⇒contraddizione quindi: p→q.

Esempio tipico

Si vuole dimostrare:

Se n2 è pari, allora n è pari.

Per assurdo si assume che:

• n2 sia pari;
• n sia dispari.

Se n è dispari, allora: n=2k+1. Elevando al quadrato: n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1. Quindi n2 sarebbe dispari, ma per ipotesi era pari. Contraddizione.

Dunque n è pari.

Dimostrazione per contrapposizione

La contrapposizione si basa sul fatto che l’implicazione p→q è logicamente equivalente a: ¬q→¬p.

Quindi, invece di dimostrare direttamente “se p, allora q”, si può dimostrare:

se q è falsa, allora anche p è falsa.

È un caso particolare della dimostrazione per assurdo, ma spesso è più ordinato e diretto.

Esempio

Per dimostrare:

Se x2 è irrazionale, allora x è irrazionale.

Si dimostra la contrapposta:

Se x è razionale, allora x2 è razionale.

Infatti, se:

x=ba​ con a,b interi e b!=0, allora: x2=b2a2​, che è ancora razionale.

Dimostrazione per contraddizione

Per dimostrare:

x+y≥2⇒(x≥1)∨(y≥1)

assumo: x+y≥2 e contraddico l'affermazione a destra dell'uguale: ¬((x≥1)∨(y≥1)) che usando le leggi di De Morgan equivale a: x<1∧y<1 ovvero x+y<2, il contrario dellì'asssunzione di origine, il che valida la prova

Quindi la contrapposta è vera, e di conseguenza è vera anche l’implicazione originale.

Un esempio pratico: il paradosso del bevitore

Per verificare che tale affermazione è vera: “Esiste una persona in questa stanza tale che, se essa beve, allora tutti bevono.”

Si può quindi dire:

B(x)="x beve"

ed in tal modo si può esprimere l'affermazione di cui sopra così:

∃x ∈ S (B(x) → ∀y B(y))

Se B(x) è vera e tutti bevono (∀y B(y) è vera) l'affermazione è ovviamente vera, ma anche nel caso B(x) fosse falsa l'implicazione è per forza vera indipendentemente dal termine ∀y B(y) per come funziona la tavola di verità dell'implicazione, anche se per la logica del "senso comune" non è così. le regole della logica formale non sempre corrispondono a quelle che utilizziamo ogni giorno

Dimostrazione per casi

La dimostrazione per casi si usa quando l’ipotesi può essere divisa naturalmente in più possibilità.

Se per dimostrare p→q, l’ipotesi p può essere spezzata in casi: p1​,p2​,…,pn​, allora si dimostra separatamente: p1​→q, p2​→q, e così via.

Se tutti i casi coprono tutte le possibilità, allora la dimostrazione è completa.

Esempio con il valore assoluto

Si vuole dimostrare che per ogni reale x: ∣x∣≥0. Si considerano due casi.

Caso 1: x≥0.

Per definizione: ∣x∣=x. Quindi: ∣x∣≥0. Caso 2: x<0.

Per definizione: ∣x∣=−x. Poiché x<0, allora −x>0, quindi: ∣x∣>0. In entrambi i casi: ∣x∣≥0.

Dimostrazione esaustiva

Una forma particolare di dimostrazione per casi è la dimostrazione esaustiva.

Si usa quando il numero di casi è finito e abbastanza piccolo da poterli controllare tutti uno per uno.

Per esempio, se un’equazione può avere soluzioni solo in un insieme limitato di valori, si possono provare tutti quei valori e mostrare che nessuno funziona.

Dimostrazione di equivalenze

Molti teoremi hanno la forma: p⟺q

cioè:

p se e solo se q.

Per dimostrare un “se e solo se”, bisogna dimostrare due implicazioni:

p→q e q→p. Quindi la dimostrazione ha due direzioni.

Esempio

Dimostrare:

Un intero n è dispari se e solo se n+1 è pari.

Bisogna dimostrare due cose.

Prima direzione

Se n è dispari, allora: n=2k+1. Quindi: n+1=2k+2=2(k+1), perciò n+1 è pari.

Seconda direzione

Se n+1 è pari, allora: n+1=2k. Quindi: n=2k−1=2(k−1)+1, perciò n è dispari.

Dunque: n eˋ dispari⟺n+1 eˋ pari.

Equivalenza tra più proposizioni

A volte bisogna dimostrare che più proposizioni sono equivalenti, per esempio: p1​,p2​,p3​,…,pn​. Un metodo comune consiste nel dimostrare una catena ciclica: p1​→p2​, p2​→p3​, … pn​→p1​. Questo basta per concludere che tutte le proposizioni sono equivalenti.

Attenzione: non basta dimostrare implicazioni “a caso”; devono collegare tutte le proposizioni in modo corretto.

Dimostrazioni di esistenza

Una dimostrazione di esistenza serve a dimostrare una proposizione del tipo: ∃xP(x),

cioè:

esiste almeno un x tale che P(x) è vera.

Ci sono due tipi principali di dimostrazioni di esistenza.

7.1 Dimostrazione costruttiva

È una dimostrazione in cui si mostra esplicitamente un esempio.

Per dimostrare che esiste un x con una certa proprietà, si trova concretamente un valore di x e si verifica che funziona.

Esempio

Se a e b sono reali con: a<b, allora esiste un reale x tale che: a<x<b. Basta scegliere: x=2a+b​. Questo numero sta esattamente a metà tra a e b, quindi soddisfa la proprietà richiesta.

Dimostrazione non costruttiva

È una dimostrazione che mostra che un oggetto esiste, ma senza indicare esplicitamente quale sia.

Spesso si usa la dimostrazione per assurdo.

Esempio

Siano: a1​,a2​,…,an​ numeri reali, e sia: aˉ=na1​+a2​+⋯+an​​ la loro media.

Si vuole dimostrare che esiste almeno un indice i tale che: ai​≥aˉ. Per assurdo, si suppone che tutti gli ai​ siano minori della media: ai​<aˉper ogni i. Sommando tutte le disuguaglianze: a1​+a2​+⋯+an​<naˉ. Dividendo per n: na1​+a2​+⋯+an​​<aˉ. Ma il membro sinistro è proprio aˉ, quindi si ottiene: aˉ<aˉ, che è impossibile.

Dunque deve esistere almeno un ai​ tale che: ai​≥aˉ. Questa è una dimostrazione non costruttiva perché prova che tale indice esiste, ma non lo indica direttamente.

Consigli pratici per scegliere il metodo di dimostrazione

Se una dimostrazione diretta sembra difficile, prova una dimostrazione per assurdo. In questo modo hai più informazioni, perché puoi assumere sia l’ipotesi sia la negazione della conclusione.

Quando usi una dimostrazione per assurdo, è bene scrivere chiaramente frasi come:

Supponiamo per assurdo che la conclusione sia falsa.

Oppure:

Assumiamo, per ottenere una contraddizione, che...

La dimostrazione per casi è utile quando l’ipotesi si divide naturalmente in possibilità diverse. Per esempio, con il valore assoluto conviene distinguere tra:

x≥0 e x<0. Per dimostrare un “se e solo se”, bisogna sempre ricordare di dimostrare entrambe le direzioni: p→q e q→p. Per dimostrare che più proposizioni sono equivalenti, spesso conviene costruire una catena di implicazioni ciclica.

Per dimostrare un enunciato esistenziale, bisogna mostrare che almeno un oggetto con quella proprietà esiste. Se lo si trova esplicitamente, la dimostrazione è costruttiva; se si dimostra solo che deve esistere, è non costruttiva.

Schema finale

Metodo	Quando usarlo	Idea principale
Per assurdo	Quando la prova diretta è difficile	Assumi la negazione della conclusione e trova una contraddizione
Per contrapposizione	Quando è più facile dimostrare ¬q→¬p	Usa l’equivalenza tra p→q e ¬q→¬p
Per casi	Quando l’ipotesi si divide in possibilità	Dimostra la conclusione in ogni caso
Esaustiva	Quando i casi sono pochi e finiti	Controlla tutti i casi possibili
Equivalenza	Per dimostrare p⟺q	Dimostra entrambe le direzioni
Esistenza costruttiva	Quando puoi trovare un esempio	Esibisci un oggetto che funziona
Esistenza non costruttiva	Quando non trovi l’esempio direttamente	Dimostra indirettamente che deve esistere