Perfekt konjunktiv normalform

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 november 2018; kontroller kräver 2 redigeringar .

En perfekt konjunktiv normalform (CKNF) är en av formerna för att representera en funktion av logikens algebra (boolesk funktion) som ett logiskt uttryck. Det är ett specialfall av CNF som uppfyller följande tre villkor:

Den har inga identiska termer (elementära disjunktioner);

Det finns inga återkommande variabler i varje faktor;

· varje multiplikator innehåller alla variabler som den booleska funktionen beror på (varje variabel kan inkluderas i multiplikatorn antingen i direkt eller invers form).

Varje boolesk formel som inte är identiskt sann kan reduceras till SKNF. [1] .

Ett exempel på att hitta SKNF

För att få SKNF för en funktion krävs att den kompilerar dess sanningstabell. Låt oss till exempel ta en av sanningstabellerna i artikeln som minimerar logiska funktioner med Quines metod :

0 0 0 0 ett
0 0 0 ett ett
0 0 ett 0 ett
0 0 ett ett 0
0 ett 0 0 0
0 ett 0 ett 0
0 ett ett 0 ett
0 ett ett ett 0
ett 0 0 0 0
ett 0 0 ett 0
ett 0 ett 0 0
ett 0 ett ett 0
ett ett 0 0 0
ett ett 0 ett 0
ett ett ett 0 ett
ett ett ett ett ett

I cellerna på raden är endast de kombinationer markerade som bringar det logiska uttrycket till noll.

Den fjärde raden innehåller 0 i det angivna fältet. Värdena för alla fyra variablerna är noterade, dessa är:

En variabel skrivs in i disjunktionen utan inversion om den är lika med 0 i mängden, och med inversion om den är lika med 1. Den första medlemmen av SKNF för den betraktade funktionen ser ut så här:

De återstående medlemmarna i SKNF sammanställs analogt: [2]

Se även


Anteckningar

  1. ↑ Matematisk logik. Riktlinjer för kursen "Fundamentals of Discrete Mathematics for students of speciality 220220" . Hämtad 25 mars 2016. Arkiverad från originalet 9 april 2016.
  2. ↑ V.I. Igoshin. Uppgiftsbok-workshop om matematisk logik. 1986