Logica matematica/Calcolo dei predicati

Il linguaggio della logica proposizionale ha un potere espressivo molto limitato. Infatti esso esprime, tramite un enunciato, solo le connessioni fra lettere proposizionali che a loro volta denotano, o rappresentano, fatti del mondo reale. Gli enunciati proposizionali sono indipendenti dalle particolari caratteristiche degli oggetti e individui di cui tali fatti trattano.

I linguaggi predicativi, o del primo ordine, benché anch'essi non adeguati per tutte le esigenze di rappresentazione del mondo reale, sono molto più espressivi del linguaggio proposizionale. Tramite un linguaggio del primo ordine si ha infatti la possibilità di esprimere proprietà e operazioni relative a individui e, quindi, si ha la possibilità di predicare (di qui il nome logica dei predicati) delle caratteristiche di oggetti e individui e, tramite l'uso di variabili e quantificatori, si può astrarre una caratteristica, o un'operazione, da un individuo a una classe di individui. Si ha infatti, nel linguaggio formale, ciò che nel linguaggio naturale è espresso da "un", "alcuni" e "tutti", quantificatori che permettono di indicare in modo generico oggetti che godono di proprietà.

Analogamente al caso proposizionale, insieme al linguaggio introduciamo una semantica che permette di interpretare i simboli del linguaggio. La semantica del primo ordine ci permetterà di capirne meglio la maggiore espressività rispetto al calcolo proposizionale.

Sintassi

Alfabeto

Un linguaggio predicativo o linguaggio del primo ordine ${\mathcal {L}}$ è costruito sui seguenti insiemi di simboli.

Simboli logici

• I connettivi proposizionali: $\neg ,\land ,\lor ,\to$ e $\leftrightarrow$;
• Le costanti proposizionali $\top$ e $\bot$;
• Il simbolo di uguaglianza $=$, eventualmente assente;
• I simboli separatori $'('$, $')'$ e $','$;
• Un'infinità numerabile di simboli di variabile individuale $x_{1},x_{2},...$;
• Il simbolo di quantificazione universale $\forall$;
• Il simbolo di quantificazione esistenziale $\exists$.

Parametri

• Un insieme finito o numerabile di simboli di predicato, ognuno dei quali ha associato un intero positivo $n$, detto arietà. Un predicato di arietà $n$ è detto $n$-ario;
• Un insieme finito o numerabile di simboli di funzione, ognuno dei quali ha associato un intero positivo $n$, detto arietà. Una funzione di arietà $n$ è detta $n$-aria;
• Un insieme finito o numerabile di simboli di costante.

Convenzioni

Per le variabili, piuttosto che usare pedici, preferiamo usare le ultime lettere dell'alfabeto minuscole: $x,y,w,z,t$. Inoltre, indicheremo i simboli di predicato con $P,Q,R,S,...$, oppure con parole con iniziale maiuscola. Indicheremo i simboli di funzione con $f,g,h,...$, oppure con parole con iniziale minuscola. Ometteremo il pedice che denota l'arietà quando questa sarà chiara dal contesto. Infine, indicheremo le costanti con le lettere minuscole della prima parte dell'alfabeto, oppure con nomi con iniziale minuscola.

I simboli di predicato a un argomento, cioè di arietà 1, vengono anche detti monadici.

Alcuni linguaggi del primo ordine includono tra i simboli logici il simbolo di uguaglianza, indicata con $=$. Il simbolo di uguaglianza è un simbolo di predicato binario, che si distingue dagli altri simboli di predicato, in quanto è un simbolo logico e ha un'interpretazione prefissata: qualunque sia il linguaggio del primo ordine, e qualunque sia l'interpretazione che se ne dà, il simbolo di uguaglianza deve essere interpretato come l'identità sul dominio d'interpretazione.

Osservazioni

Come nel linguaggio proposizionale, altri connettivi possono essere definiti in termini di quelli presentati sopra. L'insieme dei connettivi che abbiamo introdotto non è minimale; per esempio, il simbolo di quantificazione universale $\forall$ può essere definito in termini di quello esistenziale: $\forall \equiv \neg \exists \neg$.

