Valuation Function (Logic)

logic

Definition

Valuation Function

The valuation function ${\mathrm{val}}_{I,\sigma }$ assigns a value to terms and formulas based on a given interpretation $I$ and a variable assignment $\sigma$.

Evaluation of Terms

For a term $t$, the value ${\mathrm{val}}_{I,\sigma }(t)\in \mathcal{U}$ is defined recursively:

• ${\mathrm{val}}_{I,\sigma }(x)=\sigma (x)$ for a variable $x$.
• ${\mathrm{val}}_{I,\sigma }(f(t_1,\dots ,t_n))=f^I({\mathrm{val}}_{I,\sigma }(t_1),\dots ,{\mathrm{val}}_{I,\sigma }(t_n))$ for a function symbol $f$.

Evaluation of Formulas

For a formula $F$, the value ${\mathrm{val}}_{I,\sigma }(F)\in \{0,1\}$ is defined inductively:

• ${\mathrm{val}}_{I,\sigma }(P(t_1,\dots ,t_n))=1⟺({\mathrm{val}}_{I,\sigma }(t_1),\dots ,{\mathrm{val}}_{I,\sigma }(t_n))\in P^I$.
• ${\mathrm{val}}_{I,\sigma }(\neg F)=1-{\mathrm{val}}_{I,\sigma }(F)$.
• ${\mathrm{val}}_{I,\sigma }(F\wedge G)=\min ({\mathrm{val}}_{I,\sigma }(F),{\mathrm{val}}_{I,\sigma }(G))$.
• ${\mathrm{val}}_{I,\sigma }(\forall xF)=1⟺\forall {\sigma }^{\prime }\stackrel{x}{\sim }\sigma :{\mathrm{val}}_{I,{\sigma }^{\prime }}(F)=1$.
• ${\mathrm{val}}_{I,\sigma }(\exists xF)=1⟺\exists {\sigma }^{\prime }\stackrel{x}{\sim }\sigma :{\mathrm{val}}_{I,{\sigma }^{\prime }}(F)=1$.