Logica matematica

Logica formale

In logica è importante fare una distinzione tra la verità e la correttezza del ragionamento: sono due concetti diversi. L'idea è che la verità riguardi il significato di una singola affermazione, indipendentemente dal contesto. Un ragionamento, invece, non è vero o falso: quello che ci interessa è come le affermazioni sono collegate tra loro.

Un ragionamento deve permetterti di passare da una, o più, ipotesi a una conclusione. In logica un ragionamento si considera corretto se, ogni volta che è vera l'ipotesi, è vera anche la conclusione. In questo caso si dice che il ragionamento è valido.

In logica non si parla di frasi, ma di proposizioni: sono affermazioni a cui bisogna poter assegnare un valore di verità: vero o falso.

Le proposizioni si indicano con una lettera minuscola dell'alfabeto latino come p, q, s. Come sempre, però, non tutti usano la stessa notazione matematica: potresti trovarle indicate anche con lettere maiuscole come \(A, B, ...\) oppure con le lettere dell'alfabeto greco \(\alpha, \beta, \phi, \psi\).

Date due proposizioni puoi combinarle con dei connettivi logici che permettono di crearne una nuova. Non pensare a qualcosa di strano: i connettivi imitano elementi del nostro linguaggio, solo, hanno un significato più preciso! Il connettivo forse più semplice è \(\neg\) che esprime la negazione di una proposizione. Data \(p\), la negazione \(\neg p\) è un'altra proposizione che è vera se \(p\) è falsa, ed è falsa se \(p\) è vera. Un altro esempio è la congiunzione, che corrisponde alla "e" del linguaggio comune e si indica con il simbolo \( \wedge \). La congiunzione \(p \wedge q\) di due proposizioni logiche \(p, q\) è vera se sono vere sia \(p\) che \(q\).

Un altro esempio è la disgiunzione, che si indica col simbolo \(\vee\) e ha un significato simile alla "o" nel linguaggio, come in Vado in vacanza al mare o in montagna. A volte quando parliamo non è chiaro se la "o" indica una sola tra le opzioni, o se sono possibili tutte e due assieme: sto dicendo che se vado in vacanza al mare non andrò anche in montagna? O che forse vado in vacanza in un luogo in cui c'è montagna vicino al mare? In logica la disgiunzione è inclusiva: ovvero, \(p \vee q\) è vera nei tre casi seguenti:

• se \(p\) è vera e \(q\) è falsa;
• se \( p \) è falsa e \(q\) è vera;
• se \(p\) è vera e \(q\) è vera.

\(p \vee q\) è falsa solo nel caso in cui \(p\) e \(q\) sono entrambe false.

Deduzione logica

Torniamo al problema di partenza: capire quando un ragionamento è valido e quando no. Come hai già visto nel paragrafo qui sopra, un ragionamento è fatto di premesse e conclusioni. Una premessa è una proposizione che si dà per vera e fa da punto di partenza del ragionamento. L'idea è che un ragionamento, a partire da una o più premesse, arrivi a dimostrare un'altra proposizione finale che viene chiamata conclusione.

Le regole di deduzione logica consentono precisamente di fare un passaggio corretto dalle premesse alla conclusione. Un esempio di regola valida è la seguente (regola di eliminazione della disgiunzione o dimostrazione per casi):

• Premessa: \(p \vee q\)
• Premessa \(\neg p\)
• Conclusione: \(q\)

Al posto di \(p\) e \(q\) puoi mettere qualunque proposizione: la regola resta valida!

Contraddizioni e tautologie

La contraddizione è il peggior nemico della logica! Recuperando i simboli che hai visto finora, puoi esprimere una contraddizione come

\[p \wedge \neg p\]

Una tra \(p\) e \(\neg p\) è per forza falsa, quindi la congiunzione delle due non può essere vera. Una contraddizione logica è sempre falsa! Non è importante qual è il significato di una proposizione \(p\): che sia il sole splende e il sole non splende, ho vinto 100 euro e non ho vinto 100 euro, 0 è pari e 0 è dispari. Al contrario, un'affermazione sempre vera è chiamata tautologia: un esempio è \(p \vee \neg p\) (principio del terzo escluso).

In qualunque caso, una contraddizione mostra che un sistema di premesse è incoerente: le premesse non possono essere tutte vere contemporaneamente.

Insiemi

Le proposizioni logiche si usano spesso in matematica per affermare che un oggetto ha una proprietà, o che non la ha. La collezione di elementi che hanno una certa proprietà definisce un insieme, un concetto fondamentale per la matematica moderna. Attenzione, però: non tutte le collezioni di oggetti formano un insieme! Per definire un insieme si deve sempre poter dire se un elemento appartiene o no alla collezione, esattamente come le proposizioni logiche devono poter essere vere o false.

