Dipendenza dagli assegnamenti: termini

Proposizione: Sia $t$ un termine con $FV(t)=\{x_1,...,x_n\}$, e sia $\cal M$ un modello. Se $e_1$ ed $e_2$ sono due assegnamenti su $\cal M$ tali che

$$ e_1(x_i)=e_2(x_i) \text{ per ogni }x_i\in FV(t) $$

allora $\llbracket t\rrbracket_{\mathcal M}^{e_1}=\llbracket t\rrbracket_{\mathcal M}^{e_2}$.

• Dimostrazione

Dipendenza dagli assegnamenti: formule

Proposizione: Sia $\varphi$ una formula con $FV(\varphi)=\{x_1,...,x_n\}$, e sia $\cal M$ un modello. Se $e_1$ ed $e_2$ sono due assegnamenti su $\cal M$ tali che

$$ e_1(x_i)=e_2(x_i)\text{ per ogni }x_i\in FV (\varphi) $$

allora

$$ (\mathcal M, e_1)\models \varphi \iff (\mathcal M, e_2)\models \varphi $$

• Dimostrazione

Soddisfacibilità

Definizione: Si considerino una formula $\varphi$ (su un alfabeto $A$) e un modello $\cal M$ (per $A$).

• Dato un assegnamento $e$ (su $\cal M$), si dice che $(\cal M, e)$ soddisfa $\varphi$ se $(\cal M, e)\models \varphi$.
• $\varphi$ è soddisfacibile in $\cal M$ se esiste un assegnamento $e$ (su $\cal M$) tale che $(\cal M, e)\models \varphi$.
• Al contrario, $\varphi$ è false in $\cal M$ se non esistono assegnamnti $e$ tali che $(\cal M, e)\models \varphi$.
• $\cal M$ è un modello di $\varphi$ se, per ogni assegnamento $e$, $(\cal M, e)\models \varphi$. Allora, si dice anche che $\varphi$ è vera in $\cal M$, e si scrive $\cal M\models \varphi$.

Osservazione: Se $\varphi$ è una formula chiusa, allora $\varphi$ è soddisfatta da $\cal M$ se e solo se $\cal M$ è un modello di $\varphi$, cioè le definizioni di soddisfacibilità e modello coincidono. Si “giustifica” così l’uso della stessa notazione, $\cal M \models \varphi$, per indicare

• che $\cal M$ soddisfa una formula chiusa $\varphi$
• che $\cal M$ è un modello di una formula (anche non chiusa) $\varphi$