Regole di deduzione
Obiettivo (corso Analisi Matematica 1)
- Regole di deduzione
- Strategie dimostrative
- Modus ponens (ragionamento diretto)
- Dimostrazione per assurdo (due versioni)
- Irrazionalità di $\sqrt{2}$
Regole di deduzione
Dimostrare un teorema
Dedurre nuove affermazioni vere a partire da altre affermazioni
Esempio (sillogismo)
Dall'ipotesi $$P=\text{Socrate è un uomo}$$ e dal teorema $$P \implies Q=\text{l'uomo è mortale}$$ segue (allora) la tesi $$Q=\text{Socrate è mortale}$$
Dimostrare il teorema significa dimostrare la verità dell'implicazione $P \implies Q$
Strategie dimostrative
- Modus ponens (ragionamento diretto)
- Dimostrazione per assurdo (due versioni)
Modus ponens (ragionamento diretto)
Definizione
Se $P$ è vera e si vuole provare che $Q$ è vera, si deve dimostrare che $P \implies Q$ è vera
Dimostrazione
Da $P$ e $P\implies Q$ si deduce $Q$ ovvero $$P \land (P\implies Q) \implies Q$$
La tabella di verità è:
| $P$ | $Q$ | $P \implies Q$ | $P \land (P \implies Q)$ | $P \land (P\implies Q) \implies Q$ |
|---|---|---|---|---|
| $V$ | $V$ | $V$ | $V$ | $V$ |
| $V$ | $F$ | $F$ | $F$ | $V$ |
| $F$ | $V$ | $V$ | $F$ | $V$ |
| $F$ | $F$ | $V$ | $F$ | $V$ |
Dimostrazione per assurdo
Dimostrazione per assurdo (versione 1)
Se $P$ è vera e si vuole provare che $Q$ è vera, si deve dimostrare che $\neg Q \implies \neg P$ è vera
Dimostrazione
$$\neg Q \implies \neg P \;\iff\; P \implies Q$$
Dimostrazione per assurdo
Dimostrazione per assurdo (versione 2)
Per dimostrare che $P \implies Q$ si assume $P$ vera e $Q$ falsa e si dimostra che $$P \land \neg Q \implies R \land \neg R$$ è vero (i.e $R \land \neg R$ è sempre falso, contraddizione) dove $R$ è una qualunque proposizione
Nota: Assumere contemporaneamente vere l'ipotesi e la negazione della tesi porta ad una contraddizione
Dimostrazione per assurdo
Dimostrazione
L'implicazione $P \land \neg Q \implies R \land \neg R$ (con tesi falsa) è vera se l'ipotesi è falsa, ovvero $P \land \neg Q$ è falsa
Tabella di verità: $P \implies Q$
| $P$ | $Q$ | $\quad P \implies Q\quad$ |
|---|---|---|
| $V$ | $V$ | $V$ |
| $V$ | $F$ | $F$ |
| $F$ | $V$ | $V$ |
| $F$ | $F$ | $V$ |
Dimostrazione
L'implicazione $P \land \neg Q \implies R \land \neg R$ (con tesi falsa) è vera se l'ipotesi è falsa, ovvero $P \land \neg Q$ è falsa
Il valore di verità di $\neg(P \land \neg Q)$ è lo stesso di $\neg P \lor Q$ (De Morgan)
Quindi, $P \land \neg Q$ è falsa se $\neg P \lor Q$ è vera
Il valore di verità di $\neg P \lor Q$ è lo stesso di $P \implies Q$ (equivalenza dell'implicazione)
Da $\neg P \lor Q$ vera segue che $P \implies Q$ è vera
Esempio: irrazionalità di $\sqrt{2}$
Non esiste alcun numero razionale $p=m/n$ (con $m$ e $n$ primi tra loro) il cui quadrato sia 2, i.e. $p^2=2$
Dimostrazione (per assurdo)
- Ipotesi: $P(m,n)$: $m,n$ interi positivi, primi tra loro tali che $p^2=2$ ($p=m/n$)
- Tesi: $Q(m,n)=p=\frac{m}{n}\ne 2$, i.e. $p$ non è razionale
Per assurdo (versione 2) con
- $P$ vera
- $Q$ falsa
i.e.
- $P(m,n)$ vera (primi tra loro), e
- $Q(m,n)$ falsa i.e. $\neg Q(m,n)$ vera, cioè $p$ è razionale
si arriva ad una contraddizione
Nel nostro caso sarà $R(m,n)$: "$m$, $n$ primi tra loro"
Essendo $p={m\over n}$ razionale, elevandolo al quadrato si ha $$2 = {m^2\over n^2}$$ ovvero $m^2 = 2 n^2$
Per un qualunque $n$, $m^2$ è pari, e quindi anche $m$ è pari (se $m$ fosse dispari sarebbe della forma $m=2h+1$ e $m^2=4h^2+4h+1$ sarebbe dispari)
Quindi posso scrivere $m = 2k$, con $k\in\mathbb{N}$, da cui $(2k)^2 = 2n^2$, i.e. $2k^2 = n^2$
Allo stesso modo confrontando $k$ con $n$ in $$2k^2 = n^2$$ deduco che $n$ è pari
Quindi ho dimostrato che $m$ e $n$ non sono primi tra loro ($\neg R$), arrivando ad un assurdo, e questo conclude la dimostrazione
Curiosità: il formato di carta ISO 216
- Il formato standard di carta ISO 216 (A0, A1, A2, A3, A4, ecc.) ha la proprietà
$$ \operatorname{Lato\;corto}:\operatorname{Lato\;lungo} = 1: \sqrt{2} $$
- Questa rapporto permette di mantere la proporzione se tagliato a metà lungo il lato più lungo (${\sqrt{2}\over 2}={1\over \sqrt{2}}$) perché
$$ {\operatorname{Nuovo\;lato\;corto}\over \operatorname{Nuovo\;lato\;lungo}} = {{1\over \sqrt{2}}\over 1} = {1\over \sqrt{2}} $$
Dimostriamo che $\sqrt{2}$ è quella che garantisce questa suddivisione
Da
$$ \operatorname{Nuovo\;lato\;corto}:\operatorname{Nuova\;lato\;lungo} = \operatorname{Lato\;corto}:\operatorname{Lato\;lungo} $$
indichiamo con $x=\operatorname{Lato\;lungo}$ e quindi sarà ${x\over 2}=\operatorname{Nuovo\;lato\;corto}$
da cui
$$ {x\over 2} : 1 = 1 :x \;\implies\; x= \sqrt{2} $$
Ricorda di sostenere questo progetto con una donazione (PayPal.Me/ManoloVenturin).