Kuba Caro - grafický spôsob, ako minimalizovať spínacie (booleanové) funkcie, ktoré poskytujú relatívnu jednoduchosť práce s veľkými výrazmi a elimináciou potenciálneho pretekania. Predstavuje párov spárovaného nekompletného lepenia a základná absorpcia. Mapy Carno sa považujú za prestavané nádrž Funkcie. Mapy Carno je možné zobraziť ako definované ploché skenovanie n-dimenzionálne bulve Kuba.

Carno karty boli vynájdené v roku 1952 Edward V. Vayich a zlepšil v roku 1953 Maurice Carno, fyzik z " Bell Labs."A boli navrhnuté tak, aby pomohli zjednodušiť digitálne elektronické obvody.

Mapa Carno Booleovské premenné sa prenášajú z tabuľky pravdy a sú objednané pomocou Šedé kódyv ktorom každý Ďalšie číslo odlišné od predchádzajúceho jediného vypúšťania

Princípy minimalizácie

Hlavná metóda minimalizácie logických funkcií prezentovaných vo forme SDNF. alebo SvorkaJe prevádzka párovej neúplnej lepiacej a elementárnej absorpcie. Párovanie lepenie operácie sa uskutočňuje medzi dvoma tepelnými (členmi), ktoré obsahujú rovnaké premenné, ktorých záznam (priamy a inverzný) sa zhodujú pre všetky premenné, okrem jedného. V tomto prípade môžu byť všetky premenné, okrem jednej, môžu byť vyrobené pre konzoly a zostávajúce priame a inverzné položky jednej premennej, aby sa odstránili lepeniu. Napríklad:

Podobne ako PFF:

Možnosť absorpcie vyplýva z zjavných vyrovnaností

Touto cestou, hlavnú úlohu Pri minimalizácii SDNF a SCPF je vyhľadávanie termínov vhodných na lepenie, po ktorom nasleduje absorpcia, ktorá pre veľké formy to môže stačiť náročná úloha. Carno karty poskytujú vizuálny spôsob, ako nájsť takéto výrazy.

Ako viete, Booleovské funkcie N. Premenné prezentované vo forme CDNF alebo SCFF môžu mať 2 v jeho zložení N. RÔZNE PODMIENKY. Všetci títo členovia tvoria určitú štruktúru, topologicky ekvivalentnú N.-Hell Kuba a všetky dva termíny spojené okrajom sú vhodné na lepenie a absorpciu.

Obrázok ukazuje jednoduchú tabuľku pravdy pre funkciu dvoch premenných, čo zodpovedá tejto tabuľke 2-dimenzionálnej kocky (štvorec), ako aj 2-dimenzionálnu kocku s označením CDNF členov a ekvivalentnú tabuľku na zoskupenie pojmov:

V prípade funkcií troch premenných sa musíte vysporiadať s trojrozmernou kockou. Je to zložitejšie a menej jasne, ale technicky možné. Na obrázku je pravda zobrazená ako príklad pre booleovskú funkciu troch premenných a zodpovedajúcej kocky.

Tabuľka nie je pravda. Bude to pravda: 1 1 0 0 1 1 0 0 Ako možno vidieť z obrázku, sú možné, zložitejšie tepelné konfigurácie sú možné pre trojrozmerný prípad. Napríklad štyri termíny patriace do jednej plochy kocky sú kombinované do jednej tepelnej absorpcie dvoch premenných:

V všeobecný Môžeme povedať, že 2 K. Podmienky patriace k jednému K.-Harovaná tvár hypercube, ktorá sa v jednom termíne zlepeli K. Premenné.

Na zjednodušenie práce s booleovou funkciou veľkého počtu premenných bolo navrhnuté nasledujúce pohodlné prijatie. Kocka, ktorá je štruktúrou termínu, otočí rovinu, ako je znázornené na obrázku. Zdá sa teda možnosť reprezentovať booleovské funkcie s počtom premennej viac ako dve vo forme plochého stola. V tomto prípade treba pripomenúť, že poradie kódových kódov v tabuľke (00 01 11 10) nezodpovedá poradiu binárnych čísel a buniek, ktoré sú v extrémnych stĺpcoch tabuľky susediaci iné.

Podobne môžete pracovať s piatimi, siedmimi funkciami (povinné prvočíslo), atď., Používanie nepokojných multidimenzionálnych booleovských kociek.

Postup práce s Carno Card

