Logické vzorce v matematice umožňují popsat a analyzovat různé podmínky a vztahy. Někdy je však užitečné představit tyto vzorce jako disjunktivní normální formu (DNF) nebo konjunktivní normální formu (KNF). To umožňuje zjednodušit výraz a učinit jej srozumitelnějším pro analýzu.
DNF je logický výraz složený z dizjunkcí literátů, kde každý literát může být proměnnou nebo jejím popřením. Disjunkce je logická operace "nebo", což znamená, že alespoň jeden z výrazů musí být pravdivý. DNF umožňuje představit logický vzorec jako souhrn přípustných hodnot proměnných.
KNF je zase logický výraz složený z Konjunktur literátů, kde každý literát může být proměnnou nebo jejím popřením. Konjunktura je logická operace "a", která znamená, že všechny výrazy musí být pravdivé. KNF také umožňuje představit logický vzorec jako souhrn přípustných hodnot proměnných.
Tento článek se bude zabývat jednoduchým algoritmem, který vám umožní získat DNF a KNF z jakéhokoli logického vzorce. Budou prozkoumána základní pravidla pro převod vzorce na DNF a KNF a bude také ukázáno, jak učinit výraz kompaktnějším a čitelnějším.
Základní pojmy
- Vzorec je matematický výraz složený z proměnných a logických operací, jako je konjunktura (logická a), disjunkce (logická nebo) a negace.
- Disjunktivní normální forma (DNF) je logický vzorec, ve kterém se každý disjunkt (kombinace přes nebo) skládá z literátů (proměnných nebo jejich negací) a každá proměnná se používá pouze jednou.
- Konjunktivní normální forma (KNF) je logický vzorec, ve kterém se každý spojivek (kombinace přes a) skládá z literátů (proměnných nebo jejich negací) a každá proměnná se používá pouze jednou.
- Litera je proměnná nebo její negace.
- Konjunktura je logická operace označená symbolem a, která vrací pravdu pouze tehdy, když jsou oba operandy pravdy.
- Disjunkce je logická operace označená symbolem nebo, která vrací pravdu, pokud je alespoň jeden z operandů pravda.
- Negace je logická operace označená symbolem Ne, která mění pravdivost operandu na opak.
Jak získat DNF ze vzorce
1. Rozdělte logický vzorec na jednotlivé prvky (logické proměnné, operace a závorky).
2. Zapište pravdivostní hodnoty každého prvku vzorce do tabulky pravdivosti. Chcete-li to provést, vytvořte všechny možné kombinace hodnot logických proměnných a určete výsledek pro každou kombinaci.
3. Vytvořte logický vzorec v disjunktivní normální formě pomocí výsledků pravdivostní tabulky. Chcete-li to provést, zkombinujte Prvky vzorce, které berou hodnotu "1", Pomocí "nebo" (symbol "|"). Každý prvek vzorce musí být uzavřen v závorkách.
4. V případě potřeby přiveďte DNF k kanonickému vzhledu. Kanonický pohled na DNF naznačuje, že každá závorka má stejný počet prvků a všechny závorky obsahují všechny logické proměnné (možná s negacemi).
5. Zkontrolujte, zda je výsledná DNF správná, pomocí pravdivostní tabulky.
Použití DNF umožňuje snadnější analýzu a práci s logickými vzorci, zejména v kontextu kombinačních obvodů a programování.
Jak získat KNF ze vzorce
Chcete-li získat KNF ze vzorce, musíte postupovat podle následujících kroků:
1. Rozložte vzorec na elementární logické výrazy pomocí logických operátorů (konjunktura, disjunktura, negace a implikace).
2. Aplikujte de Morganovy zákony k přeměně implikací a negací:
- Implikace: vyměňte výraz "a → B" za "~A ∨ B".
- Popírání: vyměňte výraz " ~(a ∨ B) "za" ~A ∧ ~B "a výraz" ~(a ∧ B) "za"~A ∨ ~B".
3. Otevřete závorky a použijte zákony distribuce k převodu logických operací:
- Distribuce konjunktury vzhledem k disjunktuře: vyměňte výraz "a ∧ (B ∨ C)" za "(A ∧ B) ∨ (A ∧ C)".
- Distribuce disjunkce vzhledem ke konjunktuře: vyměňte výraz "a ∨ (B ∧ C)" za "(A ∨ B) ∧ (A ∨ C)".
4. Uveďte výraz do kanonického tvaru KNF:
- Konjunktura disjunktů by měla být provedena pouze proměnnými.
- Eliminujte opakující se disjunkty.
Důsledná aplikace těchto kroků tedy umožňuje získat KNF z tohoto vzorce.
Příklady transformace
Podívejme se na několik příkladů konverze logických vzorců na DNF a KNF.
Příklad 1:
Původní vzorec: P ∨ Q
| Funkce P | Funkce Q | Původní vzorec | DNF | KNF |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Příklad 2:
Původní vzorec: (P ∧ Q) ∨ R
| Funkce P | Funkce Q | Funkce R | Původní vzorec | DNF | KNF |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
Zvláštní případ
V některých případech, při práci se vzorci, mohou nastat zvláštní situace, které vyžadují zvláštní pozornost.
Jedním z takových případů je vzorec, který postrádá negace. V tomto případě budou DNF a KNF vypadat následovně:
- DNF: vzorec bude prezentován jako součet děl proměnných a jejich negací;
- KNF: vzorec bude prezentován jako součin součtů proměnných a jejich negací.
Také je třeba vzít v úvahu případ, kdy se vzorec skládá pouze z jedné proměnné. V tomto případě:
- DNF bude prezentována jako součet děl této proměnné a její popření;
- KNF bude prezentován jako součet této proměnné a její negace.
Je třeba mít na paměti tyto zvláštní případy a vzít je v úvahu při získávání DNF a KNF ze vzorce.
Algoritmus pro DNF a KNF
Pro získání DNF (disjunktivní normální forma) a KNF (konjunktivní normální forma) ze vzorce je nutné provést následující kroky:
1. Uvedení vzorce do normální formy:
- Odstranění dvojitého popírání.
- Uplatňování zákonů de Morgana.
- Použití asociativity a komutativnosti logických operací.
- Použití distribučního zákona.
2. Rozdělení vzorce na elementární výrazy:
- Rozdělení vzorce se provádí na formuly, kde každá formula obsahuje pouze jednu jednoduchou logickou operaci.
3. Budování DNF:
- Pro každou Formuli je vytvořena tabulka pravdivosti.
- V tabulce pravdivosti jsou zvýrazněny řádky, kde je podformula pravdivá.
- Z těchto řádků se vytvoří spojivka, která bude DNF.
4. Budování KNF:
- Pro každou Formuli je vytvořena tabulka pravdivosti.
- V tabulce pravdivosti jsou zvýrazněny řádky, kde je podformula falešná.
- Z těchto řádků se skládá disjunkce, která bude KNF.
Po provedení všech popsaných kroků tedy získáme DNF a KNF pro původní vzorec.
Aplikace DNF a KNF
Disjunktivní normální forma (DNF) a konjunktivní normální forma (KNF) jsou široce používány v logice a matematice pro analýzu a zjednodušení bulových funkcí.
Aplikace DNF umožňuje vyřešit problém hledání možností splnění podmínky rozdělením vzorce na disjunkci. Každá disjunkce definuje samostatnou sadu hodnot proměnných, ve kterých je vzorec pravdivý. To může být užitečné například při navrhování digitálních obvodů nebo při analýze logického výrazu.
KNF se naopak používá k odhalování rozporů nebo chyb. Vzorec v KNF má vzhled, kdy jsou všechny proměnné spojeny spojivkami, to znamená, že každá proměnná je reprezentována v každé ze sad hodnot v KNF. Pokud jsou hodnoty proměnných KNF pravdivé, znamená to, že vzorec má rozpor nebo chybu. KNF se používá k ověření správnosti logického výrazu nebo k identifikaci chyb v programovém kódu.
Použití DNF a KNF umožňuje zjednodušit analýzu a účetnictví různých kombinací hodnot proměnných. To umožňuje optimalizovat funkce a systémy, zvýšit spolehlivost a efektivitu programů nebo zařízení. Při vývoji softwaru nebo navrhování složitých systémů se doporučuje používat DNF a KNF k analýze a optimalizaci logických výrazů.