Aussagenlogik

Mit der Aussagenlogik lässt sich die Struktur von logischen Aussagen kurz und präzise erfassen.
Wir können mit ihr erkennen, welche Arten von Aussagen unabhängig von ihrem Inhalt immer wahr sind, oder ob 2 Aussagen/Argumentationen gleichbeutend sind. z.B.
"Das Wetter ändert sich oder es ändert sich nicht"  ist immer wahr, unabhängig vom Wetter.
"Wenn er der Täter war, dann war er am Tatort"     bedeutet das gleiche, wie
"Wenn er nicht am Tatort war, dann war er nicht der Täter".
Dagegen bedeutet "Wenn er am Tatort war, dann war er der Täter" etwas anderes.
Kompliziertere Fälle als diese sind oft mit unserem Alltagsverständnis nicht mehr so leicht zu erkennen.
Eine Formale Darstellung die zu den obigen Aussagen passt ist: a∨¬a⇔wahr, bzw.  a→b⇔¬b→¬a
In der Aussagenlogik werden immer nur solche Aussagen betrachtet, die entweder wahr oder der falsch sind.
Die Bedeutung der logischen Verknüpfungssymbole, genannt Junktoren, sind durch folgende Verknüpfungstafeln festgelegt

a ¬a w f f w nicht

a b a∧b a∨b a→b a↔b w w w w w w w f f w f f f w f w w f f f f f w w und oder folgt äquiv.

Jede der 4 Kombinationen von Parameterwerten ist also ein Resultatwert zugeordnet. (¬ hat nur einen parameter wert, 2 Kombinationen).
Damit können wir also den Wahrheitswert einer Formel , etwa a→(b∧c) bei vorgegebene Werten für a,b,c , etwa a=w,b=f,c=w,  berechnen, indem wir die Teilaussagen entsprechen der Tabelle verknüpfen: (f∧w)=f , und w→f=f, daher Resultat: f.
Die Zuordnung von Wahrheitswerten zu den Elementaraussagen (a,b,c) nennen wir eine Belegung. Bei n Elementaraussagen gibt es 2ⁿ mögliche Belegungen.

Aussage A heißt Tautologie	A ist bei jeder Belegung wahr.
B folgt aus A (A⇒B)	Bei jeder Belegung, für die A wahr ist, ist auch B wahr.
A und B sind äquivalent (A⇔B)	A und B sind genau bei den selben Belegungen wahr

Wir können obige Äquivalenz  a→o ⇔ ¬o→¬a   (a=Täter, o= Tatort) beweisen, in dem wir alle 4 Wertekombinationen für a und o durchrechnen und dann feststellen, das für beide Aussagen bei jeder Kombination das selbe Ergebnis herauskommt:

a	o	¬o	¬a	¬o→¬a	a→o
w	w	f	f	w	w
w	f	w	f	f	f
f	w	f	w	w	w
f	f	w	w	w	w

So fiinden wir etwa auch heraus, dass
"Wenn es regnet oder schneit, dann findet das Spiel nicht statt"      äquivalent ist zu:
"Wenn das Spiel stattfindet, dann regnet es nicht und schneit es nicht".
Dafür sind dann schon 8 Fälle zu unterscheiden.Es geht aber oft auch einfacher. Dazu sind ein paar Überlegungen nötig:
Es gibt folgende Zusammenhänge:  (gdw = "genau dann wenn")

A ⇒ B	gdw	A→B ist Tautologie
A ⇔ B	gdw	A↔B ist Tautologie

Das ist sehr paktisch, denn deshalb können wir mit der Aussagenlogik auch über Folgerungs-  und Äquivalenzbeziehungen innerhalb der Aussagenlogik sprechen.
Wenn wir in einer Tautologie jedes Vorkommen einer Variable durch eine beliebige (jedes mal die selbe) Formel ersetzen, dann ist die neue Aussage auch eine Tautologie. Ausserdem: wenn eine Aussage  A als Teilaussage enthält, und es gilt A äquivalent B, dann dürfen wir A durch B ersetzen und die neue Gesamtaussage ist äquivalent zur alten. Wir können dies also nutzen um Formeln umzuformen. Wir werden sehen , daß eine kleine Menge von bekannten Äquivalenz Formeln (die wir mit Belegungstabelle beweisen können) ausreichen, um beliebige äquivalente Aussagen ineinander umzuwandeln.
Einige bekannte Äquivalenzen sind:

¬¬a⇔a	a↔b⇔(a→b)∧(b→a)	a→b⇔¬b→¬a
a∧a⇔a	a∨a⇔a	a∧b⇔b∧a	a∧b∨a⇔a
¬(a∧b)⇔¬a∨¬b	¬(a∨b)=¬a∧¬b	a∨b⇔b∨a	a∨b∧a⇔a
a∧(b∨c)⇔(a∧b)∨(a∧c)	a∨(b∧c)⇔(a∨b)∧(a∨c)	a∧¬a⇔f	a∨¬a⇔w
a∧w⇔a;   a∧f⇔f	a∨w⇔w;   a∨f⇔a	¬w⇔f; ¬f⇔w

Für das obige Beispiel (r=regnet, s=schneit, a=findet statt):  (r∨s)→¬a  ⇔ a→¬(r∨s) ⇔ a→(¬r∧¬s); benutzt wurden 1.1,1.3 und 3.2 Zeile.Spalte der Tabelle.
So ist auch der Beweis einer Tautologie (A⇔w) oder einer Folgerungsbeziehung (A→B⇔w) möglich.

Mit der Aussagenlogik können wir jetzt also die Struktur von logischen Aussagen erfassen, und Folgerungs bzw Äquivalenzbeiehungen zwischen verschiedenen Aussagen erkennen.

Ich verwende im Folgenden die Operatoren ⇒, ⇔, um die Folgerungs/Äquivalenzbeziehungen herauszustellen. Sie könnten aber genauso durch →, ↔ ersetzt werden. Da wir oft Ketten aus Folgerungen aufbauen steht A⇔B⇔C für A⇔B und  B⇔C; analog mit ⇒,⇐, und diese Operatoren haben syntaktisch niedrigeren Vorrang als die normalen Junktoren.

Die Prädikatenlogik ist eine Erweiterung der Aussagenlogik. Mit ihr können wir auch über Objekte und Eigenschaften und Beziehungen zwischen Ihnen sprechen.
aus "Alle Vögel können fliegen"  (∀x: vo(x)→fl(x)) und "Karl ist ein Vogel" (vo(k)) folgt "Karl kann fliegen" (fl(k)).

Die Umformungsregeln für Ausdrücke mit Quantoren (∀,∃) werden später ausführlich besprochen.
Der Variablenname 'x' im obigen Beispiel ist beliebig; Die Wichtigsten Umformungen sind:
∀x:φ(x) ⇒ φ(a);   ∃x:φ(x) ⇐ φ(a);   ¬∃x:φ(x)⇔∀x:¬φ(x)  .