Zdrojové informácie pre prácu s kartou CARNO je nádrž Minimalizovaná funkcia. Tabuľka pravdy obsahuje úplné informácie o logickej funkcii, nastavenie jeho hodnôt na všetkých možných 2 N. Súpravy vstupných premenných X. 1 ... X. N. . Mapa Carno obsahuje aj 2 N. bunky, z ktorých každý je spojený s jedinečnou sadou vstupných premenných X. 1 ... X. N. . Existuje teda vzájomne jednoznačná zhoda medzi pravdou a mapou Carno, a Carno mapa môže byť považovaná za vhodne formátovanú tabuľku pravdy.

V tomto oddiele sa ako príklad použije funkcia štyroch premenných, nastavuje tabuľku pravdy znázornenou na obr. 2A. Mapa Carno pre rovnakú funkciu je znázornená na obr. 2b.

Obr. 2. Vzorka pracuje s mapou Carno

Ďalším spôsobom, ako získať jednoduché implikačné vzorce s malým počtom premenných (a teda nájdenie minimálne DNF) je založené na používaní tzv. Carno kariet.

Mapa Carno - toto Špeciálny pohľad Tabuľka, ktorá vám umožní zjednodušiť proces nájdenia minimálnych formulárov a úspešne sa používa, keď počet premenných nepresahuje šesť. Karnečné karty Pre funkcie v závislosti od premenných N je obdĺžnik delený 2N buniekmi. Každá bunka diagramu je uvedená v súlade s binárnym N-dimenzionálnym množstvom. Hodnoty špecifikovanej funkcie f sú vyrobené na požadované štvorce, ale ak bunka zodpovedá 0, potom zvyčajne zostáva prázdne.

Prvá tabuľka zobrazuje príklad markupu mapy karnote pre funkciu v závislosti od troch premenných. Nižšie štyri kartové bunky zodpovedajú binárnym súborom, v ktorých premenná X trvá 1, štyri horné bunky zodpovedajú množstvám, v ktorých premenná X má hodnotu 0. Štyri bunky tvoriace pravú polovicu karty zodpovedajú množstvám ktoré variabilné y; Má hodnotu 1, atď. Druhá tabuľka zobrazuje značku kariet pre n \u003d 4 premenné.

y. z. - x.	0 0	0 1	1 1	1 0
0	000	001	011	010
1	100	101	111	110

z. w. -- xy.	0 0	0 1	1 1	1 0
00	0000	0001	0011	0010
01	0100	0101	0011	0010
11	1100	1101	1111	1110
10	1000	1001	1011	1010

Na vytvorenie minimálneho DNF sa vykoná postup lepenia "1". Hodnoty spojenia "1" zodpovedajú susedným bunkám, t.j. Bunky sa líšia len v hodnote jednej premennej (na grafickom obraze oddelenej vertikálnej alebo horizontálnej čiary, berúc do úvahy susedstvo protichodných extrémnych buniek).

Proces lepenia "1" prichádza k kombinácii do skupín jednotlivých buniek Carno karty a musia sa dodržiavať tieto pravidlá: \\ t

1. Počet buniek zahrnutých v jednej skupine musí byť vyjadrený počtom viacerých 2, t.j. 2 m, kde m \u003d 0,1,2, ...

2. Každá bunka zahrnutá v skupine 2 M buniek musí mať M susediace v skupine.

3. Každá bunka musí byť aspoň v jednej skupine.

4. Maximálny počet buniek by mal byť zahrnutý v každej skupine, t.j. Žiadna skupina by nemala byť obsiahnutá v inej skupine.

5. Počet skupín by mal byť minimálny.

Funkcia čítania F pre lepiacu skupinu je nasledovná: Premenné, ktoré ušetria rovnaké hodnoty Bunky lepenia skupiny sú zahrnuté v spojení a samotné premenné zodpovedajú hodnotám 1 a hodnotám 0 ich odmietnutia.

Poskytujeme šablóny, ktoré pomáhajú budovať nátery 1 (premenné zvážiť rovnaké, ale nebudeme písať). Na zjednodušenie nahrávania nebudeme označiť premenné, hoci ušetríme svoje označenie ako vo vyššie uvedených tabuľkách.

F \u003d Y & Z & W

		1
		1

