Kurs:Logik/Kurs

In diesem Kurs soll die formale Aussagenlogik erlernt werden.

In der Aussagenlogik gibt es Variablen, die nur einen der beiden Wahrheitswerte "wahr" (true) und "unwahr" (false) annehmen können. (Der Informationsgehalt entspricht einem Bit). Wir werden solche Variablen mit a,b,c,.. bezeichnen. Solche Variablen können nun mit den Logischen Operatoren "UND", "ODER" und "NICHT" (Negation) verknüpft werden: a UND b, c ODER b, NICHT a ODER c, b UND NICHT a etc...

Aussagen und Information

Die erste Frage, die sich bei der Thematik Aussagenlogik stellt, ist - "Was ist denn überhaupt eine Aussage?". Tja diese Frage kann man auf unterschiedlichste Art und Weise beantworten. Sprachwissenschaftlich gesehen sind Aussagen Sätze, die eine bestimmte Meinung, Vermutung oder Behauptung vermitteln, wobei der Inhalt der Aussage meist subjektiver Natur ist, das heisst jeder Mensch hat eine andere Aufassung davon, ob die Aussage sinnvoll, richtig, oder falsch ist. Da man sich aber als Naturwissenschaftler, Mathematiker oder eben Informatiker nur mit konkreten, objektiv überprüfbaren Fakten bzw. Daten befasst, hat diese Form der Aussage keinerlei Relevanz für uns. Wir befassen uns in diesem Kurs nur mit Aussagen von denen eindeutig entscheidbar ist, ob sie richtig oder falsch sind.

Die Aussage "Alle Menschen sind habgierig" ist von einem bestimmten Standpunkt aus gesehen vielleicht verständlich, für uns jedoch ohne Bedeutung, da es nicht eindeutig beweisbar ist, ob diese Aussage zutrifft oder nicht. Eine andere Form von Aussage, nämlich eine Aussage, die überprüfbar ist, nennt man logische Aussage. "23 ist durch 5 teilbar" ist z.B. eine solche logische Aussage, da man überprüfen kann, ob ${\frac {23}{5}}$ eine Natürliche Zahl ist oder nicht. Wie Sie bestimmt schon festgestellt haben, ist ${\frac {23}{5}}=4{,}6$ keine Natürliche Zahl und somit ist die Aussage falsch. Eine weitere Form von Aussage sieht folgendermassen aus: "Diese Aussage ist falsch!". Falls diese Aussage tatsächlich falsch ist, ist sie wahr... falls sie jedoch wahr ist, ist sie falsch! Wir haben es hier mit einem interessanten Paradoxon zu tun, welches für die Aussagenlogik allerdings auch keine Bedeutung hat.

Wir wollen uns in diesem Kurs nur mit Aussagen befassen, die entweder wahr oder falsch sind. Jede dieser Aussagen hat eine Datenmenge von einem Bit. Ein Bit ist das kleinst mögliche Maß einer Datenmenge, und es repräsentiert in unserem Fall den Wahrheitswert einer Aussage. Das Bit kann nur zwei Zustände annehmen (wahr oder falsch; 1 oder 0; High oder Low).

Vereinbarung

Unsere Aussagen werden mithilfe von Variablen dargestellt. Hierzu mal ein kleines Beispiel.

Die Aussage "Alice ist Bobs Schwester" soll durch die Variable $x\$ dargestellt werden. Das Gegenteil von $x\$ ist $\neg x\$. Somit meint $\neg x\$ folgende Aussage: "Alice ist nicht Bobs Schwester".

Alle Variablen, die in diesem Kurs auftauchen, werden mit Kleinbuchstaben bezeichnet, manchmal werden auch Indizes angehängt. $a\$ ist somit per Definition eine Variable, während $T\$ keine Variable darstellt. Die Wahrheitswerte der Variablen werden mit 1 (Aussage ist wahr) und 0 (Aussage ist falsch) bezeichnet.

Aussagenkombinationen haben immer genau einen Wahrheitswert für genau eine Variablenbelegung. Die Aussage $a\land b$ ist für $a=1\$ und $b=1\$ auch 1 (nur zur Erinnerung... wahr *g*)

In den sogenannten Wahrheitswerttabellen werden alle möglichen Kombinationen der Wahrheitswerte der jeweiligen Variablen und Aussagenkombinationen dargestellt.

Negation	Konjunktion
$a\$ $\neg a\$ 0 1 1 0	$a\$ $b\$ $a\land b$ 1 1 1 1 0 0 0 1 0 0 0 0

