Die konjunktive Normalform einer logischen Funktion heißt. Konjunktive Darstellungsformen logischer Funktionen

Beispiel. Finden Sie CNF-Formeln

~ ~

Die perfekte disjunktive Normalform von SDNF kann mit dem folgenden Algorithmus konstruiert werden:

1. = 1. DNF-Algorithmus

2. = 2. DNF-Algorithmus

3. = 3. DNF-Algorithmus

4. = 4. DNF-Algorithmus

5. Lassen Sie identisch falsche Begriffe, also Begriffe der Form, weg

6. Ergänzen Sie die restlichen Terme mit den fehlenden Variablen

7. Wiederholen Sie Punkt 4.

Beispiel. Finden Sie SDF-Formeln.

Das folgende Schema kann zum Aufbau des SKNF verwendet werden:

Beispiel. Finden Sie SDF-Formeln.

Es ist bekannt (Sätze 2.11, 2.12), dass SDNF und SKNF durch die Formel eindeutig definiert sind und daher gemäß der Wahrheitstabelle der Formel erstellt werden können.

Das Schema zur Konstruktion von SDNF und SKNF gemäß der Wahrheitstabelle ist unten für die Formel angegeben ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. Übung.

2.2.1 Nachfolgend finden Sie logische Ausdrücke. Vereinfachen Sie die Ausdrücke Ihrer Option so weit wie möglich, indem Sie die Booleschen Gesetze der Logik verwenden. Vergleichen Sie dann mithilfe von Wahrheitstabellen Ihren vereinfachten Ausdruck mit dem Original.

2.2.2. Finden Sie die Frage nach der Äquivalenz von f 1 und f 2 heraus, indem Sie sie auf SDNF reduzieren (Tabelle 1).

2.2.3. Finden Sie die Dualfunktion für f 3 nach dem verallgemeinerten und booleschen Prinzip (Tabelle 1). Vergleichen Sie die Ergebnisse.

№	f1	f2	f 3

2.3. Kontrollfragen.

2.3.1. Definieren Sie eine Aussage.

2.3.2. Listen Sie die grundlegenden Operationen der Anweisung auf.

2.3.3. Was ist eine Wahrheitstabelle?

2.3.4. Erstellen Sie Wahrheitstabellen für die folgenden Formeln:

~ ~ ~ ;

2.3.5. Unter Berücksichtigung der Konventionen zur Reihenfolge der Operationen lassen Sie die „zusätzlichen“ Klammern und das Zeichen „“ in den Formeln weg:

;

2.3.6. Beweisen Sie durch Anwendung äquivalenter Transformationen die identische Wahrheit der Formeln:

2.3.7. Finden Sie duale Formeln:

)

2.3.8. Reduzieren Sie die folgenden Formeln auf die perfekte DNF-Form (SDNF):

2.3.9. Wandeln Sie die folgenden Formeln in die perfekte CNF-Form (SKNF) um:

Labor Nr. 3

Thema:„Minimierung boolescher Funktionen. Logik"

Ziel: Erwerb praktischer Kenntnisse im Umgang mit Methoden zur Minimierung boolescher Funktionen.

3.1. Theoretische Informationen.

Mindestformen

Wie in gezeigt, kann jede boolesche Funktion in perfekter Normalform (disjunktiv oder konjunktiv) dargestellt werden. Darüber hinaus ist eine solche Darstellung der erste Schritt beim Übergang von einer tabellarischen Definition einer Funktion zu ihrem analytischen Ausdruck. In Zukunft werden wir von der disjunktiven Form ausgehen und die entsprechenden Ergebnisse für die konjunktive Form auf der Grundlage des Dualitätsprinzips erhalten.

Das kanonische Problem der Synthese logischer Schaltkreise auf boolescher Basis reduziert sich auf die Minimierung boolescher Funktionen, d.h. um sie in der disjunktiven Normalform darzustellen, die die geringste Anzahl von Buchstaben (Variablen und deren Negationen) enthält. Solche Formen werden als minimal bezeichnet. Bei der kanonischen Synthese wird davon ausgegangen, dass beide Signale und ihre Umkehrungen den Eingängen der Schaltung zugeführt werden.

Die in der disjunktiven Normalform dargestellte Formel wird durch wiederholte Anwendung der Klebeoperation und der Absorptionsoperation vereinfacht (die dualen Identitäten für die konjunktive Normalform sind: und). Unter und kann hier jede beliebige Formel der Booleschen Algebra verstanden werden. Als Ergebnis gelangen wir zu einem solchen analytischen Ausdruck, wenn weitere Transformationen nicht mehr möglich sind, d. h. Wir erhalten ein Sackgassenformular.

Unter den Dead-End-Formen gibt es auch eine minimale disjunktive Form, die möglicherweise nicht eindeutig ist. Um sicherzustellen, dass diese Sackgassenform minimal ist, müssen Sie alle Sackgassenformen finden und sie anhand der Anzahl der darin enthaltenen Buchstaben vergleichen.

Die Funktion sei zum Beispiel in perfekt normaler disjunktiver Form angegeben:

Wenn wir die Mitglieder gruppieren und den Klebevorgang anwenden, haben wir .

Mit einer anderen Gruppierungsmethode erhalten wir:

Beide Sackgassenformen sind nicht minimal. Um die Mindestform zu erhalten, müssen Sie raten, einen Term in der Originalformel zu wiederholen (dies ist seitdem immer möglich). Im ersten Fall kann ein solches Mitglied sein. Dann . Durch Hinzufügen des Begriffs erhalten wir: . Nachdem wir alle möglichen Optionen durchgegangen sind, können wir sicherstellen, dass die letzten beiden Formen minimal sind.

Auf dieser Ebene mit Formeln zu arbeiten ist wie im Dunkeln zu tappen. Der Prozess der Suche nach Minimalformen wird visueller und zielgerichteter, wenn einige speziell für diesen Zweck entwickelte grafische und analytische Darstellungen und Symbole verwendet werden.

Mehrdimensionaler Würfel

Jedem Eckpunkt eines -dimensionalen Würfels kann ein Einheitskonstituent zugewiesen werden. Daher ist die Teilmenge der markierten Eckpunkte eine Abbildung auf dem -dimensionalen Würfel einer booleschen Funktion von Variablen in perfekter disjunktiver Normalform. Auf Abb. 3.1 zeigt eine solche Abbildung für die Funktion aus Abschnitt 3.7.

Abb.3.1 Darstellung einer in SDNF dargestellten Funktion auf einem dreidimensionalen Würfel

Um eine Funktion von Variablen in einer disjunktiven Normalform anzuzeigen, muss eine Entsprechung zwischen ihren Minitermen und Elementen des -dimensionalen Würfels hergestellt werden.

