Logische Formeln in der Mathematik ermöglichen es Ihnen, verschiedene Bedingungen und Beziehungen zu beschreiben und zu analysieren. Manchmal ist es jedoch hilfreich, diese Formeln als disjunktive Normalform (DNF) oder konjunktive Normalform (CNF) darzustellen. Dies vereinfacht den Ausdruck und macht ihn für die Analyse verständlicher.
DNF ist ein boolescher Ausdruck, der aus Literaluntersetzungen besteht, wobei jedes Literal eine Variable oder eine Negation davon sein kann. Eine Disjunktion ist eine logische "oder" -Operation, was bedeutet, dass mindestens einer der Ausdrücke wahr sein muss. DNF ermöglicht es Ihnen, eine logische Formel als eine Sammlung von gültigen Variablenwerten darzustellen.
CNF ist wiederum ein boolescher Ausdruck, der aus Literalkonjunktionen besteht, wobei jedes Literal eine Variable oder eine Negation davon sein kann. Eine Konjunktion ist eine logische "und" -Operation, was bedeutet, dass alle Ausdrücke wahr sein müssen. Der CNF ermöglicht es Ihnen auch, eine logische Formel als eine Sammlung von gültigen Variablenwerten darzustellen.
Dieser Artikel behandelt einen einfachen Algorithmus, mit dem Sie DNF und CNF aus jeder logischen Formel abrufen können. Es werden die grundlegenden Regeln für die Umwandlung von Formeln in DNF und CNF untersucht und gezeigt, wie der Ausdruck kompakter und lesbarer wird.
Grundbegriff
- Eine Formel ist ein mathematischer Ausdruck, der aus Variablen und logischen Operationen wie Konjunktion (logisch UND), Disjunktion (logisch ODER) und Negation besteht.
- Die disjunktive Normalform (DNP) ist eine logische Formel, bei der jede Disjunktive (Kombination durch ODER) aus Literalen (Variablen oder deren Negationen) besteht und jede Variable nur einmal verwendet wird.
- Die konjunktive Normalform (CNF) ist eine logische Formel, bei der jeder Konjunktiv (eine Kombination aus durch Und) aus Literalen (Variablen oder deren Negationen) besteht und jede Variable nur einmal verwendet wird.
- Ein Literal ist eine Variable oder ihre Negation.
- Eine Konjunktion ist eine logische Operation, die durch das Symbol Und gekennzeichnet ist und die nur dann wahr ist, wenn beide Operanden wahr sind.
- Eine Disjunktion ist eine logische Operation, die durch das Symbol ODER gekennzeichnet ist und true zurückgibt, wenn mindestens einer der Operanden wahr ist.
- Negation ist eine logische Operation, die durch das Symbol NICHT bezeichnet wird und die die Wahrheit des Operanden in den entgegengesetzten ändert.
Wie bekomme ich DNF aus einer Formel
1. Teilen Sie die logische Formel in einzelne Elemente auf (boolesche Variablen, Operationen und Klammern).
2. Notieren Sie die Wahrheitswerte jedes Formelelements in die Wahrheitstabelle. Erstellen Sie dazu alle möglichen Kombinationen von booleschen Variablenwerten und definieren Sie das Ergebnis für jede Kombination.
3. Erstellen Sie eine logische Formel in disjunktiver normaler Form mithilfe der Ergebnisse der Wahrheitstabelle. Kombinieren Sie dazu die Formelelemente, die den Wert "1" annehmen, mit "ODER" (das Symbol "|"). Jedes Element der Formel muss in Klammern eingeschlossen werden.
4. Bringen Sie die DNF bei Bedarf zu einer kanonischen Form. Die kanonische Form von DNF setzt voraus, dass jede Klammer die gleiche Anzahl von Elementen hat und alle Klammern alle booleschen Variablen enthalten (möglicherweise mit Negationen).
5. Überprüfen Sie die resultierende DNF anhand der Wahrheitstabelle auf Richtigkeit.
Die Verwendung von DNF macht es einfacher, logische Formeln zu analysieren und zu bearbeiten, insbesondere im Zusammenhang mit Kombinationsschaltungen und Programmierung.
Wie bekomme ich CNF aus einer Formel
Führen Sie die folgenden Schritte aus, um die CNF aus einer Formel zu erhalten:
1. Zerlegen Sie die Formel mithilfe von logischen Operatoren (Konjunktion, Disjunktion, Negation und Implikation) in elementare logische Ausdrücke.
2. Wenden Sie de Morgans Gesetze an, um Implikationen und Negationen umzuwandeln:
- Implikation: Ersetzen Sie den Ausdruck "A → B" durch "~A ∨ B".
- Leugnung: ersetzen Sie den Ausdruck "~(A ∨ B)" durch "~A ∧ ~B" und den Ausdruck "~(A ∧ B)" durch "~A ∨ ~B".
3. Erweitern Sie die Klammern und wenden Sie die Verteilungsgesetze an, um logische Operationen zu transformieren:
- Verteilungsfähigkeit der Konjunktion relativ zur Disjunktion: Ersetzen Sie den Ausdruck "A ∧ (B ∨ C)" durch "(A ∧ B) ∨ (A ∧ C)".
- Disjunktionsverteilung relativ zur Konjunktion: Ersetzen Sie den Ausdruck "A ∨ (B ∧ C)" durch "(A ∨ B) ∧ (A ∨ C)".
4. Bringen Sie den Ausdruck in die kanonische Form von CNF:
- Die Verknüpfung von Disjunktionen sollte nur durch Variablen durchgeführt werden.
- Beseitigen Sie wiederholte Disjunktionen.
Die konsequente Anwendung dieser Schritte ermöglicht es daher, die CNF aus dieser Formel zu erhalten.
Beispiele für Konvertierungen
Betrachten wir einige Beispiele für die Umwandlung von logischen Formeln in DNF und CNF.
Beispiel 1:
Die ursprüngliche Formel lautet: P ∨ Q
| Funktion P | Funktion Q | Ursprüngliche Formel | DNF | KNF |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Beispiel 2:
Die ursprüngliche Formel lautet: (P ∧ Q) ∨ R
| Funktion P | Funktion Q | Funktion R | Ursprüngliche Formel | DNF | KNF |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
Sonderfall
In einigen Fällen kann es bei der Arbeit mit Formeln zu besonderen Situationen kommen, die besondere Aufmerksamkeit erfordern.
Ein solcher Fall ist eine Formel, in der es keine Negationen gibt. In diesem Fall werden DNF und CNF wie folgt aussehen:
- DNF: die Formel wird als Summe der Variablenwerke und ihrer Negationen dargestellt;
- CNF: Die Formel wird als Produkt der Variablensummen und ihrer Negationen dargestellt.
Außerdem müssen Sie den Fall berücksichtigen, in dem die Formel nur aus einer Variablen besteht. In diesem Fall:
- DNF wird als Summe der Werke dieser Variablen und ihrer Negation dargestellt;
- Der CNF wird als Produkt der Summe dieser Variablen und ihrer Negation dargestellt.
Es ist notwendig, sich an solche besonderen Fälle zu erinnern und sie zu berücksichtigen, wenn Sie DNF und CNF aus der Formel erhalten.
Algorithmus zur Erzeugung von DNF und CNF
Um DNF (disjunktive Normalform) und CNF (konjunktive Normalform) aus der Formel zu erhalten, müssen die folgenden Schritte unternommen werden:
1. Eine Formel in die normale Form bringen:
- Beseitigung der doppelten Negation.
- Anwendung von de Morgans Gesetzen.
- Anwendung der Assoziativität und Kommutativität von logischen Operationen.
- Verwendung des Verteilungsgesetzes.
2. Aufteilen einer Formel in elementare Ausdrücke:
- Die Formel wird in Unterformeln unterteilt, wobei jede Unterformel nur eine einfache logische Operation enthält.
3. Aufbau von DNF:
- Für jede Unterformel wird eine Wahrheitstabelle erstellt.
- In der Wahrheitstabelle werden Zeilen hervorgehoben, in denen die Unterformel wahr ist.
- Aus diesen Zeilen wird eine Konjunktion gebildet, die DNF sein wird.
4. Aufbau von CNF:
- Für jede Unterformel wird eine Wahrheitstabelle erstellt.
- In der Wahrheitstabelle werden Zeilen hervorgehoben, in denen die Unterformel falsch ist.
- Aus diesen Zeilen wird eine Disjunktion gebildet, die CNF sein wird.
Auf diese Weise erhalten wir nach Abschluss aller beschriebenen Schritte DNF und CNF für die ursprüngliche Formel.
Anwendung von DNF und CNF
Die disjunktive Normalform (DNF) und die konjunktive Normalform (CNF) werden häufig in Logik und Mathematik verwendet, um boolesche Funktionen zu analysieren und zu vereinfachen.
Die Verwendung von DNF ermöglicht es, das Problem der Suche nach Optionen für die Erfüllung einer Bedingung zu lösen, indem die Formel in Disjunktionen unterteilt wird. Jede Disjunktion definiert einen separaten Satz von Variablenwerten, bei denen die Formel wahr ist. Dies kann beispielsweise beim Entwerfen digitaler Schaltkreise oder beim Analysieren eines logischen Ausdrucks nützlich sein.
Die CNF wird dagegen verwendet, um Widersprüche oder Fehler zu identifizieren. Die Formel im CNF hat die Form, wenn alle Variablen durch Konjunktionen kombiniert werden, dh jede Variable wird in jedem Wertesatz im CNF dargestellt. Wenn die CNF bei irgendwelchen Variablenwerten wahr ist, bedeutet dies, dass es einen Widerspruch oder einen Fehler in der Formel gibt. CNF wird verwendet, um die Korrektheit eines logischen Ausdrucks zu überprüfen oder Fehler im Code zu erkennen.
Die Verwendung von DNF und CNF vereinfacht die Analyse und Berücksichtigung verschiedener Kombinationen von Variablenwerten. Dadurch können Sie Funktionen und Systeme optimieren, die Zuverlässigkeit und Effizienz von Programmen oder Geräten erhöhen. Es wird empfohlen, bei der Entwicklung von Software oder beim Entwerfen komplexer Systeme DNF und CNF zu verwenden, um logische Ausdrücke zu analysieren und zu optimieren.