Die linke Tabelle zeigt zum Beispiel die Variable $a\$ und die Negation von $a\$ , sowie alle möglichen Wahrheitswerte die $a\$ annehmen kann (1 und 0), sowie die dazugehörigen Wahrheitswerte der Negation $\neg a\$ (ausgesprochen nicht a, oder non a). Die rechte Tabelle zeigt... na... genau, alle Kombinationen von $a\$ und $b\$ sowie den Wert für die Konjunktion $a\land b$.

Operatoren

Operatoren werden eingesetzt, um zwei Aussagen zu kombinieren, oder um eine Aussage bzw. Aussagenkombination zu Negieren (in ihr Gegenteil umzukehren). Operatoren sind somit DAS Werkzeug der Formalen Logik, da man mit ihnen verschiedene Kernaussagen kombiniert und auf den Wahrheitswert hin untersuchen kann. Dies soll an einem Beispiel verdeutlicht werden. Keine Bange, wenn Sie die einzelnen Operatoren noch nicht verstehen, Sie werden weiter unten im Einzelnen behandelt. Es werden jetzt zwei verschiedene Variablen mit Kernaussagen belegt, und diese dann kombiniert.

Kernaussage 1 - $a:\$ "Es regnet."

Kernaussage 2 - $b:\$ "Die Strasse ist nass."

Aussage 1 - $a\rightarrow b:\$ "Wenn es regnet, dann ist die Strasse nass."

Aussage 2 - $a\equiv b:\$ "Es regnet genau dann, wenn die Strasse nass ist."

Aussage 3 - $a\oplus b:\$ "Entweder es regnet, oder die Strasse ist nass."

Ausgehend von der alltäglichen Erfahrung würde man sagen, dass Aussagen 1 und 2 richtig sind, Aussage 3 jedoch Falsch. Dass die 3. Aussage falsch ist, scheint klar zu sein, da die Nassheit der Strasse eine notwendige Bedingung für Regen ist. Allerdings ist die Kernaussage 1 nur hinreichend für die Kernaussage 2 (Die Strasse kann auch aus anderen Gründen nass sein), somit ist nur die Aussage 1 wahr.

Im folgenden Abschnitt werden die einzelnen Operatoren genauer beschrieben. Wir werden uns auch von der Vorstellung lösen, dass die Variablen mit absolut real gegebenen Aussagen "gefüllt sein" müssen. Vielmehr wollen wir die Struktur einer Aussagenkombination untersuchen, und daraus die formale Wahrheit schlussfolgern. Zuerst sollen alle Aussagenlogischen Verknüpfungen eingeführt werden, die auch in der Philosophischen Logik und in bestimmten Soft- und Hardware Implementierungen eine Rolle spielen. Es kann jedoch gezeigt werden, dass sämtliche Verknüpfungen auch durch drei Operatoren $(\neg ,\land ,\lor )\$ gebildet werden können (siehe Transformationsgesetze).

Mathematisch gesehen können Operatoren auch als Funktionen realisiert werden. In der hier besprochenen Booleschen Algebra – präziser: dualen Booleschen Algebra – geht das sogar mit Relationen ohne Probleme. Das Attribut dual resultiert einfach aus der Tatsache, dass stets genau einer von zwei möglichen Werten das Ergebnis ist.

Die meisten hier betrachteten Operatoren sind binär, d.h. sie verknüpfen zwei Operanden miteinander. Es gibt aber auch unäre Operatoren, die nur auf einen Operanden wirken – so wie die Negation. Wenn es um mehr als zwei Operanden geht, dann werden einfach die Operatoren mehrfach benutzt. Bei einer Funktion die n Argumente hat wird dann von einer n-adischen Funktion gesprochen.

Schon gewusst? Die hier besprochene Logik wird auch als Aristotelische Logik bezeichnet. Derselbe sagte: Eine Aussage ist entweder wahr oder falsch. Ein Drittes gibt es nicht.

Ein Beispiel für die Konjunktion:

• operativ: $y=a\wedge b\wedge c...$
• funktional:$y=and\left(a,b,c,...\right)$

Ein (logischer) Operator verknüpft also genau zwei Operanden. Jeder Operand stellt genau einen der der beiden möglichen Werte wahr oder falsch dar und das Ergebnis ist ebenfalls entweder wahr oder falsch. Daraus kann die Anzahl aller Operatoren und der damit korrespondierenden binären Funktionen ermittelt werden. Jeder der beteiligten Komponenten, also a, b und y kann genau zwei Zustände annehmen, womit es gemäß den Gesetzen der Kombinatorik

$2^{2^{2}}=16$

Operatoren oder binäre Funktionen gibt.

a	b	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

