Beispiel. Finden Sie CNF-Formeln

~ ~

Die perfekte disjunktive Normalform des 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. Vervollständigen Sie die restlichen Terme mit den fehlenden Variablen

7. Wiederholen Sie Punkt 4.

Beispiel. Finden Sie SDNF-Formeln.

~

Um den SCNF zu erstellen, können Sie das folgende Schema verwenden:

Beispiel. Finden Sie SDNF-Formeln.

~

Es ist bekannt (Theoreme 2.11, 2.12), dass SDNF und SCNF durch die Formel eindeutig definiert sind und daher unter Verwendung der Wahrheitstabelle der Formel konstruiert werden können.

Das Schema zur Konstruktion von SDNF und SCNF 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 sind die booleschen Ausdrücke aufgeführt. Vereinfachen Sie die Ausdrücke Ihrer Variante mithilfe der Booleschen Gesetze der Logik so weit wie möglich. 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 Dualfunktion für f 3 mithilfe des verallgemeinerten und booleschen Prinzips (Tabelle 1). Vergleichen Sie die Ergebnisse.

№	f 1	f 2	f 3

2.3. Kontrollfragen.

2.3.1. Definieren Sie eine Aussage.

2.3.2. Listen Sie die Hauptoperationen einer 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 mithilfe ä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. Reduzieren Sie die folgenden Formeln auf die perfekte CNF-Form (SCNF):

~

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.

Minimale Formen

Wie in gezeigt wurde, 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 Spezifikation einer Funktion zu ihrem analytischen Ausdruck. Im Folgenden gehen wir von der disjunktiven Form aus und erhalten auf Basis des Dualitätsprinzips die entsprechenden Ergebnisse für die konjunktive Form.

Das kanonische Problem der Synthese logischer Schaltkreise auf boolescher Basis besteht darin, boolesche Funktionen zu minimieren, 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 Verwendung der Klebeoperation und der Absorptionsoperation und vereinfacht (die dualen Identitäten für die konjunktive Normalform haben die Form: und). Hier kann jede boolesche Algebraformel verstanden werden. Dadurch gelangen wir zu einem analytischen Ausdruck, bei dem 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 ein bestimmtes Dead-End-Formular minimal ist, müssen Sie alle Dead-End-Formulare 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 Begriffe gruppieren und den Klebevorgang anwenden, erhalten wir .

Mit einer anderen Gruppierungsmethode erhalten wir:

Beide Sackgassenformen sind nicht minimal. Um die Minimalform zu erhalten, müssen Sie raten, einen Term in der Originalformel zu wiederholen (dies ist immer möglich, da ). Im ersten Fall kann ein solches Mitglied sein. Dann . Durch Hinzufügen des Begriffs 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 der Suche nach Minimalformen wird visueller und zielgerichteter, wenn Sie einige speziell für diesen Zweck entwickelte grafische und analytische Darstellungen und Symbole verwenden.

Mehrdimensionaler Würfel

Jeder Scheitelpunkt eines -dimensionalen Würfels kann einem Bestandteil einer Einheit zugeordnet werden. Folglich ist die Teilmenge der markierten Eckpunkte eine Abbildung einer booleschen Funktion von Variablen in perfekter disjunktiver Normalform auf den -dimensionalen Würfel. In 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 beliebigen disjunktiven Normalform anzuzeigen, muss eine Entsprechung zwischen ihren Minitermen und den Elementen des -dimensionalen Würfels hergestellt werden.

Ein Miniterm mit dem Rang (-1) kann als Ergebnis des Zusammenklebens zweier Miniterme mit dem Rang (Konstituent der Einheit) betrachtet werden, d. h. , Auf einem -dimensionalen Würfel entspricht dies dem Ersetzen zweier Scheitelpunkte, die sich nur in den Werten der Koordinaten unterscheiden, die diese Scheitelpunkte mit einer Kante verbinden (die Kante soll die mit ihr inzidenten Scheitelpunkte abdecken). Somit entsprechen die Miniterme (-1)-ter Ordnung den Kanten des -dimensionalen Würfels. In ähnlicher Weise wird die Entsprechung von Minitermen der (-2)-ten Ordnung mit den Flächen eines -dimensionalen Würfels hergestellt, 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 usw. Wenn wir die obige Argumentation verallgemeinern, können wir annehmen, dass ein Miniterm ()-ten Ranges in disjunktiver Normalform für eine Funktion von Variablen durch einen -Würfel dargestellt wird und jeder -Würfel alle -Würfel niedrigerer Dimension abdeckt, die seinen Eckpunkten zugeordnet sind . Als Beispiel in Abb. 3.2 zeigt eine Funktion von drei Variablen. Hier entsprechen die Miniterme einem 1-Würfel (), und der Miniterm wird durch einen 2-Würfel () dargestellt.

Abb.3.2 Funktionsabdeckung

Jede disjunktive Normalform wird also auf einen -dimensionalen Würfel durch eine Menge von -Würfeln abgebildet, die alle Eckpunkte abdecken, die den Konstituenten der Einheit entsprechen (0-Würfel). Auch die umgekehrte Aussage gilt: Wenn eine bestimmte Menge 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 im disjunktiven Normal bilden. Eine solche Sammlung von -Würfeln (oder ihren entsprechenden Minitermen) soll eine Abdeckung einer Funktion bilden.

