Normal Forms

Definition

A normal form in propositional logic is a logically equivalent representation of a propositional formula written in a standardized structural pattern.

The most common normal forms are:

Disjunctive Normal Form (DNF)

• a disjunction (OR) of conjunctions (ANDs) of literals.

Conjunctive Normal Form (CNF)

• a conjunction (AND) of disjunctions (ORs) of literals.

Where a literal is either a propositional variable or its negation, such as P or ¬P.

Example:

• DNF: (P ∧ ¬Q) ∨ (R ∧ S)
• CNF: (P ∨ ¬Q) ∧ (R ∨ S)

Main Content

1. Disjunctive Normal Form and Conjunctive Normal Form

Disjunctive Normal Form (DNF)

• A formula is in DNF when it is written as an OR of one or more AND-terms.
• Each AND-term contains only literals.
• Example: (P ∧ Q) ∨ (¬R ∧ S) ∨ T
• This form is often interpreted as listing the conditions under which the formula is true.

Conjunctive Normal Form (CNF)

• A formula is in CNF when it is written as an AND of one or more OR-clauses.
• Each OR-clause contains only literals.
• Example: (P ∨ Q) ∧ (¬R ∨ S) ∧ (T ∨ ¬U)
• This form is often interpreted as listing the conditions that must all be satisfied.

These two forms are central because every propositional formula can be converted into an equivalent DNF or CNF using logical laws.

2. Literals, Clauses, and Terms

Literal

• A literal is the basic unit used in normal forms.
• It can be a variable such as P or the negation of a variable such as ¬P.
• No other operators should appear inside a literal.

Term and Clause

• In DNF, each AND-group is called a term or minterm-like product term.
• In CNF, each OR-group is called a clause or sum term.
• Example of a DNF term: (P ∧ ¬Q ∧ R)
• Example of a CNF clause: (P ∨ ¬Q ∨ R)

Role in simplification

• Normal forms make formulas uniform, so they can be compared, simplified, or mechanically processed.
• They are especially useful in truth-table based methods, where rows making the formula true or false can be directly converted into DNF or CNF.

3. Conversion into Normal Form

Stepwise transformation using laws of logic

• Remove implications and biconditionals:
  • P → Q becomes ¬P ∨ Q
  • P ↔ Q becomes (P → Q) ∧ (Q → P)
• Push negations inward using De Morgan’s laws:
  • ¬(P ∧ Q) becomes ¬P ∨ ¬Q
  • ¬(P ∨ Q) becomes ¬P ∧ ¬Q
• Distribute AND over OR for CNF, or OR over AND for DNF.

Truth-table method

• For DNF, list all rows where the formula is true and form a conjunction for each such row.
• Combine these conjunctions using OR.
• For CNF, list all rows where the formula is false and form a disjunction for each such row.
• Combine these disjunctions using AND.

Example

• Suppose the formula is P → Q.
• Rewrite it as ¬P ∨ Q.
• This is already in CNF because it is a single clause containing literals.

Working / Process

1. Eliminate non-basic connectives

• Replace →, ↔, and other derived connectives using only ¬, ∧, and ∨.
• Example:
  • P → Q becomes ¬P ∨ Q
  • P ↔ Q becomes (¬P ∨ Q) ∧ (¬Q ∨ P)

2. Move negations inward

• Apply De Morgan’s laws and double negation elimination.
• Keep negation only directly before variables.
• Example:
  • ¬(P ∨ Q) becomes ¬P ∧ ¬Q
  • ¬¬P becomes P

3. Use distribution to obtain the target form

• For CNF, distribute ∨ over ∧ until the formula becomes an AND of OR-clauses.
• For DNF, distribute ∧ over ∨ until the formula becomes an OR of AND-terms.
• Example for CNF:
  • P ∨ (Q ∧ R) becomes (P ∨ Q) ∧ (P ∨ R)

Advantages / Applications

Simplifies logical analysis

• Normal forms make formulas easier to inspect, compare, and verify.
• Logical equivalence can be checked more systematically when formulas are standardized.

Useful in digital logic and circuit design

• CNF and DNF correspond closely to logic gate structures.
• DNF can be implemented using AND gates feeding an OR gate.
• CNF can be implemented using OR gates feeding an AND gate.

Important in computer science and finite state machine design

• Transition conditions and state conditions are often written in normal form for implementation.
• SAT solvers typically work with CNF, making it essential in automated reasoning.
• Boolean control logic in FSMs is commonly minimized and then realized using these forms.

Summary

• Normal forms are standardized representations of propositional formulas.
• The two main types are DNF and CNF.
• Any propositional formula can be converted into an equivalent normal form.
• Normal forms are essential for logic simplification, truth tables, digital circuits, and finite state machine design.