Der Miniterm des (-1)-ten Rangs kann als Ergebnis der Verklebung zweier Miniterms des -ten Rangs (Einheitsbestandteil) betrachtet werden, d. h. , Auf einem -dimensionalen Würfel entspricht dies dem Ersetzen zweier Eckpunkte, die sich nur in den Werten der diese Eckpunkte verbindenden Koordinaten unterscheiden, durch eine Kante (die Kante soll die mit ihr inzidenten Eckpunkte abdecken). Somit entsprechen die Miniterme der Ordnung (-1) den Kanten des -dimensionalen Würfels. Ebenso entsprechen die Miniterme der (-2)-ten Ordnung den Flächen des -dimensionalen Würfels, die jeweils vier Eckpunkte (und vier Kanten) abdecken.

Elemente eines durch Dimensionen gekennzeichneten -dimensionalen Würfels werden als -Würfel bezeichnet. Scheitelpunkte sind also 0-Würfel, Kanten sind 1-Würfel, Flächen sind 2-Würfel und so weiter. Wenn wir die obige Argumentation verallgemeinern, können wir annehmen, dass der Miniterm des ()-ten Rangs in der disjunktiven Normalform für eine Funktion von Variablen durch einen -Würfel abgebildet wird und jeder -Würfel alle diese -Würfel der niedrigsten Dimension abdeckt mit seinen Eckpunkten verbunden. Als Beispiel in Abb. 3.2 zeigt die Abbildung einer Funktion von drei Variablen. Hier entsprechen Miniterme und 1-Cubes() und Miniterme werden durch 2-Cubes() dargestellt.

Abb.3.2 Funktionsabdeckung

Jede disjunktive Normalform wird also auf einem -dimensionalen Würfel durch eine Menge von -Würfeln dargestellt, die alle Eckpunkte abdecken, die den Einheitskonstituenten entsprechen (0-Würfel). Auch die umgekehrte Aussage gilt: Wenn eine bestimmte Sammlung von -Würfeln die Menge aller Eckpunkte abdeckt, die den Einheitswerten einer Funktion entsprechen, dann ist die Disjunktion der diesen -Würfeln entsprechenden Miniterme ein Ausdruck dieser Funktion in disjunktiver Normalform . Man sagt, dass eine solche Ansammlung von -Würfeln (oder ihnen entsprechenden Minitermen) eine Abdeckung einer Funktion bildet.

Der Wunsch nach einer minimalen Form wird intuitiv als Suche nach einer solchen Hülle verstanden, deren Anzahl an Würfeln kleiner und deren Abmessungen größer wären. Die der Mindestform entsprechende Überdeckung wird als Mindestüberdeckung bezeichnet. Zum Beispiel für die Abdeckungsfunktion in Abb. 3.3 entspricht den Mindestformen Und .

Reis. 3.3 Funktionsabdeckungen.

links – ; rechts –

Die Darstellung einer Funktion auf einem -dimensionalen Würfel ist klar und einfach, wenn . Ein vierdimensionaler Würfel kann wie in Abb. gezeichnet werden. 3.4, das eine Funktion von vier Variablen und ihre dem Ausdruck entsprechende Mindestabdeckung anzeigt . Die Verwendung dieser Methode erfordert so komplexe Konstruktionen, dass alle Vorteile verloren gehen.

Reis. 3.4 Funktionsanzeige auf einem vierdimensionalen Würfel

Karnot-Karten

Eine andere Methode zur grafischen Darstellung boolescher Funktionen verwendet Carnot-Karten, bei denen es sich um speziell organisierte Nachschlagetabellen handelt. Die Spalten und Zeilen der Tabelle entsprechen allen möglichen Wertesätzen von nicht mehr als zwei Variablen, und diese Sätze sind in einer solchen Reihenfolge angeordnet, dass sich jeder nachfolgende Satz vom vorherigen nur um den Wert einer der Variablen unterscheidet . Aus diesem Grund unterscheiden sich die benachbarten Zellen der Tabelle sowohl horizontal als auch vertikal im Wert nur einer Variablen. Zellen, die sich an den Rändern der Tabelle befinden, gelten ebenfalls als benachbart und verfügen über diese Eigenschaft. Auf Abb. 3.5 zeigt Karnaugh-Karten für zwei, drei, vier Variablen.

Reis. 3.5 Karnot-Karten für zwei, drei und vier Variablen

Wie in gewöhnlichen Wahrheitstabellen werden die Zellen der Mengen, auf denen die Funktion den Wert 1 annimmt, mit Einsen gefüllt (Nullen passen normalerweise nicht hinein, sie entsprechen leeren Zellen). Zum Beispiel in Abb. 3,6, A zeigt die Karnaugh-Karte für die Funktion, deren Darstellung auf einem vierdimensionalen Würfel in Abb. 1 dargestellt ist. 3.4. Zur Vereinfachung werden die Zeilen und Spalten, die den Werten 1 für eine Variable entsprechen, durch eine geschweifte Klammer mit der Bezeichnung dieser Variablen hervorgehoben.

Reis. 3.6 Carnot-Diagrammdarstellung einer Funktion von vier Variablen

(a) und seine Mindestdeckung (b)

Zwischen Funktionszuordnungen auf N-dimensionaler Würfel und auf der Karnaugh-Karte gibt es eine Eins-zu-eins-Entsprechung. Auf der Karte von Carnot S-Würfel entspricht einem Satz von 2 benachbarten Zellen, die in einer Reihe, Spalte, einem Quadrat oder einem Rechteck angeordnet sind (unter Berücksichtigung der Nähe gegenüberliegender Kanten der Karte). Daher gelten alle oben genannten Bestimmungen (siehe Absatz mehrdimensionaler Würfel) gelten für Carnot-Karten. Also, in Abb. 3,6, B Die Abdeckung der Karteneinheiten wird entsprechend der minimalen disjunktiven Form angezeigt die jeweilige Funktion.

Das Auslesen von Minitermen aus der Karnot-Karte erfolgt nach einer einfachen Regel. Die Zellen, die sich bilden S-Würfel, gib Miniter (n–s) Rang, der diese einschließt (n–s) Variablen, die dabei die gleichen Werte behalten S-Würfel, wobei der Wert 1 den Variablen selbst und der Wert 0 ihren Negationen entspricht. Variablen, die ihre Werte nicht behalten S-Würfel, fehlen im Minitherm. Unterschiedliche Lesarten führen zu unterschiedlichen Darstellungen der Funktion in disjunktiver Normalform (die rechte Seite ist minimal) (Abb. 3.7).

