Zjednodušovač booleovské algebry

Minimalizace booleovských výrazů v praxi

Zjednodušování logických funkcí je základním krokem při návrhu digitálních obvodů i při optimalizaci softwarového kódu. Cílem je redukovat počet hradel, vstupů nebo logických operací na absolutní minimum, což v hardwaru snižuje zpoždění signálu a spotřebu energie, zatímco v softwaru zlepšuje čitelnost a rychlost vyhodnocování podmínek.

Tento online nástroj provádí exaktní minimalizaci libovolného zadaného výrazu. Na rozdíl od heuristických metod nebo ručního zakreslování do map, které jsou náchylné k chybám, algoritmus systematicky prochází všechny kombinace, identifikuje klíčové vazby a předkládá dvě ekvivalentní, avšak strukturálně odlišné minimální formy: minimální součet součinů (SOP) a minimální součin součtů (POS). Celý proces výpočtu probíhá transparentně a je doprovázen podrobným matematickým zdůvodněním.

---

Podporované zápisy a syntaxe

Návrháři, programátoři a matematici používají pro zápis logických operací různé konvence. Tento zjednodušovač odstraňuje bariéry mezi těmito světy a umožňuje v jediném výrazu volně kombinovat různé styly zápisu. Proměnné se zadávají jako jednotlivá písmena (např. A, B, C). Maximální délka vstupu je omezena na 2,000 znaků a systém podporuje až 6 různých proměnných, což představuje 64 řádků pravdivostní tabulky.

Nástroj interpretuje následující operátory a zápisy:

• AND (konjunkce): Může být zapsán implicitně spojením písmen (např. AB), tečkou A·B, hvězdičkou A*B, programátorským zápisem A && B, logickým slovem A AND B nebo příslušným logickým symbolem. Vícepísmenné řetězce jako ABC jsou automaticky vyhodnoceny jako A AND B AND C.
• OR (disjunkce): Zapisuje se pomocí znaménka plus A + B, programátorských svislic A || B, klíčového slova A OR B nebo logického symbolu.
• NOT (negace): Lze vyjádřit apostrofem za proměnnou A', vykřičníkem !A, slovem NOT A, symbolem ¬A nebo znakem primu.
• XOR (exkluzivní OR): Podporuje zápisy A ^ B, A XOR B a symbol A ⊕ B.
• NAND: Zapisuje se jako A NAND B nebo pomocí symbolu ⊼.
• NOR: Zapisuje se jako A NOR B nebo pomocí symbolu ⊽.
• Konstanty: V zápisu lze přímo použít logické hodnoty 0 a 1.

Pro rychlé seznámení s možnostmi nástroje jsou k dispozici přednastavené příklady, které lze načíst jedním kliknutím. Patří mezi ně "Slučování členů" (demonstrující konsenzus), "Negovaný součin" (ukázka De Morganových zákonů) a "Trojcestný XOR". Vstupní pole lze kdykoli vyčistit tlačítkem Vymazat.

---

Metoda Quine–McCluskey a vyhledání primárních implikantů

Pro nalezení garantovaného minima využívá nástroj Quine–McCluskeyho algoritmus, který doplňuje o metodu přesného minimálního pokrytí. Tento postup je na rozdíl od Karnaughových map (K-map) snadno algoritmizovatelný a spolehlivě zvládá i složitější funkce o 5 či 6 proměnných, kde je lidská představivost v multidimenzionálních mapách již omezena.

Proces minimalizace probíhá v několika krocích:

1. Generování pravdivostní tabulky: Výraz je nejprve normalizován a zobrazen v poli Načteno jako. Následně se sestaví kompletní tabulka pro všech 2ⁿ kombinací (kde n je počet proměnných).
2. Nalezení mintermů a maxtermů: Identifikují se řádky, kde je výsledná hodnota rovna 1 (mintermy, značeno Σm), a řádky, kde je rovna 0 (maxtermy, značeno ΠM).
3. Slučování sousedních řádků: Algoritmus systematicky porovnává dvojice mintermů, které se liší v hodnotě právě jedné proměnné, a slučuje je. Tento proces se opakuje pro skupiny o velikosti 2, 4, 8 atd., dokud je sloučení možné. Výsledkem jsou takzvané primární implikanty.
4. Výběr podstatných primárních implikantů: Jsou vyhledány ty implikanty, které jako jediné pokrývají alespoň jeden minterm. Tyto členy musí být v konečném minimálním výrazu obsaženy.
5. Pokrytí zbývajících řádků: Pokud po výběru podstatných implikantů zůstanou některé jedničkové řádky nepokryté, algoritmus vyřeší takzvaný pokrývací problém a vybere nejmenší možný počet zbývajících implikantů tak, aby byla pokryta celá funkce.

