Täydellinen disjunktiivinen normaalimuoto

Täydellinen disjunktiivinen normaalimuoto (PDNF) on yksi niistä muodoista, joilla esitetään logiikan algebran funktio (Boolen funktio) loogisen lausekkeen muodossa. Se on DNF :n erikoistapaus, joka täyttää seuraavat kolme ehtoa [1] :

sillä ei ole identtisiä termejä (alkeiskonjunktiot);
jokaisessa termissä ei ole toistuvia muuttujia;
jokainen termi sisältää kaikki muuttujat, joista Boolen funktio riippuu (jokainen muuttuja voidaan sisällyttää termiin joko suorassa tai käänteisessä muodossa).

Mikä tahansa Boolen kaava , joka ei ole identtisesti epätosi, voidaan pelkistää SDNF:ksi, ja ainutlaatuisella tavalla, toisin sanoen mille tahansa logiikkaalgebran tyydyttävälle funktiolle, on oma SDNF, ja ainoa [2] .

Lyhyt teoria

DNF on "tulojen summa", ja AND-operaatio (konjunktio) toimii "kerto-operaationa" ja OR-operaatio (disjunktio) toimii "lisäys"-operaationa. Tekijät ovat erilaisia muuttujia, ja ne voidaan sisällyttää tuotteeseen sekä suorassa että käänteisessä muodossa.

Alla on esimerkki DNF:stä:

$F(A,B,C,D,E)={\bar {A}}B+A{\bar {B}}E+B{\bar {C}}D.$

Yleisesti ottaen DNF voi sisältää toistuvia termejä, ja jokainen termi voi sisältää toistuvia tekijöitä, esimerkiksi:

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D.$

Matemaattisesti katsottuna tällainen kloonaus on merkityksetöntä, koska Boolen algebrassa minkä tahansa lausekkeen kertominen itsestään ja lausekkeen lisääminen itseensä ei muuta tulosta ( ), mutta lausekkeen lisääminen omalla inversiollaan ja kertominen omalla inversiollaan antaa vakiot ( ). Viimeisessä lausekkeessa voit poistaa toistuvat termit ja tekijät seuraavasti: $x+x=x;x\cdot x=x$ $x+{\bar {x}}=1;x\cdot {\bar {x}}=0$

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D={\bar {A}}\cdot (B{\bar {B)))+(AA)\cdot {\bar {B}}E+B{\bar {C}}D={\bar {A}}\cdot 0+A{\bar {B}}E+B{\bar {C}}D=A{\bar {B}}E+B{\ baari{C}}D.$

Tästä syystä toistuvia termejä ja tekijöitä sisältäviä DNF:itä käytetään yleensä vain aputarkoituksiin, esimerkiksi lausekkeiden analyyttiseen muuntamiseen.

SDNF on kanoninen muoto Boolen funktion esittämiseksi DNF:nä, jossa termien ja tekijöiden toisto on kielletty. Lisäksi jokaisen termin tulee sisältää kaikki muuttujat (suorassa tai käänteisessä muodossa).

Alla on esimerkki SDNF:stä:

$F(A,B,C,D,E)={\bar {A}}BCDE+A{\bar {B}}C{\bar {D}}E+AB{\bar {C} }D{\bar{E}}.$

SDNF:n merkitys on se

jokaiselle tietylle toiminnolle sen SDNF on ainutlaatuinen ja yksiselitteinen;
SDNF vastaa yksitellen funktion totuustaulukkoa. Jokainen SDNF:n termi vastaa yhtä riviä totuustaulukossa, jossa funktio on yhtä suuri kuin yksi. Siten SDNF:n termien määrä on yhtä suuri kuin yksikköarvojen määrä, jonka Boolen funktio ottaa määrittelyalueellaan;
SDNF saadaan alkeellisesti funktion totuustaulukosta;
SDNF on kätevä peruslauseke funktion minimoinnissa, siitä on erityisen helppo löytää "liimaukseen" sopivia termejä.

Esimerkki SDNF:n löytämisestä

Funktion SDNF:n saamiseksi sen on käännettävä sen totuustaulukko . Otetaan esimerkiksi yksi totuustaulukoista:

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

Tuloksen soluihin merkitään vain ne yhdistelmät, jotka tuovat loogisen lausekkeen tilaan yksi. Lisäksi otetaan huomioon muuttujien arvot, joissa funktio on yhtä suuri kuin 1. Jos muuttujan arvo on 0, niin se kirjoitetaan inversiolla. Jos muuttujan arvo on 1, ei inversiota. $f(x_{1},x_{2},x_{3})$

Ensimmäisellä rivillä on 1 määritetyssä kentässä. Kaikkien kolmen muuttujan arvot on merkitty muistiin, nämä ovat:

$x_{1}=0$
$x_{2}=0$
$x_{3}=0$

Nolla-arvot - tässä kaikki muuttujat edustavat nollia - kirjoitetaan lopulliseen lausekkeeseen tämän muuttujan käänteisarvolla. Tarkasteltavan funktion SDNF:n ensimmäinen jäsen näyttää tältä: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$

Toisen jäsenen muuttujat:

$x_{1}=0$
$x_{2}=0$
$x_{3}=1$

$x_{3}$ tässä tapauksessa esitetään ilman käänteistä: ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}$

Siten kaikki solut analysoidaan . Tämän funktion täydellinen DNF on kaikkien tuloksena olevien termien disjunktio ( alkeiskonjunktiot ). $f(x_{1},x_{2},x_{3})$

Tämän toiminnon täydellinen DNF on:

$f(x_{1},x_{2},x_{3})=({\overline {x_{1))}\land {\overline {x_{2))}\land {\overline { x_{3}}})\vee ({\overline {x_{1}}}\land {\overline {x_{2}}}\land x_{3})\vee ({\overline {x_{1} }}\land x_{2}\land {\overline {x_{3}}})\vee (x_{1}\land x_{2}\land {\overline {x_{3}}})$

Katso myös

Muistiinpanot

↑ Vinogradova M.S., Tkachev S.B. Boolen funktiot. - M . : Kustantaja MSTU im. N.E. Bauman, 2007. - 32 s.
↑ Matemaattinen logiikka . - Perm: Publishing House of PSTU, 1998. - 17 s. Arkistoitu 9. huhtikuuta 2016 Wayback Machinessa