Logic for Computer Scientists/Predicate Logic/Semantics

From Wikibooks, open books for an open world
< Logic for Computer Scientists‎ | Predicate Logic
Jump to: navigation, search

Semantics[edit]

Definition 4 (Semantics of predicate logic - Interpretation)[edit]

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)[edit]

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[edit]

Problem 1 (Predicate)[edit]

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)[edit]

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)[edit]

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