Disjunktivní a konjunktivní normální formy výrokové algebry. Pro každou funkci výrokové logiky lze sestavit pravdivostní tabulku. Inverzní problém je také vždy řešitelný. Uveďme několik definic.
Elementární konjunkce (konjunkce) se nazývají konjunkce proměnných nebo jejich negace, ve kterých se každá proměnná vyskytuje nejvýše
jednou.
Disjunktivní normální forma(DNF) je formule, která má tvar disjunkce elementárních spojek.
Elementární disjunkce (disjunkce) se nazývají disjunkce proměnných s negacemi nebo bez nich.
Konjunktivní normální forma(CNF) je formule, která má tvar konjunkce elementárních disjunkcí.
Pro každou funkci výrokové algebry lze najít množinu disjunktivních a konjunktivních normálních forem.
Algoritmus pro konstrukci DNF:
1. Přejděte na Booleovské operace pomocí ekvivalentních transformačních vzorců.
2. Přejděte na vzorce s blízkými negacemi, tedy na vzorec, ve kterém se negace nenacházejí výše než nad proměnnými – aplikujte De Morganovy zákony.
3. Otevřete závorky - použijte zákony distributivity.
4. Vezměte opakující se termíny jednou za druhým – zákon idempotence.
5. Aplikujte zákony absorpce a poloviční absorpce.
Příklad 6. Najděte vzorce DNF: .
V Booleově algebře je to pravda princip duality. Je to následovně.
Funkce je volána dvojí na funkci if . Tito. Abychom našli funkci duální k dané, je nutné sestrojit negaci funkce z negací argumentů.
Příklad 7. Najděte funkci dual to .
Mezi elementární funkce algebra logiky 1 je duální k 0 a naopak, x je duální k x, duální k , duální a naopak.
Pokud ve vzorci F 1 představující funkci nahradíme všechny spojky
na disjunkci, disjunkci na konjunkci, 1 na 0, 0 na 1, pak dostaneme vzorec F * reprezentující funkci * duální na .
Konjunktivní normální forma (CNF) je duální koncept pro DNF, takže ji lze snadno zkonstruovat podle následujícího schématu:
Příklad 8. Najděte vzorec CNF: .
S použitím výsledku příkladu 6 máme
Dokonalé disjunktivní a dokonalé konjunktivní normální formy. V každém z typů normálních forem (disjunktivní a konjunktivní) lze rozlišit třídu dokonalých forem SDNF a SCNF.
Dokonalá elementární konjunkce je logickým součinem všech proměnných s negací nebo bez negace a každá proměnná se v součinu vyskytuje pouze jednou.
Jakékoli DNF lze redukovat na SDNF rozdělením konjunkcí, které neobsahují všechny proměnné, tzn. přičtením za chybějící proměnnou se x i vynásobí pomocí distributivního zákona
Příklad 9. Najděte SDNF pro DNF z příkladu 6
Dokonalá elementární disjunkce je logický součet všech proměnných s negací nebo bez negace a každá proměnná je do součtu zahrnuta pouze jednou.
Jakýkoli CNF může být redukován na SCNF přidáním konjunkce, která neobsahuje žádnou proměnnou Xi konjunkcí a použitím distributivního zákona
Příklad 10. Přineste KNF do SKNF:
Pro konstrukci SCNF můžete použít diagram
Příklad 11. Najděte SCNF pro vzorec z příkladu 6.
Každá funkce má SDNF a navíc jedinečný. Každá funkce má SCNF a navíc unikátní.
Protože SDNF a SKNF jsou jednoznačně definovány vzorci, lze je sestavit pomocí pravdivostní tabulky vzorce.
Pro konstrukci SDNF je nutné vybrat řádky, ve kterých F nabývá hodnotu 1, a zapsat k nim dokonalé elementární spojky. Pokud je hodnota proměnné v požadovaném řádku pravdivostní tabulky rovna jedné, pak se v dokonalé konjunkci bere bez negace, je-li nula, pak s negací. Pak dokonalé spojky (jejich počet se rovná počtu jednotek v tabulce) spojíme disjunkčními znaménky.
Pro konstrukci SCNF pomocí pravdivostní tabulky je nutné vybrat v ní řádky, kde F = 0, a zapsat dokonalé elementární disjunkce a poté je spojit znaménky konjunkce. Pokud v požadovaném řádku pravdivostní tabulky (F=0) hodnota proměnné odpovídá nule, pak se v dokonalé klauzuli bere bez negace, je-li jedna, pak s negací.
Příklad 12. Najděte SDNF a SCNF pomocí pravdivostní tabulky pro vzorec z příkladu 6.
Tabulka 14 ukazuje pouze konečnou hodnotu F=10101101. Platnost tohoto tvrzení byste si měli ověřit sami sestavením podrobné pravdivostní tabulky.
Tabulka 14
| X | y | z | ||
Příklad. Najděte vzorce CNF 
~ 
~
Dokonalou disjunktivní normální formu SDNF lze zkonstruovat pomocí následujícího algoritmu:
1. = 1. Algoritmus DNF
2. = 2. Algoritmus DNF
3. = 3. Algoritmus DNF
4. = 4. Algoritmus DNF
5. Vynechejte stejně nepravdivé výrazy, tedy výrazy formuláře
6. Doplňte zbývající termíny chybějícími proměnnými
7. Opakujte bod 4.
Příklad. Najděte vzorce SDNF.
~
Pro konstrukci SCNF můžete použít následující schéma:
Příklad. Najděte vzorce SDNF.
~
Je známo (Věty 2.11, 2.12), že SDNF a SCNF jsou jednoznačně definovány vzorcem, a proto je lze sestavit pomocí pravdivostní tabulky vzorce.
Schéma pro konstrukci SDNF a SCNF podle pravdivostní tabulky je uvedeno níže pro vzorec ~ :
 ~