Der Wunsch nach einer minimalen Form wird intuitiv als Suche nach einer solchen Hülle verstanden, deren Anzahl an Würfeln kleiner und deren Dimension größer wäre. Die der Mindestform entsprechende Deckung wird als Mindestdeckung bezeichnet. Beispielsweise für die Abdeckfunktion in Abb. 3.3 erfüllt 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. dargestellt dargestellt werden. 3.4, das eine Funktion von vier Variablen und ihre dem Ausdruck entsprechende Mindestabdeckung zeigt . Die Verwendung dieser Methode erfordert so komplexe Konstruktionen, dass alle Vorteile verloren gehen.

Reis. 3.4 Funktionsanzeige auf einem vierdimensionalen Würfel

Carnot-Karten

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

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

Wie in gewöhnlichen Wahrheitstabellen werden die Zellen der Mengen, in 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 eine Karnaugh-Karte für eine Funktion, deren Darstellung auf einem vierdimensionalen Würfel in Abb. gegeben ist. 3.4. Zur Vereinfachung werden Zeilen und Spalten, die den Werten 1 für eine Variable entsprechen, mit einer geschweiften Klammer hervorgehoben, die diese Variable angibt.

Reis. 3.6 Darstellung einer Funktion von vier Variablen auf einer Carnaugh-Karte

(a) und seine Mindestdeckung (b)

Zwischen Funktionszuordnungen zu N-dimensionalen Würfel und der Carnot-Karte besteht eine Eins-zu-eins-Entsprechung. Auf der Carnot-Karte S-Ein Würfel entspricht einer Menge von zwei 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 Karnaugh-Karten. Also, in Abb. 3,6, B zeigt die Abdeckung von Karteneinheiten, die der minimalen disjunktiven Form entsprechen die jeweilige Funktion.

Das Lesen von Miniterms aus einer Karnaugh-Karte folgt einer einfachen Regel. Es bilden sich Zellen S-Würfel, gib Miniter (n–s)-ter 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-cube, fehlen im Miniterm. Unterschiedliche Lesarten führen zu unterschiedlichen Darstellungen der Funktion in disjunktiver Normalform (die Darstellung ganz rechts ist minimal) (Abbildung 3.7).

Die Verwendung von Karnaugh-Karten erfordert im Vergleich zur Kartierung auf einfachere Konstruktionen N-dimensionaler Würfel, insbesondere im Fall von vier Variablen. Um Funktionen von fünf Variablen anzuzeigen, werden zwei Karnaugh-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 Karnaugh-Karten praktisch unbrauchbar.

Berühmt in der Literatur Veitch-Karten Sie unterscheiden sich lediglich in der unterschiedlichen Reihenfolge der Mengen der Variablenwerte und haben die gleichen Eigenschaften wie Karnaugh-Karten.

Komplex aus Würfeln

Die Inkonsistenz grafischer Methoden bei einer großen Anzahl von Variablen wird durch verschiedene analytische Methoden zur Darstellung boolescher Funktionen ausgeglichen. Eine solche Darstellung ist Komplex aus Würfeln, unter Verwendung der Terminologie eines mehrdimensionalen logischen Raums in Kombination mit einer speziell entwickelten Symbolik.

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

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

Der Würfelkomplex entsteht maximale Funktionsabdeckung. Das alles davon ausgenommen 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 . In diesem Fall ist diese Deckung minimal.

Für zwei boolesche Funktionen entspricht die Disjunktionsoperation der Vereinigung ihrer Würfelkomplexe und die Konjunktionsoperation der Schnittmenge ihrer Würfelkomplexe. Die Negation einer Funktion entspricht dem Komplement 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 Kodierung von Informationen bei der Verwendung von Computern erleichtert wird.

Boolesche Funktionen minimieren

Formulierung des Problems. Bei der Minimierung eines Schaltkreises auf boolescher Basis kommt es darauf an, die minimale disjunktive Form zu finden, die der minimalen Abdeckung entspricht. Die Gesamtzahl der in der Normalform enthaltenen Briefe wird durch die Deckungskosten ausgedrückt , wobei die Anzahl der Würfel ist, die eine Abdeckung einer gegebenen Funktion von n Variablen bilden. Die Mindestdeckung zeichnet sich durch den niedrigsten Wert ihres Preises aus.

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

Im zweiten Schritt erfolgt ein Übergang von reduzierten zu 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 an Würfeln immer noch eine Abdeckung einer gegebenen Funktion bildet, aber mit weiterem Ausschluss eines der Würfel deckt sie nicht mehr die Menge aller ab Eckpunkte, die einzelnen Werten der Funktion entsprechen, d. h. es ist 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 wird wie sein entsprechender Implikant Extremal (essentieller Implikant) genannt, und die Eckpunkte, die er abdeckt, werden gelöschte Eckpunkte genannt. Die Menge der Extremale bildet den Kern der Bedeckung; es ist klar, dass beim Übergang von einer reduzierten zu einer minimalen Bedeckung zunächst alle Extremale isoliert werden sollten. Wenn die Menge der Extremale keine Überdeckung bildet, wird sie durch Würfel aus der reduzierten Überdeckung zur Überdeckung ergänzt.

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

