Disjunctive Normal Form

boolean-algebra

Definition

Disjunctive Normal Form

In Boolean algebra, a Boolean function is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literal. Thus, $f$ of form the following form, where $L_{ij}$ are literals, is in disjunctive normal form:

$$f=(L_{1,1}\wedge \cdots \wedge L_{1,m})\vee \cdots \vee (L_{n,1}\wedge \cdots \wedge L_{n,m})$$

Examples:

• $(a\wedge b)\vee (a\wedge \neg c\wedge d)\vee \neg b$
• $(\neg a\wedge x\wedge \neg c\vee d)\vee (\neg b\wedge \neg y)$