Shannon expansion

Inom matematik är Shannon -nedbrytning eller Shannon -nedbrytning i en variabel en metod för att representera en boolesk funktion av variabler som summan av två underfunktioner av andra variabler. Även om denna metod ofta tillskrivs Claude Shannon , bevisade Boole det mycket tidigare, och själva möjligheten till en sådan expansion i någon av variablerna följer direkt av möjligheten att definiera valfri boolesk funktion med hjälp av sanningstabellen . $x_{i}$ $n$ $(n-1)$

Nedbrytning

Shannon-expansionen i termer av en variabel är baserad på det faktum att sanningstabellen för en boolesk funktion av binära variabler kan delas upp i två delar så att den första delen endast innehåller de indatakombinationer där variabeln alltid tar värdet , och den andra delen innehåller endast de kombinationer av ingångskombinationer där variabeln alltid tar värdet (och dess inverterade värde tar värdet ). Som ett resultat blir följande identitet giltig , kallad Shannon-expansionen: $x_{i}$ $n$ $x_{i}$ $ett$ $x_{i}$ $0$ ${\overline {x_{i))}$ $ett$

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

var är den booleska funktionen som ska expanderas, och är de icke-inverterade och inverterade värdena för variabeln med avseende på vilken expansionen utförs, och och är det positiva respektive negativa komplementet för funktionen med avseende på variabeln . I Shannon-expansionen anger symbolerna och operationerna för konjunktion ("AND", AND) respektive disjunktion ("OR", OR), men identiteten förblir giltig när man ersätter disjunktion med strikt disjunktion (modulo 2 addition, exklusiv " OR", XOR), eftersom termerna aldrig får det sanna värdet samtidigt (eftersom det positiva komplementet kombineras med konjunktion med , och det negativa komplementet kombineras med konjunktion med dess invers ). $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))}$

Positivt komplement bestäms av den del av sanningstabellen där variabeln alltid antar ett värde (och dess inverterade värde antar värdet av ): $f_{x_{i))(x)$ $x_{i}$ $ett$ ${\overline {x_{i))}$ $0$

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

Det negativa komplementet bestäms av resten av tabellen, där variabeln alltid får ett värde (och det inverterade värdet får ett värde av ): $f_{\overline {x_{i))}(x)$ $x_{i}$ $0$ ${\overline {x_{i))}$ $ett$

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

Shannon-nedbrytningssatsen är, trots all dess självklarhet, en viktig idé i boolesk algebra för att representera booleska funktioner som binära beslutsdiagram , lösa problemet med tillfredsställelse av booleska formler och implementera många andra tekniker relaterade till datorteknik och formell verifiering av digitala kretsar. .

I artikeln "The Synthesis of Two-Terminal Switching Circuits" [1] beskrev Shannon nedbrytningen av en funktion med avseende på en variabel som: $x_{1}$

f(x_{1},x_{2},\dots ,x_{n})=x_{1}\cdot f(1,x_{2},\dots ,x_{n})+{\ överlinje {x_{1}}}\cdot f(0,x_{2},\dots ,x_{n})

följt av expansion i två variabler, och noterade att expansionen kunde fortsätta i valfritt antal variabler.

Nedbrytningsexempel

Låt en boolesk funktion av tre variabler , och , ges som en perfekt disjunktiv normalform , det vill säga som en disjunktion av elementära konjunktioner, som var och en innehåller varje variabel eller dess komplement (inversion) i samma ordning: $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}}

För expansion i en variabel kan denna funktion skrivas om till en summa: $x$

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

efter att ha erhållit expansionen av en boolesk funktion i en variabel genom att helt enkelt tillämpa den fördelande egenskapen för en variabel och dess komplement (inversion) : $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 {\överlinje {z)))

På liknande sätt utförs expansionen av funktionen i termer av variabeln eller : $f$ $y$ $z$

f=y(x\cdot z+{\overline {x}}\cdot z)+{\overline {y}}(x\cdot z+{\overline {x}}\cdot z+{\overline {x ))\cdot {\överlinje {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}})

I sin tur, för var och en av de återstående funktionerna i ett mindre antal variabler, kan man fortsätta expansionen i en av de återstående variablerna.

Generalisering

Variabeln i expansionen av en boolesk funktion kan inte bara vara individuella variabler som ingår i denna funktion, utan alla multiplexeringsvillkor. Det är till exempel känt expansion genom uttryck (x > y) och dess negation.

Se även

Anteckningar

↑ Shannon, Claude E. Syntesen av tvåterminala kopplingskretsar // Bell System Technical Journal : journal. — Vol. 28 . - S. 59-98 .

Länkar

Shannons nedbrytningsexempel med multiplexorer.
Optimera sekventiella cykler genom Shannon Decomposition and Retiming (PDF) papper på ansökan.