Konjunktive Normalform einer logischen Funktion. Normalformen logischer Funktionen

Standardbasis. Elementare Formeln sind Literale. Elementare Konjunktion (Disjunktion). Disjunktive (Konjunktiv) Normalform und Perfektform. Satz: Jede boolesche Funktion außer 0 (von 1) kann als SDNF (SKNF) dargestellt werden. Vollständigkeit der Standardbasis. Beispiele für vollständige Basen: Zhegalkin-Basis, Schaeffers Strich, Peirce's Pfeil.

Standardbasis ist eine Menge von drei Anfangsoperationen der Booleschen Algebra: Addition (Vereinigung), Multiplikation (Schnittpunkt) und Negation.

Hier rufen wir an wörtlich Variable x oder ihre Negation x und bezeichnen xИ. Boolesche Schnittmenge mehrerer Literale, die durch verschiedene Variablen definiert sind, d.h. Ausdruck der Form X = xИ 1 xИ 2. ... ... xИ л heißt elementare Konjunktion ... Die Anforderung, dass alle Variablen unterschiedlich sein müssen, wird durch Folgendes bedingt. Enthält die Konjunktion mehrere identische Literale, so ist es aufgrund der Kommutativität, Assoziativität und Idempotenz der Konjunktion möglich, auf eine äquivalente Formel überzugehen, nur ein Literal zu belassen (zB x 1 x 1 = x 1). Enthält die Konjunktion eine Variable und ihre Negation, dann entspricht die Formel der Konstanten 0, da x x = 0 und für jede Formel Y gilt Y x x = 0.

Eine Disjunktion mehrerer elementarer Konjunktionen heißt disjunktive Normalform , oder DNF ... Beispielsweise,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5.

Wenn die Zusammensetzung der Variablen in jeder Elementarkonjunktion einer gegebenen DNF gleich ist, dann heißt die DNF perfekt ... Das angegebene Beispiel ist DNF, was nicht perfekt ist. Im Gegenteil, die Formel

x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4

Es gibt eine perfekte Form.

Da in der Booleschen Algebra Addition und Multiplikation symmetrische Operationen sind und man Addition immer als Multiplikation und Multiplikation als Addition interpretieren kann, gibt es auch ein duales Konzept - konjunktive Normalform (CNF ), die eine Konjunktion elementarer Disjunktionen ist, und perfekte Konjunktivform (SKNF ). Aus dem Dualitätsprinzip für symmetrische Halbringe folgt, dass jede Aussage über DNF einer dualen Aussage über CNF entspricht, die man erhält, indem man Addition (Disjunktion) durch Multiplikation, Multiplikation (Konjunktion) durch Addition, Konstante 0 durch Konstante 1, Konstante 1 durch ersetzt Konstante 0, Ordnungsbeziehung durch duale (inverse) Ordnung. Daher werden wir uns weiterhin darauf konzentrieren, nur DNF zu studieren.

Satz 1.4. Jede andere boolesche Funktion als die Konstante 0 kann als SDNF dargestellt werden.

◀ Vereinbaren wir mit x σ eine Formel x für σ = 1 und eine Formel x für σ = 0. Die Funktion f (y 1,..., Yn) nehme den Wert 1 auf dem Vektor (t 1 ,..., Tn ) (ein solcher Vektor heißt Bestandteil der Einheit ). Dann nimmt die elementare Konjunktion auch auf dieser Menge den Wert 1 an, verschwindet aber auf allen anderen n-dimensionalen Booleschen Vektoren. Betrachten Sie die Formel

wobei sich die Summe (Union) auf alle diese Mengen (t 1,..., tn) von Werten der Argumente erstreckt, für die die gegebene Funktion den Wert 1 annimmt. Beachten Sie, dass die Menge solcher Mengen nicht leer ist. die Summe enthält also mindestens einen Term.

Es ist leicht zu erkennen, dass die Formel Φ für diejenigen und nur für diejenigen Werte der Variablen 1 wird, für die die betrachtete Funktion 1 wird. Daher repräsentiert die Formel Ψ die Funktion f.

Folgerung 1.1. Die Standardbasis ist fertig.

◀ Wenn eine Funktion keine Konstante 0 ist, kann sie in der Tat entweder in Form von SDNF dargestellt werden, einer Formel auf Standardbasis. Die Konstante 0 lässt sich beispielsweise durch die Formel f (x 1, x 2,..., X n) = x 1 x 1 darstellen.

