Semantische Konsequenz und Äquivalenz

ZUSAMMENFASSUNG
In dieser Lektion untersuchen wir die semantische Konsequenz und Äquivalenz in der Aussagenlogik, was eine natürliche Fortsetzung dessen ist, was wir zuvor gesehen haben. Wir lernen, wie sich die Vorstellung der semantischen Konsequenz aus den Wahrheitswertzuweisungen ableiten lässt und wie diese Idee mit dem Deduktionstheorem zusammenhängt. Außerdem sehen wir praktische Beispiele für die Verwendung von Wahrheitstabellen, um nützliche Eigenschaften wie die Elimination der Konjunktion und die Einführung der Disjunktion zu erhalten. Wir werden auch den Begriff der semantischen Äquivalenz untersuchen und sehen, wie er mit den bereits bekannten Eigenschaften zusammenhängt. Schließlich zeigen wir, wie der Einsatz von Modellen und deduktiven Techniken uns erlaubt, das Studium von Problemen der semantischen Konsequenz und Äquivalenz zu vereinfachen.

LERNZIELE:
Am Ende dieser Lektion wird der Studierende in der Lage sein,

zu verstehen, was unter semantischer Konsequenz zu verstehen ist.
die verschiedenen Interpretationen des Symbols ⊨ zu verstehen.
das semantische Deduktionstheorem und seine Anwendung im Studium der semantischen Konsequenz und Äquivalenz zu verstehen.
die Definition der semantischen Äquivalenz und deren Zusammenhang mit den Wahrheitswerten zu verstehen.
das Deduktionstheorem in seiner semantischen Version anzuwenden, um Konsequenzprobleme in Gültigkeitsprobleme umzuwandeln.
die nützlichen Eigenschaften der Wahrheitstabellen zur Demonstration semantischer Äquivalenzen anzuwenden.
die Gesetze der Absorption, Distribution und DeMorgan zur Vereinfachung komplexer Ausdrücke anzuwenden.
die Beziehung zwischen Modellen und Deduktionen im Studium der Aussagenlogik zu analysieren.

INHALTSVERZEICHNIS
ZUWEISUNGEN UND MODELLE
DAS DEDUKTIONSTHEOREM (SEMANTISCHE VERSION)
VERWENDUNG DES DEDUKTIONSTHEOREMS IM STUDIUM DER SEMANTISCHEN KONSEQUENZ UND ÄQUIVALENZ
SEMANTISCHE ÄQUIVALENZ UND EIGENSCHAFTEN
ZUSAMMENFASSUNG

Das Studium der semantischen Konsequenz und Äquivalenz ist eine natürliche Fortsetzung dessen, was wir bei der Betrachtung der Semantik der Aussagenlogik getan haben. Nun untersuchen wir, wie sich aus den Wahrheitswertzuweisungen die Vorstellung der semantischen Konsequenz ergibt und wie daraus auf natürliche Weise eine semantische Version des Deduktionstheorems hervorgeht. Darauf aufbauend zeigen wir praktische Beispiele zur Nutzung von Wahrheitstabellen zur Gewinnung nützlicher Eigenschaften. All dies findest du auch auf dem YouTube-Kanal.

Zuweisungen und Modelle

Zunächst beginnen wir mit einer Definition, die für die Entwicklungen in diesem Abschnitt entscheidend ist: die der semantischen Konsequenz.

DEFINITION: Ein Ausdruck

G

ist eine (semantische) Konsequenz eines anderen Ausdrucks

F

, wenn für jede Zuweisung

\mathcal{A}

gilt:

$\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$

Dies schreiben wir als $F\models G$ und lesen es als „Der Ausdruck $F$ modelliert den Ausdruck $G$ “ oder „ $G$ ist eine (semantische) Konsequenz von $F$ .“

Mit dieser Definition im Gepäck sollten wir beachten, dass das Symbol $\models$ je nach Kontext verschiedene Bedeutungen hat:

$\mathcal{A} \models F$ bedeutet, dass $\mathcal{A}(F) = 1$ ; das heißt, dass „ $\mathcal{A}$ $F$ modelliert.“
$G \models F$ bedeutet, dass wenn eine beliebige Zuweisung $G$ modelliert, sie auch $F$ modelliert; wir lesen dies als „ $F$ ist eine Konsequenz von $G$ .“
$\models F$ bedeutet, dass $F$ unter jeder Zuweisung gilt; das heißt, dass $F$ eine Tautologie ist.

