Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- home-harmening:mathematik:aussagenlogische_formeln [2025/10/21 08:21] – [3. Syntax aussagenlogischer Formeln] charmening
+++ home-harmening:mathematik:aussagenlogische_formeln [2025/10/22 06:51] (aktuell) – [7. Junktionen als NAND] charmening
@@ Zeile 111: / Zeile 111: @@
 |1|1|1|1|0|1|1|
 \\
+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) $ \\
 ===== - Syntax aussagenlogischer Formeln =====
   - Jeder lateinische Großbuchstabe A,...,Z (auch indiziert $ A_{i} $) ist eine aussagenlogische Formel.\\
@@ Zeile 122: / Zeile 125: @@
 Die aussagenlogische Formel wird mit Hilfe des Syntaxbaum asseinander gefächert bis zu den Einzelnen Operatoren (A,B,...,Z).\\
 \\
+===== - Begriffe =====
+ 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**.
+\\
+===== - Umformen von Formeln =====
+\\
+|**Name**|**Beschreibung**|**Beispiel**|
+|**Kommunikativgesetz**|Die Reihenfolge der Aussagen bei **Konjunktion** und **Disjunktion** ist egal|$ A \land B \equiv B \land A $ \\ $ A \lor B \equiv B \lor A $|
+|**Assoziativgesetz**|Die Gruppierung von Aussagen bei Konjunktion und Disjunktion kann beliebig verändert werden.| $ (A \land B) \land C \equiv A \land ( B \land C ) $ \\ $ (A \lor B) \lor C \equiv A \lor ( B \lor C ) $ |
+|**Distributivgesetz**|Konjunktion kann über Disjunktion verteilt werden und umgekehrt.| $ 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 ) $ |
+|**Absorptionsgesetz**|Eine Aussage absorbiert eine durch Konjunktion oder Disjunktion verbundene zweite Aussage.| $ A \lor ( A \land B) \equiv A $ \\ $ A \land ( A \lor B) \equiv A $ |
+|**Neutralitätsgesetz**|Eine Aussage und Wahr ist immer gleich der Aussage. \\ Eine Aussage oder Falsch ist immer gleich der Aussage.| $ A \land \top \equiv A $ \\ $ A \lor \bot \equiv A $ |
+|**Extremalgesetz**|Eine Aussage und Falsch ist immer Falsch. \\ Eine Aussage oder Wahr ist immer Wahr.| $ A \land \bot \equiv \bot $ \\ $ A \lor \top \equiv \top $ |
+|**Komplementärgesetz**|Eine Aussage oder ihre Negation ist immer wahr. \\ Eine Aussage und ihre Negation ist immer falsch.|$ A \lor \neg A \equiv \top $ \\ $ A \land \neg A \equiv \bot $ |
+|**Involutionsgesetz**|Eine Verneinung der Verneinung ist die Aussage selbst.| $ \neg ( \neg A ) \equiv A $ |
+|**De Morganische Gesetze**|Negationen von Konjunktion und Disjunktion tauschen.| $ \neg ( A \land B ) \equiv \neg A \lor \neg B $ \\ $ \neg ( A \lor B ) \equiv \neg A \land \neg B $ |
+|**Idempotenzgesetze**|Wiederholte Anwendung derselben Operation ändert die Aussage nicht.| $ A \land A \equiv A $ \\ $ A \lor A \equiv A $ |
+\\
+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.
+\\
+\\
+===== Normalformen =====
+==== KNF (UND Verbunden) ====
+**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.
+\\
+=== Kanonische Konjunktive Normalform ===
+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.\\
+\\
+=== KNF erstellen ===
+  - Wahrheitstabelle aufstellen.
+  - Alle Formeln Notieren bei denen das Endergebnis Wahr ist. Z.B. $ ( A \land B \land C) $
+  - Diese Formeln miteinander ODER verknüpfen. Z.B $ ( A \land B \land C) \lor ( \neg A \land \neg B \land C) $
+  - Das Ergebnis ist die **kanonische Konjunktive Normalform**.
+  - Kanonische KNF vereinfachen.
+  - Das Ergebnis ist die KNF.
+\\
+==== DNF (ODER Verbunden)====
+**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) $ . \\
+\\
+=== Kanonische Disjunktive Normalform ===
+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.\\
+\\
+=== DNF erstellen ===
+  - Wahrheitstabelle aufstellen.
+  - Alle Formeln Notieren bei denen das Endergebnis Falsch ist. $ ( A \land B \land C) $
+  - Diese Formeln miteinander ODER verknüpfen. $ ( A \land B \land C) \lor ( \neg A \land \neg B \land C) $
+  - 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) $
+  - Das Ergebnis ist die **kanonische Disjunktive Normalform**.
+  - Kanonische DNF vereinfachen.
+  - Das Ergebnis ist die DNF.
+\\
+===== - Junktionen als NAND =====
+NAND gilt als universeller Junktor. Mit NAND lassen sich auch alle anderen Junktionen darstellen.\\
+\\
+|**Bezeichnung**|**Formel**|**Vereinfachung 1**|**Vereinfachung 2**|**Vereinfachung 3**|**NAND mit Negation**|**Formel als NAND**|
+|**Konjunktion**| $ A \land B $ |-/-|-/-|-/-|-/-| $ (A \barwedge B) \barwedge (A \barwedge B) $ |
+|**Disjunktion**| $ A \lor B $ |-/-|-/-|-/-| $ \neg A \barwedge \neg B $ | $ (A \barwedge A) \barwedge (B \barwedge B) $ |
+|**Subjunktion**| $ A \rightarrow B $ | $ \neg A \lor B $ |-/-|-/-| $ A \barwedge \neg B $ | $ A \barwedge (B \barwedge B) $ |
+|**Bijunktion**| $ A \leftrightarrow B $ | $ (A \rightarrow B) \land (B \rightarrow A) $ | $ (\neg A \lor B) \land (\neg B \lor A) $ | $ ( A \barwedge \neg B ) \land ( B \barwedge \neg A) $ | $ (( A \barwedge \neg B ) \barwedge ( B \barwedge \neg A )) \barwedge (( A \barwedge \neg B ) \barwedge ( B \barwedge \neg A )) $ | $ (( A \barwedge (B \barwedge B) ) \barwedge ( B \barwedge (A \barwedge A) )) \barwedge (( A \barwedge (B \barwedge B) ) \barwedge ( B \barwedge (A \barwedge A))) $ |