The Central Idea
Logical expressions can often be written in many equivalent ways.
A normal form imposes a standard structure on the expression.
Two of the most important normal forms are:
- disjunctive normal form, abbreviated DNF;
- conjunctive normal form, abbreviated CNF.
DNF is built as an OR of AND-groups.
CNF is built as an AND of OR-groups.
Why Standard Form Matters
Standardization makes logical structure easier to inspect.
A normal form can help us:
- compare logically equivalent formulas;
- identify satisfying assignments;
- translate truth tables into formulas;
- prepare formulas for satisfiability procedures;
- design digital logic;
- organize symbolic transformations.
Literal
A literal is either a propositional variable or the negation of a propositional variable.
Examples include
\[ p,\qquad \neg p,\qquad q,\qquad \neg r. \]The expression
\[ p\land q \]is not a literal because it combines two propositions.
Positive and Negative Literals
A variable appearing without negation is a positive literal.
\[ p \]is a positive literal.
A negated variable is a negative literal.
\[ \neg p \]is a negative literal.
Terms and Clauses
In the language of normal forms, two common structures appear repeatedly.
A term is a conjunction of literals.
For example,
\[ p\land\neg q\land r. \]A clause is a disjunction of literals.
For example,
\[ p\lor\neg q\lor r. \]Disjunctive Normal Form
A formula is in disjunctive normal form when it is written as a disjunction of one or more terms.
Its overall pattern is
\[ \boxed{ (\text{AND-group})\lor(\text{AND-group})\lor\cdots }. \]For example,
\[ (p\land q)\lor(\neg p\land r) \]is in DNF.
Reading DNF
A DNF formula is true when at least one of its terms is true.
Consider
\[ (p\land q)\lor(\neg p\land r). \]The formula is true if either:
- \(p\) and \(q\) are both true; or
- \(p\) is false and \(r\) is true.
DNF therefore naturally describes alternative satisfying cases.
Conjunctive Normal Form
A formula is in conjunctive normal form when it is written as a conjunction of one or more clauses.
Its overall pattern is
\[ \boxed{ (\text{OR-group})\land(\text{OR-group})\land\cdots }. \]For example,
\[ (p\lor q)\land(\neg p\lor r) \]is in CNF.
Reading CNF
A CNF formula is true only when every clause is true.
Consider
\[ (p\lor q)\land(\neg p\lor r). \]Both conditions must hold:
- at least one of \(p\) or \(q\) must be true;
- at least one of \(\neg p\) or \(r\) must be true.
CNF therefore naturally describes systems of simultaneous constraints.
DNF and CNF Are Structural Descriptions
DNF and CNF describe the outer and inner operations of a formula.
In DNF:
\[ \text{OR outside, AND inside}. \]In CNF:
\[ \text{AND outside, OR inside}. \]This structural distinction is the central pattern to recognize.
A Single Literal Can Count as a Normal Form
A single literal such as
\[ p \]can be regarded as both a one-term DNF and a one-clause CNF.
Likewise,
\[ \neg p \]is already structurally simple enough to satisfy both forms.
Negation Normal Form
Before converting to CNF or DNF, it is often useful to place a formula in negation normal form, or NNF.
In NNF:
- only AND, OR, and NOT remain;
- every NOT applies directly to a propositional variable.
For example,
\[ (\neg p\lor q)\land(\neg r\lor s) \]is in NNF.
What Is Not in Negation Normal Form?
The expression
\[ \neg(p\land q) \]is not in NNF because the negation applies to a compound expression.
Using De Morgan’s law,
\[ \neg(p\land q) \equiv \neg p\lor\neg q. \]The rewritten expression is in NNF.
Removing Implication Before Normalization
Implications are usually eliminated before constructing CNF or DNF.
Use
\[ \boxed{p\to q\equiv\neg p\lor q}. \]For example,
\[ (p\to q)\land r \]becomes
\[ (\neg p\lor q)\land r. \]This is already in CNF.
Removing Biconditional Before Normalization
A biconditional can be rewritten as
\[ p\leftrightarrow q \equiv (p\to q)\land(q\to p). \]Replacing the implications gives
\[ (\neg p\lor q)\land(\neg q\lor p). \]This is a CNF representation of the biconditional.
Moving Negations Inward
De Morgan’s laws move negations toward the variables:
\[ \neg(A\land B) \equiv \neg A\lor\neg B, \] \[ \neg(A\lor B) \equiv \neg A\land\neg B. \]Double negation removes pairs of negations:
\[ \neg\neg A\equiv A. \]Repeating these steps eventually places NOT directly on variables.
Example: Convert to Negation Normal Form
Rewrite
\[ \neg(p\to q). \]Eliminate implication:
\[ \neg(\neg p\lor q). \]Apply De Morgan:
\[ \neg\neg p\land\neg q. \]Remove double negation:
\[ \boxed{p\land\neg q}. \]The result is in NNF and also in DNF.
Distribution Creates DNF
To create DNF, distribute AND over OR when necessary.
For example,
\[ p\land(q\lor r) \]becomes
\[ \boxed{(p\land q)\lor(p\land r)}. \]The result is an OR of AND-terms.
Distribution Creates CNF
To create CNF, distribute OR over AND when necessary.
For example,
\[ p\lor(q\land r) \]becomes
\[ \boxed{(p\lor q)\land(p\lor r)}. \]The result is an AND of OR-clauses.
Example: Convert to DNF
Convert
\[ p\land(q\lor\neg r) \]to DNF.
Distribute \(p\):
\[ (p\land q)\lor(p\land\neg r). \]Therefore,
\[ \boxed{ p\land(q\lor\neg r) \equiv (p\land q)\lor(p\land\neg r) }. \]Example: Convert to CNF
Convert
\[ p\lor(q\land\neg r) \]to CNF.
Distribute \(p\lor\) across the conjunction:
\[ \boxed{ (p\lor q)\land(p\lor\neg r) }. \]More Than One Distribution Step
Consider
\[ (p\lor q)\land(r\lor s). \]This is already in CNF.
To obtain DNF, distribute:
\[ (p\land r)\lor(p\land s)\lor(q\land r)\lor(q\land s). \]The result is a disjunction of four conjunctions.
Normal Form Need Not Be Unique
A logical function may have several equivalent formulas in CNF or DNF.
For example,
\[ p \]is equivalent to
\[ (p\land q)\lor(p\land\neg q). \]Both are in DNF, but one is much simpler.
This motivates the distinction between ordinary normal forms and canonical normal forms.
Canonical Disjunctive Normal Form
A canonical DNF is built from terms that mention every propositional variable exactly once, either positively or negatively.
Such complete terms are often called minterms.
For variables \(p\) and \(q\), examples are
\[ p\land q, \] \[ p\land\neg q, \] \[ \neg p\land q, \] \[ \neg p\land\neg q. \]Minterms Describe Individual True Rows
Each minterm is true under exactly one truth assignment.
For example,
\[ p\land\neg q \]is true exactly when
\[ p=T,\qquad q=F. \]This makes minterms ideal for translating true rows of a truth table into DNF.
Constructing Canonical DNF from a Truth Table
To construct canonical DNF:
- find every row where the formula is true;
- write one minterm for each true row;
- OR all of those minterms together.
The resulting formula is true in exactly the same rows as the original.
Example: Canonical DNF from True Rows
Suppose a function of \(p\) and \(q\) is true in the rows
\[ (T,F) \]and
\[ (F,T). \]The first row gives
\[ p\land\neg q. \]The second gives
\[ \neg p\land q. \]Therefore, the canonical DNF is
\[ \boxed{ (p\land\neg q)\lor(\neg p\land q) }. \]This is the XOR pattern.
Canonical Conjunctive Normal Form
A canonical CNF is built from clauses that mention every propositional variable exactly once, either positively or negatively.
Such complete clauses are often called maxterms.
Maxterms Describe Individual False Rows
Each maxterm is false under exactly one truth assignment.
Suppose we want a clause false when
\[ p=T,\qquad q=F. \]A disjunction is false only when every literal in it is false.
Therefore, use
\[ \boxed{\neg p\lor q}. \]When \(p=T\) and \(q=F\), both literals are false.
Constructing Canonical CNF from a Truth Table
To construct canonical CNF:
- find every row where the formula is false;
- write one maxterm that is false in each such row;
- AND all of those maxterms together.
The Sign Rule for Minterms
When building a minterm from a true row:
- write the variable unnegated if its row value is T;
- write the variable negated if its row value is F.
Thus the row
\[ p=T,\quad q=F,\quad r=T \]gives the minterm
\[ \boxed{p\land\neg q\land r}. \]The Sign Rule for Maxterms
When building a maxterm from a false row:
- write the variable negated if its row value is T;
- write the variable unnegated if its row value is F.
Thus the row
\[ p=T,\quad q=F,\quad r=T \]gives the maxterm
\[ \boxed{\neg p\lor q\lor\neg r}. \]Every literal in that clause is false in the selected row.
Example: Canonical CNF
Suppose a function of \(p\) and \(q\) is false in the rows
\[ (T,T) \]and
\[ (F,F). \]For \((T,T)\), the maxterm is
\[ \neg p\lor\neg q. \]For \((F,F)\), the maxterm is
\[ p\lor q. \]Therefore, the canonical CNF is
\[ \boxed{ (\neg p\lor\neg q)\land(p\lor q) }. \]This formula is true exactly when \(p\) and \(q\) differ.
Canonical Forms Encode the Truth Table
Canonical DNF records the true rows.
Canonical CNF records the false rows.
Therefore, either canonical form completely describes the Boolean function represented by the truth table.
Canonical DNF of a Tautology
A tautology is true in every row.
Its canonical DNF therefore includes a minterm for every possible truth assignment.
For two variables,
\[ (p\land q) \lor (p\land\neg q) \lor (\neg p\land q) \lor (\neg p\land\neg q) \]is a canonical DNF for \(T\).
Canonical CNF of a Contradiction
A contradiction is false in every row.
Its canonical CNF therefore includes one maxterm for every possible truth assignment.
This construction forces the overall conjunction to fail under every row.
Empty-Case Conventions
In formal treatments, a function with no true rows can be represented by the Boolean constant
\[ F, \]while a function with no false rows can be represented by
\[ T. \]These constants serve as the simplest normal forms for contradiction and tautology.
From DNF to CNF
A DNF formula can be converted to CNF using equivalence laws, especially distribution.
For example,
\[ (p\land q)\lor r \]becomes
\[ \boxed{(p\lor r)\land(q\lor r)}. \]OR has been distributed over AND.
From CNF to DNF
Similarly,
\[ (p\lor q)\land r \]can be converted to DNF:
\[ \boxed{(p\land r)\lor(q\land r)}. \]AND has been distributed over OR.
Normal-Form Conversion Can Expand an Expression
Conversion may make a formula much longer.
For example,
\[ (p\lor q)\land(r\lor s) \]is compact CNF.
Its fully distributed DNF is
\[ (p\land r) \lor (p\land s) \lor (q\land r) \lor (q\land s). \]Standardization can therefore trade compactness for structural regularity.
Normal Form and Simplest Form Are Different Goals
A formula can be in CNF or DNF without being minimal or especially short.
For example,
\[ (p\land q)\lor(p\land\neg q) \]is DNF.
It is also equivalent to the simpler expression
\[ p. \]Normalization standardizes structure; simplification reduces unnecessary structure.
CNF and Constraint Satisfaction
CNF is especially important in satisfiability problems.
A CNF formula
\[ C_1\land C_2\land\cdots\land C_k \]is satisfied only when every clause \(C_i\) is true.
This makes each clause a separate logical constraint.
Example: A CNF Constraint System
Consider
\[ (p\lor q)\land(\neg p\lor r)\land(\neg q\lor r). \]A satisfying assignment must make all three clauses true simultaneously.
This type of representation is central to SAT solving.
DNF and Explicit Satisfying Cases
DNF is often useful when the satisfying assignments can be described as a collection of explicit alternatives.
For example,
\[ (p\land q)\lor(\neg p\land r) \]directly presents two separate ways the formula can become true.
Normal Forms and Digital Logic
DNF naturally corresponds to an OR of AND-produced terms.
CNF naturally corresponds to an AND of OR-produced clauses.
These structures can be translated into layered digital circuits.
The later lesson on logic gates and circuits will make that connection explicit.
Common Error: Reversing CNF and DNF
Remember:
\[ \boxed{\text{DNF = OR of ANDs}} \]and
\[ \boxed{\text{CNF = AND of ORs}}. \]Reversing these patterns is one of the most common classification errors.
Common Error: Leaving Implications Inside a Claimed Normal Form
A formula such as
\[ (p\to q)\land r \]is not in standard CNF because the implication has not been eliminated.
Rewrite it as
\[ (\neg p\lor q)\land r. \]Common Error: Leaving Negation on a Compound Expression
The expression
\[ \neg(p\lor q) \]has not yet been pushed to literal level.
Use De Morgan:
\[ \boxed{\neg p\land\neg q}. \]Common Error: Using the Wrong Sign in a Minterm
For the true row
\[ p=T,\qquad q=F, \]the correct minterm is
\[ p\land\neg q. \]The literal must be true under the selected row.
Common Error: Using the Minterm Rule for Maxterms
Maxterms use the opposite sign rule because every literal in the selected clause must be false in the designated false row.
If
\[ p=T,\qquad q=F, \]the maxterm is
\[ \boxed{\neg p\lor q}. \]Common Error: Assuming Every DNF Is Canonical
The formula
\[ p\lor(q\land r) \]is in DNF because it is an OR of terms.
But it is not canonical with respect to \(p,q,r\), because the term \(p\) does not mention every variable.
Common Error: Assuming Canonical Means Simplest
Canonical forms are systematic, not necessarily short.
A canonical DNF may contain many minterms even when an equivalent simplified formula is much smaller.
A Reliable Procedure for Converting to NNF
- Eliminate biconditionals.
- Eliminate implications.
- Use De Morgan’s laws to move negations inward.
- Remove double negations.
- Continue until every negation applies directly to a variable.
A Reliable Procedure for Converting to DNF
- Convert the formula to negation normal form.
- Identify conjunctions containing disjunctions.
- Distribute AND over OR.
- Repeat until the formula is an OR of terms.
- Remove unnecessary parentheses where the structure remains clear.
- Optionally simplify equivalent repeated or impossible terms.
A Reliable Procedure for Converting to CNF
- Convert the formula to negation normal form.
- Identify disjunctions containing conjunctions.
- Distribute OR over AND.
- Repeat until the formula is an AND of clauses.
- Remove unnecessary parentheses where the structure remains clear.
- Optionally simplify redundant clauses.
A Reliable Procedure for Canonical DNF from a Truth Table
- Find every row where the output is T.
- For each such row, write every variable exactly once.
- Use a positive literal for T.
- Use a negative literal for F.
- Join the literals in each row with AND.
- Join the resulting minterms with OR.
A Reliable Procedure for Canonical CNF from a Truth Table
- Find every row where the output is F.
- For each such row, write every variable exactly once.
- Use a negative literal for T.
- Use a positive literal for F.
- Join the literals in each row with OR.
- Join the resulting maxterms with AND.
Example: Full Symbolic Conversion to CNF
Convert
\[ p\to(q\land r) \]to CNF.
Eliminate implication:
\[ \neg p\lor(q\land r). \]Distribute OR over AND:
\[ (\neg p\lor q)\land(\neg p\lor r). \]Therefore,
\[ \boxed{ p\to(q\land r) \equiv (\neg p\lor q)\land(\neg p\lor r) }. \]Example: Full Symbolic Conversion to DNF
Convert
\[ p\land(q\lor r) \]to DNF.
Distribute AND over OR:
\[ (p\land q)\lor(p\land r). \]Therefore,
\[ \boxed{ p\land(q\lor r) \equiv (p\land q)\lor(p\land r) }. \]Example: Negation, Implication, and CNF
Convert
\[ \neg(p\to q)\lor r \]to CNF.
First,
\[ \neg(p\to q)\equiv p\land\neg q. \]So the formula becomes
\[ (p\land\neg q)\lor r. \]Distribute OR over AND:
\[ (p\lor r)\land(\neg q\lor r). \]Thus,
\[ \boxed{ \neg(p\to q)\lor r \equiv (p\lor r)\land(\neg q\lor r) }. \]Practice 1: Identify the Form
Is
\[ (p\land q)\lor(\neg p\land r) \]in CNF, DNF, or neither?
Practice 2: Identify the Form
Is
\[ (p\lor q)\land(\neg p\lor r) \]in CNF, DNF, or neither?
Practice 3: Convert to NNF
Rewrite
\[ \neg(p\lor q) \]in negation normal form.
Practice 4: Convert to DNF
Convert
\[ p\land(q\lor r) \]to DNF.
Practice 5: Convert to CNF
Convert
\[ p\lor(q\land r) \]to CNF.
Practice 6: Remove Implication
Rewrite
\[ p\to q \]using only NOT and OR.
Practice 7: Build a Minterm
Write the minterm corresponding to
\[ p=T,\qquad q=F,\qquad r=T. \]Practice 8: Build a Maxterm
Write the maxterm that is false under
\[ p=T,\qquad q=F,\qquad r=T. \]Practice 9: Canonical DNF
A two-variable function is true only for
\[ (p,q)=(T,T) \]and
\[ (p,q)=(F,T). \]Write its canonical DNF.
Practice 10: Canonical CNF
A two-variable function is false only for
\[ (p,q)=(T,F). \]Write its canonical CNF.
Practice Answers
Practice 1
The expression is an OR of AND-terms.
\[ \boxed{\text{DNF}}. \]Practice 2
The expression is an AND of OR-clauses.
\[ \boxed{\text{CNF}}. \]Practice 3
\[ \boxed{\neg p\land\neg q}. \]Practice 4
\[ \boxed{(p\land q)\lor(p\land r)}. \]Practice 5
\[ \boxed{(p\lor q)\land(p\lor r)}. \]Practice 6
\[ \boxed{\neg p\lor q}. \]Practice 7
\[ \boxed{p\land\neg q\land r}. \]Practice 8
\[ \boxed{\neg p\lor q\lor\neg r}. \]Practice 9
The row \((T,T)\) gives
\[ p\land q. \]The row \((F,T)\) gives
\[ \neg p\land q. \]Therefore,
\[ \boxed{ (p\land q)\lor(\neg p\land q) }. \]Practice 10
For the false row
\[ p=T,\qquad q=F, \]the required maxterm is
\[ \boxed{\neg p\lor q}. \]Because this is the only false row, that one maxterm is the canonical CNF.
What to Remember
- A literal is a variable or its negation.
- A term is a conjunction of literals.
- A clause is a disjunction of literals.
- DNF is an OR of AND-terms.
- CNF is an AND of OR-clauses.
- NNF uses only AND, OR, and negations directly on variables.
- Implications and biconditionals are normally removed before normalization.
- Canonical DNF is built from minterms corresponding to true rows.
- Canonical CNF is built from maxterms corresponding to false rows.
- Normal form standardizes structure but does not necessarily minimize length.
The central habit is to separate the task into stages: remove higher-level connectives, move negations to literal level, and then distribute until the required outer structure appears.
Where We Go Next
Normal forms organize logical expressions into standard structures. The next lesson develops the algebraic laws that govern these structures and provides a systematic framework for manipulating Boolean expressions.
The next lesson, Boolean Algebra, studies Boolean identities, algebraic manipulation, duality, simplification, and structural reasoning over two-valued systems.