Následující "inženýrsko-konstruktivní" smysl lze dát reprezentaci booleovských funkcí pomocí vzorců. Vzorec Ф (x 1, ..., xn) budeme nad libovolně pevnou množinou F považovat za „černou skříňku“, určité zařízení, na jehož vstup jsou přiváděny všechny možné množiny proměnných hodnot a výstup odpovídající těmto množinám hodnot funkce f , představovaný vzorcem Ф (obr. 6.22).
Abychom pochopili, jak funguje „černá skříňka“, musíme analyzovat proces konstrukce vzorce z podformulí. Dostat se k „základním“ podformulím, tj. prvků množiny F, dostaneme se k „cihlům“, konstrukčním prvkům, ze kterých je sestavena „černá skříňka“, která vypočítá funkci f. Každá funkce „základu“ F je vypočítána odpovídajícím „uzlem“, který je považován za nejmenší strukturální jednotku naší „černé skříňky“, a její vnitřní struktura již není analyzována.
Příklad 6.22. Vyberme standardní základ pro množinu F. Potom je vzorec na standardní bázi představující funkci ~ (ekvivalence) sestaven následovně:
Výpočet tímto vzorcem (a proces jeho konstrukce z prvků standardní báze) lze schematicky znázornit, jak je znázorněno na obr. 6.23.
Proměnná x 1 (přesněji hodnota této proměnné) se přivádí na vstup konstrukčního prvku zvaného invertor (obr. 6.24, a) a výpočet negace. Záporná hodnota x 1 odstraněna z výstupu střídače, tj. funkce x 1, se přivádí na jeden ze vstupů spojivky (obr. 6.24, b), na druhý vstup, na který se přivádí proměnná x 2. Na výstupu spojivky se objeví funkce x 1 x 2. Výpočet funkce x 1 x 2 lze vysledovat podobným způsobem. Obě tyto funkce jsou přiváděny na vstupy disjunktoru (obr. 6.24, c), z jehož výstupu je odstraněna funkce x 1 x 2 ∨ x 1 x 2 (to není nic jiného než součet modulo 2: x 1 ⊕ x 2). Nakonec se tato funkce přivádí na vstup střídače, jehož výstup je již funkcí ~ (ekvivalence). #
Tak se dostáváme k myšlence „obvodu“ - matematického modelu kalkulačky booleovské funkce, představovaného určitým vzorcem, sestaveného ze strukturních prvků, z nichž každý vypočítává jednu ze „základních“ booleovských funkcí. V obecném případě „obvod“ vypočítá logický operátor a každá souřadnicová funkce tohoto operátoru je odstraněna z jednoho z výstupů obvodu.
Matematicky je „schéma“ definováno jako směrovaný graf zvláštního druhu, ve kterém jsou označeny vrcholy i oblouky.
Představme si notaci: pokud F je nějaká množina booleovských funkcí, pak pomocí F (n) označíme podmnožinu F skládající se ze všech funkcí n proměnných (n ≥0).
Definice 6.14. Nechť jsou množiny pevné: F (booleovské funkce) a X (booleovské proměnné).
Schéma funkčních prvků na základě F ∪ X (С Ф Э), nebo jednoduše zkrácené na základě F ∪ X, také (F, X) schéma, se nazývá nekontrolovaný směrovaný graf (tj. Síť), jehož každý vrchol je označen jedním z prvků množiny FU X, takže že jsou splněny následující požadavky:
- každý vstup do sítě je označen buď nějakou proměnnou z X, nebo nějakou konstantou z F (0);
- je-li vrchol v síti označen funkcí f v n proměnných (tj. f ∈ F (n)), pak se jeho poloviční stupeň vstupu rovná n a na množině oblouků vstupujících do vrcholu v je číslování (jedna k jedné) dáno tak, že každý oblouk je očíslován od 1 do n.
Pokud je základ implikován, řekneme jednoduše „schéma“. Kromě toho, pokud je sada proměnných fixována „jednou provždy“ a při zvažování různých schémat změníme pouze množinu funkcí F, pak, jak jsme to udělali, zavedením konceptů vzorce a superpozice na daném základě, budeme hovořit o SFE na základě F, za předpokladu, že každý krát, což znamená jednou fixní sadu proměnných X, která (pokud to nepoškodí přesnost) není uvedena.
Nyní definujeme indukcí koncept booleovská funkce vypočítaná vrcholem obvodu .
Definice 6.15. Nechť je uveden CFE S přes základnu F ∪ X, jejíž sada vrcholů je V.
- Předpokládá se, že každý vstup CFE počítá booleovskou funkci, kterou je označen (tj. Nějaká proměnná nebo konstanta).
- Pokud je vrchol v ∈ V označen funkcí f ∈ F (n), oblouk s vstupujícím číslem i (1≤i≤n) pochází z vrcholu ui ∈ V, který počítá funkci gi, pak vrchol v počítá superpozici f (g 1, ..., gn).
Pokud tedy každý vrchol CFE nad F počítá nějakou funkci, pak je v obecném případě zásadní pořadí, ve kterém jsou uvedeny funkce g 1, ..., g n, nahrazené proměnnými funkce f. Je přirozené volat booleovskou funkci f v n proměnných komutativní, pokud si zachovává svou hodnotu pod libovolnou permutací svých proměnných. V tomto případě si nemusíme dělat starosti s číslováním oblouků vstupujících do horní části obvodu, označených takovou funkcí.
Příklad 6.23. Zvažte SPE na obr. 6.25. Vrcholy v 1 a v 2 jsou vstupy SFE. Tyto vrcholy počítají funkce x a y. Poté vrchol v 3, stejně jako vrchol v 4, podle definice 6.15, počítá funkci x | y (Schaefferův tah), a vrchol v 5 (výstup sítě) počítá funkci (x | y) l (x | y), která, je známo, že se rovná spojení x y.
SPE zobrazené na obr. 6.26, má dva výstupy, které počítají funkce (x | x) | (y | y) \u003d x ∨ y a (x | y) | (x | y) \u003d x y.
Definice 6.16. Booleovská funkce vypočítaná pomocí SFE přes základnu F ∪ X, je funkce vypočítaná kterýmkoli z jejích výstupů.
CFE tedy přesně vypočítá, kolik booleovských funkcí, kolik výstupů. SFE na obr. 6.25 vypočítá jednu funkci a SPE na obr. 6,26 - dva.
Obecně platí, že pokud (x 1, ..., x n) je množina všech proměnných, které slouží jako štítky pro vstupy obvodu S přes základnu F ∪ X s m výstupy, CFE S definuje zobrazení logické krychle B n na boolovskou kostku B m, tj. booleovský operátor.
Poznámka 6.10. V některých případech je funkce vypočítaná daným SFE definována poněkud odlišně, za předpokladu, že se jedná o funkci vypočítanou jakýmkoli vrcholem z podmnožiny vybraných vrcholů SFE. Zejména to mohou být výstupy. V každém případě souhlasíme s nakreslením „výstupní“ šipky z vybraných (v uvedeném smyslu) vrcholů obvodu. #
Každý obvod bran tedy vypočítává nějaký booleovský operátor, zejména pokud je počet výstupů obvodu 1, pak počítá nějakou booleovskou funkci.
Lze také dokázat opak: u libovolného booleovského operátoru lze CFE postavit na základě F, kde F je úplná sada, která tento operátor počítá.
Představujeme funkci y 1 na základě Zhegalkinu. Použitím de Morganových zákonů dostaneme
(připomeňme, že součet modulo 2 libovolného sudého počtu stejných členů je roven 0).
y 1 \u003d x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 \u003d x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE pro logický operátor uvedený v tabulce. 6.9, základ Zhegalkinu je znázorněn na Obr. 6.27.
Při navrhování SFE je užitečné mít na paměti numerický parametr zvaný jeho složitost.
Složitost SFE je počet jeho vrcholů, které nejsou vstupy.
Na obr. 6.27 CFE na bázi Zhegalkinu má složitost 5.
Uvažujme nyní o CFE pro stejného operátora na standardní bázi.
Pomocí tabulky (viz tabulka 6.9) zkonstruujeme SDNF pro funkci y 2:
y 2 \u003d x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
Mapa Karnot pro tuto funkci, zobrazená na obr. 6.28 ukazuje, že jej nelze minimalizovat (přesněji výše uvedený SDNF je minimální DNF pro tuto funkci). Ale můžete jít jinou cestou. Můžeme uvažovat o tabulce. 6.9 jako tabulka definující částečnou booleovskou funkci y 2 \u003d y 2 (x 1 x 2 x 3 y 1). Minimalizováním této funkce pomocí
mapa Karnot * zobrazená na obr. 6,29, máme
* Na této mapě jsme označili množiny, na kterých má funkce hodnotu 0, přičemž do příslušných buněk jsme vložili nuly. Chceme tedy znovu upozornit na skutečnost, že bychom si neměli mýlit nuly s pomlčkami: pomlčka v buňce mapy určující dílčí funkci znamená, že hodnota funkce není na této množině definována, tj. není ani 0 ani 1.
y 2 \u003d x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
CFE nad standardní základnou pro uvažovaný booleovský operátor je znázorněn na obr. 6.30. Složitost tohoto SFE je 11. Všimněte si, že vrchol výpočtu funkce y 1 není výstup.
Booleovský operátor v tomto příkladu vypočítá dvouciferný součet (mod 2) tří jednociferných výrazů. Lze jej také považovat za jednobitový binární sčítač - funkční blok vícebitového binárního sčítače - pro dva termíny. Poté je funkce y 1 interpretována jako „přenosový signál“ v nejvýznamnějším bitu. Na obr. 6.31 ukazuje „spojení“ tří SFE (jak je znázorněno na obr. 6.30), pomocí kterého se vypočítá součet dvou třímístných binárních čísel. Konstanta 0 se přivádí na třetí vstup sčítače pro nejméně významný bit a „přenosový signál“ nejvýznamnějšího bitu je nejvýznamnějším bitem součtu, což bude obecně čtyřmístné číslo.
Poznámka 6.11. Pokud navrhujeme SFE na standardním základě a chceme minimalizovat jeho složitost, musíme nejprve vytvořit odpovídající minimální DNF. V tomto případě můžeme vzít v úvahu ještě jedno kritérium, kterým je minimalizován samotný DNF - počet negací. Ze všech minimálních (ve smyslu definice 6.6) DNF je třeba vybrat ty, ve kterých je počet výskytů proměnných pod značkou negace nejmenší. Z hlediska složitosti SFE, která bude postavena na základě minimálního DNF, to znamená, že minimalizuje počet „invertorů“ - vrcholů SFE označených funkcí negace.
Například pro funkci danou Karnotovou mapou (obr. 6.32), do jádra skládajícího se z jednoduchých implikantů x 1 x 2 x 4 a x 1 x 3 x 4, byste měli přidat jednoduchý implikant x 2 x 3 x 4, a ne x 1 x 2 x 3, protože neobsahuje žádná negace.
Funkční diagramy (FS) jsou určeny k transformaci logických informací. Počáteční informace, kódovaná jako diskrétní signály, se přivádí na vstupy obvodu `x n... Poté jsou tyto informace zpracovány a načteny v diskrétní formě z výstupů obvodu „U m(n, m - počet jeho vstupů a výstupů). Zvažte, že FS pracuje ve dvouhodnotové logice a má jeden výstup ( m\u003d 1). Transformaci informací do nich lze specifikovat jako funkci algebry logiky v= F(x n). Místo reléových prvků ve FS se používají funkční prvky (FE), které zpravidla implementují základní logické funkce.
Definice. Analýza se nazývá konstrukce vzorce pro algebru logiky (pokud je to nutné, její pravdivostní tabulka) pro daný FS.
Pro konstrukci vzorce podle daného schématu je nutné reprezentovat vztah mezi FE v FS ve formě substitucí v odpovídajících elementárních funkcích. Předpokládá se, že zpracování informací probíhá postupně od vstupů po výstupy. V reálných obvodech se používají další prvky k zajištění načasování provozu všech FS.
FS analýzu lze provést dvěma způsoby - od vstupů k výstupům a od výstupů ke vstupům. Zvažme první metodu, která používá další označení pro připojení meziobvodu.
Příklad 1. (&, Ú, Ø) se berou jako FE. Analyzujte FE, jejíž fyzikální struktura je uvedena na obrázku 1.19.
Rozhodnutí. Určením mezilehlých připojení FV, jak je znázorněno na obrázku, krok za krokem určujeme signály, které jim odpovídají . V tomto případě přejdeme ze vstupů obvodu na jeho výstup.
Obrázek 1.19
KROK 1. R=`y, Q = `z.
KROK 2. X= X& R= x&`` P= X& y, W=P&Q= x& y&`z.
KROK 3. Y=X& z= X&`` y& z, U=P& z = x& y& z.
KROK 4. Z = YÚ U= X&`` y& zÚ X& y& z.
KROK 5. F = ZÚ Ž= X&`` y& zÚ x& y& zÚ X& y&`z.
Uvažovaný FS tedy implementuje následující vzorec algebry logiky:
F(x, y, z) = x& `` y& zÚ x& y& zÚ x& y& `z.
Nalezený vzorec je SDNF. Vektor jejích hodnot pravdy má tvar (00000111) .
V závislosti na počátečních datech lze rozlišit mezi úkoly syntézy (designu) FS:
1) syntéza obvodů podle daných vzorců,
2) syntéza obvodů pro dané funkce.
Definice. Syntézou PS podle uvedeného vzorce se nazývá konstrukce struktury FS odpovídající danému vzorci algebry logiky.
Řešení těchto problémů se provádí podle algoritmu obráceného k metodě analýzy. Jak je uvedeno v části 1.7, struktura booleovských vzorců umožňuje izomorfně zobrazit pouze systémy s paralelním a sekvenčním spojením prvků. FS, který je izomorfní s odpovídajícím vzorcem, by proto měl obsahovat pouze sloučeniny tohoto typu.
Definice. Syntézou PS pro danou funkci se nazývá konstrukce strukturního diagramu, který implementuje danou funkci logické algebry.
Protože reprezentace funkcí pomocí vzorců je nejednoznačná, má tento problém nejedinečné řešení. Stejně jako v případě reléových obvodů jsou optimální ty FS, skládající se z minimálního počtu FV a spojení mezi nimi. Takový FS lze získat pomocí vzorců s minimálním počtem proměnných.
Co se týče počítačů, budeme zvlášť uvažovat o vzorcích, které jsou optimální ve třídě normálních forem (které se rovnají odpovídajícím minimálním formám), a také o absolutně optimálních vzorcích získaných z minimálních normálních forem jejich další redukcí pomocí zákonů logické algebry. Metody pro získání optimálních vzorců jsou stejné jako v reléových obvodech. Příklad 1 uvažuje FS, který implementuje funkci (00000111) . Tento FS není optimální, protože odpovídající vzorec popisuje SDNF F = x`y z Ú x y zÚ x y`zcož není minimální. Minimalizujeme to, dostaneme následující MDNF: F = x yÚ x z.Odpovídá FS na obrázku 1.20.
Obrázek 1.20
Pokud použijeme distributivní zákon na MDNF, dostaneme vzorec s ještě menším počtem proměnných: F = x(yÚ z). U této funkce se shodoval s MCNF. Odpovídá naprosto optimálnímu schématu
Obrázek 1.21
Je zřejmé, že toto schéma je mnohem jednodušší než původní (obrázek 1.19). Protože syntéza optimálního FS je omezena na konstrukci minimálních vzorců, jsou optimální schémata v jiných základnách konstruována podobným způsobem. Analogy prvního a druhého distributivního zákona algebry logiky pro Schefferovy a webové formuláře lze získat nahrazením v těchto zákonech:
&( X, y)= Ø ½ ( X, y) = ¯ (Ø x,Ø y);
Ú ( X, y)= ½ (Ø X, Ø y) =Ø ¯ ( x, y).
Příklad 2. Vytvořte FS, který implementuje jednobitový binární sčítač dvou čísel pomocí FE odpovídající základu (Ø, ¯), stejně jako v základu (¯).
Rozhodnutí. Označme jednobitová binární čísla dodávaná na vstup prostřednictvím ( x,v). Výstupem by měl být jejich součet v binární soustavě. Li x \u003d1, y \u003d1, pak S = 2 10 \u003d 10 2, proto je pro jeho zobrazení v obecném případě nutné použít dvě binární znaménka a FS musí mít dva výstupy. Pojďme je určit f (nejvýznamnější číslice součtu) a G (nejméně významná číslice). Pravdivostní tabulky funkcí f (x,v), G(x,v):
| x | y | f(x,y) | g(x,y) |
Konstruujeme SVNF funkcí v základu (Ø, ¯). Fmá jednu jednotku ve vektoru pravdy, proto se její forma skládá z jedné složky: F\u003d ¯ (Ř x, Ř v). Funkce GSVNF má formu: g=د(¯( x,Ø v),¯(Ø x,v)). Tyto formy jsou minimální. Při kombinaci vstupů prvků lze funkční diagram znázornit takto:
Obrázek 1.22
V uvažovaném příkladu je nemožné zjednodušit webové normální formy pomocí zákonů logické algebry. V jednofunkčním základu (¯) FS získáme pomocí substituce Ø x= ¯ ( x,x). Odpovídající obvod je znázorněn na obrázku 1.23.
Obrázek 1.23
ÚLOHY
1. Sestavte pomocí FE (&, Ú, Ø) optimální ve třídě normálních forem a absolutně optimální FS, které implementují následující funkce:
a) ( x® y)Å z y; b) ( xÅ y)|z,v) xy® yz; d) X|(yÚ z); e) x®( y® z) ;
f) (10011101); g) (01101011); h) (1110101111111110) .
2. Konstruujte pomocí funkcí FE (Ú, Ø) FS 1.a) -g).
3. Sestavte pomocí funkcí FE (&, Ø) FS 1.a) -g).
4. Vytvořte FS, který implementuje jednobitový binární sčítač (příklad 2) pomocí FE v následujícím tvaru:
a) (&, Ú, Ø), b) (Ú, Ø) , c) (&, Ø), d) ( x | y} .
5. Pomocí FE (&, Ú, Ø) vytvořte FS následujících zařízení:
a) převodník s binárními vstupy ( x,v) a výstup fkterý funguje následovně: při krmení x \u003d0 na výjezdu f = v a při podávání x \u003d1 u vchodu f =`y;
b) selektivní zařízení s binárními vstupy ( x, v) a výstupy f 0 , f 1 , f 2 , f 3, který přijímá kombinaci hodnot ( x y) jako binární číslo i, ležící v rozsahu od 0 do 3. Hodnoty výstupů pro každý i následující: f i\u003d 1 a všechny ostatní f j\u003d 0, (0 £ j3 £, j¹ i).
6. Je možné brát následující sady funkcí jako základ pro konstrukci FS:
a) (1001), (10001110),
b) (0101), (1011), (1101),
c) (1010), (01110001)?
Odůvodněte odpověď.
7. Uveďte příklady řídicích funkcí, jejichž FS nelze sestrojit pouze z FE typu (®).
8. Uveďte příklady řídících funkcí, jejichž FS nelze sestrojit pouze z FE typu (M, º).
9. Dana FS z FE (&, Ú, Ø).
Obrázek 1.24
Je možné z něj vyloučit ekvivalentními převody:
a) všechny prvky (Ø)?
b) všechny prvky (&)?
c) všechny prvky (Ú)?
10. Optimalizujte FS z FE (&, Ú, Ø), jak je znázorněno na obr. 1.25.
Obrázek 1.25
Build FS:
a) optimální ve třídě normálních forem a
b) naprosto optimální.
Následující "inženýrsko-konstruktivní" smysl lze dát reprezentaci booleovských funkcí pomocí vzorců. Vzorec nad libovolně pevnou sadou budeme považovat za „černou skříňku“, jakési zařízení, na jehož vstup se přivádí všechny druhy sad proměnných hodnot a výstup odpovídající těmto sadám hodnot funkce představované vzorcem (obr. 6.22).
Abychom pochopili, jak funguje „černá skříňka“, musíme analyzovat proces konstrukce vzorce z podformulí. Dostat se k „základním“ podformulím, tj. prvky sady, dostaneme se k „stavebním blokům“, konstrukčním prvkům, ze kterých je sestavena „černá skříňka“, která vypočítá funkci. Každá funkce „základu“ je vypočítána odpovídajícím „uzlem“, který je považován za nejmenší strukturální jednotku naší „černé skříňky“, a její vnitřní struktura již není analyzována.
Příklad 6.22. Vyberme si jako základ standardní základnu. Potom je vzorec na standardní bázi představující funkci (ekvivalenci) sestaven následovně:
Výpočet tímto vzorcem (a proces jeho konstrukce z prvků standardní báze) lze schematicky znázornit, jak je znázorněno na obr. 6.23.
Proměnná (přesněji hodnota této proměnné) se přivádí na vstup konstrukčního prvku zvaného invertor (obr. 6.24, a) a výpočet negace. Negativ odstraněný z výstupu měniče, tj. Funkce je přiváděna na jeden ze vstupů spojivky (obr. 6.24.5), na druhý vstup je přiváděna proměnná. Na výstupu spojivky se objeví funkce. Výpočet funkce je sledován podobným způsobem. Obě tyto funkce jsou přiváděny na vstupy disjunktoru (obr. 6.24, c), z jehož výstupu je funkce odstraněna (není to nic jiného než součet modulo 2 :). Nakonec je tato funkce přiváděna na vstup střídače, jehož výstup je již funkcí (ekvivalence).
Tak se dostáváme k myšlence „obvodu“ - matematického modelu kalkulačky booleovské funkce, představovaného určitým vzorcem, sestaveného ze strukturních prvků, z nichž každý vypočítává jednu ze „základních“ booleovských funkcí. V obecném případě „obvod“ vypočítá logický operátor a každá souřadnicová funkce tohoto operátoru je odstraněna z jednoho z výstupů obvodu.
Matematicky je „schéma“ definováno jako směrovaný graf zvláštního druhu, ve kterém jsou označeny vrcholy i oblouky.
Pojďme si představit notaci: pokud je nějaká množina booleovských funkcí, pak tím označuje podmnožinu skládající se ze všech funkcí proměnných.
Definice 6.14. Nechte množiny opravit: (booleovské funkce) a (booleovské proměnné).
Okruh funkčních prvků na bázi (SFE), nebo jednoduše obvod na bázi, také schéma (F, X), je otevřený řízený graf (tj. Síť), jehož každý vrchol je označen jedním z prvků sady, takže následující Požadavky:
1) každý vstup do sítě je označen buď nějakou proměnnou z, nebo nějakou konstantou z;
2) pokud je vrchol v síti označen funkcí proměnných (tj.), Pak je jeho poloviční stupeň vstupu stejný a na množině oblouků vstupujících do vrcholu je dáno číslování (jedna k jedné), ve kterém každý oblouk získá číslo od 1 do.
Při kreslení diagramů jsou vstupy označeny kruhy a vrcholy, které nejsou vstupy, jsou označeny trojúhelníky, uvnitř kterých je napsáno označení funkce, která označuje tento vrchol. Východy jsou označeny šipkami „ukončení“. Na obr. 6.25 ukazuje SPE na základě.
Pokud je základ implikován, řekneme jednoduše „schéma“. Kromě toho, pokud je sada proměnných fixována „jednou provždy“ a při zvažování různých schémat měníme pouze sadu funkcí, pak, jak jsme to udělali, zavedením konceptů vzorce a superpozice na daném základě, budeme hovořit o SFE na základě, za předpokladu, že pokaždé, což implikuje kdysi pevnou sadu proměnných, která (pokud to nepoškodí přesnost) není uvedena.
Nyní definujeme indukcí pojem booleovské funkce vypočítané vrcholem obvodu.
Definice 6.15. Nechte CFE dát na základě se sadou vrcholů.
1. Předpokládá se, že každý vstup CFE počítá booleovskou funkci, se kterou je označen (tj. Nějaká proměnná nebo konstanta).
2. Pokud je vrchol označen funkcí, oblouk se zadaným číslem pochází z vrcholu, který funkci vyhodnotí, pak vrchol v vypočítá superpozici.
Pokud tedy každý vrchol CFE over počítá určitou funkci, pak je v obecném případě zásadní pořadí, ve kterém jsou funkce substituované místo proměnných funkcí vyčísleny. Je přirozené volat booleovskou funkci proměnných komutativní, pokud zachovává svou hodnotu pod libovolnou permutací svých proměnných. V tomto případě se nemusíme starat o číslování oblouků vstupujících do horní části obvodu označeného takovou funkcí.
Příklad 6.23. Zvažte SPE na obr. 6.25. Vrcholy a jsou vstupy SFE. Tyto vrcholy počítají funkce, resp. Poté vrchol, stejně jako vrchol, podle definice 6.15 vypočítá funkci (Schaefferův tah) a vrchol (výstup sítě) vypočítá funkci, o které je známo, že se rovná spojce.
SPE zobrazená na obr. 6.26, má dva výstupy, výpočetní funkce a.
Definice 6.16. Booleovská funkce vypočítaná CFE na základě je funkce vypočítaná kterýmkoli z jejích výstupů.
CFE tedy vypočítá přesně tolik booleovských funkcí, kolik má výstupů. SFE na obr. 6.25 vypočítá jednu funkci a SPE na obr. 6,26 - dva.
Obecně platí, že pokud je množina všech proměnných, které slouží jako popisky pro vstupy obvodu na základě s výstupy g, CFE definuje mapování z booleovské kostky na booleovskou kostku, tj. booleovský operátor.
Poznámka 6.10. V některých případech je funkce vypočítaná daným SFE definována poněkud odlišně, za předpokladu, že se jedná o funkci vypočítanou jakýmkoli vrcholem z podmnožiny vybraných vrcholů SFE. Zejména to mohou být výstupy. V každém případě souhlasíme s nakreslením šipky „výstup“ z vybraných (v uvedeném smyslu) vrcholů obvodu.
Každý obvod bran tedy vypočítává nějaký booleovský operátor, zejména pokud je počet výstupů obvodu 1, pak počítá nějakou booleovskou funkci.
Lze také dokázat opak: pro libovolného booleovského operátora lze SFE postavit na základě, kde je kompletní sada, která počítá daného operátora.
Příklad 6.24. Nastavme tabulku na logický operátor, který se mapuje na (tabulka 6.9).
Z tabulky je dobře vidět, že (funkce není nic jiného než většinová funkce proměnných a minimální DNF pro ni je napsáno výše, viz příklad 6.12). Představujeme funkci na základě Zhegalkinu. Použitím de Morganových zákonů dostaneme
Vzhledem k tomu budeme mít
(připomeňme, že součet modulo 2 libovolného sudého počtu stejných členů je roven 0). Tak,
SFE pro logický operátor uvedený v tabulce. 6.9, základ Zhegalkinu je znázorněn na Obr. 6.27.
Při navrhování SFE je užitečné mít na paměti numerický parametr zvaný jeho složitost.
Složitost SPE je počet jeho vrcholů, které nejsou vstupy.
Na obr. 6.27 CFE na bázi Zhegalkinu má složitost 5.
Uvažujme nyní o CFE pro stejného operátora na standardní bázi. Pomocí tabulky (viz tabulka 6.9) vytvoříme pro funkci SDNF
Mapa Karnot pro tuto funkci, zobrazená na obr. 6.28 ukazuje, že to nelze minimalizovat (přesněji výše uvedený SDNF je minimální DNF pro tuto funkci).
Ale můžete jít jinou cestou. Můžeme uvažovat o tabulce. 6.9 jako tabulka definující částečnou booleovskou funkci. Minimalizací této funkce podle Karnotovy mapy * zobrazené na obr. 6,29, máme
* Na této mapě jsme explicitně označili množiny, na kterých funkce nabývá hodnoty 0, a to vložením nul do odpovídajících buněk. Chceme tedy znovu upozornit na skutečnost, že bychom si neměli mýlit nuly s pomlčkami: pomlčka v buňce mapy určující částečnou funkci znamená, že hodnota funkce není na této množině definována, tj. není ani 0 ani 1.
CFE nad standardní základnou pro uvažovaný booleovský operátor je znázorněn na obr. 6.30. Složitost tohoto SFE je 11. Všimněte si, že vrchol výpočtu funkce není výstupem.
Booleovský operátor v tomto příkladu vypočítá dvouciferný součet (mod 2) tří jednociferných výrazů. Lze jej také považovat za jednobitový binární sčítač - funkční blok vícebitového binárního sčítače - pro dva termíny. Poté je funkce r / 1 interpretována jako „přenosový signál“ v nejvýznamnějším bitu. Na obr. 6.31 ukazuje „spojení“ tří SFE (jak je znázorněno na obr. 6.30), pomocí kterého se vypočítá součet dvou třímístných binárních čísel. Konstanta 0 je přiváděna na třetí vstup sčítače pro nejméně významný bit a „přenosový signál“ nejvýznamnějšího bitu je nejvýznamnějším bitem součtu, což bude obecně čtyřmístné číslo.
V moderní technologii řídicích a výpočetních zařízení zaujímají důležité místo diskrétní převaděče, tedy zařízení, která mají určitý počet vstupů a výstupů. Sady signálů přicházejících na vstupy a vznikající na výstupech patří ke známým konečným sadám.
Sdílejte svou práci na sociálních médiích
Pokud vám tato práce nevyhovovala, ve spodní části stránky je seznam podobných prací. Můžete také použít tlačítko Hledat
aranov Victor Pavlovich. Diskrétní matematika. Sekce 5. Obvody DNF a FE.
Přednáška 28. Schémata funkčních prvků. Problémy s analýzou a syntézou
Přednáška 28. SCHÉMATA Z FUNKČNÍCH PRVKŮ.
PROBLÉMY S ANALÝZOU A SYNTÉZOU
Přednáškový plán:
1. Koncept obvodu funkčních prvků (FE).
2. Problémy analýzy a syntézy obvodů z PV.
- Koncept obvodu z PV
V moderní technologii zaujímají řídicí a výpočetní zařízení důležité místodiskrétní převodníky, tj. zařízení, která mají určitý počet vstupů a výstupů. Sady signálů přicházejících na vstupy a vznikající na výstupech patří ke známým konečným sadám. Zařízení převádějí vstupní sady signálů na výstup. Matematickým modelem těchto zařízení je tzvdiagramy funkčních prvků (SFE).
Jako příklad zvažte elektrický obvod tří diod a odpor, znázorněný na obr. 1.
Postava: 1. Elektrické schéma a jeho symbol
V bodech obvodu zobrazeného v kruhu se v různých časech může objevit buď vysoká úroveň, přibližně rovná 5 V, nebo nízká úroveň, přibližně rovná nule. V bodě v obvodu označeném pomlčkou je úroveň napětí neustále udržována na nízké úrovni.
Označené body budou interpretovány jako vstupy a bod - jako východ. Činnost obvodu lze popsat takto: pokud mají všechny vstupy nízkou úroveň napětí, pak je také nízký výstup, pokud alespoň jeden ze vstupů má vysokou úroveň napětí, pak je výstup vysoký. Pokud označíte stav s vysokou úrovní napětí jako jeden a s nízkou úrovní napětí - nula, pak lze závislost výstupu na vstupech nastavit pomocí booleovské funkce.
Na základě toho se výše uvedený obvod nazývá logický prvek „OR“.
Takové obvody mohou být sestaveny z elektronických trubek, elektromechanických spínačů, pneumatických prvků atd. Závislost výstupu na vstupech lze popsat nejen jako disjunkci, ale také pomocí konjunkce, negace a složitějších booleovských funkcí.
Budeme uvažovat logické prvky s různými závislostmi výstupu na vstupech. Tyto prvky lze vzájemně propojit přiváděním výstupů některých prvků ke vstupům ostatních. Ve výsledku získáme SFE.
Definici SFE lze rozdělit do dvou fází. V první fázi je odhalena strukturální část tohoto konceptu, ve druhé - funkční.
Já etapa. Rozdělme tuto fázi na několik bodů.
1 ... Existuje konečná sada objektů (), tzvlogické prvky.Každý prvek má vstupy a jeden výstup. Prvek je graficky znázorněn, jak je znázorněno na obr. 2.
2 ... Indukcí definujeme konceptlogická síť jako objekt, ve kterém je určitý počet vstupů a určitý počet výstupů (obr. 3).
a) Základ indukce. Izolovaný vrchol se nazývá triviální logická síť. Podle definice se jedná o vstup i výstup (obr. 4).
… …
…
Postava: Obr Obr 4
b) Indukční přechod. Tato část je založena na použití tří operací.
Já ... Provoz kombinování disjunktních sítí. Dovolit a být dvě neprotínající se sítě (bez společných prvků, vstupů a výstupů), které mají vstupy a výstupy. Set-teoretické síťové propojení je logická síť, která má vstupy a výstupy.
II ... Operace připojení prvku. Nechť síť a prvek jsou takové, že ve vybraných různých výstupech s čísly. Potom se obrázek nazývá logická síť, která je výsledkem připojení prvku k síti. Vstupy jsou všechny vstupy, výstupy jsou všechny síťové výstupy, s výjimkou výstupů s čísly, stejně jako výstup prvku. Síť má vstupy a výstupy (obr. 5).
… …
Postava: 6.
Postava: Pět
III ... Operace rozdělení výstupu. Nechte v síti přidělit zásuvku s číslem. Potom se obrázek nazývá logická síť získaná rozdělením výstupu. Vstupy jsou všechny vstupy, výstupy jsou všechny síťové výstupy s čísly 1,…,… a další dva výstupy, které vznikly z výstupu s číslem sítě (obr. 6). Proto má vstupy a výstupy.
3 ... Nechť abecedy a být uvedeny.
Schéma funkčních prvků se nazývá logická síť se vstupy z abecedy a výstupy z abecedy, která je označena
. (1)
Uveďme příklady obvodů.
1. Nechť sestava sestává ze tří prvků AND (spojka), OR (disjunktor) a NOT (invertor).
Potom bude obrázek (obr.6) diagramem, protože jej lze sestavit pomocí operacíI - III .
Postava: 6 Obr. 7
2. Obrázek na obr. 7 je také schematický.
II etapa. Stanovení funkce obvodu.
4 ... Porovnejme CFE (1) se systémem funkcí booleovské algebry
(2)
také zvanývodivost tohoto obvodu.
Příklad. a) Pro schéma máme systém skládající se z jedné rovnice
Nebo.
b) Obdobně získáme pro obvod
- Implementace booleovských funkcí obvody FE. Problémy s analýzou a syntézou
fV obvody
Úkol analýzy: pro daný SFE (1) získat systém booleovských rovnic (2).
Algoritmus pro řešení problému: sledování operací budování sítěI - III , postupně počítáme funkce na výstupech síťových prvků.
Problém syntézy: pro daný základ funkčních prvků a libovolný systém booleovských rovnic (2) zkonstruujte obvod (1) z dané FE, který tento systém rovnic implementuje.
Existenci řešení problému syntézy určuje Postova věta, podle které musí být systém funkcí, které implementují základní FE, kompletní. Funkce mohou být reprezentovány jako superpozice funkcí a každý krok superpozice odpovídá určité kombinaci prvků.
Příklad. Pro funkci
(3)
Schéma odpovídající superpozici na pravé straně vzorce (3) je znázorněno na obr. 8.
Postava: 8
Problém syntézy spočívá ve skutečnosti, že pro daný systém booleovských rovnic je možné z FE sestavit mnoho obvodů, které tento systém implementují. V tomto ohledu vyvstává problém optimální syntézy: ze všech druhů schémat, která implementují tuto funkci, vyberte nejlepší podle jednoho nebo jiného kritéria, například s nejmenším počtem prvků. Taková schémata se budou nazývatminimální.
Následující tvrzení je pravdivé.
Teorém. Existuje algoritmus, který vytváří minimální obvod pro každý systém booleovských funkcí.
Tento algoritmus pro konstrukci minimálních obvodů patří do třídy algoritmů typu „vyčerpávajícího vyhledávání“, protože je založen na prohlížení všech obvodů do určité složitosti. Vyčerpávající vyhledávací algoritmy jsou zpravidla velmi pracné a nevhodné pro praktické účely. Proto níže zvážíme jednodušší problém, pro který původní soustava rovnic obsahuje jednu rovnici
a proto má požadovaný obvod jeden výstup.
Složitost minimálního obvodu je označena. Uvažujeme problém syntézy nikoli pro samostatnou funkci, ale pro celou třídu funkcí proměnných. Kvalita syntézních algoritmů je srovnávána porovnáním takzvaných Shannonových funkcí. Nech být
- minimální složitost implementujících schémat, která jsou získána pomocí algoritmu.
Funkce se nazývají Shannonovy funkce a je zřejmé, že
Úkolem syntézy je najít algoritmus, pro který by byl co nejblíže, a tak, aby složitost algoritmu byla podstatně menší než složitost vyčerpávajícího vyhledávacího algoritmu. S touto formulací problému se nevyžaduje, aby algoritmus našel minimální obvod pro každou funkci, je jen nutné, aby nejjednodušší obvod získaný pomocí měl složitost, která nepřesahuje.
Další podobná díla, která by vás mohla zajímat |
|||
| 9013. | METODY PRO SYNTÉZU REŽIMŮ Z FE. SCHÉMA DEKODÉRU A BINÁRNÍHO ADDERU | 153,07 KB | |
| Obecná teorie syntézy CFE vede k závěru, že většina booleovských funkcí pro velké hodnoty má složité minimální obvody. To znamená, že velmi úzká třída booleovských funkcí má praktickou hodnotu z hlediska syntézy. | |||
| 5321. | Typy a hodnoty parametrů automatické ochrany pro různé prvky daného návrhového schématu | 526,7 KB | |
| K zajištění normálního provozu energetické soustavy a spotřebičů elektřiny je nutné co nejdříve identifikovat a oddělit místo poškození od nepoškozené sítě a obnovit normální provozní podmínky energetické soustavy a spotřebitelů. | |||
| 5384. | Vývoj elektrického obvodu stojanu pro analýzu činnosti taktovaného dekodéru pro 4 vstupy a 16 výstupů | 626,63 KB | |
| Ke zlepšení provozu kolejových vozidel ATP byla vyvinuta organizační struktura systému údržby a oprav kolejových vozidel ATP a byla navržena sada zařízení pro diagnostiku a údržbu. Hlavním úkolem fungování podnikových opravárenských zařízení je zajistit nepřetržitý provoz zařízení. Zahrnuje: opravárenskou a restaurátorskou základnu podniku, sklady, obchody a generální oddělení opravárenských zařízení, technologická zařízení, dispečink. Organizace... | |||
| 1886. | Fáze systémové analýzy, jejich hlavní cíle, cíle | 27,44 KB | |
| Teorie optimálních systémů umožňuje odhadnout hranici, které lze v optimálním systému dosáhnout, porovnat ji s indikátory fungujícího neoptimálního systému a zjistit, zda je v uvažovaném případě vhodné vyvinout optimální systém. U automaticky řízeného procesu automaticky řízeného systému se rozlišují dva optimalizační stupně: statický a dynamický. Statická optimalizace řeší otázky vytváření a implementace optimálního modelu procesu, zatímco dynamická ... | |||
| 5123. | Vývoj funkčních strategií | 35,44 KB | |
| HR strategie. Funkce a struktura řízení. Řídicí funkce a jejich role při formování řídících struktur. Hierarchický typ struktury řízení. | |||
| 20368. | Vliv složení recepturních složek a technologií na spotřebitelské vlastnosti funkčních produktů | 742,05 KB | |
| Koncept optimální výživy je přijat moderní lékařskou vědou. To znamená, že došlo k přechodu od konceptu adekvátní výživy, kdy byly makroživiny převážně regulovány a normalizovány - zdroje tuků, zdroje energie, plastů (lipidy, bílkoviny, tuky), k konceptu optimální výživy, kdy spektrum živin potřebných pro život těla a další drobné komponenty, které byly dříve přehlédnuty, jsou značně rozšířeny. | |||
| 4706. | Způsoby syntézy Me karboxylátů | 9,26 MB | |
| Podstata způsobu spočívá v rozpuštění oxidu, hydroxidu nebo uhličitanu kovu ve vodném roztoku odpovídající kyseliny. Produkt je izolován odpařením roztoku před krystalizací nebo filtrací sraženiny, pokud je karboxylát nerozpustný nebo omezeně rozpustný ve vodě. | |||
| 15923. | Základní metody syntézy pyrazalodiazepinů | 263,39 KB | |
| Nové způsoby syntézy derivátů pyrazolodiazepinu. Vývoj nových strategií syntézy je velmi zajímavý. Systematické a zevšeobecňující studie syntézy derivátů pyrazolodiazepinu nebyly provedeny, některé otázky zůstávají nedotčeny kontroverzí nebo zcela nevyřešeny. | |||
| 11978. | Elektrárny založené na hydrotermální oxidaci hliníku pro výrobu elektřiny, tepla, vodíku a funkčních nanomateriálů | 49,89 KB | |
| Vývoj je založen na reakci hydrotermální oxidace hliníku, při které se uvolňuje velké množství tepelné energie a vytvářejí se oxidy a vodík hliníku: l2H2O → lOOH boehmit15H2415. Jako výchozí činidla se používají destilovaná voda a hliníkové prášky o velikosti mikronů. Instalace KEU10 Instalace ETK100 Technické vlastnosti instalace ETK100: Parametr Hodnota Spotřeba hliníku kg h 101 Spotřeba vody na vstupu do zařízení na úpravu vody kg h 484 Kapacita vodíku nm3 110 Tepelný výkon ... | |||
| 6605. | Expertní systémy. Návrh TP metodou syntézy | 11,67 KB | |
| Reprezentace akumulace znalostí a jejich udržování v aktuálním stavu je komplexní úkol zkoumaný v sekci informatiky zvané znalostní inženýrství. Znalostní inženýr se podílí na vývoji znalostní základny - jádra systémů zvaných inteligentní. Nejčastěji se inteligentní systémy používají k řešení složitých problémů, kde hlavní složitost řešení ... | |||
Přednáška 2. Schémata funkčních prvků
(SFE) na určitém základě. Složitost a hloubka
schémata. Příklady. Způsob syntézy SFE pomocí DNP.
Přednášející - docentka Svetlana Nikolaevna Selezneva
Přednášky na téma „Diskrétní matematika 2“.
1. ročník, skupina 141,
fakulta CMC, Moskevská státní univerzita pojmenovaná po M.V. Lomonosov
Přednášky na webu http://mk.cs.msu.su
Příklady SFE Syntéza SFE z DNP
Schémata funkčních prvků
Pojďme definovat obvody funkčních prvků na určitém základě.
Dejme nám množinu booleovských funkcí B \u003d (g1 (x1, ..., xn1), ..., gs (x1, ..., xns)) P2, kde n1, ..., ns 0.
Nazvěme tuto sadu základem.
Všimněte si, že tento koncept základny nemá nic společného s konceptem základny P2, který byl zvažován v algebře logiky.
Zpravidla budeme uvažovat standardní základnu B0 \u003d (x & y, x y, x).
Příklady SFE Syntéza SFE pomocí DNF Definice obvodu z funkčních prvků Obvod z funkčních prvků (SFE) na základě B0 \u003d (x & y, x y, x) je
1) směrovaný acyklický graf G \u003d (V, E), jehož každý vrchol v V má poloviční stupeň vstupu d (v) nepřesahující dva (d (v) 2);
2) každý vrchol v s polovičním stupněm vstupu rovným 0 (d (v) \u003d 0) se nazývá vstup (nebo vstup obvodu) a je mu přiřazena nějaká booleovská proměnná xi;
3) všechny ostatní uzly (kromě vstupů) se nazývají vnitřní uzly obvodu;
4) každému vrcholu v s půlstupňovým přístupem rovným 1 (d (v) \u003d 1) je přiřazen (funkční) prvek negace; všechny takové vrcholy se nazývají invertory;
5) ke každému vrcholu v s polovičním stupněm vstupu rovným 2 (d (v) \u003d 2) je přiřazen buď (funkční) spojovací prvek & nebo (funkční) disjunkční prvek; všechny vrcholy, ke kterým jsou přiřazeny spojovací prvky, se nazývají spojky, všechny vrcholy, ke kterým jsou přiřazeny disjunkční prvky, se nazývají disjunktory;
Příklady SFE Syntéza SFE z DNF Stanovení obvodu z funkčních prvků (pokračování)
6) navíc jsou některým vrcholům přiřazeny párově různé výstupní proměnné y1, ..., ym.
Pokud je zadán SPE S, jehož vstupům jsou přiřazeny pouze proměnné x1, ..., xn a s výstupními proměnnými y1, ..., ym, pak tento SPE označíme S (x1, ..., xn; y1, .. , ym).
Příklady SFE Syntéza SFE z DNP
- & nbsp– & nbsp–
Stanovení hloubky vrcholu CFE Indukcí určíme hloubku d (v) vrcholu v v CFE S.
1. Základ indukce. Každý vstup v SFE S má hloubku rovnou 0: d (v) \u003d 0.
- & nbsp– & nbsp–
SFE a jejich charakteristiky Schémata funkčních prvků jsou výpočtovým modelem.
Charakteristiky CFE, které jsme představili, ukazují různé aspekty výpočetní efektivity.
Složitost CFE odpovídá času sekvenčního výpočtu.
Hloubka CFE odpovídá době paralelního výpočtu.
Maximální počet vrcholů se stejnou hloubkou v SFE odpovídá počtu procesorů v paralelním výpočtu.
Příklady SFE Syntéza SFE z DNF Příklad: součet tří bitů Řešení. Podobně jako v příkladu 6 napíšeme tabulku součtu tří bitů x, yaz. Tento součet může být také číslo se dvěma binárními číslicemi, takže zavedeme dvě logické proměnné
u0, u1 takové, že x + y + z \u003d 2u1 + u0:
- & nbsp– & nbsp–
Literatura pro přednášku 4
1. Yablonsky S.V. Úvod do diskrétní matematiky. M.:
Vyšší škola, 2001. Část V, Ch. 2, s. 336-355.
2. Gavrilov G.P., Sapozhenko A.A. Problémy a cvičení z diskrétní matematiky. Moskva: Fizmatlit, 2004. Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.
Příklady SFE Syntéza SFE z DNP