Aus der Tabelle können viele Operatoren den indizierten Funktionen zugeordnet werden. So entspricht f₁₄ der Disjunktion (OR) und f₈ der Konjunktion (UND). Der hauptsächliche Sinn dieser Tabelle legt aber darin, die Operatoren zu klassifizieren.

• unär

f₀  = Nullfunktion (Kontradiktion)

Identität

Negation

f₁₅ = Tautologie (Einsfunktion)

• binär

f₈  = Konjunktion

f₁₄ = Disjunktion

f₇  = Sheffer-Funktion (NAND)

f₁  = Peirce-Funktion (NOR)

• • symmetrisch, relativ

f₉  = Äquivalenz $=\$

f₆  = Antivalenz $\neq$

• • asymmetrisch, relativ

f₂  = $<\$

f₄  = $>\$

f₁₁ = $\leq$

f₁₃ = $\geq$

Beim Nachzählen ergeben sich nur 12 zugeordnete Funktionen und zwei (Negation, Idenität) mit denen keine Funktion assoziiert ist. Wie sollen denn auch binäre Funktionen unär betrachtet werden?

Ganz einfach – sie sind zweimal vorhanden.

Die Identität ist sowohl für das Argument a, als auch für das Argument b in der Tabelle vorhanden. Gleiches gilt für die Negation.

f(a) = a = f₁₂ und f(a) = ¬a = f₃

f(b) = b = f₁₀ und f(b) = ¬b = f₅

Jetzt sind alle Operatoren, Relationen und Funktionen zugeordnet.

Aufgabe:

Wie viele unäre Funktionen mit dualem Argument sind möglich?

Aufgabe:

Wie wird die Äquivalenz über zwei asymmetrische und eine symmetrische Funktion erklärt?

Hinweis: Kon- und Disjunktion sind symmetrisch.

Negation

$a\$	$\neg a\$
0	1
1	0

Symbol: $\neg a\$ oder ${\overline {a}}$

Die Negation, bzw. der NICHT- Operator macht aus einem Wahrheitswert das Gegenteil. Wenn eine Aussage wahr ist, so ist ihre Negation falsch und umgekehrt. Die Negation kann nur auf eine Variable bzw. Variablenkombination einwirken (unärer Operator), ausserdem besitzt die Negation von allen Operatoren die stärkste Bindung, soll heissen, dass bei einer Kombination von Variablen und Operatoren, die Negation als Erstes analysiert werden muss (ausser bei Klammersetzung, welche stets am Stärksten bindet). In der Digitaltechnik wird für die technische Realisierung einer Negation ein Inverter eingesetzt, welcher den Spannungspegel von High auf Low und umgekehrt verändert.

Konjunktion

$a\$	$b\$	$a\land b$
1	1	1
1	0	0
0	1	0
0	0	0

Symbol: $a\land b$ oder $a\cdot b$

Die Konjunktion, bzw. der UND- Operator kombiniert 2 Variablen miteinander, das Ergebniss ist immer genau dann wahr, wenn beide Wahrheitswerte wahr sind. Beispielsweise ist der Satz "Anja und Tanja sind Geschwister" nur dann wahr, wenn Tanja UND Anja die selben Eltern haben. Technisch wird eine Konjunktion mit einem Und-Gatter realisiert, welches genau dann den High-Pegel durchschaltet, wenn auf allen Eingängen ein High-Pegel anliegt.

Disjunktion

$a\$	$b\$	$a\lor b$
1	1	1
1	0	1
0	1	1
0	0	0

Symbol: $a\lor b$ oder $a+b\$

Die Disjunktion, bzw. der ODER- Operator kombiniert 2 Variablen miteinander, das Ergebniss ist wahr, wenn eine der beiden Aussagen, oder beide Aussagen wahr sind. Die Disjunktion darf nicht mit dem umgangssprachlich geläufigen 'oder' verwechselt werden, denn dies ist ein 'ausschliessendes oder' (siehe Antivalenz). Technisch wird eine Disjunktion mit einem Oder-Gatter realisiert, welches immer dann einen High-Pegel durchschaltet, wenn auf mindestens einen der Eingänge ein High-Pegel anliegt, es wird dann meist für den weiteren Aufbau logischer Gatter und Verknüpfungen verwendet (z.B. NOR-Gatter).

Implikation

$a\$	$b\$	$a\rightarrow b\$
1	1	1
1	0	0
0	1	1
0	0	1

Symbol: $a\rightarrow b\$ oder $a\supset b$

