Shannonův rozvoj

Většina návrhů a řešení logických obvodu v praxi začíná sestavením pravdivostní tabulky. Teprve tabulka, která je popisem požadované reakce logické sítě na různé vstupní podmínky (kombinace vstupních proměnných), je podkladem pro sestavení logických rovnic. Jednu z velmi vhodných cest představuje užívání Karnaughovy mapy, která na základě určitých pravidel představuje grafickou interpretaci pravdivostní tabulky. Mapa umožňuje podstatnou část algebraického řešení logické rovnice nahradit efektivnějším a mnohem přehlednějším řešením grafickým. Pochopit princip Karnaughovy mapy, jejího formátu, zápisu proměnných i vlastní práce s ní pomůže princip Shannona rozvoje.

Jeho smyslem je především možnost rozložit složité logické funkce podle zvolené proměnné do soustavy dvou funkcí. Přitom se proměnné z obou funkcí vytýká a tak v nich není obsažena, tím se zmenší počet proměnných o jednu, jde tedy o podstatné zjednodušení. Funkci lze přitom rozkládat jak podle libovolné proměnné, tak postupně podle všech proměnných. Z praktických důvodů se operace používá téměř výlučně u funkcí v disjukčním tvaru. Obecný postup rozkladu podle jedné proměnné (např. A) naznačuje vztah:

f_A [A, B, C …] = A . f [1, B, C …] + /A . f [0, B, C …]

Zvolené proměnné rozložíme tedy tak, že ji v tom tvaru, v jakém se vyskytuje v původním výrazu, vytkneme před první výraz a v negovaném tvaru před výraz druhý. Do obou výrazů opíšeme původní tvar s tím rozdíle, že do prvního zapisujeme konstantu 1 a do druhého 0 za všechny výskyty proměnné (ať v přímém nebo inverzním tvaru), podle které se provádí rozvoj. Obsah funkce se rozvojem nemění.

Po úplném rozvoji podle jedné proměnné získáme disjukční normální tvar funkce nebo výrazu - DNT. Postup je v tomto případě přesně opačný než při zjednodušování výrazu. Nevyužíváme například operací jedné proměnné, abychom ve funkci DNT získali co největší počet konjukcí.

Jestliže budeme v rozkladu systematicky pokračovat až do vyčerpání všech proměnných, rozložíme nakonec funkci do úplného normálního disjukčního tvaru - UDNT. Ani nyní se obsah logické funkce nemění.

Pro úplnost je třeba dodat, že obdobná pravidla platí pro duální, konjukční rozvoj. V praxi se s výhodou užívá možnosti vzájemné konverze DNT/KNT (konjukčního normální tvar ) a UDNT/UKNT využitím inverze funkce Shannonovým teorémem a její následnou negací.

Disjukční rozvoj si ukážeme na příkladu jednoduchého logického součtu dvou proměnných A + /B.
Nejprve výraz rozložíme podle proměnné A:

f_{DNT (A)} [A + /B] = A(1 + /B) + (0 + /B) = A + A . /B + /A . /B

Stejným postupem rozložíme výraz i podle B:

f_{DNT (B)} [A + /B] = /B(A + 1) + B(A + 0) = A . /B + /B + AB

Lze odvodit, např. minimalizací, že oba hořejší rozvoje (obě funkce DNT) jsou obsahově shodné a odpovídají původní funkci. Vidíme, že DNT tvoří určitý počet vzájemně různých konjukcí, které mají obecně různý počet členů (menší nebo rovný počtu vstupních proměnných) a že podle zvolené proměnné a nakonec i podle početního postupu mohou mít rozvoje různá řešení.

Úplný disjukční normální tvar UDNT získáme navazujícím rozvojem DNT podle zbývající proměnné.

Proto:

f_{UDNT(A, /B)} [A + A . /B + /A . /B] = B(A + A .1 + /A . 1) + B (A + A . 0 + /A . 0) = A . /B + /A . /B + AB

Pokračujeme-li naopak v rozvoji z funkce, zbývá provést rozvoj podle proměnné A:

f_{UDNT(B, A)} [A . /B + /B + AB] = A(1 . /B + /B + 1 . B) + /A(0 . /B + /B + B) = A . /B + AB + /A . /B

UDNT je na rozdíl od DNT charakteristickým tím, že pro každou funkci má právě jedno jediné řešení. Právě to je důležité pro pochopení systému Karnaughovy mapy. Má opět určitý konečný počet vzájemně různých konjukcí, vázaných operátory logického součtu. Jednotlivé konjukce však nyní mají všechny přesně stejný počet členů, který je roven počtu proměnných původní funkce. Každá proměnná se tak podílí na jednoznačném určení konjukce,jejímž je členem. Z hlediska Karnaughovy mapy určuje jednu její souřadnici. Jednotlivé konjukce v UDNT se nazývají mintermy. V rovnicích o dvou, třech či čtyřech proměnných mají mintermy dva, tři či čtyři členy. Tím je také určen počet souřadnic, nutných pro jednoznačné určení polohy mintermu na Karnaughově mapě.

Jistě se ptáte, proč jsme se vlastně Shannonovým rozvojem zabývali. V uvedených příkladech jsme sice odvodili zajímavou funkci dvou proměnných, ale v podstatě složitějším tvaru, než byla původní funkce.To je pravda, podobné úpravy funkcí by nám nic užitečného nepřinesly. Získané poznatky nám však nyní umožní pochopit systém Karnaughovy mapy a její souvislost s algebraickým řešením logické funkce.