Tökéletes konjunktív normál forma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2018. november 23-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A tökéletes konjunktív normálforma (CKNF) a logikai algebra függvényének (Boole-függvény) logikai kifejezésként való megjelenítésének egyik formája. Ez a CNF egy speciális esete, amely megfelel a következő három feltételnek:

Nincsenek benne azonos kifejezések (elemi diszjunkciók);

Nincsenek ismétlődő változók az egyes tényezőkben;

· minden szorzó tartalmazza az összes változót, amelytől a Boole-függvény függ (minden változó direkt vagy inverz formában is szerepelhet a szorzóban).

Bármely Boole-képlet , amely nem teljesen igaz , redukálható SKNF-re. [1] .

Példa az SKNF megtalálására

Ahhoz, hogy egy függvény SKNF-jét megkapjuk, össze kell fordítani annak igazságtáblázatát. Vegyük például a cikk egyik igazságtáblázatát, amely a logikai függvényeket Quine módszerével minimalizálja :

$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

A sor celláiban csak azok a kombinációk vannak megjelölve, amelyek a logikai kifejezést nulla állapotba hozzák. $f(x_{1},x_{2},x_{3},x_{4})$

A negyedik sor 0-t tartalmaz a megadott mezőben. Mind a négy változó értéke fel van jegyezve, ezek a következők:

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

Egy változót inverzió nélkül írunk a diszjunkcióba, ha a halmazban egyenlő 0-val, és inverzióval, ha egyenlő 1-gyel. A vizsgált függvény SKNF első tagja így néz ki: $x_{1}\vee x_{2}\vee {\overline {x_{3}}}\vee {\overline {x_{4}}}$

Az SKNF többi tagját analógia alapján állítjuk össze: [2]

({x_{1}}\vagy {x_{2}}\vagy {\overline {x_{3}}}\vagy {\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}}}\vagy {\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}}}\vagy {x_{2 }}\lor {\overline {x_{3}}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline { x_{3}}}\vagy {\overline {x_{4}}})\land

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

Lásd még

Jegyzetek

↑ Matematikai logika. Útmutató a "Diszkrét matematika alapjai a 220220 szakos hallgatóknak" kurzushoz . Letöltve: 2016. március 25. Az eredetiből archiválva : 2016. április 9.. (határozatlan)
↑ V.I. Igoshin. Feladatfüzet-műhely a matematikai logikáról. 1986

$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}$	$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}$	$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