Skolemizzazione

In logica matematica, si dice skolemizzazione l'applicazione dell'algoritmo di Albert Thoralf Skolem che trasforma un enunciato in forma normale in un enunciato universale. L'enunciato in questione, dopo l'applicazione dell'algoritmo di Skolem, perde l'equivalenza semantica con l'enunciato di partenza. È interessante però constatare che rimane invariata la soddisfacibilità (ovvero, preso un qualsiasi enunciato $\varphi$, esiste un modello per $\varphi$ se e solo se ne esiste uno per la forma normale di Skolem di $\varphi$).

Dato un linguaggio $L$, una frase $\alpha \in L$ è un enunciato universale se:

1. $\alpha$ è un enunciato (non ci sono variabili libere)
2. $\alpha$ è in forma normale e gli unici quantificatori, se esistono, sono di tipo $\mathrm{\forall }$.

Esempio di enunciati universali.

• $A(b)\wedge C(a)$
• $\mathrm{\forall }x\mathrm{\forall }y(A(y)\wedge \mathrm{\neg }C(x))$

N.B. L'algoritmo di Skolem non mantiene l'equivalenza semantica. La frase risultante dall'applicazione dell'algoritmo di Skolem è soddisfacibile se lo è la frase normale di partenza.

Algoritmo di Skolem

1. Trasformazione in forma prenessa. I quantificatori $\mathrm{\forall }$ e $\mathrm{\exists }$ devono essere raggruppati all'inizio della frase. $\mathrm{\forall }{x}_1,\mathrm{\exists }{x}_2\mathrm{\forall }{x}_3(\dots )$
2. Determinare le variabili libere e vincolate. Nella frase non ci devono essere variabili libere, nel caso ci siano è necessario eseguire una sostituzione.
3. Se $Q_1$ (primo quantificatore) è $\mathrm{\forall }$ si passa direttamente al punto successivo.
   Se $Q_1$ è $\mathrm{\exists }$ allora si cancella $\mathrm{\exists }{x}_1$ e si sostituisce ad ogni occorrenza di $x_1$ in $\alpha$ una stessa costante (nota come "costante di Skolem") che non compaia già in $\alpha$. Esempio: $\mathrm{\exists }x\mathrm{\forall }y(A(a,x)\wedge B(b,x,y)$ diventa $\mathrm{\forall }y(A(a,c))\wedge B(b,c,y)$
   Come si può facilmente notare si è tolto il quantificatore $\mathrm{\exists }$ e si è sostituita la variabile $x$ con la costante $c$.
   La scelta della costante $c$ non è casuale visto che $a$ e $b$ erano già utilizzate.
4. Prendo in rassegna $Q_n$
   • Se $Q_n$ è un $\mathrm{\forall }$ si riparte da questo punto con $Q_{n+1}$.
   • Se $Q_n$ è $\mathrm{\exists }$ allora i casi possono essere i seguenti:
     • Se il quantificatore $Q_{n-1}$ era di tipo $\mathrm{\exists }$ ovvero $\mathrm{\exists }{x}_{n-1}\mathrm{\exists }{x}_n$ allora si ripete il punto precedente con $\mathrm{\exists }{x}_n$ sostituendo però ad ogni occorrenza della variabile $x_n$ un funtore che prenda in rassegna tutte le variabili precedentemente utilizzate dai quantificatori $\mathrm{\forall }$.
       Come si può notare finché non appaiono quantificatori di tipo $\mathrm{\forall }$ si sostituiscono alle variabili $x_n$ delle semplici costanti.
     • Se il quantificatore $Q_{n-1}$ è di tipo $\mathrm{\forall }$ ovvero $\mathrm{\forall }{x}_{n-1}\mathrm{\exists }{x}_n$ si cancella $\mathrm{\exists }{x}_n$ e si sostituisce ogni occorrenza di $x_n$ in $\alpha$ con un funtore $f(\cdot )$ che prenda in rassegna le variabili utilizzate dai quantificatori $\mathrm{\forall }$ che lo precedono. Se fosse $\mathrm{\forall }y\mathrm{\forall }z\mathrm{\exists }u(\alpha )$ dovrei in primis cancellare $\mathrm{\exists }u$ poi sostituire nella frase $\alpha$ la variabile $u$ con il funtore $f(y,z)$ (il funtore non deve esistere già).
   Esempio: $\mathrm{\forall }x\mathrm{\exists }y(A(x,f(x),y)\wedge C(y))$ diventa $\mathrm{\forall }x(A(x,f(x),g(x))\wedge C(g(x)))$
   Come si può facilmente notare, si è tolto il quantificatore $\mathrm{\exists }y$ e si è sostituita la variabile $y$ con il funtore $g(x)$.
   La scelta della variabile $x$ non è casuale, visto che $x_1$ in questo caso è proprio $x$.

Esempio pratico

$\mathrm{\exists }x\mathrm{\forall }y\mathrm{\forall }z\mathrm{\exists }u\mathrm{\forall }t\mathrm{\exists }v(\alpha )$

• Cancello $\mathrm{\exists }x$ e dentro $\alpha$ sostituisco le $x$ con delle costanti (che non siano già state utilizzate)

Diventa $\mathrm{\forall }y\mathrm{\forall }z\mathrm{\exists }u\mathrm{\forall }t\mathrm{\exists }v({\alpha }^1)$ (${\alpha }^1$ è la nostra frase dopo aver applicato la sostituzione)

• Salto i due quantificatori $\mathrm{\forall }$ e cancello il $\mathrm{\exists }u$ ricordando di sostituire ogni occorrenza di $u$ in ${\alpha }^1$ con un funtore (che non sia stato già utilizzato) che prende in rassegna le variabili utilizzate precedentemente dai quantificatori $\mathrm{\forall }$. Nel nostro caso sarà $h(z,y)$.

Diventa $\mathrm{\forall }y\mathrm{\forall }z\mathrm{\forall }t\mathrm{\exists }v({\alpha }^2)$ (${\alpha }^2$ è la nostra frase dopo aver applicato la sostituzione $u\to h(z,y)$)

• Rimane solo un ultimo quantificatore esistenziale, lo elimino e sostituisco in ${\alpha }^2$ a tutte le occorrenze di $v$ un funtore che prenda in rassegna tutte le variabili utilizzate dai quantificatori universali utilizzati in precedenza. La sostituzione sarà $v\to i(y,z,t)$.

L'algoritmo terminerà quando i quantificatori saranno tutti del tipo $\mathrm{\forall }$.