Beispiel 1.2. Betrachten Sie eine Funktion von drei Variablen m (x 1, x 2, x 3) (Tabelle 1.4), genannt Mehrheitsfunktion . Diese Funktion wird zu 1 ausgewertet, wenn mehr als die Hälfte ihrer Argumente 1 sind. Daher wird sie oft als Abstimmungsfunktion bezeichnet. Lassen Sie uns dafür ein SDNF erstellen.

Die Vollständigkeit der Standardbasis ermöglicht die Auswahl weiterer kompletter Funktionssysteme. Die Vollständigkeit der Menge F kann aus den folgenden Überlegungen festgestellt werden. Angenommen, jede der drei Standard-Busis-Funktionen ist durch eine Formel über F darstellbar. Dann ist nach Satz 1.3 die Menge F vollständig.

Beispiel 1.3. Die Menge der Operationen der Addition mod 2, der Multiplikation und der Konstanten 1 heißt die Zhegalkin-Basis ... Modulo 2 Addition und Multiplikation sind Grundoperationen des Ringes Z2, die mit ihrer Hilfe zusammengesetzten Ausdrücke sind Polynome über den Ring Z2. Die Konstante 1 ist in diesem Fall erforderlich, um das freie Element zu schreiben. Da xx = x, haben alle Faktoren im Polynom den Grad 1. Daher kann man beim Schreiben eines Polynoms auf den Begriff des Grades verzichten. Beispiele für Formeln über der Zhegalkin-Basis:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Jede solche Formel wird Zhegalkin-Polynom genannt. Tatsächlich ist das Zhegalkin-Polynom ein Polynom über dem Ring Z2.

Es ist nicht schwer, Formeln über die Zhegalkin-Basis zu konstruieren, die die Operationen der Addition und Negation der Standardbasis darstellen (die Multiplikation der beiden Basen ist üblich):

x + y = x⊕y⊕xy, x = x⊕1.

Daher ist die Zhegalkin-Basis ein komplettes Set.
Es kann gezeigt werden, dass für jede Boolesche Funktion das Zhegalkin-Polynom eindeutig bestimmt ist

(genauer gesagt, bis zur Reihenfolge der Begriffe). Die Koeffizienten des Zhegalkin-Polynoms für eine kleine Anzahl von Variablen können mit der Methode der undefinierten Koeffizienten ermittelt werden.

Beispiel 1.4. Betrachten Sie einen Satz einer einzelnen Funktion, den Schaeffer-Strich *. Dieser Satz ist vollständig, was sich aus den folgenden leicht überprüfbaren Identitäten ergibt:

x = x | x, xy = x | y = (x | y) | (x | y), x + y = x | y = (x | x) | (y | y).

Beispiel 1.5. Auch die Basis bestehend aus einer einzigen Funktion, dem Pierce-Pfeil, ist komplett. Der Nachweis hierfür ist ähnlich wie beim Schaeffer-Hub. Dieser Schluss lässt sich aber auch auf Basis des Dualitätsprinzips für symmetrische Halbringe ziehen.

* Schaeffers Strich ist eine binäre, aber keine assoziative Operation. Daher sollten Sie bei der Verwendung des Infix-Formulars vorsichtig sein: Das Ergebnis hängt von der Reihenfolge ab, in der die Operationen ausgeführt werden. In diesem Fall empfiehlt es sich, die Reihenfolge der Operationen explizit in Klammern anzugeben, zum Beispiel write (x | y) | z, nicht x | y | z, obwohl beide Formen gleichwertig sind.

Die konjunktive Normalform eignet sich zum automatischen Beweisen von Theoremen. Jede boolesche Formel kann in CNF umgewandelt werden. Um dies zu tun, können Sie verwenden: das Gesetz der doppelten Negation, das Gesetz von de Morgan, die Distributivität.

College-YouTube

1 / 5

Formeln in KNF:

¬ A ∧ (B ∨ C), (\ displaystyle \ neg A \ Keil (B \ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\ displaystyle (A \ v B) \ Keil (\ neg B \ v C \ v \ neg D) \ Keil ( D \ vee \ neg E),) A ∧ B. (\ Displaystil A \ Keil B.)

Formeln nicht im CNF:

¬ (B ∨ C), (\ displaystyle \ neg (B \ vee C),) (A ∧ B) ∨ C, (\ displaystyle (A \ Keil B) \ vee C,) A (B ∨ (D ∧ E)). (\ Displaystil A \ Keil (B \ Vee (D \ Keil E)).)

Aber diese 3 Formeln nicht in CNF sind äquivalent zu den folgenden Formeln in CNF:

¬ B ∧ ¬ C, (\ displaystyle \ neg B \ Keil \ neg C,) (A ∨ C) ∧ (B ∨ C), (\ displaystyle (A \ v C) \ Keil (B \ v C),) A (B D) ∧ (B ∨ E). (\ Displaystil A \ Keil (B \ Vee D) \ Keil (B \ Vee E).)

Aufbau des CNF

Algorithmus zur Konstruktion von CNF

1) Beseitigen Sie alle in der Formel enthaltenen logischen Operationen und ersetzen Sie sie durch die wichtigsten: Konjunktion, Disjunktion, Negation. Dies kann mit äquivalenten Formeln erfolgen:

A → B = ¬ A ∨ B, (\ displaystyle A \ rightarrow B = \ neg A \ vee B,) A B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ Keil (A \ vee \ neg B).)

2) Ersetzen Sie das Negationszeichen, das sich auf den gesamten Ausdruck bezieht, durch die Negationszeichen, die sich auf einzelne Variablenaussagen beziehen, basierend auf den Formeln:

¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ displaystyle \ neg (A \ vee B) = \ neg A \ Keil \ neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B. (\ displaystyle \ neg (A \ Keil B) = \ neg A \ vee \ neg B.)

3) Befreien Sie sich von doppelten Verneinungszeichen.

4) Wenden Sie, falls erforderlich, auf die Verknüpfungs- und Disjunktionsoperationen die Eigenschaften der Distributivität und der Absorptionsformel an.

Ein Beispiel für den Bau eines CNF

Bringen wir die Formel zu CNF

F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ displaystyle F = (X \ rightarrow Y) \ Keil ((\ neg Y \ rightarrow Z) \ rightarrow \ neg X).)

Lass uns die Formel transformieren F (\ Anzeigestil F) zu einer Formel, die nicht enthält → (\ Anzeigestil \ Pfeil nach rechts):

F = (¬ X Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ Keil (\ neg (\ neg Y \ rightarrow Z) \ vee \ neg X) = (\ neg X \ vee Y) \ Keil (\ neg (\ neg \ neg Y \ vee Z) \ vee \ neg X).)

In der resultierenden Formel übertragen wir die Negation auf Variablen und reduzieren doppelte Negative:

F = (¬ X Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ Keil ((\ neg Y \ Keil \ neg Z) \ vee \ neg X).)

Die folgende Formel wird beispielsweise in 2-CNF geschrieben:

(A B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C). (\ displaystyle (A \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)

Normalform logische Formel enthält keine Zeichen der Implikation, Äquivalenz und Negation nicht-elementarer Formeln.

Die Normalform gibt es in zwei Formen:

konjunktive Normalform (CNF)- Konjunktion mehrerer Disjunktionen, zB $ \ left (A \ vee \ overline (B) \ vee C \ right) \ Keil \ left (A \ vee C \ right) $;

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

SKNF

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

enthält keine identischen elementaren Disjunktionen;

keine der Klauseln enthält dieselben Variablen;

jede elementare Disjunktion enthält jede Variable aus der gegebenen KNF.

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

Regeln für die Konstruktion von SKNF nach der Wahrheitstabelle

Für jeden Variablensatz, für den die Funktion 0 ist, wird die Summe geschrieben, und die Variablen mit dem Wert 1 werden negiert.

SDNF

Perfekte Disjunktive Normalform (SDNF) ist ein DNF, der drei Bedingungen erfüllt:

enthält keine identischen elementaren Konjunktionen;

keine der Konjunktionen enthält dieselben Variablen;

jede elementare Konjunktion enthält jede Variable aus dem gegebenen DNF, außerdem in der gleichen Reihenfolge.

Jede Boolesche Formel, die nicht identisch falsch ist, kann im SDNF außerdem auf einzigartige Weise dargestellt werden.

Regeln für die Konstruktion von SDNF nach der Wahrheitstabelle

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

Beispiele für das Finden von SKNF und SDNF

Beispiel 1

Schreiben Sie eine logische Funktion gemäß ihrer Wahrheitstabelle:

Bild 1.

Lösung:

Lassen Sie uns die Regel zum Konstruieren von SDNF verwenden:

Figur 2.

Wir erhalten SDNF:

Lassen Sie uns die Regel zum Konstruieren von SKNF verwenden.

Einfache Disjunktion(inklusive Disjunktion) oder disjunkt(engl. disjunct) ist eine Disjunktion von einer oder mehreren Variablen oder deren Negationen, und jede Variable kommt nicht mehr als einmal vor.

Einfache Disjunktion

Komplett wenn jede Variable (oder ihre Negation) genau einmal darin vorkommt;
eintönig wenn es keine negativen Variablen enthält.

Konjunktive Normalform, CNF(engl. konjunktive Normalform, CNF) Normalform, bei der eine Boolesche Funktion die Form einer Konjunktion mehrerer einfacher Klauseln hat.

CNF-Beispiel:$ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $

SKNF

Perfekte konjunktive Normalform, SKNF(Perfekte konjunktive Normalform, PCNF) ist ein CNF, das die folgenden Bedingungen erfüllt:

es hat nicht die gleichen einfachen Disjunktionen
jede einfache Disjunktion ist vollständig

SKNF-Beispiel:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

Satz: Für jede boolesche Funktion $ f (\ vec (x)) $, die nicht gleich der Identität ist, gibt es eine SKNF, die sie definiert.

Nachweisen: Da die Inverse der Funktion $ \ neg (f) (\ vec x) $ auf den Tupeln gleich eins ist, auf denen $ f (\ vec x) $ gleich null ist, dann ist die SDNF für $ \ neg (f) (\ vec x) $ kann wie folgt geschrieben werden:

$ \ neg (f) (\ vec x) = \ bigvee \ limit_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ Keil x_ (2) ^ (\ sigma_ (2)) \ Keil ... \ Keil x_ (n) ^ (\ sigma_ (n ))) $, wobei $ \ sigma_ (i) $ das Vorhandensein oder Fehlen einer Negation für $ x_ (i) $ . bezeichnet

Lassen Sie uns die Umkehrung der linken und rechten Seite des Ausdrucks finden:

$ f (\ vec x) = \ neg ((\ bigvee \ limit_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ Keil x_ (2) ^ (\ sigma_ (2)) \ Keil ... \ Keil x_ (n) ^ (\ sigma_ (n ))))) $

Wenden wir die de Morgansche Regel zweimal auf den auf der rechten Seite erhaltenen Ausdruck an, erhalten wir: $ f (\ vec x) = \ bigwedge \ limits_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ dots, x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ dots \ vee \ neg (x_n ^ (\ sigma_n)) ) $

Der letzte Ausdruck ist SKNF. Da die SKNF aus der SDNF erhalten wird, die für jede Funktion konstruiert werden kann, die nicht identisch Null ist, ist der Satz bewiesen.

Algorithmus zur Konstruktion von SKNF nach der Wahrheitstabelle

In der Wahrheitstabelle markieren wir diejenigen Variablenmengen, bei denen der Wert der Funktion gleich $ 0 $ ist.
Für jede markierte Menge schreiben wir die Disjunktion aller Variablen nach folgender Regel: Wenn der Wert einer Variablen $ 0 $ ist, dann nehmen wir die Variable selbst in die Disjunktion auf, andernfalls ihre Negation.
Wir verbinden alle resultierenden Disjunktionen durch Konjunktionsoperationen.

Ein Beispiel für die Konstruktion von SKNF für den Median

eins). In der Wahrheitstabelle markieren wir diejenigen Variablenmengen, bei denen der Wert der Funktion gleich $ 0 $ ist.

x	ja	z	$ \ langle x, y, z \ rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2). Für jede markierte Menge schreiben wir die Konjunktion aller Variablen nach folgender Regel: Wenn der Wert einer Variablen $ 0 $ ist, dann schließen wir die Variable selbst in die Disjunktion ein, andernfalls ihre Negation.

x	ja	z	$ \ langle x, y, z \ rangle $
0	0	0	0	$ (x \ lor y \ lor z) $
0	0	1	0	$ (x \ lor y \ lor \ neg (z)) $
0	1	0	0	$ (x \ lor \ neg (y) \ lor z) $
0	1	1	1
1	0	0	0	$ (\ neg (x) \ lor y \ lor z) $
1	0	1	1
1	1	0	1
1	1	1	1

