An interpretation is a pair I = ( U I , A I ) {\displaystyle {\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})} , where U I {\displaystyle U_{\mathcal {I}}} is an arbitrary nonempty set, called domain, or universe. A I {\displaystyle A_{\mathcal {I}}} is a mapping which associates to a k {\displaystyle k} -ary predicate symbol, a k {\displaystyle k} -ary predicate over U I {\displaystyle U_{\mathcal {I}}} , a k {\displaystyle k} -ary function symbol, a k {\displaystyle k} -ary function over U I {\displaystyle U_{\mathcal {I}}} , and a variable an element from the domain. Let F {\displaystyle F} be a formula and I = ( U I , A I ) {\displaystyle {\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})} be an interpretation. We call I {\displaystyle {\mathcal {I}}} an interpretation for F {\displaystyle F} , if A I {\displaystyle {\mathcal {A}}_{\mathcal {I}}} is defined for every predicate and function symbol, and for every variable, that occurs free in F {\displaystyle F} . Example: Let F = ∀ x p ( x , f ( x ) ) ∧ q ( g ( a , z ) ) {\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 F {\displaystyle F} : I 1 = ( N 0 , A 1 ) {\displaystyle {\mathcal {I}}_{1}=(N_{0},A_{1})} , such that A 1 ( p ) = { ( m , n ) ∣ m , n ∈ N 0  and  m < n } {\displaystyle A_{1}(p)=\{(m,n)\mid m,n\in N_{0}{\text{ and }}m<n\}} A 1 ( q ) = { n ∈ N 0 ∣ n  is prime } {\displaystyle A_{1}(q)=\{n\in N_{0}\mid n{\text{ is prime}}\}} A 1 ( f ) ( n ) = n + 1 ∀ n ∈ N 0 {\displaystyle A_{1}(f)(n)=n+1\;\forall n\in N_{0}} A 1 ( g ) ( m , n ) = m + n ∀ n , m ∈ N 0 {\displaystyle A_{1}(g)(m,n)=m+n\;\forall n,m\in N_{0}} A 1 ( a ) = 2 {\displaystyle A_{1}(a)=2} A 1 ( z ) = 3 {\displaystyle A_{1}(z)=3} Under this interpretation the formula F {\displaystyle F} can be read as " Every natural number is smaller than its successor and the sum of 2 {\displaystyle 2} and 3 {\displaystyle 3} is a prime number." I 2 = ( U 2 , A 2 ) {\displaystyle {\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 ) ) , ⋯ } {\displaystyle U_{2}=\{a,f(a),g(a,a),f(g(a,a)),g(f(a),f(a)),\cdots \}} A 2 ( f ) ( t ) = f ( t ) {\displaystyle A_{2}(f)(t)=f(t)} for t ∈ U 2 {\displaystyle t\in U_{2}} A 2 ( g ) ( t 1 , t 2 ) = g ( t 1 , t 2 ) {\displaystyle A_{2}(g)(t_{1},t_{2})=g(t_{1},t_{2})} , if t 1 , t 2 ∈ U 2 {\displaystyle t_{1},t_{2}\in U_{2}} A 2 ( a ) = a {\displaystyle A_{2}(a)=a} A 2 ( z ) = f ( f ( a ) ) {\displaystyle A_{2}(z)=f(f(a))} A 2 ( p ) = { p ( a , a ) , p ( f ( a ) , f ( a ) ) , p ( f ( f ( a ) ) , f ( f ( a ) ) ) } {\displaystyle 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 ) ∣ t 1 , t 2 ∈ U 2 } {\displaystyle A_{2}(q)=\{g(t_{1},t_{2})\mid t_{1},t_{2}\in U_{2}\}} For a given interpretation I = ( U , A ) {\displaystyle {\mathcal {I}}=(U,A)} we write in the following p I {\displaystyle p^{\mathcal {I}}} instead of A ( p ) {\displaystyle A(p)} ; the same abbreviation will be used for the assignments for function symbols and variables. Let F {\displaystyle F} be a formula and I {\displaystyle {\mathcal {I}}} an interpretation for F {\displaystyle F} . For terms t {\displaystyle t} which can be composed with symbols from F {\displaystyle F} the value I ( t ) {\displaystyle {\mathcal {I}}(t)} is given by I ( x ) = x I {\displaystyle {\mathcal {I}}(x)=x^{\mathcal {I}}} I ( f ( t 1 , ⋯ , t k ) ) = f I ( I ( t 1 ) , ⋯ , I ( t k ) ) {\displaystyle {\mathcal {I}}(f(t_{1},\cdots ,t_{k}))=f^{\mathcal {I}}({\mathcal {I}}(t_{1}),\cdots ,{\mathcal {I}}(t_{k}))} , if t 1 , ⋯ , t k {\displaystyle t_{1},\cdots ,t_{k}} are terms and f {\displaystyle f} a k {\displaystyle k} -ary function symbol. (This holds for the case k = 0 {\displaystyle k=0} as well.) The value I ( F ) {\displaystyle {\mathcal {I}}(F)} of a formula F {\displaystyle F} is given by I ( p ( t 1 , ⋯ , t k ) ) = { t r u e  if  ( I ( t 1 ) , ⋯ , I ( t k ) ) ∈ p I f a l s e o t h e r w i s e {\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}}} I ( F ∧ G ) ) = { t r u e  if  I ( F ) = t r u e a n d I ( G ) = t r u e f a l s e o t h e r w i s e {\displaystyle {\mathcal {I}}(F\land G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{and}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}} I ( ( F ∨ G ) ) = { t r u e  if  I ( F ) = t r u e o r I ( G ) = t r u e f a l s e o t h e r w i s e {\displaystyle {\mathcal {I}}((F\lor G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{or}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}} I ( ¬ F ) = { t r u e  if  I ( F ) = f a l s e f a l s e o t h e r w i s e {\displaystyle {\mathcal {I}}(\lnot F)={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=false\\\;\;\,false&otherwise\end{cases}}} I ( ∀ G ) = { t r u e  if for every  d ∈ U : I [ x / d ] ( G ) = t r u e f a l s e o t h e r w i s e {\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}}} I ( ∃ G ) = { t r u e  if there is a  d ∈ U : I [ x / d ] ( G ) = t r u e f a l s e o t h e r w i s e {\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, f [ x / d ] ( y ) = { f ( y )  if  x ≠ y d o t h e r w i s e {\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 0 {\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. ∀ p ∃ f p ( f ( x ) ) {\displaystyle \forall p\exists f\;p(f(x))} Another example for a second order formula of is the induction principle from Induction. The interpretation I =  is given  ( U I , A I ) {\displaystyle {\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})} as follows: U I = N {\displaystyle U_{\mathcal {I}}=\mathbb {N} } p I = ( m , n ) ∣ m < n {\displaystyle p^{\mathcal {I}}={(m,n)\mid m<n}} f I ( m , n ) = m + n {\displaystyle f^{\mathcal {I}}(m,n)=m+n} x I = 5 ; y I = 7 {\displaystyle x^{\mathcal {I}}=5;y^{\mathcal {I}}=7} Determine the value of following terms and formulae: I ( f ( f ( x , x ) , y ) ) {\displaystyle {\mathcal {I}}(f(f(x,x),y))} I ( ∀ x ∀ y ( p ( x , y ) ∨ p ( y , x ) ) {\displaystyle {\mathcal {I}}(\forall x\forall y(p(x,y)\lor p(y,x))} I ( p ( x , x ) → p ( y , x ) ) {\displaystyle {\mathcal {I}}(p(x,x)\to p(y,x))} I ( ∃ x p ( y , x ) ) {\displaystyle {\mathcal {I}}(\exists xp(y,x))} ◻ {\displaystyle \Box } The interpretation I =  is given  ( U I , A I ) {\displaystyle {\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})} as follows: U I = R {\displaystyle U_{\mathcal {I}}=\mathbb {R} } P I = z ∣ z ≥ 0 {\displaystyle P^{\mathcal {I}}={z\mid z\geq 0}} f I ( z ) = z 2 {\displaystyle f^{\mathcal {I}}(z)=z^{2}} x I = 2 {\displaystyle x^{\mathcal {I}}={\sqrt {2}}} E I = ( x , y ) ∣ x = y {\displaystyle E^{\mathcal {I}}={(x,y)\mid x=y}} g I ( x , y ) = x + y {\displaystyle g^{\mathcal {I}}(x,y)=x+y} y I = − 1 {\displaystyle y^{\mathcal {I}}=-1} Determine the value of following terms and formulae: 1. I ( g ( f ( x ) , f ( y ) ) ) {\displaystyle 1. {\mathcal {I}}(g(f(x),f(y)))} 2. I ( ∀ x P ( f ( x ) ) ) {\displaystyle 2. {\mathcal {I}}(\forall x\,P(f(x)))} 3. I ( ∃ z ∀ x ∀ y E ( g ( x , y ) , z ) ) {\displaystyle 3. {\mathcal {I}}(\exists z\forall x\forall y\,E(g(x,y),z))} 4. I ( ∀ y ( E ( f ( x ) , y ) → P ( g ( x , y ) ) ) ) {\displaystyle 4. {\mathcal {I}}(\forall y(E(f(x),y)\to P(g(x,y))))} ◻ {\displaystyle \Box } The following formula is given: F = ∀ x ∀ y ∀ z R ( h ( h ( x , y ) , z ) , h ( x , h ( y , z ) ) )   ∧   ∃ x ∃ y ¬ R ( h ( x , y ) , h ( y , x ) ) {\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 A {\displaystyle {\mathcal {A}}} , which is a model for F {\displaystyle F} and a structure B {\displaystyle {\mathcal {B}}} which is no model for F {\displaystyle F} !
{'wiki_source': 'wikibooks', 'other_info': "{'content_model': 'wikitext', 'language': 'en', 'title': 'Logic for Computer Scientists/Predicate Logic/Semantics', 'type': 'text'}"}