Osserviamo che i simboli logici sono formati dagli elementi considerati immutabili, costituenti ogni linguaggio del primo ordine. Gli altri simboli, cioè i simboli di predicato, di costante e di funzione, sono considerati parametri, poiché possono essere diversi, a seconda del linguaggio. L'insieme dei parametri viene spesso indicato anche col nome di "segnatura" del linguaggio, in quanto i simboli della segnatura contraddistinguono il linguaggio stesso.

Si osservi che gli insiemi dei simboli di costante e funzione possono essere vuoti; non sono quindi essenziali nella definizione di una logica del primo ordine. Viceversa, l'insieme dei simboli di predicato (nel caso in cui il simbolo di uguaglianza sia assente) non deve essere vuoto. L'insieme dei simboli di variabile è infinito: vogliamo infatti avere sempre a disposizione variabili "fresche" da utilizzare nelle formule.

La ragione per la denominazione "primo ordine" sarà chiarita in seguito: vedremo infatti che si può solo quantificare su individui (simboli di variabili), non su insiemi di individui (simboli di funzioni e predicato).

Formule ben formate

Definiamo ora le espressioni legali del linguaggio ${\mathcal {L}}$, cioè le formule. Esse hanno quelle caratteristiche importanti che abbiamo già visto per il linguaggio proposizionale: si possono comporre, dando luogo a nuove espressioni legali, e sono un insieme induttivo. Nel caso di un linguaggio del primo ordine, gli elementi dell'insieme si compongono utilizzando i simboli logici e i parametri del linguaggio.

Per definire le formule, dobbiamo prima definire i termini e le formule atomiche o atomi.

Termini

L'insieme dei termini di ${\mathcal {L}}$ è l'insieme induttivo definito come segue:

1. Ogni simbolo di costante e di variabile è un termine;
2. Se $t_{1},...,t_{n}$ sono termini e $f$ è un simbolo di funzione $n$-aria, $f(t_{1},...,t_{n})$ è un termine (detto termine funzionale).

Atomi

L'insieme degli atomi o formule atomiche è definito induttivamente come segue:

1. $\top$ e $\bot$ sono atomi;
2. Se $t_{1}$ e $t_{2}$ sono termini, allora $t_{1}=t_{2}$ è un atomo;
3. Se $t_{1},...,t_{n}$ sono termini e $P$ è un simbolo di predicato $n$-ario, allora $P(t_{1},...,t_{n})$ è un atomo.

L'insieme delle formule ben formate di ${\mathcal {L}}$ è l'insieme delle espressioni che possono essere costruite, a partire dai termini e dagli atomi, usando opportunamente i connettivi e i quantificatori. In genere, una formula ben formata è detta semplicemente formula, o anche enunciato.

Formule

L'insieme delle formule di ${\mathcal {L}}$ è l'insieme induttivo definito come segue:

• Ogni atomo è una formula;
• Se $A$ è una formula, $\neg A$ è una formula;
• Se $\circ$ è un connettivo binario, $A$ e $B$ due formule, $A\circ B$ è una formula;
• Se $A$ è una formula, $x$ una variabile, $\forall xA$ e $\exists xA$ sono formule.

Si noti che, per definizione, i quantificatori $\forall$ ed $\exists$ possono solo essere applicati a simboli di variabile individuale e non, per esempio, a simboli di funzione o predicato. Questo spiega il nome di "logica del primo ordine", per contrasto con le "logiche di ordine superiore", in cui si può quantificare non solo su individui, ma su insiemi di individui.

Denotiamo, nel seguito, le formule di ${\mathcal {L}}$ sia con le lettere dell'alfabeto greco $\alpha ,\beta ,\gamma ,\phi ,\psi ,...$, sia con lettere maiuscole della prima parte dell'alfabeto $A,B,C,...$. Insiemi di formule verranno indicati con lettere greche maiuscole $\Gamma ,\Delta$, o anche con alcune lettere maiuscole, tipo $T$.

La precedenza tra gli operatori logici è stabilita come segue:

$\forall ,\exists ,\neg ,\land ,\lor ,\to ,\leftrightarrow$

e, come nel caso proposizionale, si assume che tutti gli operatori associno a destra.

Inoltre, quando uno stesso simbolo di quantificazione si ripete, invece di scrivere $\forall x\forall y$ possiamo scrivere $\forall xy$; analogamente quando si ripete il quantificatore esistenziale.

Variabili libere e legate

In una formula atomica, per definizione, non occorrono quantificatori, ma possono comparire variabili.

Consideriamo le seguenti formule non atomiche di ${\mathcal {L}}$:

1. $\forall x(Uomo(x)\to Vivo(x))$
2. $Uomo(x)\land Vivo(x)$

Nella formula 1 la variabile $x$ è quantificata. Possiamo parafrasare l'enunciato come segue: "Ogni uomo è vivo". Qualunque sia il discorso in cui esprimiamo questa frase, essa può essere vera o falsa, comunque è dotata di senso.

Nella formula 2, invece, la variabile $x$ occorre libera, poiché non ci sono quantificatori che la legano. Possiamo parafrasare la formula 2 come "un uomo vivo", ma non sappiamo di quale uomo si stia parlando. Per dare un senso alla formula 2, essa dev'essere inserita in un discorso più ampio che, eventualmente, ci permetta di individuare di quale uomo si tratti, o che dica che la proprietà è vera per tutti gli uomini, o che ne esiste qualcuno. Una variabile libera denota un individuo rispetto a un contesto. In un certo senso, in italiano, come in un linguaggio del primo ordine, una frase con variabili libere si può considerare come una parte costitutiva di una frase più ampia.

Veniamo ora alla definizione di variabili libere. Per fare ciò, definiamo prima l'insieme delle variabili che occorrono in un termine e in una formula atomica.

Insieme delle variabili di un termine

L'insieme $var(t)$ delle variabili di un termine $t$ è definito come segue:

1. $var(t)=\{t\}$, se $t$ è una variabile;
2. $var(t)=\emptyset$, se $t$ è una costante;
3. $var(f(t_{1},...,t_{n}))=\bigcup _{i=1}^{n}var(t_{i})$

Un termine si dice chiuso, o anche ground, se non contiene variabili.

Insieme delle variabili di un atomo

L'insieme delle variabili in una formula atomica $P(t_{1},...,t_{n})$ è:

$var(P(t_{1},...,t_{n}))=\bigcup _{i=1}^{n}var(t_{i})$

Un atomo si dice chiuso, o anche ground, se non contiene variabili.

Ovviamente, le variabili che occorrono nei termini e negli atomi possono solo essere libere, in quanto gli unici operatori che "legano" variabili sono i quantificatori.

Prima di fornire una definizione di occorrenza libera o legata di variabili in una formula, definiamo il campo d'azione di un quantificatore.

Campo d'azione di un quantificatore

Nella formula ${\mathcal {Q}}xA$, dove ${\mathcal {Q}}$ è un quantificatore (cioè ${\mathcal {Q}}\in \{\forall ,\exists \}$), il campo d'azione del quantificatore ${\mathcal {Q}}x$ è $A$.

Un quantificatore ${\mathcal {Q}}x$ "lega" le (eventuali) occorrenze libere della variabile quantificata $x$ nel campo d'azione $A$. Si noti che la nozione di campo d'azione è coerente con la convenzione che stabilisce le precedenze dei connettivi.

È chiaro che qualunque lettura diversa da quella convenzionale va imposta tramite un appropriato uso delle parentesi.

Definiamo ora cosa significa per una variabile $x$ occorrere libera in una formula.

Occorrenza libera di una variabile

L'occorrenza libera di una variabile in una formula è definita induttivamente sulla struttura della formula, come segue:

1. Se $A$ è un atomo, $x$ occorre libera in $A$ se $x$ occorre in $A$;
2. $x$ occorre libera in $\neg A$ se $x$ occorre libera in $A$;
3. $x$ occorre libera in $A\circ B$ se $x$ occorre libera in $A$ o $x$ occorre libera in $B$;
4. $x$ occorre libera in ${\mathcal {Q}}zA$ se $x$ occorre libera in $A$ e $x\neq z$.

