Ontola > diskuze
(Upr. 07.03. 11:38) | Nahlásit

Metodou Karnaughovy mapy minimalizujte funkce:

Můžete mi někdo s tím poradit nechápu jak to řešit.
Předem děkuji za odpověď
Témata: Nezařazené

3 reakce

| Nahlásit
Přeji pěkné odpoledne, Mareli,

tohle se těžko vysvětluje pouhým slovním popisem, ale nějak to zkusím a později dodám i obrázek.

Máte logickou funkci čtyř proměnných f(a,b,c,d). Potřebujete nakreslit schéma (tabulku) tak, aby počet políček této tabulky byl roven počtu kombinací vstupních hodnot funkce f. Tato tabulka musí být pro sudý počet vstupních hodnot čtvercová a pro lichý počet hodnot musí jít o 'přepůlený čtverec'.

V tomto případě nakreslete tabulku 4*4. Nyní nad prvními dvěma sloupci udělejte jednu společnou vodorovnou značku popsanou symbolem a, nad druhým a třetím sloupcem vodorovnou značku popsanou symbolem b, vedle prvních dvou řádků svislou značku popsanou symbolem c a vedle druhého a třetího řádku svislou značku popsanou symbolem d.

Tak docílíte toho, že přesně polovina všech buněk tabulky odpovídá logické hodnotě 1 (označkované buňky) dané logické proměnné a druhá polovina buněk logické hodnotě 0 pro danou logickou proměnnou (neoznačkované buňky). Současně reprezentuje každá buňka jedinečnou kombinaci vstupních hodnot a každé dvě sousední buňky se liší pouze v logickém ohodnocení jedné proměnné.

Tento stav tabulky vidíte na přiloženém obrázku 1.

Vaše funkce je v disjunktivní normální formě, tedy jde o disjunkci formulí, které jsou několikanásobnými konjunkcemi. Tyto dílčí formule nyní zaneseme do tabulky.

První je ¬a¬bcd. Najdeme tedy takovou polovinu tabulky, která není označená značkou a (a tam nabývá logickou hodnotu 0). Tuto polovinu tabulky poté omezíme na případ, kdy i b nabývá hodnoty 0, dále ji opět omezíme na případ, kdy c nabývá hodnoty 1 a kdy d nabývá hodnoty 1. Takto najdete jednu jedinečnou buňku, která odpovídá kombinaci vstupních hodnot a=0, b=0, c=1 a d=1. Zapište do ní symbol 1.

Takto postupujte pro všechny konjunkty a až je vyčerpáte, do všech ostatních buněk vepište 0. Vyjde vám tabulka, kterou ukazuji na obrázku 2.

Nyní musíte najít co největší skupiny jedniček. Jde konkrétně o takové skupiny jedniček, které tvoří čtverce 2x2, dvojice 1x2, řádky 1x4, obdélníky 2x4 nebo celý čtverec 4x4. Útvary se mohou překrývat, je ale nutné, aby byly co největší to jde, abychom obsadili všechny jedničky. A pozor, předpokládejte, že krajní řádky a sloupce tabulky spolu také sousedí, tedy tyto útvary mohou být tvořeny 'přes okraj'.

Na obrázku 3 ilustruji volbu skupin.

Nyní musíme tyto skupiny jako celky vyjádřit pomocí disjunktivní normální formy.

Například červenou skupinu jedniček tvoří celý druhý řádek. Do druhého řádku spadne vstup logické funkce tehdy, pokud jsou proměnné c, d ohodnoceny jako 1. Na proměnných a, b v tomto případě nezáleží, nemají vliv na výsledek funkce. Máme tedy první formuli cd.

Rychle zjistíme, že v případě modrého čtverce jde o formuli cb a v případě zeleného o formuli db. Tyto formule spojíme konjunkcí a máme minimalizovanou funkci:

f(a, b, c, d) = cd + cb + db

která pro všechna ohodnocení zcela ekvivalentní zadané funkci:

f(a, b, c, d) = ¬a¬bcd + abc¬d + ¬abc¬d + a¬bcd + ¬abcd + ab¬cd + ¬ab¬cd + abcd,

jen, jak vidíte, je minimalizovaná a nejde ji už napsat jednodušeji, pokud jsme postupovali správně.

Snad je tedy vše úplně jasné! Určitě se ozvěte, pokud ne.
(Upr. 07.03. 13:20) | Nahlásit
Ještě jen dodám několik technických detailů. Pro minimalizaci logické funkce je Karnaughova mapa vhodná, pokud jde o funkci dvou, tří, čtyř nebo pěti logických proměnných. Pro vyšší počet se stává zcela neúnosnou, proto se používá obecný algoritmus Quine-McCluskey. Je ale o něco náročnější na pochopení než Karnaughova mapa.

Dále stojí za zmínku uvést, že v praktických aplikacích při vývoji číslicových obvodů se občas setkáte s tím, že předem víte, že funkce nikdy nebude mít nějaké konkrétní ohodnocení logických vstupů. Představte si třeba, že byste jako vývojář nějakého číslicového obvodu věděla, že vstup a=1, b=0, c=1, d=0 ani a=0, b=0, c=1, d=0 (první a poslední buňka prvního řádku) nemůže vůbec nikdy vzhledem k vlastnostem obvodu nastat. Pak místo nuly na daná místa Karnaughovy mapy můžete napsat X - jako že je úplně jedno, zda to budu považovat za 0 nebo za 1.

Toho pak využijete při hledání skupin jedniček. Mohli bychom jako skupinu jedniček brát rovnou celé první dva řádky, což je jednoduše formule 'c', protože je úplně jedno, co je v oněch rohových buňkách za hodnoty, tak je třeba budeme považovat za jedničku, aby nám to pomohlo při minimalizaci. Jak ale uvádím, jde jen o zajímavost a v zadání by muselo být uvedeno, že na výstupu pro tuto kombinaci logických vstupů nezáleží. I s takovými příklady jsem se ale setkal.
| Nahlásit
Krásné děkuji vám za odpověď!
 Anonym
Odpovídat lze i bez registrace. Dodržujte pravidla Ontoly
Vložit: Obrázek