Konjunktive Normalform einer logischen Funktion. Konjunktive Darstellungsformen logischer Funktionen

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).)

Einfach Verbindung namens Verbindung einer oder mehrere Variablen, bei Dies Jeder Variable trifft nicht mehr einer mal (oder selbst, oder Sie Negation).

Ist zum Beispiel eine einfache Konjunktion,

Disjunktiv normal Form(DNF) namens Disjunktion einfach Konjunktionen.

Der Ausdruck ist beispielsweise DNF.

Perfekt disjunktiv normal Form(SDNF) namens so disjunktiv normal die Form, bei welcher v jeden Verbindung sind inklusive alle Variablen gegeben aufführen (oder sich, oder ihr Leugnungen), Außerdem v einer und Volumen das gleicheokay.

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

Ähnliche Definitionen (mit Ersetzung der Konjunktion durch Disjunktion und umgekehrt) gelten für CNF und SKNF. Hier die genauen Formulierungen.

Einfach Disjunktion namens Disjunktion einer oder mehrere Variablen, bei Dies Jeder Variable tritt ein nicht mehr einer mal (oder selbst, oder Sie Negation) Zum Beispiel ist ein Ausdruck eine einfache Disjunktion,

Konjunktiv normal Form(CNF) namens Verbindung einfach Disjunktionen(z. B. ist der Ausdruck CNF).

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

Zum Beispiel der Ausdruck ist SKNF.

Hier sind die Algorithmen für Übergänge von einer Form in eine andere. Natürlich ist der Einsatz von Algorithmen in bestimmten Fällen (mit einem gewissen kreativen Ansatz) mühsamer als einfache Transformationen mit einem bestimmten Typ einer bestimmten Form:

a) Übergang von DNF zu CNF

Der Algorithmus für diesen Übergang ist wie folgt: Wir stellen zwei Negationen über den DNF und bringen die Negation des DNF unter Verwendung der de Morgan-Regeln (ohne die obere Negation zu berühren) zurück zum DNF. In diesem Fall müssen Sie die Klammern mit der Absorptionsregel (oder der Blake-Regel) öffnen. Die Negation (oben) des erhaltenen DNF (wieder nach der de-Morgan-Regel) gibt uns sofort den CNF:

Beachten Sie, dass die CNF auch aus dem Anfangsausdruck erhalten werden kann, wenn wir bei außerhalb der Klammern;

b) Übergang von CNF zu DNF

Dieser Übergang erfolgt durch einfaches Öffnen der Klammern (hier wird wiederum die Absorptionsregel verwendet)

So haben wir DNF bekommen.

Der umgekehrte Übergang (von SDNF zu DNF) ist mit dem Problem der Minimierung von DNF verbunden. Dies wird in Abschn. 5, hier zeigen wir, wie man DNF (oder SDNF) gemäß der Blake-Regel vereinfachen kann. Diese DNF heißt abgekürzt DNF;

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

Die Anwendung dieser Regel besteht aus zwei Teilen:

Wenn sich unter den disjunkten Begriffen im DNF Begriffe befinden , dann fügen wir zur ganzen Disjunktion den Term ZU 1 ZU 2. Wir führen diese Operation mehrere Male (sie kann sequentiell oder gleichzeitig sein) für alle möglichen Termpaare durch und wenden dann die übliche Absorption an;

War der hinzugefügte Begriff bereits im DNF enthalten, kann er z.B. ganz verworfen werden,

oder

Natürlich ist das abgekürzte DNF nicht eindeutig definiert, aber sie enthalten alle die gleiche Anzahl von Buchstaben (zum Beispiel gibt es ein DNF , nachdem Sie Blakes Regel darauf angewendet haben, können Sie zu einem DNF-Äquivalent zu diesem gelangen:

c) Übergang von DNF zu SDNF

Wenn einer einfachen Konjunktion beispielsweise eine Variable fehlt, z, fügen Sie den Ausdruck ein und erweitern Sie dann die Klammern (in diesem Fall schreiben wir keine wiederholten disjunkten Terme). Zum Beispiel:

d) Übergang von CNF zu SKNF

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

Somit wird SKNF aus CNF erhalten.

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

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 alle Boolesche Funktion$ f (\ vec (x)) $, ungleich der Identität, es gibt 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

1). 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) $

Definition 1.Konjunktiv Monom (elementare Konjunktion) aus Variablen nennt man die Konjunktion dieser Variablen oder deren Negationen.

Zum Beispiel, Ist eine elementare Konjunktion.

Definition 2.Disjunktives Monom (elementare Disjunktion) von Variablen nennt man die Disjunktion dieser Variablen oder deren 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 die Konjunktion elementarer disjunktiver Monome ist, heißt konjunktive Normalform(CNF) dieser Formel.

Zum Beispiel, - KNF.

Für jede Formel der Aussagenalgebra kann man eine Menge von disjunktiven und konjunktiven Normalformen finden.

Algorithmus zur Konstruktion von Normalformen

Ersetzen Sie mit den Äquivalenzen der Algebra der Logik alle Operationen in der Formel durch die grundlegenden: Konjunktion, Disjunktion, Negation:

Befreien Sie sich von doppelten Verneinungszeichen.

Wenden Sie bei Bedarf auf die Verknüpfungs- und Disjunktionsoperationen die Eigenschaften der Distributivität und der Absorptionsformel an.

2.6. Perfekte disjunktive und perfekt konjunktive Normalformen

Jede boolesche Funktion kann viele Darstellungen in Form von DNF und CNF haben. Einen besonderen Platz unter diesen Darstellungen nehmen perfekte DNF (SDNF) und perfekte CNF (SKNF) ein.

Definition 1. Perfekte disjunktive Normalform(SDNF) ist ein DNF, in dem in jedem konjunktiven Monom jede Variable aus der Menge genau einmal vorkommt und entweder sie selbst oder ihre Negation vorkommt.

Konstruktiv kann der SDNF für jede auf den DNF reduzierte Formel der Aussagenalgebra wie folgt definiert werden:

Definition 2. Perfekte disjunktive Normalform(SDNF) einer Formel der Aussagenalgebra wird als DNF bezeichnet, das die folgenden Eigenschaften hat:

Definition 3. Perfekte konjunktive Normalform(SKNF) ist eine KNF, in der in jedem disjunktiven Monom jede Variable aus der Menge genau einmal vorkommt und entweder sie selbst oder ihre Negation vorkommt.

Strukturell kann der SKNF für jede Formel der auf den CNF reduzierten Aussagenalgebra wie folgt definiert werden.

Definition 4. Perfekte konjunktive Normalform(SKNF) einer gegebenen Formel der Aussagenalgebra wird ihr CNF genannt, der die folgenden Eigenschaften erfüllt.

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

So finden Sie SDNF

1. Weg

2. Weg

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

wir bilden eine Disjunktion von Konjunktionen, vorausgesetzt, wenn eine Variable in einer Konjunktion mit einem Wert von 1 enthalten ist, schreiben wir diese Variable, wenn sie einen Wert von 0 hat, dann ihre Negation. Wir erhalten SDNF.

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

So finden Sie SKNF

1. Weg- mit äquivalenten Transformationen:

2. Weg- Verwenden von Wahrheitstabellen:

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

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

Beispiel 1. Zeichnen Sie CNF-Funktionen.

Lösung

Lassen Sie uns den Link "" nach den Transformationsgesetzen von Variablen ausschließen:

= / de Morgan und doppelte Negationsgesetze / =

/ Verteilungsgesetze / =

Beispiel 2. Bringen Sie die Formel zu DNF.

Lösung

Lassen Sie uns logische Operationen in Form von und ausdrücken:

= / wir werden die Negation auf Variablen beziehen und doppelte Negative reduzieren / =

= / Verteilungsgesetz /.

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

Lösung

Mit den Gesetzen der Logik werden wir diese Formel in eine Form bringen, die nur Disjunktionen elementarer Konjunktionen enthält. Die resultierende Formel ist die gewünschte DNF:

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

Wir markieren die Zeilen der Tabelle, in denen die Formel (die letzte Spalte) den Wert 1 annimmt. Für jede solche Zeile schreiben wir die Formel aus, die für die Menge der Variablen der gegebenen 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 perfekt disjunktive Normalform (SDNF):

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

a) äquivalente Transformationen verwenden;

b) Verwenden der Wahrheitstabelle.

Lösung:

Wir transformieren die zweite elementare Disjunktion:

Die Formel lautet:

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

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

Zeile 2:;

Zeile 6:.

Die Konjunktion dieser beiden Formeln nimmt nur auf den Variablenmengen in den Zeilen 2 und 6 den Wert 0 an und ist daher die gewünschte perfekte konjunktive Normalform (SCNF):

Fragen und Aufgaben zur eigenständigen Lösung

1. Bringen Sie die Formeln mit äquivalenten Transformationen in DNF:

2. Bringen Sie die Formeln mit äquivalenten Transformationen in CNF:

3. Verwenden Sie das zweite Verteilungsgesetz, um DNF in CNF umzuwandeln:

ein) ;

4. Konvertieren Sie die angegebenen DNFs in SDNFs:

5. Konvertieren Sie die angegebene CNF in SKNF:

6. Konstruieren Sie für die gegebenen logischen Formeln die SDNF und SKNF auf zwei Arten: unter Verwendung äquivalenter Transformationen und unter Verwendung der Wahrheitstabelle.

B) ;

Disjunktive und konjunktive Normalformen der Aussagenalgebra. Für jede Funktion der Aussagelogik können Sie eine Wahrheitstabelle erstellen. Auch das inverse Problem ist immer lösbar. Lassen Sie uns mehrere Definitionen einführen.

Elementare Konjunktionen (konjunkt) heißen Konjunktionen von Variablen oder deren Negationen, in denen jede Variable höchstens vorkommt

wenn.

Disjunktive Normalform(DNF) ist eine Formel, die die Form einer Disjunktion von elementaren Konjunktionen hat.

