Normal Forms
This chapter explains standard logical arrangements called normal forms for propositional formulae. A normal form is a formula equivalent to a given formula but written in a restricted, standard syntactic shape. Normal forms are used widely in logic, automated reasoning and digital design because they make structure explicit and simplify mechanical manipulation.
Basic concepts
- Logical equivalence: Two formulae are equivalent when they have the same truth value for every assignment of truth values to their variables.
- Atomic/elementary literal: A propositional variable (for example P) or its negation (for example ~P).
- Clause: A disjunction (sum) of literals (for example P ∨ ~Q ∨ R).
- Term: A conjunction (product) of literals (for example P ∧ ~Q ∧ R).
- Canonical forms: Forms that use every variable in every clause or term in a fixed way (see PDNF and PCNF below).
Disjunctive Normal Form (DNF)
Definition: A formula is in disjunctive normal form (DNF) if it is a disjunction (logical OR) of one or more terms, where each term is a conjunction (logical AND) of one or more literals. Each term is often called an elementary product or simply a product. A DNF equivalent to a given formula is called a DNF of that formula.
- Example: (P ∧ ~Q) ∨ (Q ∧ R) ∨ (~P ∧ Q ∧ ~R)
- The DNF of a formula is not unique: different algebraic rearrangements or different sets of terms may represent the same truth function.
How to obtain a DNF from a truth table
- List all rows of the truth table where the formula is true (value T).
- For each such row, form a minterm (a conjunction) that contains each variable either as itself if the variable is T on that row, or as its negation if the variable is F on that row.
- Take the disjunction of all these minterms. The result is the canonical DNF (PDNF) of the formula.
Principal Disjunctive Normal Form (PDNF)
Definition: The principal disjunctive normal form (PDNF), also called the sum-of-products canonical form, is a DNF expressed as the disjunction of all minterms that make the original formula true. Each minterm contains every propositional variable exactly once, either negated or unnegated.
- Example: (P ∧ ~Q ∧ ~R) ∨ (P ∧ ~Q ∧ R) ∨ (~P ∧ ~Q ∧ ~R)
- The minterm consists of conjunctions in which each variable or its negation appears exactly once.
- Minterms are written by including the variable if its truth value is T and its negation if its truth value is F in that row of the truth table.
Conjunctive Normal Form (CNF)
Definition: A formula is in conjunctive normal form (CNF) if it is a conjunction (logical AND) of one or more clauses, where each clause is a disjunction (logical OR) of one or more literals. A CNF equivalent to a given formula is called a CNF of that formula.
- Example: (~P ∨ Q) ∧ (Q ∨ R) ∧ (~P ∨ Q ∨ ~R)
- The CNF of a formula is not unique.
- If every clause (elementary sum) in a CNF is a tautology (always true), then the whole CNF is a tautology and thus the given formula is a tautology.
How to obtain a CNF
- Use logical equivalences (for example, eliminate implications, push negations inside using De Morgan's laws, and use distributive laws) to transform the formula into a conjunction of disjunctions.
- Alternatively, construct the principal conjunctive normal form (PCNF) from the truth table by forming maxterms for rows where the formula is false and conjuncting them (see next section).
Principal Conjunctive Normal Form (PCNF)
Definition: The principal conjunctive normal form (PCNF), also called the product-of-sums canonical form, is a CNF expressed as the conjunction of all maxterms that make the original formula false. Each maxterm contains every propositional variable exactly once, either negated or unnegated.
- Example: (P ∨ ~Q ∨ ~R) ∧ (P ∨ ~Q ∨ R) ∧ (~P ∨ ~Q ∨ ~R)
- A maxterm is a disjunction in which each variable or its negation appears exactly once.
- The dual of a minterm is a maxterm.
- Each maxterm has truth value F for exactly one combination of the variables; it is written by including the variable if its truth value is F and its negation if its truth value is T for that specific row.
How to obtain the PCNF from a truth table - worked example
Suppose a formula of variables P, Q, R is false on exactly those rows with assignments: (P=T, Q=T, R=F) and (P=F, Q=T, R=T). Construct the PCNF.
Sol.
Form the maxterm for the row (P=T, Q=T, R=F).
(~P ∨ ~Q ∨ R)
Form the maxterm for the row (P=F, Q=T, R=T).
(P ∨ ~Q ∨ ~R)
Take the conjunction of these maxterms.
(~P ∨ ~Q ∨ R) ∧ (P ∨ ~Q ∨ ~R)
Minterms and Maxterms - precise definitions
- Minterm: A conjunctive term in which each variable of the function appears exactly once, either unnegated or negated. A minterm evaluates to true for precisely one assignment of the variables (the assignment that matches the literal choices).
- Maxterm: A disjunctive clause in which each variable appears exactly once, either unnegated or negated. A maxterm evaluates to false for precisely one assignment - the one that makes every literal in the clause false.
- There are 2^n distinct minterms (and 2^n distinct maxterms) for n variables. The PDNF is the disjunction of those minterms corresponding to true rows of the function. The PCNF is the conjunction of those maxterms corresponding to false rows of the function.
Conversions and algebraic methods
- To convert an arbitrary formula to CNF or DNF, begin by eliminating implication and biconditional connectives, then push negations inward using De Morgan's laws so that negation applies only to variables, and finally apply distributive laws as needed to reach the required shape.
- Distributive laws used are:
- A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
- A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
- Using these repeatedly transforms between forms, but repeated distribution can cause exponential growth in size; canonical PDNF/PCNF may be large for many variables.
- De Morgan's laws:
- ~(A ∧ B) ≡ (~A ∨ ~B)
- ~(A ∨ B) ≡ (~A ∧ ~B)
Properties and observations
- Uniqueness (canonical forms): PDNF and PCNF for a given function are unique up to the order of terms/clauses and the order of literals inside them.
- Non-uniqueness (general DNF/CNF): General DNF or CNF are not unique; simplification rules (absorption, idempotence, consensus) can produce many equivalent but different forms.
- Duality: Taking negation and swapping ∧ with ∨ converts PDNF of a function to PCNF of its negation, and vice versa.
- Tautology and contradiction tests: A formula is a tautology if its PDNF contains all minterms (i.e., is the disjunction of all 2^n minterms). A formula is a contradiction if its PCNF contains all maxterms (i.e., is the conjunction of all 2^n maxterms) or equivalently its PDNF is empty (no true rows).
Applications in Computer Science and Engineering
- Digital logic design: Sum-of-products (DNF) corresponds directly to two-level logic circuits implemented with AND gates feeding an OR gate; product-of-sums (CNF) corresponds to OR gates feeding an AND gate.
- SAT solving: Many satisfiability solvers expect input in CNF. Converting propositional formulae to CNF is therefore a standard preprocessing step for automated reasoning.
- Simplification and minimisation: Boolean simplification techniques (Karnaugh maps, Quine-McCluskey) start from canonical forms and reduce them to compact DNFs or CNFs that implement the same function with fewer gates or terms.
- Compiler and program analysis: Logical normal forms are used in optimisations and in encoding conditions for symbolic reasoning.
Worked example: Construct PDNF from a truth table
Consider a Boolean function f(P,Q,R) that is true exactly on the rows with assignments (P=1,Q=0,R=0), (P=1,Q=0,R=1) and (P=0,Q=0,R=0). Construct the PDNF.
Sol.
Form the minterm for (P=1,Q=0,R=0):
P ∧ ~Q ∧ ~R
Form the minterm for (P=1,Q=0,R=1):
P ∧ ~Q ∧ R
Form the minterm for (P=0,Q=0,R=0):
~P ∧ ~Q ∧ ~R
Disjoin the minterms to obtain the PDNF:
(P ∧ ~Q ∧ ~R) ∨ (P ∧ ~Q ∧ R) ∨ (~P ∧ ~Q ∧ ~R)
Simplification remarks and common identities
- Absorption: A ∨ (A ∧ B) ≡ A and A ∧ (A ∨ B) ≡ A. These reduce redundant terms.
- Idempotence: A ∨ A ≡ A and A ∧ A ≡ A.
- Consensus (resolution): (A ∧ B) ∨ (~A ∧ C) ∨ (B ∧ C) ≡ (A ∧ B) ∨ (~A ∧ C).
- Apply these identities to reduce DNF or CNF obtained mechanically from canonical forms to more compact, human-friendly expressions.
Concluding notes
- Normal forms make logical structure explicit and are foundational both for theoretical logic and practical applications in computing.
- PDNF and PCNF are canonical and unique up to order; ordinary DNF and CNF are not unique but are often easier to work with after simplification.
- When converting formulae, always first eliminate implications and biconditionals and push negations inward; then use distributive laws carefully to avoid excessive expansion.