Obwohl das Symbol $\models$ also viele Interpretationen zulässt, ist der Kontext eindeutig.

Die Vorstellung der (semantischen) Konsequenz ist eng verwandt mit dem Begriff der „Implikation“, den wir zuvor untersucht haben, insofern gilt: Wenn $F\models G$ , dann $\models (F\rightarrow G)$ . Tatsächlich ähnelt dies sehr dem Deduktionstheorem, das wir vor mehreren Lektionen behandelt haben.

Das Deduktionstheorem (Semantische Version)

[ansehen]

SATZ: Wenn

F

und

G

beliebige Ausdrücke sind, dann gilt:

$F\models G \Leftrightarrow \models (F\rightarrow G)$

Beweis:

Der Beweis dieses Satzes ergibt sich leicht durch Betrachtung der Wahrheitstabellen

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Wenn wir uns auf die Bedeutung von $F\models G$ konzentrieren, sehen wir, dass dies gleichbedeutend ist mit $\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$ , was wiederum dasselbe ist wie zu sagen $\mathcal{A}\not\models F \vee \mathcal{A}\models G$ . Wenn wir nun beachten, dass $\mathcal{A}\not\models F$ genau dasselbe ist wie $\mathcal{A}\models \neg F$ , dann ergibt sich, dass $F\models G$ gleichbedeutend ist mit $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ . Wenn wir jetzt eine Wahrheitstabelle für $F \rightarrow G$ erstellen und den Bereich markieren, in dem $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ gilt, und diesen Bereich grün einfärben, dann ergibt sich folgendes Bild:

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Daraus ergibt sich: Wenn $F\models G$ , dann gilt stets $\models (F \rightarrow G)$ und umgekehrt – was nichts anderes ist als das Deduktionstheorem und seine Umkehrung in semantischer Version.

Angenommen, wir möchten wissen, ob ein Ausdruck $G$ eine Konsequenz eines anderen Ausdrucks $F$ ist. Wir bezeichnen dies als das Konsequenzproblem. Mithilfe des obigen Theorems lässt sich dieses Problem in ein Gültigkeitsproblem umwandeln, denn: „ $G$ ist eine Konsequenz von $F$ genau dann, wenn $(F\rightarrow G)$ ein Theorem ist“.

Verwendung des Deduktionstheorems im Studium der semantischen Konsequenz und Äquivalenz

Ausgehend von den Wahrheitstabellen lassen sich einige Eigenschaften ableiten, die an bereits behandelte erinnern.

BEISPIEL: Zeigen Sie mithilfe von Wahrheitstabellen, dass die folgenden Eigenschaften gelten

Elimination der Konjunktion:

(F\wedge G)\models F

Einführung der Disjunktion:

F\models (F\vee G)

Kontradiktion:

(F\wedge\neg F)\models G

Lösung: Mit dem zuvor besprochenen Deduktionstheorem lässt sich das Konsequenzproblem in ein Gültigkeitsproblem überführen.

Zur Lösung der Elimination der Konjunktion können wir die folgende Wahrheitstabelle erstellen:

$F$	$G$	$(F\wedge G)$	$((F\wedge G) \rightarrow F)$
$0$	$0$	$0$	$1$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

Damit zeigen wir, dass $((F\wedge G)\rightarrow F)$ eine Tautologie ist und folglich ergibt sich gemäß der Umkehrung des Deduktionstheorems: $(F\wedge G) \models F$ .

Die Einführung der Disjunktion wird analog gelöst, indem eine geeignete Wahrheitstabelle erstellt wird.

$F$	$G$	$(F\vee G)$	$(F\rightarrow(F\vee G))$
$0$	$0$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$1$	$1$

Hier sehen wir, dass $(F\rightarrow (F\vee G))$ eine Tautologie ist, und daher gilt gemäß der Umkehrung des Deduktionstheorems: $F\models (F\vee G)$

Und schließlich wird die Eigenschaft der Kontradiktion mit derselben Methode bewiesen:

$F$	$\neg F$	$(F\wedge \neg F)$	$G$	$((F\wedge \neg F)\rightarrow G)$
$0$	$1$	$0$	$0$	$1$
$0$	$1$	$0$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$