| ||||
| 1 0 1 0 1 1 0 1 | SDNF; SKNF. |
2.2. Cvičení.
2.2.1 Níže jsou uvedeny booleovské výrazy. Zjednodušte výrazy své varianty co nejvíce pomocí Booleových logických zákonů. Poté pomocí pravdivostních tabulek porovnejte svůj zjednodušený výraz s původním.
2.2.2. Objasněte otázku ekvivalence f 1 a f 2 jejich redukcí na SDNF (tab. 1).
2.2.3. Najděte duální funkci pro f 3 pomocí zobecněného a booleovského principu (tabulka 1). Porovnejte výsledky.
| № | f 1 | f 2 | f 3 |
 | |||
 |
|||
 | |||
 | |||
 | |||
 |  |
||
 |  |
||
 |
|||
 | |||
 | |||
 |
|||
 | |||
 |  |
||
 | |||
 |
2.3. Kontrolní otázky.
2.3.1. Definujte prohlášení.
2.3.2. Uveďte hlavní operace na výpisu.
2.3.3. Co je pravdivostní tabulka?
2.3.4. Vytvořte pravdivostní tabulky pro následující vzorce:
~ ~ 
~ ;
2.3.5. S ohledem na konvence o pořadí operací vynechejte ve vzorcích závorky „navíc“ a znaménko „ “:
;
2.3.6. Pomocí ekvivalentních transformací dokažte identickou pravdivost vzorců:
2.3.7. Najít duální vzorce:
)
2.3.8. Zredukujte následující vzorce na dokonalou formu DNF (SDNF):
~
2.3.9. Zredukujte následující vzorce na dokonalou formu CNF (SCNF):
~
Předmět:„Minimalizace booleovských funkcí. Logika"
Cílová: Získání praktických dovedností v práci s metodami pro minimalizaci booleovských funkcí.
3.1. Teoretické informace.
Minimální formy
Jak bylo ukázáno v, jakákoli booleovská funkce může být reprezentována v dokonalé normální formě (disjunktivní nebo konjunktivní). Navíc je taková reprezentace prvním krokem v přechodu od tabulkové specifikace funkce k jejímu analytickému vyjádření. V následujícím budeme vycházet z disjunktivní formy a odpovídajících výsledků pro konjunktivní forma se získává na principu duality.
Kanonický problém syntézy logických obvodů na booleovské bázi spočívá v minimalizaci booleovských funkcí, tj. k jejich reprezentaci v disjunktivní normální formě, která obsahuje nejmenší počet písmen (proměnných a jejich negací). Takové formy se nazývají minimální. Při kanonické syntéze se předpokládá, že na vstupy obvodu jsou přiváděny oba signály a jejich inverze.
Vzorec uvedený v disjunktivní normální formě je zjednodušen opakovaným použitím operace lepení a operace absorpce a (duální identity pro konjunktivní normální formu mají tvar: a ). Zde a může být chápán jako jakýkoli vzorec Booleovy algebry. V důsledku toho se dostáváme k analytickému vyjádření, kde další transformace již nejsou možné, tzn. dostaneme slepou uličku.
Mezi slepými formami existuje také minimální disjunktivní forma, která nemusí být jedinečná. Abyste se ujistili, že daný slepý formulář je minimální, musíte najít všechny slepé formuláře a porovnat je podle počtu písmen, které obsahují.
Nechť je například funkce uvedena v dokonalé normální disjunktivní formě:
Seskupení termínů a použití operace lepení máme .
Další metodou seskupování dostaneme:
Obě formy slepé uličky nejsou minimální. Chcete-li získat minimální tvar, musíte uhodnout opakování jednoho termínu v původním vzorci (toto lze provést vždy, protože ). V prvním případě může být takovým členem . Pak . Přidáním výrazu získáme: . Po prozkoumání všech možných možností se můžete ujistit, že poslední dva formuláře jsou minimální.
Práce se vzorci na této úrovni je jako bloudění ve tmě. Proces hledání minimálních forem se stane vizuálnějším a účelnějším, pokud použijete některá grafická a analytická znázornění a symboly speciálně vyvinuté pro tento účel.
Vícerozměrná krychle
Každý vrchol -rozměrné krychle může být spojen se složkou jednotky. V důsledku toho je podmnožina označených vrcholů zobrazením na -rozměrné krychli booleovské funkce proměnných v dokonalé disjunktivní normální formě. Na Obr. 3.1 ukazuje takové mapování pro funkci z článku 3.7.
Obr. 3.1 Zobrazení funkce prezentované v SDNF na trojrozměrné krychli
Pro zobrazení funkce proměnných prezentovaných v jakékoli disjunktivní normální formě je nutné stanovit shodu mezi jejími minitermy a prvky -rozměrné krychle.
Minitermíny (-1) hodnosti lze považovat za výsledek slepení dvou miniterminů hodnosti (součást jednoty), tzn. 
, Na -rozměrné krychli to odpovídá nahrazení dvou vrcholů, které se liší pouze hodnotami souřadnic spojujících tyto vrcholy s hranou (hrana údajně zakrývá vrcholy, které k ní přiléhají). Minitermy (-1)-tého řádu tedy odpovídají hranám -rozměrné krychle. Podobně je stanovena korespondence minitermů (-2)-tého řádu s plochami -rozměrné krychle, z nichž každá pokrývá čtyři vrcholy (a čtyři hrany).
Prvky -rozměrné krychle charakterizované rozměry se nazývají -krychle. Vrcholy jsou tedy 0-kostky, hrany jsou 1-kostky, plochy jsou 2-kostky atd. Když zobecníme výše uvedené úvahy, můžeme předpokládat, že miničlen ()tého řádu v disjunktivní normální formě pro funkci proměnných je reprezentován -kostkou a každá -kostka pokrývá všechny ty -krychle nižší dimenze, které jsou spojeny s jejími vrcholy. . Jako příklad na Obr. 3.2 ukazuje funkci tří proměnných. Zde minitermy odpovídají 1-krychli () a miniterm je reprezentován 2-kostkou ().
Obr.3.2 Pokrytí funkcí 
Takže jakákoli disjunktivní normální forma je mapována na -rozměrnou krychli pomocí sady -krychlí, které pokrývají všechny vrcholy odpovídající složkám jednoty (0-krychle). Platí i obrácené tvrzení: pokud určitá množina -kostek pokrývá množinu všech vrcholů odpovídajících jednotkovým hodnotám funkce, pak je disjunkce minitermů odpovídajících těmto -kostkám vyjádřením této funkce v disjunktivní normále. formulář. O takové sbírce -kostek (nebo jejich odpovídajících minitermů) se říká, že tvoří obal funkce.
Touha po minimální formě je intuitivně chápána jako hledání takové krytiny, jejíž počet kostek by byl menší a jejich rozměr větší. Krytí odpovídající minimální formě se nazývá minimální krytí. Například pro krycí funkci na Obr. 3.3 splňuje minimální formy 
A 
.
Rýže. 3.3 Pokrytí funkcí.
vlevo, odjet – ; napravo –
Zobrazení funkce na prostorové krychli je jasné a jednoduché, když . Čtyřrozměrnou krychli lze znázornit tak, jak je znázorněno na obr. 3.4, který ukazuje funkci čtyř proměnných a její minimální pokrytí odpovídající výrazu 
. Použití této metody vyžaduje tak složité konstrukce, že všechny její výhody jsou ztraceny.
Rýže. 3.4 Zobrazení funkcí na čtyřrozměrné krychli
Carnotovy mapy
Další metoda pro grafické zobrazení booleovských funkcí používá Carnotovy mapy, což jsou speciálně organizované korespondenční tabulky. Sloupce a řádky tabulky odpovídají všem možným množinám hodnot nejvýše dvou proměnných a tyto množiny jsou uspořádány v takovém pořadí, aby se každá následující lišila od předchozí v hodnotě pouze jedné z proměnných. . Díky tomu se sousední buňky tabulky horizontálně a vertikálně liší hodnotou pouze jedné proměnné. Buňky umístěné na okrajích tabulky jsou také považovány za sousední a mají tuto vlastnost. Na Obr. Obrázek 3.5 ukazuje Karnaughovy mapy pro dvě, tři, čtyři proměnné.
 |
