Quando conviene usare la dimostrazione per assurdo?

È una buona scelta quando l'enunciato afferma che qualcosa non esiste (nessun numero più grande di tutti, nessuna frazione uguale a $\sqrt{2}$) o che esistono infiniti oggetti di un certo tipo. In questi casi, supporre il contrario ti dà un oggetto concreto con cui lavorare.

La dimostrazione per assurdo è la stessa cosa della dimostrazione per contronominale?

No. La dimostrazione per contronominale prova direttamente "se non q, allora non p" e finisce con "non p". La dimostrazione per assurdo suppone che l'enunciato sia falso e può finire con una qualsiasi impossibilità. Ogni dimostrazione per contronominale si può riscrivere come dimostrazione per assurdo, ma non ogni dimostrazione per assurdo è una dimostrazione per contronominale.

Che cosa significa c.v.d. e che cos'è la "reductio ad absurdum"?

c.v.d. ("come volevasi dimostrare", in latino quod erat demonstrandum) segna la fine di una dimostrazione. Reductio ad absurdum, "riduzione all'assurdo", è il nome latino della dimostrazione per assurdo.

Risorse per insegnanti

Dimostrazione per assurdo

Impara a dimostrare un enunciato supponendo che sia falso e mostrando che questo porta a qualcosa di impossibile, con dimostrazioni classiche come l'irrazionalità della radice quadrata di 2.

Avanzato30 minLezione

Scheda da stampare

Definizione

Una dimostrazione per assurdo (detta anche dimostrazione indiretta) dimostra un enunciato

P

con un giro largo: supponi che

P

sia falso e mostri che questa ipotesi porta a qualcosa di impossibile. Poiché un ragionamento corretto non può mai ricavare un'impossibilità da un'ipotesi vera, l'ipotesi deve essere sbagliata, quindi

P

è vero.

Il metodo ha quattro passi:

1.Supporre la negazione: la prima riga è "Supponiamo per assurdo che $\neg P$ ."
2.Ragionare con definizioni e fatti noti, esattamente come in una dimostrazione diretta.
3.Arrivare a una contraddizione: un enunciato $Q$ e il suo contrario $\neg Q$ valgono entrambi (per esempio " $a/b$ è ridotta ai minimi termini" e " $a$ e $b$ sono entrambi pari"), oppure si viola un fatto noto (come $1 = 0$ ).
4.Concludere: l'ipotesi $\neg P$ era falsa, quindi $P$ è vero.

In simboli: se

\neg P \Rightarrow (Q \land \neg Q)

, allora

P

. Funziona perché

Q \land \neg Q

è sempre falso. Nella tavola di verità interattiva più in basso in questa pagina scegli NOT per vedere che

\neg P

è sempre il contrario di

P

, poi scegli AND: nelle due righe in cui

Q

è il contrario di

P

(F, V e V, F),

P \land Q

vale F. Quindi

P \land \neg P

vale F in ogni riga (V = vero, F = falso).

Scrivere bene la negazione è la riga più importante della dimostrazione:

" $\sqrt{2}$ è irrazionale" diventa " $\sqrt{2}$ è razionale"
"Esistono infiniti numeri primi" diventa "Esiste solo un numero finito di numeri primi"
"Non esiste un numero pari più grande di tutti" diventa "Esiste un numero pari più grande di tutti"
" $x > 5$ " diventa " $x \le 5$ "
"Ogni ... ha la proprietà" diventa "Almeno un ... non ha la proprietà"

Assurdo o contronominale? Una dimostrazione per contronominale (lezione precedente) prova "se

p

, allora

q

" supponendo solo

\neg q

e puntando a un unico obiettivo fisso:

\neg p

. Una dimostrazione per assurdo suppone che tutto l'enunciato sia falso (per un enunciato "se ... allora":

p

\neg q

insieme) e può finire con una qualsiasi impossibilità.

Prova subito

Vuoi dimostrare per assurdo che

\sqrt{3}

è irrazionale. Qual è la prima riga corretta?

Esempi svolti

Dimostra che non esiste un numero pari più grande di tutti gli altri.

Scrivi la negazione come prima riga

Supponiamo per assurdo che esista un numero pari più grande di tutti, $N$ → Ipotesi: $N$ è pari e $N \ge$ ogni numero pari

Usa la definizione di pari

$N = 2k$ per un intero $k$ , quindi $N + 2 = 2k + 2 = 2(k + 1)$ → $N + 2$ è pari

Confronta i due numeri

$N + 2 > N$ → Esiste un numero pari più grande di $N$

Individua la contraddizione e concludi

