aussagenlogik

Einführung in die Aussagenlogik

Was du lernen wirst

Du wirst lernen, was die Aussagenlogik ist, was eine Aussage ist, wie man die Aussage von der Aussageform unterscheidet, welche Symbole dir zur Verfügung stehen, welche Terminologie wichtig ist und wie man Wahrheitstabellen erstellt.

Was du mit damit anfangen kannst

Mit Hilfe der Aussagenlogik, kannst du – sobald du die Regeln kennst – die Gültigkeit von verknüpften Aussagen bestimmen, ohne genau zu wissen worum es in der Aussage geht. Die Aussagenlogik ist ein wichtiger Teil der Informatik. Dank ihrer Hilfe, können zum Beispiel Schaltnetze entworfen werden.


Was ist die Aussagenlogik?


Die Aussagenlogik ist neben der Prädikatenlogik eine Quälerei, mit der sich ein Informatik-Student früher oder später rumschlagen muss. Sie besteht aus kleinen sprachlichen Einheiten, die wahr oder falsch sein können – sogenannte Elementaraussagen – und deren Verknüpfung durch logische Operatoren – sogenannte Junktoren, zu Aussagen, welchen ebenfalls ein Wahrheitswert zugeordnet werden kann.

Was sind Aussagen?

In der Aussagenlogik dreht sich alles um Aussagen. Wir möchten sagen können, ob eine Aussage wahr oder falsch ist. Aber was genau ist eine Aussage und was ist keine?

Eine Aussage ist nur dann eine, wenn wir sie als wahr oder falsch interpretieren können.

Dabei spielt es zunächst keine Rolle, ob die Aussage nun wahr oder falsch ist:
“Budapest ist die Hauptstadt von Deutschland” ist eine falsche Aussage.
“Berlin ist die Hauptstadt von Deutschland” ist eine wahre Aussage.
“Berlin wird immer die Hauptstadt von Deutschland sein” ist keine Aussage, denn wir können nicht bestimmen, ob es wahr oder falsch ist.

AussageKeine Aussage
Stroh wird als Tierfutter verwendetWarum liegt da Stroh?
Ein Kilogramm Muskeln sind schwerer, als ein halber Kilogramm Fett.Muskeln sind schwerer als Fett.
Eine Ente kann weiter fliegen, als ein Nashorn.Was ist der Unterschied zwischen einer Ente?

Was ist eine Aussageform?

Ein Fachbegriff, welcher in der Aussagenlogik wichtig zu unterscheiden ist, ist die Aussageform.

Eine Aussageform ist, ein Ausdruck in der eine Aussagevariable vorkommt (z.b A(x) ). Sie wird zu einer Aussage, sobald wir diese Variable mit einem Begriff belegen.

Eine solche Aussageform könnte lauten
H(x) = x ist die Hauptstadt von Deutschland.
x kann irgendeine Stadt darstellen.

Da wir nicht wissen um welche Stadt es sich handelt können wir auch nicht sagen, ob es wahr oder falsch ist. Somit handelt es sich nicht um eine Aussage. Eine Aussage wird es erst, wenn wir etwas für x einsetzen und die Gültigkeit bestimmen können:

AussageformAussage
x ist die Hauptstadt von Deutschland.London ist die Hauptstadt von Deutschland.

Welche Symbole stehen uns zur Verfügung?

Genau genommen kommt es auf die Logik an. So Verwenden wir in der Aussagenlogik nicht die gleichen Symbole wie in der Prädikatenlogik. In der Aussagenlogik verwendet man Aussagenvariablen wie p_1, p_2, p_3, ... (statt p_n sieht man häufig auch A,B,C...) oder Junktoren wie \rightarrow, \leftarrow, \leftrightarrow, \neg, \vee, \wedge und Hilfszeichen wie die Klammern ( ).Falls dir diese Zeichen nichts sagen, dann keine Sorge ich erkläre sie im folgenden.
In der Prädikatenlogik wirst du schrecklichen Symbolen wie dem Allquantor (\forall) oder Existenzquantor(\exists) begegnen. Aber keine Sorge. Tatsächlich sind diese Symbole ganz leicht zu verstehen. An dieser Stelle musst du auch nicht wissen was sie bedeuten.

Was zum Teufel sind Junktoren?

