Forma normală a conjunctivei

În logica booleană , o formulă este în formă normală conjunctivă sau comună ( FNC ), denumită și CNF (acronim pentru forma normală conjunctivă ) dacă este o conjuncție de clauze , în care clauzele sunt o disjuncție a literelor. Prin urmare, o formulă în CNF are următoarea structură:

$\bigwedge _{i=1}^{n}\left(\bigvee _{k=1}^{m(i)}L_{i,k}\right)$ ${\ displaystyle \ bigwedge _ {i = 1} ^ {n} \ left (\ bigvee _ {k = 1} ^ {m (i)} L_ {i, k} \ right)}$ ${\ displaystyle \ bigwedge _ {i = 1} ^ {n} \ left (\ bigvee _ {k = 1} ^ {m (i)} L_ {i, k} \ right)}$

$n$ ${\ displaystyle n}$ $n$ : Numărul de clauze.

$m(i)$ ${\ displaystyle m (i)}$ ${\ displaystyle m (i)}$ : Numărul de litere ale clauzei a-a.

$L_{i,k}$ ${\ displaystyle L_ {i, k}}$ ${\ displaystyle L_ {i, k}}$ : Este al k-lea literal al clauzei a-a. Un literal poate fi o variabilă booleană (adică poate fi doar 0 sau 1, adevărat sau fals) sau negarea unei variabile.

O funcție booleană este o funcție care are mai multe valori booleene ca intrare (adică adevărat / fals sau 1/0) și ca urmare are o valoare booleană. Pentru fiecare funcție booleană, există o formulă în formă normală conjunctivă care produce aceleași valori ca rezultat.

Exemple

Următoarele formule sunt în CNF:

(\neg A\vee B)\wedge (B\vee C)

{\ displaystyle (\ neg A \ vee B) \ wedge (B \ vee C)}

{\ displaystyle (\ neg A \ vee B) \ wedge (B \ vee C)}

(A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E)

{\ displaystyle (A \ vee B) \ wedge (\ neg B \ vee C \ vee \ neg D) \ wedge (D \ vee \ neg E)}

{\ displaystyle (A \ vee B) \ wedge (\ neg B \ vee C \ vee \ neg D) \ wedge (D \ vee \ neg E)}

(\neg B\vee C)

{\ displaystyle (\ neg B \ vee C)}

{\ displaystyle (\ neg B \ vee C)}

(\neg B\vee C)\wedge A

{\ displaystyle (\ neg B \ vee C) \ wedge A}

{\ displaystyle (\ neg B \ vee C) \ wedge A}

A\wedge B

{\ displaystyle A \ wedge B}

A \ wedge B

Ultima formulă are două clauze, ambele cu un singur literal.

Rețineți că formule precum ultima, adică de tip $A_{1}\vee A_{2}\vee ...\vee A_{n}$ ${\ displaystyle A_ {1} \ vee A_ {2} \ vee ... \ vee A_ {n}}$ ${\ displaystyle A_ {1} \ vee A_ {2} \ vee ... \ vee A_ {n}}$ (sau similar $A_{1}\wedge A_{2}\wedge ...\wedge A_{n}$ ${\ displaystyle A_ {1} \ wedge A_ {2} \ wedge ... \ wedge A_ {n}}$ ${\ displaystyle A_ {1} \ wedge A_ {2} \ wedge ... \ wedge A_ {n}}$ ) unde este $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ sunt literali, trebuie considerați simultan DNF și CNF.

Elemente conexe

linkuri externe

( EN ) Formă conjunctivă normală , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică