Aussagenlogische Formeln

(F1) Die Behauptung muss inhaltlich verständlich sein. Eventuell muss dafür auf notwendige
Begriffsdefinitionen verwiesen werden.

(F2) Es muss möglich sein, Bedingungen anzugeben, unter denen sich der Wahrheitsgehalt der
Behauptung (zumindest hypothetisch) objektiv und eindeutig feststellen lässt

Eine durch (eine natürliche oder eine künstliche) Sprache ausgedrückte Behauptung, die die Bedingungen (F1) und (F2) erfüllt, bezeichnen wir als Aussageform. Enthält eine Aussageform bereits sämtliche Kontextinformation im Sinne von (F2), so dass ihr Wahrheitsgehalt in einem übergeordnet festgelegten Grundkontext ohne weitere Angabe von Informationen – wenigstens hypothetisch – objektiv und eindeutig feststellbar ist, so nennen wir diese eine Aussage.

Durch den Grundkontext „Mathematik“ wissen wir, was Variablen und Zahlen sind, ferner kennen wir die Bedeutung des Zeichens „>“. Nachfolgend ist eine Aussageform in diesem
Grundkontext gegeben:

Grundkontext: Mathematik
Behauptung: Es ist x > 3.
Hier kann der Wahrheitsgehalt erst dann zweifelsfrei evaluiert werden, wenn bekannt ist, welchen Wert die Variable x hat. Erst dann entsteht also eine (wahre oder falsche) Aussage:

Grundkontext: Mathematik
Kontext: x habe den Wert 2.
Behauptung: Es ist x > 3

Nochmal einfacher

Aussage
Eine Aussage ist ein Satz, der eindeutig wahr (w) oder falsch (f) ist. Sie enthält keine Variablen.

Beispiele:
„5 ist eine ungerade Zahl.“ → wahr
„3 = 5.“ → falsch
„6 < 11.“ → wahr

Diese Sätze haben einen festen Wahrheitswert und heißen daher Aussagen.

Aussageform
Eine Aussageform ist ein Satz, der mindestens eine Variable (Platzhalter) enthält. Sein Wahrheitswert lässt sich erst nach dem Einsetzen eines konkreten Wertes bestimmen.

Beispiele:
A (x):x+1=7
Für x=6: wahr
Für x=4: falsch

B (x,y):x<y
Für (x,y)=(3,5): wahr
Für (x,y)=(7,2): falsch

Eine Aussageform hat noch keinen Wahrheitswert, sondern wird zur Aussage, wenn man:
Variablen durch konkrete Werte ersetzt (z.B. x=6), oder
Variablen mit Quantoren bindet, etwa:
Allquantor („für alle“): ∀x:x+1=7
Existenzquantor („es gibt“): ∃x:x+1=7

💡 Merkregel

Aussage: enthält keine Variablen → hat festen Wahrheitswert
Aussageform: enthält Variable(n) → Wahrheitswert noch offen

Gegeben ist der Satz

Wenn heute Montag ist, dann ist Morgen Mittwoch

Die Negation zu diesem Satz zu bilden ist nicht so intuitiv und sollte daher durch zu Hilfenahme von Formeln gebildet werden.

• Wenn heute Montag ist, dann ist Morgen Mittwoch $A \rightarrow B$
  
• Die Transformation der Disjunktion ist $A \rightarrow B$ ⇒ $\neg A \lor B$
  
• Jetzt die Negation der Formel $\neg A \lor B$ ⇒ $A \land \neg B$
  
• Die negierte Formel in einen Satz überführen $A \land \neg B$ ⇒ Heute ist Montag, und Morgen ist nicht Mittwoch.
  

Die Negation lautet

Heute ist Montag, und Morgen ist nicht Mittwoch.

In der Logik sind Quantoren besondere Operatoren, die angeben, für welche Objekte oder Elemente einer Menge eine Aussage gelten soll.

Der Allquantor steht für „für alle“ oder „jedes“.
Er gibt an, dass eine Aussage für alle Elemente einer betrachteten Menge gilt.
Symbol: ∀ (umgedrehtes A)

Beispiel:
„Für alle natürlichen Zahlen x gilt: x + 0 = x“
Formal:
$∀x∈N:x+0=x$

Der Existenzquantor steht für „es gibt mindestens ein“.
Er drückt aus, dass es mindestens ein Element gibt, für das die Aussage wahr ist.
Symbol: ∃ (gespiegeltes E)

Beispiel:
„Es gibt eine natürliche Zahl x, sodass x² = 4“
Formal:
$∃x∈N:x^{2}=4$

In der Aussagenlogik sind Junktionen (richtiger: Junktoren) logische Verknüpfungszeichen, mit denen man einzelne Aussagen zu komplexeren Aussagen zusammensetzt.

Folgende Junktionen existieren

Hier ist zu sagen, dass eine

• Subjunktion $ A \rightarrow B $ in eine Disjunktion gewandelt werden kann
  
  $ A \rightarrow B \equiv \neg A \lor B $
  
• Bijunktion in zwei Subjunktionen bzw, zwei Disjunktionen mit einer Konjunktion gewandelt werden kann
  
  $ A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A) \equiv (\neg A \lor B) \land (\neg B \lor A) $
  

1. Jeder lateinische Großbuchstabe A,…,Z (auch indiziert $ A_{i} $) ist eine aussagenlogische Formel.
   
