Aus Wikibooks

[Bearbeiten] Motivation

Die Aussagenlogik ist nicht nur eines der einfachsten, sondern auch eines der am häufigsten verwendeten logischen Systeme. Viele kompliziertere logische Systeme, wie auch die Prädikatenlogik verwenden die Aussagenlogik als Grundlage und erweitern diese.

Mit Hilfe der Aussagenlogik ist es möglich, eine Reihe von Argumenten - so auch das Beispiel aus der Einleitung - auf ihre Folgerichtigkeit hin zu überprüfen.

[Bearbeiten] Eine formale Sprache

[Bearbeiten] Aufbau einer formalen Sprache (Syntax)

Eine formale Sprache besteht aus einem Alphabet und einer Grammatik. Das Alphabet bestimmt dabei, welche Zeichen Bestandteil der Sprache sind; es wird manchmal auch als Vokabular oder Lexikon bezeichnet. Die Grammatik bestimmt hingegen, wie die Zeichen zu gültigen Sätzen oder Formeln zusammengesetzt werden können.

Da es für die Aussagenlogik sehr viele verschiedene Einsatzgebiete gibt, gibt es keine einheitliche Notation. Dies äußert sich bereits im verwendeten Alphabet. Das hier vorgestellte Alphabet hat den Vorteil, dass es sich sehr gut in Bezug auf die Anforderungen der Prädikatenlogik erweitern lässt.

[Bearbeiten] Alphabet

In der Aussagenlogik gibt es 3 Arten von Zeichen:

Satzbuchstaben
Junktoren
Klammern

[Bearbeiten] 1. Satzbuchstaben

Satzbuchstaben sind Großbuchstaben des lateinischen Alphabetes. Sollten die 26 Buchstaben nicht ausreichen, können sie mit einem Index versehen werden, der nach dem Buchstaben tiefgestellt zu schreiben ist.

Beispiele für Satzbuchstaben wären also: A, B, C, D, Y, Z, $A 1$ , $B 23$ , $C 5977$ .

Die Satzbuchstaben stehen für einfache Aussagen; aus Sicht der Logik ist eine Aussage ein Satz, der wahr oder falsch ist oder – allgemeiner – dem genau ein Wahrheitswert zugeordnet ist ^[1].

[Bearbeiten] 2. Junktoren

Die zweite wichtige Gruppe von Zeichen sind die Junktoren, auch Verknüpfungszeichen genannt.

Die Junktoren sind:

der Negator $\neg$ (lat. non)
der Konjunktor $\wedge$ (lat. et)
der Disjunktor $\vee$ (lat. vel)
der Subjunktor $\rightarrow$ (Pfeil)
der Bisubjunktor $\leftrightarrow$ (Doppelpfeil)

[Bearbeiten] 3. Klammern

Die dritte Gruppe von Zeichen sind die Klammern ( und ).

[Bearbeiten] Grammatik

Genausowenig wie in einer natürlichen Sprache wie Deutsch nicht jede beliebige Anordnung von Worten einen grammatikalisch sinnvollen Satz ergibt, stellt auch nicht jede beliebige Anordnung von Zeichen des Alphabets einer formalen Sprache eine gültige Formel dar. Damit eine Anordnung von Zeichen eine gültige Formel in der Aussagenlogik bildet, muss sie gewissen Regeln genügen. Die Regeln sind dabei als Bildungsvorschriften definiert:

Jeder Satzbuchstabe ist eine Formel.
Ist $\phi\,$ eine Formel, so ist auch $\neg \phi$ eine Formel.
Sind sowohl $\phi\,$ als auch $\psi\,$ gültige Formeln, so sind auch $(\phi \wedge \psi)$ , $(\phi \vee \psi)$ , $(\phi \rightarrow \psi)$ und $(\phi \leftrightarrow \psi)$ gültige Formeln.
Nichts anderes ist eine gültige Formel.

