Introduzione alla logica matematica

La logica matematica è il settore della matematica che studia i sistemi formali dal punto di vista del modo di codificare i concetti intuitivi della dimostrazione e di computazione come parte dei fondamenti della matematica.

Sebbene molti siano indotti a pensare che la logica matematica sia la matematica della logica, è più giustificato affermare che essa è la logica applicata alla matematica. Essa si occupa delle parti della logica che possono essere modellate matematicamente.

Altri termini utilizzati spesso nel passato sono logica simbolica (termine contrapposto a logica filosofica) e metamatematica, termine che ora si applica più specificamente a taluni aspetti della teoria della dimostrazione.

Sebbene, come detto, la logica matematica sia un sistema formale, è opportuno, per chi volesse avvicinarsi ad essa senza un'approfondita pratica matematica, interporre un po' di esercizio sull'insiemistica nella sua forma naïve, con alcune semplici dimostrazioni. A questo scopo il primo modulo della materia, che può essere omesso dallo studente esperto.

Insiemi, proposizioni e predicati

Il primo approccio alla logica deve seguire la teoria naïve degli insiemi. Senza bisogno di definizioni e formalismi, ognuno possiede 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 il matematico si domanda è: «Quali elementi appartengono a questo insieme?»

La notazione matematica : gli insiemi

Chi studia matematica, dovendo scrivere molto per sviluppare ragionamenti e dimostrazioni in modo preciso, ha sviluppato nel tempo un codice di simboli e abbreviazioni che sveltiscono il lavoro da fare. È necessario famigliarizzare con la notazione per potersi avventurare con i testi tecnici di matematica. Una parte di questo codice riguarda anche l'insiemistica: la descrizione di un insieme è, in molti casi, l'elenco dei suoi elementi tra parentesi graffe. Ovvero, al posto che dire "L'insieme che ha per elementi precisamente 1, 3, 5 e 15", i matematici scrivono

$\{1,3,5,15\}$

Dal momento che alcuni insiemi sono enormi, e non è possibile elencare tutti i loro elementi, talvolta si usa una notazione descrittiva. In questi casi, al posto che scrivere "L'insieme di tutti marinai inglesi", il matematico scriverà

$\{x\mid x{\mbox{ è un marinaio inglese}}\}$

La sbarretta verticale si legge in questi casi come un «tale che» oppure «tali che». L'intera definizione si leggera quindi come «L'insieme degli x tali che x è un marinaio inglese». Infine, l'ultimo simbolo introdotto serve per denotare l'appartenenza di un elemento ad un insieme. Se stiamo cominciando a definire un nuovo insieme, cominceremo dandogli un nome, ad esempio A. Se vogliamo spiegare che l'elemento 0, cioè il numero 0 ( zero ) appartiene a tale insieme, scriveremo secondo la convenzione:

$0\in A\quad {\mbox{ oppure }}\quad A\ni 0$

La notazione matematica : le proposizioni

Un altro tipo 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 ha piovuto» è una proposizione, e posso collegarla alla precedente: «Oggi è martedì $\wedge$ ieri ha 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 prendo 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).

Strumenti minimi della teoria degli insiemi

Inclusione

Dati due insiemi A, B, può accadere che tutti gli elementi del primo insieme siano anche elementi del secondo insieme. Tale situazione, espressa in linguaggio matematico è la formula:

$\forall x(x\in A\Rightarrow x\in B)$

Questa proprietà si riassume con un simbolo $\subseteq$ detto di "inclusione": $A\subseteq B$.

Uguaglianza

Dati due insiemi A e B, può accadere che essi siano uguali. In insiemistica "uguali" significa che tutti gli elementi del primo sono anche elementi del secondo insieme, e viceversa. Questa è una definizione di uguaglianza che si dice estensiva, ovvero legata esclusivamente a quali elementi appartengono agli insiemi. Ovviamente questa proprietà si indica con il simbolo =, ed è formalmente equivalente ad una doppia inclusione, ovvero:

$A=B\Leftrightarrow (A\subseteq B\wedge B\subseteq A)$

Infatti, nella maggior parte delle dimostrazioni, per dimostrare un'uguaglianza tra due insiemi si procede separatamente a dimostrare le due inclusioni.

Unione

Dati due insiemi A e B, si può ottenere un terzo insieme che abbia tutti gli elementi del primo e tutti gli elementi del secondo insieme. Tale nuovo insieme si chiama unione di A e B e si indica con il simbolo $A\cup B$, e una definizione formale è la seguente:

$A\cup B=\{x\mid x\in A\vee x\in B\}$

Intersezione

Dati due insiemi A e B, si può ottenere un terzo insieme che abbia solo gli elementi che sono sia nel primo che nel secondo insieme. Tale nuovo insieme si chiama intersezione di A e B e si indica con il simbolo $A\cap B$, definito con:

$A\cap B=\{x\mid x\in A\wedge x\in B\}$

Coppia ordinata

Nulla negli insiemi può distinguere un ordine degli elementi. Si utilizza una definizione apposita per creare un insieme nel quale, a tutti gli effetti, c'è un primo elemento ed un secondo elemento. Questo tipo di insieme di chiama coppia ordinata: dati due elementi x e y, l'insieme

$(x,y)=\{\{x\},\{x,y\}\}$

A dimostrare che effettivamente x è il primo elemento e y è il secondo, c'è un teorema che stabilisce che: due coppie ordinate (a,b) e (c,d) sono uguali se e solo se a=c e b=d.

Prodotto cartesiano

Vedi anche Prodotto cartesiano

Funzione

Vedi anche Funzione

Biiezione

Vedi anche Biiezione