La logica matematica e la teoria degli insiemi - WeSchool


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.





















Videolezione "Studio di funzione: il procedimento"

























    const isRelatedVideo = 1;

 
 


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}$:


$p$


$\overline{p}$


V


F


F


V


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$: 


$p$


$q$


$p \wedge q$


V


V


V


V


F


F


F


V


F


F


V


F


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:


##KATEX##\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}##KATEX##


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à:


$p$


$q$


$p \vee q$


V


V


V


V


F


V


F


V


V


F


F


F


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à:


$p$


$q$


$p \rightarrow q$


V


V


V


V


F


F


F


V


V


F


F


V


 


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à:


$p$


$q$


$p \leftrightarrow q$


V


V


V


V


F


F


F


V


F


F


F


V


 


 


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:


##KATEX##\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}##KATEX##


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