Po prvé, pozeráme sa, či existujú povlaky_1 zo 16 buniek pokrývajúcich aspoň jeden odkrytý 1. Nie sú takéto povlaky. Prejdite na povlaky 8 buniek. Vyzeráme, či existujú povlaky 1 z 8 buniek pokrývajúcich aspoň jeden odkrytý 1. Neexistujú takéto povlaky. Prejdite na nátery 4 buniek. Vyzeráme, či existujú povlaky 1 zo 4 buniek pokrývajúcich aspoň jeden odkrytý 1. Existujú dva takéto povlaky. Prejdite na povlaky 2 buniek. Taký povlak. Všetci sa teda pokryli. Ďalej vidíme, či sa môžu odstrániť niektoré nátery, takže všetky jednotky zostávajú pokryté. Na konci, píšeme MDNF: F \u003d ¬x¬zvywv¬yz¬ww.

Komentár. Ak chcete vytvoriť minimálnu funkciu PFF F, stačí vybudovať minimálnu DNF pre funkciu ¬F a potom použite F \u003d ¬FF a de Morganove zákony.

Minimalizácia funkcií pomocou Carno kariet

Pri použití tejto metódy sa logická funkcia zaznamenáva ako mapa KARO, ako je uvedené v bode 1.4. Pripomeňme, že stĺpce a riadky karty CARNO sú uvedené v sivom kóde. Potom bunky, ktoré môžu byť lepené, sú navzájom blízko.

Minimálny DNF sa získa zakrytím buniek obsahujúcich logické 1, obdĺžnikové oblasti. Región by mal obsahovať 2 K. buniek, kde na - Integer (2 k \u003d 1,2; štyri; osem; ...). Pre každý región sa vypracuje kombinácia, v ktorej sú rozdielne vypúšťanie označené symbolom (*).

Pri minimalizácii logickej funkcie reprezentovanej Carno Card (tabuľka 1.14), získavame dve oblasti. Prvá oblasť zodpovedá set 1 * 00, druhá plocha - nastavená 0 \u200b\u200b* 1 *. V dôsledku toho je minimálna DNF (MDNF) napísaná vo forme

Ak chcete získať minimálny PFF v mape Karo podobných obdĺžnikových oblastí, sú zakryté nulové bunky a súpravy zodpovedajúce krytých oblastiach sa zaznamenávajú (tabuľka 1.15).

Ak chcete získať disjunktúry, ktoré tvoria MKNF, premenné sú označené inverziou súborov regiónov. Prvá oblasť zodpovedá Disjunkcii 01 *,

Druhá plocha - SET * 00, DYSUNCTION Funkcie MKNF (tabuľka 1.15) Napíšte vo formulári

Mapy Carno uľahčujú zvýraznenie oblastí spojky (alebo disjunkcií), ktoré podliehajú zjednodušeniu. Z tabuľky 1.15, na príklade možno vidieť, že karty CARNO môžu byť reprezentované ako valce vertikálne a horizontálne na zvýraznenie jednoduchých alebo nulových oblastí.

V praxi sa používajú iné metódy minimalizácie logických funkcií - metóda Petrika, metóda WAICH CARD. Tieto metódy sú však vhodné pre počet premenných na 5. So zvýšením počtu premenných, stávajú objemným, stratia jasnosť. Okrem toho výber oblastí v týchto metódach vo väčšine prípadov sa vykonáva intuitívne, zároveň závisí od individuálnych skúseností a umenia developera, ktorý zabraňuje automatizácii dizajnu a aplikuje sa na počítač.

Príklad 1 [Upraviť Upraviť text WIKI]

Chlapec, ak je matka, otec, dedko a babička. Kohl pôjde chodiť na ulicu, ak a len vtedy, ak je povolený aspoň dvoch príbuzných.
Pre stručnosť, označujeme príbuzných, ak listy:
MOM - X1
Otec - x2.
Dedko - X3
Babička - X4
Dovoľte nám zvážiť značenie súhlasu príbuzných jednotkou, nezhodou - nula. Možnosť ísť na prechádzku s písmenom F, Kolya ide chodiť - F \u003d 1, Kohl nechodí do chodiť - F \u003d 0.
Urobte tabuľku pravdy:

Prekreslite tabuľku pravdy v 2-dimenzionálnom vzhľade:

Usporiadajte v ňom riadky a stĺpce v súlade s sivým kódom. Mapa CARNO:

Vyplňte ho hodnotou z tabuľky pravdy:

Minimalizovať v súlade s pravidlami:

1. 1. Všetky oblasti obsahujú 2-N buniek;

