# Logic for Computer Scientists/Predicate Logic/Semantics

## Definition 4 (Semantics of predicate logic - Interpretation)

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

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

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

Example: Let ${\displaystyle 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 ${\displaystyle F}$:

• ${\displaystyle {\mathcal {I}}_{1}=(N_{0},A_{1})}$, such that
• ${\displaystyle A_{1}(p)=\{(m,n)\mid m,n\in N_{0}{\text{ and }}m
• ${\displaystyle A_{1}(q)=\{n\in N_{0}\mid n{\text{ is prime}}\}}$
• ${\displaystyle A_{1}(f)(n)=n+1\;\forall n\in N_{0}}$
• ${\displaystyle A_{1}(g)(m,n)=m+n\;\forall n,m\in N_{0}}$
• ${\displaystyle A_{1}(a)=2}$
• ${\displaystyle A_{1}(z)=3}$
Under this interpretation the formula ${\displaystyle F}$ can be read as " Every natural number is smaller than its successor and the sum of ${\displaystyle 2}$ and ${\displaystyle 3}$ is a prime number."
• ${\displaystyle {\mathcal {I}}_{2}=(U_{2},A_{2})}$, such that
• ${\displaystyle U_{2}=\{a,f(a),g(a,a),f(g(a,a)),g(f(a),f(a)),\cdots \}}$
• ${\displaystyle A_{2}(f)(t)=f(t)}$ for ${\displaystyle t\in U_{2}}$
• ${\displaystyle A_{2}(g)(t_{1},t_{2})=g(t_{1},t_{2})}$, if ${\displaystyle t_{1},t_{2}\in U_{2}}$
• ${\displaystyle A_{2}(a)=a}$
• ${\displaystyle A_{2}(z)=f(f(a))}$
• ${\displaystyle A_{2}(p)=\{p(a,a),p(f(a),f(a)),p(f(f(a)),f(f(a)))\}}$
• ${\displaystyle A_{2}(q)=\{g(t_{1},t_{2})\mid t_{1},t_{2}\in U_{2}\}}$

For a given interpretation ${\displaystyle {\mathcal {I}}=(U,A)}$ we write in the following ${\displaystyle p^{\mathcal {I}}}$ instead of ${\displaystyle 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 ${\displaystyle F}$ be a formula and ${\displaystyle {\mathcal {I}}}$ an interpretation for ${\displaystyle F}$. For terms ${\displaystyle t}$ which can be composed with symbols from ${\displaystyle F}$ the value ${\displaystyle {\mathcal {I}}(t)}$ is given by

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

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

• ${\displaystyle {\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}}}$

• ${\displaystyle {\mathcal {I}}(F\land G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{and}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}}$
• ${\displaystyle {\mathcal {I}}((F\lor G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{or}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}}$
• ${\displaystyle {\mathcal {I}}(\lnot F)={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=false\\\;\;\,false&otherwise\end{cases}}}$
• ${\displaystyle {\mathcal {I}}(\forall G)={\begin{cases}\;\;\,true&{\text{ if for every }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}}$
• ${\displaystyle {\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, ${\displaystyle f_{[x/d]}(y)={\begin{cases}\;\;\,f(y)&{\text{ if }}x\neq y\\\;\;\,d&otherwise\end{cases}}}$

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

Note that, predicate calculus is an extension of propositional calculus: Assume only ${\displaystyle 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.

${\displaystyle \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 ${\displaystyle {\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})}$ as follows:

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

Determine the value of following terms and formulae:

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

${\displaystyle \Box }$

#### Problem 2 (Predicate)

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

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

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

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

Determine the value of following terms and formulae:

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

${\displaystyle \Box }$

#### Problem 3 (Predicate)

The following formula is given:

${\displaystyle 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 ${\displaystyle {\mathcal {A}}}$, which is a model for ${\displaystyle F}$ and a structure ${\displaystyle {\mathcal {B}}}$ which is no model for ${\displaystyle F}$!
${\displaystyle \Box }$