La logica matematica e la teoria degli insiemi

La logica è un ambito della Matematica molto importante, che permette di studiare e schematizzare concetti ricorrenti e fondamentali come l’implicazione logica, la congiunzione e la disgiunzione di enunciati, e così via. In questa lezione daremo una introduzione di quella che viene chiamata logica classica, e mostreremo il legame che essa ha con la teoria degli insiemi.

Definizione

Si chiama proposizione o enunciato una frase per la quale si possa stabilire con certezza se è vera o falsa.
Un predicato è invece una proposizione che dipende da una variabile (o più variabili) appartenenti a un certo insieme $D$, detto dominio (o domini $D_1, D_2, \ldots$, nel caso di più variabili) del predicato.

Intuitivamente, possiamo dire che un predicato è una collezione di proposizioni che si possono esprimere secondo una “regola generale”.

Facciamo alcuni esempi:

• la frase “8 è un numero primo” è una proposizione (che in questo caso è certamente falsa); non è una proposizione, invece, una frase del tipo “I quadri di Picasso sono belli”.
• l’espressione $p(x): \quad x \text{ è un numero primo} \quad x \in \mathbb{N}$ è un predicato, che dipende dalla variabile $x \in D = \mathbb{N}$.
• l’espressione $p(x, y): \quad x \text{ è un multiplo di }y \quad x, y \in \mathbb{N}$ è un predicato, che dipende dalle variabili $x \in D_1 = \mathbb{N}, y \in D_2 = \mathbb{N}$.

Notazione: generalmente una proposizione viene indicata con una lettera minuscola dell’alfabeto latino ($p, q, \ldots$) e un predicato viene indicato con scritture del tipo $p(x), q(x), \ldots$ (che ricordano il modo di scrivere una funzione; in un certo senso, infatti, un predicato è una “funzione con valori nell’insieme delle proposizioni”).

Definizione

Dato un predicato $p(x)$ con dominio $D$, chiameremo insieme di verità di $p(x)$ l’insieme $P \subseteq D$ costituito dagli elementi di $D$ per cui $p(x)$ è vero.

Per esempio, il predicato $p(x): x \text{ è un divisore di } 12, x \in \mathbb{N}$ ha come insieme di verità l’insieme $P = \{ 1, 2, 3, 4, 6, 12\}$ che è un sottoinsieme proprio di $D = \mathbb{N}$.

Operazioni tra proposizioni e il loro legame con gli insiemi

In questo paragrafo vediamo alcune delle operazioni che si possono svolgere tra due o più proposizioni in logica, e vedremo come questa branca della Matematica sia strettamente legata con la teoria degli insiemi.

Definizione

Si dice negazione di una proposizione $p$ la proposizione che è vera quando $p$ è falsa, e falsa quando $p$ è vera.
La negazione di $p$ si scrive $\overline{p}$ e si legge “non $p$”.

Riassumiamo la definizione appena data utilizzando una tavola di verità, uno strumento che utilizzeremo anche in seguito. In essa vediamo come, a seconda del valore di verità di $p$ (dove con V intendiamo “vero” , e con F intendiamo “falso”), varia il valore di verità di $\overline{p}$:

Possiamo definire anche la negazione di un predicato $p(x)$ con dominio $D$, in questo senso: $\overline{p}(x)$ sarà il predicato negazione di $p(x)$ che - una volta fissato un $x_1 \in D$ - assumerà il valore “vero” o “falso” a seconda che la $\overline{p}(x_1)$ sia una proposizione vera o falsa, rispettivamente.

Se chiamiamo $P$ l'insieme di verità di $p(x)$, l'insieme di verità $R$ di $\overline{p}(x)$ risulta essere il complementare $\overline{P}$ di $P$ (considerando il dominio di $p(x)$ come insieme universo). Abbiamo quindi un parallelismo tra l’operazione di negazione tra predicati $\overline{\cdot}$ e il passaggio al complementare tra insiemi.

Per esempio, considerando il predicato $p(x): x \text{ è maggiore di }5, x \in \mathbb{N}$ con insieme di verità $P = \{6, 7, 8, \ldots \}$ allora abbiamo che l’insieme di verità $R$ di $\overline{p}(x)$ è dato da $R = \{1, 2, 3, 4, 5\} = \overline{P}$.

Definizione

Si definisce congiunzione di due proposizioni $p$ e $q$ la proposizione che è:

• vera se $p$ e $q$ sono contemporaneamente entrambe vere;
• falsa in ogni altro caso.
  
  

La congiunzione tra $p$ e $q$ si indica con la scrittura $p \wedge q$ e si legge “$p$ e $q$”.

Riassumiamo la definizione appena data utilizzando una tavola di verità, uno strumento che utilizzeremo anche in seguito. In essa vediamo come, a seconda dei valori di verità di $p$ e $q$ (dove con V intendiamo “vero” , e con F intendiamo “falso”), varia il valore di verità di $p \wedge q$: 

Possiamo pensare di effettuare l’operazione $\wedge$ anche tra due predicati $p(x), q(x)$ in maniera simile a quanto fatto prima. Inoltre, la somiglianza tra il simbolo $\wedge$ e il simbolo $\cap$ non è casuale: infatti, se $P, Q$ sono gli insiemi di verità di $p(x)$ e $q(x)$ rispettivamente, allora l’insieme di verità di $R$ di $p(x) \cap q(x)$ è uguale a $P \cap Q$. Abbiamo quindi un parallelismo tra la congiunzione tra predicati $\wedge$ e l’intersezione tra insiemi $\cap$.

Per capire meglio la situazione, prendiamo il seguente esempio:

$\begin{aligned}p(x) & : x \text{ è un multiplo di 3}, x \in \mathbb{N} \\q(x) & : x \text{ è un divisore di 12}, x \in \mathbb{N} \\p(x) \wedge q(x) & : x \text{ è un divisore di }12\text{, ed è un multiplo di }3, x \in \mathbb{N}\end{aligned}$

Allora $P = \{3, 6, 9, \ldots \}$ e $Q = \{1, 2, 3, 4, 6, 12\}$; inoltre l’insieme di verità di $p(x) \wedge q(x)$ è $R = \{3, 6, 12\}$ e vale $R = P \cap Q$.

Insomma affinché un predicato ottenuto dalla congiunzione di due predicati sia vero è necessario che la variabile $x$ soddisfi contemporaneamente (cioè renda contemporaneamente veri) entrambi i predicati di partenza.

Definizione

Si definisce disgiunzione di due proposizioni $p$ e $q$ la proposizione che è:

• falsa se $p$ e $q$ sono contemporaneamente entrambe false;
• vera in ogni altro caso.
  
  

La disgiunzione tra $p$ e $q$ si indica con la scrittura $p \vee q$ e si legge “$p$ o $q$”, o anche “$p$ vel $q$”.

Costruiamo la tavola di verità:

Possiamo estendere l’operazione di disgiunzione anche tra due predicati $p(x), q(x)$, con insiemi di verità $P, Q$ rispettivamente, in maniera simile a quanto fatto in precedenza per la disgiunzione. In questo caso, inoltre, l’insieme di verità del predicato disgiunzione $p(x) \vee q(x)$ è dato da $P \cup Q$. Abbiamo quindi un parallelismo tra l’operazione di disgiunzione tra predicati $\vee$ e l’unione tra insiemi $\cup$.

Continuando con l’esempio precedentemente introdotto: $p(x) \vee q(x) : x \text{ è un divisore di }12\text{, oppure è un multiplo di }3, x \in \mathbb{N}$ e dunque $R = \{1, 2, 3, 4, 6, 9, 12, \ldots \} = P \cup Q$.

Insomma affinché un predicato ottenuto dalla disgiunzione di due predicati sia vero è sufficiente che la variabile $x$ soddisfi (cioè renda vero) almeno uno dei predicati di partenza.

Definizione

Si definisce implicazione materiale, o più semplicemente implicazione di due proposizioni $p$ e $q$, la proposizione che è:

• falsa quando $q$ è falsa e $p$ è vera;
• vera in tutti gli altri casi.
  
  

L’implicazione materiale di $p$ e $q$ si indica con la scrittura $p \rightarrow q$ e si legge “se $p$ allora $q$”, o anche “$p$ implica $q$”.
In questo contesto, inoltre, la proposizione $p$ si chiama antecedente, mentre la $q$ si chiama conseguente.

Costruiamo la tavola di verità:

Osserviamo che l’unico caso in cui un predicato ottenuto dall’implicazione di due predicati può risultare falso è quello in cui esiste almeno una variabile $x \in D$ che rende vera l’antecendente e contemporaneamente rende falsa la conseguente.

Definizione

