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 , where

  • is an arbitrary nonempty set, called domain, or universe.
  • is a mapping which associates to
    • a -ary predicate symbol, a -ary predicate over ,
    • a -ary function symbol, a -ary function over , and
    • a variable an element from the domain.

Let be a formula and be an interpretation. We call an interpretation for , if is defined for every predicate and function symbol, and for every variable, that occurs free in .


Example: Let and assume the varieties of the symbols as written down. In the following we give two interpretations for :

  • , such that
    Under this interpretation the formula can be read as " Every natural number is smaller than its successor and the sum of and is a prime number."
  • , such that
    • for
    • , if


For a given interpretation we write in the following instead of ; 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 be a formula and an interpretation for . For terms which can be composed with symbols from the value is given by

  • , if are terms and a -ary function symbol. (This holds for the case as well.)

The value of a formula is given by


where,


The notions of satisfiable, valid, and are defined according to the propositional case (Semantic (Propositional logic)).


Note that, predicate calculus is an extension of propositional calculus: Assume only -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.

Another example for a second order formula of is the induction principle from Induction.

Problems[edit]

Problem 1 (Predicate)[edit]

The interpretation as follows:




Determine the value of following terms and formulae:

Problem 2 (Predicate)[edit]

The interpretation as follows:







Determine the value of following terms and formulae:





Problem 3 (Predicate)[edit]

The following formula is given:

Indicate a structure , which is a model for and a structure which is no model for !