Normal Forms
January 2026
Disjunctive Normal Form
A formula is in DNF when it is a disjunction ($\vee$) of conjunctions ($\wedge$) of propositional variables or their negatives.
A DNF can be constructed by finding every set of variables that makes a statement true.
Conjunctive Normal Form
A formula is said to be in conjunctive normal form (CNF) when it is the conjunction ($\wedge$) or the disjunctions ($\vee$) of propositional variables or their negations.
Every expression built up according to the rules of propositional calculus is equivalent to some formula in conjunctive normal form!
To construct CNFs, logical equivalences can be used.
Logical Equivalences
Double Negation
\[
¬(¬P) \Leftrightarrow P
\]
Commutative Laws
\[
P \vee Q \Leftrightarrow Q \vee P\\
\\
P \wedge Q \Leftrightarrow Q \wedge P
\]
Associative Laws
\[
(P \vee Q) \vee R \Leftrightarrow P \vee (Q \vee R)\\
\\
(P \wedge Q) \wedge R \Leftrightarrow P \wedge (Q \wedge R)
\]
Distributive Laws
\[
P \vee (Q \wedge R) \Leftrightarrow (P \vee Q) \wedge (P \vee R)\\
\\
P \wedge (Q \vee R) \Leftrightarrow (P \wedge Q) \vee (P \wedge R)\\
\\
(Q \wedge R) \vee P \Leftrightarrow (Q \vee P) \wedge (R \vee P)\\
\\
(Q \vee R) \wedge P \Leftrightarrow (Q \wedge P) \vee (R \wedge P)
\]
De Morgan’s Laws
\[
¬(P \vee Q) \Leftrightarrow ¬P \wedge ¬Q\\
\\
¬(P \wedge Q) \Leftrightarrow ¬P \vee ¬Q
\]
Implication
\[
(P \Rightarrow Q) \Leftrightarrow (¬P \vee Q)\\
\\
(P \Leftrightarrow Q) \Leftrightarrow (P \Rightarrow Q) \wedge (Q \Rightarrow P)
\]
Excluded Middle
\[
P \vee ¬P \Leftrightarrow T
\]
Contradiction
\[
P \wedge ¬P \Leftrightarrow F
\]
Idempotence
\[
P \vee P \Leftrightarrow P\\
\\
P \wedge P \Leftrightarrow P
\]
Identity
\[
P \wedge T \Leftrightarrow T\\
\\
P \vee F \Leftrightarrow P
\]
Domination
\[
P \vee T \Leftrightarrow T\\
\\
P \wedge F \Leftrightarrow F
\]
Using Logical Equivalences
Logical equivalences can be used to assist with rewriting an expression in CNF or DNF.
- Use implication laws to eliminate $\Rightarrow$ and $\Leftrightarrow$
- Use Double negation and De Morgan to bring
¬immediately before propositional variables - Repeatedly use distributive laws, etc to obtain a normal form
Example to find CNF
\[
Q \Rightarrow (¬P \wedge (Q \vee R))\\
\\
\begin{aligned}
Q \Rightarrow (¬P \wedge (Q \vee R)) &\Leftrightarrow ¬Q \vee (¬P \wedge (Q \vee R))\\
&\Leftrightarrow ¬Q \vee ((¬P \wedge Q) \vee (¬P \wedge R))\\
&\Leftrightarrow ¬Q \vee (¬P \wedge Q) \vee (¬P \wedge R)
\end{aligned}
\]
Example to find DNF
\[
Q \Rightarrow (¬P \wedge (Q \vee R))\\
\\
\begin{aligned}
Q \Rightarrow (¬P \wedge (Q \vee R)) &\Leftrightarrow ¬Q \vee (¬P \wedge (Q \vee R))\\
&\Leftrightarrow (¬Q \vee ¬P) \wedge (¬Q \vee (Q \vee R))\\
&\Leftrightarrow (¬Q \vee ¬P) \wedge (¬Q \vee Q \vee R)
\end{aligned}
\]