LogicaUniPR - Guida Interattiva

Appunti della Professoressa: Capitolo 9 - Logica del Primo Ordine (Logica dei Predicati)

Appunti del Corso: Capitolo 9 - Logica del Primo Ordine (Logica dei Predicati)

Limiti della Logica Proposizionale e Introduzione alla Logica dei Predicati

La logica proposizionale ci permette di analizzare la struttura di argomentazioni basate su come le proposizioni intere sono connesse. Tuttavia, non ci permette di "guardare dentro" le proposizioni per analizzare affermazioni che riguardano oggetti, le loro proprietà e le relazioni tra di essi. Ad esempio, l'argomentazione "Tutti gli uomini sono mortali. Socrate è un uomo. Quindi, Socrate è mortale" è intuitivamente valida, ma la sua validità non può essere catturata trattando le frasi come atomi indivisibili.

La Logica del Primo Ordine (LPO), o Logica dei Predicati, estende la logica proposizionale fornendo un linguaggio più espressivo per parlare di:

  • Oggetti (individui o elementi di un dominio di discorso).
  • Proprietà di questi oggetti (es. "$x$ è pari").
  • Relazioni tra questi oggetti (es. "$x$ è maggiore di $y$").
  • Quantificatori come "per ogni" ($\forall$) e "esiste" ($\exists$).

Sintassi della Logica del Primo Ordine

La sintassi definisce come costruire espressioni corrette (termini e formule) nel linguaggio del primo ordine.

1. Alfabeto del Primo Ordine ($\mathcal{L}_{PO}$)

Un alfabeto del primo ordine include:

  • Simboli di costante: $a, b, c, \dots$ (per denotare specifici oggetti del dominio).
  • Simboli di variabile: $x, y, z, x_1, \dots$ (segnaposto per oggetti generici del dominio).
  • Simboli funzionali: $f^{(n)}, g^{(m)}, \dots$ Ogni simbolo funzionale ha un'arietà (indicata dall'apice) che specifica il numero di argomenti che prende. Ad esempio, $f^{(2)}$ è un simbolo di funzione binaria. Se l'arietà è 0, il simbolo funzionale è di fatto una costante.
  • Simboli predicativi (o di relazione): $P^{(n)}, Q^{(m)}, R^{(j)}, \dots$ Ogni simbolo predicativo ha un'arietà. $P^{(1)}$ è un predicato unario (proprietà), $R^{(2)}$ è un predicato binario (relazione tra due oggetti). Un predicato 0-ario è una variabile proposizionale.
  • Connettivi logici: $\neg, \wedge, \vee, \Rightarrow, \Leftrightarrow$.
  • Quantificatori: $\forall$ (quantificatore universale), $\exists$ (quantificatore esistenziale).
  • Simboli ausiliari: Parentesi $(, )$ e virgole.

Un linguaggio specifico del primo ordine è definito dalla scelta dei suoi simboli di costante, funzionali e predicativi (la sua "segnatura").

2. Termini (TER)

I termini sono espressioni che denotano oggetti del dominio. L'insieme dei termini è definito induttivamente:

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

Esempi di termini (assumendo $a$ costante, $x,y$ variabili, $f^{(1)}$ unaria, $g^{(2)}$ binaria): $a$, $x$, $f(a)$, $g(x, f(y))$, $g(a,x)$.

3. Formule Ben Formate (FBF) del Primo Ordine

Le **Formule Ben Formate (FBF)** sono espressioni che possono avere un valore di verità. L'insieme delle FBF è definito induttivamente:

  1. $\perp$ (e $\top$, se presente) sono FBF (formule atomiche costanti).
  2. Se $P^{(n)}$ è un simbolo predicativo $n$-ario e $t_1, \dots, t_n$ sono termini, allora $P(t_1, \dots, t_n)$ è una FBF. Questa è chiamata formula atomica (o atomo). Un caso particolare è un predicato 0-ario, che è una variabile proposizionale.
  3. Se $A$ e $B$ sono FBF, allora $(\neg A)$, $(A \wedge B)$, $(A \vee B)$, $(A \Rightarrow B)$, $(A \Leftrightarrow B)$ sono FBF.
  4. Se $A$ è una FBF e $x$ è un simbolo di variabile, allora $(\forall x A)$ e $(\exists x A)$ sono FBF.

