# Interpretazione (logica)

Un'interpretazione è l'assegnazione di un significato ai simboli di un linguaggio formale. Molti linguaggi formali usati in matematica, logica e informatica teorica sono definiti esclusivamente in termini sintattici e come tali non hanno alcun significato fino a quando non vengono interpretati. Lo studio generale delle interpretazioni dei linguaggi formali è chiamato semantica formale.
Le logiche formali più comunemente studiate sono la logica proposizionale, la logica dei predicati (e i loro analoghi modali), per le quali esistono modi standard di attribuire un'interpretazione. In questi contesti l'interpretazione è una funzione che fornisce l'estensione di simboli e stringhe di simboli di un linguaggio in oggetto. Ad esempio, una funzione di interpretazione potrebbe prendere il predicato A (per "alto") e assegnargli l'estensione { a } (per "Alice"). Si noti che tutto ciò che questa interpretazione fa è assegnare l'estensione {a} alla costante non logica A, e non afferma che A stia per "alto" e a per Alice.
Un'interpretazione spesso (ma non sempre) fornisce un modo per determinare i valori di verità delle formule in un linguaggio. Se una data interpretazione assegna il valore "vero" a una proposizione o teoria, l'interpretazione è chiamata modello di quella proposizione o teoria.
Il concetto di interpretazione è fondamentale per definire la soddisfacibilità di una formula, ovvero l'esistenza di almeno un modello per la stessa.

## Linguaggi formali

Un linguaggio formale consiste in un insieme possibilmente infinito di proposizioni costruito da un insieme fisso di lettere o simboli. L'inventario da cui vengono prese queste lettere è chiamato alfabeto su cui è definita la lingua. Per distinguere le stringhe di simboli che appartengono ad un linguaggio formale da stringhe arbitrarie di simboli, le prime sono talvolta chiamate formule ben formate (FBF). La caratteristica essenziale di un linguaggio formale è che la sua sintassi può essere definita senza riferimento all'interpretazione. Ad esempio, possiamo determinare che $(P\ or\ Q)$ è una formula ben formata anche senza sapere se è vera o falsa.

### Esempio

Un linguaggio formale ${\mathcal {W}}$ può essere definito con l'alfabeto $\alpha =\{\triangle ,\square \}$ e con una parola (detta appartenente a ${\mathcal {W}}$) se essa inizia con $\triangle$ ed è composta esclusivamente dai simboli contenuti in $\alpha$ ($\triangle$ e $\square$).
Una possibile interpretazione di ${\mathcal {W}}$ potrebbe assegnare la cifra decimale "1" a $\triangle$ e da "0" a $\square$. Poi $\triangle \square \triangle$ denoterebbe 101 sotto questa interpretazione di ${\mathcal {W}}$.

### Costanti logiche

Nei casi specifici di logica proposizionale e logica dei predicati, i linguaggi formali considerati hanno alfabeti che si dividono in due insiemi: i simboli logici (costanti logiche) e i simboli non logici. L'idea alla base di questa terminologia è che i simboli logici hanno lo stesso significato indipendentemente dal campo di studio, mentre i simboli non logici possono assumere significati diversi in base all'argomento trattato.
Le costanti logiche includono simboli quantificatori ∀ (universale) e ∃ (esistenziale), simboli per connettivi logici ∧ ("e"), ∨ ("o"), ¬ ("non"), parentesi e altri simboli di raggruppamento, e (in alcuni acsi) il simbolo di uguaglianza =.

### Semantica dei connettivi logici