Si noti quindi che l'insieme delle variabili libere di ${\mathcal {Q}}xA$ è:

$var({\mathcal {Q}}xA)=var(A)-\{x\}$.

Occorrenza legata di una variabile

Un'occorrenza di una variabile $x$, in una formula, si dice vincolata o legata se non è libera.

Quindi, le occorrenze legate di una variabile $x$ in una formula ${\mathcal {Q}}xA$ sono quella dopo il quantificatore ${\mathcal {Q}}$ e le eventuali occorrenze libere di $x$ nella formula $A$; queste ultime sono dette occorrenze proprie.

Nel seguito, chiameremo occorrenze di una variabile legata solo le occorrenze proprie. Osserviamo che una variabile può occorrere sia libera che legata in una stessa formula.

Enunciato o formula chiusa

Un enunciato, detto altrimenti formula chiusa, è una formula senza occorrenze libere di variabili.

Interpretazioni e modelli

Nella logica proposizionale abbiamo introdotto delle funzioni di assegnazione che associano un valore di verità ai simboli proposizionali e quindi, ricorsivamente, agli enunciati. La nozione di interpretazione, nella logica proposizionale, ci serve per sapere se la rappresentazione della realtà, che abbiamo dato per mezzo degli enunciati, è vera o falsa. Essa autorizza solo una rappresentazione superficiale, in cui gli oggetti del linguaggio hanno un valore di verità, ma non è possibile determinare una corrispondenza tra oggetti sintattici e oggetti del "mondo reale". Nella logica del primo ordine abbiamo invece la possibilità di interpretare i simboli del linguaggio per mezzo di strutture. Una struttura del primo ordine è un oggetto matematico che ci permette di tradurre formule, espresse nel linguaggio del primo ordine, in espressioni che hanno un significato specifico relativamente alla struttura, cioè la realtà che stiamo rappresentando. Per questo motivo, una struttura è un oggetto formale più complesso di un'interpretazione proposizionale, poiché è necessario individuare l'insieme degli oggetti su cui si quantifica e cosa denotano gli altri parametri del linguaggio, ovvero i predicati, le costanti e le funzioni.

Strutture

Intuitivamente, una struttura per ${\mathcal {L}}$ deve fornirci una funzione che assegni al quantificatore $\forall$ un insieme non vuoto di elementi. Questa funzione è la funzione di interpretazione e l'insieme non vuoto di elementi è il dominio di tale interpretazione. Più formalmente, diciamo che:

Definizione di struttura

Una struttura per il linguaggio ${\mathcal {L}}$ è una coppia ${\mathfrak {A}}=\langle D,I\rangle$, dove:

• $D$ è un insieme non vuoto, chiamato dominio di ${\mathfrak {A}}$;
• $I$ è una funzione chiamata interpretazione. $I$ associa:
  • ad ogni simbolo di costante $c$ un elemento $c^{I}\in D$;
  • ad ogni simbolo di funzione $n$-aria $f$ una funzione $f^{I}:D^{n}\mapsto D$;
  • ad ogni simbolo di predicato $n$-ario $P$ una relazione $n$-aria $P^{I}\subseteq D^{n}$.

La definizione ci dice che l'interpretazione $I$ assegna un preciso significato a ciascun parametro di ${\mathcal {L}}$. In particolare, il simbolo $c$ è un nome per l'elemento $c^{I}$, che è un individuo (o un punto) di $D$; la formula atomica $P(t_{1},...,t_{n})$ denota la n-upla di individui in $D$, che sono a loro volta denotati da $t_{1},...,t_{n}$ e che stanno fra loro nella relazione $P^{I}$; il termine $f(t_{1},...,t_{n})$ denota la funzione $f^{I}$ in $D$ sulla n-upla di individui denotati da $t_{1},...,t_{n}$. Osserviamo che è richiesto che il dominio sia non vuoto e che la funzione $f^{I}$ sia definita su tutto il dominio. Il dominio $D$ è il riferimento per l'interpretazione dei quantificatori: $\forall x$ significa "per ogni elemento di $D$"; $\exists x$ significa "esiste un elemento di $D$". Come ovvio, $I$ non fornisce un'interpretazione per $=$, $\top$ e $\bot$, in quanto sono simboli logici e non parametri del linguaggio, quindi la loro interpretazione è fissata.

