Interpretation (Logik)

Eine Interpretation (von lat. interpretatio: Auslegung, Erklärung, Deutung) im Sinn der mathematischen Logik ordnet allen zunächst bedeutungslosen oder unbestimmten Ausdrücken einer formalen Sprache einen konkreten Wert zu. Dadurch erhält die Zeichenkette einen auf ein spezifisches Anwendungsgebiet bezogenen Sinn und es wird möglich, über die Gültigkeit von Aussagen zu sprechen. Dieselbe formale Zeichenreihe (Aussage) kann in einer Interpretation wahr sein, in einer anderen falsch. Falls sie in jeder möglichen Interpretation wahr ist, nennt man sie ein (mathematisches) Theorem.

Abgrenzung: Dieser Artikel befasst sich nicht mit Interpretation im Sinn der Geisteswissenschaften oder der Künste.

Überblick

Folgende Aspekte der Interpretation können unterschieden werden:

• Interpretationen der Symbole (Signatur) einer formalen (logischen) Sprache,
• Interpretationen einer Menge von Aussagen (Axiomen) über dieser Sprache,
• Interpretationen von Formeln mit Variablen über dieser Sprache.

Interpretation der Symbole einer Sprache

Die Gesamtheit der zu interpretierenden Symbole hängt von der Sprache ab. Speziell im Sinn der Prädikatenlogik erster Stufe kann die Sprache Konstanten-, Relations- und Funktionssymbole enthalten, z. B. die Konstantensymbole "0" und "1", das (zweistellige) Relationssymbol "<" und das (zweistellige) Funktionssymbol "+". Ohne eine Interpretation sind dies sinnleere Zeichen; eine Interpretation definiert, für welchen Wert aus welcher Gesamtmenge eine Konstante steht, wann eine Relation gilt und wie die Funktion Werte abbildet. Somit besteht eine Interpretation aus einem Wertebereich (auch Universum, Domäne, Wertemenge, Individuenmenge, Individuenbereich oder Gegenstandsbereich genannt) und Interpretationen der Konstanten-, Relations- und Funktionssymbole über diesem Universum. Variablen stehen für nicht festgelegte Werte aus dem Universum. (Statt Relationssymbol wird auch der Begriff Prädikat verwendet.)

Man beachte, dass der Wertebereich (das Universum) Teil der Interpretation ist; daher können zwei Interpretationen unterschiedlich sein, auch wenn sie sich in der Interpretation der Konstanten-, Relations- und Funktionssymbole nicht unterscheiden. (Beispielsweise, wenn eine Interpretation eine Erweiterung der anderen ist).

Je nach Interpretation ergibt sich eine unterschiedliche Struktur; Aussagen in der Sprache können nur die in der Struktur enthaltenen Elemente und Beziehungen betreffen.

Interpretation einer Menge von Aussagen

Die Definition der Interpretation bestimmt unmittelbar den Wahrheitswert atomarer Aussagen. Der Wahrheitswert einer zusammengesetzten Aussage über einer Struktur (Interpretation) lässt sich aus dem Wahrheitswert der atomaren Ausdrücke mittels Wahrheitstabellen ableiten.

Ist eine Menge von Aussagen (ein Axiomensystem) gegeben, ist in der Regel eine Interpretation gesucht, die alle diese Axiome gleichzeitig erfüllt, d. h. wahr macht. Die Axiome des Systems werden dann zu wahren Aussagen über das Universum, in dem das System interpretiert werden soll. Eine solche Struktur nennt man ein Modell des Axiomensystems. Im allgemeinen hat ein Axiomensystem mehrere Modelle.

Beispiele:

• Die Aussage "Jeder hat eine Mutter" gilt, wenn wir als Universum alle Menschen annehmen, die je gelebt haben, aber nicht, wenn das Universum nur alle lebenden Menschen umfasst.
• Die Aussage $\forall x \exists y: y = x+1$ hat mehrere Modelle, z. B. die natürlichen, die ganzen und die reellen Zahlen mit der Standard-Addition, aber auch die Menge der Zeichenfolgen, wenn die Funktion "+" als Konkatenation interpretiert wird und die Konstante 1 als Ziffer.

Die Umformungsregeln des formalen Systems werden damit zu Regeln über die Gewinnung bzw. Umwandlung von Aussagen bzw. Ausdrücken über das betreffende Sachgebiet.

Interpretation von Formeln mit Variablen

Sobald freie Variablen in einer logischen Formel auftauchen, hängt der Wahrheitswert davon ab, welche Werte man für die Variablen einsetzt. Von einer Interpretation im engeren Sinn werden Variablen (im Gegensatz zu Konstanten) nicht mit Werten belegt. Damit Aussagen überprüfbar sind, muss eine Belegung der Variablen hinzukommen. Manchmal spricht man aber auch von einer Interpretation einer Formel, wenn man genaugenommen eine Kombination aus Interpretation und Belegung meint.

In der theoretischen Informatik werden Aussagen mit freien Variablen oft als "Constraints" (von Englisch constraint = Einschränkung) über diesen Variablen bezeichnet; in diesen Kontexten ist die Interpretation (Semantik) der Symbole meist gegeben. Dann wird eine Variablenbelegung oder "Interpretation" gesucht, die zu den Constraints passt, d. h. diese simultan erfüllt.

Beispiele:

• x ist kleiner als y, x + y = 3. (Eine mögliche Lösung ist x=1, y = 2; je nach Universum auch x=0, y=3.)
• x ist oberhalb von y, y ist rechts von z, z ist oberhalb von x. (Diese Constraintmenge ist nicht erfüllbar.)

Eine Belegung, die alle Constraints erfüllt, wird oft als Modell bezeichnet (siehe Constraint Satisfaction Problem).

Bedeutung

