Věta o expanzi Booleů - Booles expansion theorem - Wikipedia

Booleova věta o expanzi, často označované jako Shannonova expanze nebo rozklad, je identita: ${ displaystyle F = x cdot F_ {x} + x ' cdot F_ {x'}}$, kde ${ displaystyle F}$ je jakýkoli Booleovská funkce, ${ displaystyle x}$ je proměnná, ${ displaystyle x '}$ je doplňkem ${ displaystyle x}$, a ${ displaystyle F_ {x}}$a ${ displaystyle F_ {x '}}$ jsou ${ displaystyle F}$ s argumentem ${ displaystyle x}$ nastaven na ${ displaystyle 1}$ a do ${ displaystyle 0}$ resp.

Podmínky ${ displaystyle F_ {x}}$ a ${ displaystyle F_ {x '}}$ se někdy nazývají pozitivní a negativní Shannonovy kofaktory, respektive, z ${ displaystyle F}$ s ohledem na ${ displaystyle x}$. Jedná se o funkce počítané pomocí omezit operátor, ${ displaystyle operatorname {omezit} (F, x, 0)}$ a ${ displaystyle operatorname {omezit} (F, x, 1)}$ (vidět ocenění (logika) a částečná aplikace ).

Nazývá se „základní věta booleovské algebry“.^[1] Kromě teoretického významu to připravilo cestu pro binární rozhodovací diagramy, řešitelé uspokojivosti a mnoho dalších příslušných technik počítačové inženýrství a formální ověření digitálních obvodů.

Výrok věty

Explicitnější způsob vyjádření věty je:

${ displaystyle f (X_ {1}, X_ {2}, dots, X_ {n}) = X_ {1} cdot f (1, X_ {2}, dots, X_ {n}) + X_ { 1} ' cdot f (0, X_ {2}, tečky, X_ {n})}$

Variace a důsledky

Formulář XOR

Výrok také platí, když disjunkce "+" se nahrazuje XOR operátor:

${ displaystyle f (X_ {1}, X_ {2}, dots, X_ {n}) = X_ {1} cdot f (1, X_ {2}, dots, X_ {n}) oplus X_ {1} ' cdot f (0, X_ {2}, dots, X_ {n})}$

Duální forma

Existuje dvojí forma expanze Shannon (která nemá související formu XOR):

${ displaystyle f (X_ {1}, X_ {2}, dots, X_ {n}) = (X_ {1} + f (0, X_ {2}, dots, X_ {n})) cdot (X_ {1} + f (1, X_ {2}, dots, X_ {n}))}$

Opakovaná aplikace pro každý argument vede k Součet produktů (SoP) kanonická forma booleovské funkce ${ displaystyle f}$. Například pro ${ displaystyle n = 2}$ to by bylo

${ displaystyle { begin {aligned} f (X_ {1}, X_ {2}) & = X_ {1} cdot f (1, X_ {2}) + X_ {1} ' cdot f (0, X_ {2}) & = X_ {1} X_ {2} cdot f (1,1) + X_ {1} X_ {2} ' cdot f (1,0) + X_ {1}' X_ {2} cdot f (0,1) + X_ {1} 'X_ {2}' cdot f (0,0) end {zarovnáno}}}$

Stejně tak použití duální formy vede k Součin součtů (PoS) kanonická forma (pomocí zákon o distribuci z ${ displaystyle +}$ přes ${ displaystyle cdot}$):

${ displaystyle { begin {aligned} f (X_ {1}, X_ {2}) & = (X_ {1} + f (0, X_ {2})) cdot (X_ {1} 'f ( 1, X_ {2})) & = (X_ {1} + X_ {2} + f (0,0)) cdot (X_ {1} + X_ {2} '+ f (0,1) ) cdot (X_ {1} '+ X_ {2} + f (1,0)) cdot (X_ {1}' + X_ {2} '+ f (1,1)) end {zarovnáno}} }$

Vlastnosti kofaktorů

Lineární vlastnosti kofaktorů:

Pro booleovskou funkci F který se skládá ze dvou booleovských funkcí G a H platí to:

Li ${ displaystyle F = H '}$ pak ${ displaystyle F_ {x} = H '_ {x}}$

Li ${ displaystyle F = G cdot H}$ pak ${ displaystyle F_ {x} = G_ {x} cdot H_ {x}}$

Li ${ displaystyle F = G + H}$ pak ${ displaystyle F_ {x} = G_ {x} + H_ {x}}$

Li ${ displaystyle F = G oplus H}$ pak ${ displaystyle F_ {x} = G_ {x} oplus H_ {x}}$

Vlastnosti unate funkcí:

Li F je unate funkce a...

Li F je pak pozitivní unate ${ displaystyle F = x cdot F_ {x} + F_ {x '}}$

Li F je pak negativní unate ${ displaystyle F = F_ {x} + x ' cdot F_ {x'}}$

Operace s kofaktory

Booleovský rozdíl:

Booleovský rozdíl nebo boolovský derivát funkce F vzhledem k doslovnému x je definována jako:

${ displaystyle { frac { částečné F} { částečné x}} = F_ {x} oplus F_ {x '}}$

Univerzální kvantifikace:

Univerzální kvantifikace F je definována jako:

${ displaystyle forall xF = F_ {x} cdot F_ {x '}}$

Existenční kvantifikace:

Existenční kvantifikace F je definována jako:

${ displaystyle existuje xF = F_ {x} + F_ {x '}}$

Dějiny

George Boole představil tuto expanzi ve svém Proposition II, „Rozšířit nebo vyvinout funkci zahrnující libovolný počet logických symbolů“ Zákony myšlení (1854),^[2] a bylo „široce používáno Booleem a dalšími logiky devatenáctého století“.^[3]

Claude Shannon zmínil tuto expanzi, mimo jiné booleovské identity, v dokumentu z roku 1948,^[4] a ukázal přepínací síťové interpretace identity. V literatuře počítačového designu a teorie přepínání je identita často nesprávně připisována Shannonovi.^[3]

Aplikace na spínací obvody

1. Binární rozhodovací diagramy plynou ze systematického používání této věty
2. Libovolnou booleovskou funkci lze implementovat přímo do a spínací obvod pomocí hierarchie základních multiplexer opakovanou aplikací této věty.

Poznámky

Viz také

• Reed – Mullerova expanze

externí odkazy

• Shannonův rozklad Příklad s multiplexery.
• Optimalizace sekvenčních cyklů Shannonovým rozkladem a retimováním (PDF) Papír o aplikaci.