Dieser Begriff der Gültigkeit bezieht sich ausschließlich auf die äußere Form der Formel; über eine Wahrheit in einem inhaltlichen Sinne wird hier keine Aussage getroffen. Eine alternative, häufig anzutreffende Bezeichnung, die diesem möglichen Missverständnis aus dem Wege geht, ist Wohlgeformtheit. In der englischsprachigen Literatur schreibt man häufig auch "wff" für "well formed formula" (wohlgeformte Formel).

So ist z.B. $((A\wedge \neg B)\rightarrow C)$ eine gültige Formel. Aus 1. und 2. folgt, dass $\neg B$ eine gültige Formel ist. Da nach 1. auch $A$ eine gültige Formel ist, ergibt 3., dass auch $(A\wedge \neg B)$ eine gültige Formel ist. Eine erneute Anwendung von 1. und 3. zeigt dann der Gültigkeit von $((A\wedge \neg B)\rightarrow C)$ .

Beispiele für ungültige Formeln sind $A\vee B$ , $(A\wedge B\wedge C)$ oder $A\neg \vee B$ , denn diese entstehen nicht durch eine Anwendung obiger Regeln: Bei der ersten Formel fehlen die Klammern, bei der zweiten muss man sich für $((A\wedge B)\wedge C)$ oder $(A\wedge (B\wedge C))$ entscheiden, um eine gültige Formel zu erhalten). Überlege selbst, was an der dritten Formel nicht stimmt!

Durch sog. Klammerregeln lassen sich einige Probleme mit ungültigen Formeln beheben:

Klammerregeln

$\wedge$ und $\vee$ binden stärker als $\rightarrow$ und $\leftrightarrow$ . Also z.B.

$A\wedge B \rightarrow C = (A\wedge B) \rightarrow C$ .

Iterierte (d.h. wiederholte) $\wedge$ und $\vee$ - Verbindungen sind von links her zu klammern; z.B.

$A\wedge B \wedge C \wedge D=((A\wedge B)\wedge C)\wedge D)$

[Bearbeiten] Interpretation der formalen Sprache: Semantik

[Bearbeiten] Wahrheitswerte

Bereits in der Einleitung haben wir zur Definition der Folgerichtigkeit die Begriffe wahr und falsch verwendet. Stattdessen benutzt man häufig auch die Bezeichnungen

1 für wahr, 0 für falsch

.

Im überwiegenden Teil der Anwendungen der Logik sind diese beiden Begriffe die sogenannten Wahrheitswerte. Nur in seltenen und speziellen Fällen wird an Stelle dieser zweiwertigen Logik eine mehrwertige Logik verwendet.

Einen zentralen Begriff stellt im Zusammenhang mit den Wahrheitswerten die Bewertung dar:

Eine Bewertung $\mathfrak{B}$ weist jedem Satzbuchstaben genau einen Wahrheitswert zu.

Beispiele für Bewertungen sind also:

$\mathfrak{B}_1(A)=\mathfrak{B}_1(B)=\mathfrak{B}_1(C)=\mathfrak{B}_1(D)= ... = ''wahr''$ : alle wahr

$\mathfrak{B}_2(A)=\mathfrak{B}_2(B)=\mathfrak{B}_2(C)=\mathfrak{B}_2(D)= ... = ''falsch''$ : alle falsch

$\mathfrak{B}_3(A)=\mathfrak{B}_3(B)=''wahr'', \mathfrak{B}_3(C)=\mathfrak{B}_3(D)=\mathfrak{B}_3(E)=...=''falsch''$ : A, B: wahr, Rest: falsch

Eine konkrete Bewertung stellt man am einfachsten durch eine Tabelle dar, in der links die Satzbuchstaben und rechts die zugehörigen Bewertungen aufgeführt sind (eine solche Tabelle wird auch Wahrheitstafel genannt):

Satzbuchst.	Bewertung
A	$\mathfrak{B}(A)$
B	$\mathfrak{B}(B)$
C	$\mathfrak{B}(C)$
D	$\mathfrak{B}(D)$
...	...

Als Beispiel geben wir die Wahrheitstabelle für die eben definierte Bewertung $\mathfrak{B}_3$ an, wobei wir hier und in Zukunft zur Abkürzung stets "w" für "wahr" und "f" für "falsch" schreiben werden:

Satzbuchst.	Bewertung
A	w
B	w
C	f
D	f
...	...

[Bearbeiten] Wahrheitstafeln der Junktoren

Um in weiterer Folge etwas über den Wahrheitswert einer beliebigen Formel aussagen zu können, ist es notwendig, die Wahrheitstafeln der Junktoren festzulegen.

Hier die Wahrheitstafel des Negators:

$\phi\,$	$\neg \phi$
w	f
f	w

Zu lesen ist diese Wahrheitstafel wie folgt: Ist eine beliebige Formel $\phi\,$ wahr (w), so ist ihre Negation $\neg \phi$ falsch (f), ist hingegen $\phi\,$ falsch, so ist ihre Negation wahr - der Negator dreht sozusagen den Wahrheitswert einer Funktion um. Eine Besonderheit der Wahrheitstafel des Negators ist, dass sie nur zwei Spalten und zwei Zeilen besitzt - der Negator wirkt nämlich nur auf eine Formel $\phi\,$ . Man sagt daher auch: der Negator ist ein einstelliger Junktor.

Im Gegensatz dazu wirken Konjunktor, Disjunktor, Subjunktor und Bisubjunktor auf zwei Formeln; man nennt sie daher auch zweistellige Junktoren. In den folgenden Wahrheitstafeln heißen diese zwei stellvertretenden Formeln $\phi\,$ und $\psi\,$ . Der Grund für die Verwendung dieser Symbole, die nicht Teil der verwendeten formalen Sprache sind, ist es, zu betonen, dass es sich auch wirklich um beliebige Formeln handeln kann, also insbesonder auch zusammengesetzte Formeln und nicht etwa nur Aussagebuchstaben.

Die Wahrheitstafel für den Konjunktor lautet:

$\phi\,$	$\psi\,$	$(\phi \wedge \psi)$
w	w	w
w	f	f
f	w	f
f	f	f

Eine Formel, die durch die Verbindung zweier Formeln durch den Konjunktor entsteht, ist eine Konjunktion. Eine Konjunktion ist genau dann wahr, wenn beide Formeln, aus der sie besteht, wahr sind. Wie auch die lateinische Bezeichnung et für den Konjunktor naheliegt, hat der Konjunktor eine enge Verwandtschaft mit dem lateinischen et, also dem deutschsprachigen und.

Die Wahrheitstafel für den Disjunktor lautet:

$\phi\,$	$\psi\,$	$(\phi \vee \psi)$
w	w	w
w	f	w
f	w	w
f	f	f

Eine Formel, die durch die Verbindung zweier Formeln durch den Disjunktor entsteht, ist eine Disjunktion. Eine Disjunktion ist genau dann wahr, wenn mindestens eine der Formeln, aus der sie besteht, wahr ist. Wie auch die lateinische Bezeichnung vel für den Disjunktor naheliegt, hat der Disjunktor eine enge Verwandtschaft mit dem lateinischen vel, das im Deutschen einem einschließenden oder entspricht.

Die Wahrheitstafel für den Subjunktor lautet:

$\phi\,$	$\psi\,$	$(\phi \rightarrow \psi)$
w	w	w
w	f	f
f	w	w
f	f	w

Eine Formel, die durch die Verbindung zweier Formeln durch den Subjunktor entsteht, ist eine Subjunktion. Eine Subjunktion ist wahr, wenn sie ein falsches Vorderglied oder ein wahres Nachglied hat. Die Bedeutung der Subjunktion lässt sich dabei mit einer Bedeutung von wenn, dann vergleichen. Ein Beispiel für diese Bedeutung von wenn - dann wäre: "Wenn es regnet, dann ist die Straße nass." Diese Aussage ist wahr, wenn die Straße nass ist oder wenn es erst gar nicht regnet. Nicht in die Irre führen lassen sollte man sich im Fall, dass es nicht regnet und die Straße trotzdem nass ist. In diesem Fall ist die Aussage wahr. Formal kann man das damit begründen, dass die Bedingung des wenn-Teils nicht eingetreten ist und die Aussage in diesem Fall gar nichts aussagt. Anschaulich könnte man diesen Sachverhalt damit begründen, dass ja jemand mit dem Gartenschlauch die Straße abspritzen könnte. Der Fall, dass die Straße nass ist, obwohl es nicht regnet, stellt also definitiv keinen Widerspruch zur Aussage "Wenn es regnet, ist die Straße nass." dar.

Das einzige, was der Wahrheit eines wenn - dann-Satzes widerspricht, ist ein Fall, in dem das Vorderglied wahr ist, also die Bedingung eintritt, das Nachglied aber falsch ist, die Behauptung also nicht eintritt. Sollte im oben ausgeführten Beispiel also der Fall auftreten, dass es geregnet hat, aber die Straße entgegen unserer Erwartung nicht nass ist, so ist die Aussage "Wenn es regnet, ist die Straße nass." widerlegt, also falsch.

Die Wahrheitstafel für den Bisubjunktor lautet:

$\phi\,$	$\psi\,$	$(\phi \leftrightarrow \psi)$
w	w	w
w	f	f
f	w	f
f	f	w

Eine Formel, die durch die Verbindung zweier Formeln durch den Bisubjunktor entsteht, ist eine Bisubjunktion. Eine Bisubjunktion ist genau dann wahr, wenn beide Formeln, aus der sie besteht, den selben Wahrheitswert besitzen. Im Deutschen entspricht der Bisubjunktor einer Konstruktion wie dann und nur dann, wenn oder genau dann, wenn.

[Bearbeiten] Weitere Junktoren

Neben den oben angeführten Junktoren gibt es in verschiedenen Anwendungsgebieten der Aussagenlogik den Bedarf für weitere Junktoren.

In der Mathematik kennt man beispielsweise den Sheffer-Strich, der unter dem Namen NAND-Gatter (s. auch den Artikel NAND) eine große Bedeutung in der Technischen Informatik erlangt hat.

Der Sheffer-Strich $|\,$ stellt eine Kurzschreibweise für die Negation einer Konjunktion dar. $(\phi | \psi)\,$ ist also eine alternative Schreibweise für $\neg (\phi \wedge \psi)$ .

Man kann den Sheffer-Strich aber auch als Junktor mit folgender Wahrheitstafel definieren:

$\phi\,$	$\psi\,$	$(\phi \| \psi)\,$
w	w	f
w	f	w
f	w	w
f	f	w

Die Besonderheit des Shefferschen Striches ist, dass jede aussagenlogische Formel so umgeschrieben werden kann, dass alle Junktoren durch ihn ersetzt werden.

$\neg \phi$ ist äquivalent zu $(\phi | \phi)\,$
$(\phi \wedge \psi)$ ist äquivalent zu $((\phi | \psi) | (\phi | \psi))\,$
$(\phi \vee \psi)$ ist äquivalent zu $((\phi | \phi) | (\psi | \psi))\,$

Da man jede aussagenlogische Formel sowohl in eine Konjunktive Normalform, d.h. eine Konjunktion von Disjunktionen, als auch in eine Disjunktive Normalform, d.h. eine Disjunktion von Konjunktionen überführen kann, reicht es, die drei oben aufgeführten Behauptungen zu beweisen. Denn man kann zunächst die konjunktive oder disjunktive Normalform herstellen und dann die Junktoren Negation, Konjunktion und Disjunktion durch den Sheffer-Strich ersetzen. Da wie schon erwähnt, die technische Realisierung des Sheffer-Strichs in der Informatik das NAND- Gatter ist, wird die zentrale Bedeutung dieses Gatters deutlich: Mit NAND- Gattern als Grundbausteinen lassen sich alle aussagelogischen Gatter aufbauen.

[Bearbeiten] Anwendung

[Bearbeiten] Fragestellungen

Eine der wichtigsten und auch ältesten Fragestellungen, die man mit Hilfe logischer Systeme beantworten kann, ist, ob ein Argument folgerichtig ist. Eng verbunden mit dieser Frage ist die Frage nach der Erfüllbarkeit einer Formelmenge. Eine weitere häufige Fragestellung ist, wann zwei Formeln äquivalent sind.

[Bearbeiten] Folgerichtigkeit

Unter einem Argument verstehen wir das folgende Schema:

Gegeben die Prämissen (Voraussetzungen)

$δ 1$
$δ 2$
...

---

Also gilt die Konklusion (die Folgerung): $φ$

Die Frage der Folgerichtigkeit lässt sich in der Aussagenlogik wie folgt formulieren: Die Formeln, die als Prämissen dienen, werden zur Formelmenge $Δ$ zusammengefasst. Man schreibt $\Delta \models \phi$ und spricht, $\phi\,$ folgt aus $\Delta\,$ .

$\Delta \models \ \phi$ genau dann, wenn bei jeder Bewertung, bei der alle Formeln aus $\Delta\,$ wahr sind, auch $\phi\,$ wahr ist.

[Bearbeiten] Erfüllbarkeit

Die Erfüllbarkeit ist die Eigenschaft einer Formelmenge, die besagt, dass es mindestens eine Bewertung gibt, bei der jede einzelne Formel $\phi \in \Delta$ wahr ist.

$\Delta\,$ ist genau dann erfüllbar, wenn eine Bewertung $\mathfrak{B}$ existiert, sodass alle Formeln aus $Δ$ (gleichzeitig) wahr sind.

[Bearbeiten] Tautologie

Eine Tautologie ist eine Aussage, die bei jeder Bewertung wahr ist.

Eine Aussage $\phi\,$ ist genau dann tautologisch, wenn sie bei jeder Bewertung wahr ist.

[Bearbeiten] Verwendung von Wahrheitstafeln

Wahrheitstafeln, wie wir sie bereits zum Einführen der Junktoren verwendet haben, sind ein wichtiges und universell einsetzbares Werkzeug in der Logik. So kann man mit Hilfe von Wahrheitstafeln alle Eigenschaften von Formeln (Tautologie, Kontradiktion, Erfüllbarkeit) sowie von Formelmengen (Äquivalenz, Folgerichtigkeit) nachweisen.

[Bearbeiten] Überprüfen auf Tautologie

Betrachten wir nun die Funktionsweise der Wahrheitstafeln an folgendem Beispiel: Angenommen, wir wollen die Formel $(A \vee \neg A)$ untersuchen:

Zunächst erstellen wir für jeden Satzbuchstaben, der in der Formel bzw. in der Formelmenge vorkommt eine Spalte. Danach erstellen wir für jede Formel, also auch für jede Teilformel ebenfalls jeweils eine Spalte.

In unserem Beispiel haben wir also folgende Spalten:

A	(A	$\vee$	$\neg$	A)

Die Zeilen representieren alle möglichen Wahrheitsbelegungen der Satzbuchstaben. Da wir in unserem Beispiel nur den einen Satzbuchstaben A enthalten haben, gibt es auch nur 2 Möglichkeiten: A kann wahr oder falsch sein.

Unsere Wahrheitstafel schaut damit wie folgt aus:

A	(A	$\vee$	$\neg$	A)
w
f

Jetzt können wir mit dem Ausfüllen der Wahrheitstafel beginnen. Wir gehen dabei von innen nach außen vor. Das bedeutet wir beginnen mit den Aussagebuchstaben. Wir tragen nun die Wahrheitswerte bei jedem Vorkommen eines Satzbuchstabens ein. Unsere Tafel schaut damit so aus:

A	(A	$\vee$	$\neg$	A)
w	w			w
f	f			f

Nun können wir damit beginnen, die Junktionen auszuwerten. Hier spielt die Reihenfolge - nämlich von innen nach außen eine wesentliche Rolle.

