3.3 Interpretationen und Modelle aussagenlogischer Formeln

© 1999 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials bedarf der Erlaubnis des Autors.

In diesem Abschnitt werden wir zunächst festlegen, wie einer aussagenlogischen Formel ein Wahrheitswert zugeordnet wird, und darauf aufbauend semantische Begriffe wie die Folgerungsbeziehung formalisieren.

Betrachten wir zur Motivation zwei Aussagen:

Aussagenvariable A₁ repräsentiert die Aussage: ,,ich arbeite``
Aussagenvariable A₂ repräsentiert die Aussage: ,,ich spiele``

Intuitiv folgt aus der von A₁ repräsentierten Aussage die von (A₁∨A₂) repräsentierte Aussage: wenn ich arbeite, dann gilt dass ich arbeite oder spiele. Interessanterweise folgt sie auch dann, wenn die beiden Aussagenvariablen ganz anders interpretiert werden, zum Beispiel:

Aussagenvariable A₁ repräsentiert die Aussage: ,,es regnet``
Aussagenvariable A₂ repräsentiert die Aussage: ,,es schneit``

Die Folgerungsbeziehung ist also unabhängig von der eigentlichen (anwendungsbezogenen) Interpretation der Aussagenvariablen. Sie ergibt sich bereits völlig aus den Zusammenhängen der Wahrheitswerte von A₁ und A₂ mit den Wahrheitswerten von (A₁∨A₂).

Diese Zusammenhänge sind hier gerade durch die Wahrheitstabelle der Boole'schen Funktion OR definiert, die dem Disjunktionsjunktor zugeordnet ist. Jede Zeile dieser Tabelle legt den Wahrheitswert von (A₁∨A₂) für eine der möglichen Kombinationen von Wahrheitswerten von A₁, A₂ fest. Jede Zeile stellt damit eine mögliche Interpretation der Aussagenvariablen dar, die von sämtlichen anwendungsbezogenen Aspekten bis auf die Wahrheitswerte abstrahiert. In allen Interpretationen, in denen A₁ wahr ist, ist nach der Tabelle auch (A₁∨A₂) wahr. Diese Tatsache ist die formale Begründung für die Folgerungsbeziehung zwischen den beiden Aussagen.

Bemerkungen:

Die obige Form der Definition von W* macht die Zuordnung zwischen Junktoren und Boole'schen Funktionen ganz explizit. Diese Definition liefert die Begründung dafür, warum man die Wahrheitswerte von Formeln auch über Wahrheitstabellen bestimmen kann, deren Überschriften -Formeln sind (im Gegensatz zu den Tabellen in Abschnitt 3.1, in denen keine -Formeln vorkamen).

Man überzeuge sich, dass die Definition von W* völlig gleichwertig zu der folgenden ist, die deutlicher betont, dass die Junktoren die gleiche Bedeutung haben sollen wie die entsprechenden metasprachlichen Junktoren. Diese zweite Form der Definition hat den Vorteil, dass ihr Stil sich auch auf die über die Aussagenlogik hinausgehenden Bestandteile der Prädikatenlogik übertragen lässt.

W*(T)	:=	w
W*()	:=	f
W*(F)	:=	W(F) falls F Aussagenvariable von ist
W*(¬F)	:=	w falls nicht gilt: W*(F)=w f andernfalls
W((F₁ ∧ F₂*))	:=	w falls W(F₁)=w und W(F₂)=w f andernfalls
W((F₁ ∨ F₂*))	:=	w falls W(F₁)=w oder W(F₂)=w f andernfalls
W((F₁ ⇒ F₂*))	:=	w falls gilt: wenn W(F₁)=w so W(F₂)=w f andernfalls
W((F₁ ⇔ F₂*))	:=	w falls entweder W(F₁)=w und W(F₂)=w oder weder W(F₁)=w noch W(F₂)=w f andernfalls

Ist aber durch die Definition, egal in welcher der beiden Formen, überhaupt eine Funktion W* festgelegt? Diese muss ja total und wohldefiniert sein, das heißt, für jede -Formel einen und nur einen Wert liefern. Dass dies in der Tat so ist, ergibt sich aus einem allgemeinen Ergebnis über das verwendete Definitionsprinzip.

Satz 3.3.2 (Definitionsprinzip der strukturellen Rekursion für aussagenlogische Formeln). Sei

eine Sprache der Aussagenlogik. Um eine Funktion Φ:F→B von der Menge der

-Formeln in einen Wertebereich B eindeutig zu definieren, genügen folgende Angaben für Φ:
1. Basisfälle:

1.1: Die Werte $b_{\bot}$ und $b_{A}$ von Φ auf $\bot$ und $\ensuremath{{\cal L}}$ werden explizit angegeben.
1.2: Der Wert b_A von Φ auf jeder atomaren -Formel A wird explizit angegeben.

2. Rekursionsfälle:

2.1: Der Wert von Φ auf zusammengesetzten Formeln der Gestalt ¬F wird in Abhängigkeit von dem Wert von Φ auf der Teilformel F definiert.
2.2: Der Wert von Φ auf zusammengesetzten Formeln der Gestalt (F θ G) wird für jeden zweistelligen Junktor θ in Abhängigkeit von den Werten von Φ auf den Teilformeln F und G definiert.

Beweis:

Seien Definitionen der Form 1.1, 1.2, 2.1, 2.2 gegeben. Die Rekursionsfälle seien mittels einer einstelligen Funktion und zweistelligen Funktionen BB → B für zweistellige Junktoren θ definiert.

Sei M die Menge aller Relationen über , die alle Bedingungen dieser Definitionen erfüllen, also die Menge aller , für die gilt:

1.1		$(\bot, b_{\bot}) \in R$ und $(A,b_{A}) \in R$ .
1.2		(A, b_A ∈ R für jede Aussagenvariable A von .
2.1		Wenn (F,b) ∈ R, dann auch $(F_1,b_1) \in R$ R.
2.2		Wenn (F₁, b₁) ∈ R und (F₂, b₂) ∈ R, dann auch ((F₁θF₂), φ_θ(b₁,b₂)) ∈ R
		für jeden zweistelligen Junktor θ.

Offensichtlich erfüllt

diese Bedingungen, also

. Ferner garantiert 1.1, dass

für jedes R ∈ M.

Wir konstruieren eine zweistellige Relation Φ über :

(F,b) ∈ Φ gdw. für alle R ∈ M gilt (F,b) ∈ R. ()

Anders ausgedrückt ist . Da die Bedingungen 1.1, 1.2, 2.1, 2.2 für alle R ∈ M gelten, gelten sie auch für Φ, das heißt, Φ ∈ M. Wir zeigen, dass Φ eine Funktion ist.

Φ ist linkstotal, d.h., für jede -Formel F gilt
es gibt b ∈ B mit (F,b) ∈ Φ (*)

Beweis durch strukturelle Induktion nach Satz 2.1.4, wobei (*) die nachzuweisende Eigenschaft ε ist. Sämtliche Teilbeweise ergeben sich unmittelbar aus der Tatsache, dass Φ die Eigenschaften 1.1, 1.2, 2.1, 2.2 erfüllt.
Φ ist rechtseindeutig, d.h., für jede -Formel F gilt
wenn (F,b) ∈ Φ und (F,b') ∈ Φ, dann b = b' (**)

Beweis durch strukturelle Induktion nach Satz 2.1.4, wobei (**) die nachzuweisende Eigenschaft ε ist.

Basisfall : Wegen 1.1 gilt . Angenommen, es gäbe ein Tupel mit . Dann würde auch die Bedingungen 1.1, 1.2, 2.1, 2.2 erfüllen (dass keines der in diesen Bedingungen geforderten Tupel gleich dem weggenommenen ist, ergibt sich aus dem Eindeutigkeitssatz 2.1.7). Also wäre ∈ M, und damit wäre . Widerspruch.
Also besitzt $\bot$ die Eigenschaft (**).

Die übrigen Basisfälle werden analog gezeigt.

Induktionsfall Negation: F besitze die Eigenschaft (**). Wegen der Linkstotalität von Φ gibt es b ∈ B mit (F,b) ∈ Φ. Wegen 2.1 gilt Φ. Angenommen, es gäbe ein Tupel mit . Dann würde auch R=Φ\{(¬F,b')} die Bedingungen 1.1, 1.2, 2.1, 2.2 erfüllen (nach dem Eindeutigkeitssatz 2.1.7 kann durch das Wegnehmen dieses Tupels höchstens Bedingung 2.1 verletzt sein, wenn es nämlich ein b₁ ∈ B gibt mit und (F,b₁)∈Φ; dies ist aber ausgeschlossen, da nach Induktionsannahme F die Eigenschaft (**) besitzt, somit b₁=b und ist, wo ja gerade sein soll). Also wäre R=Φ\{(¬F,b')}∈M, und damit wäre (¬ F, b') ∉ Φ. Widerspruch.
Also besitzt ¬F die Eigenschaft (**).

Die übrigen Induktionsfälle werden analog gezeigt.

Also ist das so konstruierte Φ eine Funktion, die die Bedingungen 1.1, 1.2, 2.1, 2.2 erfüllt. Es bleibt noch der Nachweis zu führen, dass es die einzige derartige Funktion ist.

Angenommen, es gibt noch eine weitere Funktion Φ', die die Bedingungen 1.1, 1.2, 2.1, 2.2 erfüllt. Nach Definition von M gilt Φ'∈M. Nach Definition von Φ gilt . Für jedes F∈ ergibt sich damit: wenn , also (F,b)∈Φ, dann (F,b)∈Φ'. Da Φ' nach Annahme eine Funktion ist, gibt es kein anderes b' mit . Das heißt Φ'(F)=b=Φ(F) für jedes F, also Φ'=Φ.

Definition 3.3.4 (Modellbeziehung, Folgerungsbeziehung, logische Äquivalenz). Sei

eine Sprache der Aussagenlogik. W bezeichne eine

-Interpretation (oder Wahrheitsbelegung), F und G bezeichne

-Formeln, S bezeichne eine Menge von

-Formeln.

W erfüllt F (oder W ist ein Modell von F) notiert WF, gdw. W*(F)=w.
Andernfalls: W falsifiziert F, notiert $W \models S$ .
W erfüllt S (oder W ist ein Modell von S), notiert $F \in S$ , gdw. $W \models S$ für jedes F ∈ S.
Andernfalls: W falsifiziert S, notiert $F \models G$ .

Eine

-Formel (oder Menge von

-Formeln) heißt

allgemeingültig		gdw. sie von jeder -Interpretation erfüllt wird
erfüllbar		gdw. sie von einer -Interpretation erfüllt wird
falsifizierbar		gdw. sie von einer -Interpretation falsifiziert wird
unerfüllbar		gdw. sie von jeder -Interpretation falsifiziert wird

Eine allgemeingültige Formel nennt man auch Tautologie, eine unerfüllbare Formel(menge) auch widersprüchlich, eine erfüllbare Formel(menge) auch widerspruchsfrei.

Aus F folgt G, notiert FG, gdw. für jede -Interpretation W gilt: wenn W F dann W G (jedes Modell von F erfüllt auch G).
F, G sind logisch äquivalent, notiert F $G \models F$ G, gdw. FG und GF (F und G haben dieselben Modelle).
Die Folgerungsbeziehung FG und die logische Äquivalenz F G sind genauso definiert, wenn F oder G oder sowohl F als auch G eine Formelmenge ist.

Bemerkungen:

Man beachte, dass das Symbol stark überladen ist. Es wird für die Modellbeziehung und für die Folgerungsbeziehung verwendet und zwar sowohl für Formeln als auch für Mengen von Formeln. Steht auf der linken Seite von eine Interpretation (Wahrheitsbelegung), handelt es sich um die Modellbeziehung. Steht links eine Formel oder eine Formelmenge, dann handelt es sich um die Folgerungsbeziehung.
Im Fall der Folgerungsbeziehung zwischen einer Menge S und einer Formel G ist man versucht, SG durch F G zu ersetzen, wobei F die Konjunktion aller Elemente von S ist. Da Formeln aber endliche Gebilde sind, ist dies nur dann zulässig, wenn S eine endliche Menge ist, was die Definition 3.3.4 aber keineswegs voraussetzt.
Um auszudrücken, dass W ein Modell von F ist, ist für die Aussagenlogik die Notation W*(F)=w etwas gebräuchlicher, für die Prädikatenlogik die Notation W F. Wir benutzen ab sofort durchgängig die Notation WF, auch für die Aussagenlogik.

Beweis: Anwendung der Definitionen.

Der Satz erklärt, warum man sich für die Allgemeingültigkeit oder Unerfüllbarkeit interessiert: Die Folgerungsbeziehung lässt sich darauf zurückführen. Die Zurückführung auf die Unerfüllbarkeit wird mit der Technik des Widerspruchsbeweises häufig ausgenutzt. In Kapitel 4 werden wir Berechnungsverfahren - Beweismethoden genannt - kennenlernen, mit denen man ermitteln kann, ob eine Formel allgemeingültig bzw. unerfüllbar ist.

Mit der letzten Aussage des Satzes zeigt man leicht, dass die logische Äquivalenz eine Äquivalenzrelation auf der Menge F aller -Formeln ist. Sie ist darüberhinaus mit der Struktur der Formeln verträglich im folgenden Sinn (eine Äquivalenzrelation, die diese Art von Strukturverträglichkeit besitzt, nennt man eine Kongruenzrelation).

Beweis: Strukturelle Induktion.

Beweis: Anwendung der Definitionen.

Warum diese Beziehungen zwischen aussagenlogischen Formeln ,,Regeln`` genannt werden, ergibt sich zum Teil aus Satz 3.3.5 und Satz 3.3.6. Man kann die Beziehungen dazu verwenden, eine Ausgangsformel in eine andere Formel umzuwandeln, die eine spezielle syntaktische Gestalt hat, ohne dass sich dadurch der Wahrheitswert unter irgend einer Wahrheitsbelegung ändert - die beiden Formeln werden völlig gleich interpretiert im Sinn der Einleitung zu Abschnitt 3.3 (Mehr zu diesem Thema in Kapitel 4.)

Rein äußerlich haben die Regeln 1 bis 4 eine starke Ähnlichkeit zu den in Definition 3.2.1 geforderten Eigenschaften einer Boole'schen Algebra. Der wesentliche Unterschied ist, dass in den obigen Regeln das Zeichen steht, wo in Definition 3.2.1 ein Gleichheitszeichen steht. Mit dieser Sichtweise entsprechen die Regeln 5 bis 7 Rechenregeln, die in jeder Boole'schen Algebra gelten. Der nächste Satz zeigt, dass diese Sichtweise in der Tat gerechtfertigt ist. Wir erinnern daran, dass die logische Äquivalenz eine Äquivalenzrelation auf der Menge F aller -Formeln ist.

Beweis: (skizziert)

Zunächst müssen wir uns vergewissern, dass ‾, , mit den obigen Definitionen wirklich Funktionen sind. Die Linkstotalität ist offensichtlich, weil Äquivalenzklassen nie leer sind. Für die Rechtseindeutigkeit ist zu zeigen, dass die auf den Klassen definierten Werte nicht von den gewählten Repräsentanten abhängen. Wir zeigen dies exemplarisch für .

Sei also und , das heißt, und . Durch zweimaliges Anwenden des Ersetzungssatzes 3.3.6 auf (F∧G) erhalten wir (F'∧G'), das heißt, und damit , was zu zeigen war.

Von den in Definition 3.2.1 geforderten Eigenschaften zeigen wir exemplarisch die Kommutativität von $\sqcup$ .

[F] $\sqcup$ [G]	=	[(F∧G)]	nach Definition
	=	[(G∧F)]	weil nach Satz 3.3.7 gilt (F∧G)(G∧F)
	=	[G] $\sqcup$ [F]	nach Definition

Die übrigen Teilbeweise folgen dem gleichen kanonischen Schema.

Bemerkung: Das obige Argument (F∧G)

(F'∧G) macht wesentlich davon Gebrauch, dass der Ersetzungssatz 2.14.6 die logische Äquivalenz sichert, sobald ein einziges Vorkommen einer Teilformel durch eine dazu äquivalente ersetzt wird, aber nicht notwendigerweise alle Vorkommen.

Wäre der Ersetzungssatz so formuliert, dass alle Vorkommen ersetzt werden müssen und käme F in G vor, wäre das obige Argument nicht begründet.

Das Nullelement [] dieser Boole'schen Algebra besteht aus allen unerfüllbaren -Formeln, das Einselement [] aus allen allgemeingültigen.

Es reicht also, anhand der Wahrheitstabellen die Regeln 1 bis 4 in Satz 3.3.7 nachzuweisen, weil diese für den Beweis von Satz 3.3.8 benötigt werden. Die Regeln 5 bis 7 in Satz 3.3.7 ergeben sich dann ebenso wie alle anderen Rechenregeln für Boole'sche Algebren nach einem einheitlichen Argumentationsmuster, das hier am Beispiel der de Morgan'schen Regel dargestellt ist:

‾[F][G]	=	‾[F] $\sqcup$ ‾[G]
[¬(F∨G)]	=	[(¬F∧¬G)]
¬(F∨G)		(¬F∧¬G)

Die erste Zeile gilt, weil (, , ) nach Satz 3.3.8 eine Boole'sche Algebra ist. Die zweite Zeile ergibt sich daraus durch Einsetzen der Definitionen von (‾,, ). Die dritte Zeile entsteht aus der zweiten mit der Definition der Äquivalenzklassen.

Die Rechenregeln aus der ersten Zeile lassen sich also rein schematisch auf aussagenlogische Formeln übertragen, indem man = durch ersetzt.

Wie oben erwähnt, erlaubt Satz 3.3.5, die Folgerungsbeziehung und die logische Äquivalenz auf die Allgemeingültigkeit oder Unerfüllbarkeit zurückzuführen. Der folgende Satz ist ein wichtiges Hilfsmittel für den Nachweis der Unerfüllbarkeit.

Beweis:

Wenn alle endlichen Teilmengen einer Menge S von -Formeln erfüllbar sind, sagen wir, dass S die Eigenschaft E besitzt.

Sei S eine unendliche Menge, die die Eigenschaft E besitzt. Wir zeigen nun, dass S erfüllbar ist.

Da die Menge F aller -Formeln abzählbar ist, gibt es eine Surjektion 0}→ F. Sei F_n jeweils das Bild von . Dann kommt jede -Formel in der Folge F₁, F₂,...,F_n,... vor. Wir definieren rekursiv:

S₀	:=	S
S_n+1	:=	S_n∪{F_n+1} falls diese Menge die Eigenschaft E besitzt, S_n∪{¬F_n+1} sonst.

Für alle n≥0 besitzt S die Eigenschaft E.
Dies wird durch vollständige Induktion über n bewiesen.
Induktionsbasis n=0: Nach Annahme über S besitzt S₀=S die Eigenschaft E.

Induktionsschritt n→n+1: Sei angenommen, dass S_n die Eigenschaft E besitzt. Wir zeigen, dass es keine zwei endlichen Teilmengen T₁ und T₂ von S_n gibt, so dass sowohl T₁∪{F_n+1} als auch T₂∪{¬F_n+1} unerfüllbar ist.

Seien also T₁⊆S_n und T₂⊆S_n endlich. Da T₁∪T₂ endlich ist und S_n die Eigenschaft E besitzt, ist T₁∪T₂ erfüllbar. Sei W ein Modell von T₁∪T₂. Dieses Modell erfüllt sowohl T₁ als auch T₂ und natürlich eine der beiden Formeln F_n+1 und ¬F_n+1. Also erfüllt W eine der beiden Mengen T₁∪{F_n+1} und T₂∪{¬F_n+1}.

Falls S_n∪{F_n+1} die Eigenschaft E besitzt, dann ist S_n+1=S_n∪{F_n+1} nach Definition und besitzt also die Eigenschaft E. Wenn aber S_n∪{F_n+1} die Eigenschaft E nicht besitzt, folgt aus dem obigen, dass S_n∪{¬F_n+1} sie besitzt und nach Definition ist S_n+1=S_n∪{¬F_n+1}. In allen Fällen besitzt S_n+1 die Eigenschaft E.
S*:=∪S_n mit n∈N besitzt die Eigenschaft E.
Sei T eine endliche Teilmenge von S*. Da T endlich ist, gibt es ein i∈N so dass T⊆S_i. Da jedes S_i die Eigenschaft E besitzt, ist T erfüllbar.
Offensichtlich S⊆S* und für jede -Formel F_i ist entweder F_i∈S* oder ¬F_i∈S*.
Sei W die folgende Wahrheitsbelegung: für jede Aussagenvariable A sei W(A):=w gdw. A∈S*. Dann gilt für jede -Formel F, dass WF gdw. F∈S*. Beweis durch strukturelle Induktion.
Basisfälle: Nach Definition von W.

Induktionsfall zweistelliger Junktor ∧: Sei F eine Formel der Gestalt (F₁∧F₂) und es gelte WF₁ gdw. F₁∈S* und WF₂ gdw. F₂∈S*.
Angenommen WF, aber F∉S*. Das heißt, WF₁ und WF₂ und F₁∈S* und F₂∈S*, aber (F₁∧F₂)∉S*. Wegen 3. ist dann ¬(F₁∧F₂)∈S*. Also enthält S* die unerfüllbare endliche Teilmenge {F₁,F₂,¬(F₁∧F₂)}, im Widerspruch zu 2.
Angenommen WnichtF, aber F∈S*. Dann gilt für wenigstens eine der Teilformeln WnichtF_i, also F_i∉S*. Wegen 3. ist dann ¬F_i∈S*. Also enthält S* die unerfüllbare endliche Teilmenge {¬F₁,(F₁∧F₂)} bzw. {¬F₂,(F₁∧F₂)}, im Widerspruch zu 2.
Also gilt WF gdw. F∈S*.

Die übrigen Induktionsfälle werden in ähnlicher Weise bewiesen.
Da S⊆S*, erfüllt W auch die Menge S.

[‾F]	:=	[¬F]
[F][G]	:=	[(F∧G)]
[F][G]	:=	[(F∨G)]