Logica: proposizioni, predicati e quantificatori (da zero)

La matematica è fatta di affermazioni e di ragionamenti che collegano un'affermazione all'altra. La logica è la "grammatica" di questi ragionamenti: ci dice come si scrivono le affermazioni con i simboli, quando sono vere e come si negano. È il primo argomento del corso perché tutto il resto (insiemi, sup e inf, limiti…) si scrive con questo linguaggio.

Collegamenti: Operazioni tra insiemiUnione, intersezione, differenza, complementare e prodotto cartesiano, con le leggi di De Morgan e il legame con la logica.Operazioni tra insiemi → (le operazioni sugli insiemi sono la logica "vista con gli insiemi"), Tecniche di dimostrazioneDimostrazione diretta, per contronominale e per assurdo di un teorema del tipo ipotesi implica tesi.Tecniche di dimostrazione → (come si usa la logica per dimostrare).

Proposizioni

Una proposizione è un'affermazione che è vera (V) oppure falsa (F), senza vie di mezzo. Si indicano con lettere come $p$, $q$.

La terza riga è importante: un'affermazione che contiene una variabile libera non è né vera né falsa finché non si sa quanto vale la variabile. Queste affermazioni si chiamano predicati (vedi sotto).

Connettivi logici

Da proposizioni semplici se ne costruiscono di più complicate con i connettivi.

Attenzione all'"o". In matematica "$p \vee q$" è vera anche quando sono vere tutte e due. Non è l'"o" esclusivo del linguaggio comune ("o mangi la minestra o salti dalla finestra").

Attenzione all'implicazione. $p \Rightarrow q$ dice solo: "se $p$ è vera, allora $q$ è vera". Non dice nulla su cosa succede quando $p$ è falsa. Esempio: "se piove, prendo l'ombrello". Se non piove, la frase non viene smentita qualunque cosa io faccia. Per questo $p \Rightarrow q$ è falsa solo nel caso "$p$ vera e $q$ falsa".

Tabella di verità completa (V = vera, F = falsa):

Implicazione e doppia implicazione. $p \Leftrightarrow q$ significa che valgono sia $p \Rightarrow q$ sia $q \Rightarrow p$. Per dimostrare un "se e solo se" si dimostrano quindi due implicazioni (le due "frecce").

Predicati

Un predicato $p(x)$ è un'affermazione che contiene una variabile $x$ presa da un insieme $X$, e che diventa una proposizione (V o F) non appena si sceglie un valore di $x \in X$.

Esempio. $X = \mathbb{R}$ e $p(x)$: "$x^2 \le 4$".

• per $x = 1$: $1 \le 4$, quindi $p(1)$ è V;
• per $x = 3$: $9 \le 4$, quindi $p(3)$ è F;
• per $x = -2$: $4 \le 4$, quindi $p(-2)$ è V.

Due predicati possono essere equivalenti, cioè veri esattamente per gli stessi $x$. Per esempio

$$p(x): \ x^2 \le 4 \qquad \Longleftrightarrow \qquad q(x): \ -2 \le x \le 2$$

(un numero ha quadrato al più $4$ esattamente quando sta tra $-2$ e $2$; la verifica si fa come nelle disequazioni di secondo grado: $x^2 - 4 \le 0 \iff (x-2)(x+2) \le 0$, valori interni alle radici).

Quantificatori

Un predicato da solo non è né vero né falso. Diventa una proposizione anche se, invece di scegliere un valore di $x$, si dice per quanti $x$ deve valere. Si usano i quantificatori:

Nelle formule i due punti "$:$" si leggono "si ha", "tale che".

Regola d'oro: quantificatore + predicato = proposizione.

Esempio 1: "$\forall x \in \mathbb{R} : x^2 > 0$"

Si legge "per ogni numero reale $x$ si ha $x^2 > 0$". È falsa: basta un solo controesempio, $x = 0$, perché $0^2 = 0$ non è $> 0$.

Per smentire un "per ogni" basta un controesempio. Per dimostrarlo, invece, non bastano mille esempi: serve un ragionamento che valga per ogni $x$.

Esempio 2: "$\exists x \in \mathbb{R} : x^2 \le 0$"

"Esiste un reale con quadrato $\le 0$". È vera: $x = 0$ va bene ($0 \le 0$). Per dimostrare un "esiste" basta esibire un esempio.

Esempio 3: "$\exists x \in \mathbb{R} : \exists\, x^{-1}$"

"Esiste un reale che ha l'inverso" ($x^{-1} = \frac{1}{x}$). È vera: per esempio $x = 2$ ha inverso $\frac{1}{2}$.

