Quine metod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 februari 2020; kontroller kräver 6 redigeringar .

Quines metod är ett sätt att representera en funktion i DNF eller CNF med ett minimum antal medlemmar och en minsta uppsättning variabler. [1] [2] [3]
Funktionskonvertering kan delas in i två steg:

i det första skedet genomförs övergången från den kanoniska formen ( KDNF eller KKNF ) till den så kallade förkortade formen ;
i det andra steget - övergången från den förkortade formen till minimiformen .

Det första steget (att erhålla en förkortad form)

Låt oss föreställa oss att den givna funktionen är representerad i SDNF . För att implementera det första steget går transformationen igenom två steg: $f$

Limningsoperation ;
övertagande operation .

Limningsoperationen reduceras till att hitta termpar som motsvarar formen eller och omvandla dem till följande uttryck: . Limningsresultaten spelar nu rollen som ytterligare termer. Det är nödvändigt att hitta alla möjliga termpar (varje term med varje). $w \cdot x$ $w \cdot \overline{x}$ $w \cdot x \lor w \cdot \overline{x} = w \cdot (x \lor \overline{x}) = w$ $w$

Därefter utförs absorptionsoperationen . Den bygger på jämlikhet (termen absorberar uttrycket ). Som ett resultat av denna åtgärd raderas alla medlemmar som absorberas av andra variabler, vars resultat erhålls i limningsoperationen , från det logiska uttrycket . Båda operationerna i det första steget kan utföras så länge det kan göras. Tillämpningen av dessa operationer visas i tabellen: $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	ett	0
0	ett	0	ett
0	ett	ett	0
ett	0	0	ett
ett	0	ett	ett
ett	ett	0	ett
ett	ett	ett	ett

SDNF ser ut så här:

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

Resultatet av limningsoperationen behövs för att transformera funktionen i det andra steget (absorption)

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

Medlemmarna i limningsresultatet är

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

Medlemmen absorberar de medlemmar av det ursprungliga uttrycket som innehåller , det vill säga det första och det fjärde. Dessa medlemmar raderas. Termen absorberar den andra och den tredje, och termen absorberar den femte termen i det ursprungliga uttrycket. $x_2 \cdot \overline{x_3}$ $x_2 \cdot \overline{x_3}$ $x_1 \cdot \overline{x_2}$ $x_1\cdot x_3$

Upprepa båda operationerna resulterar i följande uttryck:

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

Här, ett par termer och limmas ihop (limmar ett par termer och leder till samma resultat), absorberar resultatet av limning de 2-, 3-, 4-, 5:e termerna i uttrycket. Ytterligare limnings- och absorptionsoperationer visar sig vara omöjliga, en förkortad form av uttrycket för den givna funktionen (i det här fallet sammanfaller det med minimiformen) $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

Förkortade termer (i vårt fall är detta och ) kallas enkla implikanter av funktionen. Som ett resultat fick vi det enklaste uttrycket jämfört med den ursprungliga versionen - SDNF . Blockschemat för ett sådant element visas i bilden till höger. $x_2 \cdot \overline{x_3}$ $x_{1}$

Det andra steget (tabell) (att erhålla minimiformen)

Liksom i det första steget kan den resulterande jämlikheten innehålla termer vars eliminering inte på något sätt kommer att påverka det slutliga resultatet. Nästa steg av minimering är borttagandet av sådana variabler. Tabellen nedan innehåller sanningsvärdena för funktionen. Enligt den kommer nästa SDNF att samlas in .

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

SDNF som sammanställts från den här tabellen ser ut så här:

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

Termerna för detta uttryck är enkla implikationer av uttrycket. Övergången från den reducerade formen till den minimala utförs med hjälp av implikantmatrisen .

Implikant matris

