Regole fondamentali usate nelle dimostrazioni

Quando si fa una dimostrazione, di un teorema, o in generale di una proposizione che si vuole far vedere essere vera, bisogna procedere seguendo delle regole ben precise, dette regole di deduzione.



In una dimostrazione si parte da un'ipotesi, cioè una o più proposizioni che vengono assunte come vere e si giunge ad una tesi, cioè una proposizione che non potrà che essere vera ogni volta che è vera l'ipotesi. In generale, nulla si può dire sulla tesi quando l'ipotesi non risulta vera.

Dunque, diciamo A l'ipotesi e B la tesi.

Deduzione diretta.
E'il metodo di dimostrazione fondamentale, il cui schema è il seguente:

Se, A e se da A segue B, allora B.

In simboli logici:

$$[A \land (A \implies B) ] \implies B$$

La precedente è una tautologia, dunque rappresenta uno schema di ragionamento corretto, indipendentemente dalla verità o falsità delle proposizioni A e B.

Tuttavia interessa dimostrare la verità di B, che si ottiene soltanto quando la proposizione A è vera e la proposizione $A \implies B$ è vera.

Esercizio: si verifichi la tautologia $[A \land (A \implies B) ] \implies B$
Si può procedere scrivendo la tavola delle verità, oppure, ricordando che $(A \implies B)\equiv\lnot A\lor B$, in maniera analitica la si può ridurre nel seguente modo:
$$[A \land (A \implies B) ] \implies B \\  [A \land (\lnot A \lor B) ] \implies B \\  [(A \land \lnot A) \lor (A \land B)] \implies B \\  (A \land B) \implies B \\  \lnot(A \land B) \lor B \\  \lnot A \lor \lnot B \lor B$$
Che per il principio del terzo escluso è sempre vera, contenendo contemporaneamente B e la sua negazione.


Deduzione per assurdo.
Un altro schema molto usato è il seguente:

Se, A e se da non B segue non A, allora B.

In simboli logici:

$$[ A \land (\lnot B \implies \lnot A) ] \implies B$$

 Anche la precedente è una tautologia, che si riduce a quella della deduzione  diretta non appena si osserva che $(\lnot B \implies \lnot A) \equiv (A \implies B)$.

Deduzione per induzione.

Esiste anche quest'altro schema, che non riporto qui perché riguarda un infinità numerabile di proposizioni. Lascio a voi approfondire.