Werten wir also den inneren Negator aus. Die Negation ist dann wahr, wenn die ursprüngliche Behauptung falsch ist und dann falsch, wenn die ursprüngliche Behauptung wahr ist - der Wahrheitswert wird also umgedreht.

Für unsere Wahrheitstafel bedeutet das:

A	(A	$\vee$	$\neg$	A)
w	w		f	w
f	f		w	f

Nun können wir die Disjunktion auflösen. Die Disjunktion ergibt bekanntlich immer dann Wahrheit, wenn mindestens eines ihrer Glieder Wahrheit ergibt. In unserem Fall ist nun das erste Glied das A und das zweite Glied $\neg$ A.

Unsere Wahrheitstafel sieht nun wie folgt aus:

A	(A	$\vee$	$\neg$	A)
w	w	w	f	w
f	f	w	w	f

Nun haben wir auch die äußerste Junktion aufgelöst. Die Wahrheitswerte in dieser Spalte entsprechen nun den Wahrheitswerten unserer Formel. In diesem Fall steht in jeder Zeile ein w. Die Formel ist also eine Tautologie.

[Bearbeiten] Überprüfen auf Folgerichtigkeit

Betrachten wir nun ein anderes Beispiel, das uns demonstriert, wie Wahrheitstafeln dazu verwendet werden können, die Folgerichtigkeit eines Argumentes zu prüfen.

Gegeben sei folgenes Argument:

$A$
$(A \vee B)$

---

Also gilt: $B$

Wir konstuieren wieder eine Wahrheitstafel, mit den Formeln als Spalten und den Wahrheitsbelegungen als Zeilen:

A	B		(A	$\vee$	B)		B
w	w
w	f
f	w
f	f

Diese Tafel füllen wir nun analog zum vorigen Beispiel aus. Diesmal achten wir jedoch besonders auf den Zusammenhang zwischen Prämissen und Konklusion. Folgerichtig ist unser Argument nämlich dann und nur dann, wenn es keine Wahrheitsbelegung (Zeile) gibt, in der alle Prämissen wahr sind, aber die Konklusion falsch ist. Eine solche Zeile markieren wir als "böse" Zeile.

A	B	A	(A	$\vee$	B)	B
w	w	w	w	w	w	w
w	f	w	w	w	f	f (böse Zeile!)
f	w	f	f	w	w	w
f	f	f	f	f	f	f

Es gibt also eine böse Zeile: Es ist die zweite von oben, bei der beide Prämissen $A$ sowie $(A \vee B)$ wahr sind. Daher können wir das Argument als nicht folgerichtig klassifizieren. Geht es also nur um die Frage der Folgerichtigkeit, so kann das Ausfüllen der Wahrheitstafel natürlich bereits abgebrochen werden, sobald eine "böse" Zeile gefunden wurde, und beim obigen Beispiel müssten wir die dritte und vierte Zeile gar nicht mehr ausfüllen.

Beim folgenden Beispiel lässt sich mit dieser Methode die Folgerichtigkeit zeigen; denn keine der Zeilen erweist sich als böse:

Gegeben sei das Argument:

$(A \vee B)$
$\neg A$

---

Also gilt: $B$

Die zugehörige Wahrheitstafel ist die folgende:

A	B	$\neg$ A	(A	$\vee$	B)	B
w	w	f	w	w	w	w
w	f	f	w	w	f	w
f	w	w	f	w	w	w
f	f	w	f	f	f	f

Beachte, dass die letzte Zeile nicht böse ist - denn es ist zwar die Konklusion falsch, aber auch eine der Prämissen.

Das Ausfüllen der Wahrheitstafel kann unter Umständen sehr aufwändig werden; denn die Anzahl der Wahrheitsbelegungen und damit der Zeilen wächst mit $2 n$ wenn n die Anzahl der unterschiedlichen Aussagebuchstaben ist.

[Bearbeiten] Hinweise

↑ Aussagen

[0] Aussagen

[1]

Mathematik: Logik: Aussagenlogik