3). Wir verbinden alle resultierenden Disjunktionen durch Konjunktionsoperationen.

$ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

SKNF-Beispiele für einige Funktionen

Pierce's Arrow: $ x \ downarrow y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) $

Exklusives oder: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $

Beispiel. CNF-Formeln finden

~ ~

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

1. = 1.des DNF-Algorithmus

2. = 2.des DNF-Algorithmus

3. = 3.DNF-Algorithmus

4. = 4. des DNF-Algorithmus

5. Lassen Sie die identisch falschen Terme weg, d. h. Terme der Form

6. Verbleibende Terme mit fehlenden Variablen ergänzen

7. Wiederholen Sie Schritt 4.

Beispiel. Finden Sie SDNF-Formeln.

Um den SKNF zu konstruieren, können Sie das folgende Schema verwenden:

Beispiel. Finden Sie SDNF-Formeln.

Es ist bekannt (Theoreme 2.11, 2.12), dass SDNF und SKNF durch die Formel eindeutig bestimmt sind und daher aus der Wahrheitstabelle der Formel konstruiert werden können.

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

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

2.2. Die Aufgabe.

2.2.1 Unten sind die logischen Ausdrücke. Vereinfachen Sie die Ausdrücke Ihrer Variante so weit wie möglich, indem Sie die Booleschen Gesetze der Logik verwenden. Verwenden Sie dann Wahrheitstabellen, um Ihren vereinfachten Ausdruck mit dem Original zu vergleichen.

2.2.2. Klären Sie die Frage der Äquivalenz von f 1 und f 2, indem Sie sie auf SDNF reduzieren (Tabelle 1).

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

№	f 1	f 2	f 3

2.3. Testfragen.

2.3.1. Geben Sie die Definition der Aussage an.

2.3.2. Listen Sie die grundlegenden Operationen der Äußerung 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 mit äquivalenten Transformationen die gleiche Wahrheit der Formeln:

2.3.7. Finden Sie duale Formeln:

)

2.3.8. Bringen Sie die folgenden Formeln in die perfekte DNF (SDNF)-Form:

2.3.9. Bringen Sie die folgenden Formeln in die perfekte CNF (SKNF) Form:

Laborarbeit Nr. 3

Thema:„Minimierung boolescher Funktionen. Logik"

Ziel: Erwerb praktischer Fähigkeiten im Umgang mit Methoden zur Minimierung boolescher Funktionen.

3.1. Theoretische Informationen.

Minimalformen

Wie in gezeigt, ist jede boolesche Funktion in perfekter Normalform (Disjunktiv oder Konjunktiv) darstellbar. Darüber hinaus ist eine solche Darstellung der erste Schritt beim Übergang von der Tabellendefinition einer Funktion zu ihrem analytischen Ausdruck. Im Folgenden gehen wir von der disjunktiven Form aus, und die entsprechenden Ergebnisse für die konjunktive Form ergeben sich aufgrund des Dualitätsprinzips.

Das kanonische Problem der Synthese von Logikschaltungen auf Boolescher Basis wird auf die Minimierung von Booleschen Funktionen reduziert, d.h. sie in disjunktiver Normalform darzustellen, die die kleinste Anzahl von Buchstaben enthält (Variablen und ihre Negationen). Solche Formen werden minimal genannt. Bei der kanonischen Synthese wird davon ausgegangen, dass sowohl Signale als auch deren Inversionen den Eingängen der Schaltung zugeführt werden.

Die in disjunktiver Normalform dargestellte Formel wird durch Mehrfachanwendungen des Klebevorgangs und des Absorptionsvorgangs und vereinfacht (Doppelidentitäten für die konjunktive Normalform haben die Form: und). Hier und kann als jede Formel der Booleschen Algebra verstanden werden. Als Ergebnis kommen wir zu einem solchen analytischen Ausdruck, wenn weitere Transformationen bereits unmöglich sind, d.h. Wir bekommen eine Sackgassenform.

Unter den Sackgassenformen befindet sich die minimale disjunktive Form, die möglicherweise nicht eindeutig ist. Um sicherzustellen, dass eine bestimmte Sackgassenform minimal ist, ist es notwendig, alle Sackgassenformen zu finden und sie nach der Anzahl der darin enthaltenen Buchstaben zu vergleichen.

Zum Beispiel sei die Funktion in perfekt normaler disjunktiver Form gegeben:

Das Gruppieren der Mitglieder und das Anwenden des Klebevorgangs haben wir.

Mit einer anderen Gruppierungsmethode erhalten wir:

Beide Sackgassenformen sind nicht minimal. Um die minimale Form zu erhalten, müssen Sie erraten, um einen Begriff in der ursprünglichen Formel zu wiederholen (dies ist immer möglich). Im ersten Fall kann ein solches Mitglied sein. Dann . Durch das Hinzufügen eines Mitglieds erhalten wir:. Nachdem Sie alle möglichen Optionen durchgegangen sind, können Sie sicherstellen, dass die letzten beiden Formen minimal sind.

Auf dieser Ebene mit Formeln zu arbeiten ist wie im Dunkeln zu tappen. Der Prozess des Findens von Minimalformen wird visueller und zielgerichteter, wenn Sie einige grafische und analytische Darstellungen und Symbole verwenden, die speziell für diesen Zweck entwickelt wurden.

Mehrdimensionaler Würfel

Jeder Scheitelpunkt des -dimensionalen Würfels kann dem Bestandteil der Einheit zugeordnet werden. Folglich ist die Teilmenge der markierten Knoten eine Abbildung auf den -dimensionalen Würfel einer Booleschen Funktion von Variablen in perfekter disjunktiver Normalform. In Abb. 3.1 zeigt eine solche Abbildung für die Funktion aus Abschnitt 3.7.

Abbildung 3.1 Darstellung der in SDNF . dargestellten Funktion auf einem dreidimensionalen Würfel

Um eine Funktion von Variablen darzustellen, die in einer beliebigen disjunktiven Normalform dargestellt werden, ist es notwendig, eine Entsprechung zwischen ihren Minitermen und den Elementen des -dimensionalen Würfels herzustellen.

Minitherm vom (-1)-ten Rang kann als Ergebnis der Verklebung von zwei Minitermen vom -ten Rang (Bestandteil der Einheit) betrachtet werden, d.h. Auf einem -dimensionalen Würfel entspricht dies dem Ersetzen von zwei Scheitelpunkten, die sich nur in den Werten der Koordinaten unterscheiden, die diese Scheitelpunkte durch eine Kante verbinden (die Kante soll die einfallenden Scheitelpunkte überdecken). Somit entsprechen Miniterme der (-1)-ten Ordnung den Kanten des -dimensionalen Würfels. In ähnlicher Weise wird die Entsprechung von Minitermen der (-2)-ten Ordnung zu den Flächen des -dimensionalen Würfels hergestellt, von denen jede vier Ecken (und vier Kanten) bedeckt.

Elemente eines -dimensionalen Würfels, die durch Dimensionen gekennzeichnet sind, werden -Würfel genannt. Scheitelpunkte sind also 0-Würfel, Kanten sind 1-Würfel, Flächen sind 2-Würfel usw. Zusammenfassend können wir davon ausgehen, dass der Miniterm des () -ten Rangs in der disjunktiven Normalform für die Funktion von Variablen durch einen -Würfel dargestellt wird und jeder -Würfel alle jene -Würfel der niedrigsten Dimension abdeckt, die mit seinen Scheitelpunkten verbunden. Als Beispiel ist Abb. 3.2 ist die Abbildung der Funktion von drei Variablen gegeben. Hier entsprechen Miniterms und 1-cubes() und Miniterms werden von 2-cubes() angezeigt.

Abbildung 3.2 Funktionsumfang

Jede disjunktive Normalform wird also auf dem -dimensionalen Würfel durch eine Menge von -Würfeln dargestellt, die alle Knoten abdecken, die den Bestandteilen der Einheit (0-Würfel) entsprechen. Das Umgekehrte gilt auch: Wenn eine Sammlung von -Würfeln die Menge aller Knoten abdeckt, die den Einheitswerten der Funktion entsprechen, dann ist die Disjunktion der diesen -Würfeln entsprechenden Miniterme der Ausdruck dieser Funktion in disjunktiver Normalform . Man sagt, dass eine solche Sammlung von -Würfeln (oder den entsprechenden Miniterms) die Abdeckung einer Funktion bildet.

Das Streben nach der Minimalform wird intuitiv als Suche nach einer solchen Hülle verstanden, deren Anzahl -Würfel kleiner und deren Dimension größer wäre. Die der minimalen Form entsprechende Abdeckung wird als minimale Abdeckung bezeichnet. Zum Beispiel für die Funktionsüberdeckung in Abb. 3.3 entspricht minimalen Formen und .

