Logic for Computer Scientists/Predicate Logic/Semantics

Definition 4 (Semantics of predicate logic - Interpretation)

An interpretation is a pair ${\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})$, where

• $U_{\mathcal {I}}$ is an arbitrary nonempty set, called domain, or universe.
• $A_{\mathcal {I}}$ is a mapping which associates to
  • a $k$-ary predicate symbol, a $k$-ary predicate over $U_{\mathcal {I}}$,
  • a $k$-ary function symbol, a $k$-ary function over $U_{\mathcal {I}}$, and
  • a variable an element from the domain.

Let $F$ be a formula and ${\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})$ be an interpretation. We call ${\mathcal {I}}$ an interpretation for $F$, if ${\mathcal {A}}_{\mathcal {I}}$ is defined for every predicate and function symbol, and for every variable, that occurs free in $F$ .

Example: Let $F=\forall xp(x,f(x))\land q(g(a,z))$ and assume the varieties of the symbols as written down. In the following we give two interpretations for $F$:

• ${\mathcal {I}}_{1}=(N_{0},A_{1})$, such that
  • $A_{1}(p)=\{(m,n)\mid m,n\in N_{0}{\text{ and }}m<n\}$
  • $A_{1}(q)=\{n\in N_{0}\mid n{\text{ is prime}}\}$
  • $A_{1}(f)(n)=n+1\;\forall n\in N_{0}$
  • $A_{1}(g)(m,n)=m+n\;\forall n,m\in N_{0}$
  • $A_{1}(a)=2$
  • $A_{1}(z)=3$

  Under this interpretation the formula $F$ can be read as " Every natural number is smaller than its successor and the sum of $2$ and $3$ is a prime number."

• ${\mathcal {I}}_{2}=(U_{2},A_{2})$, such that
  • $U_{2}=\{a,f(a),g(a,a),f(g(a,a)),g(f(a),f(a)),\cdots \}$
  • $A_{2}(f)(t)=f(t)$ for $t\in U_{2}$
  • $A_{2}(g)(t_{1},t_{2})=g(t_{1},t_{2})$, if $t_{1},t_{2}\in U_{2}$
  • $A_{2}(a)=a$
  • $A_{2}(z)=f(f(a))$
  • $A_{2}(p)=\{p(a,a),p(f(a),f(a)),p(f(f(a)),f(f(a)))\}$
  • $A_{2}(q)=\{g(t_{1},t_{2})\mid t_{1},t_{2}\in U_{2}\}$

For a given interpretation ${\mathcal {I}}=(U,A)$ we write in the following $p^{\mathcal {I}}$ instead of $A(p)$; the same abbreviation will be used for the assignments for function symbols and variables.

Definition 5 (Semantics of predicate logic - Evaluation of Formulae)

Let $F$ be a formula and ${\mathcal {I}}$ an interpretation for $F$. For terms $t$ which can be composed with symbols from $F$ the value ${\mathcal {I}}(t)$ is given by

• ${\mathcal {I}}(x)=x^{\mathcal {I}}$
• ${\mathcal {I}}(f(t_{1},\cdots ,t_{k}))=f^{\mathcal {I}}({\mathcal {I}}(t_{1}),\cdots ,{\mathcal {I}}(t_{k}))$, if $t_{1},\cdots ,t_{k}$ are terms and $f$ a $k$-ary function symbol. (This holds for the case $k=0$ as well.)

The value ${\mathcal {I}}(F)$ of a formula $F$ is given by

• ${\mathcal {I}}(p(t_{1},\cdots ,t_{k}))={\begin{cases}\;\;\,true&{\text{ if }}({\mathcal {I}}(t_{1}),\cdots ,{\mathcal {I}}(t_{k}))\in p^{\mathcal {I}}\\\;\;\,false&\;otherwise\end{cases}}$

• ${\mathcal {I}}(F\land G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{and}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}$
• ${\mathcal {I}}((F\lor G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{or}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {I}}(\lnot F)={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=false\\\;\;\,false&otherwise\end{cases}}$
• ${\mathcal {I}}(\forall G)={\begin{cases}\;\;\,true&{\text{ if for every }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}$
• ${\mathcal {I}}(\exists G)={\begin{cases}\;\;\,true&{\text{ if there is a }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}$

where, $f_{[x/d]}(y)={\begin{cases}\;\;\,f(y)&{\text{ if }}x\neq y\\\;\;\,d&otherwise\end{cases}}$

The notions of satisfiable, valid, and $\models$ are defined according to the propositional case (Semantic (Propositional logic)).

Note that, predicate calculus is an extension of propositional calculus: Assume only $0$-ary predicate symbols and a formula which contains no variable, i.e. there can be no terms and no quantifier in a well-formed formula.

On the other hand, predicate calculus can be extended: If one allows for quantifications over predicate and function symbols, we arrive at a second order predicate calculus. E.g.

$\forall p\exists f\;p(f(x))$

Another example for a second order formula of is the induction principle from Induction.

Problems

Problem 1 (Predicate)

The interpretation ${\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})$ as follows:

$U_{\mathcal {I}}=\mathbb {N}$
$p^{\mathcal {I}}={(m,n)\mid m<n}$
$f^{\mathcal {I}}(m,n)=m+n$
$x^{\mathcal {I}}=5;y^{\mathcal {I}}=7$

Determine the value of following terms and formulae:

1. ${\mathcal {I}}(f(f(x,x),y))$
2. ${\mathcal {I}}(\forall x\forall y(p(x,y)\lor p(y,x))$
3. ${\mathcal {I}}(p(x,x)\to p(y,x))$
4. ${\mathcal {I}}(\exists xp(y,x))$

$\Box$

Problem 2 (Predicate)

The interpretation ${\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})$ as follows:

$U_{\mathcal {I}}=\mathbb {R}$

$P^{\mathcal {I}}={z\mid z\geq 0}$
$f^{\mathcal {I}}(z)=z^{2}$
$x^{\mathcal {I}}={\sqrt {2}}$
$E^{\mathcal {I}}={(x,y)\mid x=y}$
$g^{\mathcal {I}}(x,y)=x+y$

$y^{\mathcal {I}}=-1$

Determine the value of following terms and formulae:

$1.{\mathcal {I}}(g(f(x),f(y)))$
$2.{\mathcal {I}}(\forall x\,P(f(x)))$
$3.{\mathcal {I}}(\exists z\forall x\forall y\,E(g(x,y),z))$
$4.{\mathcal {I}}(\forall y(E(f(x),y)\to P(g(x,y))))$

$\Box$

Problem 3 (Predicate)

The following formula is given:

$F=\forall x\forall y\forall z\,R(h(h(x,y),z),h(x,h(y,z)))\ \land \ \exists x\exists y\,\lnot R(h(x,y),h(y,x))$

Indicate a structure ${\mathcal {A}}$, which is a model for $F$ and a structure ${\mathcal {B}}$ which is no model for $F$!
$\Box$