# Insiemi, proposizioni e predicati

Il primo approccio alla logica deve seguire la teoria naive degli insiemi. Senza bisogno di definizioni e formalismi, tutti posseggono un' idea di cosa sia un insieme: si può parlare dell'insieme dei numeri naturali, e dell'insieme dei numeri pari, così come dell'insieme dei medici italiani. Qualcuno fa parte dell'insieme dei medici, qualcuno non ne fa parte; qualcuno fa parte dell'insieme dei medici, ma non merita di farne parte. Queste sottigliezze, però, non esistono in matematica: ogni insieme è chiaramente e completamente definito senza ambiguità. Infatti non ci sono dubbi, per chi conosce la materia, su quali elementi appartengano o meno all'insieme dei numeri naturali: 1 vi appartiene, 162345 vi appartiene, -5 non vi appartiene, Garibaldi non vi appartiene. Già, perché la matematica non si limita a trattare solo i numeri. Attraverso l'insiemistica può definire categorie, cioè insiemi, per qualsiasi elemento. Si potrebbe quindi parlare dell'insieme degli attori di teatro, dell'insieme dei giorni della settimana, etcetera. A questo livello, tutto quello che ci si domanda è: «Quali elementi appartengono a questo insieme?»

## La notazione matematica: le proposizioni

Un altro tipo di concetti che il matematico si ritrova spesso a scrivere in gran quantità sono le relazioni logiche. L'esempio più classico è quello del sillogismo: "Ogni uomo è un animale e Socrate è un uomo quindi Socrate è un animale". Fino a che si fanno ragionamenti così semplici bastano le parole, ma la matematica si addentra in verità ben più complicate; sono stati sviluppati quindi per maggiore chiarezza dei simboli per sintetizzare le relazioni logiche, che nella lingua, di solito, sono congiunzioni. Il sillogismo di prima diventa quindi
$({\mbox{Ogni uomo è un animale }}\wedge {\mbox{ Socrate è un uomo }})\Rightarrow {\mbox{ Socrate è un animale}}$.
Come si può bene intuire, il simbolo $\wedge$ sta al posto della congiunzione "e", mentre il simbolo $\Rightarrow$ sostituisce la congiunzione "quindi". In altri termini, l'ultima formula potrebbe essere riscritta con "Se ogni uomo è un animale e se Socrate è un uomo allora Socrate è un animale". Come vedete, le congiunzioni sono cambiate un pochino, ma il significato è sempre lo stesso. Non è possibile, tuttavia, scrivere cose come "Tizio $\wedge$ Caio vanno al cinema", perché questi simboli, chiamati connettivi logici, servono esclusivamente per collegare tra loro proposizioni. Le proposizioni sono frasi che possono stare in piedi da sole, delle quali (normalmente) si può dire se sono vere o false. «Oggi» non è una proposizione, dal momento che non è ne vera ne falsa; «Oggi è martedì» è una proposizione, anche se il suo essere vera o falsa dipende da che giorno è. Anche «Ieri è piovuto» è una proposizione, e posso collegarla alla precedente: «Oggi è martedì $\wedge$ ieri è piovuto». Oltre ai due presentati si usano anche altri connettivi logici; questi sono i più comuni:
| simbolo | significato |
| $\wedge$ | e |
| $\vee$ | o |
| ¬ | non |
| $\Rightarrow$ | se ... allora ... |
| $\Leftrightarrow$ | se e solo se |
Per chiarire in modo sistematico il significato di questi connettivi logici, si usano delle tabelle di verità. Questo perché di una proposizione, quello che interessa maggiormente è il suo essere vera o falsa. In sostanza se una proposizione generica, che possiamo chiamare $p$ è vera, di conseguenza la sua negazione, cioè la proposizione ${\mbox{¬}}p$ è falsa; e viceversa se una proposizione è falsa, la sua negazione è vera. Altrettanto specifichiamo caso per caso, in modo da escludere ambiguità, il valore di verità per tutti gli altri connettivi:
| proposizione P | proposizione Q | proposizione P$\wedge$Q | proposizione P$\vee$Q | proposizione P$\Rightarrow$Q | proposizione P$\Leftrightarrow$Q |
| vera | vera | vera | vera | vera | vera |
| vera | falsa | falsa | vera | falsa | falsa |
| falsa | vera | falsa | vera | vera | falsa |
| falsa | falsa | falsa | falsa | vera | vera |
Alcuni esempi permettono di capire meglio come funzionano queste proposizioni. Uso le lettere P, Q ed R come variabili: sono dei segnaposto, dei nomi generici che utilizzo per indicare una qualsiasi proposizione; ad esempio P potrebbe essere «Oggi è martedì», oppure «5 è minore di 10», o chissà cos'altro. Vediamo quindi questa proposizione composita:
$(P\vee Q)\Rightarrow R$
Che cosa significa? Dipende da cosa sostituiamo al posto di P, Q e R. Se queste variabili significano, nell'ordine «Oggi è sabato», «Oggi è domenica» e «Andiamo al cinema». Adesso la frase precedente prende un certo significato:
$({\mbox{Oggi è sabato}}\vee {\mbox{oggi è domenica}})\Rightarrow {\mbox{andiamo al cinema}}$
ovvero, a parole:
Se oggi è sabato oppure oggi è domenica, allora andiamo al cinema.

## La notazione matematica : i predicati

Quello che permette di mescolare gli insiemi e le proposizioni, amplificando enormemente le potenzialità espressive del linguaggio matematico, sono i predicati. In verità, però, si utilizza un solo tipo di predicato, quello di appartenenza già descritto per gli insiemi:
$x\in A$
A partire da questo predicato minimo si possono costruire predicati più complessi, grazie ai connettivi logici, ad esempio
$x\in A\Leftrightarrow (x\in B\wedge \neg (x\in C))$
Ma la vera potenzialità dei predicati sta nell'utilizzo dei quantificatori. Questi sono due, il quantificatore universale $\forall$ e il quantificatore esistenziale $\exists$. Il primo, come tutti gli altri simboli che si usano in matematica, è l'abbreviazione di un concetto: al posto di dire «Per ogni elemento x, $\neg x\in A$» (nel significato che se preso un qualsiasi elemento x, è vera la proposizione che segue) scriveremo «$\forall x(\neg x\in A)$». Allo stesso modo anche il quantificatore esistenziale è un'abbreviazione. L'idea è che esiste almeno un elemento che rende vera la proposizione che segue il quantificatore: ad esempio «$\exists x(x\in B)$» significa che esiste almeno un elemento che rende vera la proposizione (cioè che appartiene a B).