Un oggetto che appartiene a un insieme si chiama elemento. Gli insiemi si indicano con le lettere maiuscole dell'alfabeto latino: \(A, B, C, X, \dots\), mentre gli elementi con le minuscole \(a, b, c, x, \dots \). La relazione di appartenenza si indica con il simbolo \(\in\): per dire che l'elemento \(x\) appartiene all'insieme \(A\) si può scrivere \(x \in A\). Se gli elementi di un insieme \(A\) appartengono tutti a un insieme \(B\), si dice che \(A\) è un sottoinsieme di \(B\) (o che \(A\) è contenuto in \(B\)): questo si indica col simbolo \(A \subset B\). Per indicare che \(x\) non appartiene a un insieme \(A\), o che \(A\) non è un sottoinsieme di \(B\), si mette una barra sul simbolo corrispondente: \(x \not\in A\), \(A \not\subset B\).

Un insieme si può rappresentare per elencazione mettendo tra parentesi graffe i suoi elementi, così: \(A = \{1, 3, 5, 7\}\). Un'altra rappresentazione possibile è quella per caratteristica, in cui si mette tra le graffe la proprietà che lo definisce, così: \(S =\{ x : x \text{ è un giorno della settimana }\}\)I

In generale, dire che un elemento appartiene a un insieme, o che un elemento ha una certa proprietà, è una proposizione logica. Questa proposizione è vera se un elemento appartiene all'insieme e falsa se non gli appartiene.

Dati due insiemi, puoi definire la loro unione e la loro intersezione. L'unione di due insiemi \(A\) e \(B\) si indica con \(A \cup B\) ed è l'insieme che contiene tutti gli elementi di \(A\) e tutti gli elementi di \(B\). L'intersezione di due insiemi \(A\) e \(B\) si indica con il simbolo \(A \cap B\) : è l'insieme che contiene tutti gli elementi comuni ad \(A\) e \(B\).

In molte aree della matematica capita di fare esercizi fissando un insieme che fa da ambiente in cui si svolge tutta la "storia". Succede ad esempio quando risolvi equazioni: ti interessa risolverle nei numeri reali \(\mathbb{R}\). Oppure in probabilità: tutti gli eventi sono sottoinsiemi dello spazio campionario \(\Omega\). Questo insieme allora viene chiamato insieme universo: tutti gli insiemi che consideri nell'esercizio sono contenuti in esso. Dato un insieme universo \(U\) e un suo sottoinsieme \(A \subset U\), il complementare di \(A\) si indica con \(A^c\) o \(\bar{A}\) ed è formato da tutti gli elementi di \(U\) che non sono in \(A\).

Diagrammi di Venn

Un altro modo di descrivere un insieme è tramite i diagrammi di Venn, o di Eulero-Venn. L'idea è molto semplice: rappresentare un insieme con una linea circolare chiusa. Gli elementi si possono indicare come punti: all'esterno dell'insieme se non gli appartengono, all'interno se gli appartengono. Nel disegno, l'elemento \(x\) appartiene ad \(A\) mentre \(y\) no.

Fig 1. Insiemi ed elementi.

Con i diagrammi di Venn si possono indicare facilmente unione e intersezione di insiemi: l'intersezione è la parte in cui i due insiemi si sovrappongono, mentre l'unione corrisponde alla parte coperta da almeno uno dei due insiemi.

Fig. 2. Intersezione e unione.

Oppure si può rappresentare il complementare di un insieme all'interno di un insieme universo: in questi casi, l'insieme universo si rappresenta con un rettangolo in modo da identificarlo meglio.

Fig. 3. Complementare di un insieme

I diagrammi di Venn si possono usare anche per rappresentare gli eventi in probabilità, e in generale per rappresentare le relazioni tra proposizioni in un ragionamento logico. Un insieme è l'elenco di elementi per cui è vera una certa proposizione \(p\): i connettivi logici \(\wedge\) e \(\vee\) si possono rappresentare con le operazioni insiemistiche \(\cap\) e \(\cup\). Allo stesso modo, fissato un insieme universo in cui puoi fare l'operazione di complementare, \(\neg p\) corrisponde all'operazione di complementare.

Può sembrare strana l'idea di rappresentare un ragionamento con un diagramma: si può fare un esempio con il ragionamento iniziale di questo articolo.

Tutti i gatti sono mortali.

Socrate è mortale.

Socrate è un gatto.

Le prime due frasi sono le premesse: supponiamo siano vere. Allora vuol dire che l'insieme dei gatti è un sottoinsieme di quello dei mortali. La seconda frase dice che Socrate è un elemento dell'insieme dei mortali. Ma dobbiamo metterlo dentro l'insieme dei gatti oppure no? Entrambe le rappresentazioni sono coerenti con le premesse: non è corretto, quindi, dedurre che vada bene solo quella in cui Socrate è un gatto. Il ragionamento quindi non è valido.

Fig. 4. Socrate è un mortale. Non sappiamo se è un gatto o no.