Konjunktivní normální forma logické funkce. Konjunktivní formy reprezentace logických funkcí

Konjunktivní normální forma je vhodná pro automatické dokazování věty. Jakýkoli booleovský vzorec lze převést na CNF. K tomu můžete použít: zákon dvojí negace, de Morganův zákon, distributivita.

Collegiate YouTube

1 / 5

Vzorce v KNF:

¬ A ∧ (B ∨ C), (\ styl zobrazení \ neg A \ klín (B \ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\ styl zobrazení (A \ vee B) \ klín (\ neg B \ vee C \ vee \ neg D) \ klín ( D \ vee \ neg E),) A ∧ B. (\ styl zobrazení A \ klín B.)

Vzorce ne v KNF:

¬ (B ∨ C), (\ styl zobrazení \ neg (B \ vee C),) (A ∧ B) ∨ C, (\ styl zobrazení (A \ klín B) \ vee C,) A ∧ (B ∨ (D ∧ E)). (\ styl zobrazení A \ klín (B \ vee (D \ klín E)).)

Ale tyto 3 vzorce, které nejsou v CNF, jsou ekvivalentní následujícím vzorcům v CNF:

¬ B ∧ ¬ C, (\ styl zobrazení \ neg B \ klín \ neg C,) (A ∨ C) ∧ (B ∨ C), (\ styl zobrazení (A \ vee C) \ klín (B \ vee C),) A ∧ (B ∨ D) ∧ (B ∨ E). (\ styl zobrazení A \ klín (B \ vee D) \ klín (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 těmi hlavními: konjunkce, disjunkce, negace. To lze provést pomocí ekvivalentních vzorců:

A → B = ¬ A ∨ B, (\ styl zobrazení A \ šipka vpravo B = \ neg A \ vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ styl zobrazení A \ šipka doleva doprava B = (\ neg A \ vee B) \ klín (A \ vee \ neg B).)

2) Nahraďte znaménko negace odkazující na celý výraz zápornými znaménky odkazujícími na jednotlivé příkazy proměnných na základě vzorců:

¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ styl zobrazení \ neg (A \ vee B) = \ neg A \ klín \ neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B. (\ displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)

3) Zbavte se znaků dvojité negace.

4) V případě potřeby aplikujte na operace konjunkce a disjunkce vlastnosti distributivity a absorpční vzorec.

Příklad budování CNF

Přenesme do CNF vzorec

F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ styl zobrazení F = (X \ šipka vpravo Y) \ klín ((\ neg Y \ šipka vpravo Z) \ šipka vpravo \ neg X).)

Pojďme transformovat vzorec F (\ styl zobrazení F) na vzorec, který neobsahuje → (\ styl zobrazení \ šipka vpravo):

F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ klín (\ neg (\ neg Y \ šipka vpravo Z) \ vee \ neg X) = (\ neg X \ vee Y) \ klín (\ neg (\ neg \ neg Y \ vee Z) \ vee \ zápor X).)

Ve výsledném vzorci převedeme negaci na proměnné a snížíme dvojité zápory:

F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ klín ((\ 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 \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)

Jednoduchý spojení volala spojení jeden nebo několik proměnné, na tento každý variabilní schází ne více jeden časy (nebo sám, nebo její negace).

Jedná se například o jednoduchou spojku,

Disjunktivní normální formulář(DNF) volala disjunkce jednoduchý spojky.

Například výraz je DNF.

Perfektní disjunktivní normální formulář(SDNF) volala tak disjunktivní normální formulář, na který proti každý spojení jsou zahrnuty Všechno proměnné daný seznam (nebo oni sami, nebo jejich popření), navíc proti jeden a objem stejnýdobře.

Například výraz je DNF, ale ne SDNF. Výraz je SDNF.

Podobné definice (s nahrazením spojky disjunkcí a naopak) platí pro CNF a SKNF. Zde jsou přesné formulace.

Jednoduchý disjunkce volala disjunkce jeden nebo několik proměnné, na tento každý variabilní vstoupí ne více jeden časy (nebo sám, nebo její negace) Například výraz je jednoduchá disjunkce,

Konjunktiv normální formulář(CNF) volala spojení jednoduchý disjunkce(například výraz je CNF).

Dokonalá konjunktivní normální forma (SCNF) je CNF, ve které každá jednoduchá disjunkce obsahuje všechny proměnné daného seznamu (buď samotné nebo jejich negace), a to ve stejném pořadí.

Například výraz je SKNF.

Zde jsou algoritmy pro přechody z jedné formy do druhé. Ve specifických případech (s určitým kreativním přístupem) je samozřejmě použití algoritmů pracnější než jednoduché transformace pomocí specifického typu této formy:

a) přechod z DNF na CNF