Per poter caratterizzare il significato di verità in una struttura è necessario definire come vengono interpretate le variabili.

Assegnazione alle variabili

Sia ${\mathcal {Var}}$ l'insieme dei simboli di variabili di un linguaggio del primo ordine ${\mathcal {L}}$. Un'assegnazione, o ambiente, o stato delle variabili $\eta$ in una struttura ${\mathfrak {A}}=\langle D,I\rangle$ è una funzione dall'insieme ${\mathcal {Var}}$ all'insieme $D$:

$\eta :{\mathcal {Var}}\mapsto D$.

Per ogni simbolo di variabile $x$, indichiamo il suo valore relativo all'assegnazione $\eta$ con $x^{\eta }$.

Un'assegnazione $\eta$, quindi, è una maniera di associare un valore alle variabili del linguaggio ${\mathcal {L}}$.

A questo punto, definiamo la nozione di formula vera in una struttura ${\mathfrak {A}}$. Il significato intuitivo è che una formula è vera in una struttura ${\mathfrak {A}}=\langle D,I\rangle$ sse è vera la sua interpretazione in $D$, ottenuta assegnando un valore alle variabili per mezzo di un'assegnazione $\eta$.

Per dare una definizione precisa, è necessario prima estendere la funzione di assegnazione ai termini del linguaggio.

Assegnazione sui termini

Sia ${\mathfrak {A}}=\langle D,I\rangle$ una struttura per ${\mathcal {L}}$ e sia $\eta$ un'assegnazione. Estendiamo tale assegnazione a un'assegnazione ${\overline {\eta }}=\langle I,\eta \rangle$ sui termini ricorsivamente come segue:

• per ogni simbolo di variabile $x$, $x^{\overline {\eta }}=x^{\eta }$;
• per ogni simbolo di costante $c$, $c^{\overline {\eta }}=c^{I}$;
• se $t_{1},...,t_{n}$ sono termini ed $f$ è un simbolo di funzione $n$-aria, allora $f(t_{1},...,t_{n})^{\overline {\eta }}=f^{I}(t_{1}^{\overline {\eta }},...,t_{n}^{\overline {\eta }})$.

Osserviamo che l'esistenza di un'unica ${\overline {\eta }}$ è assicurata dal teorema di ricorsione, sulla base del fatto che l'insieme dei termini è un insieme induttivo generato liberamente.

Un'assegnazione ${\overline {\eta }}$ è quindi una maniera di associare un valore ai termini del linguaggio ${\mathcal {L}}$. La definizione appena esposta, infatti, associa un elemento del dominio $D$ ad ogni termine del linguaggio. Se il termine è chiuso, ovviamente il suo valore non dipende dall'assegnazione $\eta$.

A questo punto, definita una funzione che dà significato (cioè un valore) alle variabili, estesa quest'ultima ai termini del linguaggio, rispetto a una struttura in cui vengono interpretati predicati e funzioni, possiamo associare a ogni formula un valore di verità, quindi definire la nozione di soddisfacibilità e validità. Lo facciamo introducendo una funzione di valutazione ${\mathcal {V}}$ tra struttura e formula, relativamente ad un'assegnazione ${\overline {\eta }}$. La valutazione di una formula $\phi$, in una struttura ${\mathfrak {A}}$ e rispetto ad un'assegnazione ${\overline {\eta }}$, è denotata con:

${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},\phi )$

che, intuitivamente, restituisce $\mathrm {T}$ sse è vera l'interpretazione di $\phi$ determinata da ${\mathfrak {A}}$ e in cui una variabile $x$, ovunque occorra libera in $\phi$, è valutata come $x^{\overline {\eta }}$.