Die Verwendung von Karnaugh-Karten erfordert einfachere Konstruktionen im Vergleich zur Anzeige auf N-dimensionaler Würfel, insbesondere im Fall von vier Variablen. Um Funktionen von fünf Variablen anzuzeigen, werden zwei Karnot-Karten für vier Variablen verwendet, und für eine Funktion von sechs Variablen werden vier solcher Karten verwendet. Mit einer weiteren Zunahme der Anzahl der Variablen werden Karnot-Karten praktisch unbrauchbar.

In der Literatur bekannt Veitchs Karten unterscheiden sich nur in einer anderen Reihenfolge der Mengen der Variablenwerte und haben die gleichen Eigenschaften wie Karnaugh-Karten.

Komplex aus Würfeln

Das Versagen grafischer Methoden für eine große Anzahl von Variablen wird durch verschiedene analytische Methoden zur Darstellung boolescher Funktionen kompensiert. Eine dieser Darstellungen ist Komplex aus Würfeln, das die Terminologie eines mehrdimensionalen logischen Raums in Kombination mit einer speziell entwickelten Symbolik verwendet.

). 0-Würfel, die den Konstituenten der Einheit entsprechen, werden durch Mengen variabler Werte dargestellt, bei denen die Funktion gleich Eins ist. Offensichtlich im Protokoll

Reis. 3.8 Komplex von Funktionswürfeln dreier Variablen ( A) und seine symbolische Darstellung ( B)

Der Würfelkomplex entsteht maximale Funktionsabdeckung. Ohne all das S-Würfel, die von Würfeln höherer Dimension überdeckt werden, erhalten wir Überdeckungen, die Sackgassenformen entsprechen. Für das betrachtete Beispiel (Abb. 3.8) haben wir also eine Sackgassenabdeckung

was der Funktion entspricht . Auch in diesem Fall ist diese Deckung minimal.

Für zwei boolesche Funktionen entspricht die Disjunktionsoperation der Vereinigung ihrer Würfelkomplexe und die Konjunktionsoperation dem Schnittpunkt ihrer Würfelkomplexe. Die Negation einer Funktion entspricht der Addition eines Würfelkomplexes, d. h., und wird durch alle Eckpunkte bestimmt, an denen die Funktion den Wert 0 annimmt. Somit besteht eine Eins-zu-eins-Entsprechung (Isomorphismus) zwischen der Algebra von Boolesche Funktionen und Boolesche Mengen, die Würfelkomplexe darstellen.

Die Darstellung einer Funktion in Form von Würfelkomplexen ist weniger visuell, ihre wichtigsten Vorteile bestehen jedoch darin, dass Beschränkungen hinsichtlich der Anzahl der Variablen aufgehoben werden und die Codierung von Informationen bei der Verwendung von Computern erleichtert wird.

Boolesche Funktionen minimieren

Formulierung des Problems. Die Minimierung eines Schemas auf boolescher Basis reduziert sich auf die Suche nach der minimalen disjunktiven Form, die der minimalen Abdeckung entspricht. Die Gesamtzahl der im Normalformular enthaltenen Briefe wird durch die Deckungskosten ausgedrückt , wobei die Anzahl der Würfel ist, die die Abdeckung der gegebenen Funktion in n Variablen bilden. Die Mindestdeckung wird durch den niedrigsten Wert ihres Preises charakterisiert.

Normalerweise wird das Minimierungsproblem in zwei Schritten gelöst. Zunächst wird nach einer reduzierten Überdeckung gesucht, die alle -Würfel maximaler Dimension umfasst, aber keinen Würfel enthält, der von irgendeinem Würfel dieser Überdeckung überdeckt wird. Die entsprechende disjunktive Normalform heißt reduziert, ihre Miniterme heißen einfache Implikanten. Für diese Funktion ist die reduzierte Abdeckung die einzige, sie kann jedoch redundant sein, da einige der Würfel durch Sammlungen anderer Würfel abgedeckt sind.

Im zweiten Schritt erfolgt der Übergang von reduzierten zu Dead-End-disjunktiven Normalformen, aus denen Minimalformen ausgewählt werden. Dead-End-Formen werden gebildet, indem alle redundanten Würfel aus der reduzierten Abdeckung ausgeschlossen werden, ohne dass die verbleibende Menge von Würfeln immer noch eine Abdeckung einer bestimmten Funktion bildet, aber bei weiterem Ausschluss eines der Würfel deckt sie nicht mehr die Menge aller ab Scheitelpunkte entsprechen den Einheitswerten der Funktion, d. h. sie sind keine Abdeckung mehr.

Ein Würfel mit reduzierter Abdeckung, der Eckpunkte einer bestimmten Funktion abdeckt, die von keinem anderen Würfel abgedeckt werden, kann nicht redundant sein und wird immer in der Mindestabdeckung enthalten sein. Ein solcher Würfel sowie der ihm entsprechende Implikant werden als Extremal (essentieller Implikant) bezeichnet, und die von ihm abgedeckten Eckpunkte werden als aufgehobene Eckpunkte bezeichnet. Die Menge der Extremale bildet den Kern der Abdeckung. Es ist klar, dass beim Übergang von einer reduzierten zu einer minimalen Abdeckung zunächst alle Extremale ausgewählt werden sollten. Wenn die Menge der Extremale keine Überdeckung bildet, wird sie durch Würfel aus der reduzierten Überdeckung zu einer Überdeckung ergänzt.

Die angegebenen Definitionen sind in Abb. dargestellt. 3.9, wobei die reduzierte Abdeckung (siehe Abb. 3.9a, ) und Mindestüberdeckungen (Abb. 3.9b) und (siehe Abb. 3.9b) werden wie folgt ausgedrückt.

Lassen Sie uns das Konzept der elementaren Disjunktion einführen.

Eine elementare Disjunktion ist ein Ausdruck der Form

Die konjunktive Normalform (KNF) einer logischen Funktion ist die Konjunktion einer beliebigen endlichen Menge paarweise unterschiedlicher elementarer Disjunktionen. Zum Beispiel logische Funktionen

sind Konjunktionen elementarer Disjunktionen. Daher werden sie in konjunktiver Normalform geschrieben.

Eine durch einen analytischen Ausdruck gegebene beliebige logische Funktion kann durch Ausführen der folgenden Operationen auf CNF reduziert werden:

Verwendung der Inversionsregel, wenn die Negationsoperation auf einen logischen Ausdruck angewendet wird;

Verwendung des Distributivitätsaxioms in Bezug auf die Multiplikation:

Verwendung der Absorptionsoperation:

Ausnahmen bei Disjunktionen sich wiederholender Variablen oder deren Negationen;

Entfernung aller identischen Elementardisjunktionen bis auf eine;

Löschen aller Disjunktionen, die gleichzeitig eine Variable und ihre Negation enthalten.

Die Gültigkeit der aufgeführten Operationen ergibt sich aus den Grundaxiomen und Identitätsrelationen der Algebra der Logik.

Eine konjunktive Normalform heißt perfekt, wenn jede darin enthaltene Elementardisjunktion alle Variablen, von denen die Funktion abhängt, in direkter oder inverser Form enthält.

Die Umwandlung von CNF in perfektes CNF erfolgt durch die Durchführung der folgenden Operationen:

Zusätze zu jeder Elementardisjunktion von Konjunktionen von Variablen und deren Negationen, sofern sie nicht in dieser Elementardisjunktion enthalten sind;

Verwendung des Distributivitätsaxioms;

Entfernung aller identischen Elementardisjunktionen bis auf eine.

Jede logische Funktion kann in einem perfekten CNF dargestellt werden, außer

identisch gleich eins (). Eine besondere Eigenschaft eines perfekten CNF besteht darin, dass die Darstellung einer logischen Funktion darin einzigartig ist.

Die in einer perfekten CNF-Funktion enthaltenen elementaren Disjunktionen werden Nullkonstituenten genannt. Jede Nullkomponente in einem perfekten CNF verschwindet auf der einzigen Menge von Variablenwerten, die die Nullmenge der Funktion ist. Folglich stimmt die Anzahl der Nullmengen einer logischen Funktion mit der Anzahl der in ihrer perfekten CNF enthaltenen Nullkonstituenten überein.

Die Nullkonstante der logischen Funktion im perfekten CNF wird durch die Konjunktion 2nKonstituent von Null dargestellt. Lassen Sie uns eine Regel zum Kompilieren des SKNF einer logischen Funktion gemäß der Korrespondenztabelle formulieren.

Für jede Zeile der Korrespondenztabelle, in der die Funktion gleich Null ist, wird eine elementare Disjunktion aller Variablen erstellt. Die Disjunktion umfasst die Variable selbst, wenn ihr Wert gleich Null ist, oder die Negation, wenn ihr Wert gleich Eins ist. Die resultierenden Elementardisjunktionen werden durch das Konjunktionszeichen zusammengefasst.

Beispiel 3.4. Für die logische Funktion z(x), gegeben durch die Nachschlagetabelle 2.2, definieren wir die perfekte Konjunktivform.

Für die erste Zeile der Tabelle, die der Nullfunktionsmenge 000 entspricht, finden wir die Nullkomponente. Nachdem wir ähnliche Operationen für die zweite, dritte und fünfte Zeile durchgeführt haben, bestimmen wir die gewünschte perfekte CNF-Funktion:

Es ist zu beachten, dass es für Funktionen, deren Anzahl an Einheitsmengen die Anzahl an Nullmengen übersteigt, kompakter ist, sie in der Form von SKNF zu schreiben und umgekehrt.

Normalform Die logische Formel enthält keine Zeichen der Implikation, Äquivalenz und Negation nichtelementarer Formeln.

Die Normalform gibt es in zwei Formen:

Konjunktive Normalform (CNF)-- Konjunktion mehrerer Disjunktionen, zum Beispiel $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

disjunktive Normalform (DNF)-- Disjunktion mehrerer Konjunktionen, zum Beispiel $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.

SKNF

Perfekte konjunktive Normalform (SKNF) ist ein CNF, der drei Bedingungen erfüllt:

enthält keine identischen Elementardisjunktionen;

keine der Disjunktionen enthält die gleichen Variablen;

Jede Elementardisjunktion enthält jede Variable in der gegebenen KNF.

Jede boolesche Formel, die nicht identisch wahr ist, kann in SKNF dargestellt werden.

Regeln zur Konstruktion von SKNF gemäß der Wahrheitstabelle

Für jeden Variablensatz, für den die Funktion 0 ist, wird die Summe aufgezeichnet, wobei Variablen mit dem Wert 1 mit einer Negation genommen werden.

SDNF

Perfekte disjunktive Normalform (PDNF) ist ein DNF, der drei Bedingungen erfüllt:

enthält keine identischen Elementarkonjunktionen;

keine der Konjunktionen enthält die gleichen Variablen;

Jede Elementarkonjunktion enthält alle Variablen aus der gegebenen DNF, und zwar in derselben Reihenfolge.

Darüber hinaus kann jede boolesche Formel, die nicht identisch falsch ist, in SDNF auf einzigartige Weise dargestellt werden.

Regeln zum Aufbau von SDNF gemäß der Wahrheitstabelle

Für jeden Variablensatz, in dem die Funktion gleich 1 ist, wird das Produkt geschrieben und die Variablen, die den Wert 0 haben, werden mit Negation genommen.

Beispiele für die Suche nach SKNF und SDNF

Beispiel 1

Schreiben Sie eine logische Funktion gemäß ihrer Wahrheitstabelle:

Bild 1.

Lösung:

Lassen Sie uns die Regel zum Erstellen von SDNF verwenden:

Figur 2.

Wir erhalten SDNF:

Verwenden wir die SKNF-Konstruktionsregel.

Normalformen boolescher Funktionen Die Darstellung einer booleschen Funktion in Form einer Disjunktion konjunktiver Terme von Einheitskonstituenten Ki 2.7 wird als disjunktive Normalform des DNF dieser Funktion bezeichnet. Enthalten genau nacheinander alle logischen Variablen mit oder ohne Negationen, dann heißt diese Darstellungsform der Funktion die perfekte disjunktive Normalform der SDNF dieser Funktion. Wie Sie sehen, müssen Sie beim Kompilieren einer SDNF-Funktion eine Disjunktion aller Minterme durchführen, für die die Funktion den Wert 1 annimmt.

Teilen Sie Ihre Arbeit in sozialen Netzwerken

Wenn Ihnen dieses Werk nicht zusagt, finden Sie unten auf der Seite eine Liste ähnlicher Werke. Sie können auch die Suchschaltfläche verwenden

Vorlesung 1.xx

Normalformen boolescher Funktionen

Darstellung einer booleschen Funktion in Form einer Disjunktion konjunktiver Terme (eines Einheitskonstituenten) K i

, (2.7)

angerufen disjunktive Normalform(DNF) dieser Funktion.

