Forma disjunctivă normală

În logica booleană , o formulă este în formă normală disjunctivă sau disjunctivă ( FND ), denumită și DNF (acronim pentru Disjunctive Normal Form ) dacă este o disjuncție a clauzelor, unde clauzele sunt o conjuncție a literelor. Prin urmare, o formulă DNF are următoarea structură:

$\bigvee _{i=1}^{n}\left(\bigwedge _{k=1}^{m(i)}L_{i,k}\right)$ ${\ displaystyle \ bigvee _ {i = 1} ^ {n} \ left (\ bigwedge _ {k = 1} ^ {m (i)} L_ {i, k} \ right)}$ ${\ displaystyle \ bigvee _ {i = 1} ^ {n} \ left (\ bigwedge _ {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.

Exemple

Următoarele formule sunt în DNF:

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

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

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

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

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

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

(\neg B\wedge C)

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

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

(\neg B\wedge C)\vee A

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

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

A\vee B

{\ displaystyle A \ vee B}

A \ v și 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

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