Reis. 3.3 Funktionsabdeckungen.

links – ; rechts –

Das Anzeigen einer Funktion auf einem -dimensionalen Würfel ist klar und einfach für. Ein vierdimensionaler Würfel kann wie in Abb. 3.4, wobei die Funktion von vier Variablen und ihre minimale Überdeckung entsprechend dem Ausdruck ... Die Anwendung dieses Verfahrens erfordert so komplexe Konstruktionen, dass alle seine Vorteile verloren gehen.

Reis. 3.4 Funktionsanzeige auf einem vierdimensionalen Würfel

Karnaugh-Karten

Eine andere Methode zur grafischen Darstellung von booleschen Funktionen verwendet Karnot-Karten, die speziell organisierte Nachschlagetabellen sind. 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 jede nachfolgende von der vorherigen durch den Wert nur einer der Variablen unterscheidet . Aus diesem Grund unterscheiden sich sowohl horizontal als auch vertikal benachbarte Zellen der Tabelle nur im Wert einer Variablen. Zellen, die sich an den Rändern der Tabelle befinden, werden ebenfalls als benachbart betrachtet und haben diese Eigenschaft. In Abb. 3.5 zeigt Karnaugh-Diagramme für zwei, drei, vier Variablen.

Reis. 3.5 Karnot-Maps 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 aufgefüllt (Nullen passen normalerweise nicht, sie entsprechen leeren Zellen). Zum Beispiel in Abb. 3.6, aber zeigt die Karnot-Abbildung für die Funktion, deren Abbildung auf den vierdimensionalen Würfel in Abb. 3.4. Der Einfachheit halber werden die Zeilen und Spalten, die den Werten von 1 für eine Variable entsprechen, in geschweifte Klammern mit der Bezeichnung dieser Variablen eingeschlossen.

Reis. 3.6 Anzeigen einer Funktion von vier Variablen in einem Karnot-Diagramm

(a) und seine Mindestdeckung (b)

Zwischen Funktionszuordnungen an n-dimensionaler Würfel und auf der Karnot-Karte gibt es eine Eins-zu-Eins-Entsprechung. Auf der Karnot-Karte S-cube entspricht einer Sammlung von 2 benachbarten Zellen, die sich in einer Reihe, Spalte, einem Quadrat oder einem Rechteck befinden (unter Berücksichtigung der Nähe der gegenüberliegenden Kanten der Karte). Daher gelten alle oben genannten Bestimmungen (siehe S. mehrdimensionaler Würfel) gelten für Karnot-Karten. Also, in Abb. 3.6, B die Abdeckung von Karteneinheiten entsprechend der minimalen disjunktiven Form wird angezeigt die betrachtete Funktion.

Das Auslesen von Miniterms von der Karnot-Karte erfolgt nach einer einfachen Regel. Zellen, die sich bilden S-Würfel, gib Miniter (n – s)-ter Rang, der die einschließt (n – s) Variablen, die auf diesem die gleichen Werte speichern S-cube, wobei der Wert 1 den Variablen selbst entspricht und die Werte 0 ihren Negationen entsprechen. Variablen, die ihre Werte nicht speichern für S-Würfel, im Miniterm fehlen. Unterschiedliche Lesarten führen zu unterschiedlichen Darstellungen der Funktion in disjunktiver Normalform (die ganz rechte ist minimal) (Abb. 3.7).

Die Verwendung von Karnaugh-Maps erfordert einfachere Konstruktionen als das Mapping auf n-dimensionaler Würfel, insbesondere bei vier Variablen. Um Funktionen von fünf Variablen darzustellen, werden zwei Karnot-Maps für vier Variablen verwendet, und für eine Funktion von sechs Variablen werden vier solcher Maps verwendet. Mit einer weiteren Zunahme der Variablenanzahl werden Karnot-Karten praktisch unbrauchbar.

In der Literatur bekannt Weich-Karten unterscheiden sich nur in einer anderen Reihenfolge der Wertemengen von Variablen und haben die gleichen Eigenschaften wie Karnot-Maps.

Komplex aus Würfeln

