Matematica · 1ª superiore

Logica e dimostrazioni: spiegazione, formule ed esempio svolto

Qui trovi la spiegazione, le formule che servono e un esempio svolto. Quando hai capito, fai un esercizio vero con il tutor di Atlante: ti fa la domanda giusta finché ci arrivi tu, e se sbagli ti dice dove, non cosa scrivere.

Fai un esercizio di logica e dimostrazioni con il tutor Gratis, senza registrarti. Il tutor non ti dà la risposta: ti ci porta.

Da dove si parte

Elementi di logica

Sotto ogni discorso matematico c'è una struttura invisibile: il modo in cui le affermazioni si legano e si negano. La logica è questa impalcatura. Impararla significa capire non solo cosa è vero, ma come si costruisce la verità.

Il mattone di base è la proposizione: una frase di cui ha senso dire se è vera o falsa, senza vie di mezzo. " $7$ è primo" è una proposizione (vera); " $5>9$ " lo è (falsa); ma "che ore sono?" o "questo numero è bello" non lo sono, perché non hanno un valore di verità oggettivo. Ogni proposizione porta con sé un solo bit: vero o falso.

Le proposizioni si combinano con i connettivi logici, e ognuno rispecchia un'operazione tra insiemi vista prima. La negazione $\neg p$ ribalta il valore di verità. La congiunzione $p\land q$ ("e") è vera solo se lo sono entrambe. La disgiunzione $p\lor q$ ("o") è vera se almeno una lo è. L'implicazione $p\Rightarrow q$ ("se... allora") promette che, quando $p$ è vera, lo è anche $q$ ; è falsa solo nel caso in cui $p$ è vera ma $q$ è falsa. Questo è il connettivo più insidioso: quando l'ipotesi $p$ è falsa, l'implicazione è considerata vera comunque, perché nessuna promessa è stata tradita.

Infine i quantificatori ci fanno parlare di interi universi. Il quantificatore universale $\forall$ significa "per ogni": $\forall x\in\mathbb{R},\ x^2\ge 0$ dice che il quadrato di ogni numero reale è non negativo. Il quantificatore esistenziale $\exists$ significa "esiste almeno un": $\exists x\in\mathbb{Z},\ x+1=0$ afferma che tra gli interi c'è un numero con quella proprietà (è $x=-1$ ). Attenzione: l'insieme in cui varia $x$ è decisivo, perché la stessa formula $\exists x,\ x+1=0$ è vera in $\mathbb{Z}$ ma falsa in $\mathbb{N}$ . Dire "per ogni" o "esiste" cambia radicalmente il significato di un'affermazione.

E qui De Morgan ritorna, in veste logica e più potente: negare "per ogni" dà "esiste un contro-esempio", negare "esiste" dà "per ogni... non". In simboli $\neg(\forall x\,P(x))\iff \exists x\,\neg P(x)$ . È esattamente ciò che fai quando smentisci un'affermazione universale trovando un solo caso che la rompe: la negazione scambia $\forall$ con $\exists$ , come scambiava $\cup$ con $\cap$ .

Le formule che servono

Righe della tavola di verità

n\ \text{proposizioni}\ \Rightarrow\ 2^n\ \text{righe}

Tautologia e contraddizione

p\lor\neg p\ \text{tautologia},\qquad p\land\neg p\ \text{contraddizione}

Negazione di una tautologia

A\ \text{tautologia}\ \Longleftrightarrow\ \neg A\ \text{contraddizione}

Equivalenza logica

A\equiv B\ \text{se e solo se}\ A\Leftrightarrow B\ \text{è una tautologia}

Doppia negazione

\neg\neg p\equiv p

De Morgan (congiunzione)

\neg(p\land q)\equiv\neg p\lor\neg q

De Morgan (disgiunzione)

\neg(p\lor q)\equiv\neg p\land\neg q

Implicazione come disgiunzione

p\Rightarrow q\equiv\neg p\lor q

Negazione dell'implicazione

\neg(p\Rightarrow q)\equiv p\land\neg q

Esportazione

p\Rightarrow(q\Rightarrow r)\equiv(p\land q)\Rightarrow r

Proprietà distributive

p\land(q\lor r)\equiv(p\land q)\lor(p\land r),\qquad p\lor(q\land r)\equiv(p\lor q)\land(p\lor r)

Connettivi e operazioni fra insiemi