$N$ è il numero pari più grande, eppure $N + 2$ è un numero pari più grande → L'ipotesi è falsa

Risposta: L'ipotesi porta a una contraddizione, quindi non esiste un numero pari più grande di tutti. c.v.d.

Errori comuni

Negare "Esistono infiniti numeri primi" con "Non esistono numeri primi"

Perché è sbagliato: Il contrario di "infiniti" non è "nessuno". La negazione deve coprire tutti i casi in cui l'enunciato è falso, cioè "solo un numero finito".

Corretto: Supponi "Esiste solo un numero finito di numeri primi". Allo stesso modo, la negazione di "ogni primo è dispari" è "almeno un primo non è dispari", non "ogni primo è pari".

Negare $x > 5$ con $x < 5$

Perché è sbagliato: Si dimentica il caso $x = 5$ . Se la dimostrazione esclude solo $x < 5$ , il numero $5$ resta possibile.

Corretto: La negazione di $x > 5$ è $x \le 5$ , e la negazione di $x \ge 5$ è $x < 5$ .

Dimenticare "ai minimi termini" nella dimostrazione che $\sqrt{2}$ è irrazionale

Perché è sbagliato: Senza questa condizione, scoprire che $a$ e $b$ sono entrambi pari non è affatto una contraddizione: $\frac{4}{2}$ ha numeratore e denominatore pari.

Corretto: Scrivi $\sqrt{2} = \frac{a}{b}$ ridotta ai minimi termini. Ogni frazione si può semplificare, quindi non costa nulla, ed è proprio il fatto che la dimostrazione poi contraddice.

Chiamare contraddizione un risultato sorprendente

Perché è sbagliato: Un risultato che sembra strano (un numero molto grande, una frazione inattesa) non è impossibile. Una contraddizione deve scontrarsi con l'ipotesi o con un fatto noto.

Corretto: Indica i due enunciati che si scontrano, per esempio " $r$ è il più piccolo" e " $\frac{r}{2} < r$ ", e poi scrivi la conclusione.

Visuale interattivo

Tabella di verità

Seleziona operatore

P ∧ Q

P	Q	P ∧ Q
F	F	F
F	V	F
V	F	F
V	V	V

V= VeroF= Falso

Sandbox interattivo

Calcolatrice di espressioni

Prova questi:

Cronologia

Ancora nessun calcolo

Esercizi pratici

18 esercizi

Problema 1 di 18

Facile

Vuoi dimostrare per assurdo che $\sqrt{3}$ è irrazionale. Qual è la prima riga corretta?

Perché è importante

Alcuni dei risultati più famosi della matematica si dimostrano più comodamente per assurdo:

Numeri irrazionali: i Greci dimostrarono circa 2500 anni fa che $\sqrt{2}$ non è una frazione, e questo cambiò il modo di pensare ai numeri
Numeri primi: la dimostrazione di Euclide che i primi non finiscono mai è ancora usata in ogni corso di teoria dei numeri
Informatica: il principio dei cassetti spiega perché due file possono ricevere la stessa breve impronta (una collisione di hash) e perché nessuna compressione può ridurre tutti i file
Giochi di logica: risolvere un Sudoku spesso significa dire "se in questa casella ci fosse un 5, ci sarebbero due 5 nella stessa riga, quindi non è 5"
Ragionamento quotidiano: detective e medici escludono possibilità mostrando che portano a qualcosa di impossibile

Ogni volta che un enunciato afferma che qualcosa NON esiste (nessun numero più grande di tutti, nessuna frazione uguale a

\sqrt{2}

), la dimostrazione per assurdo è di solito lo strumento naturale.

Applicazioni nel mondo reale

Calzini dello stesso colore al buio

Il principio dei cassetti, dimostrato per assurdo, ti dice il numero minimo di oggetti che garantisce una ripetizione.

Esempio:

In un cassetto ci sono calzini neri, bianchi e grigi. Se potessi prendere 4 calzini tutti di colori diversi, ti servirebbero 4 colori, ma ce ne sono solo 3. Quindi 4 calzini contengono sempre una coppia dello stesso colore.

1Provaci tu stesso

In un cassetto ci sono calzini spaiati di 5 colori diversi ed è troppo buio per vederli.

Quanti calzini devi prendere per essere sicuro di averne due dello stesso colore?

Passo 1: Scrivi l'espressione matematica

Numero di colori più uno:

Collisioni di hash in informatica

I computer assegnano ai file codici brevi chiamati hash. Poiché i file possibili sono più dei codici, a volte due file diversi devono condividere lo stesso codice.

Esempio:

Un sistema assegna a ogni file un codice da 00 a 99. Con 101 file, supporre che tutti i codici siano diversi richiederebbe 101 codici, ma ce ne sono solo 100, quindi due file condividono un codice.

2Provaci tu stesso

Un sistema assegna a ogni file un codice di 3 cifre da 000 a 999.

Quanti file garantiscono che due di loro abbiano lo stesso codice?

Passo 1: Scrivi l'espressione matematica

Numero di codici più uno:

Perché la calcolatrice non mostra mai la radice di 2 esatta

Poiché $\sqrt{2}$ è irrazionale, la sua espansione decimale non finisce mai e non si ripete mai. Ogni decimale sullo schermo è solo un'approssimazione, e gli ingegneri devono tenerne conto quando calcolano le diagonali.

Esempio:

Una piastrella quadrata di lato 1 m ha una diagonale di $\sqrt{2} \approx 1{,}4142$ m. Il valore 1,4142 è vicino, ma non esatto.

3Provaci tu stesso

Una calcolatrice mostra $\sqrt{2} \approx 1{,}4142$ .

Verifica che 1,4142 non è esattamente la radice quadrata di 2.

Passo 1: Scrivi l'espressione matematica

Eleva il decimale al quadrato:

Punti chiave

1Una dimostrazione per assurdo suppone che l'enunciato sia falso e mostra che questo porta a qualcosa di impossibile
2La prima riga è la negazione corretta: "infiniti" diventa "solo un numero finito", $x > 5$ diventa $x \le 5$ , "ogni" diventa "almeno un ... non"
3Una contraddizione sono due enunciati che non possono essere veri insieme, come $Q \land \neg Q$ , che è falso in ogni riga di una tavola di verità
4Risultati classici dimostrati così: $\sqrt{2}$ è irrazionale, esistono infiniti primi, non esiste un numero pari più grande di tutti né un razionale positivo più piccolo di tutti
5Il principio dei cassetti: se più di $n$ oggetti vanno in $n$ cassetti, almeno un cassetto contiene due oggetti
6La dimostrazione per contronominale prova direttamente "se non q, allora non p", mentre la dimostrazione per assurdo suppone falso tutto l'enunciato e cerca una qualsiasi impossibilità

Domande frequenti

Un ragionamento corretto a partire da enunciati veri produce solo enunciati veri. Se arriviamo a qualcosa di impossibile, almeno un punto di partenza era falso, e l'unico punto di partenza che abbiamo aggiunto noi è l'ipotesi

\neg P

. Quindi

\neg P

è falso e

P

è vero.

Glossario

Dimostrazione per assurdo: Una dimostrazione che suppone falso l'enunciato e ne ricava un'impossibilità, per cui l'enunciato deve essere vero (detta anche dimostrazione indiretta)
Contraddizione: Due enunciati che non possono essere veri insieme, come $Q$ e $\neg Q$ ; l'enunciato $Q \land \neg Q$ è sempre falso
Negazione: Il contrario di un enunciato, scritto $\neg P$ ; è vera esattamente quando $P$ è falso
Numero irrazionale: Un numero reale che non si può scrivere come frazione $\frac{a}{b}$ di interi, per esempio $\sqrt{2}$
Principio dei cassetti: Se si mettono più di $n$ oggetti in $n$ cassetti, almeno un cassetto contiene due o più oggetti

Scheda formule

Dimostrazione per assurdo

\neg P \Rightarrow (Q \land \neg Q) \;\text{ quindi }\; P

Se supporre non P porta a una contraddizione, allora P è vero

Una contraddizione è sempre falsa

Q \land \neg Q = F

Un enunciato e la sua negazione non possono mai essere veri insieme

Principio dei cassetti

n + 1 \text{ oggetti in } n \text{ cassetti}

Almeno un cassetto riceve due o più oggetti

Altro su questo argomento

Definizione

Esempi svolti

Errori comuni

Visuale interattivo

Tabella di verità

Sandbox interattivo

Calcolatrice di espressioni

Cronologia

Esercizi pratici

Perché è importante

Applicazioni nel mondo reale

Calzini dello stesso colore al buio

Collisioni di hash in informatica

Perché la calcolatrice non mostra mai la radice di 2 esatta

Punti chiave

Domande frequenti

Glossario

Scheda formule

Dimostrazione per assurdo

Una contraddizione è sempre falsa

Principio dei cassetti

Altro su questo argomento

Introduzione alle dimostrazioni matematiche

Dimostrazione diretta

Dimostrazioni a due colonne

Dimostrazioni discorsive