2. Es sind $ \top $ für Tautalogie und $ \bot $ für Kontradiktion aussagenlogische Formeln.
3. Ist $ \varphi $ eine aussagenlogische Formel, so gilt dies auch für $ (\varphi) $ und $ (\neg \varphi ) $.
4. Sind $ \varphi $ und $ \epsilon $ aussagenlogische Formeln, so gilt dies auch für $ ( \varphi \land \epsilon ) $,$ ( \varphi \lor \epsilon ) $,$ ( \varphi \oplus \epsilon ) $
   $ ( \varphi \rightarrow \epsilon ) $,$ ( \varphi \leftrightarrow \epsilon ) $

Um komplexe aussagenlogische Formeln zu vestehen und zu bewerten kann ein Syntaxbaum als Werkzeug erstellt werden.
Die aussagenlogische Formel wird mit Hilfe des Syntaxbaum asseinander gefächert bis zu den Einzelnen Operatoren (A,B,…,Z).

Abhängig davon, welche Werte von einer Booleschen Funktion tatsächlich angenommen werden,
unterscheiden wir drei wesentliche Szenarien:

• Erfüllbarkeit: Eine Boolesche Funktion heißt erfüllbar, wenn sie für mindestens eine Eingabe den Wert 1 annimmt.
• Widersprüchlichkeit: Eine Boolesche Funktion heißt widersprüchlich, wenn sie nicht erfüllbar ist. Damit nimmt sie für alle Eingaben den Wert 0 an. Man spricht dann von einer Kontradiktion.
• Allgemeingültigkeit: Eine Boolesche Funktion heißt allgemeingültig, wenn sie für alle Eingaben den Wert 1 annimmt. Man spricht dann von einer Tautologie.

• Logisch Gleichwertig: Wenn zwei unterschiedliche Formeln zum selben Ergebnis führen. Bzw. wenn diese die gleiche Wahrheitstabelle aufweisen nennt man diese Formeln logisch Gleichwertig.

Um bei langen Formen eine kleine Hilfe zu haben, gibt es die Möglichkeit die Gesetze aus der Addition und der Multiplikation zu verwenden. Dabei wird

• Und $ \land \equiv * $ Multiplikation
• Oder $ \lor \equiv + $ Addition

gesetzt.

Konjunktive Normalform (KNF): Diese Form liegt vor, wenn eine gegebene aussagenlogische Formel eine Konjunktion von Disjunktionen von Literalen ist und kein Großbuchstabe
je Disjunktion in mehr als einem Literal vorkommt.

Einfach:
Eine Formel ist in KNF, wenn sie eine UND-Verknüpfung von mehreren ODER-Verknüpfungen von einfachen Aussagen (genannt Literale) ist.
Wichtig dabei:

• Literale sind Aussagen oder deren Verneinungen.
• In jeder ODER-Verknüpfung darf kein Literal doppelt vorkommen.

Die kanonische KNF zeichnet sich dadurch aus, das der Letzte Punkt nicht erfüllt ist. Es können auch Literale und komplette Funktionen doppelt vorkommen.
Diese Form ist eine absolute Nachbildung der Wahrheitstabelle und nicht vereinfacht.

1. Wahrheitstabelle aufstellen.
2. Alle Formeln Notieren bei denen das Endergebnis Wahr ist. Z.B. $ ( A \land B \land C) $
3. Diese Formeln miteinander ODER verknüpfen. Z.B $ ( A \land B \land C) \lor ( \neg A \land \neg B \land C) $
4. Das Ergebnis ist die kanonische Konjunktive Normalform.
5. Kanonische KNF vereinfachen.
6. Das Ergebnis ist die KNF.

Disjunktive Normalform (DNF): Diese Form liegt vor, wenn eine gegebene aussagenlogische Formel eine Disjunktion von Konjunktionen von Literalen ist und kein Großbuchstabe
je Konjunktion in mehr als einem Literal vorkommt.

Einfach:
Eine Formel steht in DNF, wenn sie eine ODER-Verknüpfung von mehreren UND-Verknüpfungen von einfachen Aussagen (den sogenannten Literalen) ist.

Dabei gilt:

• Literale sind Aussagenvariablen oder ihre Verneinungen.
  
• Jede UND-Verknüpfung fasst einige Literale zusammen, z. B. $ A \land \neg B $.
  
• Die einzelnen UND-Verknüpfungen sind dann durch ODER verbunden, z. B. $ (A \land B) \lor ( \neg A \land C \land D) $ .
  

Die kanonische DNF zeichnet sich dadurch aus, das der Letzte Punkt nicht erfüllt ist. Es können auch Literale und komplette Funktionen doppelt vorkommen.
Diese Form ist eine absolute Nachbildung der Wahrheitstabelle und nicht vereinfacht.

1. Wahrheitstabelle aufstellen.
2. Alle Formeln Notieren bei denen das Endergebnis Falsch ist. $ ( A \land B \land C) $
3. Diese Formeln miteinander ODER verknüpfen. $ ( A \land B \land C) \lor ( \neg A \land \neg B \land C) $
4. Jetzt die gesamte Formel negieren!
   So das innerhalb der Klammer ein ODER steht und diese einzelnen Formeln miteinander UND Verknüpfen! $ ( \neg A \lor \neg B \lor \neg C) \land ( A \lor B \lor \neg C) $
5. Das Ergebnis ist die kanonische Disjunktive Normalform.
6. Kanonische DNF vereinfachen.
7. Das Ergebnis ist die DNF.

NAND gilt als universeller Junktor. Mit NAND lassen sich auch alle anderen Junktionen darstellen.