Eine solche Interpretation bezieht sich immer auf ein zugrunde gelegtes Universum. Indem den Konstanten und Funktionen des Axiomensystems Individuen aus diesem Universum, den Prädikaten Eigenschaften von bzw. Beziehungen zwischen diesen Individuen zugeordnet werden, erhalten sie eine Bedeutung (Semantik). Dadurch kann man über die Struktur Aussagen treffen.

Ein abstraktes Axiomensystem, das keine einzige Interpretation zulässt, ist im allgemeinen wertlos, und die Beschäftigung damit hat nur den Charakter einer Zeichenspielerei. Von besonderem Interesse sind Systeme, die mehrere Interpretationen zulassen, wie etwa die Boolesche Algebra:

Deren Signatur σ enthält die Konstantensymbole "0" und "1", die zweistelligen Funktionssymbole $\vee, \wedge$ und das einstellige Funktionssymbol $\neg$ . Sie können beispielsweise als Teilmengen einer Menge interpretiert werden oder als logische Wahrheitswerte oder als Zahlen des Einheitsintervalls [0,1], und je nachdem bezeichnet "0" beispielsweise die leere Menge, den Wert falsch oder die Zahl 0.

Hat ein Axiomensystem Interpretationen in zwei verschiedenen Gebieten G₁ und G₂, so lassen sich Untersuchungen von G₂ durch solche des anderen Gebiets und Uminterpretation der Ergebnisse ersetzen.

Formale Definition

Interpretation einer Sprache der Logik erster Stufe

Sei σ die Signatur einer Sprache. Formal besteht eine σ-Interpretation $\mathcal{I}$ im Sinn der Logik erster Stufe aus einer nichtleeren Menge U (Domäne, auch Universum, Wertemenge, Individuenbereich genannt), und Zuordnungen für Konstanten-, Funktionen- und Relationssymbole:

• Jedem Konstantensymbol c wird ein Wert $c^{\mathcal{I}} \in U$ zugewiesen,
• jedem k-stelligen Funktionssymbol f eine Funktion $f^{\mathcal{I}}: U^k \mapsto U$
• und jedem k-stelligen Relationssymbol R wird eine Funktion $R^{\mathcal{I}}: U^k \mapsto \{\mbox{wahr, falsch}\}$ zugewiesen. Manchmal findet man auch die Formulierung, dass jedem k-stelligen Relationssymbol R eine Teilmenge $R^{\mathcal{I}} \subseteq U^k$ zugeordnet wird. Letzteres ist so zu verstehen, dass genau dann $R^{\mathcal{I}}(x_1,\ldots , x_k) = \mbox{wahr}$ gilt, wenn $(x_1,\ldots, x_k)\in U^k$ vorliegt.

Dadurch wird eine σ-Struktur $\mathcal{A} = (U; c_1^{\mathcal{I}}, c_2^{\mathcal{I}}, ..., f_1^{\mathcal{I}}, ..., R_1^{\mathcal{I}},... )$ definiert. In ihr sind die Wahrheitswerte für alle Aussagen ableitbar.

Beispiele:

• Die atomare Aussage ${\mathcal{A}}\models c_1 = c_2$ gilt genau dann, wenn c₁ durch denselben Wert interpretiert wird wie c₂.
• Die atomare Aussage ${\mathcal{A}}\models R(c, f(c))$ gilt genau dann, wenn $f^{\mathcal{I}}$ den Wert $c^{\mathcal{I}}$ auf einen abbildet, der mit ihm in der Relation $R^{\mathcal{I}}$ steht. Wird über den ganzen Zahlen beispielsweise $f^{\mathcal{I}}$ als Verdopplungsfunktion interpretiert und $R^{\mathcal{I}}$ als Relation $\le$, so gilt diese Aussage für $c^{\mathcal{I}}=1$ und$c^{\mathcal{I}}=0$, aber nicht für $c^{\mathcal{I}}=-1$.

Mit den Junktoren $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$ zusammengesetzte Aussagen werden gemäß der Wahrheitstabellen aus diesen abgeleitet. Für die Ableitung der Wahrheitswerte bei Quantorenausdrücken muss die Gültigkeit der Formelausdrücke unter möglichen Belegungen der Variablen ausgewertet werden.

Die Interpretation (im weiteren Sinn) für eine Formel φ mit freien Variablen ist ein Paar $\mathcal{I}=(\mathcal{A},\beta)$ bestehend aus einer σ-Struktur $\mathcal{A}= (U; c_1^{\mathcal{I}}, c_2^{\mathcal{I}}, ..., f_1^{\mathcal{I}}, ..., R_1^{\mathcal{I}},... )$ und einer Belegung $\beta: Var(\varphi) \rightarrow U$, die allen Variablen aus φ einen Wert des Universums zuordnet.

Siehe auch

• Constraint Satisfaction Problem
• Logischer Ausdruck
• Löwenheim-Skolem-Theorem
• Modell
• Signatur (Modelltheorie)
• Struktur (Modelltheorie)
• Terminterpretation

Literatur

• Hans-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas: Einführung in die mathematische Logik. Vierte Auflage. Spektrum Akademischer Verlag, Heidelberg 1996, ISBN 3-8274-1691-4.
• Chin-Liang Chang and Richard Char-Tung Lee: Symbolic Logic and Mechanical Theorem Proving. Academic Press, San Diego 1987, ISBN 0-12-170350-9.
• Stephen Cole Kleene: Mathematical Logic. Dover, Mineola N. Y. 2002, ISBN 0-486-42533-9.
• Elliott Mendelson: Introduction to Mathematical Logic. 4th Edition. Chapman & Hall, London 1997, ISBN 0-412-80830-7.

Weblinks

• Interpretation auf Mathworld (englisch)