Konjunktivní normální forma (KNF) a disjunktivní normální forma (DNF) jsou hlavními formami reprezentace logických výrazů. Umožňují vám představit jakoukoli bulevou funkci ve formě konjunktury (KNF) nebo disjunkce (DNF) logických proměnných a jejich negací. Sestavování KNF a DNF podle tabulky pravdivosti je jednou z hlavních metod řešení logických problémů a budování logických obvodů.
Sestavení KNF a DNF podle pravdivostní tabulky začíná analýzou výstupních hodnot funkce na různých kombinacích hodnot vstupních proměnných. Pro každý řádek pravdivostní tabulky, ve kterém funkce přebírá hodnotu "1", je sestaven příslušný člen KNF nebo DNF. V KNF se používají konjunktury a v DNF disjunktury, které se kombinují logickým nebo.
Sestavování KNF a DNF podle tabulky pravdivosti je proces, který vyžaduje pozornost a přesnost. Pro úspěšné sestavení KNF a DNF je nutné jasně pochopit, jaké hodnoty proměnných vedou k výsledku " 1 " a jak je kombinovat pomocí logických operací. V tomto článku se podíváme na to, jak sestavit KNF a DNF podle tabulky pravdivosti na příkladu konkrétní bulové funkce.
Popis tabulky pravdivosti
Tabulka pravdivosti má následující strukturu:
- První řádek tabulky obsahuje nadpisy sloupců, které označují proměnné, které jsou součástí výrazu, a samotný výraz.
- Následující řádky tabulky obsahují kombinace hodnot pravdivosti pro proměnné a hodnoty pravdivosti pro výraz.
V tabulce pravdivosti může každá proměnná mít pouze dvě možné hodnoty - pravdu (1) nebo lež (0). Počet řádků pravdivostní tabulky je určen počtem proměnných ve výrazu a je roven 2^n, kde n je počet proměnných.
Hodnota pravdivosti pro výraz je určena na základě logických operací aplikovaných na proměnné ve výrazu. Každá kombinace hodnot proměnných odpovídá jednomu řádku tabulky pravdivosti. Hodnota pravdivosti pro výraz se vypočítá aplikací logických operací na hodnoty proměnných.
Tabulka pravdivosti umožňuje analyzovat a vypočítat hodnoty pravdivosti pro složité logické výrazy a také ji použít k sestavení KNF (konjuktivní normální forma) a DNF (disjunktivní normální forma) pro tyto výrazy.
Hodnoty proměnných
Pro sestavení KNF a DNF podle tabulky pravdivosti je důležité určit hodnoty proměnných, pro které byla Tabulka pravdivosti postavena.
V tomto kontextu jsou proměnné často označeny velkými písmeny latinské abecedy, jako je A, B, C a tak dále.
Každá proměnná může mít pouze dvě hodnoty: skutečná hodnota 1 nebo falešná hodnota 0.
Hodnoty proměnných v tabulce pravdivosti lze nastavit jako sadu kombinací 0 a 1, kde každá kombinace odpovídá určitému souboru hodnot proměnných.
Hodnoty proměnných jsou základními stavebními kameny při sestavování KNF a DNF podle tabulky pravdivosti, protože to jsou ty, které určují podmínky, za kterých bude výraz pravdivý nebo nepravdivý.
Vezměme si příklad. Řekněme, že máme tabulku pravdivosti se dvěma proměnnými a A B:
| A | Do | Výsledek |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Zde proměnné a A B berou hodnoty 0 nebo 1 v závislosti na příslušné kombinaci. Výsledek odpovídající kombinace bude 1 nebo 0 v závislosti na logickém výrazu, který je daný.
Pro sestavení KNF a DNF je nutné pečlivě analyzovat hodnoty proměnných v pravdivostní tabulce a použít je k vytvoření odpovídajícího logického výrazu.
Hodnoty funkce
Zaznamenáním tabulky pravdivosti můžeme vidět, jak se hodnoty funkce mění v různých kombinacích hodnot proměnných. Každý řádek pravdivostní tabulky odpovídá jedné kombinaci hodnot proměnných.
Zvažte například funkci " a "(logické"a"). V tabulce pravdivosti pro tuto funkci jsou hodnoty funkce 1 pouze v případě, že obě hodnoty jsou
Sestavování ČLF
Konjunktivní normální forma (KNF) je výrazem logické funkce sestávající z konjunktiv (logických "a") elementárních výroků nebo jejich negací. Sestavení KNF podle tabulky pravdivosti pomáhá zjednodušit a analyzovat složité logické funkce.
Pro sestavení tabulky pravdivosti je nutné:
- Zvažte řádky pravdivostní tabulky, ve kterých je hodnota funkce 1.
- V každém z těchto řádků vytvořte konjunkturu elementárních výroků nebo jejich negací.
- Zkombinujte získané konjunktury do jednoho výrazu pomocí dizjunkce (logické "nebo").
Podívejme se například na následující tabulku pravdivosti:
| A | B | C | F(A, B, C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
Z tabulky je vidět, že hodnoty funkce F jsou 1 v řádcích 2, 3 a 4. Pro tyto řádky vytváříme konjunktury:
- (ne A) a (ne B) A C
- (ne A) A B a (ne C)
- (ne A) A B A C
Kombinujeme získané konjunktury pomocí disjunktury:
(ne A) a (ne B) A C nebo (ne A) A B a (ne C) nebo (ne A) A B A C
Tímto způsobem se ČLF pro danou funkci rovná výrazu (ne A) a (ne B) A C nebo (ne A) A B a (ne C) nebo (ne A) A B A C.
Vyloučení hodnot 0
Při sestavování KNF (konjuktivní normální forma) a DNF (disjunktivní normální forma) podle tabulky pravdivosti je často nutné vyloučit hodnoty 0.
Chcete-li vyloučit hodnoty 0 z tabulky pravdivosti, postupujte podle následujících kroků:
- Analyzujte tabulku a najděte řádky, kde je hodnota funkce 0.
- Pro každý řádek, který najdete, jej vyloučte z dalšího použití při sestavování KNF a DNF.
Pokud po vyloučení hodnot 0 zbyly řádky v pravdivostní tabulce, můžete zbývající řádky použít k sestavení KNF a DNF.
Vedoucí k elementárním konjunkturám
Základní myšlenkou přivádění k elementárním konjunkturám je rozklad komplexního logického výrazu na jednoduché, elementární logické proměnné a jejich negace Spojené operátory konjunktury a disjunktury.
K vyvolání elementárních Konjunktur lze použít tabulku pravdivosti logického výrazu. Nejprve určete hodnoty logických proměnných, pro které je daný výraz pravdivý, a poté výraz rozložte na konjunkturu elementárních spojivek pomocí operátorů spojivek a disjunktů.
Přivedení k elementárním konjunkturám usnadňuje další práci s logickými výrazy, protože elementární konjunktury lze nezávisle zvážit a lze je použít k vytvoření složitějších logických výrazů.
Sestavování DNF
Proces sestavování DNF podle tabulky pravdivosti sleduje následující kroky:
- Určete počet proměnných: Podívejte se na tabulku pravdivosti a určete, kolik proměnných se na výrazu podílí.
- Určete řádky, ve kterých je výraz pravdivý: Podívejte se na tabulku pravdivosti a zvýrazněte řádky, ve kterých výraz bere hodnotu "1" (pravda).
- Vytvořte spojivky pro tyto řádky: Pro každý řádek, ve kterém je výraz pravdivý, vytvořte konjunkturu proměnných nebo jejich negací. Každá konjunktura bude představovat samostatný spojitý DNF.
- Spojte všechny konjunktury: Zkombinujte všechny spojivky vytvořené v předchozím kroku pomocí symbolu "nebo" ("∨"). To bude závěrečná fáze.
Podívejme se například na tabulku pravdivosti:
| p | q | r | Výraz |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
Pomocí navrhovaných kroků lze vytvořit DNF:
- Pro první řádek pravdivostní tabulky (p=0, q=0, r=0) získáme spojivku !p∧!q∧!r.
- Pro druhý řádek (p=0, q=0, r=1) dostaneme spojivku !p∧!q∧r.
- Pro čtvrtý řádek (p=0, q=1, r=1) dostaneme spojivku !p∧q∧r.
Výsledná DNF bude vypadat následovně:
Získali jsme tedy DNF, které umožňuje představit všechny možné kombinace hodnot proměnných, ve kterých se výraz stává skutečným.
Vyloučení hodnot 1
Při sestavování KNF a DNF podle tabulky pravdivosti jsou možné případy, kdy jsou některé hodnoty proměnných vyloučeny. Zejména hodnoty proměnných, ve kterých funkce přebírá hodnotu 1, mohou být vyloučeny z KNF nebo DNF.
Chcete-li vyloučit hodnoty 1, musíte v tabulce pravdivosti zkontrolovat, které kombinace proměnných vedou k hodnotě 1 pro funkci. Poté můžete vytvořit KNF nebo DNF, s výjimkou těchto kombinací.
Například nechte nastavit funkci f (x, y, z) = x ∨ (y ∧ z).
| x | y | z | f(x, y, z) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
V tomto příkladu bere funkce f hodnotu 1 pro kombinace (0, 0, 1), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0) a (1, 1, 1). K vyloučení těchto hodnot z KNF nebo DNF je nutné použít operace negace, konjunktury a disjunktury.
S výjimkou hodnot 1 je tedy možné kompaktněji prezentovat funkci v KNF nebo DNF, což může být užitečné při zjednodušování výrazů bulů a optimalizaci logických obvodů.
Vedoucí k elementárním disjunktům
Kroky k uvedení logického výrazu do elementárních disjunktů:
- Zapisujeme pravdivou tabulku pro danou logickou funkci.
- Vypočítáme logický výraz v každém řádku pravdivostní tabulky, kde se výsledek funkce rovná pravdě (1).
- Pro každý řádek, kde se ukáže pravda, vytvoříme disjunkci (logickou nebo) elementárních logických proměnných pomocí negace pro proměnné, které se rovnají lóži (0).
- Spojujeme všechny elementární disjunkce pomocí logické a (konjunktury).
Nechť je dána Logická funkce F(A, b, c) = a∧(b∨c). Pro tuto funkci sestavíme tabulku pravdivosti:
| a | b | c | F(a, b, c) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
Z tabulky pravdivosti je vidět, že funkce F se rovná pravdě pouze ve čtvrtém řádku. V souladu s tím by elementární disjunkce pro tento řádek byla b∨c. logický výraz F(a, b, c) = a∧(b∨c) lze tedy představit jako KNF, což jej přivádí k elementárním disjunkcím:
KNF: F(a, b, c) = (¬a∧b∧¬c) ∨ (¬a∧b∧c)
Přivedení logické funkce k elementárním disjunktům tedy umožňuje kompaktnější prezentaci ve formě KNF, což usnadňuje vyjádření a analýzu logických operací.
Příklad
Podívejme se na několik příkladů sestavování KNF a DNF podle tabulky pravdivosti.
Příklad 1:
Podívejme se na tabulku pravdivosti následujícího výrazu:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Chcete-li vytvořit KNF, musíte vzít řádky tabulky, ve kterých je hodnota funkce 0, a sloučit je pomocí logické nebo. V tomto případě bude KNF vypadat takto:
F = (~A & ~B & ~C) | (A & ~B & C) | (A & B & C)
Chcete-li vytvořit DNF, musíte vzít řádky tabulky, ve kterých je hodnota funkce 1, a sloučit je pomocí logického i. v tomto případě bude DNF vypadat takto:
F = (A & C) | (B & C) | (~A & ~B & C) | (~A & ~B & ~C)
Příklad 2:
Podívejme se na tabulku pravdivosti následujícího výrazu:
| P | Q | R | G |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
KNF pro tento výraz bude vypadat takto:
G = (~P & ~Q & ~R) | (~P & Q & ~R) | (P & ~Q & ~R) | (P & Q & ~R)
DNF pro tento výraz bude vypadat takto:
G = (~P & ~Q & R) | (~P & Q & R) | (P & ~Q & R) | (P & Q & R)