Quine menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7.2.2020 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Quinen menetelmä on tapa esittää funktio DNF :ssä tai CNF :ssä vähimmäismäärällä jäseniä ja vähimmäismäärällä muuttujia. [1] [2] [3]
Toimintojen muuntaminen voidaan jakaa kahteen vaiheeseen:

ensimmäisessä vaiheessa suoritetaan siirtyminen kanonisesta muodosta ( KDNF tai KKNF ) niin kutsuttuun lyhennettyyn muotoon ;
toisessa vaiheessa - siirtyminen lyhennetystä muodosta vähimmäismuotoon .

Ensimmäinen vaihe (lyhennetyn muodon hankkiminen)

Kuvitellaan, että annettu funktio on edustettuna SDNF :ssä . Ensimmäisen vaiheen toteuttamiseksi muunnos käy läpi kaksi vaihetta: $f$

Liimaustoiminta ;
haltuunottooperaatio .

Liimaustoiminto rajoittuu muotoa tai vastaavien termiparien etsimiseen ja niiden muuntamiseen seuraaviksi lausekkeiksi: . Liimaustulokset ovat nyt lisäehtojen roolissa. On tarpeen löytää kaikki mahdolliset termiparit (jokainen termi jokaisen kanssa). $w \cdot x$ $w \cdot \overline{x}$ $w \cdot x \lor w \cdot \overline{x} = w \cdot (x \tai \overline{x}) = w$ $w$

Sitten suoritetaan absorptiotoiminto . Se perustuu tasa -arvoon (termi imee ilmaisun ). Tämän toimenpiteen seurauksena kaikki muiden muuttujien absorboimat jäsenet, joiden tulokset saadaan liimausoperaatiossa , poistetaan loogisesta lausekkeesta . Ensimmäisen vaiheen molemmat toiminnot voidaan suorittaa niin kauan kuin ne voidaan tehdä. Näiden operaatioiden soveltaminen on esitetty taulukossa: $w \lor w \cdot z = w \cdot (1 \tai z) = w$ $w$ $w\cdotz$

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

SDNF näyttää tältä:

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

Liimausoperaation tulos tarvitaan funktion muuntamiseen toisessa vaiheessa (absorptio)

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

Liimaustuloksen jäsenet ovat

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

Jäsen imee ne alkuperäisen lausekkeen jäsenet, jotka sisältävät , eli ensimmäisen ja neljännen. Nämä jäsenet on poistettu. Termi absorboi alkuperäisen lausekkeen toisen ja kolmannen termin, ja termi absorboi viidennen termin. $x_2 \cdot \overline{x_3}$ $x_2 \cdot \overline{x_3}$ $x_1 \cdot \overline{x_2}$ $x_1\cdot x_3$

Molempien toimintojen toistaminen tuottaa seuraavan lausekkeen:

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

Tässä termipari ja liimataan yhteen (termiparin liimaaminen johtaa samaan tulokseen), liimauksen tulos absorboi lausekkeen 2-, 3-, 4-, 5-termit. Muut liimaus- ja absorptiotoimenpiteet osoittautuvat mahdottomaksi, lyhennetty muoto tietyn funktion ilmaisusta (tässä tapauksessa se on yhtäpitävä minimimuodon kanssa) $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} \tai x_1

Lyhennettyjä termejä (meissämme tämä on ja ) kutsutaan funktion yksinkertaisiksi implikantteiksi . Tuloksena saimme yksinkertaisimman lausekkeen verrattuna alkuperäiseen versioon - SDNF . Tällaisen elementin lohkokaavio on esitetty oikealla olevassa kuvassa. $x_2 \cdot \overline{x_3}$ $x_{1}$

Toinen vaihe (taulukkomuotoinen) (minimimuodon saaminen)

Kuten ensimmäisessä vaiheessa, tuloksena oleva yhtäläisyys voi sisältää termejä, joiden poistaminen ei millään tavalla vaikuta lopputulokseen. Seuraava minimoinnin vaihe on tällaisten muuttujien poistaminen. Alla oleva taulukko sisältää funktion totuusarvot. Sen mukaanseuraava SDNF kerätään .

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

Tästä taulukosta koottu SDNF näyttää tältä:

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

Tämän lausekkeen termit ovat lausekkeen yksinkertaisia implikantteja . Siirtyminen pelkistetystä muodosta minimiin tapahtuu implicanttimatriisin avulla .

Implikanttimatriisi

