Interpretation (logic)

An interpretation (from Latin interpretatio: interpretation, explanation, interpretation ) in the sense of model theory is a structure that is based on a logical formula. Under the interpretation can be true or false the formula. An interpretation under which a formula is true, ie the model formula. If it is true in every possible interpretation, they are called universal.

2.1 Interpretation of the language of first -order logic

Overview

The following aspects of the interpretation can be distinguished:

Interpretations of the symbols ( signature ) of a formal (logical) language,
Interpretations of a set of statements ( axioms ) about this language,
Interpretations of formulas with variables on this language.

Interpretation of the symbols of a language

All of the symbols to be interpreted will depend on the language. Especially in the sense of first-order predicate logic, the language can contain constants, relations and function symbols, such as the constant symbols " 0" and " 1", the (two -digit ) relation symbol "<" and the (two -digit ) function symbol " ". Without an interpretation, these are meaningless characters; an interpretation is defined for the value from which the total amount is a constant, when a relation holds, and how the value function mapping. Thus, there is an interpretation of a range of values ( also universe domain of values , individual flow rate, domain of individuals or subject matter called ) and interpretations of the constants, relations and function symbols over this universe. Variables are available for non-fixed values from the universe. ( Instead relation symbol, the term predicate is used. )

Note that the range of values ( the world ) is part of the interpretation; Therefore, two interpretations can be different, even if they do not differ in the interpretation of the constants, relations and function symbols. ( For example, if an interpretation of the other is an extension ).

Depending on the interpretation results in a different structure; Statements in the language can only affect the elements and relationships contained in the structure.

Interpretation of a set of statements

The definition of interpretation directly determines the truth value of atomic statements. The truth value of a compound statement of a structure ( interpretation) can be derived from the truth value of the atomic expressions using truth tables.

Is a set of statements given ( an axiom system ), an interpretation is usually sought which satisfies all of these axioms simultaneously, ie makes true. The axioms of the system are then true statements about the universe in which the system is to be interpreted. Such a structure is called a model of the axiom system. In general, a system of axioms several models.

Examples:

The statement " Everyone has a mother " is true if we accept as a universe all people who have ever lived, but not if the universe only includes all those living.
The statement has several models, such as the natural, the whole and the real numbers with the standard addition, but also the set of strings when the " " is interpreted as concatenation and the constant 1 as a digit.

The transformation rules of the formal system are thus rules relating to the exploitation and transformation of statements or expressions over the area concerned.

Interpretation of formulas with variables

Once free variables appear in a logical formula, the truth value depends on what values are used for the variables. From an interpretation in the narrower sense variables (as opposed to constants ) are not assigned values . This statements are verifiable, an assignment of the variables must be added. Sometimes one also speaks of an interpretation of a formula, if one means, strictly speaking, a combination of interpretation and occupancy.

In theoretical computer science are statements with free variables often referred to as " constraints " (from English constraint = constraint ) on these variables indicated; in these contexts, the interpretation (semantics) is usually given the symbols. Then, a variable assignment or "interpretation" sought that fits the constraints, ie, it satisfies simultaneously.

Examples:

X is smaller than y, x y = 3, ( a possible solution is x = 1, y = 2, depending on the universe and x = 0, y = 3 )
X is greater than y, y is the right side of z, z is greater than x. (This constraint set is not satisfiable. )

An assignment that satisfies all constraints is often referred to as a model (see Constraint Satisfaction Problem ).

Importance

Such an interpretation is always based on on an underlying universe. By assigning the constants and functions of the axiom system individuals from this universe, the properties of predicates or relations between these individuals, they will receive a meaning (semantics). This allows you to draw conclusions about the structure.

An abstract axiom system that allows no single interpretation is generally worthless, and employment so that only the character of a character gimmick. Of particular interest are systems which allow multiple interpretations, such as the Boolean algebra:

Their signature contains the constant symbols " 0" and " 1", the two -digit function symbols and the unary function symbol. They can be interpreted for example as part of a set or as a logical truth values or numbers of the unit interval, and depending on "0" denotes, for example, the empty set, the value or the number 0

Has an axiom system interpretations in two different areas, and so can be replaced by those of studies in the other territory and re-interpretation of the results.

Formal definition

Interpretation of the language of first -order logic

Be the signature of a language. Formally, an interpretation in the sense of first-order logic of a non-empty set ( domain, even the universe of values , called domain of individuals ) and assignments for constants, functions and relation symbols:

Each constant symbol is assigned a value,
Each - ary function symbol a function
And each digit relation symbol is assigned to a function. Sometimes you can find the formulation that each digit relation symbol is assigned a subset. The latter is to be understood that if and only if there is.

This defines a structure. In her the truth values for all statements are derived.

Examples:

The atomic statement is true if and only if interpreted by the same value as.
The atomic statement is true if and only if the value to a mapping, which is in relation with him. Is interpreted, for example, over the integers as doubling function and as a relation, and the statement is true for, but not.

With the connectives composite statements are derived according to the truth tables of these. For the derivation of truth values in Quantorenausdrücken the validity of the formula expressions among possible assignments of the variables must be evaluated.

The interpretation ( in the broader sense ) for a formula with free variables is a pair consisting of a σ - structure and an assignment that assigns each variable a value from the universe.

Well-formed formula

415558