Wenn alle Konjunktivbegriffe in DNF sind Minterms , d.h. genau nacheinander alle logischen Variablen enthalten, mit oder ohne Negationen, dann heißt diese Darstellungsform der Funktionperfekte disjunktive Normalform(SDNF ) dieser Funktion. SDNF heißt perfekt , weil jeder Term in der Disjunktion alle Variablen umfasst; disjunktiv , weil die Hauptoperation in der Formel die Disjunktion ist. Das Konzept "Normalform„bedeutet eine eindeutige Art, eine Formel zu schreiben, die eine bestimmte Funktion implementiert.

Angesichts des oben Gesagten impliziert Satz 2.1 den folgenden Satz.

Satz 2. Jede boolesche Funktion(nicht identisch gleich 0) kann in SDNF dargestellt werden, .

Beispiel 3 Lassen Sie uns eine Tabellenfunktion haben f (x 1, x 2, x 3) (Tabelle 10).

Tabelle 10

			f (x 1 , x 2 , x 3 )

Basierend auf Formel (2.6) erhalten wir:

Wie Sie sehen, müssen Sie beim Kompilieren einer SDNF-Funktion eine Disjunktion aller Minterme durchführen, für die die Funktion den Wert 1 annimmt.

Darstellung einer booleschen Funktion in Form einer Konjunktion disjunktiver Terme (Konstituent Null) D i

, (2.8)

angerufen konjunktive Normalform(CNF) dieser Funktion.

Wenn alle disjunktiven Begriffe von CNF sind maxterms , also genau nacheinander alle logischen Variablen der Funktion enthalten, mit oder ohne Negationen, dann wird ein solcher CNF aufgerufenperfekte konjunktive Normalform(SKNF) dieser Funktion.

Satz 3. Jede boolesche Funktion(nicht identisch gleich 1) können bei SKNF eingereicht werden, und diese Darstellung ist einzigartig.

Der Beweis des Satzes kann analog zum Beweis von Satz 2.1 auf der Grundlage des folgenden Shannon-Lemmas zur konjunktiven Zerlegung durchgeführt werden.

Shannons Lemma . Jede boolesche Funktion f (x 1 , x 2 , …, x m ) aus m Variablen können dargestellt werden als:

. (2.9)

Es ist zu beachten, dass beide Formen der Darstellung einer logischen Funktion (DNF und CNF) theoretisch in ihren Fähigkeiten gleich sind: Jede logische Formel kann sowohl in DNF (mit Ausnahme der identischen Null) als auch in CNF (mit Ausnahme der identischen Einheit) dargestellt werden. . Je nach Situation kann die Darstellung der Funktion in der einen oder anderen Form kürzer sein.

In der Praxis wird am häufigsten DNF verwendet., weil diese Form einem Menschen vertrauter ist: Seit seiner Kindheit ist er eher daran gewöhnt, Produkte zu addieren als Summen zu multiplizieren (im letzteren Fall möchte er intuitiv die Klammern öffnen und so zu DNF gelangen).

Beispiel 4. Für die Funktion f (x 1, x 2, x 3 ), in der Tabelle angegeben. 10, schreiben Sie es an SKNF.

Im Gegensatz zu SDNF müssen Sie beim Kompilieren von SKNF in der Wahrheitstabelle einer logischen Funktion Kombinationen von Variablen betrachten, für die die Funktion den Wert 0 annimmt, und eine Konjunktion der entsprechenden Maxterms erstellen.aber die Variablen müssen mit inverser Inversion genommen werden:

Es ist zu beachten, dass es unmöglich ist, direkt vom SDNF einer Funktion zu ihrem SKNF zu wechseln oder umgekehrt. Beim Versuch solcher Transformationen erhält man Funktionen, die zu den gewünschten invers sind. Ausdrücke für SDNF- und SKNF-Funktionen können direkt nur aus ihrer Wahrheitstabelle abgerufen werden.

Beispiel 5. Für die Funktion f (x 1, x 2, x 3 ), in der Tabelle angegeben. 10. Versuchen Sie, von SDNF zu SKNF zu wechseln.

Mit dem Ergebnis von Beispiel 2.3 erhalten wir:

Wie Sie sehen können, erhalten wir bei der allgemeinen Inversion die SKNF einer logischen Funktion, die in Bezug auf die in Beispiel 2.4 erhaltene Funktion invers ist:

da es alle Maxterms enthält, die nicht im Ausdruck für den SKNF der betrachteten Funktion enthalten sind.

1. Unter Verwendung der Eigenschaften der Operationen (siehe Tabelle 9) Identität (), Summe Modulo 2 (), Implikation () gehen wir zu den Operationen UND, ODER, NICHT (zur Boole-Basis) über.

2. Mithilfe der Eigenschaften der Negation und der Gesetze von de Morgan (siehe Tabelle 9) erreichen wir, dass die Negationsoperationen nur für einzelne Variablen und nicht für ganze Ausdrücke gelten.

3. Mithilfe der Eigenschaften der logischen Operationen AND und OR (siehe Tabelle 9) erhalten wir die Normalform (DNF bzw. CNF).

4. Bei Bedarf gehen wir zu perfekten Formen über (SDNF oder SKNF). Um beispielsweise den SKNF zu erhalten, müssen Sie häufig die Eigenschaft verwenden: .

Beispiel 6 In eine boolesche SKNF-Funktion konvertieren

Wenn wir die Schritte des obigen Algorithmus der Reihe nach ausführen, erhalten wir:

Unter Verwendung der Absorptionseigenschaft erhalten wir:

Somit haben wir CNF-Funktionen erhalten f (x 1 , x 2 , x 3 ). Um seinen SKNF zu erhalten, müssen Sie jede Disjunktion, in der eine Variable fehlt, zweimal mit dieser Variablen und mit ihrer Negation wiederholen:

2.2.6. Minimierung boolescher Funktionen

Da die gleiche logische Funktion dargestellt werden kann durch H persönliche Formeln, dann das einfachste Pho finden R Mule, das eine boolesche Funktion definiert, vereinfacht die Logikschaltung, die die boolesche Funktion implementiert zu tsyu. Mindestform lÖ logische FunktionIn gewisser Weise können wir eine solche Basis betrachten, die die minimale Anzahl von Überlagerungen von func enthält Zu Basis, Erlauben und Klammern. Allerdings ist es schwierig, eine effiziente Lösung zu konstruieren l der Algorithmus einer solchen Minimierung mit Erhalt des Minimums in Klammern fo r wir.

Betrachten Sie ein einfacheres Minimierungsproblem bei der Synthese kombinatorischer Schaltkreise, bei dem nicht die minimale Klammerform einer Funktion gesucht wird, sondern ihr minimaler DNF. Für diese Aufgabe gibt es einfache effiziente Algorithmen.

Quine-Methode

Die zu minimierende Funktion wird in SDNF dargestellt und alle möglichen Operationen des unvollständigen Klebens werden darauf angewendet