Tietyn funktion SDNF :n jäsenet sopivat sarakkeisiin ja riveihin - yksinkertaisiin implikantteihin, eli lyhennetyn muodon jäseniin. PDNF- termien sarakkeet on merkitty , jotka yksittäiset pääimplikantit absorboivat. Seuraavassa taulukossa yksinkertainen implikantti absorboi termit ja (ensimmäiseen ja toiseen sarakkeeseen sijoitetaan ristit). ${\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$

Yksinkertainen implikantti	$\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}}}$	$\ajat$	$\ajat$
$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$	$\ajat$		$\ajat$
$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$			$\ajat$	$\ajat$
$x_2 \cdot x_3 \cdot \overline{x_4}$				$\ajat$	$\ajat$
$x_1 \cdot x_2 \cdot x_3$					$\ajat$	$\ajat$

Toinen implikantti absorboi SDNF:n ensimmäisen ja kolmannen jäsenen ( merkitty ristillä) jne. Implikantit, joita ei voida sulkea pois, muodostavat ytimen . Tällaiset implikantit määritetään yllä olevan matriisin avulla. Jokaiselle niistä on vähintään yksi sarake, jonka vain tämä implikantti kattaa.

Esimerkissämme implikantit ja (ne menevät päällekkäin toisen ja kuudennen sarakkeen kanssa) muodostavat ytimen. On mahdotonta sulkea samanaikaisesti pois pelkistetystä muodosta kaikkia implicantteja, jotka eivät sisälly ytimeen, koska yhden implikantin poissulkeminen voi tehdä toisesta tarpeettoman jäsenen. Vähimmäismuodon saamiseksi riittää, että valitaan ytimeen sisältymättömien implikanttien joukosta sellainen vähimmäismäärä, jossa kussakin näistä implicanteista on vähintään kirjaimia, mikä varmistaa kaikkien sarakkeiden päällekkäisyyden, joita ei kata ytimen jäseniä. Tarkasteltavassa esimerkissä on tarpeen peittää matriisin kolmas ja neljäs sarake implikantteilla, jotka eivät sisälly ytimeen. Tämä voidaan saavuttaa useilla tavoilla, mutta koska on välttämätöntä valita implikanttien vähimmäismäärä, on selvää, että implikantti tulee valita siten, että se peittää nämä sarakkeet . ${\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}$

Tietyn funktion pienin disjunktiivinen normaalimuoto (MDNF) on:

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)

Tätä lauseketta vastaava lohkokaavio on esitetty vasemmalla olevassa kuvassa. Siirtyminen supistetusta järjestelmästä MDNF:ään toteutettiin poistamalla ylimääräiset termit - implikantti ja . Osoittakaamme, että tällainen jäsenten jättäminen loogisen lausekkeen ulkopuolelle on hyväksyttävää. $\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$ $x_2 \cdot x_3 \cdot \overline{x_4}$

Implikanteista tulee yhtä suuria kuin loki. 1 seuraaville argumenttiarvoille: , , ja , , . $\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$

Näiden implikanttien rooli funktion lyhennetyn muodon ilmaisussa on vain antaa funktiolle arvo 1. Näillä joukoilla funktio on kuitenkin yhtä suuri kuin 1 muiden implikanttien takia. ilmaisusta. Itse asiassa korvaamalla yllä ilmoitetut arvot kaavaan (a) saamme: $f(x_{1},x_{2},x_{3},x_{4})$

osoitteessa , , $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 = yksi$ ;

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

Menetelmän käyttäminen CNF :n vähimmäismäärän saamiseksi

Minimikonjunktiivisen normaalimuodon (MCNF) saamiseksi Quinen menetelmällä otetaan käyttöön seuraavat kriteerit:

minimointia varten emme ota SDNF , vaan SKNF- funktioita;
liimattavat termiparit muutetaan muotoon: tai ; $w\vee x$ $w\vee\overline{x}$
Absorptiosäännöstö näyttää tältä:

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

Katso myös

Muistiinpanot

↑ Lyhyt kuvaus Quine-menetelmästä Arkistoitu 20. helmikuuta 2009 Wayback Machinessa www.ptca.narod.ru
↑ Luento: FAL-minimointi Arkistoitu 14. huhtikuuta 2009 Wayback Machinessa www.works.tarefer.ru
↑ Esimerkki kytkentätoiminnon minimoimisesta Quine-menetelmällä Arkistoitu 17. huhtikuuta 2010 Wayback Machinessa matri-tri-ca.narod.ru