Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
| home-harmening:mathematik:aussagenlogische_formeln [2025/10/21 09:00] – WoUTwS7hfctqqo,Wqg7k(b4- 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| | |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 ===== | ===== - Syntax aussagenlogischer Formeln ===== | ||
| - Jeder lateinische Großbuchstabe A,...,Z (auch indiziert $ A_{i} $) ist eine aussagenlogische Formel.\\ | - Jeder lateinische Großbuchstabe A,...,Z (auch indiziert $ A_{i} $) ist eine aussagenlogische Formel.\\ | ||
| Zeile 140: | Zeile 143: | ||
| |**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 $ | | |**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 $ | | |**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 $ | | ||
| - | Bongopuschel | + | |**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 $ | | |**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 $ | | |**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 $ | | |**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 $ | | |**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 $ |-/ | ||
| + | |**Disjunktion**| $ A \lor 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))) $ | | ||
| + | |||