# 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:
* ${\mathcal {I}}(f(f(x,x),y))$
* ${\mathcal {I}}(\forall x\forall y(p(x,y)\lor p(y,x))$
* ${\mathcal {I}}(p(x,x)\to p(y,x))$
* ${\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$