---

Porovnání forem SOP a POS v obvodovém návrhu

Při realizaci logických funkcí pomocí fyzických hradel hraje volba správné formy zásadní roli v efektivitě celého schématu. Nástroj proto generuje obě ekvivalentní formy:

Porovnáním obou výsledných forem v diagnostickém panelu Rychlý přehled (který zobrazuje počet literálů před a po zjednodušení) může návrhář okamžitě určit, která varianta spotřebuje méně materiálu a povede k jednoduššímu plošnému spoji.

---

Diagnostika, verifikace a zpracování chyb

Nástroj po každé změně vstupu okamžitě provádí syntaktickou analýzu a výpočet. Pokud je výraz zadán správně, zobrazí se stavové hlášení o úspěšném zjednodušení a ověření na všech řádcích. Výsledné minimalizované výrazy lze snadno zkopírovat do schránky pomocí tlačítka Kopírovat výsledek.

Zvláštní stavy výrazů

• Tautologie: Pokud je výraz vždy pravdivý, zobrazí se zpráva: „Tento výraz je vždy 1: každá kombinace hodnot ho činí pravdivým.“
• Kontradikce: Pokud je výraz vždy nepravdivý, zobrazí se zpráva: „Tento výraz je vždy 0: žádná kombinace hodnot ho nečiní pravdivým.“
• Již minimální: Pokud vstup nelze dále zjednodušit, systém uživatele informuje textem: „Váš výraz je již v minimální součtové formě.“

Chybová hlášení

Při zadání neplatného výrazu systém přesně lokalizuje problém a zobrazí jedno z následujících hlášení:

• Prázdný vstup: „Zadejte booleovský výraz.“
• Překročení délky: „Udržujte výraz pod hranicí 2,000 znaků.“
• Nepodporovaný znak: „„‹char›“ (pozice ‹position›) není booleovský operátor, proměnná ani konstanta.“
• Chyba syntaxe: „Poblíž pozice ‹position› chybí operátorovi jeho operand – zkontrolujte, zda nezůstal viset znak +, · nebo ⊕.“
• Nesymetrické závorky: „Závorky nejsou vyvážené – přidejte nebo odeberte závorku.“
• Mnoho proměnných: „Tento výraz používá ‹count› různých proměnných; zjednodušovač podporuje nejvýše 6.“

---

Ochrana soukromí při výpočtu

Bezpečnost dat je zajištěna samotnou architekturou této webové aplikace. Veškeré operace, parsování textu, minimalizace pomocí Quine–McCluskeyho algoritmu i generování pravdivostní tabulky probíhají lokálně přímo v internetovém prohlížeči uživatele. Žádná data se neodesílají na externí servery.

---

Často kladené otázky

Jaký je rozdíl mezi výsledky SOP a POS?

Obě formy popisují stejnou funkci. Součet součinů (SOP) spojuje členy AND pomocí operátoru OR, jako například AB' + BC, a mapuje se přímo na obvody AND–OR; součin součtů (POS) spojuje členy OR pomocí operátoru AND, jako například (A + B)(B' + C), a mapuje se na obvody OR–AND. V závislosti na konkrétní funkci může jedna forma vyžadovat méně hradel než druhá, proto nástroj vždy zobrazuje obě.

Jak se hledá minimální forma?

Nástroj sestaví úplnou pravdivostní tabulku, sloučí sousední jedničkové řádky do primárních implikantů (Quine–McCluskeyho metoda), ponechá ty podstatné a zbývající řádky pokryje přesným minimálním pokrytím. Výsledek je garantovaně minimální pro součtovou formu (SOP) – nejedná se o heuristiku – a stejný postup na nulových řádcích vytvoří součinovou formu (POS).

Které způsoby zápisu výrazu jsou podporovány?

Všechny běžné konvence lze libovolně kombinovat: inženýrský styl (AB + A'C, s implicitním AND a apostrofem pro NOT), programátorský styl (A &&!B || C, A ^ B), logické symboly (¬ ∧ ∨ ⊕ ⊼ ⊽) i běžná slova (A AND B OR NOT C, NAND, NOR). Sekvence více písmen jako ABC znamenají A AND B AND C, přičemž slova AND, OR, NOT, XOR, NAND, NOR jsou vždy interpretována jako operátory.

Proč je podporováno nejvýše 6 proměnných?

Šest proměnných již vytváří pravdivostní tabulku o 64 řádcích, což je přibližně limit toho, co je ještě čitelné a ručně kontrolovatelné. Nad tento rámec minimalizace teoreticky stále funguje, ale odvození a tabulka, na kterých je tato stránka postavena, přestávají být užitečné jako názorný důkaz. Pro širší funkce se lépe hodí software pro návrh logických obvodů se souborovým výstupem.