Esempi di FBF: $P(a)$, $R(x, f(c))$, $(\forall x (P(x) \Rightarrow Q(f(x), y)))$, $(\exists z R(z,z))$.

Variabili Libere e Vincolate

Un'occorrenza di una variabile $x$ in una formula $A$ è detta vincolata se si trova all'interno del raggio d'azione (scope) di un quantificatore $\forall x$ o $\exists x$ in $A$. Altrimenti, l'occorrenza è libera.

  • In $\forall x P(x,y)$, la $x$ in $P(x,y)$ è vincolata, mentre la $y$ è libera.
  • In $(\forall x P(x)) \wedge Q(x)$, la $x$ in $P(x)$ è vincolata, la $x$ in $Q(x)$ è libera.

L'insieme delle variabili libere di un termine $t$, $FV(t)$, è:

  • $FV(c) = \emptyset$ se $c$ è una costante.
  • $FV(x) = \{x\}$ se $x$ è una variabile.
  • $FV(f(t_1, \dots, t_n)) = FV(t_1) \cup \dots \cup FV(t_n)$.

L'insieme delle variabili libere di una FBF $A$, $FV(A)$, è:

  • $FV(\perp) = \emptyset$.
  • $FV(P(t_1, \dots, t_n)) = FV(t_1) \cup \dots \cup FV(t_n)$.
  • $FV((\neg A)) = FV(A)$.
  • $FV((A \bullet B)) = FV(A) \cup FV(B)$ per $\bullet \in \{\wedge, \vee, \Rightarrow, \Leftrightarrow\}$.
  • $FV((\forall x A)) = FV(A) \setminus \{x\}$.
  • $FV((\exists x A)) = FV(A) \setminus \{x\}$.

Una FBF $A$ è detta chiusa o un enunciato (o sentenza) se non contiene variabili libere ($FV(A)=\emptyset$). Solo gli enunciati possono avere un valore di verità definito una volta fissata un'interpretazione per il linguaggio.

Sostituzione di Termini in Formule ($A[t/x]$)

La notazione $A[t/x]$ indica la formula ottenuta da $A$ sostituendo ogni occorrenza *libera* della variabile $x$ con il termine $t$.

È cruciale la nozione di "termine $t$ è libero per $x$ in $A$". Questo significa che nessuna variabile libera in $t$ deve diventare vincolata da un quantificatore in $A$ dopo la sostituzione. Se una variabile libera di $t$ (diciamo $y$) venisse "catturata" da un $\forall y$ o $\exists y$ in $A$, il significato della formula cambierebbe. In tali casi, prima di sostituire, è necessario rinominare le variabili vincolate nella formula $A$ che causerebbero la cattura.

Sia $A = \exists y (x < y)$. Il termine $t = y+1$ non è libero per $x$ in $A$, perché la $y$ in $t$ verrebbe catturata da $\exists y$.
Prima si rinomina: $A' = \exists z (x < z)$. Ora $t$ è libero per $x$ in $A'$, e $A'[t/x] = \exists z (y+1 < z)$.

Semantica della Logica del Primo Ordine

Per dare un significato (valore di verità) alle formule del primo ordine, abbiamo bisogno di più di una semplice valutazione degli atomi come nella logica proposizionale. Necessitiamo di:

1. Struttura (o Modello) $\mathcal{M}$

Una struttura (o modello) $\mathcal{M}$ per un linguaggio del primo ordine $\mathcal{L}_{PO}$ è 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 parla il linguaggio.
  • $I$ (o $\cdot^\mathcal{M}$) è una funzione di interpretazione che assegna un significato ai simboli non logici (costanti, funzioni, predicati) della segnatura del linguaggio:
    • Per ogni simbolo di costante $c$, $I(c)$ (o $c^\mathcal{M}$) è un elemento di $D$.
    • Per ogni simbolo funzionale $f$ di arietà $n$, $I(f)$ (o $f^\mathcal{M}$) è una funzione $n$-aria su $D$, cioè $I(f): D^n \to D$.
    • Per ogni simbolo predicativo $P$ di arietà $n$, $I(P)$ (o $P^\mathcal{M}$) è una relazione $n$-aria su $D$, cioè $I(P) \subseteq D^n$.