Elementarsätze (Klauseln) heißen Disjunktionen von Variablen mit oder ohne Negationen.

Konjunktive Normalform(CNF) ist eine Formel, die die Form einer Konjunktion elementarer Disjunktionen hat.

Für jede Funktion der Satzalgebra kann man eine Menge disjunktiver und konjunktiver Normalformen finden.

Algorithmus zur Konstruktion von DNF:

1. Gehen Sie zu Booleschen Operationen mit äquivalenten Transformationsformeln.

2. Gehen Sie zu Formeln mit engen Negationen, dh zu einer Formel, in der die Negationen nicht höher als über den Variablen liegen - um die Gesetze von de Morgan anzuwenden.

3. Klammern erweitern - Wenden Sie die Verteilungsgesetze an.

4. Nehmen Sie die wiederholten Begriffe einmal - das Gesetz der Idempotenz.

5. Wenden Sie die Gesetze der Absorption und Halbabsorption an.

Beispiel 6. Finden Sie DNF-Formeln:.

Die Boolesche Algebra gilt Dualitätsprinzip... Es ist wie folgt.

Die Funktion heißt Dual zur Funktion wenn. Jene. Um eine Funktion zu finden, die zu einer gegebenen dual ist, ist es notwendig, die Negation der Funktion aus den Negationen der Argumente zu konstruieren.

Beispiel 7. Finden Sie die Doppelfunktion zu.

Zu den elementaren Funktionen der Algebra der Logik gehört 1 dual zu 0 und umgekehrt, x ist dual zu x, dual, dual und umgekehrt.

Wenn in der Formel F 1 für die Funktion alle Konjunktionen ersetzt werden

auf Disjunktion, Disjunktion auf Konjunktion, 1 zu 0, 0 zu 1, dann erhalten wir die Formel F *, die die Funktion * dual darstellt.

Die konjunktive Normalform (CNF) ist ein duales Konzept für DNF, daher ist es einfach, sie nach dem Schema zu konstruieren:

Beispiel 8. Finden Sie die CNF-Formel:.

Mit dem Ergebnis von Beispiel 6 haben wir

Perfekte disjunktive und perfekt konjunktive Normalformen. In jedem der Typen der Normalformen (disjunktiv und konjunktiv) kann eine Klasse von perfekten Formen SDNF und SKNF unterschieden werden.

Eine perfekte elementare Konjunktion ist das logische Produkt aller Variablen mit oder ohne Negation, und jede Variable kommt im Produkt nur einmal vor.

Jedes DNF kann auf SDNF reduziert werden, indem man Konjunktionen aufspaltet, die nicht alle Variablen enthalten, d.h. Addition für die fehlende Variable x i wird mit dem Verteilungsgesetz multipliziert

Beispiel 9. Finden Sie SDNF für DNF-Beispiel 6

Perfekte elementare Disjunktion ist die logische Summe aller Variablen mit oder ohne Negationen, und jede Variable ist nur einmal in der Summe enthalten.

Jede CNF kann auf SKNF reduziert werden, indem ein Konjunktionsterm hinzugefügt wird, der keine variable X i-Konjunktion enthält, und das Distributivgesetz anwendet

Beispiel 10. Bringen Sie CNF zu SKNF:

Um den SKNF zu bauen, können Sie das Schema verwenden

Beispiel 11. Finden Sie den SKNF für die Formel in Beispiel 6.

Jede Funktion hat SDNF und ist außerdem einzigartig. Jede Funktion hat eine SKNF und außerdem die einzige.

Weil SDNF und SKNF sind durch Formeln eindeutig definiert, sie können gemäß der Wahrheitstabelle der Formel gebildet werden.

Um die SDNF zu konstruieren, ist es notwendig, die Zeilen auszuwählen, in denen F den Wert 1 annimmt, und dafür perfekte elementare Konjunktionen aufzuschreiben. Wenn der Wert einer Variablen in der gewünschten Zeile der Wahrheitstabelle gleich eins ist, wird er in einer perfekten Konjunktion ohne Negation genommen, wenn null, dann mit Negation. Dann werden perfekte Konjunkte (ihre Zahl ist gleich der Zahl der Einsen in der Tabelle) durch Disjunktionszeichen verbunden.

Um SKNF nach der Wahrheitstabelle zu konstruieren, ist es notwendig, die darin enthaltenen Linien mit F = 0 auszuwählen und die perfekten elementaren Disjunktionen aufzuschreiben und sie dann mit Konjunktionszeichen zu verbinden. Wenn in der gewünschten Zeile der Wahrheitstabelle (F = 0) der Wert der Variablen Null entspricht, dann wird er in der perfekten Klausel ohne Negation genommen, wenn er eins ist - dann mit Negation.

Beispiel 12. Finden Sie SDNF und SKNF mithilfe der Wahrheitstabelle für die Formel in Beispiel 6.

Tabelle 14 zeigt nur den Endwert von F = 10101101. Sie sollten sich selbst von der Gültigkeit dieser Aussage überzeugen, indem Sie eine erweiterte Wahrheitstabelle erstellen.

Tabelle 14

x	ja	z