Die Implikation kann man umgangssprachlich als Schlussfolgerung bzw. Kausalitätsbeziehung verstehen. Implikationen haben somit eine "Wenn...,dann..."-Gestalt. Die wichtigste Eigenschaft der Implikation ist, dass aus einer wahren Aussage niemals eine falsche gefolgert werden kann, insofern ist die Aussage $1\rightarrow 0$ die einzige falsche Implikation. Dieser, auf den ersten Blick, etwas unlogisch erscheinende Zusammenhang ist in der Wikipedia unter -Hinreichende und notwendige Bedingung- etwas genauer erklärt. In der (Hochsprachen-)Programmierung werden Implikationen als IF-THEN-ELSE- bzw. SWITCH-Strukturen realisiert.

Äquivalenz

$a\$	$b\$	$a\Leftrightarrow b\$
1	1	1
1	0	0
0	1	0
0	0	1

Symbol: $a\Leftrightarrow b$ oder $a\equiv b\$

Die Äquivalenz drückt eine Gleichheitsbeziehung aus, d.h. wenn sich die Werte der 2 verknüpften Aussagen nicht unterscheiden, spricht man von Äquivalenz. Umgangssprachlich würde man eine Äquivalenz mit einem "...ist genau dann, wenn..."-Satz ausdrücken. Die beiden verknüpften Aussagen bedingen sich also gegenseitig hinreichend, statt $a\Leftrightarrow b$ könnte man also auch $(a\rightarrow b)\land (b\rightarrow a)$ schreiben. In der Digitaltechnik wird die Äquivalenz durch ein XNOR-Gatter realisiert. In der Programmiersprache c++ werden Ausdrücke mit "==" auf äquivalenz verglichen.

Antivalenz

$a\$	$b\$	$a\oplus b$
1	1	0
1	0	1
0	1	1
0	0	0

Symbol: $a\oplus b$

Die Antivalenz ist, wie der Name schon vermuten lässt, das Gegenteil der Äquivalenz. Dass heisst, die antivalent verknüpften Aussagen sind nur dann wahr, wenn sich beide Wahrheitswerte unterscheiden. Am ehesten kann man die Antivalenz mit dem umgangssprachlichen "entweder..., oder..." vergleichen, also mit dem ausschliessenden oder. Technisch wird die Antivalenz mithilfe eines XOR-Gatters realisiert.

Bindungen

...TODO...

Ein etwas praxisnäheres Beispiel, das ihnen auch den Umgang mit den Wahrheitswerttabellen etwas näher bringen soll ist ein technisches System. Stellen wir uns vor wir haben ein Gerät mit 2 Grundbauteilen (a, b) und einer LED(l). Für ein defektes Bauelement schreiben wir die Variable auf (a, b), die LED-Variable bezeichnen wir, wenn sie leuchtet, mit - l -. Es sind folgende Eigenschaften des Geräts bei einem Fehler bekannt:

• Bauteil A oder Bauteil B oder beide sind defekt. - $a\lor b$
• Wenn das Bauteil A defekt ist, ist auch das Bauteil B defekt. - $a\rightarrow b\$
• Wenn das Bauteil B defekt ist, und die LED leuchtet, so ist Bauteil A nicht defekt - $(b\land l)\rightarrow \neg a$
• Die LED leuchtet. - $l\$

Nun müssen wir, ausgehend aus unseren 4 Aussagen des Gerätes eine aussagenlogische Formel basteln, die diese 4 Eigenschaften berücksichtigt. Es trifft die 1. Eigenschaft UND die 2. UND die 3. UND die 4. zu, also müssen wir die Aussagen konjunktiv verknüpfen. Das ganze sieht dann so aus.

$(a\lor b)\land (a\rightarrow b)\land ((b\land l)\rightarrow \neg a)\land l$

Jetzt haben wir unsere fertige Aussage, nun müssen wir nurnoch alle möglichkeiten durchgehen, die die Variablen annehmen können. Für ein defektes Bauteil, bzw. die leuchtende LED schreiben wir eine 1. Wenn also folgende Kombination im linken Teil der Tabelle auftritt...

$a\$	$b\$	$l\$
1	0	1

...bedeutet das, dass wir annehmen Bauteil A sei defekt, Bauteil B sei intakt und die LED leuchtet. Zuerst müssen wir die inneren Ausdrücke, also die Aussagen in den Klammern auswerten.

$a\$	$b\$	$l\$	$(a\lor b)$	$\land$	$(a\rightarrow b\ )$	$\land$	$((b\land l)$	$\rightarrow \$	$\neg a\$	$\land$	$l\$
0	0	0	0		1		0	1	1		0
0	0	1	0		1		0	1	1		1
0	1	0	1		1		0	1	1		0
0	1	1	1		1		1	1	1		1
1	0	0	1		0		0	1	0		0
1	0	1	1		0		0	1	0		1
1	1	0	1		1		0	1	0		0
1	1	1	1		1		1	0	0		1

Nun müssen wir die äusseren Ausdrücke, also die UND-Verknüpfungen analysieren, indem wir die Klammerausdrücke miteinander in (UND-)verbindung setzen.

$a\$	$b\$	$l\$	$(a\lor b)$	$\land$	$(a\rightarrow b\ )$	$\land$	$((b\land l)$	$\rightarrow \$	$\neg a\$	$\land$	$l\$
0	0	0	0	0	1	0	0	1	1	0	0
0	0	1	0	0	1	0	0	1	1	1	1
0	1	0	1	1	1	0	0	1	1	0	0
0	1	1	1	1	1	1	1	1	1	1	1
1	0	0	1	0	0	0	0	1	0	0	0
1	0	1	1	0	0	0	0	1	0	1	1
1	1	0	1	1	1	1	0	1	0	0	0
1	1	1	1	1	1	0	1	0	0	0	1

Wir sehen, dass es nur eine Möglichkeit gibt, in der alle Aussagen der Formel wahr sind. Somit kann nur eine Möglichkeit als Fehler in Frage kommen (a - intakt;b - defekt;l - leuchtet).

Gesetze

Jetzt wollen wir uns eingehender mit den Rechenregeln und Gesetzen der Aussagenlogik befassen. Wie jedes Mathematische Kalkül hat auch die Aussagenlogik bestimmte Gesetzmäßigkeiten, die aus der Struktur der Operatoren heraus resultieren. Die Beweise zu den Gesetzen könnt ihr in Beweise nachschlagen. In der Aussagenlogik gibt es immer mehrere Formen von Aussagen, dass heisst, dass jede Aussage auch durch eine andere äquivalente Aussage ausgedrückt werden kann. Besonders ist hierbei, dass es sogenannte Normalformen gibt, welche alle Aussagen nur mit drei Operatoren konstruieren. Zwischen Konjunktion und Disjunktion besteht ein besonderer Dualismus, denn jede konjunktiv verknüpfte Aussage kann durch eine äquivalente disjunktiv verknüpfte Aussage dargestellt werden. Deshalb gelten die Grundgesetze (und nur die!) für die Konjunktion und die Disjunktion.

Grundgesetze

	Konjunktion	Disjunktion
1. Kommutativität:	$a\land b\equiv b\land a$	$a\lor b\equiv b\lor a$
2. Assoziativität:	$a\land (b\land c)\equiv (a\land b)\land c$	$a\lor (b\lor c)\equiv (a\lor b)\lor c$
3. Distributivität:	$a\land (b\lor c)\equiv (a\land b)\lor (a\land c)$	$a\lor (b\land c)\equiv (a\lor b)\land (a\lor c)$
4. Absorption:	$a\land (a\lor b)\equiv a$	$a\lor (a\land b)\equiv a$
5. Komplement:	$a\land \neg a\equiv 0$	$a\lor \neg a\equiv 1$
6. Neutralität der wahren Aussage:	$a\land 1\equiv a$	$a\lor 1\equiv 1$
7. Neutralität der falschen Aussage:	$a\land 0\equiv 0$	$a\lor 0\equiv a$
8. Identität:	$a\land a\equiv a$	$a\lor a\equiv a$
9. De Morgansche Regel:	$\neg (a\land b)\equiv \neg a\lor \neg b$	$\neg (a\lor b)\equiv \neg a\land \neg b$

Negationsgesetze

Die Negationsgesetze beschreiben, was mit den Relationen bzw. Operatoren passiert, wenn die ganze Aussage negiert wird. Im Prinzip sind die De Morganschen Regeln auch Negationsgesetze, allerdings haben sie grundlegende Bedeutung für die Normalformen, deshalb werden sie als Grundgesetze definiert.

Mehrfache Negation

Das Prinzip der doppelten Verneinung ist das wichtigste Negationsgesetz, denn wenn eine falsche Aussage falsch ist, so ist sie wahr.

$a\equiv \neg (\neg a\ )\equiv \neg (\neg (\neg (\neg a\ )))$

$\neg a\equiv \neg (\neg (\neg a\ ))\equiv \neg (\neg (\neg (\neg (\neg a\ ))))$

Negation der Implikation

$\neg (a\rightarrow b)\equiv a\land \neg b$

Negation der Äquivalenz

$\neg (a\equiv b)\equiv a\oplus b$

Negation der Antivalenz

$\neg (a\oplus b)\equiv a\equiv b$

Boolesche Normalformen

Boolesche Formeln

Konkrete Realisierungen