Medlemmar av SDNF för en given funktion passar in i kolumner och i rader - enkla implikanter, det vill säga medlemmar av en förkortad form. Kolumner med PDNF- termer är markerade , som absorberas av individuella primära implikanter. I följande tabell absorberar den enkla implikanten termerna och (kryss placeras i den första och andra kolumnen). ${\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$

Enkel 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}}}$	$\ gånger$	$\ gånger$
$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$	$\ gånger$		$\ gånger$
$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$			$\ gånger$	$\ gånger$
$x_2 \cdot x_3 \cdot \overline{x_4}$				$\ gånger$	$\ gånger$
$x_1 \cdot x_2 \cdot x_3$					$\ gånger$	$\ gånger$

Den andra implikanten absorberar de första och tredje medlemmarna av SDNF (anges med kryss), etc. De implikanter som inte är föremål för uteslutning utgör kärnan . Sådana implikanter bestäms av ovanstående matris. För var och en av dem finns det minst en kolumn som endast täcks av denna implikant.

I vårt exempel bildar implikanterna och (de överlappar den andra och sjätte kolumnen) kärnan. Det är omöjligt att samtidigt utesluta från den reducerade formen alla implikanter som inte ingår i kärnan, eftersom uteslutningen av en av implikanterna kan göra den andra till en onödig medlem. För att få minimiformuläret räcker det att välja bland implikanterna som inte ingår i kärnan, ett sådant minsta antal av dem med ett minsta antal bokstäver i var och en av dessa implikanter, vilket säkerställer överlappning av alla kolumner som inte täcks av medlemmar av kärnan. I exemplet under övervägande är det nödvändigt att täcka den tredje och fjärde kolumnen i matrisen med implikanter som inte ingår i kärnan. Detta kan uppnås på olika sätt, men eftersom det är nödvändigt att välja minsta antal implikanter är det uppenbart att implikanten bör väljas för att överlappa dessa kolumner . ${\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}$

Den minsta disjunktiva normalformen (MDNF) för en given funktion är:

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\överlinje{x_4}

(a)

Blockdiagrammet som motsvarar detta uttryck visas i figuren till vänster. Övergången från det reducerade systemet till MDNF genomfördes genom att eliminera de extra villkoren - den implicerande och . Låt oss visa tillåtligheten av en sådan uteslutning av medlemmar från ett logiskt uttryck. $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$ $x_2 \cdot x_3 \cdot \overline{x_4}$

Implikanterna och blir lika med logga. 1 för följande uppsättningar av argumentvärden: , , och , , . $\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$

Rollen för dessa implikanter i uttrycket av den förkortade formen av funktionen är endast att tilldela funktionen värdet 1 på de givna uppsättningarna av argumentvärden. Men med dessa uppsättningar är funktionen lika med 1 på grund av de andra implikanterna av uttrycket. Genom att ersätta uppsättningen av värden som anges ovan med formel (a) får vi: $f(x_{1},x_{2},x_{3},x_{4})$

vid , , $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 = ett$ ;

vid , , $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$ ;

Använda metoden för att få minsta CNF

För att erhålla den minimala konjunktiva normala formen (MCNF) med hjälp av Quines metod, introduceras följande kriterier:

för minimering tar vi inte SDNF , utan SKNF- funktioner;
termpar som ska limmas ändras till: eller ; $w\vee x$ $w\vee\överlinje{x}$
Absorptionsregeln ser ut så här:

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

Se även

Anteckningar

↑ Kort beskrivning av Quine-metoden Arkiverad 20 februari 2009 på Wayback Machine www.ptca.narod.ru
↑ Föreläsning: FAL-minimering Arkiverad 14 april 2009 på Wayback Machine www.works.tarefer.ru
↑ Ett exempel på minimering av en växlingsfunktion med Quine-metoden Arkiverad 17 april 2010 på 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	ett	0
0	ett	0	ett
0	ett	ett	0
ett	0	0	ett
ett	0	ett	ett
ett	ett	0	ett
ett	ett	ett	ett

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

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

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

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

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