Dimostrazione per contrapposizione
# Dimostrazione per contrapposizione

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 | $\lnot$p | $\lnot$q | p → q | $\lnot$q → $\lnot$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 $\neg A$ sia vera. Si dimostra che $\neg A\to B$ è falsa, deducendo quindi che $\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 \neg B$.
* Dimostrazione per contrapposizione: per dimostrare che $A\to B$, si dimostra la proposizione contrapposta che è $\neg B\to \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{\textstyle$ 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.

