Logic for Computer Scientists/Predicate Logic/Semantics

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

Semantics[edit | edit source]

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

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

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


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

Problem 1 (Predicate)[edit | edit source]

The interpretation as follows:

Determine the value of following terms and formulae:

Problem 2 (Predicate)[edit | edit source]

The interpretation as follows:

Determine the value of following terms and formulae:

Problem 3 (Predicate)[edit | edit source]

The following formula is given:

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