Quine módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. február 7-én felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A Quine - módszer egy olyan módszer, amely egy függvényt DNF -ben vagy CNF -ben reprezentál minimális számú taggal és minimális változókészlettel. [1] [2] [3]
A függvénykonverzió két lépésre osztható:

az első szakaszban a kanonikus formáról ( KDNF vagy KKNF ) az úgynevezett rövidített formára való áttérés történik ;
a második szakaszban - az átmenet a rövidített formáról a minimális formára .

Az első szakasz (rövidített forma beszerzése)

Képzeljük el, hogy az adott függvény az SDNF -ben van ábrázolva . Az első szakasz megvalósításához az átalakítás két lépésen megy keresztül: $f$

Ragasztási művelet ;
átvételi művelet .

A ragasztási művelet a vagy alaknak megfelelő kifejezéspárok megkeresésére és a következő kifejezésekké alakítására redukálódik: . A ragasztási eredmények most további kifejezések szerepét töltik be. Meg kell találni az összes lehetséges kifejezéspárt (minden kifejezés mindegyikével). $w \cdot x$ $w \cdot \overline{x}$ $w \cdot x \lor w \cdot \overline{x} = w \cdot (x \vagy \overline{x}) = w$ $w$

Ezután megtörténik az abszorpciós művelet . Az egyenlőségen alapul (a kifejezés elnyeli a kifejezést ). Ennek a műveletnek az eredményeként a logikai kifejezésből törlődik az összes olyan tag, amelyet más változók abszorbeáltak, és amelyek eredményeit a ragasztási műveletben kapjuk meg . Az első szakasz mindkét művelete mindaddig végrehajtható, amíg megtehető. Ezen műveletek alkalmazását a táblázat mutatja: $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	egy	0
0	egy	0	egy
0	egy	egy	0
egy	0	0	egy
egy	0	egy	egy
egy	egy	0	egy
egy	egy	egy	egy

Az SDNF így néz ki:

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} \vagy x_1 \cdot \overline {x_2 } \cdot x_3 \vagy x_1 \cdot x_2 \cdot \overline{x_3} \vagy x_1 \cdot x_2 \cdot x_3

A ragasztási művelet eredménye szükséges a függvény átalakításához a második szakaszban (abszorpció)

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

A ragasztási eredmény tagjai a

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

A tag elnyeli az eredeti kifejezés azon tagjait, amelyek tartalmazzák az elsőt és a negyediket. Ezek a tagok törlésre kerülnek. A kifejezés elnyeli az eredeti kifejezés második és harmadik tagját, a kifejezés pedig az ötödik tagot. $x_2 \cdot \overline{x_3}$ $x_2 \cdot \overline{x_3}$ $x_1 \cdot \overline{x_2}$ $x_1\cdot x_3$

Mindkét művelet megismétlése a következő kifejezést eredményezi:

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

Itt a és a kifejezéspár össze van ragasztva (egy kifejezéspár ragasztása ugyanarra az eredményre vezet), a ragasztás eredménye elnyeli a kifejezés 2-, 3-, 4-, 5-edik tagját. A további ragasztási és abszorpciós műveletek lehetetlennek bizonyulnak, az adott függvény kifejezésének rövidített formája (jelen esetben egybeesik a minimális formával) $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} \vagy x_1

A rövidített tagokat (esetünkben ez és ) a függvény egyszerű implikánsainak nevezzük . Ennek eredményeként a legegyszerűbb kifejezést kaptuk a kezdeti verzióhoz képest - SDNF . Egy ilyen elem blokkvázlata a jobb oldali ábrán látható. $x_2 \cdot \overline{x_3}$ $x_{1}$

A második szakasz (táblázatos) (a minimális forma megszerzése)

Az első szakaszhoz hasonlóan a kapott egyenlőség tartalmazhat olyan kifejezéseket, amelyek kiiktatása semmilyen módon nem befolyásolja a végeredményt. A minimalizálás következő szakasza az ilyen változók eltávolítása. Az alábbi táblázat a függvény igazságértékeit tartalmazza. Eszerint a következő SDNF kerül összegyűjtésre .

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

Az ebből a táblázatból összeállított SDNF így néz ki:

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

Ennek a kifejezésnek a feltételei a kifejezés egyszerű következményei . Az átmenet a redukált formáról a minimumra az implikáns mátrix segítségével történik .