Die Inkonsistenz grafischer Methoden mit einer Vielzahl von Variablen wird durch verschiedene analytische Methoden zur Darstellung boolescher Funktionen kompensiert. Eine dieser Darstellungen ist Komplex von Würfeln unter Verwendung der Terminologie des mehrdimensionalen logischen Raums in Kombination mit speziell entworfener Symbologie.

). 0-Würfel, die den Bestandteilen von einem entsprechen, werden durch Wertemengen von Variablen dargestellt, bei denen die Funktion gleich eins ist. Offensichtlich im Protokoll

Reis. 3.8 Würfelkomplex einer Funktion von drei Variablen ( aber) und seine symbolische Darstellung ( B)

Der Komplex der Würfel bildet maximale Funktionsabdeckung... Ausgenommen davon all die S-Würfel, die von Würfeln der höchsten Dimension bedeckt sind, erhalten wir Hüllen, die Sackgassenformen entsprechen. Für das betrachtete Beispiel (Abb. 3.8) haben wir also eine Sackgassenabdeckung

was der Funktion entspricht ... In diesem Fall ist diese Abdeckung ebenfalls minimal.

Für zwei Boolesche Funktionen entspricht die Disjunktionsoperation der Vereinigung ihrer Würfelkomplexe und die Konjunktionsoperation entspricht der Schnittmenge von Würfelkomplexen. Die Negation einer Funktion entspricht dem Komplement eines Würfelkomplexes, wird also durch alle Ecken 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 klar, aber ihre wichtigsten Vorteile sind, dass sie die Beschränkung der Anzahl der Variablen aufhebt und die Verschlüsselung von Informationen bei der Verwendung von Computern erleichtert.

Minimieren von Booleschen Funktionen

Formulierung des Problems. Das Minimieren einer Schaltung in einer Booleschen Basis reduziert sich auf das Finden der minimalen disjunktiven Form, die der minimalen Abdeckung entspricht. Die Gesamtzahl der Briefe in der Normalform wird durch den Preis des Umschlags ausgedrückt , wobei die Anzahl der - Würfel ist, die eine Abdeckung der gegebenen Funktion in n Variablen bilden. Die Mindestdeckung ist durch den niedrigsten Wert ihres Preises gekennzeichnet.

Üblicherweise wird das Minimierungsproblem in zwei Schritten gelöst. Zuerst suchen wir nach einem reduzierten Coverage, das alle -Cubes der maximalen Dimension enthält, aber keinen Cube enthält, der von einem Cube dieses Coverages abgedeckt wird. Die entsprechende disjunktive Normalform heißt abgekürzt und ihre Miniterme werden einfache Implikanten genannt. Für diese Funktion ist die Schnittabdeckung die einzige, die jedoch überflüssig sein kann, da einige der Cubes von Sammlungen anderer Cubes abgedeckt werden.

Im zweiten Schritt erfolgt der Übergang von reduzierten zu disjunktiven Normalformen am Ende, aus denen die Minimalformen ausgewählt werden. Sackgassenformen werden gebildet, indem alle redundanten Würfel aus der abgekürzten Abdeckung ausgeschlossen werden, ohne die die verbleibende Menge von Würfeln immer noch eine Abdeckung der gegebenen Funktion bildet, aber bei weiterem Ausschluss eines der Würfel nicht mehr die Mengen von alle Scheitelpunkte, die den Einheitswerten der Funktion entsprechen, dh es hört auf, eine Abdeckung zu sein ...

Ein Cube mit reduzierter Abdeckung, der die Scheitel dieser Funktion abdeckt, die nicht von anderen Cubes abgedeckt werden, kann nicht redundant sein und wird immer in die minimale Abdeckung eingeschlossen. Ein solcher Würfel wird wie der entsprechende Implikant als Extremal (wesentlicher Implikant) bezeichnet, und die von ihm bedeckten Scheitel werden als gelöschte Scheitel bezeichnet. Die Menge der Extremale bildet den Kern der Überdeckung, es ist klar, dass beim Übergang von einer reduzierten zu einer minimalen Überdeckung zunächst alle Extremale unterschieden werden sollten. Wenn die Extremalmenge keine Überdeckung bildet, wird sie durch Würfel aus der reduzierten Überdeckung ergänzt.

Diese Definitionen sind in Abb. 3.9, wobei die reduzierte Abdeckung (siehe Abb.3.9a, ) und die Mindestdeckung (Abb. 3.9b) und (siehe Abb. 3.9, b) werden wie folgt ausgedrückt.