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:05] – [6. Umformen von 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| | |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 150: | Zeile 153: | ||
| * Oder $ \lor \equiv + $ Addition | * Oder $ \lor \equiv + $ Addition | ||
| gesetzt. | 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))) $ | | ||