# 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 x p(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} = \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 x p(y,x))$

$\Box$

#### Problem 2 (Predicate)

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

$U_\mathcal{I} = \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$