LogicaUniPR - Guida Interattiva

9.1 Sintassi della Logica del Primo Ordine: Costruire il Linguaggio

Come per la logica proposizionale, iniziamo definendo l'alfabeto e le regole per costruire espressioni sintatticamente corrette: i termini e le formule ben formate (FBF).

9.1.1 L'Alfabeto di un Linguaggio del Primo Ordine ($\mathcal{L}$)

Un linguaggio del primo ordine $\mathcal{L}$ è costruito a partire da un alfabeto che include diverse categorie di simboli:

1. Simboli Logici (comuni a tutti i linguaggi del primo ordine):
   • Variabili: $x, y, z, x_0, x_1, \dots$ (un insieme numerabile di simboli usati come segnaposto per oggetti).
   • Connettivi proposizionali: $\neg, \wedge, \vee, \Rightarrow, \Leftrightarrow$.
   • Quantificatori: $\forall$ (quantificatore universale, "per ogni"), $\exists$ (quantificatore esistenziale, "esiste").
   • Simboli ausiliari: Parentesi $(, )$ e talvolta la virgola.
   • (Opzionale) Simbolo di uguaglianza: $=$ (se l'uguaglianza è trattata come simbolo logico).
   • (Opzionale) Costanti logiche: $\perp$ (falso), $\top$ (vero).
2. Simboli Non Logici (specifici per un particolare linguaggio $\mathcal{L}$), che costituiscono la sua "segnatura":
   • Simboli di costante: $a, b, c, \text{zero}, \text{pippo}, \dots$ (denotano specifici oggetti del dominio di discorso).
   • Simboli di funzione: $f, g, h, \text{somma}, \text{successore}, \dots$. Ogni simbolo di funzione $f$ ha un'arietà $n \ge 1$ (indicata a volte come $f^{(n)}$), che è il numero di argomenti che la funzione prende. Una funzione 0-aria è, di fatto, una costante.
   • Simboli di predicato (o di relazione): $P, Q, R, \text{MaggioreDi}, \text{Pari}, \dots$. Ogni simbolo di predicato $P$ ha un'arietà $n \ge 0$. $P^{(1)}$ è un predicato unario (esprime una proprietà), $R^{(2)}$ è un predicato binario (esprime una relazione tra due oggetti). Un predicato 0-ario ($P^{(0)}$) è una variabile proposizionale della logica proposizionale.

La scelta dei simboli non logici (costanti, funzioni, predicati) definisce un particolare linguaggio del primo ordine, adatto a parlare di un certo dominio (es. l'aritmetica, la teoria degli insiemi, database specifici).

9.1.2 Termini: Denotare Oggetti

I termini sono le espressioni del nostro linguaggio che "nominano" o "si riferiscono a" oggetti del dominio di discorso. L'insieme dei termini ($TER_{\mathcal{L}}$) è definito induttivamente:

1. Ogni variabile $x$ è un termine.
2. Ogni simbolo di costante $c$ è un termine.
3. Se $f^{(n)}$ è un simbolo di funzione $n$-ario e $t_1, t_2, \dots, t_n$ sono termini, allora $f(t_1, t_2, \dots, t_n)$ è un termine.

Esempio: Se abbiamo la costante $0$, la funzione unaria $s(x)$ (successore) e la funzione binaria $+(x,y)$ (somma):
Sono termini: $x$, $0$, $s(0)$, $s(x)$, $+(x,y)$ (spesso scritto $x+y$), $s(+(s(0), x))$.
Non sono termini: $P(x)$ (è una formula), $s(P(x))$.

Un termine è chiuso (o ground) se non contiene variabili.

9.1.3 Formule Ben Formate (FBF): Esprimere Affermazioni

Le Formule Ben Formate (FBF) sono le espressioni del linguaggio che possono essere vere o false, cioè che esprimono affermazioni sugli oggetti del dominio. L'insieme delle FBF ($FORM_{\mathcal{L}}$) è definito induttivamente:

1. Formule Atomiche (Atomi):
   • Se $P^{(n)}$ è un simbolo di predicato $n$-ario e $t_1, t_2, \dots, t_n$ sono termini, allora $P(t_1, t_2, \dots, t_n)$ è una FBF (un atomo).
   • Se l'uguaglianza $=$ è nel linguaggio, e $t_1, t_2$ sono termini, allora $(t_1 = t_2)$ è una FBF (un atomo).
   • $\perp$ e $\top$ (se presenti) sono FBF (atomi).
2. Formule Composte:
   • Se $A$ è una FBF, allora $(\neg A)$ è una FBF.
   • Se $A$ e $B$ sono FBF, allora $(A \wedge B)$, $(A \vee B)$, $(A \Rightarrow B)$, $(A \Leftrightarrow B)$ sono FBF.
   • Se $A$ è una FBF e $x$ è una variabile, allora $(\forall x A)$ e $(\exists x A)$ sono FBF.

Esempio: Usando i simboli dell'esempio precedente e i predicati $Pari^{(1)}$ e $Maggiore^{(2)}$:
Sono FBF: $Pari(s(0))$, $Maggiore(x,0)$, $(Pari(x) \Rightarrow Maggiore(x,0))$, $\forall x (Pari(x) \Rightarrow \exists y (x = y+y))$.
Non è FBF: $\forall x (x)$ (manca un predicato).

9.2 Variabili Libere e Vincolate: Lo "Scope" dei Quantificatori

In una formula del primo ordine, le variabili possono giocare ruoli diversi.

• Un'occorrenza di una variabile $x$ in una formula $F$ è vincolata se si trova all'interno del "raggio d'azione" (scope) di un quantificatore $\forall x$ o $\exists x$ presente in $F$. Il quantificatore "lega" quella variabile.
• Un'occorrenza di una variabile $x$ è libera se non è vincolata da alcun quantificatore in $F$.

Nella formula $F = (\forall x (P(x) \Rightarrow Q(y))) \wedge R(x)$:

• La $x$ in $P(x)$ è vincolata dal $\forall x$.
• La $y$ in $Q(y)$ è libera.
• La $x$ in $R(x)$ è libera (il $\forall x$ iniziale ha il suo scope limitato alla sottoformula $(P(x) \Rightarrow Q(y))$).

L'insieme delle variabili libere di una formula $F$ si denota con $FV(F)$.

• $FV(P(t_1, \dots, t_n)) = FV(t_1) \cup \dots \cup FV(t_n)$ (le variabili libere di un atomo sono quelle libere nei suoi termini).
• $FV(\neg A) = FV(A)$.
• $FV(A \bullet B) = FV(A) \cup FV(B)$ (per i connettivi binari).
• $FV(\forall x A) = FV(A) \setminus \{x\}$ (il quantificatore lega $x$).
• $FV(\exists x A) = FV(A) \setminus \{x\}$.

Una FBF $F$ è detta chiusa o un enunciato (o sentenza) se non contiene variabili libere, cioè $FV(F) = \emptyset$. Solo gli enunciati possono essere considerati veri o falsi in modo assoluto una volta che si fissa un'interpretazione per i simboli non logici. Le formule con variabili libere hanno un valore di verità che dipende dall'assegnazione di valori a tali variabili.

9.3 Sostituzione di Termini in Formule: $A[t/x]$

La notazione $A[t/x]$ indica la formula che si ottiene da $A$ sostituendo tutte le occorrenze libere della variabile $x$ con il termine $t$.

Attenzione alla "Cattura di Variabili": La sostituzione deve essere fatta con cautela. Un termine $t$ è detto libero per $x$ in $A$ (o "sostituibile per $x$ in $A$") se nessuna variabile libera che occorre in $t$ diventa vincolata da un quantificatore in $A$ dopo la sostituzione. Se una variabile $y$ in $t$ venisse "catturata" da un $\forall y$ o $\exists y$ già presente in $A$ (e il cui scope include l'occorrenza di $x$ che stiamo sostituendo), il significato della formula cambierebbe drasticamente e in modo errato.

Se $t$ non è libero per $x$ in $A$, è necessario prima rinominare le variabili vincolate in $A$ che causerebbero la cattura, scegliendo nomi di variabili "freschi" che non compaiono né in $A$ né in $t$.

Sia $A = \exists y (x=y)$. Vogliamo calcolare $A[y/x]$.
Il termine $t=y$ non è libero per $x$ in $A$, perché la $y$ di $t$ verrebbe catturata da $\exists y$.
1. Rinominiamo la variabile vincolata in $A$: $A' = \exists z (x=z)$.
2. Ora $y$ è libero per $x$ in $A'$.
3. $A'[y/x] = \exists z (y=z)$.
Se avessimo sostituito direttamente: $\exists y (y=y)$, che ha un significato diverso (è una tautologia in molte strutture, mentre $\exists z (y=z)$ afferma che $y$ è nel dominio).

9.4 Semantica della Logica del Primo Ordine: Interpretare le Formule

Per dare un significato (valore di verità) alle formule del primo ordine, non basta un'assegnazione di verità agli atomi. Dobbiamo specificare un "mondo" o "contesto" in cui interpretare i simboli.

9.4.1 Strutture (o Modelli) $\mathcal{M}$

Una struttura (o modello) $\mathcal{M}$ per un linguaggio del primo ordine $\mathcal{L}$ è una coppia $\mathcal{M} = (D, I)$, dove:

• $D$ (o $|\mathcal{M}|$) è un insieme non vuoto chiamato dominio (o universo del discorso). È l'insieme degli oggetti di cui stiamo parlando.
• $I$ (o $\cdot^\mathcal{M}$) è una funzione di interpretazione che assegna un significato concreto ai simboli non logici (costanti, funzioni, predicati) della segnatura del linguaggio $\mathcal{L}$:
  • Per ogni simbolo di costante $c$ di $\mathcal{L}$, $I(c)$ (o $c^\mathcal{M}$) è un elemento specifico del dominio $D$.
  • Per ogni simbolo di funzione $f$ di arietà $n$ di $\mathcal{L}$, $I(f)$ (o $f^\mathcal{M}$) è una funzione effettiva $n$-aria sul dominio $D$, cioè $I(f): D^n \to D$.
  • Per ogni simbolo di predicato $P$ di arietà $n$ di $\mathcal{L}$, $I(P)$ (o $P^\mathcal{M}$) è una relazione effettiva $n$-aria sul dominio $D$, cioè $I(P) \subseteq D^n$. (Un sottoinsieme di $D^n$ che specifica quali tuple di elementi del dominio soddisfano il predicato).

Consideriamo un linguaggio con una costante $0$, una funzione unaria $s$ (successore), e un predicato binario $P$ (minore).
Una possibile struttura $\mathcal{M}_{nat}$ (per i naturali):

• Dominio $D_{nat} = \mathbb{N} = \{0, 1, 2, \dots\}$.
• Interpretazione $I_{nat}$: $I_{nat}(0) = 0 \in \mathbb{N}$; $I_{nat}(s)$ è la funzione $s(n)=n+1$; $I_{nat}(P)$ è la relazione $\{(n,m) \in \mathbb{N} \times \mathbb{N} \mid n < m\}$.

9.4.2 Assegnazione di Variabili (o Ambiente) $h$

Per interpretare formule che contengono variabili libere, abbiamo bisogno di un'assegnazione di variabili (o ambiente) $h$, che è una funzione che mappa ogni variabile del linguaggio a un elemento del dominio $D$ della struttura $\mathcal{M}$.

$h: VAR \to D$.

Con $h[x \mapsto d]$ si indica un nuovo ambiente che è identico a $h$ tranne per il fatto che assegna l'elemento $d \in D$ alla variabile $x$.

9.4.3 Valutazione dei Termini

Data una struttura $\mathcal{M}=(D,I)$ e un ambiente $h$, il valore (o denotazione) di un termine $t$ in $\mathcal{M}$ sotto $h$, scritto $[[t]]^{\mathcal{M},h}$ (o $t^{\mathcal{M},h}$), è un elemento del dominio $D$. È definito ricorsivamente:

• Se $t$ è una variabile $x$: $[[x]]^{\mathcal{M},h} = h(x)$.
• Se $t$ è una costante $c$: $[[c]]^{\mathcal{M},h} = I(c)$.
• Se $t$ è $f(t_1, \dots, t_n)$: $[[f(t_1, \dots, t_n)]]^{\mathcal{M},h} = I(f)([[t_1]]^{\mathcal{M},h}, \dots, [[t_n]]^{\mathcal{M},h})$. (Si applica la funzione interpretata ai valori interpretati degli argomenti).

9.4.4 Soddisfazione delle Formule (Verità in una Struttura sotto un Ambiente)

Definiamo quando una formula $A$ è soddisfatta (o è vera) in una struttura $\mathcal{M}$ sotto un ambiente $h$. Scriviamo $\mathcal{M}, h \models A$. La definizione è ricorsiva:

• $\mathcal{M}, h \models P(t_1, \dots, t_n) \iff \text{la tupla } ([[t_1]]^{\mathcal{M},h}, \dots, [[t_n]]^{\mathcal{M},h}) \text{ appartiene alla relazione } I(P)$.
• $\mathcal{M}, h \models (t_1 = t_2) \iff [[t_1]]^{\mathcal{M},h} \text{ è lo stesso elemento di } [[t_2]]^{\mathcal{M},h}$.
• $\mathcal{M}, h \models \neg A \iff \text{non è vero che } \mathcal{M}, h \models A$ (scritto $\mathcal{M}, h \not\models A$).
• $\mathcal{M}, h \models A \wedge B \iff \mathcal{M}, h \models A \text{ e } \mathcal{M}, h \models B$. (Analogamente per $\vee, \Rightarrow, \Leftrightarrow$, seguendo le tavole di verità).
• $\mathcal{M}, h \models \forall x A \iff \text{per ogni elemento } d \in D, \text{ si ha che } \mathcal{M}, h[x \mapsto d] \models A$.
• $\mathcal{M}, h \models \exists x A \iff \text{esiste almeno un elemento } d \in D \text{ tale che } \mathcal{M}, h[x \mapsto d] \models A$.

9.4.5 Verità, Validità, Modelli e Conseguenza Logica in LPO

• Un enunciato $A$ (formula chiusa) è vero in una struttura $\mathcal{M}$ (e $\mathcal{M}$ è detto un modello di $A$), scritto $\mathcal{M} \models A$, se $\mathcal{M}, h \models A$ per un qualsiasi (e quindi per tutti, dato che non ci sono variabili libere) ambiente $h$.
• Un enunciato $A$ è logicamente valido (o una verità logica) se è vero in ogni possibile struttura $\mathcal{M}$ per il linguaggio. Scritto $\models A$.
• Un enunciato $A$ è soddisfacibile se esiste almeno una struttura $\mathcal{M}$ in cui è vero (cioè, $A$ ha almeno un modello).
• Un enunciato $A$ è contraddittorio (o insoddisfacibile) se non è vero in alcuna struttura (cioè non ha modelli).
• Un enunciato $A$ è una conseguenza logica di un insieme di enunciati $\Gamma$, scritto $\Gamma \models A$, se $A$ è vero in ogni struttura $\mathcal{M}$ che è un modello per tutti gli enunciati in $\Gamma$.

A differenza della logica proposizionale, non esiste un metodo generale (come le tavole di verità) per decidere in un numero finito di passi se una formula del primo ordine è logicamente valida (problema della decidibilità, Teorema di Church-Turing).

9.5 Esercizi del Capitolo 9