Die Junktoren sind sogenannte logische Verknüpfungen. Man nennt sie auch logische Operatoren. Operatoren in der Hinsicht, das wir eine Verknüpfung haben. Wenn ich 2+3 rechne, dann habe ich die Addition als Operator und 2, bzw. 3 als Operanden. Die jeweilige Vorschrift (Addition, Subtraktion usw.) gibt vor was mit unseren Operanden passiert. Aus 2+3 wird 5. So ist das auch mit den Logischen Operationen/Junktoren.

JunktorBeschreibung
P \wedge QDie Konjunktion, bzw das logische Und.
Sowohl P und Q.
Die logische Formel wird dann wahr, wenn P und Q beide wahr sind.
P \vee QDisjunktion, bzw das logische Oder.
Die logische Formel wird dann wahr, wenn P oder Q wahr ist(oder beide).
\neg  PDie Negation. Was wahr ist wird falsch und was falsch ist wird wahr.
P \rightarrow QDie Implikation, bzw. wenn dann.
wenn P , dann Q.
Wenn P wahr ist, dann muss Q auch wahr sein.
P \leftrightarrow QÄquivalenz, bzw genau dann wenn.
Q genau dann, wenn P
Man kann es auch als “Beide nicht, oder beide” lesen.
Das heißt wenn beide falsch, oder beide wahr sind, ist deine aussagenlogische Formel wahr.

Wenn wir Aussagenveriablen(A,B, C…) mit Junktoren verknüpfen spricht man von Aussagenverknüpfungen bzw. verknüpften Aussagen.
Welche praktische Bedeutung die Junktoren noch haben, erkläre ich in einem anderen Beitrag.

Herr der Elementaraussagen – Was sind Elementaraussagen?

Man unterscheidet generell zwischen Elementaraussagen und verknüpften Aussagen(Elementaraussagen werden auch atomare Aussagen genannt). Wie bereits der Name ausdrückt, besteht eine Elementaraussage ohne logischen Operatoren, bzw Junktoren. Also ohne: nicht, und, oder, wenn…dann, genau dann wenn.

ElementaraussageVerknüpfte Aussage
Da liegt StrohDa liegt kein Stroh
2 ist ein Teiler von 82 ist Teiler von 8 und 2 ist Teiler von 12

Wahrheitstabellen, Modell und Interpretationen

