Logic for Computer Scientists/Predicate Logic/Semantics

Definition 4 (Semantics of predicate logic - Interpretation)

An interpretation is a pair $ℐ=(U_{ℐ},A_{ℐ})$, where

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

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

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

• ${ℐ}_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\mathrm{\forall }n\in N_0$
  • $A_1(g)(m,n)=m+n\mathrm{\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."

• ${ℐ}_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 $ℐ=(U,A)$ we write in the following $p^{ℐ}$ 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 $ℐ$ an interpretation for $F$. For terms $t$ which can be composed with symbols from $F$ the value $ℐ(t)$ is given by

• $ℐ(x)=x^{ℐ}$
• $ℐ(f(t_1,\cdots ,t_k))=f^{ℐ}(ℐ(t_1),\cdots ,ℐ(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 $ℐ(F)$ of a formula $F$ is given by

• $ℐ(p(t_1,\cdots ,t_k))=\{\begin{array}{cc}true& \text{ if }(ℐ(t_1),\cdots ,ℐ(t_k))\in p^{ℐ}\\ false& otherwise\end{array}$

• $ℐ(F\wedge G))=\{\begin{array}{cc}true& \text{ if }ℐ(F)=trueandℐ(G)=true\\ false& otherwise\end{array}$
• $ℐ((F\vee G))=\{\begin{array}{cc}true& \text{ if }ℐ(F)=trueorℐ(G)=true\\ false& otherwise\end{array}$

• $ℐ(\mathrm{\neg }F)=\{\begin{array}{cc}true& \text{ if }ℐ(F)=false\\ false& otherwise\end{array}$
• $ℐ(\mathrm{\forall }G)=\{\begin{array}{cc}true& \text{ if for every }d\in U:{ℐ}_{[x/d]}(G)=true\\ false& otherwise\end{array}$
• $ℐ(\mathrm{\exists }G)=\{\begin{array}{cc}true& \text{ if there is a }d\in U:{ℐ}_{[x/d]}(G)=true\\ false& otherwise\end{array}$

where, $f_{[x/d]}(y)=\{\begin{array}{cc}f(y)& \text{ if }x\ne y\\ d& otherwise\end{array}$

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.

$\mathrm{\forall }p\mathrm{\exists }fp(f(x))$

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

Problems

Problem 1 (Predicate)

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

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

Determine the value of following terms and formulae:

1. $ℐ(f(f(x,x),y))$
2. $ℐ(\mathrm{\forall }x\mathrm{\forall }y(p(x,y)\vee p(y,x))$
3. $ℐ(p(x,x)\to p(y,x))$
4. $ℐ(\mathrm{\exists }xp(y,x))$

$◻$

Problem 2 (Predicate)

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

$U_{ℐ}=ℝ$

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

$y^{ℐ}=-1$

Determine the value of following terms and formulae:

$1.ℐ(g(f(x),f(y)))$
$2.ℐ(\mathrm{\forall }xP(f(x)))$
$3.ℐ(\mathrm{\exists }z\mathrm{\forall }x\mathrm{\forall }yE(g(x,y),z))$
$4.ℐ(\mathrm{\forall }y(E(f(x),y)\to P(g(x,y))))$

$◻$

Problem 3 (Predicate)

The following formula is given:

$F=\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }zR(h(h(x,y),z),h(x,h(y,z)))\wedge \mathrm{\exists }x\mathrm{\exists }y\mathrm{\neg }R(h(x,y),h(y,x))$

Indicate a structure $𝒜$, which is a model for $F$ and a structure $ℬ$ which is no model for $F$!
$◻$