Linguaggio con costante $0$, funzione binaria $+$ e predicato binario $<$.
Una possibile struttura $\mathcal{M}_1$: Dominio $D_1 = \mathbb{N}$. Interpretazione $I_1$: $I_1(0)=0 \in \mathbb{N}$, $I_1(+)$ è l'usuale addizione su $\mathbb{N}$, $I_1(<)$ è l'usuale relazione "minore di" su $\mathbb{N}$.
Un'altra struttura $\mathcal{M}_2$: Dominio $D_2 = \{\text{vero, falso}\}$. Interpretazione $I_2$: $I_2(0)=\text{falso}$, $I_2(+)$ è la disgiunzione logica $\vee$, $I_2(<)$ potrebbe essere la relazione $\{(falso, vero)\}$.

2. Ambiente (o Assegnazione di Variabili) $h$

Poiché le formule possono contenere variabili libere, il loro valore di verità dipende anche da come queste variabili sono interpretate. Un ambiente (o assegnazione) $h$ per una struttura $\mathcal{M}$ è una funzione che mappa ogni simbolo di variabile a un elemento del dominio $D$.
$h: VAR \to D$.

Indichiamo con $h[x \mapsto d]$ (o $h[d/x]$) l'ambiente che è identico a $h$ tranne per il fatto che assegna l'elemento $d \in D$ alla variabile $x$.

3. Valutazione dei Termini

Data una struttura $\mathcal{M}=(D,I)$ e un ambiente $h$, il valore (o denotazione) di un termine $t$, 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)$, allora $[[f(t_1, \dots, t_n)]]_{\mathcal{M},h} = I(f)([[t_1]]_{\mathcal{M},h}, \dots, [[t_n]]_{\mathcal{M},h})$.

4. Soddisfazione delle Formule (Verità)

Data una struttura $\mathcal{M}=(D,I)$ e un ambiente $h$, definiamo quando una formula $A$ è soddisfatta (o è vera) in $\mathcal{M}$ sotto $h$, scritto $\mathcal{M}, h \models A$. La definizione è ricorsiva sulla struttura di $A$:

  • $\mathcal{M}, h \models P(t_1, \dots, t_n) \iff ([[[t_1]]_{\mathcal{M},h}, \dots, [[t_n]]_{\mathcal{M},h}) \in I(P)$. (Un atomo è vero se la tupla dei valori dei suoi termini appartiene alla relazione interpretata per il predicato).
  • $\mathcal{M}, h \models \neg A \iff \text{non è vero che } \mathcal{M}, h \models A$.
  • $\mathcal{M}, h \models A \wedge B \iff (\mathcal{M}, h \models A \text{ e } \mathcal{M}, h \models B)$. (Simile per $\vee, \Rightarrow, \Leftrightarrow$).
  • $\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$. (Universale è vero se la formula interna è vera per tutte le possibili assegnazioni della variabile quantificata).
  • $\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$. (Esistenziale è vero se la formula interna è vera per almeno una possibile assegnazione della variabile quantificata).

5. Verità in una Struttura, Validità Logica

  • Un enunciato $A$ (formula senza variabili libere) è vero in una struttura $\mathcal{M}$ (o $\mathcal{M}$ è un modello di $A$), scritto $\mathcal{M} \models A$, se $\mathcal{M}, h \models A$ per ogni (o equivalentemente, per qualche, dato che $h$ non influenza il valore degli enunciati) ambiente $h$.
  • Un enunciato $A$ è logicamente valido (o una verità logica) se è vero in ogni possibile struttura $\mathcal{M}$. Scritto $\models A$.
  • Un enunciato $A$ è soddisfacibile se esiste almeno una struttura $\mathcal{M}$ in cui è vero (cioè, se ha almeno un modello).
  • Un enunciato $A$ è contraddittorio se non è vero in alcuna struttura (non ha modelli).
  • $\Gamma \models A$ (A è conseguenza logica dell'insieme di enunciati $\Gamma$) se ogni modello di $\Gamma$ (struttura che rende veri tutti gli enunciati in $\Gamma$) è anche un modello di $A$.