Quine metoda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. února 2020; kontroly vyžadují 6 úprav .

Quineova metoda je způsob, jak reprezentovat funkci v DNF nebo CNF s minimálním počtem členů a minimální sadou proměnných. [1] [2] [3]
Převod funkcí lze rozdělit do dvou kroků:

v první fázi se provádí přechod z kanonické formy ( KDNF nebo KKNF ) do tzv. zkrácené formy ;
ve druhé fázi - přechod ze zkrácené formy na minimální formu .

První fáze (získání zkrácené podoby)

Představme si, že daná funkce je reprezentována v SDNF . Pro implementaci první fáze transformace prochází dvěma kroky: $F$

operace lepení ;
operace převzetí .

Operace lepení se redukuje na hledání dvojic výrazů odpovídajících tvaru nebo a jejich převod na následující výrazy: . Výsledky lepení nyní hrají roli doplňkových termínů. Je nutné najít všechny možné dvojice termínů (každý termín s každým). $w \cdot x$ $w \cdot \overline{x}$ $w \cdot x \lor w \cdot \overline{x} = w \cdot (x \lor \overline{x}) = w$ $w$

Poté se provede operace absorpce . Je založen na rovnosti (termín absorbuje výraz ). V důsledku této akce jsou z logického výrazu vymazány všechny členy absorbované jinými proměnnými, jejichž výsledky jsou získány v operaci lepení . Obě operace prvního stupně mohou být prováděny tak dlouho, dokud to lze provést. Použití těchto operací je uvedeno v tabulce: $w \lor w \cdot z = w \cdot (1 \lor z) = w$ $w$ $w\cdotz$

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	jeden	0
0	jeden	0	jeden
0	jeden	jeden	0
jeden	0	0	jeden
jeden	0	jeden	jeden
jeden	jeden	0	jeden
jeden	jeden	jeden	jeden

SDNF vypadá takto:

f(x_1, x_2, x_3) = \overline{x_1} \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2} \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2 } \cdot x_3 \lor x_1 \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot x_2 \cdot x_3

Výsledek operace lepení je nutný k transformaci funkce na druhém stupni (absorpce)

f(x_1, x_2, x_3) = \cancel{\overline{x_1} \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot \overline{x_2} \cdot \overline{x_3}} \ vee \cancel{x_1 \cdot \overline{x_2} \cdot x_3} \vee \cancel{x_1 \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot x_2 \cdot x_3} = x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2

Členy výsledku lepení jsou

x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2

Člen absorbuje ty členy původního výrazu, které obsahují , tedy první a čtvrtý. Tito členové jsou smazáni. Termín absorbuje druhý a třetí a termín absorbuje pátý termín původního výrazu. $x_2 \cdot \overline{x_3}$ $x_2 \cdot \overline{x_3}$ $x_1 \cdot \overline{x_2}$ $x_1\cdot x_3$

Opakováním obou operací vznikne následující výraz:

f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \vee \cancel{x_1 \cdot \overline{x_2}} \vee \cancel{x_1 \cdot \overline{x_3}} \vee \cancel{ x_1 \cdot x_3} \vee \cancel{x_1 \cdot x_2} \vee x_1

Zde, dvojice pojmů a jsou slepeny k sobě (slepení dvojice pojmů vede ke stejnému výsledku), výsledek slepení pohltí 2-, 3-, 4-, 5-tý výraz výrazu. Další lepicí a absorpční operace se ukazují jako nemožné, zkrácená forma vyjádření dané funkce (v tomto případě se shoduje s minimální formou) $x_1 \cdot \overline{x_2}$ $x_1\cdot x_2$ $x_1 \cdot \overline{x_3}$ $x_1\cdot x_3$ $x_{1}$

f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \lor x_1

Zkrácené členy (v našem případě to je a ) se nazývají jednoduché implikanty funkce. Ve výsledku jsme dostali nejjednodušší výraz ve srovnání s původní verzí - SDNF . Blokové schéma takového prvku je znázorněno na obrázku vpravo. $x_2 \cdot \overline{x_3}$ $x_{1}$

Druhá fáze (tabulková) (získání minimálního tvaru)

Stejně jako v první fázi může výsledná rovnost obsahovat členy, jejichž odstranění žádným způsobem neovlivní konečný výsledek. Další fází minimalizace je odstranění takových proměnných. Níže uvedená tabulka obsahuje pravdivostní hodnoty funkce. Podle ní se bude vybírat další SDNF .

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	jeden
0	0	0	jeden	jeden
0	0	jeden	0	jeden
0	0	jeden	jeden	0
0	jeden	0	0	0
0	jeden	0	jeden	0
0	jeden	jeden	0	jeden
0	jeden	jeden	jeden	0
jeden	0	0	0	0
jeden	0	0	jeden	0
jeden	0	jeden	0	0
jeden	0	jeden	jeden	0
jeden	jeden	0	0	0
jeden	jeden	0	jeden	0
jeden	jeden	jeden	0	jeden
jeden	jeden	jeden	jeden	jeden

SDNF zkompilovaný z této tabulky vypadá takto:

f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot \overline{x_2 } \cdot \overline{x_3} \cdot{x_4} \vee \overline{x_1} \cdot \overline{x_2} \cdot{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_2 \ cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot x_4

\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_3 \cdot \overline{x_4} \vee x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3

Termíny tohoto výrazu jsou jednoduchými implikanty výrazu. Přechod z redukované formy na minimum se provádí pomocí implikantní matice .

Implicitní matice

Členy SDNF dané funkce se vejdou do sloupců a do řádků - jednoduché implikanty, tedy členy zkráceného tvaru. Sloupce termínů PDNF jsou označeny , které jsou absorbovány jednotlivými primárními implikanty. V následující tabulce jednoduchý implikant absorbuje pojmy a (křížky jsou umístěny v prvním a druhém sloupci). ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$ $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4}$ $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4$

Jednoduchý implikant	$\overline{x_1} \cdot \overline{x_2} \cdot\overline{x_3} \cdot \overline{x_4}$	$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4$	$\overline{x_1} \cdot \overline{x_2} \cdot x_3 \cdot \overline{x_4}$	$\overline{x_1} \cdot x_2 \cdot x_3 \cdot \overline{x_4}$	$x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4}$	$x_1 \cdot x_2 \cdot x_3 \cdot x_4$
${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$	$\krát$	$\krát$
$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$	$\krát$		$\krát$
$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$			$\krát$	$\krát$
$x_2 \cdot x_3 \cdot \overline{x_4}$				$\krát$	$\krát$
$x_1 \cdot x_2 \cdot x_3$					$\krát$	$\krát$

Druhý implikant absorbuje první a třetí člen SDNF (označeno křížky) atd. Implikanty, které nepodléhají vyloučení, tvoří jádro . Takové implikanty jsou určeny výše uvedenou maticí. Pro každý z nich existuje alespoň jeden sloupec, který je pokryt pouze tímto implikantem.

V našem příkladu tvoří implikanty a (překrývají druhý a šestý sloupec) jádro. Z redukované formy nelze současně vyloučit všechny implikanty, které nejsou zahrnuty v jádru, protože vyloučení jednoho z implikantů může z druhého udělat nepotřebný člen. Pro získání minimálního formuláře stačí vybrat z implikantů nezařazených do jádra takový jejich minimální počet s minimálním počtem písmen v každém z těchto implikantů, který zajistí překrytí všech sloupců, na které se nevztahuje členy jádra. V uvažovaném příkladu je nutné pokrýt třetí a čtvrtý sloupec matice implikanty, které nejsou součástí jádra. Toho lze dosáhnout různými způsoby, ale protože je nutné zvolit minimální počet implikantů, je zřejmé, že implikant by měl být vybrán tak, aby tyto sloupce překrýval . ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$ $x_1 \cdot x_2 \cdot x_3$
$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$

Minimální disjunktivní normální forma (MDNF) dané funkce je:

f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee x_1 \cdot x_2 \cdot x_3 \vee \overline{x_1} \cdot x_3 \ cdot\overline{x_4}

(A)

Blokové schéma odpovídající tomuto výrazu je znázorněno na obrázku vlevo. Přechod z redukovaného schématu na MDNF byl proveden odstraněním nadbytečných termínů - implikant a . Ukažme si přípustnost takového vyloučení členů z logického výrazu. $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$ $x_2 \cdot x_3 \cdot \overline{x_4}$

Implikanty a stanou se rovny log. 1 pro následující sady hodnot argumentů: , , a , , . $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$ $x_2 \cdot x_3 \cdot \overline{x_4}$ $x_{1}=0$ $x_{2}=0$ $x_4 = 0$ $x_{2}=1$ $x_{3}=1$ $x_4 = 0$

Role těchto implikantů ve vyjádření zkráceného tvaru funkce je pouze přiřadit funkci na daných množinách hodnot argumentů hodnotu 1. U těchto množin je však funkce rovna 1 kvůli ostatním implikantům výrazu. Dosazením množiny hodnot uvedených výše do vzorce (a) skutečně získáme: $f(x_{1},x_{2},x_{3},x_{4})$

v , , $x_{1}=0$ $x_{2}=0$ $x_4 = 0$

$f(0, 0, x_3, 0) = 1 \cdot 1 \cdot \overline{x_3} \vee 0 \cdot 0 \cdot x_3 \vee 1 \cdot x_3 \cdot 1 = \overline{x_3} \vee x_3 = jeden$ ;

v , , $x_{2}=1$ $x_{3}=1$ $x_4 = 0$

$f(x_1, 1, 1, 0) = \overline{x_1} \cdot 0 \cdot 0 \vee x_1 \cdot 1 \cdot 1 \vee \overline{x_1} \cdot 1 \cdot 1 = x_1 \vee \overline {x_1} = 1$ ;

Použití metody k získání minimálního CNF

Pro získání minimální konjunktivní normální formy (MCNF) pomocí Quineovy metody jsou zavedena následující kritéria:

pro minimalizaci nebereme funkce SDNF , ale SKNF ;
dvojice pojmů ke slepení se změní na: nebo ; $w\vee x$ $w\vee\overline{x}$
Absorpční pravidlo vypadá takto:

$z \cdot (z \vee y) = z \vee z \cdot y = z \cdot (1 \vee y) = z$

Viz také

Poznámky

↑ Stručný popis Quineovy metody Archivováno 20. února 2009 na Wayback Machine www.ptca.narod.ru
↑ Přednáška: Minimalizace FAL Archivováno 14. dubna 2009 na Wayback Machine www.works.tarefer.ru
↑ Příklad minimalizace spínací funkce metodou Quine Archivováno 17. dubna 2010 na Wayback Machine matri-tri-ca.narod.ru