Data un’implicazione $a \rightarrow b$, si definiscono:

• l’implicazione contraria di $a \rightarrow b$, che è $\overline{a} \rightarrow \overline{b}$;
• l’implicazione inversa di $a \rightarrow b$, che è $b \rightarrow a$;
• l’implicazione contronominale di $a \rightarrow b$, che è $\overline{b} \rightarrow \overline{a}$.

È importante notare che se $a \rightarrow b$ è vera, allora anche la contronominale $\overline{b} \rightarrow \overline{a}$ lo è: nulla si può dire invece sull’inversa e sulla contraria.

Facciamo un esempio per chiarire la situazione. Dato una figura geometrica $T$, consideriamo le proposizioni $p=$”$T$ è un triangolo” e $q=$”$T$ è un poligono”, e l’implicazione $p \rightarrow q$ = “se $T$ è un triangolo, allora $T$ è un poligono”. La proposizione ottenuta è vera, ma vale quanto segue.

• La contraria $\overline{p} \rightarrow \overline{q}=$”se $T$ non è un triangolo, allora $T$ non è un poligono” non è necessariamente vera . Per esempio $T$ potrebbe essere un pentagono, che rende vera l’antecedente (infatti $T$ non è un triangolo) ma rende falsa la conseguente (infatti $T$ è un poligono).
• L’inversa $q \rightarrow p =$”se $T$ è un poligono, allora $T$ è un triangolo” non è necessariamente vera. Per esempio $T$ potrebbe essere un quadrilatero, cioè un poligono che non è un triangolo.
• La contronominale $\overline{q} \rightarrow \overline{p}=$”se $T$ non è un poligono, allora $T$ non è un triangolo” è invece certamente vera. Infatti non esiste alcun triangolo che non sia un poligono.

Definizione

Si definisce coimplicazione materiale, o più semplicemente coimplicazione di due proposizioni $p$ e $q$, la proposizione che è vera quando $p$ e $q$ hanno il medesimo valore di verità.

La coimplicazione materiale di $p$ e $q$ si indica con la scrittura $p \leftrightarrow q$ e si legge “$p$ se e solo se $q$”, o anche “$p$ coimplica $q$”.

Costruiamo la tavola di verità:

Definizione

Consideriamo due predicati $p(x), q(x)$ con dominio $D$. Se ogni valore di $x \in D$ che rende vero $p(x)$ rende vero anche $q(x)$ (cioè, se $p(x) \rightarrow q(x)$ $\forall x \in D$) allora:

• diremo che $p(x)$ implica logicamente $q(x)$, e scriveremo $p(x) \Rightarrow q(x)$;
• molto spesso diremo anche che $p(x)$ è condizione sufficiente per $q(x)$, mentre $q(x)$ è condizione necessaria per $p(x)$.
  
  

Se $p(x)$ implica logicamente $q(x)$, e anche $q(x)$ implica logicamente $p(x)$, allora diremo che $p(x)$ e $q(x)$ sono logicamente equivalenti e scriveremo $p(x) \Leftrightarrow q(x)$.

L’implicazione e l'equivalenza logica tra i predicati hanno un corrispondente all’interno della teoria degli insiemi. Infatti è possibile mostrare che se $P, Q$ sono gli insiemi di verità dei predicati $p(x), q(x)$ allora:

• se $p(x) \Rightarrow q(x)$, allora $P \subset Q$;
• se $p(x) \Leftrightarrow q(x)$, allora $P = Q$.
  
  

Abbiamo quindi un parallelismo tra la implicazione logica tra predicati $\Rightarrow$ e l’inclusione insiemistica $\subset$, così come tra l'equivalenza logica tra predicati $\Leftrightarrow$ e l’uguaglianza insiemistica $=$.

Facciamo un esempio. Consideriamo i seguenti predicati:

$\begin{aligned}p(x) & : x \text{ è un multiplo di 4}, x \in \mathbb{N} \\q(x) & : x \text{ è un multiplo di 2}, x \in \mathbb{N} \\\end{aligned}$

Allora:

• l’insieme di verità $P$ di $p(x)$ è $P = \{4, 8, 12, 16, \ldots\}$;
• l’insieme di verità $Q$ di $q(x)$ è $Q = \{2, 4, 6, 8, \ldots\}$;
• è chiaro che $p(x) \Rightarrow q(x)$, e infatti $P \subset Q$.

Revisione scientifica a cura di Marco Guglielmino