, (2.10)

und dann Absorption

, (2.11)

und dieses Schrittpaar wird wiederholt angewendet. Somit ist es möglich, den Rang von Begriffen zu verringern. Dieser Vorgang wird wiederholt, bis kein Begriff mehr übrig bleibt, der mit einem anderen Begriff verklebt werden kann.

Beachten Sie, dass die linke Seite der Gleichung (2.10) sofort auf einfachere und offensichtlichere Weise minimiert werden könnte:

Diese Methode ist schlecht, weil bei einer solchen direkten Minimierung entweder Konjunktivbegriffe verschwinden, obwohl es immer noch Fälle gibt, in denen sie zum Kleben und Absorbieren mit den übrigen Begriffen verwendet werden.

Es ist zu beachten, dass die Methode von Quine ziemlich zeitaufwändig ist, sodass die Wahrscheinlichkeit, dass bei den Transformationen Fehler gemacht werden, recht hoch ist. Sein Vorteil besteht jedoch darin, dass es theoretisch für beliebig viele Argumente verwendet werden kann und mit zunehmender Anzahl von Variablen die Transformationen weniger kompliziert werden.

Carnot-Kartenmethode

Die Carnot-Methode für Karten (Tabellen) ist eine visuellere, weniger zeitaufwändige und zuverlässige Methode zur Minimierung logischer Funktionen, ihre Verwendung ist jedoch praktisch auf Funktionen mit 3–4 Variablen, maximal 5–6 Variablen, beschränkt.

Carnot-Karte Dies ist eine zweidimensionale tabellarische Form zur Darstellung der Wahrheitstabelle einer booleschen Funktion, die es einfach macht, die minimale DNF logischer Funktionen in einer grafischen visuellen Form zu finden. Jede Zelle der Tabelle ist außerdem mit dem Minterm des SDNF der minimierten Funktion verknüpft, und zwar so, dass alle Symmetrieachsen der Tabelle Zonen entsprechen, die in einer Variablen zueinander invers sind. Eine solche Anordnung der Zellen in der Tabelle erleichtert die Bestimmung der hängenden SDNF-Terme (die sich im Umkehrzeichen nur einer Variablen unterscheiden): Sie sind in der Tabelle symmetrisch angeordnet.

Wahrheitstabellen und Karnaugh-Karten für UND- und ODER-Funktionen zweier Spuren e Die Variablen sind in Abb. dargestellt. 8. In jede Zelle der Karte wird ein Wert geschrieben. A Wert der Funktion auf der Wertemenge des Arguments, das dieser Zelle entspricht n tov.

A) UND b) ODER

Reis. 8. Ein Beispiel für Karnaugh-Karten für Funktionen zweier Variablen

In der Karnaugh-Karte gibt es nur eine 1 für die Und-Funktion, daher kann sie nicht mit irgendetwas zusammengeklebt werden. Im Ausdruck für die Minimalfunktion gibt es nur einen Term, der dieser 1 entspricht:

f = x y .

Für die ODER-Funktion gibt es in der Karnaugh-Karte bereits drei Einsen, und es können zwei Klebepaare gebildet werden, wobei 1 dem Term entspricht xy , wird zweimal verwendet. Im Ausdruck für die Minimalfunktion müssen Sie die Terme für die zu verklebenden Paare schreiben, dabei alle Variablen belassen, die sich für dieses Paar nicht ändern, und die Variablen entfernen, die ihren Wert ändern. Für horizontales Kleben erhalten wir X , und für vertikal j , als Ergebnis erhalten wir den Ausdruck

f = x + y .

Auf Abb. 9 zeigt die Wahrheitstabellen von zwei Funktionen von drei Variablen ( A ) und ihre Karnot-Karten ( b und c). Funktion f 2 unterscheidet sich vom ersten darin, dass es nicht auf drei Variablensätzen definiert ist (dies wird durch einen Bindestrich in der Tabelle angezeigt).

Bei der Bestimmung des minimalen DNF einer Funktion werden die folgenden Regeln verwendet. Alle Zellen, die 1 enthalten, werden zu geschlossenen rechteckigen Bereichen namens zusammengefasst k-Würfel, wobei k = log 2 K, K Nummer 1 in einem rechteckigen Bereich. In diesem Fall sollte jede Fläche ein Rechteck mit der Anzahl der Zellen 2 sein k , wobei k = 0, 1, 2, 3, … . Für k = 1 Rechteck wird aufgerufen einer ist ein Würfel und enthält 2 1 = 2 Einheiten; für k = 2 Rechteck enthält 2 2 = 4 Einheiten und heißt Zweiwürfel; für k = 3 Fläche von 2 3 = 8 Einheiten aufgerufen Dreiwürfel ; usw. Einheiten, die nicht zu Rechtecken zusammengefasst werden können, können aufgerufen werden null Würfel , die nur eine Einheit enthalten (2 0 = 1). Wie man sehen kann, sogar k Die Regionen können quadratisch sein (aber nicht unbedingt), und wenn sie ungerade sind k nur Rechtecke.

						v. Chr

Reis. 9. Ein Beispiel für Karnaugh-Karten für Funktionen von drei Variablen

Diese Bereiche können sich überlappen, d. h. die gleichen Zellen können in unterschiedlichen Bereichen enthalten sein. Dann wird die minimale DNF der Funktion als Disjunktion aller entsprechenden Konjunktivterme geschrieben k - Würfel.

Jeder dieser Bereiche auf der Karnaugh-Karte wird im minimalen DNF durch eine Konjunktion dargestellt, deren Anzahl an Argumenten beträgt k kleiner als die Gesamtzahl der Funktionsargumente M , d.h. diese Zahl ist m k . Jede Konjunktion des minimalen DNF besteht nur aus den Argumenten, die für den entsprechenden Bereich der Karte entweder Werte ohne Inversionen oder nur mit Inversionen haben, also ihren Wert nicht ändern.

Wenn man also Kartenzellen mit geschlossenen Regionen abdeckt, sollte man darauf achten, dass die Anzahl der Regionen minimal ist und jede Region so viele Zellen wie möglich enthält, da in diesem Fall die Anzahl der Terme im minimalen DNF minimal ist und die Die Anzahl der Argumente in der entsprechenden Konjunktion ist minimal.

Für die Funktion gemäß der Karnot-Karte in Abb. 9, b finden wir

da für den oberen geschlossenen Bereich die Variablen x 1 und x 2 haben Werte ohne Inversionen für den unteren x 1 Angelegenheiten mit Inversion, und x 3 ohne Invertierung.

Undefinierte Werte in der Karte in Abb. 9, V kann durch Ersetzen durch Null oder Eins neu definiert werden. Für diese Funktion ist es klar, dass es vorteilhafter ist, beide unsicheren Werte durch 1 zu ersetzen. In diesem Fall werden zwei Regionen gebildet, bei denen es sich um unterschiedliche Arten von 2-Würfeln handelt. Dann lautet der Ausdruck für die minimale DNF-Funktion wie folgt:

Bei der Konstruktion geschlossener Bereiche ist es zulässig, die Karnot-Karte sowohl horizontal als auch vertikal zu einem Zylinder zu komprimieren. R zu den vertikalen Achsen mit der Vereinigung gegenüberliegender Flächen ka R Sie, d. h. Einheiten, die symmetrisch entlang der Ränder der Carnot-Karte angeordnet sind H können aber auch kombiniert werden.

Karnot-Karten können auf verschiedene Arten gezeichnet werden (Abbildung 10).

									x 2 x 3

ein b

Reis. 10. Verschiedene Möglichkeiten zur Darstellung von Carnot-Karten
für eine Funktion von 3 Variablen

Aber die praktischsten Versionen von Karnaugh-Karten für Funktionen von 2–4 Variablen sind die in Abb. 11 Tabellen, weil sie für jede Zelle angezeigt werden A Alle Variablen liegen in direkter oder inverser Form vor.

ein b

Reis. elf. Das bequemste Bild von Carnot-Karten
für Funktionen 3 ( a) und 4 (b) Variablen

Für Funktionen mit 5 und 6 Variablen gilt die in Abb. dargestellte Methode. 10, V.

Reis. 12. Bild einer Karnaugh-Karte für eine Funktion von 5 Variablen

Reis. 13. Bild einer Karnaugh-Karte für eine Funktion von 6 Variablen

Andere verwandte Werke, die Sie interessieren könnten.vshm>
9020.		PRINZIP DER DUALITÄT. ERWEITERUNG BOOLER FUNKTIONEN IN VARIABLEN. Perfekte disjunktive und konjunktive Normalformen	96,34 KB
	Dieser Satz ist konstruktiv, da er uns erlaubt, für jede Funktion eine Formel zu konstruieren, die sie in Form eines perfekten d.s. realisiert. F. Dazu markieren wir in der Wahrheitstabelle für jede Funktion alle Zeilen, in denen
6490.		Beschreibung und Minimierung logischer Funktionen	187,21 KB
	In verbaler Form wird die Beziehung zwischen den Argumenten einer Funktion und ihren Werten ausgedrückt. Beispiel: Eine Funktion mit drei Argumenten wertet aus, wenn zwei oder mehr beliebige Argumente der Funktion gleich sind. Es besteht darin, eine Wahrheitstabelle zu erstellen, die die Werte der Funktion für alle Sätze von Argumentwerten enthält. In diesem Beispiel erhalten wir laut Wahrheitstabelle einen solchen Eintrag in Form von DNF ...
6707.		Entwerfen relationaler Datenbanken. Designprobleme im klassischen Ansatz. Normalisierungsprinzipien, Normalformen	70,48 KB
	Was ist ein relationaler Datenbankentwurf? Es handelt sich um eine Reihe miteinander verbundener Beziehungen, in denen alle Attribute definiert, die Primärschlüssel der Beziehung festgelegt und einige zusätzliche Beziehungseigenschaften festgelegt werden, die sich auf die Prinzipien der Aufrechterhaltung der Integrität beziehen. Daher muss das Design der Datenbank sehr präzise und verifiziert sein. Tatsächlich ist das Datenbankprojekt die Grundlage des zukünftigen Softwarepakets, das noch lange und von vielen Benutzern verwendet werden wird.
4849.		Formen und Methoden der Umsetzung staatlicher Aufgaben	197,3 KB
	Der Begriff „Funktion“ hat in der in- und ausländischen wissenschaftlichen Literatur eine unterschiedliche Bedeutung. In philosophischer und allgemeiner soziologischer Hinsicht wird es als „äußere Manifestation der Eigenschaften eines Objekts in einem gegebenen Beziehungssystem“ betrachtet; als eine Reihe gewöhnlicher oder spezifischer Handlungen von Einzelpersonen oder Körperschaften
17873.		Bildung logischer UUD bei Schülern der 3. Klasse	846,71 KB
	Psychologische und pädagogische Aspekte des Problems der Bildung logischer universeller Handlungen bei jüngeren Schulkindern. Methoden zur Beurteilung der Bildung logischer UUD. Die Entwicklung eines Konzepts zur Entwicklung universeller Bildungsaktivitäten im System der Allgemeinbildung wird neuen gesellschaftlichen Anforderungen gerecht. Die wichtigste Aufgabe des modernen Bildungssystems ist die Gestaltung universeller Bildungsaktivitäten UUD. Die Gestaltung universeller Bildungsaktivitäten ist der Schlüssel zur Vorbeugung von Schulschwierigkeiten.
2638.		Technische Umsetzung logischer Verknüpfungen in automatischen Sperrsystemen	1,04 MB
	Technische Umsetzung logischer Verknüpfungen in automatischen Blockiersystemen Die technische Umsetzung drei- und vierstelliger AB-Steuerungsalgorithmen kann unter Verwendung von Relaiskontakten und berührungslosen diskreten und integralen Logikelementen erreicht werden...
10203.		ANWENDUNG DES KONZEPTS DES RISIKOORIENTIERTEN ANSATZES ZUR KONSTRUKTION STRUKTURELLER UND LOGISCHER MODELLE DER ENTSTEHUNG UND ENTWICKLUNG VON NOTFÄLLEN	70,8 KB
	Allgemeine Risikoanalyse Die Produktionsumgebung ist mit leistungsstarken technologischen Systemen und Technologien gesättigt, die menschliche Arbeit produktiver und körperlich weniger anstrengend, aber gefährlicher machen. Unter Risiko versteht man den unerwarteten und plötzlichen Eintritt einer gefährlichen Situation. Täglich sind wir mit zahlreichen Risiken konfrontiert, die meisten davon bleiben jedoch potenziell. Die Risikotheorie sieht eine quantitative Bewertung der negativen Auswirkungen auf einen Menschen sowie der Schädigung seiner Gesundheit und seines Lebens vor.
11576.		Das Konzept, die Arten und Formen von Transaktionen. Folgen der Nichteinhaltung der erforderlichen Geschäftsform	49,82 KB
	Erkennung der Transaktion als ungültige Arten einer ungültigen Transaktion. Der Anwendungswert der Kursarbeit besteht darin, das Konzept einer Transaktion zu vereinfachen, d. h. ihre öffentliche Präsentation in einer zugänglicheren Form.
6213.		Approximation von Funktionen	3,08 MB
	Die erste besteht darin, eine analytisch oder tabellarisch gegebene Funktion durch eine andere Funktion zu ersetzen, die der ursprünglichen Funktion nahe kommt, aber einfacher und für Berechnungen bequemer ist. Wenn man beispielsweise eine Funktion durch ein Polynom ersetzt, erhält man einfache Formeln für die numerische Integration und Differenzierung; Das Ersetzen einer Tabelle durch eine Näherungsfunktion ermöglicht es, Werte an ihren Zwischenpunkten zu erhalten. Es entsteht auch das zweite Problem der Wiederherstellung einer Funktion auf einem bestimmten Segment aus den Werten der Funktion, die auf diesem Segment in einer diskreten Menge von Punkten angegeben sind. Die Antwort auf eine solche Frage...
14058.		Die Entwicklung der Funktionen des Staates	29,99 KB
	Der russische Staat als Rechtsphänomen muss zunächst die Verwirklichung des Staatszwecks sowie seiner grundlegenden verfassungsrechtlichen Merkmale als demokratischer föderaler, rechtlicher, sozialer, säkularer Staat mit republikanischer Regierungsform sicherstellen. Der Hauptzweck des Staates wird durch Art bestimmt.

Für jede logische Formel ist es mit Hilfe identischer Transformationen möglich, unendlich viele ihr äquivalente Formeln zu konstruieren. In der Algebra der Logik besteht eine der Hauptaufgaben in der Suche nach kanonischen Formen (d. h. nach einer einzigen Regel, dem Kanon, aufgebauten Formeln).

Wird eine logische Funktion durch Disjunktion, Konjunktion und Negation von Variablen ausgedrückt, so nennt man diese Darstellungsform normal.

Unter den Normalformen stechen die perfekten Normalformen hervor (die Formen, in denen Funktionen auf einzigartige Weise geschrieben sind).

Perfekte disjunktive Normalform (PDNF)

Definition. Eine Formel heißt Elementarkonjunktion, wenn sie durch die Konjunktion einer bestimmten Anzahl von Variablen oder deren Negationen gebildet wird.

Beispiele: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definition. Eine Formel wird als disjunktive Normalform (DNF) bezeichnet, wenn es sich um eine Disjunktion von sich nicht wiederholenden Elementarkonjunktionen handelt.

DNF wird in der folgenden Form geschrieben: F 1 ∨ F 2 ∨ ... ∨ F n , wobei F i eine Elementarkonjunktion ist

Beispiele: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definition. Eine logische Formel in k Variablen wird als perfekte disjunktive Normalform (PDNF) bezeichnet, wenn:
1) Die Formel ist eine DNF, in der jede Elementarkonjunktion eine Konjunktion von k Variablen x 1 , x 2 , ..., x k ist und die i-te Stelle dieser Konjunktion entweder die Variable x i oder ihre Negation ist;
2) Alle Elementarkonjunktionen in einem solchen DNF sind paarweise verschieden.

Beispiel: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Perfekte konjunktive Normalform (SKNF)

Definition. Eine Formel heißt Elementardisjunktion, wenn sie durch die Disjunktion einer bestimmten Anzahl von Variablen oder deren Negationen gebildet wird.

Beispiele: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definition. Eine Formel wird als konjunktive Normalform (KNF) bezeichnet, wenn es sich um eine Konjunktion von sich nicht wiederholenden Elementardisjunktionen handelt.

CNF wird in der folgenden Form geschrieben: F 1 ∧ F 2 ∧ ... ∧ F n , wobei F i eine elementare Disjunktion ist

Beispiele: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definition. Eine logische Formel in k Variablen wird als perfekte konjunktive Normalform (KDNF) bezeichnet, wenn:
1) Die Formel ist eine CNF, in der jede elementare Disjunktion eine Disjunktion von k Variablen x 1 , x 2 , …, x k ist und die i-te Stelle dieser Disjunktion entweder die Variable x i oder ihre Negation ist;
2) Alle Elementardisjunktionen in einem solchen KNF sind paarweise verschieden.

Beispiel: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

beachte das Jede logische Funktion, die nicht identisch 0 oder 1 ist, kann als SDNF oder SKNF dargestellt werden.

Algorithmus zur Konstruktion von SDNF gemäß der Wahrheitstabelle

Wählen Sie alle Zeilen der Tabelle aus, in denen der Wert der Funktion gleich eins ist.
Schreiben Sie für jede dieser Zeilen die Konjunktion aller Variablen wie folgt: Wenn der Wert einer Variablen in dieser Menge gleich 1 ist, dann beziehen wir die Variable selbst in die Konjunktion ein, andernfalls ihre Negation.
Wir verbinden alle resultierenden Konjunktionen durch Disjunktionsoperationen.

Algorithmus zur Konstruktion von SKNF gemäß der Wahrheitstabelle

Wählen Sie alle Zeilen der Tabelle aus, in denen der Wert der Funktion gleich Null ist.
Schreiben Sie für jede dieser Zeilen die Disjunktion aller Variablen wie folgt: Wenn der Wert einer Variablen in dieser Menge 0 ist, dann beziehen wir die Variable selbst in die Konjunktion ein, andernfalls ihre Negation.
Wir verbinden alle erhaltenen Disjunktionen durch Konjunktionsoperationen.

Die Analyse der Algorithmen zeigt, dass es besser ist, einen SDNF zu erstellen, andernfalls einen SKNF, wenn der Wert der Funktion in den meisten Zeilen der Wahrheitstabelle gleich 0 ist, um ihre logische Formel zu erhalten.

Beispiel: Gegeben sei eine Wahrheitstabelle einer logischen Funktion von drei Variablen. Konstruieren Sie eine logische Formel, die diese Funktion implementiert.

X	j	z	F(x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Weil In den meisten Zeilen der Wahrheitstabelle ist der Wert der Funktion gleich 1, dann erstellen wir die SKNF. Als Ergebnis erhalten wir die folgende logische Formel:
F = (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Schauen wir uns die resultierende Formel an. Dazu erstellen wir eine Wahrheitstabelle der Funktion.

X	j	z	X	¬ x ∨ y ∨ z	¬z	¬ x ∨ y ∨ ¬ z	F(x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

Beim Vergleich der ursprünglichen Wahrheitstabelle und der für die logische Formel erstellten stellen wir fest, dass die Funktionswertspalten identisch sind. Dies bedeutet, dass die logische Funktion korrekt aufgebaut ist.

Kategorien

Die Wahl des Herausgebers