\land\ \leftrightarrow\ \cap,\qquad\lor\ \leftrightarrow\ \cup,\qquad\neg\ \leftrightarrow\ \overline{\phantom{A}}

Implicazione, forma equivalente

P\Rightarrow Q\ \equiv\ \neg P\lor Q

Contronominale

(P\Rightarrow Q)\iff(\neg Q\Rightarrow\neg P)\quad\text{(contronominale: equivalente)}

Inversa

Q\Rightarrow P\quad\text{(inversa: NON equivalente)}

Contraria

\neg P\Rightarrow\neg Q\quad\text{(contraria: NON equivalente)}

Quando un'implicazione è falsa

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

Doppia implicazione

(P\iff Q)\iff\big[(P\Rightarrow Q)\land(Q\Rightarrow P)\big]

Condizione necessaria e sufficiente

P\Rightarrow Q:\quad P\ \text{sufficiente per}\ Q,\quad Q\ \text{necessaria per}\ P

Quantificatori

\forall x\in D,\ P(x)\qquad \exists x\in D:\ P(x)\qquad \exists!\,x\in D:\ P(x)

Negazione del «per ogni»

\neg\big(\forall x\,P(x)\big)\iff \exists x\,\neg P(x)

Negazione dell'«esiste»

\neg\big(\exists x\,P(x)\big)\iff \forall x\,\neg P(x)

Negazione di «per ogni… esiste»

\neg\big(\forall x\,\exists y\,P(x,y)\big)\iff \exists x\,\forall y\,\neg P(x,y)

Negazione di «esiste… per ogni»

\neg\big(\exists x\,\forall y\,P(x,y)\big)\iff \forall x\,\exists y\,\neg P(x,y)

Quantificatori uguali si scambiano

\forall x\,\forall y\,P\iff \forall y\,\forall x\,P\qquad \exists x\,\exists y\,P\iff \exists y\,\exists x\,P

Quantificatori diversi non si scambiano

\forall x\,\exists y\,P(x,y)\ \;\text{non equivale a}\;\ \exists y\,\forall x\,P(x,y)

Negazione di una disuguaglianza

\neg(a<b)\iff a\ge b\qquad \neg(a=b)\iff a\neq b

Che cosa vuol dire dimostrare

\text{Dimostrare } P\Rightarrow Q:\ \text{escludere } P\ \text{vera con } Q\ \text{falsa}

Dimostrazione diretta

\text{Diretta: } P\Rightarrow\cdots\Rightarrow Q

Dimostrazione per casi

\text{Per casi: } P_1\lor P_2\ \text{copre tutto},\ P_1\Rightarrow Q\ \text{e}\ P_2\Rightarrow Q

Dimostrazione per contronominale

\text{Contronominale: } \neg Q\Rightarrow\cdots\Rightarrow\neg P

Dimostrazione per assurdo

\text{Assurdo: } P\land\neg Q\Rightarrow\cdots\Rightarrow R\land\neg R

Controesempio

\text{Controesempio: un solo } x_0\ \text{con } P(x_0)\ \text{vera e } Q(x_0)\ \text{falsa}

Pari e dispari

\text{pari: } n=2k\qquad\text{dispari: } n=2k+1

Gli esempi non bastano

n^2+n+41\ \text{primo per } n\le 39;\quad 40^2+40+41=41^2

Un esempio svolto

Esercizio Negare l'affermazione: "tutti gli studenti hanno superato l'esame".

L'affermazione ha forma $\forall x\,P(x)$ , con $P(x)$ = " $x$ ha superato". La sua negazione non è "nessuno ha superato", errore comune: è "esiste almeno uno studente che non ha superato", cioè $\exists x\,\neg P(x)$ .

Risultato La negazione corretta è "c'è almeno uno studente bocciato". Per smentire un "per ogni" basta un solo contro-esempio: $\forall$ si nega con $\exists$ .

Nell’app l’esempio lo svolgi tu: il tutor controlla ogni passo e, se sbagli, ti dice dove.

Gli errori tipici

Trattare come proposizioni frasi senza valore di verità (domande, opinioni, definizioni).
Compilare a occhio la colonna finale saltando le colonne delle sottoformule: è così che si perdono righe e si sbagliano le parentesi.
Confondere un'implicazione con la sua inversa: da «se P allora Q» dedurre «se Q allora P». Le due colonne della tabella differiscono proprio nelle righe in cui P e Q hanno valori diversi, quindi l'inversa è un enunciato nuovo e va dimostrata a parte.
Negare «per ogni $x$ vale $P$ » con «per ogni $x$ vale $\neg P$ »: la negazione di «tutti» è «almeno uno no», non «nessuno».
Annunciare «dimostro per contronominale» e poi partire lo stesso da $P$ : la contronominale si dimostra assumendo $\neg Q$ e arrivando a $\neg P$ . Se non riscrivi ipotesi e tesi prima di cominciare, quasi sempre finisci a dimostrare l'inversa $Q\Rightarrow P$ , che è un altro enunciato.
Credere che $p\Rightarrow q$ sia falsa quando $p$ è falsa: da un'ipotesi falsa l'implicazione resta vera.
Confondere «soddisfacibile» con «tautologia»: una riga vera dice solo che la formula può essere vera, per la tautologia servono tutte le righe.
Credere che P => Q sia falsa quando l'ipotesi P è falsa: le due righe con P falsa danno implicazione vera, ed è il motivo per cui un enunciato la cui ipotesi non si realizza mai risulta vero a vuoto.

Come lo insegna Atlante

Nell’app la teoria di logica e dimostrazioni è divisa in 5 sezioni, con un grafico interattivo da muovere. Ogni passaggio si può chiedere al tutor, che spiega il perché prima del come.

Elementi di logicaUna proposizione è un'affermazione o vera o falsa; i connettivi ( $\neg,\land,\lor,\Rightarrow$ ) la compongono e i quantificatori ( $\forall,\exists$ ) dicono "per ogni" ed "esiste". È la grammatica con cui la matematica ragiona.
Tabelle di verità e tautologieGuardi una formula come $\neg(p\land q)\lor r$ e ti chiedi se è vera. La domanda, così com'è, non ha risposta: dipende da $p$ , da $q$ e da $r$ . L'unica domanda sensata è un'altra: in quali casi è vera e in quali è falsa? La tabella di verità nasce per rispondere a questa, ed è una macchina onesta: non capisce niente di quello che stai dicendo, prova tutti i casi possibili e decide.
L'implicazione: inversa, contraria, contronominaleTi chiedono di dimostrare che, per ogni naturale $n$ , se $3n+2$ è dispari allora $n$ è dispari. Parti dall'ipotesi, scrivi $3n+2=2k+1$ , isoli $3n=2k-1$ e resti con una frazione da cui non sai ricavare niente su $n$ : sull'ipotesi non hai presa. Poi qualcuno ti fa notare che dimostrare «se $n$ è pari allora $3n+2$ è pari» costa due righe, e che è la stessa identica affermazione. Capire perché sia lecito girare un'implicazione, e in quale modo esatto girarla, è il contenuto di questa sezione.
Quantificatori: per ogni, esiste, e come si negano«I numeri pari sono somma di due dispari.» Vera o falsa? La domanda è mal posta, perché la frase non dice se sta parlando di tutti i pari o solo di qualcuno: nel primo caso è un teorema, nel secondo è un'osservazione da mezza riga. Finché non dichiari quanti oggetti stai chiamando in causa, non hai ancora affermato niente. I quantificatori servono esattamente a questo, e la maggior parte degli enunciati che incontrerai alle superiori — definizione di limite compresa — non è altro che una catena di quantificatori.
Come si dimostra: diretta, contronominale, assurdo, controesempioAlle superiori la richiesta cambia: non ti si chiede più se una formula funziona sui numeri che hai provato, ma di far vedere che vale sempre. E "sempre" quasi sempre significa su infiniti casi, che non puoi controllare uno per uno. Servono quindi delle mosse che sostituiscono la verifica con il ragionamento: sono poche, si riconoscono a occhio, e ognuna è una forma logica che hai già incontrato nelle sezioni precedenti.

Argomenti collegati

Prima di questo

Mat 1ªInsiemi e relazioni

Dopo, prosegui con

Mat 1ªGeometria dei triangoli Mat 3ªSuccessioni e progressioni

Stesso anno

Mat 1ªNumeri naturali e interi Mat 1ªNumeri razionali Mat 1ªMonomi e polinomi Mat 1ªScomposizione e frazioni algebriche

Tutti i 70 argomenti di matematica e fisica →

Ora prova tu.

Un esercizio vero di logica e dimostrazioni, corretto un passo alla volta.

Fai un esercizio di logica e dimostrazioni con il tutor Gratis, senza registrarti. Il tutor non ti dà la risposta: ti ci porta.