|||||
 |
|||||
 |
|||||
Rýže. 3.5 Carnaughovy mapy pro dvě, tři a čtyři proměnné
Stejně jako v běžných pravdivostních tabulkách jsou buňky množin, ve kterých funkce nabývá hodnoty 1, vyplněny jedničkami (nuly se většinou nevejdou, odpovídají prázdným buňkám). Například na Obr. 3,6, A ukazuje Karnaughovu mapu pro funkci, jejíž zobrazení na čtyřrozměrné krychli je uvedeno na Obr. 3.4. Pro zjednodušení jsou řádky a sloupce odpovídající hodnotám 1 pro proměnnou zvýrazněny složenou závorkou označující tuto proměnnou.
 |
|||
 |
|||
Rýže. 3.6 Zobrazení funkce čtyř proměnných na Carnaughově mapě
a) a jeho minimální krytí b)
Mezi mapování funkcí na n-rozměrná krychle a Carnotova mapa existuje vzájemná korespondence. Na Carnotově mapě s-kostka odpovídá množině 2 sousedních buněk umístěných v řadě, sloupci, čtverci nebo obdélníku (s přihlédnutím k blízkosti protilehlých okrajů mapy). Proto všechna výše uvedená ustanovení (viz odst. vícerozměrná krychle), platí pro mapy Karnaugh. Takže na Obr. 3,6, b zobrazuje pokrytí mapových jednotek odpovídající minimální disjunktivní formě 
danou funkci.
Čtení miniterminů z Karnaughovy mapy se provádí pomocí jednoduché pravidlo. Tvoření buněk s-kostka, dát minitr (n–s)-th pořadí, které zahrnuje ty (n–s) proměnné, které si zachovávají stejné hodnoty s-cube, kde hodnota 1 odpovídá samotným proměnným a hodnota 0 odpovídá jejich negacím. Proměnné, které si nezachovávají své hodnoty pro s-kostka, v minitermínu chybí. Různé způsoby čtení vedou k různým reprezentacím funkce v disjunktivní normální formě (ten úplně vpravo je minimální) (obrázek 3.7).
 |  |
||||||||
 |
|||||||||
Použití Karnaughových map vyžaduje jednodušší konstrukce ve srovnání s mapováním na n-rozměrná krychle, zejména v případě čtyř proměnných. Pro zobrazení funkcí pěti proměnných se používají dvě Karnaughovy mapy pro čtyři proměnné a pro funkci šesti proměnných čtyři takové mapy. S dalším nárůstem počtu proměnných se Karnaughovy mapy stávají prakticky nepoužitelnými.
Slavný v literatuře Veitchovy karty Liší se pouze v jiném pořadí sad proměnných hodnot a mají stejné vlastnosti jako Karnaughovy mapy.
Komplex kostek
Nejednotnost grafických metod kdy velké číslo proměnné jsou kompenzovány různými analytickými metodami pro reprezentaci booleovských funkcí. Jednou z takových reprezentací je komplex kostek, používající terminologii vícerozměrného logického prostoru v kombinaci se speciálně vyvinutou symbolikou.
). 0-kostky odpovídající složkám jednoty jsou reprezentovány sadami proměnných hodnot, na kterých se funkce rovná jednotě. Pochopitelně v nahrávce
Rýže. 3.8 Komplex krychlí funkce tří proměnných ( A) a jeho symbolické znázornění ( b)
Tvoří se komplex kostek maximální pokrytí funkcí. Vyjma všech těch s-kostky, které jsou pokryty kostkami vyšší dimenze, získáme obaly odpovídající slepým tvarům. Takže pro uvažovaný příklad (obr. 3.8) máme slepé zakrytí
,
která odpovídá funkci 
. V tomto případě je toto pokrytí minimální.
Pro dvě booleovské funkce operace disjunkce odpovídá sjednocení jejich komplexů krychle a operace konjunkce odpovídá průniku jejich komplexů krychle. Negace funkce odpovídá doplňku komplexu krychlí, tj. a je určena všemi vrcholy, ve kterých funkce nabývá hodnoty 0. Existuje tedy korespondence jedna ku jedné (izomorfismus) mezi algebrou Booleovské funkce a booleovské množiny reprezentující komplexy krychlí.
Znázornění funkce ve formě komplexů krychlí je méně vizuální, ale jeho nejdůležitější výhodou je odstranění omezení počtu proměnných a usnadnění kódování informací při použití počítačů.
Minimalizace booleovských funkcí
Formulace problému. Minimalizace obvodu na booleovské bázi spočívá v nalezení minimální disjunktivní formy, která odpovídá minimálnímu pokrytí. Celkový počet dopisů zahrnutých v normální formě je vyjádřen náklady na krytí 
, kde je počet krychlí, které tvoří krytí dané funkce n proměnných. Minimální krytí se vyznačuje nejnižší hodnotou své ceny.
Obvykle se problém minimalizace řeší ve dvou krocích. Nejprve hledáme zmenšený obal, který zahrnuje všechny -kostky maximálního rozměru, ale neobsahuje jedinou krychli pokrytou žádnou krychlí tohoto obalu. Odpovídající disjunktivní normální forma se nazývá redukovaná a její minitermy se nazývají jednoduché implikanty. Pro danou funkci je snížené pokrytí jedinečné, ale může být nadbytečné vzhledem k tomu, že některé z kostek jsou pokryty kolekcemi jiných kostek.
Ve druhém kroku se provede přechod z redukovaných na slepé disjunktivní normální formy, ze kterých jsou vybrány minimální formy. Slepé formy se tvoří tak, že se z redukovaného pokrytí vyloučí všechny nadbytečné krychle, bez nichž zbývající množina krychlí stále tvoří krytí dané funkce, ale při dalším vyloučení kterékoli z krychlí již nepokrývá množinu všech vrcholy odpovídající jednotlivým hodnotám funkce, to znamená, že přestává být krytím.
Krychle zmenšeného pokrytí, která pokrývá vrcholy dané funkce, které nejsou pokryty žádnou jinou krychlí, nemůže být nadbytečná a bude vždy zahrnuta do minimálního pokrytí. Taková krychle, stejně jako její odpovídající implikant, se nazývá extremální (esenciální implikant) a vrcholy, které pokrývá, se nazývají zrušené vrcholy. Soubor extremálů tvoří jádro krytí, je zřejmé, že při přechodu z redukovaného krytí na minimální by měly být izolovány především všechny extremály. Pokud soubor extremálů netvoří krytinu, pak se doplňuje o krytí kostkami ze zmenšené krytiny.
Uvedené definice jsou znázorněny na Obr. 3.9, kde je snížené krytí (viz obr. 3.9a, ) a minimální krytí (obr. 3.9b) a (viz obr. 3.9, b) jsou vyjádřeny následovně.
Definice 1.Konjunktivní jednočlen (elementární konjunkce) proměnných je konjunkce těchto proměnných nebo jejich negací.
Například, je elementární konjunkce.
Definice 2.Disjunktivní monomiál (elementární disjunkce) od proměnných je disjunkce těchto proměnných nebo jejich negace.
Například, je elementární disjunkce.
Definice 3. Formule, která je ekvivalentní dané formuli výrokové algebry a je disjunkcí elementárních konjunktivních monočlenů, se nazývá disjunktivní normální forma(DNF) tohoto vzorce.
Například,– DNF.
Definice 4. Formule, která je ekvivalentní dané formuli výrokové algebry a je konjunkcí elementárních disjunktivních monočlenů, se nazývá konjunktivní normální forma(CNF) tohoto vzorce.
Například, – KNF.
Pro každou formuli výrokové algebry lze najít sadu disjunktivních a konjunktivních normálních forem.
Algoritmus pro konstrukci normálních forem
Pomocí ekvivalencí logické algebry nahraďte všechny základní operace ve vzorci: konjunkce, disjunkce, negace:
Zbavte se dvojitých negativů.
V případě potřeby aplikujte vlastnosti vzorců distributivity a absorpce na operace konjunkce a disjunkce.
2.6. Dokonalé disjunktivní a dokonalé konjunktivní normální formy
Jakákoli booleovská funkce může mít mnoho reprezentací ve formě DNF a CNF. Zvláštní místo mezi těmito reprezentacemi zaujímá perfektní DNF (SDNF) a perfektní CNF (SCNF).
Definice 1. Dokonalá disjunktivní normální forma(SDNF) je DNF, ve kterém každý konjunktivní monomial obsahuje každou proměnnou z množiny právě jednou, ať už samotnou nebo její negaci.
Strukturálně lze SDNF pro každý vzorec výrokové algebry redukovaný na DNF definovat takto:
Definice 2. Dokonalá disjunktivní normální forma(SDNF) vzorce výrokové algebry se nazývá jeho DNF, který má následující vlastnosti:
Definice 3. Dokonalá konjunktivní normální forma(SCNF) je CNF, ve kterém každý disjunktivní monomiál obsahuje každou proměnnou z množiny právě jednou a objevuje se buď sama, nebo její negace.
Strukturálně lze SCNF pro každý vzorec výrokové algebry redukovaný na CNF definovat následovně.
Definice 4. Dokonalá konjunktivní normální forma(SCNF) daného vzorce výrokové algebry se nazývá CNF, který splňuje následující vlastnosti.
Věta 1. Každá booleovská funkce proměnných, která není identicky nepravdivá, může být reprezentována v SDNF, a to jedinečným způsobem.
Metody hledání SDNF
1. způsob
2. způsob
vyberte řádky, kde vzorec nabývá hodnoty 1;
disjunkci spojek skládáme za podmínky, že pokud je proměnná zahrnuta do spojky s hodnotou 1, pak tuto proměnnou zapíšeme, pokud s hodnotou 0, pak její negaci. Dostáváme SDNF.
Věta 2. Každá booleovská funkce proměnných, která není identicky pravdivá, může být reprezentována v SCNF, a to jedinečným způsobem.
Metody hledání SCNF
1. způsob– pomocí ekvivalentních transformací:
2. způsob- pomocí pravdivostních tabulek:
vyberte řádky, kde vzorec nabývá hodnoty 0;
konjunkci disjunkcí skládáme za podmínky, že pokud je v disjunkci zahrnuta proměnná s hodnotou 0, pak tuto proměnnou zapíšeme, pokud s hodnotou 1, pak její negaci. Dostáváme SKNF.
Příklad 1 Sestavte funkce CNF.
Řešení
Pojďme eliminovat spojovací výraz "" pomocí zákonů transformace proměnných:
= /de Morganovy zákony a dvojitá negace/ =
/distribuční zákony/ =
Příklad 2 Dejte vzorec DNF.
Řešení
Vyjádřeme logické operace pomocí a:
= /klasifikujme negaci jako proměnné a redukujeme dvojité zápory/ =
= /zákon distributivity/ .
Příklad 3 Napište vzorec v DNF a SDNF.
Řešení
Pomocí zákonů logiky tento vzorec zredukujeme na formu obsahující pouze disjunkce elementárních spojek. Výsledný vzorec bude požadovaný DNF:
Abychom vytvořili SDNF, vytvořte pravdivostní tabulku pro tento vzorec:
Označíme ty řádky tabulky, ve kterých má vzorec (poslední sloupec) hodnotu 1. Pro každý takový řádek vypíšeme vzorec, který je pravdivý na množině proměnných tohoto řádku:
řádek 1: ;
řádek 3: ;
řádek 5: .
Disjunkce těchto tří vzorců bude mít hodnotu 1 pouze na množinách proměnných v řádcích 1, 3, 5, a proto bude požadovanou dokonalou disjunktivní normální formou (PDNF):
Příklad 4. Přeneste vzorec do SKNF dvěma způsoby:
a) použitím ekvivalentních transformací;
b) pomocí pravdivostní tabulky.
Řešení:
Transformujme druhou elementární disjunkci:
Vzorec vypadá takto:
b) sestavte pravdivostní tabulku pro tento vzorec:
Označíme ty řádky tabulky, ve kterých má vzorec (poslední sloupec) hodnotu 0. Pro každý takový řádek vypíšeme vzorec, který je pravdivý na množině proměnných tohoto řádku:
řádek 2: ;
řádek 6: .
Konjunkce těchto dvou vzorců bude mít hodnotu 0 pouze na množinách proměnných v řádcích 2 a 6, a proto bude požadovanou dokonalou konjunktivní normální formou (PCNF):
Otázky a úkoly k samostatnému řešení
1. Pomocí ekvivalentních transformací zredukujte vzorce na DNF:
2. Pomocí ekvivalentních transformací přeneste vzorce do CNF:
3. Pomocí druhého distributivního zákona převeďte DNF na CNF:
A) 
;
4. Převeďte dané DNF na SDNF:
5. Převeďte daný CNF na SCNF:
6. Pro dané logické vzorce sestrojte SDNF a SCNF dvěma způsoby: pomocí ekvivalentních transformací a pomocí pravdivostní tabulky.
b) 
;
Jednoduchá disjunkce(angl. včetně disjunkce) popř disjunkce(anglicky disjunct) je disjunkce jedné nebo více proměnných nebo jejich negací, přičemž každá proměnná se nevyskytuje více než jednou.
Jednoduchá disjunkce
- plný, pokud se každá proměnná (nebo její negace) objeví právě jednou;
- monotónní, pokud neobsahuje negace proměnných.
Konjunktivní normální forma, CNF(angl. conjunctive normal form, CNF) normální forma, ve které má booleovská funkce tvar konjunkce několika jednoduchých klauzí.
Příklad CNF:$f(x,y) = (x \lor y) \land (y \lor \neg ( z))$
SKNF
Dokonalá konjunktivní normální forma, SCNF(anglicky perfektní konjunktivní normální forma, PCNF) je CNF, který splňuje podmínky:
- neobsahuje shodné jednoduché disjunkce
- každá jednoduchá disjunkce je úplná
Příklad SKNF:$f(x,y,z) = (x \lor \neg ( y ) \lor z) \land (x\lor y \lor \neg ( z))$
Teorém: Pro jakoukoli booleovskou funkci $f(\vec ( x ))$, která se nerovná identitě, existuje SCNF, který ji definuje.
Důkaz: Protože inverze funkce $\neg ( f ) (\vec x)$ je rovna jedné na těch množinách, na kterých se $f(\vec x)$ rovná nule, pak SDNF pro $\neg ( f ) (\vec x)$ lze zapsat následovně:
$\neg ( f ) (\vec x) = \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) ), x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \ klín x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \ klín ... \ klín x_ ( n ) ^ ( \ sigma_ ( n ) )) $, kde $ \sigma_ (i) $ označuje přítomnost nebo nepřítomnost negace v $ x_ (i) $
Pojďme najít inverzi levé a pravé strany výrazu:
$ f(\vec x) = \neg (( \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) ), x^ ( \sigma_ ( 2 ) ) ), ... ,x^ ( \sigma_ ( n ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \ klín x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \ klín ... \ klín x_ ( n ) ^ ( \ sigma_ ( n ))))) $
Dvojitým aplikováním de Morganova pravidla na výraz získaný na pravé straně získáme: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ), \dots ,x ^ ( \ sigma_n )) = 0 ) $ $ (\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \dots \vee \neg ( x_n^ ( \sigma_n ) ) ) $
Poslední výraz je SKNF. Protože SCNF je získán z SDNF, který může být zkonstruován pro jakoukoli funkci, která není shodně nulová, je věta dokázána.
Algoritmus pro konstrukci SCNF pomocí pravdivostní tabulky
- V pravdivostní tabulce označíme ty množiny proměnných, pro které je hodnota funkce rovna $0$.
- Pro každou označenou množinu zapíšeme disjunkci všech proměnných podle následujícího pravidla: je-li hodnota některé proměnné $0$, pak do disjunkce zahrneme i samotnou proměnnou, jinak její negaci.
- Všechny výsledné disjunkce spojujeme operacemi konjunkce.
Příklad konstrukce SCNF pro medián
1). V pravdivostní tabulce označíme ty množiny proměnných, pro které je hodnota funkce rovna $0$.
| X | y | z | $ \langle x,y,z \rangle $ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
2). Pro každou označenou množinu zapíšeme konjunkci všech proměnných podle následujícího pravidla: je-li hodnota některé proměnné $0$, pak do disjunkce zahrneme i samotnou proměnnou, jinak její negaci.
| X | y | z | $ \langle x,y,z \rangle $ | |
| 0 | 0 | 0 | 0 | $(x \lor y \lor z)$ |
| 0 | 0 | 1 | 0 | $(x \lor y \lor \neg ( z ))$ |
| 0 | 1 | 0 | 0 | $(x \lor \neg ( y ) \lor z)$ |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | $(\neg ( x ) \lor y \lor z)$ |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
3). Všechny výsledné disjunkce spojujeme operacemi konjunkce.
$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg ( x ) \lor y \lor z) \land (x \lor \neg ( y) \lor z) \land (x \lor y \lor \neg ( z ))$
Příklady SKNF pro některé funkce
Peirceova šipka: $ x \downarrow y = (\neg ( x ) \lor ( y )) \land (( x ) \lor \neg ( y )) \land (\neg ( x ) \lor \neg ( y ) )$
Exkluzivní nebo: $ x \oplus y \oplus z = (\neg ( x ) \lor \neg ( y) \lor z) \land (\neg ( x ) \lor y \lor \neg ( z)) \land (x \lor \neg ( y ) \lor \neg ( z)) \land (x \lor y \lor z)$
Konjunktivní normální forma je vhodná pro automatické dokazování vět. Jakýkoli booleovský vzorec lze redukovat na CNF. K tomu můžete použít: zákon dvojí negace, de Morganův zákon, distributivita.
Encyklopedický YouTube
-
1 / 5
Vzorce v KNF:
¬ A ∧ (B ∨ C), (\displaystyle \neg A\wedge (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\klín (\neg B\vee C\vee \neg D)\klín ( D\vee\neg E),) A∧B. (\displaystyle A\wedge B.)Vzorce ne v KNF:
¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\wedge (B\vee (D\wedge E)).)Ale tyto 3 vzorce, které nejsou v CNF, jsou ekvivalentní následujícím vzorcům v CNF:
¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\wedge (B\vee D)\wedge (B\vee E).)Výstavba CNF
Algoritmus pro konstrukci CNF
1) Zbavte se všech logických operací obsažených ve vzorci a nahraďte je základními: konjunkce, disjunkce, negace. To lze provést pomocí ekvivalentních vzorců:
A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)2) Nahraďte znaménko negace vztahující se k celému výrazu znaménkem negace vztahujícím se k jednotlivým výrokům proměnných na základě vzorců:
¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)3) Zbavte se dvojitých negativů.
4) Aplikujte, je-li to nutné, vlastnosti vzorců distributivity a absorpce na operace konjunkce a disjunkce.
Příklad konstrukce CNF
Přenesme vzorec do CNF
F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).)Pojďme transformovat vzorec F (\displaystyle F) na vzorec, který neobsahuje → (\displaystyle \rightarrow ):
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\doprava Z)\vee \neg X)=(\neg X\vee Y)\klín (\neg (\neg \ zápor Y\vee Z)\neg \neg X).)Ve výsledném vzorci přeneseme negaci na proměnné a snížíme dvojité zápory:
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\klín \neg Z)\vee \neg X).)Například následující vzorec je napsán v 2-CNF:
(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\nebo B)\land (\neg B\lor C)\land (B\nebo \neg C).)