Algoritmus pro tento přechod je následující: dáme dvě negace nad DNF a pomocí de Morganových pravidel (aniž bychom se dotkli horní negace) přivedeme negaci DNF zpět do DNF. V tomto případě musíte otevřít závorky pomocí absorpčního pravidla (nebo Blakeova pravidla). Negace (horní) získaného DNF (opět podle de Morganova pravidla) nám okamžitě dává CNF:

Všimněte si, že CNF lze také získat z počátečního výrazu, pokud vyjmeme na vnější držáky;

b) přechod z CNF na DNF

Tento přechod se provádí jednoduchým otevřením závorek (v tomto případě je opět použito absorpční pravidlo)

Tak jsme dostali DNF.

Reverzní přechod (od SDNF k DNF) je spojen s problémem minimalizace DNF. O tom bude podrobněji pojednáno v kap. 5, zde si ukážeme, jak zjednodušit DNF (nebo SDNF) podle Blakeova pravidla. Toto DNF se nazývá zkrácený DNF;

c) zkratka DNF (nebo SDNF) podle pravidlo Blake

Aplikace tohoto pravidla má dvě části:

Pokud mezi disjunktními pojmy v DNF existují pojmy , pak k celé disjunkci přidáme člen NA 1 NA 2. Tuto operaci provedeme několikrát (může být sekvenční, může být současně) pro všechny možné dvojice termínů a poté aplikujeme obvyklou absorpci;

Pokud byl přidaný termín již obsažen v DNF, lze jej zcela vyřadit, např.

nebo

Zkrácené DNF samozřejmě není jednoznačně definováno, ale všechny obsahují stejný počet písmen (např. existuje DNF , po aplikaci Blakeova pravidla na něj můžete přijít k DNF ekvivalentnímu tomuto):

c) přechod z DNF na SDNF

Pokud některá jednoduchá spojka postrádá proměnnou, např. z, vložte do něj výraz a poté rozbalte závorky (v tomto případě nepíšeme opakované disjunktní členy). Například:

d) přechod z CNF na SKNF

Tento přechod se provádí podobným způsobem jako předchozí: pokud jednoduchá disjunkce postrádá nějakou proměnnou (např. z, pak k němu přidáme výraz (tím se nemění samotná disjunkce), načež rozbalíme závorky pomocí distribučního zákona:

SKNF se tedy získává z CNF.

Všimněte si, že minimální nebo zkrácený CNF se obvykle získává z odpovídajícího DNF.

Jednoduchá disjunkce(včetně disjunkce) popř disjunktní(anglicky disjunct) je disjunkce jedné nebo více proměnných nebo jejich negací a každá proměnná se vyskytuje maximálně jednou.

Jednoduchá disjunkce

kompletní pokud se v něm každá proměnná (nebo její negace) objeví právě jednou;
monotónní pokud neobsahuje proměnné zápory.

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) \ země (y \ lor \ neg (z)) $

SKNF

Dokonalá konjunktivní normální forma, SKNF(dokonalá konjunktivní normální forma, PCNF) je CNF, který splňuje následující podmínky:

nemá stejné jednoduché disjunkce
každá jednoduchá disjunkce je úplná

Příklad SKNF:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ země (x \ lor y \ lor \ neg (z)) $

Teorém: Pro jakékoli booleovská funkce$ f (\ vec (x)) $, nerovná se identitě, existuje SKNF, který ji definuje.

