Tökéletes diszjunktív normál forma

A tökéletes diszjunktív normálforma (PDNF) a logikai algebra függvényének (Boole-függvény) logikai kifejezés formájában történő megjelenítésének egyik formája. Ez a DNF egy speciális esete, amely teljesíti a következő három feltételt [1] :

nincsenek benne azonos kifejezések (elemi kötőszók);
nincsenek ismétlődő változók minden tagban;
minden tag tartalmazza az összes változót, amelytől a Boole-függvény függ (minden változó szerepelhet a kifejezésben direkt vagy inverz formában).

Bármely Boole-képlet , amely nem azonosan hamis, redukálható SDNF-re, és egyedi módon, azaz a logikai algebra bármely kielégíthető függvényéhez létezik saját SDNF, és az egyetlen [2] .

Rövid elmélet

A DNF a „szorzatok összege”, és az ÉS művelet (kötőszó) „szorzás” műveletként, az VAGY művelet (disjunkció) pedig „összeadás” műveletként működik. A faktorok különféle változók, amelyek direkt és inverz formában is szerepelhetnek a termékben.

Az alábbiakban egy példa látható a DNF-re:

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

Általánosságban elmondható, hogy a DNF tartalmazhat ismétlődő kifejezéseket, és minden kifejezés tartalmazhat ismétlődő tényezőket, például:

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

Matematikai szempontból az ilyen klónozás értelmetlen, mivel a Boole-algebrában bármely kifejezés önmagával való szorzása és a kifejezés önmagához való hozzáadása nem változtatja meg az eredményt ( ), de ha hozzáadunk egy kifejezést a saját inverzével és megszorozzuk a saját inverzével állandókat ad ( ). Az utolsó kifejezésben a következőképpen távolíthatja el az ismétlődő kifejezéseket és tényezőket: $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{\ bár{C}}D.$

Emiatt az ismétlődő kifejezéseket és faktorokat tartalmazó DNF-eket általában csak segédcélokra használják, például a kifejezések analitikus átalakítása során.

Az SDNF a Boole-függvény DNF-ként való megjelenítésének kanonikus formája, amelyben a kifejezések és tényezők ismétlése tilos. Ezenkívül minden kifejezésnek tartalmaznia kell minden változót (direkt vagy inverz formában).

Az alábbiakban egy példa az SDNF-re:

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

Az SDNF jelentése az

minden egyes funkció esetében az SDNF egyedi és egyértelmű;
Az SDNF egy az egyhez megfelel egy függvény igazságtáblázatának. Az SDNF-ben minden tag egy sornak felel meg az igazságtáblázatban, ahol a függvény egyenlő eggyel. Így a kifejezések száma az SDNF-ben megegyezik azon egységértékek számával, amelyeket egy Boole-függvény a definíciós tartományában vesz fel;
Az SDNF alapvetően a függvény igazságtáblázatából származik;
Az SDNF alkalmas alapkifejezésként egy függvény minimalizálására, különösen könnyű megtalálni benne a "ragasztásra" alkalmas kifejezéseket.

Példa az SDNF megtalálására

Egy függvény SDNF értékének megszerzéséhez le kell fordítani annak igazságtáblázatát . Például vegyük az egyik igazságtáblázatot:

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

Az eredmény celláiban csak azok a kombinációk vannak megjelölve, amelyek a logikai kifejezést egy állapotba hozzák. Továbbá figyelembe veszik a változók értékeit, amelyeknél a függvény egyenlő 1-gyel. Ha egy változó értéke 0, akkor inverzióval írjuk. Ha a változó értéke 1, akkor nincs inverzió. $f(x_{1},x_{2},x_{3})$

Az első sor 1 -et tartalmaz a megadott mezőben. Mindhárom változó értéke fel van jegyezve, ezek a következők:

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

A nulla értékeket - itt minden változót nullák képviselnek - a végső kifejezésben ennek a változónak az inverze írják be. A vizsgált függvény SDNF első tagja így néz ki: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$

Második tag változók:

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

$x_{3}$ ebben az esetben inverzió nélkül ábrázoljuk: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}$

Így az összes sejtet elemzik . Ennek a függvénynek a tökéletes DNF-je az összes eredményül kapott tag diszjunkciója lesz (elemi kötőszó ). $f(x_{1},x_{2},x_{3})$

Ennek a funkciónak a tökéletes DNF -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}}})$

Lásd még

Jegyzetek

↑ Vinogradova M.S., Tkachev S.B. Boole-függvények. - M . : MSTU kiadó im. N.E. Bauman, 2007. - 32 p.
↑ Matematikai logika . - Perm: PSTU Kiadó, 1998. - 17 p. Archiválva : 2016. április 9. a Wayback Machine -nál

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

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

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