Definition 1.Konjunktivmonomial (Elementarkonjunktion) von Variablen ist die Konjunktion dieser Variablen oder ihrer Negationen.

Zum Beispiel ist eine Elementarkonjunktion.

Definition 2.Disjunktives Monom (Elementardisjunktion) von Variablen ist die Disjunktion dieser Variablen oder ihrer Negationen.

Zum Beispiel ist eine elementare Disjunktion.

Definition 3. Eine Formel, die einer gegebenen Formel der Aussagenalgebra äquivalent ist und eine Disjunktion elementarer konjunktiver Monome ist, heißt disjunktive Normalform(DNF) dieser Formel.

Zum Beispiel,– DNF.

Definition 4. Eine Formel, die einer gegebenen Formel der Aussagenalgebra äquivalent ist und eine Konjunktion elementarer disjunktiver Monome ist, heißt konjunktive Normalform(CNF) dieser Formel.

Zum Beispiel, – KNF.

Für jede Aussagenalgebraformel kann man einen Satz disjunktiver und konjunktiver Normalformen finden.

Algorithmus zur Konstruktion von Normalformen

Ersetzen Sie mithilfe der Äquivalenzen der logischen Algebra alle Grundoperationen in der Formel: Konjunktion, Disjunktion, Negation:

Beseitigen Sie doppelte Negative.

Wenden Sie bei Bedarf die Eigenschaften der Distributivitäts- und Absorptionsformeln auf die Operationen der Konjunktion und Disjunktion an.

2.6. Perfekte disjunktive und perfekte konjunktive Normalformen

Jede boolesche Funktion kann viele Darstellungen in Form von DNF und CNF haben. Eine besondere Stellung unter diesen Darstellungen nehmen perfektes DNF (SDNF) und perfektes CNF (SCNF) ein.

Definition 1. Perfekte disjunktive Normalform(SDNF) ist eine DNF, in der jedes konjunktive Monom jede Variable aus der Menge genau einmal enthält, entweder sich selbst oder ihre Negation.

Strukturell kann die SDNF für jede auf eine DNF reduzierte Formel der Aussagenalgebra wie folgt definiert werden:

Definition 2. Perfekte disjunktive Normalform(SDNF) einer Aussagenalgebraformel wird als DNF bezeichnet und hat die folgenden Eigenschaften:

Definition 3. Perfekte konjunktive Normalform(SCNF) ist ein CNF, in dem jedes disjunktive Monom jede Variable aus der Menge genau einmal enthält und entweder sich selbst oder seine Negation vorkommt.

Strukturell kann die SCNF für jede auf die CNF reduzierte Formel der Aussagenalgebra wie folgt definiert werden.

Definition 4. Perfekte konjunktive Normalform(SCNF) einer gegebenen Formel der Aussagenalgebra wird als CNF bezeichnet, die die folgenden Eigenschaften erfüllt.

Satz 1. Jede boolesche Funktion von Variablen, die nicht identisch falsch ist, kann in SDNF auf einzigartige Weise dargestellt werden.

Methoden zum Auffinden von SDNF

1. Methode

2. Methode

Wählen Sie die Zeilen aus, in denen die Formel den Wert 1 annimmt.

Wir erstellen eine Disjunktion von Konjunktionen unter der Bedingung, dass wir, wenn eine Variable mit einem Wert von 1 in der Konjunktion enthalten ist, diese Variable aufschreiben, wenn sie einen Wert von 0 hat, dann ihre Negation. Wir bekommen SDNF.

Satz 2. Jede boolesche Funktion von Variablen, die nicht identisch wahr ist, kann in SCNF auf einzigartige Weise dargestellt werden.

Methoden zum Auffinden von SCNF

1. Methode– unter Verwendung äquivalenter Transformationen:

2. Methode– Verwendung von Wahrheitstabellen:

Wählen Sie die Zeilen aus, in denen die Formel den Wert 0 annimmt.

Wir bilden eine Konjunktion von Disjunktionen unter der Bedingung, dass, wenn eine Variable mit einem Wert von 0 in der Disjunktion enthalten ist, wir diese Variable aufschreiben, wenn sie einen Wert von 1 hat, dann ihre Negation. Wir bekommen SKNF.

Beispiel 1. Konstruieren Sie CNF-Funktionen.

Lösung

Beseitigen wir das Konnektiv „“ mithilfe der Gesetze der Variablentransformation:

= /de Morgans Gesetze und doppelte Negation/ =

/Verteilungsgesetze/ =

Beispiel 2. Geben Sie DNF die Formel.

Lösung

Lassen Sie uns logische Operationen mit und ausdrücken:

= /Lassen Sie uns die Negation als Variablen klassifizieren und doppelte Negationen reduzieren/ =

= /Gesetz der Distributivität/ .