Implikáns mátrix

Egy adott függvény SDNF -jének tagjai oszlopokba és sorokba illeszkednek - egyszerű implikánsok, azaz egy rövidített forma tagjai. A PDNF kifejezések oszlopai jelöléssel vannak ellátva , amelyeket az egyes elsődleges implikánsok abszorbeálnak. A következő táblázatban az egyszerű implikáns elnyeli a és kifejezéseket (az első és a második oszlopban keresztek vannak). ${\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$

Egyszerű implicit	$\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}}}$	$\szor$	$\szor$
$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$	$\szor$		$\szor$
$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$			$\szor$	$\szor$
$x_2 \cdot x_3 \cdot \overline{x_4}$				$\szor$	$\szor$
$x_1 \cdot x_2 \cdot x_3$					$\szor$	$\szor$

A második implikáns elnyeli az SDNF első és harmadik tagját ( keresztekkel jelölve), stb. A magot azok az implikánsok alkotják, amelyekre nem vonatkozik a kizárás . Az ilyen implikánsokat a fenti mátrix határozza meg. Mindegyikhez van legalább egy oszlop, amelyet csak ez az implikant fed le.

Példánkban az implikánsok és (amelyek átfedik a második és hatodik oszlopot) alkotják a kernelt. Lehetetlen egyidejűleg kizárni a redukált formából mindazokat az implikánsokat, amelyek nem szerepelnek a magban, mivel az egyik implikáns kizárása a másikat szükségtelen taggá változtathatja. A minimális forma megszerzéséhez elegendő a kernelben nem szereplő implikánsok közül olyan minimális számot választani, amelyek mindegyikében minimális számú betű szerepel, amely biztosítja az összes olyan oszlop átfedését, amelyre nem vonatkozik a rendszermag. a kernel tagjai. A vizsgált példában a mátrix harmadik és negyedik oszlopát a kernelben nem szereplő implikánsokkal kell lefedni. Ez többféleképpen is elérhető, de mivel az implikánsok minimális számát kell kiválasztani, nyilvánvaló, hogy az implikantot úgy kell kiválasztani, hogy átfedje ezeket az oszlopokat . ${\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}$

Egy adott függvény minimális diszjunktív normálformája (MDNF) a következő:

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)

A kifejezésnek megfelelő blokkdiagram a bal oldali ábrán látható. A redukált sémáról az MDNF-re való áttérés az extra kifejezések - az implikáns és a . Mutassuk meg, hogy elfogadható-e a tagok ilyen kizárása a logikai kifejezésből. $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$ $x_2 \cdot x_3 \cdot \overline{x_4}$

Az implikánsok és egyenlővé válnak a loggal . 1 -et a következő argumentumérték-készletekhez: , , és , , . $\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$

Ezeknek az implikánsoknak a szerepe a függvény rövidített alakjának kifejezésében csak annyi, hogy az adott argumentumérték-halmazokon a függvényhez 1 értéket rendeljenek, de ezeknél a halmazoknál a függvény a többi implikáns miatt 1-gyel egyenlő. a kifejezésről. Valójában a fent jelzett értékkészletet az (a) képletbe behelyettesítve kapjuk: $f(x_{1},x_{2},x_{3},x_{4})$

itt: , , $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 = egy$ ;

itt: , , $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$ ;

A módszer használata a minimális CNF eléréséhez

A minimális konjunktív normál forma (MCNF) Quine-módszerrel történő megszerzéséhez a következő kritériumokat vezetjük be:

a minimalizáláshoz nem SDNF , hanem SKNF függvényeket veszünk;
a ragasztandó kifejezéspárok a következőkre módosulnak: vagy ; $w\vee x$ $w\vee\overline{x}$
Az abszorpciós szabály így néz ki:

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

Lásd még

Jegyzetek

↑ A Quine-módszer rövid leírása Archiválva : 2009. február 20. a Wayback Machine webhelyen www.ptca.narod.ru
↑ Előadás: FAL minimalizálás Archiválva : 2009. április 14. a Wayback Machine webhelyen www.works.tarefer.ru
↑ Példa a kapcsolási funkció minimalizálására a Quine-módszerrel Archiválva : 2010. április 17., a Wayback Machine matri-tri-ca.narod.ru

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

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

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

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

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

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