L'ordine dei quantificatori conta

• "$\forall x \in \mathbb{R}\ \exists y \in \mathbb{R} : y > x$" ("per ogni numero ce n'è uno più grande") è vera: dato $x$, prendo $y = x + 1$. Qui $y$ può dipendere da $x$.
• "$\exists y \in \mathbb{R}\ \forall x \in \mathbb{R} : y > x$" ("c'è un numero più grande di tutti") è falsa: nessun $y$ è più grande di $y + 1$.

Scambiando i quantificatori si è cambiato completamente il significato. Questo tornerà nelle definizioni di sup, inf e limite ("per ogni $\varepsilon > 0$ esiste…": l'oggetto che "esiste" può dipendere da $\varepsilon$).

Come si nega una proposizione con i quantificatori

È l'abilità logica più usata del corso (serve nelle dimostrazioni per assurdo e per capire quando una definizione non è soddisfatta).

$$\text{non}\big(\forall x \in X : p(x)\big) \quad = \quad \exists x \in X : \text{non}\, p(x)$$

$$\text{non}\big(\exists x \in X : q(x)\big) \quad = \quad \forall x \in X : \text{non}\, q(x)$$

In parole: la negazione scambia $\forall$ con $\exists$ e nega il predicato.

Perché. "Non è vero che tutti gli studenti hanno passato l'esame" significa "almeno uno non l'ha passato" (non significa "nessuno l'ha passato"!). E "non è vero che esiste uno studente che ha preso 30" significa "ogni studente non ha preso 30".

Gli esempi di prima, negati:

Si noti che la negazione di "$x^2 > 0$" è "$x^2 \le 0$", non "$x^2 < 0$": il contrario di "maggiore" è "minore o uguale".

Come controllo, una proposizione e la sua negazione hanno sempre valori opposti (una V e l'altra F), come nella tabella.

Con più quantificatori si applica la regola un pezzo alla volta, da sinistra a destra:

$$\text{non}\big(\forall x\ \exists y : p(x,y)\big) = \exists x\ \forall y : \text{non}\, p(x,y)$$

Negare "e" e "o" (leggi di De Morgan logiche)

$$\text{non}\,(p \vee q) = (\text{non}\,p) \wedge (\text{non}\,q) \qquad \text{non}\,(p \wedge q) = (\text{non}\,p) \vee (\text{non}\,q)$$

"Non è vero che (piove o nevica)" = "non piove e non nevica". "Non è vero che (sono alto e biondo)" = "non sono alto oppure non sono biondo". Negando, la "e" diventa "o" e viceversa. La prof le ricava dalle leggi di De Morgan sugli insiemi: vedi Operazioni tra insiemiUnione, intersezione, differenza, complementare e prodotto cartesiano, con le leggi di De Morgan e il legame con la logica.Operazioni tra insiemi →.

Negare un'implicazione

$p \Rightarrow q$ è falsa solo quando $p$ è vera e $q$ è falsa (tabella di verità), quindi

$$\text{non}\,(p \Rightarrow q) = p \wedge \text{non}\,q$$

È esattamente ciò che si suppone in una dimostrazione per assurdo (vedi Tecniche di dimostrazioneDimostrazione diretta, per contronominale e per assurdo di un teorema del tipo ipotesi implica tesi.Tecniche di dimostrazione →).

Ipotesi e tesi

Un teorema è quasi sempre un'implicazione $p \Rightarrow q$:

• $p$ si chiama ipotesi (ciò che si suppone vero);
• $q$ si chiama tesi (ciò che si vuole dimostrare).

Dimostrare il teorema significa mostrare, con passaggi logici corretti, che l'implicazione $p \Rightarrow q$ è vera. Le varie strategie sono in Tecniche di dimostrazioneDimostrazione diretta, per contronominale e per assurdo di un teorema del tipo ipotesi implica tesi.Tecniche di dimostrazione →.

Errori comuni

• Negare "per ogni" con "per nessuno". La negazione di "tutti i numeri sono positivi" è "almeno un numero non è positivo", non "nessun numero è positivo".
• Negare $>$ con $<$. Il contrario di $a > b$ è $a \le b$.
• Dimostrare un "per ogni" con degli esempi. Gli esempi aiutano a capire, ma non dimostrano (servono per smentire, non per confermare).
• Scambiare l'ordine dei quantificatori pensando che non cambi niente.
• Leggere $p \Rightarrow q$ come $q \Rightarrow p$. "Se $n$ è multiplo di $4$ allora è pari" è vera; "se $n$ è pari allora è multiplo di $4$" è falsa ($n = 2$).

Riassunto