Shannonova expanze

V matematice je Shannonova dekompozice nebo Shannonova dekompozice v proměnné metoda reprezentující booleovskou funkci proměnných jako součet dvou podfunkcí jiných proměnných. Ačkoli je tato metoda často připisována Claudu Shannonovi , Boole to dokázal mnohem dříve a samotná možnost takového rozšíření v kterékoli z proměnných vyplývá přímo z možnosti definovat libovolnou booleovskou funkci pomocí pravdivostní tabulky . $x_{i}$ $n$ $(n-1)$

Rozklad

Shannonova expanze z hlediska proměnné je založena na skutečnosti, že pravdivostní tabulku pro booleovskou funkci binárních proměnných lze rozdělit na dvě části tak, že první část obsahuje pouze ty vstupní kombinace, ve kterých má proměnná vždy hodnotu , a druhá část obsahuje pouze ty kombinace vstupních kombinací, ve kterých má proměnná vždy hodnotu (a její převrácená hodnota nabývá hodnoty ). V důsledku toho se stane platnou následující identita , nazývaná Shannonova expanze: $x_{i}$ $n$ $x_{i}$ $jeden$ $x_{i}$ $0$ ${\overline {x_{i))}$ $jeden$

f(x)=x_{i}\cdot f_{x_{i}}(x)+{\overline {x_{i}}}\cdot f_{\overline {x_{i}}}(x )=({\overline {x_{i}}}+f_{x_{i}}(x))\cdot ({x_{i}}+f_{\overline {x_{i}}}(x))

kde je booleovská funkce, která má být rozšířena, a jsou neinvertované a invertované hodnoty proměnné, vzhledem k níž se expanze provádí, a jsou kladným a záporným doplňkem funkce s ohledem na proměnnou . V Shannonově expanzi symboly a označují operace konjunkce („AND“, AND) a disjunkce („OR“, OR), ale identita zůstává platná i při nahrazení disjunkce striktní disjunkcí (sčítání modulo 2, výhradní „ OR", XOR), protože termíny nikdy nenabývají skutečné hodnoty současně (protože kladný doplněk je kombinován konjunkcí s , a záporný doplněk je kombinován konjunkcí s jeho inverzní ). $f(x)$ $x_{i}$ ${\overline {x_{i))}$ $f_{x_{i}}(x)$ $f_{\overline {x_{i))}(x)$ $f(x)$ $x_{i}$ $\cdot$ $+$ $f_{x_{i}}(x)$ $x_{i}$ $f_{\overline {x_{i))}(x)$ ${\overline {x_{i))}$

Kladný doplněk je určen tou částí pravdivostní tabulky, ve které proměnná vždy nabývá hodnoty (a její převrácená hodnota nabývá hodnoty ): $f_{x_{i}}(x)$ $x_{i}$ $jeden$ ${\overline {x_{i))}$ $0$

f_{x_{i}}(x)=f(x_{1},...,x_{i-1},1,x_{i+1},...,x_{n})

Záporný doplněk je určen zbytkem tabulky, kde proměnná vždy nabývá hodnoty (a převrácená hodnota nabývá hodnoty ): $f_{\overline {x_{i))}(x)$ $x_{i}$ $0$ ${\overline {x_{i))}$ $jeden$

f_{\overline {x_{i}}}(x)=f(x_{1},...,x_{i-1},0,x_{i+1},...,x_ {n})

Shannonova věta o rozkladu je přes veškerou svou samozřejmost důležitou myšlenkou v Booleově algebře pro reprezentaci booleovských funkcí jako binárních rozhodovacích diagramů , řešení problému splnitelnosti booleovských vzorců a implementaci mnoha dalších technik souvisejících s počítačovým inženýrstvím a formální verifikací digitálních obvodů . .

V článku „The Synthesis of Two-Terminal Switching Circuits“ [1] Shannon popsal rozklad funkce vzhledem k proměnné jako: $x_{1}$

f(x_{1},x_{2},\tečky ,x_{n})=x_{1}\cdot f(1,x_{2},\tečky ,x_{n})+{\ overline {x_{1}}}\cdot f(0,x_{2},\tečky ,x_{n})

následovala expanze ve dvou proměnných a poznamenal, že expanze mohla pokračovat v libovolném počtu proměnných.

Příklad rozkladu

Nechť je booleovská funkce tří proměnných , a , dána jako dokonalý disjunktivní normální tvar , tedy jako disjunkce elementárních spojek, z nichž každá obsahuje každou proměnnou nebo její doplněk (inverzi) ve stejném pořadí: $X$ $y$ $z$

f=x\cdot y\cdot z+x\cdot {\overline {y}}\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot z+{\overline {x }}\cdot y\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot {\overline {z}}

Pro expanzi v proměnné lze tuto funkci přepsat jako součet: $X$

f=x\cdot g_{x}+{\overline {x}}\cdot g_{\overline {x}}

získání expanze booleovské funkce v proměnné jednoduchým použitím distributivní vlastnosti pro proměnnou a jejího doplňku (inverze) : $F$ $X$ $X$ $X'$

f=x(y\cdot z+{\overline {y}}\cdot z)+{\overline {x}}({\overline {y}}\cdot z+y\cdot z+{\overline { y))\cdot {\overline {z)))

Podobně se expanze funkce z hlediska proměnné nebo provádí : $F$ $y$ $z$

f=y(x\cdot z+{\overline {x}}\cdot z)+{\overline {y}}(x\cdot z+{\overline {x}}\cdot z+{\overline {x ))\cdot {\overline {z)))

f=z(x\cdot y+x\cdot {\overline {y}}+{\overline {x}}\cdot {\overline {y}}+{\overline {x}}\cdot { \overline {y)))+{\overline {z}}({\overline {x}}\cdot {\overline {y}})

Na druhé straně, pro každou ze zbývajících funkcí v menším počtu proměnných lze pokračovat v expanzi v jedné ze zbývajících proměnných.

Generalizace

Proměnnou v rozšíření booleovské funkce mohou být nejen jednotlivé proměnné zahrnuté v této funkci, ale jakákoli podmínka multiplexování. Například je to znát expanze výrazem (x > y) a jeho negace.

Viz také

Poznámky

↑ Shannon, Claude E. Syntéza dvousvorkových spínacích obvodů // Bell System Technical Journal : deník. — Sv. 28 . - str. 59-98 .

Odkazy

Shannonův příklad rozkladu s multiplexery.
Optimalizace sekvenčních cyklů prostřednictvím Shannonova rozkladu a přečasování (PDF) Referát o aplikaci.