2. Keďže mapa CARNO do štyroch premenných, osi sú umiestnené na hraniciach karty a nie sú viditeľné (viac ako pozri príklad mapy na 5 premenných);

3. Keďže automobilová mapa je štyri premenné, všetky oblasti symetricky osí sú priľahlé k sebe (pozri príklad karty pre 5 premenných.

4. 4. Oblasti S3, S4, S5, S6, ako je to možné;

5. 5. Všetky oblasti sa pretínajú (voliteľný stav);

6. 6. V tomto prípade je racionálna verzia len jedna.

Teraz, podľa minimálneho získaného DNF, môžete vybudovať logickú schému.

Minimalizácia logických funkcií je jednou z typických úloh v procese vzdelávacieho obvodu. Preto sa domnievam, že takýto článok má miesto, ktoré má byť, dúfam, že sa vám to páči.

Prečo to potrebujete?

Komplexnosť logickej funkcie, a teda zložitosť a náklady na schému, ktorý ho vykonáva (reťaze), sú úmerné číslu logické operácie a počet výskytov premenných alebo ich odmietnutí. V zásade je možné zjednodušiť akúkoľvek logickú funkciu priamo pomocou axiómov a logických teoreems, ale spravidla takéto transformácie vyžadujú objemné výpočty.

Okrem toho proces zjednodušenia booleovských výrazov nie je algoritmický. Preto je vhodnejšie použiť špeciálne metódy minimalizácie algoritmic, čo vám umožní jednoduchšie zjednodušiť funkciu jednoduchšie a nezapuknuteľne. Takéto spôsoby zahŕňajú napríklad metódu Kwain, metóda Carno metóda, metóda implikačného testovania, metóda implikant, metóda implikant, metóda McClock atď. Tieto metódy sú najvhodnejšie pre bežnú prax, najmä minimalizáciu logickej funkcie pomocou Carno kariet. Metóda kariet CARNO Udržiava viditeľnosť s počtom premennej nie viac ako šesť. V prípadoch, keď je počet argumentov viac ako šesť, zvyčajne sa používa metóda Queen McCLASKI.

V procese minimalizovania logickej funkcie sa zvyčajne berie do úvahy, v ktorom základe to bude efektívnejšie implementovať jeho minimálny formulár pomocou elektronických obvodov.

Minimalizácia logických funkcií pomocou Carno kariet

Mapa CARNO - grafický spôsob, ako minimalizovať spínacie (booleanové) funkcie, ktoré poskytujú relatívnu jednoduchosť práce s veľkými výrazmi a eliminácia potenciálneho pretekania. Ide o operácie párovej neúplnej lepiacej a elementárnej absorpcie. Mapy Carno sa považujú za prestavané podľa toho, pravda tabuľka funkcie. Carno karty si môžete prezerať ako určité ploché skenovanie N-dimenzionálneho buleva Kuby.

Carno karty boli vynájdené v roku 1952 Edward V. Womech a zlepšil v roku 1953 Maurice Carno, fyzik z Bell Labs a boli navrhnuté tak, aby pomohli zjednodušiť digitálne elektronické obvody.

Na mape Carno sa booleovské premenné prenášajú z tabuľky pravdy a sú objednané pomocou vykurovacieho kódu, v ktorom sa každý nasledujúci počet líši od predchádzajúceho jediného vypúšťania.

Hlavná metóda minimalizácie logických funkcií prezentovaných vo forme CDNF alebo SCPF je prevádzka párovej nekompletnej lepiacej a elementárnej absorpcie. Párovanie lepenie operácie sa uskutočňuje medzi dvoma tepelnými (členmi), ktoré obsahujú rovnaké premenné, ktorých záznam (priamy a inverzný) sa zhodujú pre všetky premenné, okrem jedného. V tomto prípade môžu byť všetky premenné, okrem jednej, môžu byť vyrobené pre konzoly a zostávajúce priame a inverzné položky jednej premennej, aby sa odstránili lepeniu. Napríklad:

Možnosť absorpcie vyplýva z zjavných vyrovnaností

Hlavná úloha pri minimalizácii SDNF a SCFF je teda vyhľadávanie termínov vhodných na lepenie, po ktorom nasleduje absorpcia, ktorá pre veľké formy to môže byť pomerne zložitá úloha. Carno karty poskytujú vizuálny spôsob, ako nájsť takéto výrazy.

Ako viete, Boolovské funkcie n premenných prezentovaných vo forme SDNF alebo SCRF môžu mať v jeho zložení 2n odlišné pojmy. Všetci títo členovia tvoria určitú štruktúru, topologicky ekvivalentnú N-dimenzionálnu Kubu a všetky dva termíny spojené okrajom sú vhodné na lepenie a absorpciu.

Ako možno vidieť z výkresu, sú možné zložitejšie konfigurácie termínov pre trojrozmerný prípad. Napríklad štyri termíny patriace do jednej plochy kocky sú kombinované do jednej tepelnej absorpcie dvoch premenných:

Vo všeobecnosti možno povedať, že 2K termíny patriace do jednej K-dimenzionálnej tváre Hypercube sú zlepené do jedného stupňov, zatiaľ čo premenné K sa absorbujú.

Podobne môžete pracovať s funkciami štyroch, piatich alebo viacerých premenných. Príklady tabuliek pre n \u003d 4 a n \u003d 5 sú znázornené na obrázku. Pre tieto tabuľky je potrebné pripomenúť, že susedné bunky sú v zodpovedajúcich bunkách extrémnych stĺpcov a zodpovedajúcich buniek hornej a dolnej čiary. V prípade tabuliek 5 a viac premenných je tiež potrebné vziať do úvahy, že 4x4 štvorce sú prakticky navzájom v tretej dimenzii, takže zodpovedajúce bunky dvoch susedných štvorcov 4x4 sú sezóny a podmienky zodpovedajúce im môžu byť zlepené.

Mapa Carno možno vypracovať pre ľubovoľný počet premenných, ale je vhodné pracovať s počtom premennej nie viac ako päť. V podstate je Carno karta pravda tabuľka zložená v dvojrozmernej forme. Vďaka použitiu herného kódu v ňom je horná čiara susediaca so spodnou časťou a pravý stĺpec je susedí vľavo, tak ďalej. Celá mapa Karna sa zmení na postavu Torus (Bagel). Na križovatke reťazca a stĺpca je pripevnená zodpovedajúca hodnota z tabuľky pravdy. Po vyplnení karty môžete pokračovať v minimalizácii.

Ak potrebujete získať minimálny DNF, potom mapa považujeme len tie bunky, ktoré obsahujú jednotky, ak potrebujete pff, považujeme tie bunky, ktoré obsahujú nuly. Samotná minimalizácia sa vykonáva podľa nasledujúcich pravidiel (v príklade DNF):

Ďalej vezmite prvú oblasť a pozrite sa na to, aké premenné sa nezmeníme v tejto oblasti, píšeme spojenie týchto premenných, ak zbytočná premenná nula, položte nad ním inverziu. Berieme ďalšiu oblasť, vykonajte to isté ako pre prvú, atď. Pre všetky oblasti. Spojenie oblastí kombinujú disjunkciu.
Napríklad (pre karty na 2 premenných):

Pre CNF je všetko rovnaké, len nám považujeme bunky s nulami, nemeniace sa premenné v tej istej oblasti, kombinujeme v disjunkcii (inverzia sa pridáva cez jednotlivé premenné) a disjunkčné plochy sú kombinované do spojok. Táto minimalizácia sa považuje za dokončenú. Takže pre mapu Carno na obr. 1 Výraz v DNF formáte sa pozrie na:

Vo formáte CNF:

Minimalizácia logických funkcií je jednou z typických úloh v procese vzdelávacieho obvodu. Preto sa domnievam, že takýto článok má miesto, ktoré má byť, dúfam, že sa vám to páči.

Prečo to potrebujete?

Komplexnosť logickej funkcie, a teda zložitosť a náklady na jeho implementačný systém (reťaz) sú úmerné počtu logických operácií a počtu výskytov premenných alebo ich odmietnutia. V zásade je možné zjednodušiť akúkoľvek logickú funkciu priamo pomocou axiómov a logických teoreems, ale spravidla takéto transformácie vyžadujú objemné výpočty.

V procese minimalizovania logickej funkcie sa zvyčajne berie do úvahy, v ktorom základe to bude efektívnejšie implementovať jeho minimálny formulár pomocou elektronických obvodov.

Minimalizácia logických funkcií pomocou Carno kariet

Carno karty boli vynájdené v roku 1952 Edward V. Womech a zlepšil v roku 1953 Maurice Carno, fyzik z Bell Labs a boli navrhnuté tak, aby pomohli zjednodušiť digitálne elektronické obvody.

Možnosť absorpcie vyplýva z zjavných vyrovnaností