Mit dieser Wahrheitstabelle haben wir gezeigt, dass $((F\wedge \neg F)\rightarrow G)$ eine Tautologie ist und somit, gemäß der Umkehrung des Deduktionstheorems, gilt: $(F\wedge \neg F)\models G$ .

Semantische Äquivalenz und Eigenschaften

[ansehen]

DEFINITION: Wenn gleichzeitig gilt

F\models G

und

G\models F

, dann sagt man, dass

F

und

G

semantisch äquivalent sind. Dies wird dargestellt als

F\equiv G

Als Konsequenz dieser Definition gilt: Zwei Ausdrücke sind genau dann semantisch äquivalent, wenn sie dieselben Wahrheitswerte haben.

BEISPIEL: Es lässt sich mittels Wahrheitstabellen zeigen, dass die folgenden symmetrischen semantischen Äquivalenzen gelten:

(F\downarrow G) \equiv (G\downarrow F)

(F\vee G) \equiv (G\vee F)

(F\wedge G) \equiv (G\wedge F)

(F\leftrightarrow G) \equiv (G\leftrightarrow F)

(F\underline{\vee} G) \equiv (G\underline{\vee} F)

BEISPIEL: Wenn

F

ein beliebiger Ausdruck ist,

\top

eine Tautologie und

\bot

ein Widerspruch, dann lassen sich mittels Wahrheitstabellen die folgenden semantischen Äquivalenzen zeigen:

(F\wedge \top) \equiv F

(F\vee \top) \equiv \top

(F\wedge \bot) \equiv \bot

(F\vee \bot) \equiv F

Diese Äquivalenzen sind als Absorptionsgesetze bekannt.

BEISPIEL: In der Semantik der Aussagenlogik gelten die Distributivgesetze der Konjunktion und Disjunktion.

(F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H))

(F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H))

BEISPIEL: In der Semantik der Aussagenlogik gelten außerdem die DeMorgan’schen Gesetze.

\neg(F\wedge G) \equiv (\neg F \vee \neg G)

\neg(F\vee G) \equiv (\neg F \wedge \neg G)

ÜBUNG: Eine gute Übung besteht darin, mithilfe von Wahrheitstabellen zu zeigen, dass die semantischen Äquivalenzen der Absorptionsgesetze, der Distributivität und der DeMorgan’schen Gesetze tatsächlich gelten.

BEISPIEL: Zeigen Sie mithilfe semantischer Äquivalenzen, dass die folgende Äquivalenz gilt:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D))$ .

Lösung: Wir könnten diese Äquivalenz mit einer Wahrheitstabelle beweisen, aber dabei müssten wir mit einem Ausdruck mit 5 Aussagenvariablen arbeiten, was eine Wahrheitstabelle mit

2^5 = 32

Zeilen bedeutet — ein Szenario, das wir idealerweise vermeiden möchten. Um dies zu umgehen, nutzen wir die bereits bekannten Äquivalenzen.

Zunächst bemerken wir, dass $(E\vee \neg E)$ eine Tautologie ist. Bezeichnen wir diese Tautologie mit $\top$ . Dann erhalten wir mit den Absorptionsgesetzen:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B))$

Durch Anwendung der Distributivgesetze erhalten wir:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B))$

Schließlich ergibt sich durch Symmetrie:

$((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D))$

Daher ergibt sich durch Anwendung dieser Äquivalenzen:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D))$

was zu zeigen war.

Zusammenfassung

Wenn wir die Entwicklung dieses letzten Beispiels betrachten, sehen wir, dass mit steigender Anzahl von Variablen die Komplexität bei der Untersuchung von Konsequenz- und Äquivalenzproblemen exponentiell wächst, wenn wir uns ausschließlich auf Wahrheitstabellen verlassen. Wir haben jedoch gesehen, dass aus der Entwicklung der Modellidee etwas entsteht, das den deduktiven Techniken, die wir bereits ausführlich behandelt haben, sehr ähnlich ist. Diese Beziehung zwischen Modellen und Deduktionen werden wir bald näher untersuchen — und die Kombination beider Ansätze wird uns letztlich unzählige Kopfschmerzen beim Studium der Logik ersparen.