Beispiel 3. Schreiben Sie die Formel in DNF und SDNF.

Lösung

Mithilfe der Gesetze der Logik reduzieren wir diese Formel auf eine Form, die nur Disjunktionen elementarer Konjunktionen enthält. Die resultierende Formel ist der gewünschte DNF:

Um die SDNF zu erstellen, erstellen wir eine Wahrheitstabelle für diese Formel:

Wir markieren die Zeilen der Tabelle, in denen die Formel (letzte Spalte) den Wert 1 annimmt. Für jede dieser Zeilen schreiben wir eine Formel aus, die für die Variablenmenge dieser Zeile gilt:

Linie 1: ;

Zeile 3: ;

Zeile 5: .

Die Disjunktion dieser drei Formeln nimmt nur für die Variablenmengen in den Zeilen 1, 3, 5 den Wert 1 an und ist daher die gewünschte perfekte disjunktive Normalform (PDNF):

Beispiel 4. Bringen Sie die Formel auf zwei Arten zu SKNF:

a) Verwendung äquivalenter Transformationen;

b) Verwendung einer Wahrheitstabelle.

Lösung:

Transformieren wir die zweite elementare Disjunktion:

Die Formel sieht so aus:

b) Erstellen Sie eine Wahrheitstabelle für diese Formel:

Wir markieren die Zeilen der Tabelle, in denen die Formel (letzte Spalte) den Wert 0 annimmt. Für jede dieser Zeilen schreiben wir eine Formel aus, die für die Variablenmenge dieser Zeile gilt:

Zeile 2: ;

Zeile 6: .

Die Konjunktion dieser beiden Formeln nimmt nur für die Variablensätze in den Zeilen 2 und 6 den Wert 0 an und ist daher die gewünschte perfekte konjunktive Normalform (PCNF):

Fragen und Aufgaben zur eigenständigen Lösung

1. Reduzieren Sie die Formeln mithilfe äquivalenter Transformationen auf DNF:

2. Bringen Sie die Formeln mithilfe äquivalenter Transformationen in CNF:

3. Wandeln Sie DNF mithilfe des zweiten Verteilungsgesetzes in CNF um:

A) ;

4. Konvertieren Sie die angegebenen DNFs in SDNFs:

5. Konvertieren Sie den angegebenen CNF in SCNF:

6. Konstruieren Sie SDNF und SCNF für gegebene logische Formeln auf zwei Arten: mithilfe äquivalenter Transformationen und mithilfe einer Wahrheitstabelle.

B) ;

Die konjunktive Normalform eignet sich zum automatischen Beweisen von Theoremen. Jede boolesche Formel kann auf CNF reduziert werden. Hierfür können Sie Folgendes verwenden: das Gesetz der doppelten Negation, das Gesetz von de Morgan, die Distributivität.

Enzyklopädisches YouTube