Eine logische Formel(z.b (A \vee B) kann wahr oder falsch sein. Eine Interpretation der Formel ist die Konkrete Belegung der Aussagenvariablen (A, B) mit Wahrheitswerten(0 für falsch, 1 für wahr). Die Formel A \vee B hat insgesamt 4 Mögliche Interpretationen.

ABA \vee B (A oder B)
000
011
101
111
Wahrheitstabelle für die Disjunktion

An dieser Wahrheitstabelle kannst du auch die Vorschrift der Disjunktion erkennen:
Die logische Formel wird dann wahr, wenn entweder P oder Q wahr ist(oder beide).

Dargestellt werden alle möglichen Interpretationen einer logischen Formel mit Hilfe einer Wahrheitstabelle.
Wenn eine Interpretation der Formel wahr ist, nennt man sie Modell der Formel.

Sind alle Interpretationen wahr, nennt man die Formel allgemeingültig bzw. gültig oder auch Tautologie. Ist sie immer falsch nennt man sie unerfüllbar, oder auch Kontradiktion. Ist sie mindestens einmal wahr dann nennt man sie erfüllbar.

Wiki

Etwas, was du dir merken solltest ist, dass die Anzahl der Interpretationen sich mit jeder zusätzlichen Aussagenvariable verdoppelt. Das heißt du kannst die Anzahl der möglichen Interpretationen einer verknüpften Aussage ausrechnen, indem du {2}^n rechnest. Dabei steht n für die Anzahl der Aussagevariablen in deiner verknüpften Aussage.

A
0
1
nur 2 Interpretationen möglich, da es nur eine Aussagevariable gibt

AB
00
01
10
11
4 Interpretationen bei 2 Aussagevariablen

ABC
000
001
010
011
100
101
110
111
8 Interpretationen bei 3 Aussagevariablen

Wenn du eine Wahrheitstabelle aufstellst, dann beginne am besten immer mit den Nullen. Wie du in den Tabellen oben siehst, wandert die 1 immer weiter nach links:

000
001
010
011
100
101
110
111

Das solltest du üben, falls du in deiner Klausur eine Wahrheitstabelle aufstellen musst. Hier können sich hin und wieder Fehler einschleichen, wenn man nicht ganz aufmerksam ist.

Klausurtipp

Zähle einmal die Anzahl deiner Interpretationen durch, bevor du deine Wahrheitstabelle ausfüllst. Sind es z.b 7 kann es sein, dass du dich irgendwo vertan hast.

Bindungspriorität

So wie du es aus der Arithmetik kennst, gibt es auch bei der Logik eine sogenannte Operatorenreihenfolge, bzw Bindungspriorität.
Diese wird neben den logischen Operatoren auch über Klammern bestimmt.

Das \neg bindet stärker als \vee und \wedge
\wedge und \vee binden stärker als \rightarrow und \leftrightarrow
Geklammerte Verknüpfungen haben Vorrang.

Bestimmen wir diese aussagenlogische Formel: (A \wedge B) \rightarrow ( (\neg C ) \vee A)
Erinnerung: Äquivalenz ist dann wahr, wenn beide wahr, oder beide falsch sind.

ABC(\neg C )((\neg C ) \vee A)(A \wedge B)(A \wedge B) \leftrightarrow ( (\neg C ) \vee A)
0001100
0010001
0101100
0110001
1001100
1010100
1101111
1110111
Interpretationen einer aussagenlogischen Formel

Wie du siehst, kannst du dir die bestimmung der Interpretationen einfacher machen, indem du die Aussagenlogische Formel in kleinere Stücke zerlegst.

Zusammenfassung

Eine Aussage kann als wahr oder falsch interpretiert werden. Eine Aussagenform enthält eine Aussagevariable und kann nicht auf ihre Gültigkeit bestimmt werden. Eine Aussageform wird erst zu einer Aussage wenn wir für die Aussagevariable etwas einsetzen.

In der Aussagenlogik haben wir verschiedene Symbole zur Verfügung:

Aussagevariablen: p_1, p_2, p_3, ...
Die Junktoren: \rightarrow, \leftarrow, \leftrightarrow, \neg, \vee, \wedge
Klammern: ) (

Elementaraussagen, sind Aussagen, welche keine logischen Operatoren enthalten:
“2 ist gerade”.

Junktoren
sind logische Operatoren mit denen wir Elementaraussagen verknüpfen können:
“3 ist nicht gerade”.
Abhängig von der Vorschrift des jeweiligen Junktor, können wir die Wahrheitswerte bestimmen, wenn wir zwei Elementaraussagen mit ihnen verknüpfen. Dabei ist eine Wahrheitstabelle hilfreich.

Die Vorschrift eines Junktor gibt an, welche Wahrheitswerte du bei verknüpften Aussagen, in Abhängigkeit von der Belegung der Elementaraussagen, erhältst.

Eine Interpretation einer aussagenlogischen Formel, ist die konkrete Belegung der Aussagenvariablen mit Wahrheitswerten. Die aussagenlogische Formel A \vee B hat insgesamt 4 mögliche Interpretationen.

Das Modell der Formel besteht aus den Interpretationen, die wahr sind.

Allgemeingültig/Gültig/Tautologie: Alle Interpretationen sind wahr.
Unerfüllbar/Kontradiktion: Alle Interpretationen sind falsch.
Erfüllbar: Mindestens eine Interpretation ist wahr.

Das \neg bindet stärker als \vee und \wedge
\wedge und \vee binden stärker als \rightarrow und \leftrightarrow
Geklammerte Verknüpfungen haben Vorrang.

Neben der Aussagenlogik ist noch die Prädikatenlogik wichtig. Dabei handelt es sich um eine Art Erweiterung der Aussagenlogik. Diese lernst du in der Einführung zur Prädikatenlogik kennen.

Hat dir der Inhalt gefallen?

Falls du mehr zu Themen der Informatik lesen willst, kannst du die Suche dafür verwenden:


Du bist der Meinung, das war der Beste Beitrag zum Thema Informatik den du jemals gelesen hast? Dann ist die einzig logische Schlussfolgerung, diesen Beitrag mit deinen Kommilitonen zu teilen. Oder auch nicht mach was du willst, ich bin nicht dein Dad.

Kommentar verfassen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert