Shannon ekspansion

I matematik er Shannon- dekomponering eller Shannon- nedbrydning i en variabel en metode til at repræsentere en boolsk funktion af variabler som summen af to underfunktioner af andre variable. Selvom denne metode ofte tilskrives Claude Shannon , beviste Boole det meget tidligere, og selve muligheden for en sådan udvidelse i enhver af variablerne følger direkte af muligheden for at definere enhver boolsk funktion ved hjælp af sandhedstabellen . $x_{i}$ $n$ $(n-1)$

Dekomponering

Shannon-udvidelsen i form af en variabel er baseret på det faktum, at sandhedstabellen for en boolsk funktion af binære variable kan opdeles i to dele, således at den første del kun indeholder de inputkombinationer, hvor variablen altid tager værdien , og den anden del indeholder kun de inputkombinationer, hvor variablen altid tager værdien (og dens inverterede værdi tager værdien ). Som et resultat bliver følgende identitet gyldig , kaldet Shannon-udvidelsen: $x_{i}$ $n$ $x_{i}$ $en$ $x_{i}$ $0$ ${\overline {x_{i))}$ $en$

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

hvor er den boolske funktion, der skal udvides, og er de ikke-inverterede og inverterede værdier af den variabel, som udvidelsen udføres i forhold til, og og er henholdsvis det positive og negative komplement for funktionen i forhold til variablen . I Shannon-udvidelsen betegner symbolerne og operationerne for henholdsvis konjunktion ( "AND", AND) og disjunktion ("OR", OR), men identiteten forbliver gyldig, når man erstatter disjunktion med streng disjunktion (modulo 2 addition, exclusive " OR", XOR), da termerne aldrig får den sande værdi på samme tid (fordi det positive komplement kombineres med konjunktion med , og det negative komplement kombineres med konjunktion med dets inverse ). $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 bestemmes af den del af sandhedstabellen, hvor variablen altid antager en værdi (og dens inverterede værdi antager værdien af ): $f_{x_{i))(x)$ $x_{i}$ $en$ ${\overline {x_{i))}$ $0$

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

Det negative komplement bestemmes af resten af tabellen, hvor variablen altid antager en værdi (og den inverterede værdi antager en værdi på ): $f_{\overline {x_{i))}(x)$ $x_{i}$ $0$ ${\overline {x_{i))}$ $en$

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

Shannon-nedbrydningssætningen er, trods al dens åbenbarhed, en vigtig idé i boolsk algebra til at repræsentere boolske funktioner som binære beslutningsdiagrammer , løse problemet med tilfredsstillelse af boolske formler og implementere mange andre teknikker relateret til computerteknik og formel verifikation af digitale kredsløb .

I artiklen "The Synthesis of Two-Terminal Switching Circuits" [1] beskrev Shannon nedbrydningen af en funktion med hensyn til en variabel som: $x_{1}$

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

efterfulgt af udvidelse i to variable, og bemærkede, at udvidelsen kunne fortsættes i et hvilket som helst antal variable.

Nedbrydningseksempel

Lad en boolsk funktion af tre variable , og , gives som en perfekt disjunktiv normalform , det vil sige som en disjunktion af elementære konjunktioner, som hver indeholder hver variabel eller dens komplement (inversion) i samme rækkefølge: $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}}

For udvidelse i en variabel kan denne funktion omskrives som en sum: $x$

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

efter at have opnået udvidelsen af en boolsk funktion i en variabel ved blot at anvende den distributive egenskab for en variabel og dens 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 {\overline {z)))

På samme måde udføres udvidelsen af funktionen i form af variablen 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 {\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}})

Til gengæld kan man for hver af de resterende funktioner i et mindre antal variabler fortsætte udvidelsen i en af de resterende variable.

Generalisering

Variablen i udvidelsen af en boolesk funktion kan ikke kun være individuelle variable, der er inkluderet i denne funktion, men enhver multiplekseringsbetingelse. Det er f.eks. kendt ekspansion ved udtryk (x > y) og dets negation.

Se også

Noter

↑ Shannon, Claude E. Syntesen af koblingskredsløb med to terminaler // Bell System Technical Journal : journal. — Bd. 28 . - S. 59-98 .