• 1 / 5

  Formeln im KNF:

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

  Formeln nicht im KNF:

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

  Aber diese 3 Formeln, die nicht in CNF enthalten sind, entsprechen den folgenden Formeln in CNF:

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

  Konstruktion von CNF

  Algorithmus zur Konstruktion von CNF

  1) Entfernen Sie alle in der Formel enthaltenen logischen Operationen und ersetzen Sie sie durch die grundlegenden: 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)\wedge (A\vee \neg B).)

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

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

  3) Beseitigen Sie doppelte Negative.

  4) Wenden Sie bei Bedarf die Eigenschaften der Distributivitäts- und Absorptionsformeln auf die Operationen der Konjunktion und Disjunktion an.

  Beispiel einer CNF-Konstruktion

  Bringen wir die Formel zu CNF

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

  Lassen Sie uns die Formel umwandeln F (\displaystyle F) zu einer Formel, die nicht enthält → (\displaystyle \rightarrow ):

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

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

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

  Beispielsweise ist die folgende Formel in 2-CNF geschrieben:

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

  Einfach Verbindung angerufen Verbindung eins oder mehrere Variablen, bei Das jede Variable trifft Nicht mehr eins mal (oder Sie selber, oder ihr Negation).

  Ist zum Beispiel eine einfache Konjunktion,

  Disjunktiv normal Form(Nicht verfügbar) angerufen Disjunktion einfach Konjunktionen.

  Der Ausdruck lautet beispielsweise DNF.

  Perfekt disjunktiv normal Form(SDNF) angerufen so was disjunktiv normal bilden, bei welche V jeden Verbindung inbegriffen Alle Variablen gegeben Liste (oder sich, oder ihre Verweigerung), Und V eins Und Volumen DasselbeOK.

  Der Ausdruck ist beispielsweise DNF, aber nicht SDNF. Ausdruck ist SDNF.

  Ähnliche Definitionen (mit Ersetzung der Konjunktion durch Disjunktion und umgekehrt) gelten für CNF und SKNF. Lassen Sie uns den genauen Wortlaut angeben.

  Einfach Disjunktion angerufen Disjunktion eins oder mehrere Variablen, bei Das jede Variable inbegriffen Nicht mehr eins mal (oder Sie selber, oder ihr Negation).Zum Beispiel ist der Ausdruck eine einfache Disjunktion,

  Konjunktiv normal Form(KNF) angerufen Verbindung einfach Disjunktionen(Der Ausdruck lautet beispielsweise CNF).

  Eine perfekte konjunktive Normalform (PCNF) ist eine KNF, in der jede einfache Disjunktion alle Variablen einer gegebenen Liste (entweder sich selbst oder ihre Negationen) in derselben Reihenfolge enthält.

  Zum Beispiel der Ausdruck ist SKNF.

  Stellen wir Algorithmen für Übergänge von einer Form zur anderen vor. Natürlich kann der Einsatz von Algorithmen in bestimmten Fällen (bei einem bestimmten kreativen Ansatz) arbeitsintensiver sein als einfache Transformationen unter Verwendung eines bestimmten Typs einer bestimmten Form:

  a) Übergang von DNF zu CNF

  Der Algorithmus für diesen Übergang ist wie folgt: Wir setzen zwei Negationen über den DNF und reduzieren unter Verwendung der De Morgan-Regeln (ohne die obere Negation zu berühren) die Negation des DNF wieder auf DNF. In diesem Fall müssen Sie die Klammern mithilfe der Absorptionsregel (oder der Blake-Regel) öffnen. Die Negation (oben) des resultierenden DNF (wiederum gemäß de Morgans Regel) ergibt sofort den CNF:

  Beachten Sie, dass CNF auch aus dem ursprünglichen Ausdruck erhalten werden kann, wenn wir ihn herausnehmen bei jenseits von Klammern;

  b) Übergang von CNF zu DNF

  Dieser Übergang erfolgt durch einfaches Öffnen der Klammern (es kommt wieder die Absorptionsregel zur Anwendung)

  Somit haben wir DNF erhalten.

  Der umgekehrte Übergang (von SDNF zu DNF) ist mit dem Problem der Minimierung von DNF verbunden. Darauf wird im Abschnitt näher eingegangen. 5, hier zeigen wir, wie man DNF (oder SDNF) gemäß der Blake-Regel vereinfacht. Diese Art von DNF wird aufgerufen abgekürzt DNF;

  c) Abkürzung DNF (oder SDNF) von Regel Blake

  Die Anwendung dieser Regel besteht aus zwei Teilen:

  Wenn es unter den disjunkten Termen im DNF Terme gibt , dann fügen wir zur gesamten Disjunktion den Term hinzu ZU 1 ZU 2. Wir führen diese Operation mehrmals (möglicherweise nacheinander oder gleichzeitig) für alle möglichen Begriffspaare durch und wenden dann die normale Absorption an;

  Wenn der hinzugefügte Begriff bereits im DNF enthalten war, kann er beispielsweise vollständig verworfen werden,

  oder

  Natürlich ist die Abkürzung DNF nicht eindeutig definiert, aber sie enthalten alle die gleiche Anzahl an Buchstaben (z. B. gibt es DNF , nachdem man die Blake-Regel darauf angewendet hat, kann man zu einem DNF-Äquivalent zu diesem gelangen):

  c) Übergang von DNF zu SDNF

  Wenn bei einer einfachen Konjunktion beispielsweise eine Variable fehlt, z, fügen Sie den Ausdruck ein und öffnen Sie dann die Klammern (wir schreiben keine sich wiederholenden disjunkten Terme). Zum Beispiel:

  d) Übergang von KNF zu SKNF

  Dieser Übergang wird auf ähnliche Weise wie der vorherige durchgeführt: Wenn einer einfachen Disjunktion eine Variable fehlt (z. B. z, dann fügen wir einen Ausdruck hinzu (die Disjunktion selbst ändert sich dadurch nicht), danach öffnen wir die Klammern mit dem Verteilungsgesetz):

  Somit wurde SKNF von CNF erhalten.

  Beachten Sie, dass der minimale oder reduzierte CNF normalerweise aus dem entsprechenden DNF erhalten wird.

  Normalformen logischer Funktionen Die Darstellung einer booleschen Funktion in Form einer Disjunktion konjunktiver Terme der Konstituenten der Einheit Ki 2.7 wird als disjunktive Normalform des DNF dieser Funktion bezeichnet. genau eine aller logischen Variablen mit oder ohne Negationen enthalten, dann heißt diese Darstellungsform einer Funktion eine perfekte disjunktive Normalform SDNF dieser Funktion. Wie Sie sehen, müssen Sie beim Erstellen einer SDNF-Funktion eine Disjunktion aller Minterme erstellen, 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 logischer Funktionen

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

  , (2.7)

  angerufen disjunktive Normalform(DNF) dieser Funktion.

  Wenn alle Konjunktivbegriffe in DNF sind Minterms , also genau eine aller logischen Variablen, mit oder ohne Negationen, enthalten, dann heißt diese Form der Funktionsdarstellungperfekte disjunktive Normalform(SDNF ) diese Funktion. Es heißt SDNF perfekt , weil jeder Term in der Disjunktion alle Variablen enthält; disjunktiv , weil die Hauptoperation in der Formel die Disjunktion ist. Konzept "normale Form„bedeutet eine eindeutige Art, eine Formel zu schreiben, die eine bestimmte Funktion implementiert.

  Unter Berücksichtigung des oben Gesagten folgt aus Satz 2.1 der folgende Satz.

  Satz 2. Jede boolesche Funktion(nicht identisch 0) kann in SDNF präsentiert werden, .

  Beispiel 3. Lassen Sie uns eine Tabelle mit gegebener Funktion 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 Erstellen einer SDNF-Funktion eine Disjunktion aller Minterme erstellen, für die die Funktion den Wert 1 annimmt.

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

  , (2.8)

  angerufen konjunktive Normalform(CNF) dieser Funktion.

  Wenn alle disjunktiven CNF-Terme sind maxterms , also genau eine aller 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 mit 1) können bei SKNF eingereicht werden, und eine solche Darstellung ist die einzige.

  Der Beweis des Satzes kann ähnlich wie der Beweis von Satz 2.1 basierend auf dem folgenden Shannon-Lemma zur konjunktiven Zerlegung durchgeführt werden.

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

  . (2.9)

  Es ist zu beachten, dass beide Darstellungsformen 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 Null) dargestellt werden ). Je nach Situation kann die Darstellung einer 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 verspürt er intuitiv den Wunsch, die Klammern zu öffnen und so zu DNF überzugehen).

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

  Im Gegensatz zum SDNF müssen Sie beim Kompilieren des SCNF in der Wahrheitstabelle einer logischen Funktion die Variablenkombinationen betrachten, bei denen die Funktion den Wert 0 annimmt, und eine Konjunktion der entsprechenden Maxterms erstellen.aber die Variablen müssen mit umgekehrter Invertierung genommen werden:

  Es ist zu beachten, dass es unmöglich ist, direkt von der SDNF einer Funktion zu ihrer SCNF zu wechseln oder umgekehrt. Beim Versuch solcher Transformationen sind die Ergebnisse Funktionen, die das Gegenteil der gewünschten sind. Ausdrücke für die SDNF- und SCNF-Funktionen können direkt nur aus der Wahrheitstabelle abgerufen werden.

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

  Mit dem Ergebnis von Beispiel 2.3 erhalten wir:

  Wie Sie sehen können, haben wir durch die allgemeine Inversion die SCNF einer logischen Funktion erhalten, die die Umkehrung der in Beispiel 2.4 erhaltenen Funktion ist:

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

  1. Unter Verwendung der Eigenschaften der Operationen (siehe Tabelle 9) Identität (), Summe Modulo 2 (), Implikation () fahren wir mit den Operationen UND, ODER, NICHT (auf boolescher Basis) fort.

  2. Mithilfe der Eigenschaften der Negation und der Gesetze von De Morgan (siehe Tabelle 9) stellen wir sicher, dass 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. Fahren Sie bei Bedarf mit perfekten Formen fort (SDNF oder SKNF). Um beispielsweise SCNF zu erhalten, müssen Sie häufig die Eigenschaft verwenden: .

  Beispiel 6. Konvertieren Sie eine logische Funktion in SKNF

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

  Unter Verwendung der Absorptionseigenschaft erhalten wir:

  Somit haben wir die CNF-Funktion erhalten f (x 1 , x 2 , x 3 ). Um seinen SCNF 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 logischer Funktionen

  Da die gleiche logische Funktion dargestellt werden kann als H persönliche Formeln, dann die einfachste Form finden R Mule, das eine boolesche Funktion definiert, vereinfacht die Logikschaltung, die die boolesche Funktion implementiert zu tion. Mindestform lÖ logische FunktionIn gewisser Weise können wir eines in Betracht ziehen, das die minimale Anzahl an Spaßüberlagerungen enthält Zu tionen der Basis unter Berücksichtigung von Klammern. Es ist jedoch schwierig, eine wirksame Lösung aufzubauen l Algorithmus für eine solche Minimierung, um die minimale Klammer zu erhalten r wir.

  Betrachten wir ein einfacheres Minimierungsproblem bei der Synthese kombinatorischer Schaltkreise, bei dem wir nicht nach der minimalen Klammerform einer Funktion suchen, sondern nach ihrer minimalen DNF. Für diese Aufgabe gibt es einfache, effiziente Algorithmen.

  Quines Methode

  Die zu minimierende Funktion wird in SDNF dargestellt und alle möglichen unvollständigen Klebevorgänge 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 einziger Begriff mehr vorhanden ist, der mit einem anderen Begriff verbunden 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 mögliche Fälle gibt, in denen sie zur Verbindung und Absorption mit den übrigen Begriffen verwendet werden.

  Es ist zu beachten, dass Quines Methode recht arbeitsintensiv ist, sodass die Wahrscheinlichkeit, bei Transformationen Fehler zu machen, recht hoch ist. Sein Vorteil ist jedoch, dass es theoretisch für beliebig viele Argumente verwendet werden kann und mit zunehmender Anzahl an Variablen die Transformationen weniger kompliziert werden.

  Karnaugh-Kartenmethode

  Die Methode der Carnot-Karten (Tabellen) ist eine visuellere, weniger arbeitsintensive 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 der Darstellung der Wahrheitstabelle einer booleschen Funktion, die es Ihnen ermöglicht, die minimalen DNFs logischer Funktionen in einer grafischen visuellen Form einfach zu finden. Jede Zelle der Tabelle ist dem SDNF-Mintermerm der zu minimierenden Funktion zugeordnet, und zwar so, dass alle Symmetrieachsen der Tabelle Zonen entsprechen, die in Bezug auf eine Variable gegenseitig invers sind. Diese Anordnung der Zellen in der Tabelle erleichtert die Bestimmung der Haftterme des SDNF (die sich im Umkehrzeichen nur einer Variablen unterscheiden): Sie sind symmetrisch in der Tabelle angeordnet.

  Wahrheitstabellen und Carnaugh-Karten für die UND- und ODER-Funktionen zweier Spuren e Die Variablen sind in Abb. dargestellt. 8. In jedes Feld der Karte wird ein Wert geschrieben A Der Wert einer Funktion auf der Menge der Argumentwerte, die dieser Zelle entsprechen N Genosse

  A) UND b) ODER

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

  In der Karnaugh-Karte gibt es nur eine 1 für die Und-Funktion, sie kann also an nichts geklebt werden. Der Ausdruck für die Minimalfunktion enthält nur den Term, der dieser 1 entspricht:

  f = x y .

  In der Carnot-Karte für die OR-Funktion gibt es bereits drei Einsen und Sie können zwei hängende Paare bilden, wobei die Eins dem Term entspricht xy , wird zweimal verwendet. Im Ausdruck für die Minimalfunktion müssen Sie die Terme für die zusammengeklebten Paare aufschreiben, dabei alle Variablen belassen, die sich für dieses Paar nicht ändern, und die Variablen entfernen, die ihren Wert ändern. Für horizontales Kleben bekommen wir X , und für vertikal j , als Ergebnis erhalten wir den Ausdruck

  f = x + y.

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

  Bei der Bestimmung der minimalen DNF-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 Menge 1 in einer rechteckigen Fläche. 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 Bereich von 2 3 = 8 Einheiten aufgerufen wird Dreiwürfel ; usw. Einheiten, die nicht zu Rechtecken zusammengefasst werden können, können aufgerufen werden Nullwürfel , die nur eine Einheit enthalten (2 0 = 1). Wie man sehen kann, sogar k Bereiche können eine quadratische Form haben (aber nicht unbedingt), und wenn sie ungerade sind k nur Rechtecke.

  						v. Chr

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

  Diese Regionen können sich überlappen, d. h. dieselben Zellen können in verschiedene Regionen gelangen. Dann wird die minimale DNF-Funktion als Disjunktion aller entsprechenden Konjunktivterme geschrieben k - Würfel.

  Jeder der angegebenen Bereiche auf der Karnaugh-Karte wird in einem 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 gleich mk . Jede Konjunktion eines minimalen DNF besteht nur aus solchen Argumenten, die für den entsprechenden Bereich der Karte entweder Werte ohne Inversionen oder nur mit Inversionen haben, also ihre Bedeutung nicht ändern.

  Wenn man also Kartenzellen mit geschlossenen Bereichen überdeckt, sollte man darauf achten, dass die Anzahl der Bereiche minimal ist und jeder Bereich 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 Karnaugh-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 weiter definiert werden, indem es durch Null oder Eins ersetzt wird. Für diese Funktion ist es klar, dass es rentabler ist, beide undefinierten Werte durch 1 zu ersetzen. In diesem Fall werden zwei Bereiche 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 Gebiete ist es erlaubt, die Carnot-Karte sowohl horizontal als auch vertikal zu einem Zylinder zu falten. R Tikal-Achsen mit der Vereinigung gegenüberliegender Flächen R Sie, d. h. Einheiten, die sich entlang der Ränder der Carnot-Symmetriekarte befinden H sind aber auch kombinierbar.

  Carnaugh-Karten können auf unterschiedliche Weise gezeichnet werden (Abb. 10).

  									x 2 x 3

  ein b

  Reis. 10. Verschiedene Möglichkeiten, Carnaugh-Karten darzustellen
  für eine Funktion von 3 Variablen

  Die bequemsten Optionen für Karnaugh-Karten für Funktionen von 2-4 Variablen sind jedoch die in Abb. 11 Tabellen, weil sie für jede Zelle angezeigt werden A Wir haben alle Variablen in direkter oder inverser Form.

  ein b

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

  Für Funktionen mit 5 und 6 Variablen gilt die in Abb. 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 ähnliche Werke, die Sie interessieren könnten.vshm>
  9020.		DAS PRINZIP DER DUALITÄT. ERWEITERUNG BOOLER FUNKTIONEN IN VARIABLEN. Perfekte disjunktive und konjunktive Normalformen	96,34 KB
  	Dieser Satz ist konstruktiver Natur, da er es ermöglicht, für jede Funktion eine Formel zu konstruieren, die sie in Form eines perfekten d.n. implementiert. F. Dazu markieren wir in der Wahrheitstabelle für jede Funktion alle Zeilen, in denen
  6490.		Beschreibung und Minimierung logischer Funktionen	187,21 KB
  	Die Beziehung zwischen den Argumenten einer Funktion und ihren Werten wird in verbaler Form ausgedrückt. Beispiel: Eine Funktion mit drei Argumenten nimmt einen Wert an, wenn zwei oder mehr Funktionsargumente gleich sind. Besteht aus der Erstellung einer Wahrheitstabelle, die Funktionswerte für alle Sätze von Argumentwerten enthält. In diesem Beispiel erhalten wir unter Verwendung der Wahrheitstabelle den folgenden Eintrag in der Form DNF...
  6707.		Design relationaler Datenbanken. Designprobleme im klassischen Ansatz. Prinzipien der Normalisierung, Normalformen	70,48 KB
  	Was ist ein relationales Datenbankprojekt? Dabei handelt es sich um eine Reihe miteinander verbundener Beziehungen, in denen alle Attribute definiert, die Primärschlüssel der Beziehungen angegeben und einige zusätzliche Eigenschaften der Beziehungen angegeben werden, die sich auf die Grundsätze der Integritätserhaltung beziehen. Daher muss das Datenbankdesign sehr genau und verifiziert sein. Tatsächlich ist ein Datenbankprojekt die Grundlage eines zukünftigen Softwarepakets, das über einen längeren Zeitraum und von vielen Benutzern verwendet wird.
  4849.		Formen und Methoden zur Umsetzung staatlicher Funktionen	197,3 KB
  	Der Begriff „Funktion“ hat in der in- und ausländischen wissenschaftlichen Literatur bei weitem nicht die gleiche 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 einer logischen UUD für Schüler der 3. Klasse	846,71 KB
  	Psychologische und pädagogische Aspekte des Problems der Bildung logischer universeller Handlungen bei Grundschulkindern Methoden zur Beurteilung der Bildung logischer UUDs. Die Entwicklung eines Konzepts zur Entwicklung universeller Bildungsaktivitäten im allgemeinen Bildungssystem wird neuen gesellschaftlichen Bedürfnissen gerecht. Die wichtigste Aufgabe des modernen Bildungssystems ist die Gestaltung universeller Bildungsaktivitäten der UUD. Die Gestaltung universeller Bildungsaktivitäten ist der Schlüssel zur Vermeidung von Schulschwierigkeiten.
  2638.		Technische Umsetzung logischer Verknüpfungen in automatischen Sperrsystemen	1,04 MB
  	Technische Umsetzung logischer Verknüpfungen in automatischen Sperrsystemen Die technische Umsetzung von Steueralgorithmen für dreistellige und vierstellige Batterien kann durch den Einsatz von Relaiskontakten und kontaktlosen diskreten und integralen Logikelementen erreicht werden...
  10203.		ANWENDUNG DES KONZEPTS DES RISIKOORIENTIERTEN ANSATZES ZUM AUFBAU STRUKTURELLER UND LOGISCHER MODELLE DES NOTFALLS UND DER ENTWICKLUNG	70,8 KB
  	Allgemeine Risikoanalyse Die Produktionsumgebung wird 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. Jeden Tag sind wir mit zahlreichen Risiken konfrontiert, die meisten davon bleiben jedoch potenziell bestehen. Die Risikotheorie ermöglicht eine quantitative Bewertung der negativen Auswirkungen auf einen Menschen sowie der Schäden an seiner Gesundheit und seinem Leben.
  11576.		Konzept, Arten und Formen von Transaktionen. Folgen der Nichteinhaltung der erforderlichen Form von Transaktionen	49,82 KB
  	Erkennung einer Transaktion als ungültig; Arten ungültiger Transaktionen. Der Anwendungswert der Studienarbeit liegt in der Vereinfachung des Konzepts einer Transaktion, also ihrer öffentlichen Darstellung in einer zugänglicheren Form.
  6213.		Funktionsnäherung	3,08 MB
  	Die erste besteht darin, eine bestimmte analytisch oder tabellarisch spezifizierte Funktion durch eine andere Funktion zu ersetzen, die der ursprünglichen Funktion ähnelt, aber einfacher und für Berechnungen bequemer ist. Wenn Sie beispielsweise eine Funktion durch ein Polynom ersetzen, können Sie einfache Formeln für die numerische Integration und Differenzierung erhalten. Durch Ersetzen der Tabelle durch eine Näherungsfunktion können Sie Werte an ihren Zwischenpunkten erhalten. Es entsteht auch das zweite Problem: Wiederherstellen einer Funktion auf einem bestimmten Segment aus den Werten der auf diesem Segment angegebenen Funktion in einer diskreten Menge von Punkten. Die Antwort auf diese Frage...
  14058.		Entwicklung staatlicher Funktionen	29,99 KB
  	Der russische Staat als Rechtsphänomen muss zunächst die Verwirklichung des Staatszwecks sowie seiner wesentlichen Verfassungsmerkmale als demokratischer föderaler, rechtlicher, sozial-säkularer Staat mit republikanischer Regierungsform sicherstellen. Der Hauptzweck des Staates wird durch Art bestimmt.