Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- home-harmening:mathematik:aussagenlogische_formeln [2025/10/21 05:55] – [1.1 Negation von Aussagen] charmening
+++ home-harmening:mathematik:aussagenlogische_formeln [2025/10/22 06:51] (aktuell) – [7. Junktionen als NAND] charmening
@@ Zeile 56: / Zeile 56: @@
   Aussageform: enthält Variable(n) → Wahrheitswert noch offen
 \\
-==== - Negation von Aussagen ====
+=== - Negation von Aussagen ===
 Gegeben ist der Satz
   Wenn heute Montag ist, dann ist Morgen Mittwoch
@@ Zeile 90: / Zeile 90: @@
 „Es gibt eine natürliche Zahl x, sodass x² = 4“\\
 **Formal:**\\
-$∃x∈N:x^{2}=4$
+$∃x∈N:x^{2}=4$\\
+\\
+===== - Junktionen =====
+In der Aussagenlogik sind Junktionen (richtiger: Junktoren) logische Verknüpfungszeichen, mit denen man einzelne Aussagen zu komplexeren Aussagen zusammensetzt. \\
+\\
+Folgende Junktionen existieren
+|**Symbol**|**Name**|**verbale Bedeutung**|**Beispiel**|**Beschreibung**|
+|$ \neg $|Negation|nicht|$ \neg A $, "nicht A"| Verneint den Wahrheitswert einer Aussage.\\Wenn A wahr ist, ist $\neg A$ falsch - und umgekehrt.|
+|$ \land $|Konjunktion|und|$ A \land B $, "A und B"|Wahr nur wenn beide Aussagen wahr sind.|
+|$ \lor $|Disjunktion|oder (einschließend)|$ A \lor B $, "A oder B\\ oder Beide"|Wahr, wenn mindestens eine der Aussagen wahr ist.|
+|$ \oplus $|Exklusives Oder\\(XOR)|entweder - oder|$ A \oplus B $|Wahr, wenn genau eine Aussage wahr ist.|
+|$ \rightarrow $|Subjunktion/Implikation|Wenn - dann|$ A \rightarrow B $, "Wenn Am dann B"|Falsch nur, wenn A wahr und B falsch ist.\\Lässt sich gut durch den Satz:\\Ich verspreche wenn A, dann B. Herleiten.\\Versprechen gehalten oder gebrochen.|
+|$ \leftrightarrow $|Bijunktion/Äquivalenz|genau dann, wenn|$ A \leftrightarrow B $, A genau dann\\, wenn B|Wahr, wenn beide Aussagen denselben Wahrheitswert haben.|
+\\
+==== - Wahrheitstabelle der Junktionen ====
+|**A**|**B**|**Konjunktion $ A \land B $**|**Disjunktion $ A \lor B $**|**XOR $ A \oplus B $**|**Subjunktion $ A \rightarrow B $**|**Bijunktion $ A \leftrightarrow B $**|
+|0|0|0|0|0|1|1|
+|0|1|0|1|1|1|0|
+|1|0|0|1|1|0|0|
+|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.\\
+  - Es sind $ \top $ für Tautalogie und $ \bot $ für Kontradiktion aussagenlogische Formeln.
+  - Ist $ \varphi $ eine aussagenlogische Formel, so gilt dies auch für $ (\varphi) $ und $ (\neg \varphi ) $.
+  - 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 ) $
+\\
+===== - Syntaxbäume =====
+{{ :home-harmening:mathematik:syntaxbaumaussagenlogischeformel.png?200 |}}
+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).\\
+\\
+===== - 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))) $ |