Důkaz: Protože inverzní funkce $ \ neg (f) (\ vec x) $ je rovna jedné na těch n-ticí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 \ limity_ (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 pro $ x_ (i) $

Pojďme najít inverzi levé a pravé strany výrazu:

$ f (\ vec x) = \ neg ((\ bigvee \ limity_ (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ě dostaneme: $ f (\ vec x) = \ bigwedge \limits_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ tečky, x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ tečky \ vee \ neg (x_n ^ (\ sigma_n)) ) $

Poslední výraz je SKNF. Protože SKNF je získán z SDNF, který lze sestrojit pro jakoukoli funkci, která není shodně nulová, je věta dokázána.

Algoritmus pro konstrukci SKNF podle pravdivostní tabulky

V pravdivostní tabulce označíme ty množiny proměnných, na kterých 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 vzniklé disjunkce spojujeme operacemi konjunkce.

Příklad konstrukce SKNF pro medián

1). V pravdivostní tabulce označíme ty množiny proměnných, na kterých je hodnota funkce rovna $ 0 $.

X	y	z	$ \ langle x, y, z \ langle $
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 \ langle $
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 vzniklé disjunkce spojujeme operacemi konjunkce.

$ \ langle x, y, z \ range = (x \ lor y \ lor z) \ země (\ neg (x) \ lor y \ lor z) \ země (x \ lor \ neg (y) \ lor z) \ země (x \ lor y \ lor \ neg (z)) $

Příklady SKNF pro některé funkce

Pierceův šíp: $ x \ šipka dolů y = (\ neg (x) \ lor (y)) \ země ((x) \ lor \ neg (y)) \ země (\ neg (x) \ lor \ neg (y) ) $

Exkluzivní nebo: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ země (\ neg (x) \ lor y \ lor \ neg (z)) \ země (x \ lor \ neg (y) \ lor \ neg (z)) \ země (x \ lor y \ lor z) $

Definice 1.Konjunktivní jednočlen (elementární konjunkce) z proměnných se nazývá konjunkce těchto proměnných nebo jejich negace.

Například, Je elementární konjunkce.

Definice 2.Disjunktivní monomiál (elementární disjunkce) z proměnných se nazývá disjunkce těchto proměnných nebo jejich negace.

Například, Je elementární disjunkce.

Definice 3. Formule 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 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, - CNF.

Pro každý vzorec 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í algebry logiky nahraďte všechny operace ve vzorci základními: konjunkce, disjunkce, negace:

Zbavte se znaků dvojité negace.

V případě potřeby použijte na operace konjunkce a disjunkce vlastnosti distributivity a absorpční vzorec.

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 (SKNF).

Definice 1. Dokonalá disjunktivní normální forma(SDNF) je DNF, ve kterém se v každém konjunktivním monomiálu každá proměnná z množiny vyskytuje právě jednou a objevuje se buď sama, nebo její negace.

Konstruktivně 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(SKNF) je CNF, ve kterém se v každém disjunktivním monomiálu každá proměnná z množiny vyskytuje právě jednou a objevuje se buď sama, nebo její negace.

Strukturálně lze SKNF pro každý vzorec výrokové algebry redukované na CNF definovat následovně.

Definice 4. Dokonalá konjunktivní normální forma(SKNF) daného vzorce výrokové algebry se nazývá jeho CNF, který splňuje následující vlastnosti.

Věta 1. Každá booleovská funkce proměnných, která není shodně nepravdivá, může být reprezentována v SDNF a navíc jedinečným způsobem.

Způsoby, jak najít SDNF

1. způsob

2. způsob

vyberte řádky, kde vzorec nabývá hodnoty 1;

skládáme disjunkci spojek za předpokladu, že pokud je proměnná zahrnuta do spojky s hodnotou 1, pak tuto proměnnou zapíšeme, pokud s hodnotou 0, tak 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 SKNF a navíc jedinečným způsobem.

Způsoby, jak najít SKNF

1. způsob- pomocí ekvivalentních transformací:

2. způsob- pomocí pravdivostních tabulek:

vyberte řádky, kde vzorec nabývá hodnoty 0;

skládáme konjunkci disjunkcí za předpokladu, že pokud je proměnná zahrnuta do disjunkce s hodnotou 0, pak tuto proměnnou zapíšeme, pokud s hodnotou 1, tak její negaci. Dostáváme SKNF.

Příklad 1 Vykreslete funkce CNF.

Řešení

Vylučme svazek "" pomocí zákonů transformace proměnných:

= / de Morganovy a zákony dvojí negace / =

/ distributivní zákony / =

Příklad 2 Přineste vzorec do DNF.

Řešení

Vyjádřeme logické operace pomocí a:

= / odkazujeme negaci na proměnné a redukujeme dvojité zápory / =

= / zákon rozdělování /.

Příklad 3 Zapište vzorec v DNF a SDNF.

Řešení

Pomocí zákonů logiky dovedeme tento vzorec do tvaru obsahujícího pouze disjunkce elementárních spojek. Výsledný vzorec bude požadovaný DNF:

Abychom vytvořili SDNF, sestavíme pravdivostní tabulku pro tento vzorec:

Označíme ty řádky tabulky, ve kterých vzorec (poslední sloupec) nabývá hodnoty 1. Pro každý takový řádek vypíšeme vzorec, který platí na množině proměnných daného řá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 (SDNF):

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í:

Transformujeme druhou elementární disjunkci:

Vzorec je:

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ý platí na množině proměnných daného řádku:

řádek 2:;

řádek 6:.

Konjunkce těchto dvou vzorců nabude hodnoty 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 (SCNF):

Otázky a úkoly k samostatnému řešení

1.Pomocí ekvivalentních transformací přeneste vzorce do DNF:

2. Pomocí ekvivalentních transformací přeneste vzorce do CNF:

3. Použijte druhý distribuční zákon k převodu DNF na CNF:

A) ;

4. Převeďte dané DNF na SDNF:

5. Převeďte daný CNF na SKNF:

6. Pro dané logické vzorce sestrojte SDNF a SKNF dvěma způsoby: pomocí ekvivalentních transformací a pomocí pravdivostní tabulky.

b) ;