Definiamo dunque la funzione di valutazione ${\mathcal {V}}$ induttivamente come segue:

Funzione di valutazione

Sia ${\mathfrak {A}}=\langle D,I\rangle$ una struttura per ${\mathcal {L}}$, sia ${\overline {\eta }}=\langle I,\eta \rangle$ un'assegnazione in ${\mathfrak {A}}$ e sia ${\mathcal {S}}=\langle {\mathcal {B}},{\mathcal {T}},{\mathcal {Op}}\rangle$ il sistema di valutazione della logica proposizionale.

1. ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},\top )=\mathrm {T}$ e ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},\bot )=\mathrm {F}$;
2. se $A$ è una formula atomica del tipo $P(t_{1},...,t_{n})$, allora ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},P(t_{1},...,t_{n}))={\begin{cases}\mathrm {T} ,&{\text{se }}\langle t_{1}^{\overline {\eta }},...,t_{n}^{\overline {\eta }}\rangle \in P^{I}\\\mathrm {F} ,&{\text{altrimenti}}\end{cases}}$;
3. se $A$ è una formula atomica del tipo $t_{1}=t_{2}$, allora ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},t_{1}=t_{2})={\begin{cases}\mathrm {T} ,&{\text{se }}t_{1}^{\overline {\eta }}=t_{2}^{\overline {\eta }}\\\mathrm {F} ,&{\text{altrimenti}}\end{cases}}$;
4. ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},\neg A)={\mathcal {Op}}_{\neg }({\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},A))$;
5. ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},A\circ B)={\mathcal {Op}}_{\circ }({\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},A),{\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},B))$, con $\circ \in \{\land ,\lor ,\to ,\leftrightarrow \}$;
6. ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},\forall xA)={\mathcal {Op}}_{\forall x}(A,D,c)$, con $c\in D$;
7. ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},\exists xA)={\mathcal {Op}}_{\exists x}(A,D,c)$, con $c\in D$.

Dove:

• ${\mathcal {Op}}_{\forall x}(A,S,c)={\begin{cases}\mathrm {T} ,&{\text{se }}S=\emptyset \\\mathrm {F} ,&{\text{se }}{\mathcal {V}}({\mathfrak {A}},{\overline {\eta }}[c/x],A)=\mathrm {F} \\{\mathcal {Op}}_{\forall x}(A,S-\{c\},d),&{\text{se }}{\mathcal {V}}({\mathfrak {A}},{\overline {\eta }}[c/x],A)=\mathrm {T} {\text{, con }}d\in S-\{c\}{\text{, o }}d=c{\text{ se }}S-\{c\}=\emptyset \end{cases}}$
• ${\mathcal {Op}}_{\exists x}(A,S,c)={\begin{cases}\mathrm {F} ,&{\text{se }}S=\emptyset \\\mathrm {T} ,&{\text{se }}{\mathcal {V}}({\mathfrak {A}},{\overline {\eta }}[c/x],A)=\mathrm {T} \\{\mathcal {Op}}_{\exists x}(A,S-\{c\},d),&{\text{se }}{\mathcal {V}}({\mathfrak {A}},{\overline {\eta }}[c/x],A)=\mathrm {F} {\text{, con }}d\in S-\{c\}{\text{, o }}d=c{\text{ se }}S-\{c\}=\emptyset \end{cases}}$

Dove l'assegnazione ${\overline {\eta }}[c/x]$ indica la funzione che si comporta esattamente come ${\overline {\eta }}$, eccetto che sulla variabile $x$, dove assume il valore $c$:

${\overline {\eta }}[c/x](y)={\begin{cases}c,&{\text{se }}y=x\\y^{\overline {\eta }},&{\text{altrimenti}}\end{cases}}$

Soddisfacibilità delle formule

La relazione di soddisfacibilità $\models$ è definita come segue:

${\mathfrak {A}},{\overline {\eta }}\models \phi$ sse ${\mathcal {V}}({\mathfrak {A}},{\overline {\eta }},\phi )=\mathrm {T}$

Teoria della dimostrazione