Dimostrazione per contrapposizione

Template:O Nella logica, la contrapposta di una proposizione condizionale si forma negando entrambi i termini e invertendo il verso dell'implicazione logica. La contrapposta dell'affermazione "Se A è, allora è B" è la proposizione "Se non-B è, allora è non-A". La relativa operazione logica di inferenza immediata si chiama contrapposizione. Un'affermazione e la sua contrapposta sono logicamente equivalenti poiché la verità dell'una implica la verità dell'altra: o sono entrambe vere o sono entrambe false.

Nella matematica, la dimostrazione per contrapposizione o prova per contrapposizione è una regola di inferenza usata nelle dimostrazioni, in cui si deduce un'affermazione condizionale dalla sua contrapposta. In altre parole, la conclusione "se A , allora B " viene dedotta costruendo una prova dell'affermazione "se non è B , allora non è A". Tale approccio è in genere preferito se la prova della contrapposta risulta più semplice della prova dell'affermazione condizionale di partenza.

La seguente tavola di verità dimostra la validità della dimostrazione per contrapposizione:

p	q	$\mathrm{\neg }$p	$\mathrm{\neg }$q	p → q	$\mathrm{\neg }$q → $\mathrm{\neg }$p
V	V	F	F	V	V
V	F	F	V	F	F
F	V	V	F	V	V
F	F	V	V	V	V

Differenze con la dimostrazione per contraddizione

• Dimostrazione per contraddizione (reductio ad impossibile): si assume come ipotesi che $\mathrm{\neg }A$ sia vera. Si dimostra che $\mathrm{\neg }A\to B$ è falsa, deducendo quindi che $\mathrm{\neg }A$ è falsa e per doppia negazione che $A$ è vera. Si noti che nella dimostrazione per assurdo si procede in un modo ancora diverso, assumendo che la tesi $B$ sia vera per dimostrare che $B\to \mathrm{\neg }B$.
• Dimostrazione per contrapposizione: per dimostrare che $A\to B$, si dimostra la proposizione contrapposta che è $\mathrm{\neg }B\to \mathrm{\neg }A$.

Esempi

Sia $x$ un numero intero per dimostrare che se $x^2$ è pari, allora anche $x$ è pari.

Sebbene possa essere data una dimostrazione diretta, qui si sceglie di dimostrarlo per contrapposizione. La contrapposta della proposizione precedente è:

Se $x$ non è pari, allora $x^2$ non è pari

e, poiché gli unici numeri interi non pari sono quelli dispari, tale proposizione equivale a:

Se $x$ è dispari, allora $x^2$è dispari

L'ultima proposizione può essere provata come segue: se $x$ è dispari, esso è del tipo $2n+1$ per qualche $n\in \mathbb{Z}$ e, sfruttando la formula del quadrato del binomio e un raccoglimento parziale, troviamo:

$x^2=(2n+1{)}^2=4n^2+4n+1=2(2n^2+2)+1$

da cui segue che $x^2$ è dispari, come volevamo.

Avendo usato la contrapposta, possiamo inferire che la proposizione originale è vera.

Voci correlate

• Contrapposizione
• Modus tollens
• Reductio ad absurdum