La funzione di interpretazione risulta utile, ad esempio, per definire la semantica degli operatori logici. In questo contesto, l'interpretazione di un simbolo è una funzione che, dato un certo simbolo, ritorna un valore "vero" o "falso".
Ecco come definiamo i connettivi logici nella logica proposizionale:
* ¬Φ è vero se e solo se Φ è falso.
* (Φ ∧ Ψ) è vero se e solo se Φ è vero e Ψ è vero.
* (Φ ∨ Ψ) è vero se e solo se Φ è vero o Ψ è vero (o entrambi sono veri).
* (Φ → Ψ) è vero se e solo se Φ è falso o Ψ è vero (o entrambi sono veri).
* (Φ ↔ Ψ) è vero se e solo se (Φ → Ψ) è vero e (Ψ → Φ) è vero.
Quindi, data una certa interpretazione delle lettere Φ e Ψ (cioè, dopo aver assegnato un valore di verità a ciascuna lettera della proposizione), possiamo determinare i valori di verità di tutte le formule contenenti le due lettere, in funzione dei connettivi logici utilizzati. Nella tabella seguente, la seconda e la terza colonna mostrano i valori di verità delle lettere (con tutte e quattro le possibili interpretazioni). Le altre colonne mostrano i valori di verità delle formule costruite con queste lettere.
Connettivi logici :
| Interpretazione | Φ | Ψ | ¬Φ | (Φ ∧ Ψ) | (Φ ∨ Ψ) | (Φ → Ψ) | (Φ ↔ Ψ) |
| # 1 | T | T | F | T | T | T | T |
| # 2 | T | F | F | F | T | F | F |
| # 3 | F | T | T | F | T | T | F |
| # 4 | F | F | T | F | F | T | T |
Ora risulta più semplice controllare cosa rende una formula logicamente valida. Prendamo la formula $F:\Phi \lor \neg \Phi$. Se la nostra funzione di interpretazione rende Φ vero, allora ¬Φ è reso falso dal connettivo di negazione. Poiché la disgiunzione Φ di F è vera sotto quell'interpretazione, F è vera. Ora l'unica altra interpretazione possibile di Φ lo rende falso, e in tal caso ¬Φ è reso vero dalla funzione di negazione. Ciò renderebbe F nuovamente vera, poiché uno dei simboli di F, ¬Φ, sarebbe vero sotto questa interpretazione. Poiché queste due interpretazioni per F sono le uniche interpretazioni logiche possibili, e poiché F risulta vera per entrambe, diciamo che è logicamente valida o tautologica.

## Logica proposizionale

Un linguaggio formale nella logica proposizionale consiste di formule costruite a partire da simboli proposizionali (o variabili proposizionali) e connettivi logici. Gli unici simboli "non logici" in un linguaggio formale sono le variabili proposizionali, che sono spesso indicate con lettere maiuscole.
In questo contesto, l'interpretazione è solitamente effettuata mediante una funzione che mappa ogni simbolo proposizionale ad un valore di verità vero o falso. Questa funzione viene anche detta funzione di valutazione.
Per un linguaggio con n variabili proposizionali distinti esistono $2^{n}$ possibili interpretazioni distinte. Per ogni variabile a in particolare, ad esempio, ci sono $2^{1}=2$ possibili interpretazioni: possiamo infatti assegnare ad a il valore T (vero) o F (falso). Per la coppia di variabili $\langle a,b\rangle$ esistono $2^{2}=4$ possibili interpretazioni: 1) assegniamo ad entrambe il valore T, 2) assegniamo ad entrambe il valore F, 3) assegniamo T ad a e F a b, or 4) assegniamo F ad a e T a b. E così via.

## Logica del primo ordine

Per conferire un significato ad un certo linguaggio del primo ordine, dato un certo dominio $D$ (generalmente richiesto essere non vuoto), facciamo uso delle seguenti interpretazioni:
* interpretazione dei simboli costanti: ad ogni simbolo costante si associa un elemento $c^{\mathcal {I}}\in D$;
* interpretazione dei simboli di funzione: ad ogni simbolo di funzione n-ario si associa una funzione $f^{\mathcal {I}}:D^{n}\rightarrow D$;
* interpretazione dei simboli di predicato: ad ogni simbolo di predicato n-ario si associa una relazione $R^{\mathcal {I}}\subseteq D^{n}$.
Un oggetto ${\mathfrak {A}}=\langle D,{\mathcal {I}}\rangle$ contenente tali informazioni è detto struttura. Tale struttura è detta modello di una certa formula $\phi$ se ${\mathfrak {A}}\models \phi$, ovvero se $\phi$ è vera in ${\mathfrak {A}}$.

### Esempio

Definiamo un possibile linguaggio L, avente come simboli costanti $a$, $b$ e $c$; predicati $F$, $G$, $H$, $I$ e $J$; e variabili $x$, $y$ e $z$.
Un esempio di interpretazione ${\mathcal {I}}$ del linguaggio L è la seguente:
* Dominio: i pezzi degli scacchi
* Costanti individuali: $a$: il re bianco; $b$: la regina nera; $c$: un certo pedone bianco
* $F(x)$: $x$ è un pezzo
* $G(x)$: $x$ è un pedone
* $H(x)$: $x$ è nero
* $I(x)$: $x$ è bianco
* $J(x,y)$: $x$ può mangiare $y$
Nell'interpretazione di cui sopra:
* le seguenti proposizioni sono vere: $F(a)$, $G(c)$, $H(b)$, $I(a)$, $J(b,c)$;
* le seguenti proposizioni sono false: $J(a,c)$, $G(a)$, $I(b)$.
La struttura ${\mathfrak {A}}=\langle D,{\mathcal {I}}\rangle$ è un modello di tutte le proposizioni vere di cui sopra. Per esempio, abbiamo che ${\mathfrak {A}}\models J(b,c)$.