Conjunctive Normal Form

boolean-algebra

Definition

Conjunctive Normal Form

In Boolean algebra, a Boolean function is in conjunctive normal form (CNF) if it is a conjunction of disjunctions of literal. Thus, $f$ of form the following form, where $L_{ij}$ are literals, is in conjunctive normal form:

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

Examples:

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