Forma normală conjunctivă perfectă

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 noiembrie 2018; verificările necesită 2 modificări .

O formă normală conjunctivă perfectă (CKNF) este una dintre formele de reprezentare a unei funcții a algebrei logicii (funcția booleană) ca expresie logică. Este un caz special de CNF care îndeplinește următoarele trei condiții:

Nu are termeni identici (disjuncții elementare);

Nu există variabile care se repetă în fiecare factor;

· fiecare multiplicator conține toate variabilele de care depinde funcția booleană (fiecare variabilă poate fi inclusă în multiplicator fie sub formă directă, fie inversă).

Orice formulă booleană care nu este identic adevărată poate fi redusă la SKNF. [1] .

Un exemplu de găsire a SKNF

Pentru a obține SKNF-ul unei funcții, este necesar să compilați tabelul de adevăr al acesteia. De exemplu, să luăm unul dintre tabelele de adevăr ale articolului care minimizează funcțiile logice prin metoda lui Quine :

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

În celulele liniei , sunt marcate doar acele combinații care aduc expresia logică la starea zero. $f(x_{1},x_{2},x_{3},x_{4})$

A patra linie conține 0 în câmpul specificat. Sunt notate valorile tuturor celor patru variabile, acestea sunt:

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

O variabilă este scrisă în disjuncție fără inversare dacă este egală cu 0 în mulțime și cu inversare dacă este egală cu 1. Primul membru al SKNF al funcției considerate arată astfel: $x_{1}\vee x_{2}\vee {\overline {x_{3}}}\vee {\overline {x_{4}}}$

Membrii rămași ai SKNF sunt compilați prin analogie: [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}}})

Vezi și

Note

↑ Logica matematică. Orientări pentru cursul „Fundamentele matematicii discrete pentru studenții specialității 220220” . Preluat la 25 martie 2016. Arhivat din original la 9 aprilie 2016. (nedefinit)
↑ V.I. Igoshin. Caiet de sarcini-atelier de logică matematică. 1986

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

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

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