Täydellinen konjunktiivinen normaalimuoto

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

Täydellinen konjunktiivinen normaalimuoto (CKNF) on yksi logiikkaalgebran funktion (Boolen funktio) esittämisestä loogisena lausekkeena. Se on CNF:n erikoistapaus, joka täyttää seuraavat kolme ehtoa:

Sillä ei ole identtisiä termejä (alkeisdisjunktiot);

Jokaisessa tekijässä ei ole toistuvia muuttujia;

· jokainen kertoja sisältää kaikki muuttujat, joista Boolen funktio riippuu (jokainen muuttuja voidaan sisällyttää kertoimeen joko suorassa tai käänteisessä muodossa).

Mikä tahansa Boolen kaava , joka ei ole täysin totta , voidaan pelkistää SKNF:ksi. [1] .

Esimerkki SKNF:n löytämisestä

Funktion SKNF:n saamiseksi sen totuustaulukko on laadittava. Otetaan esimerkiksi yksi artikkelin totuustaulukoista, joka minimoi loogiset funktiot Quinen menetelmällä :

$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

Rivin soluihin merkitään vain ne yhdistelmät, jotka tuovat loogisen lausekkeen nollan tilaan. $f(x_{1},x_{2},x_{3},x_{4})$

Neljännellä rivillä on 0 määritetyssä kentässä. Kaikkien neljän muuttujan arvot on merkitty muistiin, nämä ovat:

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

Muuttuja kirjoitetaan disjunktioon ilman inversiota, jos se on joukossa 0, ja inversiolla, jos se on yhtä suuri kuin 1. Tarkastelun funktion SKNF:n ensimmäinen jäsen näyttää tältä: $x_{1}\vee x_{2}\vee {\overline {x_{3}}}\vee {\overline {x_{4}}}$

Muut SKNF:n jäsenet on koottu analogisesti: [2]

({x_{1}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land ({x_{1 }}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({x_{1}}\lor {\overline {x_{2} }}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {\overline { x_{3}}}\lor {\overline {x_{4}}})\land

({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1} }}\lor {x_{2}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({\overline {x_{1}}}\lor {x_{2 }}\lor {\overline {x_{3}}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline { x_{3}}}\lor {\overline {x_{4}}})\land

({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({\overline { x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})

Katso myös

Muistiinpanot

↑ Matemaattinen logiikka. Ohjeet kurssille "Diskreetin matematiikan perusteet erikoisalan opiskelijoille 220220" . Haettu 25. maaliskuuta 2016. Arkistoitu alkuperäisestä 9. huhtikuuta 2016. (määrätön)
↑ V.I. Igoshin. Matemaattisen logiikan tehtäväkirja-työpaja. 1986