Dokonalá disjunktivní normální forma

Dokonalá disjunktivní normální forma (PDNF) je jednou z forem reprezentace funkce algebry logiky (booleovské funkce) ve formě logického výrazu. Jde o speciální případ DNF , který splňuje následující tři podmínky [1] :

nemá shodné pojmy (elementární spojky);
v každém termínu nejsou žádné opakující se proměnné;
každý člen obsahuje všechny proměnné, na kterých závisí booleovská funkce (každá proměnná může být zahrnuta do termínu buď v přímé nebo inverzní podobě).

Jakýkoli booleovský vzorec , který není identicky nepravdivý, může být redukován na SDNF a jedinečným způsobem, tj. pro jakoukoli splnitelnou funkci logické algebry, existuje vlastní SDNF, a to jediný [2] .

Stručná teorie

DNF je „součet produktů“ a operace AND (konjunkce) funguje jako operace „násobení“ a operace OR (disjunkce) funguje jako operace „sčítání“. Faktory jsou různé proměnné a mohou být zahrnuty do produktu v přímé i inverzní formě.

Níže je uveden příklad DNF:

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

Obecně řečeno, DNF může obsahovat opakující se termíny a každý termín může obsahovat opakující se faktory, například:

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

Z matematického hlediska je takové klonování nesmyslné, protože v Booleově algebře násobení libovolného výrazu samo o sobě a přidání výrazu k sobě nemění výsledek ( ), ale přidání výrazu s vlastní inverzí a násobení vlastní inverzí dává konstanty ( ). V posledním výrazu můžete odstranit opakované výrazy a faktory takto: $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.$

Z tohoto důvodu se DNF s opakovanými termíny a faktory obvykle používají pouze pro pomocné účely, například při analytické transformaci výrazů.

SDNF je kanonická forma reprezentace booleovské funkce jako DNF, ve které je zakázáno opakování termínů a faktorů. Každý člen navíc musí obsahovat všechny proměnné (v přímé nebo inverzní podobě).

Níže je uveden příklad SDNF:

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

Význam SDNF je takový

pro každou konkrétní funkci je její SDNF jedinečný a jednoznačný;
SDNF má vzájemnou shodu s pravdivostní tabulkou funkce. Každý člen v SDNF odpovídá jednomu řádku v pravdivostní tabulce, kde se funkce rovná jedné. Počet termínů v SDNF se tedy rovná počtu jednotkových hodnot, které má booleovská funkce ve své doméně definice;
SDNF se elementárně získává z pravdivostní tabulky funkce;
SDNF je vhodný jako základní výraz pro minimalizaci funkce, obzvláště snadno se v něm najdou termíny vhodné pro "zalepení".

Příklad nalezení SDNF

Aby bylo možné získat SDNF funkce, je nutné sestavit její pravdivostní tabulku . Vezměte si například jednu z pravdivostních tabulek:

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

V buňkách výsledku jsou označeny pouze ty kombinace, které uvádějí logický výraz do stavu jedna. Dále jsou uvažovány hodnoty proměnných, při kterých je funkce rovna 1. Pokud je hodnota proměnné rovna 0, pak je zapsána s inverzí. Pokud je hodnota proměnné 1, pak žádná inverze. $f(x_{1},x_{2},x_{3})$

První řádek obsahuje 1 v zadaném poli. Hodnoty všech tří proměnných jsou zaznamenány, jsou to:

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

Nulové hodnoty - zde jsou všechny proměnné reprezentovány nulami - jsou ve výsledném výrazu zapsány inverzí této proměnné. První člen SDNF uvažované funkce vypadá takto: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$

Proměnné druhého člena:

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

$x_{3}$ v tomto případě bude reprezentován bez inverze: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}$

Takto jsou analyzovány všechny buňky . Dokonalým DNF této funkce bude disjunkce všech výsledných členů (elementárních spojek ). $f(x_{1},x_{2},x_{3})$

Perfektní DNF této funkce je:

$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}}})$

Viz také

Poznámky

↑ Vinogradova M.S., Tkachev S.B. Booleovské funkce. - M . : Vydavatelství MSTU im. N.E. Bauman, 2007. - 32 s.
↑ Matematická logika . - Perm: Nakladatelství PSTU, 1998. - 17 s. Archivováno 9. dubna 2016 na Wayback Machine