Perfekt disjunktiv normalform

Perfekt disjunktiv normalform (PDNF) er en af formerne til at repræsentere en funktion af logikkens algebra (boolsk funktion) i form af et logisk udtryk. Det er et særligt tilfælde af DNF , der opfylder følgende tre betingelser [1] :

det har ikke identiske udtryk (elementære konjunktioner);
der er ingen gentagne variabler i hvert led;
hvert led indeholder alle de variable, som den boolske funktion afhænger af (hver variabel kan inkluderes i udtrykket enten i direkte eller omvendt form).

Enhver boolsk formel , der ikke er identisk falsk, kan reduceres til SDNF, og på en unik måde, det vil sige for enhver tilfredsstillende funktion af den logiske algebra, er der sin egen SDNF, og den eneste ene [2] .

Kort teori

DNF er "summen af produkter", og AND-operationen (konjunktion) fungerer som "multiplikations"-operationen, og OR-operationen (disjunktion) fungerer som "additions"-operationen. Faktorer er forskellige variable, og de kan indgå i produktet både i direkte og omvendt form.

Nedenfor er et eksempel på en DNF:

$F(A,B,C,D,E)={\bar {A}}B+A{\bar {B}}E+B{\bar {C}}D.$

Generelt kan en DNF indeholde gentagne udtryk, og hver term kan indeholde gentagne faktorer, for eksempel:

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D.$

Fra et matematisk synspunkt er en sådan kloning meningsløs, da det i boolsk algebra ikke ændrer resultatet ( ), at gange ethvert udtryk med sig selv og tilføje udtrykket til sig selv, men at tilføje et udtryk med sin egen inverse og multiplicere med sin egen inversion giver konstanter ( ). I det sidste udtryk kan du fjerne gentagne udtryk og faktorer som følger: $x+x=x;x\cdot x=x$ $x+{\bar {x}}=1;x\cdot {\bar {x}}=0$

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D={\bar {A}}\cdot (B{\bar {B)))+(AA)\cdot {\bar {B}}E+B{\bar {C}}D={\bar {A}}\cdot 0+A{\bar {B}}E+B{\bar {C}}D=A{\bar {B}}E+B{\ bar{C}}D.$

Af denne grund bruges DNF'er med gentagne termer og faktorer normalt kun til hjælpeformål, for eksempel i den analytiske transformation af udtryk.

SDNF er den kanoniske form for at repræsentere en boolsk funktion som en DNF, hvor gentagelser af termer og faktorer er forbudt. Derudover skal hvert led indeholde alle variabler (i direkte eller omvendt form).

Nedenfor er et eksempel på SDNF:

$F(A,B,C,D,E)={\bar {A}}BCDE+A{\bar {B}}C{\bar {D}}E+AB{\bar {C} }D{\bar{E}}.$

Meningen med SDNF er det

for hver specifik funktion er dens SDNF unik og utvetydig;
SDNF har en en-til-en korrespondance med sandhedstabellen for en funktion. Hvert led i SDNF svarer til én række i sandhedstabellen, hvor funktionen er lig med én. Således er antallet af termer i SDNF lig med antallet af enhedsværdier, som en boolsk funktion tager i sit definitionsdomæne;
SDNF fås elementært fra funktionens sandhedstabel;
SDNF er praktisk som et basisudtryk til at minimere en funktion; det er især nemt at finde termer, der er egnede til at "lime" i den.

Eksempel på at finde SDNF

For at opnå SDNF for en funktion, er det nødvendigt at kompilere dens sandhedstabel . Tag for eksempel en af sandhedstabellerne:

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	en
0	0	en	en
0	en	0	en
0	en	en	0
en	0	0	0
en	0	en	0
en	en	0	en
en	en	en	0

I cellerne i resultatet er kun de kombinationer markeret, der bringer det logiske udtryk til tilstanden ét. Yderligere overvejes værdierne af variabler, hvor funktionen er lig med 1. Hvis værdien af en variabel er lig med 0, skrives den med inversion. Hvis værdien af variablen er 1, så ingen inversion. $f(x_{1},x_{2},x_{3})$

Den første linje indeholder 1 i det angivne felt. Værdierne for alle tre variable er noteret, disse er:

$x_{1}=0$
$x_{2}=0$
$x_{3}=0$

Nulværdier - her er alle variable repræsenteret af nuller - er skrevet i det endelige udtryk med det omvendte af denne variabel. Det første medlem af SDNF af den betragtede funktion ser sådan ud: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$

Andet medlemsvariable:

$x_{1}=0$
$x_{2}=0$
$x_{3}=1$

$x_{3}$ i dette tilfælde vil blive repræsenteret uden inversion: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}$

Således analyseres alle celler . Den perfekte DNF for denne funktion vil være disjunktionen af alle resulterende termer (elementære konjunktioner ). $f(x_{1},x_{2},x_{3})$

Den perfekte DNF for denne funktion er:

$f(x_{1},x_{2},x_{3})=({\overline {x_{1))}\land {\overline {x_{2))}\land {\overline { x_{3}}})\vee ({\overline {x_{1}}}\land {\overline {x_{2}}}\land x_{3})\vee ({\overline {x_{1} }}\land x_{2}\land {\overline {x_{3}}})\vee (x_{1}\land x_{2}\land {\overline {x_{3}}})$

Se også

Noter

↑ Vinogradova M.S., Tkachev S.B. booleske funktioner. - M . : Forlag af MSTU im. N.E. Bauman, 2007. - 32 s.
↑ Matematisk logik . - Perm: Publishing House of PSTU, 1998. - 17 s. Arkiveret 9. april 2016 på Wayback Machine