# 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 • $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 $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$ 