Disjunktivní a konjunktivní normální formy výrokové algebry. Pro každou funkci logiky výroků můžete vytvořit 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í věty (klauzule) 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 algebry výroků lze najít sadu 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 těsnými negacemi, tedy na vzorec, ve kterém se negace nenacházejí výše než nad proměnnými – pro uplatnění de Morganových zákonů.

3. Rozbalte závorky - použijte zákony rozdělování.

4. Vezměte si opakující se termíny jednou - zákon idempotence.

5. Aplikujte zákony absorpce a semiabsorpce.

Příklad 6. Najděte vzorce DNF:.

Platí Booleova algebra princip duality... Je to následovně.

Funkce je volána dvojí do funkce if. Tito. k nalezení funkce, která je duální k dané, je nutné sestrojit negaci funkce z negací argumentů.

Příklad 7. Najděte duální funkci.

Mezi elementárními funkcemi algebry logiky je 1 duální k 0 a naopak, x je duální k x, duální, duální a naopak.

Pokud ve vzorci F 1 představujícím funkci jsou nahrazeny všechny spojky

na disjunkci, disjunkci na konjunkci, 1 na 0, 0 na 1, pak dostaneme formuli F * reprezentující funkci * duál.

Konjunktivní normální forma (CNF) je duální koncept pro DNF, takže je snadné jej zkonstruovat podle 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 SKNF.

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.

Libovolné DNF lze redukovat na SDNF rozdělením konjunkcí, které neobsahují všechny proměnné, tzn. sčítání pro chybějící proměnnou x i se násobí pomocí distribučního zákona

Příklad 9. Najděte SDNF pro příklad DNF 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 SKNF přidáním konjunkce, která neobsahuje žádnou proměnnou X i konjunkci, a použitím distributivního zákona

Příklad 10. Přineste CNF do SKNF:

K sestavení SKNF můžete použít schéma

Příklad 11. Najděte SKNF pro vzorec v příkladu 6.

Každá funkce má SDNF a navíc je jedinečná. Každá funkce má SKNF a navíc jedinou.

Protože SDNF a SKNF jsou definovány vzorci jednoznačně, lze je sestavit podle 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. Je-li 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 jsou dokonalá konjunkce (jejich počet se rovná počtu jedniček v tabulce) spojena znaménky disjunkce.

Pro sestrojení SKNF podle pravdivostní tabulky je nutné v ní vybrat přímky, kde F = 0, a zapsat dokonalé elementární disjunkce a ty pak 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, pokud je jedna - pak s negací.

Příklad 12. Najděte SDNF a SKNF pomocí pravdivostní tabulky pro vzorec z příkladu 6.

Tabulka 14 ukazuje pouze konečnou hodnotu F = 10101101. Měli byste se sami přesvědčit o platnosti tohoto tvrzení vytvořením rozšířené pravdivostní tabulky.

Tabulka 14

X	y	z