Reprezentaci booleovských funkcí pomocí vzorců lze dát následující „inženýrsko-konstruktivní“ smysl. Vzorec Ф (x 1, ..., xn) nad nějakou libovolně pevnou množinou F budeme považovat za „černou skříňku“, určité zařízení, na jehož vstup jsou přiváděny všechny možné množiny hodnot proměnných, a výstup odpovídající těmto množinám hodnot funkce f reprezentované vzorcem Ф (obr. 6.22).
Abychom pochopili, jak funguje „černá skříňka“, musíme rozebrat proces konstrukce vzorce z podvzorců. Dostat se k "základním" podvzorcům, tzn. prvků množiny F se dostáváme ke "stavebním blokům", konstrukčním prvkům, ze kterých je sestavena "černá skříňka", která vypočítává funkci f. Každá funkce "základny" F je vypočítána odpovídajícím "uzlem", který je považován za nejmenší strukturní jednotku naší "černé skříňky", a její vnitřní struktura již není analyzována.
Příklad 6.22. Zvolme standardní základ pro množinu F. Potom se vzorec nad standardní bází, představující funkci ~ (ekvivalence), zkonstruuje následovně:
Výpočet podle tohoto vzorce (a postup jeho sestavení z prvků standardního základu) lze schematicky znázornit tak, jak je znázorněno na Obr. 6.23.
Proměnná x 1 (přesněji hodnota této proměnné) je přiváděna na vstup konstrukčního prvku zvaného invertor (obr. 6.24, a) a počítající negaci. Záporné x 1 odstraněné z výstupu měniče, tzn. funkce x 1, je přivedena na jeden ze vstupů konjunktoru (obr. 6.24, b), na jehož druhý vstup je přivedena proměnná x 2. Na výstupu spojky se objeví funkce x 1 x 2. Výpočet funkce x 1 x 2 lze sledovat podobným způsobem, Obě tyto funkce jsou přivedeny na vstupy disjunktoru (obr. 6.24, c), z jehož výstupu funkce x 1 x 2 ∨ x 1 x 2 je odstraněno (to není nic jiného než součet modulo 2: x 1 ⊕ x 2). A nakonec je tato funkce přivedena na vstup měniče, na jehož výstupu je již získána funkce ~ (ekvivalence). #
Dostáváme se tedy k myšlence „obvodu“ – matematického modelu kalkulátoru booleovské funkce, reprezentovaného určitým vzorcem, sestaveným ze strukturních prvků, z nichž každý počítá jednu ze „základních“ booleovských funkcí. V obecném případě „obvod“ vypočítává booleovský 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 orientovaný graf zvláštního druhu, ve kterém jsou označeny vrcholy i oblouky.
Zaveďme zápis: je-li F nějaká množina booleovských funkcí, pak F (n) označíme podmnožinu F sestávající ze všech funkcí n proměnných (n≥0).
Definice 6.14. Nechť jsou pevné množiny: F (booleovské funkce) a X (booleovské proměnné).
Schéma funkčních prvků nad základem F ∪ X (C Φ E), nebo jednoduše kontrahované přes základ F ∪ X, také schéma (F, X), se nazývá orientovaný graf s otevřeným koncem (tj. síť), jehož každý vrchol je označen jedním z prvků sady FU X tak, aby byly splněny následující požadavky:
- každý vstup sítě je označen buď nějakou proměnnou z X, nebo nějakou konstantou z F (0);
- jestliže je vrchol v sítě označen funkcí f n proměnných (tj. f ∈ F (n)), pak je jeho půlstupeň vstupu roven n a na množině oblouků vstupujících do vrcholu v, číslování (jedna ku jedné) je uvedeno tak, že každý oblouk je očíslován od 1 do n.
Pokud je naznačen základ, řekneme jednoduše „schéma“. Pokud je navíc množina proměnných pevně dána „jednou provždy“ a při zvažování různých schémat měníme pouze množinu funkcí F, pak, stejně jako při zavádění pojmů vzorce a superpozice nad danou bází, bude mluvit o SFE na bázi F, za předpokladu, že pokaždé, což znamená jednou pevnou sadu proměnných X, která (pokud to neškodí přesnosti) není zmíněna.
Nyní definujeme pojem indukcí booleovská funkce vypočítaná horní částí obvodu .
Definice 6.15. Nechť je dáno CFE S na bázi F ∪ X, jejíž množina vrcholů je V.
- Předpokládá se, že každý vstup CFE vypočítá booleovskou funkci, kterou je označen (tj. nějakou proměnnou nebo konstantou).
- Pokud je vrchol v ∈ V označen funkcí f ∈ F (n), oblouk s číslem i (1≤i≤n), které do něj vstupuje, pochází z vrcholu ui ∈ V, který vypočítává funkci gi, pak vrchol v vypočítá superpozici f (g 1, ..., gn).
Pokud tedy každý vrchol CFE nad F počítá nějakou funkci, pak pořadí, ve kterém jsou funkce g 1, ..., g n uvedeny, dosazeno na místech funkční proměnné f je obecně zásadní. Je přirozené nazývat 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ě se nemusíme starat o číslování oblouků vstupujících do vrcholu obvodu, označeného takovou funkcí.
Příklad 6.23. Zvažte SPE na obr. 6.25. Vrcholy v 1 a v 2 jsou vstupy SFE. Tyto vrcholy vypočítávají funkce x a y. Potom vrchol v 3, stejně jako vrchol v 4, podle definice 6.15, vypočítá funkci x | y (Schaefferův zdvih) a vrchol v 5 (výstup sítě) vypočítá funkci (x | y) l (x | y), o kterém je známo, že se rovná spojce x y.
SPE zobrazená na Obr. 6.26 má dva výstupy, které počítají funkce (x | x) | (y | y) = x ∨ y a (x | y) | (x | y) = x y.
Definice 6.16. Booleovská funkce vypočítaná pomocí CFE na bázi F ∪ X, je funkce vypočítaná libovolným z jejích výstupů.
CFE tedy přesně vypočítá, kolik booleovských funkcí a kolik výstupů. SFE na Obr. 6.25 vypočítá jednu funkci a SPE na Obr. 6,26 - dva.
V obecném případě, jestliže (x 1, ..., x n) je množina všech proměnných, které slouží jako štítky pro vstupy obvodu S na bázi F ∪ X s m výstupy, CFE S definuje zobrazení booleovské krychle B n na booleovskou krychli 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 libovolným vrcholem z podmnožiny vybraných vrcholů SFE. Zejména se může jednat o výstupy. V každém případě se domluvme na vykreslení „výstupní“ šipky z vybraných (v právě naznačeném smyslu) vrcholů obvodu. #
Každý obvod hradel tedy počítá nějaký booleovský operátor, zejména pokud je počet výstupů obvodu roven 1, pak počítá nějakou booleovskou funkci.
Lze dokázat i opak: pro libovolný booleovský operátor lze SFE zkonstruovat na bázi F, kde F je úplná množina, která daný operátor počítá.
Reprezentujeme funkci y 1 v Zhegalkinově bázi. Použijeme-li de Morganovy zákony, dostaneme
(připomeňme, že součet modulo 2 libovolného sudého počtu stejných členů je roven 0).
y 1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE pro booleovský operátor uvedený v tabulce. 6.9, přes Zhegalkinův základ je znázorněn na Obr. 6.27.
Při návrhu SFE je užitečné mít na paměti číselný parametr zvaný jeho složitost.
Složitost SFE je počet jeho vrcholů, které nejsou vstupy.
Na Obr. 6.27 CFE na bázi Zhegalkin má složitost 5.
Uvažujme nyní CFE pro stejného operátora nad standardním základem.
Podle tabulky (viz tabulka 6.9) sestrojíme SDNF pro funkci y 2:
y2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
Karnotova mapa pro tuto funkci, znázorněná na Obr. 6.28 ukazuje, že ji nelze minimalizovat (přesněji výše napsaný SDNF je minimální DNF pro tuto funkci). Ale můžete jít i jinou cestou. Můžeme zvážit tabulku. 6.9 jako tabulku definující parciální booleovskou funkci y 2 = y 2 (x 1 x 2 x 3 y 1). Minimalizací této funkce o
Karnotova mapa * zobrazená na Obr. 6.29, dostáváme
* Na této mapě jsme označili množiny, na kterých má funkce hodnotu 0, a do odpovídajících buněk vložili nuly. Chceme tedy ještě jednou upozornit na to, že by se nemělo zaměňovat nuly s pomlčkami: pomlčka v buňce mapy specifikující dílčí funkci znamená, že hodnota funkce není na této množině definována, tzn. není ani 0, ani 1.
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
CFE nad standardním základem 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 počítající funkci y 1 není výstupem.
Booleovský operátor v tomto příkladu vypočítá dvouciferný součet (modulo 2) tří jednociferných členů. Lze si to také představit jako jednobitovou binární sčítačku – funkční blok vícebitové binární sčítačky – na dva termíny. Potom je funkce y 1 interpretována jako "nosný signál" v nejvýznamnějším bitu. Na Obr. 6.31 znázorňuje „spojení“ tří SFE (jak je znázorněno na obr. 6.30), pomocí kterého se vypočítá součet dvou trojciferných binárních čísel. Konstanta 0 se přivádí na třetí vstup sčítačky pro nejméně významný bit a „nosný signál“ nejvýznamnějšího bitu je nejvýznamnější bit součtu, což bude v obecném případě čtyřmístné číslo. .
Poznámka 6.11. Pokud navrhujeme SFE na standardní bázi a chceme minimalizovat jeho složitost, musíme nejprve zkonstruovat 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ána samotná DNF - počet negací. Mezi všemi minimálními (ve smyslu definice 6.6) DNF by se měly vybrat ty, ve kterých je počet výskytů proměnných pod záporným znaménkem nejmenší. Z hlediska složitosti SFE, který bude postaven na základě minimálního DNF, to znamená, že minimalizuje počet "invertorů" - vrcholů SFE označených negační funkcí.
Například pro funkci definovanou Karnotovou mapou (obr. 6.32) byste do jádra sestávajícího z jednoduchých implikantů x 1 x 2 x 4 a x 1 x 3 x 4 měli přidat jednoduchý implikant x 2 x 3 x 4, a ne x 1 x 2 x 3, protože neobsahuje zápory.
Funkční diagramy (FS) jsou navrženy tak, aby transformovaly logické informace. Počáteční informace, zakódovaná ve formě diskrétních signálů, je přiváděna na vstupy obvodu `x n... Pak tato informace zpracovávány a čteny v diskrétní formě z výstupů obvodu 'v m(n, m- počet jeho vstupů a výstupů). Zvažte FS, které pracují ve dvouhodnotové logice a mají jeden výstup ( m= 1). Transformaci informace v nich lze specifikovat jako funkci algebry logiky na=F(x n). Místo reléových prvků ve FS jsou použity funkční prvky (FE), které zpravidla realizují elementární logické funkce.
Definice.Analýza se nazývá konstrukce vzorce pro algebru logiky (v případě potřeby její pravdivostní tabulka) pro daný FS.
Pro sestavení vzorce podle daného schématu je nutné znázornit vztah mezi KP ve FS formou substitucí v odpovídajících elementárních funkcích. Předpokládá se, že zpracování informací probíhá v etapách od vstupů k výstupům. PROTI reálná schémata pro zajištění dočasné koordinace práce všech FS jsou použity další prvky.
Analýza FS může být provedena dvěma způsoby - od vstupů k výstupům a od výstupů k vstupům. Podívejme se na první metodu s použitím dalších označení pro připojení meziobvodu.
Příklad 1(&, Ú, Ø) jsou brány jako MKP Analyzujte MKP, jejíž fyzikální struktura je uvedena na obr. 1.19.
Řešení. Po označení mezilehlých připojení PV, jak je znázorněno na obrázku, určíme signály, které jim odpovídají, krok za krokem . V tomto případě se přesuneme od vstupů obvodu k jeho výstupu.
Obrázek 1.19
KROK 1. R=`y, Q = `z
KROK 2. X=X&R= X&'y, 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Ú W=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 jeho pravdivostních hodnot má tvar (00000111) .
V závislosti na počátečních datech lze mezi úkoly syntézy (návrhu) FS rozlišit:
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í takových problémů se provádí podle algoritmu inverzního k metodě analýzy. Jak je uvedeno v části 1.7, struktura booleovských vzorců umožňuje izomorfně mapovat pouze systémy s paralelním a sekvenčním spojením prvků. Proto by FS, který je izomorfní s odpovídajícím vzorcem, měl obsahovat pouze sloučeniny tohoto typu.
Definice.Syntézou PS pro danou funkci se nazývá konstrukce strukturálního diagramu, který implementuje tuto funkci algebra logiky.
Protože reprezentace funkcí pomocí vzorců je nejednoznačná daný úkol má nejedinečné řešení. Stejně jako v případě reléových obvodů jsou optimální FS, skládající se z minimálního počtu PV a propojení mezi nimi. Takové FS lze získat pomocí vzorců s minimálním počtem proměnných.
Pokud jde o PC, budeme samostatně zvažovat vzorce, které jsou optimální ve třídě normálních forem (které se rovnají odpovídajícím minimálním formám), stejně jako absolutně optimální vzorce získané 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 u reléových obvodů. 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'z což není minimální. Jeho minimalizací získáme MDNF v následujícím tvaru: F = x yÚ x z. Odpovídá FS na obr. 1.20.
Obrázek 1.20
Pokud aplikujeme distributivní zákon na MDNF, dostaneme vzorec s ještě méně proměnnými: F = X(yÚ z). Pro tuto funkci se shodoval s MCNF. Tomu odpovídá naprosto optimální schéma.
Obrázek 1.21
Očividně, toto schéma mnohem jednodušší než původní (obrázek 1.19). Jelikož je syntéza optimální FS redukována na konstrukci minimálních vzorců, jsou obdobným způsobem konstruována i optimální schémata v jiných bázích. Analogy prvního a druhého distributivního zákona algebry logiky pro Schefferovy a webové formy lze získat nahrazením těchto zákonů:
&(X,y)= Ø ½ ( X,y) = ¯ (Ø X,Ø y);
Ú ( X,y)= ½ (Ø X, Ø y) =Ø ¯ ( X,y).
Příklad 2 Sestrojte FS, který implementuje jednobitovou binární sčítačku dvou čísel pomocí FE odpovídající bázi (Ø, ¯), stejně jako v bázi (¯).
Řešení. Označme jednobitová binární čísla dodávaná na vstup přes ( X,na). Výstupem by měl být jejich součet binární systém... Li x = 1, y = 1, pak S = 2 10 = 10 2, pro jeho zobrazení je tedy v obecném případě nutné použít dvě binární znaménka a FS musí mít dva výstupy. Označme je F(nejvýznamnější číslice součtu) a G(nejméně významný bit). Funkční pravdivostní tabulky F (X,na),G(X,na):
| X | y | F(X,y) | G(X,y) |
Sestrojíme SVNF funkcí v bázi (Ø, ¯). F má jednu jednotku ve vektoru pravdy, proto se jeho forma skládá z jedné složky: F= ¯ (Ø x, Ø na). Funkce G SVNF má tvar: G=د(¯( X,Ø na),¯(Ø X,na)). Tyto formy jsou minimální. Při kombinaci vstupů prvků může být funkční schéma znázorněno následovně:
Obrázek 1.22
V uvažovaném příkladu je nemožné zjednodušit normální formy webu pomocí zákonů logické algebry. V jednofunkční bázi (¯) 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
ÚKOLY
1. Konstruujte 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,proti) xy® yz;G) X|(yÚ z); e) X®( y® z) ;
f) (10011101); g) (01101011); h) (1110101111111110) .
2. Sestrojte pomocí FE (Ú, Ø) FS funkcí 1.a) -g).
3. Sestrojte pomocí FE (&, Ø) FS funkcí 1.a) -g).
4. Vytvořte FS, který implementuje jednobitovou binární sčítačku (příklad 2) pomocí FE následujícího tvaru:
a) (&, Ú, Ø), b) (Ú, Ø) , c) (&, Ø), d) ( x | y} .
5. Pomocí FE (&, Ú, Ø) sestrojte FS následujících zařízení:
a) převodník s binárními vstupy ( X,na) a ukončete F který funguje takto: při krmení x = 0 na výstupu F =na a při podávání x = 1 u vchodu F =`y;
b) selektivní zařízení s binárními vstupy ( X,na) a výstupy F 0 , F 1 , F 2 , F 3, který přijímá na vstupu 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= 1 a všechny ostatní f j= 0, (0 £ j 3 £, j¹ i).
6. Je možné vzít jako základ pro konstrukci FS následující sady funkcí:
a) (1001), (10001110),
b) (0101), (1011), (1101),
c) (1010), (01110001)?
Odpověď zdůvodněte.
7. Uveďte příklady řídicích funkcí, jejichž FS nelze sestrojit pouze z FE typu (®).
8. Uveďte příklady řídicí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 tím ekvivalentní transformace:
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
Sestavení FS:
a) optimální ve třídě normálních forem a
b) naprosto optimální.
Reprezentaci booleovských funkcí pomocí vzorců lze dát následující „inženýrsko-konstruktivní“ smysl. Vzorec nad nějakou libovolně pevnou množinou budeme považovat za „černou skříňku“, druh zařízení, na jehož vstup jsou přiváděny všechny druhy sad proměnných hodnot a výstup odpovídající těmto sadám hodnot funkce reprezentované vzorcem (obr. 6.22).
Abychom pochopili, jak funguje „černá skříňka“, musíme rozebrat proces konstrukce vzorce z podvzorců. Dostat se k "základním" podvzorcům, tzn. prvky množiny se dostáváme ke "stavebním blokům", konstrukčním prvkům, ze kterých je sestavena "černá skříňka", která vypočítává funkci. Každá funkce "základny" 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 se již neanalyzuje.
Příklad 6.22. Zvolme standardní základ jako sadu. Potom se vzorec na standardní bázi představující funkci (ekvivalenci) sestaví takto:
Výpočet podle tohoto vzorce (a postup jeho sestavení z prvků standardního základu) lze schematicky znázornit tak, jak je znázorněno na Obr. 6.23.
Proměnná (přesněji hodnota této proměnné) je přivedena na vstup konstrukčního prvku zvaného invertor (obr. 6.24, a) a výpočetní negace. Zápor odstraněný z výstupu měniče, tzn. funkce je přivedena na jeden ze vstupů konjunktoru (obr. 6.24.5), na jehož druhý vstup je přivedena proměnná. Na výstupu konjunktoru se objeví funkce. Výpočet funkce lze dohledat podobným způsobem. Obě tyto funkce jsou přivedeny na vstupy disjunktoru (obr. 6.24, c), z jehož výstupu je funkce odstraněna (nejedná se o nic jiného než součt modulo 2:). Nakonec je tato funkce přivedena na vstup měniče, jehož výstup je již funkcí (ekvivalence).
Dostáváme se tedy k myšlence „obvodu“ – matematického modelu kalkulátoru booleovské funkce, reprezentovaného určitým vzorcem, sestaveným ze strukturních prvků, z nichž každý počítá jednu ze „základních“ booleovských funkcí. V obecném případě „obvod“ vypočítává booleovský 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 orientovaný graf zvláštního druhu, ve kterém jsou označeny vrcholy i oblouky.
Zaveďme zápis: je-li nějaká množina booleovských funkcí, pak pomocí označuje podmnožinu sestávající ze všech funkcí proměnných.
Definice 6.14. Nechť jsou pevné množiny: (Booleovské funkce) a (Booleovské proměnné).
Obvod funkčních prvků na bázi (SFE), nebo jednoduše obvod na bázi, také schéma (F, X), je orientovaný graf s otevřeným koncem (tj. síť), jehož každý vrchol je označen s jedním z prvků sady tak, aby byly splněny následující požadavky:
1) každý vstup sítě je označen buď nějakou proměnnou od, nebo nějakou konstantou od;
2) pokud je vrchol v sítě označen funkcí proměnných (tj.), pak je jeho půlstupeň vstupu stejný a na množině oblouků vstupujících do vrcholu je číslování (jedna ku jedné). daný, ve kterém každý oblouk dostane číslo od 1 do.
Při kreslení diagramů se vstupy označují kroužky a vrcholy, které nejsou vstupy, se označují trojúhelníky, uvnitř kterých je napsáno označení funkce, která tento vrchol vyznačuje. Výstupy jsou označeny šipkami „exit“. Na Obr. 6.25 ukazuje SPE přes základ.
Pokud je naznačen základ, řekneme jednoduše „schéma“. Pokud je navíc množina proměnných pevně dána „jednou provždy“ a při zvažování různých schémat měníme pouze množinu funkcí, pak, stejně jako jsme to udělali, při zavádění pojmů vzorce a superpozice nad danou bází mluvit o SFE nad základem, pokaždé za předpokladu, že to znamená jednou pevně stanovenou sadu proměnných, která (pokud to neškodí přesnosti) není zmíněna.
Definujme nyní indukcí pojem booleovské funkce počítané vrcholem obvodu.
Definice 6.15. Nechť je CFE dán nad základem, jehož množina vrcholů je.
1. Předpokládá se, že každý vstup CFE vypočítá booleovskou funkci, kterou je označen (tj. nějakou proměnnou nebo konstantou).
2. Pokud je vrchol označen funkcí, oblouk s číslem, které do něj vstupuje, pochází z vrcholu, který funkci vyhodnocuje, pak vrchol v počítá superpozici.
Pokud tedy každý vrchol CFE over počítá určitou funkci, pak je v obecném případě podstatné pořadí, ve kterém jsou vyjmenovány funkce substituované místo funkčních proměnných. Je přirozené nazývat booleovskou funkci proměnných komutativní, pokud si 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 vrcholu 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. Potom vrchol, stejně jako vrchol, podle Definice 6.15, vypočítá funkci (Schaefferův zdvih) a vrchol (výstup sítě) vypočítá funkci, o které je známo, že se rovná konjunkci.
SPE zobrazená na Obr. 6.26, má dva výstupy, které počítají funkce a.
Definice 6.16. Booleovská funkce vypočítaná CFE na základě je funkce vypočítaná libovolným 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.
V obecném případě, pokud je množina všech proměnných, které slouží jako štítky pro vstupy obvodu na bázi, která má g výstupů, CFE definuje mapování z booleovské krychle do booleovské krychle, tzn. 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 libovolným vrcholem z podmnožiny vybraných vrcholů SFE. Zejména se může jednat o výstupy. V každém případě se domluvme na vykreslení „výstupní“ šipky z vybraných (v právě naznačeném smyslu) vrcholů obvodu.
Každý obvod hradel tedy počítá nějaký booleovský operátor, zejména pokud je počet výstupů obvodu roven 1, pak počítá nějakou booleovskou funkci.
Lze dokázat i opak: pro libovolný booleovský operátor lze SFE zkonstruovat na bázi, kde je kompletní množina, která daný operátor počítá.
Příklad 6.24. Nastavme tabulku na booleovský operátor, který se mapuje na (tabulka 6.9).
Z tabulky je to dobře vidět (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). Reprezentujeme funkci na bázi Zhegalkin. Použijeme-li de Morganovy zákony, 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 booleovský operátor uvedený v tabulce. 6.9, přes Zhegalkinův základ je znázorněn na Obr. 6.27.
Při návrhu SFE je užitečné mít na paměti číselný parametr zvaný jeho složitost.
Složitost SPE je počet jejích vrcholů, které nejsou vstupy.
Na Obr. 6.27 CFE na bázi Zhegalkin má složitost 5.
Uvažujme nyní CFE pro stejného operátora nad standardním základem. Pomocí tabulky (viz tabulka 6.9) sestrojíme SDNF pro funkci
Karnotova mapa pro tuto funkci, znázorněná na Obr. 6.28 ukazuje, že ji nelze minimalizovat (přesněji výše napsaný SDNF je minimální DNF pro tuto funkci).
Ale můžete jít i jinou cestou. Můžeme zvážit tabulku. 6.9 jako tabulku definující částečnou booleovskou funkci. Minimalizací této funkce podle Karnotovy mapy * zobrazené na Obr. 6.29, dostáváme
* Na této mapě jsme explicitně označili množiny, na kterých funkce nabývá hodnoty 0, vložením nul do odpovídajících buněk. Chceme tedy ještě jednou upozornit na to, že by se nemělo zaměňovat nuly s pomlčkami: pomlčka v buňce mapy specifikující dílčí funkci znamená, že hodnota funkce není na této množině definována, tzn. není ani 0, ani 1.
CFE nad standardním základem 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 počítající funkci není výstupem.
Booleovský operátor v tomto příkladu vypočítá dvouciferný součet (modulo 2) tří jednociferných členů. Lze si to také představit jako jednobitovou binární sčítačku – funkční blok vícebitové binární sčítačky – na dva termíny. Potom je funkce r / 1 interpretována jako "nosný signál" v nejvýznamnějším bitu. Na Obr. 6.31 znázorňuje „spojení“ tří SFE (jak je znázorněno na obr. 6.30), pomocí kterého se vypočítá součet dvou trojciferných binárních čísel. Konstanta 0 se přivádí na třetí vstup sčítačky pro nejméně významný bit a „nosný signál“ nejvýznamnějšího bitu je nejvýznamnější bit součtu, což bude v obecném případě čtyřmístné číslo. .
PROTI moderní technologieřídicí a výpočetní zařízení důležité místo zaujímají diskrétní převodníky, tedy zařízení, která mají určitý počet vstupů a výstupů. Množiny signálů přicházejících na vstupy a vznikajících na výstupech patří ke známým konečným množinám.
Sdílejte svou práci na sociálních sítích
Pokud by vám tato práce nevyhovovala, dole na stránce je seznam podobných prací. Můžete také použít tlačítko vyhledávání
Aranov Viktor Pavlovič. Diskrétní matematika. Sekce 5. DNF a FE obvody.
Přednáška 28. Schémata funkčních prvků. Problémy analýzy a syntézy
Přednáška 28. DIAGRAMY Z FUNKČNÍCH PRVKŮ.
PROBLÉMY ANALÝZY A SYNTÉZY
Plán přednášek:
1. Pojem obvod funkčních prvků(FE).
2. Problémy analýzy a syntézy obvodů z FV.
- Koncepce obvodu z FV
V moderních technologiích zaujímají důležité místo řídicí a výpočetní zařízenídiskrétní převodníky, tedy zařízení, která mají určitý počet vstupů a výstupů. Množiny signálů přicházejících na vstupy a vznikajících na výstupech patří ke známým konečným množinám. Zařízení převádějí vstupní sady signálů na výstupní. Matematický model taková zařízení jsou tzvschémata funkčních prvků(SFE).
Jako příklad uvažujme elektrický obvod tří diod a odporu, znázorněný na obr. jeden.
Rýže. 1. Elektrické schéma a jeho symbol
V bodech obvodu znázorněných v kruhu se v různých časech může objevit buď vysoká úroveň, přibližně rovna 5 V, nebo nízká úroveň, přibližně rovna nule. V místě diagramu označeném pomlčkou je nízká úroveň Napětí.
Označené body budou interpretovány jako vstupy a bod - jako výstup. Činnost obvodu lze popsat následovně: pokud všechny vstupy mají nízkou úroveň napětí, pak je výstup také nízký, pokud má alespoň jeden ze vstupů vysokou úroveň napětí, pak je výstup vysoký. Označíme-li stát s vysoká úroveň napětí o jedničku a s nízkým - nulovým, pak lze pomocí booleovské funkce nastavit závislost výstupu na vstupech.
Na základě toho se výše uvedený obvod nazývá logický prvek "OR".
Z podobných schémat lze sestavit elektronické elektronky, elektromechanické spínače, pneumatické prvky 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á hradla s různými závislostmi výstupu na vstupech. Tyto prvky mohou být vzájemně propojeny a napájet výstupy některých prvků vstupy jiných. V důsledku toho dostaneme SFE.
Vymezení pojmu SZZ lze rozdělit do dvou etap. V první fázi je odhalena strukturální část tohoto konceptu, ve druhé - funkční.
já etapa. Rozdělme tuto fázi do několika bodů.
1 ... Existuje konečná množina 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 pojem logická 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).
… …
…
Rýže. Obr Obr 4
b) Indukční přechod. Tato část je založena na použití tří operací.
Já ... Operace spojování disjunktních sítí. Nechť a být dvě disjunktní sítě (bez společných prvků, vstupů a výstupů), které mají vstupy a výstupy. Teoretické zřetězení sítě je logická síť který má vstupy a výstupy.
II ... Operace připevnění prvku. Nechť síť a prvek jsou takové, že ve vybraných různých výstupech s čísly. Potom se obrazec 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, kromě výstupů s čísly, stejně jako výstup prvku. Síť má vstupy a výstupy (obr. 5).
… …
Rýže. 6.
Rýže. 5
III ... Operace rozdělení výstupu. Nechte v síti zvýraznit 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 výstupy sítě s čísly 1,…,… a další dva výstupy, které vzešly z výstupu s číslem sítě (obr. 6). Má tedy vstupy a výstupy.
3 ... Nechte abecedy a být dán.
Schéma funkčních prvkůse nazývá logická síť se vstupy z abecedy a výstupy z abecedy, která se označuje
. (1)
Zde je několik příkladů obvodů.
1. Nechť se množina skládá ze tří prvků AND (konjunktor), OR (disjunktor) a NOT (invertor).
Potom bude obrázek (obr. 6) diagramem, protože jej lze sestavit pomocí operací I - III .
Rýže. 6 Obr. 7
2. Obrázek na Obr. 7 je také schéma.
II etapa. Stanovení funkce obvodu.
4 ... Srovnejme CFE (1) se systémem funkcí Booleovy 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) Pro obvod získáme obdobně
- Implementace booleovských funkcí obvody MKP. Problémy analýzy a syntézy
obvody z FV
Analytický úkol: pro danou SFE (1) získat soustavu 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ů.
Syntézní úkol: pro daný základ funkčních prvků a libovolný systém booleovských rovnic (2) k sestrojení obvodu (1) z daného MKP, který tento systém rovnic implementuje.
Existenci řešení problému syntézy určuje Postova věta, podle níž musí být systém funkcí, které implementují základní FE, úplný. 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)
Diagram odpovídající superpozici na pravé straně vzorce (3) je na Obr. osm.
Rýže. osm
Problém syntézy spočívá v tom, že pro daný systém booleovských rovnic je možné sestrojit mnoho MKP 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í danou funkci, vyberte to nejlepší podle toho či onoho kritéria, například s nejmenším počtem prvků. Taková schémata budou tzv minimální.
Následující tvrzení je pravdivé.
Teorém. Existuje algoritmus, který staví 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 "brute force", 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 pro praktické účely nevhodné. Proto níže uvažujeme o jednodušším problému, 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. Nebudeme uvažovat problém syntézy pro samostatnou funkci, ale pro celou třídu funkcí proměnných. Kvalita syntézních algoritmů je porovnána porovnáním tzv. Shannonových funkcí. Nechat
- minimální složitost implementovaných schémat, které jsou získány pomocí algoritmu.
Funkce se nazývají Shannonovy funkce a je to zřejmé
Problémem syntézy je najít algoritmus, kterému by se co nejvíce přibližoval, a tak, aby složitost algoritmu byla výrazně menší než složitost algoritmu vyčerpávajícího vyhledávání. S touto formulací problému není vyžadováno, aby algoritmus našel minimální obvod pro každou funkci, je pouze nutné, aby nejjednodušší schéma získané s pomocí měly složitost, která příliš nepřesahovala.
Další podobná díla, která by vás mohla zajímat.Wshm> |
|||
| 9013. | METODY SYNTÉZY SCHÉMAT Z FE. DIAGRAMY DEKODÉRU A BINÁRNÍ Sčítačky | 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 konstrukčního schématu | 526,7 kB | |
| Pro zajištění normálního provozu elektrizační soustavy a spotřebitelů 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 elektrizační 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 | |
| Pro zlepšení provozu kolejových vozidel ATP byla vyvinuta organizační struktura systému údržby a oprav kolejových vozidel ATP a soubor zařízení pro diagnostiku a Údržba... Hlavním úkolem fungování opravárenských zařízení podniku je zajistit nepřetržitý provoz zařízení. Zahrnuje: opravárenskou a restaurátorskou základnu podniku, sklady, prodejny a generální oddělení opravárenských zařízení, technologické vybavení, dispečink. Organizace... | |||
| 1886. | Etapy systémové analýzy, jejich hlavní cíle, cíle | 27,44 kB | |
| Teorie optimálních systémů nám umožňuje odhadnout hranici, které lze v optimálním systému dosáhnout, porovnat ji s ukazateli současného neoptimálního systému a zjistit, zda je v uvažovaném případě vhodné vyvinout optimální systém. Pro automaticky řízený proces automaticky řízeného systému se rozlišují dva stupně optimalizace: statický a dynamický. Statická optimalizace řeší problémy s tvorbou a implementací optimální model procesní a dynamický... | |||
| 5123. | Vývoj funkčních strategií | 35,44 kB | |
| HR strategie. Funkce a struktura řízení. Manažerské funkce a jejich role při utváření řídících struktur. Hierarchický typ struktury řízení. | |||
| 20368. | Vliv složení složek receptury a technologií na spotřebitelské vlastnosti funkčních produktů | 742,05 kB | |
| Moderní lékařská věda je přijat koncept optimální výživy. To znamená, že došlo k přechodu od konceptu adekvátní výživy, kdy byly regulovány a normalizovány především makroživiny - zdroje tuků, zdroje energie, plastické hmoty (lipidy, bílkoviny, tuky), ke konceptu optimální výživy, kdy Spektrum živin nezbytných pro životně důležitou činnost organismu a dalších drobných složek, které byly dříve přehlíženy, je značně rozšířeno. | |||
| 4706. | Metody syntézy Me karboxylátů | 9,26 MB | |
| Podstatou metody je rozpuštění oxidu, hydroxidu nebo uhličitanu kovu ve vodném roztoku odpovídající kyseliny. Produkt se izoluje 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é metody syntézy pyrazolodiazepinových derivátů. Vývoj nových strategií syntézy je velmi zajímavý. Systematické a zobecňující studie syntézy pyrazolodiazepinových derivátů nebyly provedeny, některé otázky zůstávají nedotčeny kontroverzí nebo jsou zcela nevyřešeny. | |||
| 11978. | Zařízení energetických technologií na bázi hydrotermální oxidace 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 vznikají oxidy hliníku a vodík: l2H2O → lOOH boehmit15H2415. Jako výchozí činidla se používají destilovaná voda a hliníkové prášky o velikosti mikronů. Instalace KEU10 Instalace ETK100 Specifikace 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 | |
| Reprezentovat akumulaci znalostí a udržovat je 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 rozvoji znalostní báze – jádra systémů nazývaných inteligentní. Nejčastěji se inteligentní systémy používají k řešení složitých problémů, kde je 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
systém. Příklady. Metoda syntézy SFE z 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í univerzity 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ů
Definujme obvody funkčních prvků v určitém základu.
Dostaneme nějakou množinu booleovských funkcí B = (g1 (x1, ..., xn1), ..., gs (x1, ..., xns)) P2, kde n1, ..., ns 0.
Nazvěme tuto sestavu základem.
Všimněte si, že tento koncept báze nemá nic společného s konceptem báze P2, který byl uvažován v algebře logiky.
Zpravidla budeme uvažovat standardní základ B0 = (x & y, x y, x).
Příklady SFE Syntéza SFE podle DNF Určení obvodu z funkčních prvků Obvod z funkčních prvků (SFE) v bázi B0 = (x & y, x y, x) je
1) orientovaný acyklický graf G = (V, E), jehož každý vrchol v V má poloviční vstupní stupeň 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) = 0) se nazývá vstup (nebo obvodový vstup) 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 polovičním stupněm přiblížení rovným 1 (d (v) = 1) je přiřazen (funkční) negační prvek; všechny takové vrcholy se nazývají invertory;
5) každému vrcholu v s polovičním vstupním stupněm rovným 2 (d (v) = 2) je přiřazen buď (funkční) spojkový prvek &, nebo (funkční) disjunkční prvek; všechny vrcholy, ke kterým jsou přiřazeny prvky konjunkce, se nazývají konjunktory, všechny vrcholy, ke kterým jsou přiřazeny prvky disjunkce, se nazývají disjunktory;
Příklady SFE Syntéza SFE podle DNF Určení obvodu z funkčních prvků (pokračování)
6) některému z vrcholů jsou navíc přiřazeny párově různé výstupní proměnné y1, ..., ym.
Je-li zadáno SPE S, jehož vstupům jsou přiřazeny pouze proměnné x1, ..., xn, a u výstupních proměnných y1, ..., ym, pak tuto SPE označíme S (x1, .. ., xn; y1,..., ym).
Příklady SFE Syntéza SFE z DNP
- & nbsp- & nbsp-
Určení hloubky vrcholu SPE Indukcí určíme hloubku d (v) vrcholu v v SPE S.
1. Základy indukce. Každý vstup v SFE S má hloubku rovnou 0: d (v) = 0.
- & nbsp- & nbsp-
SFE a jejich charakteristiky Schémata funkčních prvků jsou výpočtovým modelem.
Charakteristiky CFE, které jsme zavedli, ukazují různé aspekty výpočetní účinnosti.
Složitost CFE odpovídá době 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ů při 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, y a z. Tento součet může být také číslo se dvěma binárními číslicemi, takže zavedeme dvě booleovské proměnné
u0, u1 tak, že x + y + z = 2u1 + u0:
- & nbsp- & nbsp-
Literatura k přednášce 4
1. Yablonsky S.V. Úvod do diskrétní matematiky. M .:
Vyšší škola, 2001. Část V, Ch. 2, str. 336-355.
2. Gavrilov G.P., Sapozhenko A.A. Úlohy a cvičení v diskrétní matematice. Moskva: Fizmatlit, 2004. Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.
Příklady SFE Syntéza SFE z DNP