Converting to CNF and DNF

Welcome back! In our previous lesson, we established the foundations of propositional logic, learning how to evaluate formulas using truth tables. We saw that while truth tables are definitive, they become incredibly cumbersome as the number of variables grows. For your GATE preparation, speed and efficiency are paramount.

This lesson addresses that challenge directly. We will explore a more powerful, algebraic approach to logic. Our goal is to master the conversion of any propositional formula into two standard formats: Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF). This is achieved by systematically applying a set of rules called logical equivalences. Understanding these forms is not just crucial for scoring well on logic questions but also underpins many areas in computer science, from database query optimization to the design of AI systems.

1. The Power of Logical Equivalence

In the last lesson, we proved that $P \to Q$ has the same truth table as $\neg P \lor Q$ . When two formulas have identical truth tables, we say they are logically equivalent, denoted by the symbol $\equiv$ . Manipulating formulas using these equivalences allows us to simplify and standardize them without constructing a single truth table.

These equivalences are often called the Laws of Logic. Your B.Tech in Information Technology likely introduced you to their counterparts in Boolean algebra for digital circuit design. The principles are the same. Below is a table of the most important laws you must know for GATE. Pay special attention to the Distributive and De Morgan's laws, as they are the primary tools for our conversions.

Law Name	Conjunction ( $\land$ ) Form	Disjunction ( $\lor$ ) Form
Identity	$P \land T \equiv P$	$P \lor F \equiv P$
Domination	$P \land F \equiv F$	$P \lor T \equiv T$
Idempotent	$P \land P \equiv P$	$P \lor P \equiv P$
Double Negation	$\neg (\neg P) \equiv P$
Commutative	$P \land Q \equiv Q \land P$	$P \lor Q \equiv Q \lor P$
Associative	$(P \land Q) \land R \equiv P \land (Q \land R)$	$(P \lor Q) \lor R \equiv P \lor (Q \lor R)$
Distributive	$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$	$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$
De Morgan's	$\neg (P \land Q) \equiv \neg P \lor \neg Q$	$\neg (P \lor Q) \equiv \neg P \land \neg Q$
Negation	$P \land \neg P \equiv F$ (Contradiction)	$P \lor \neg P \equiv T$ (Tautology)
Absorption	$P \land (P \lor Q) \equiv P$	$P \lor (P \land Q) \equiv P$

2. Disjunctive Normal Form (DNF)

A formula is in Disjunctive Normal Form (DNF) if it is a disjunction (sum) of one or more conjunctions (products) of literals. A literal is simply a variable or its negation (e.g., $P$ or $\neg Q$ ). Think of DNF as a "sum of products," a structure familiar from digital logic's Sum-of-Products (SOP) form.

For example, the formula $(P \land \neg Q) \lor (\neg P \land R) \lor (S)$ is in DNF.

To convert any formula to DNF, we follow a three-step procedure. This video explains the concept and the procedure clearly.

Disjunctive Normal Form || DNF|| 7 Solved Examples || Procedure to obtain DNF ||What is || DMS |MFCS

This video by Sudhakar Atchala introduces DNF and systematically lays out the conversion process.

First, watch the definition of DNF, which he calls "sum of elementary products," from the beginning. Then, focus on the three-step procedure he outlines.

The procedure to obtain DNF is as follows:

Eliminate Conditionals: Remove all instances of $\to$ and $\leftrightarrow$ using their equivalences:
- $P \to Q \equiv \neg P \lor Q$
- $P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P) \equiv (\neg P \lor Q) \land (\neg Q \lor P)$
Apply De Morgan's Law: Use De Morgan's laws repeatedly to push all negation ( $\neg$ ) symbols inward until they apply only to individual propositional variables. You should also use the double negation law ( $\neg (\neg P) \equiv P$ ) to simplify.
Apply Distributive Law: Repeatedly apply the distributive law $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$ to distribute all $\land$ connectives over $\lor$ connectives. The final result will be a disjunction of conjunctions.

Let's see this in action. We'll convert $P \to (Q \land R)$ to DNF.

Eliminate $\to$ : $P \to (Q \land R) \equiv \neg P \lor (Q \land R)$
Apply De Morgan's Law: There are no negations to push inward. This step is done.
Apply Distributive Law: The formula is already in the form $A \lor B$ , where $A$ is $\neg P$ and $B$ is $(Q \land R)$ . Both $A$ and $B$ are conjunctions of literals (or single literals, which can be seen as a conjunction of one). So, the formula is already in DNF. The result is $\neg P \lor (Q \land R)$ .

Now, for a more complex example, let's watch one from the video.

Disjunctive Normal Form || DNF|| 7 Solved Examples || Procedure to obtain DNF ||What is || DMS |MFCS

This example demonstrates the process on a more involved formula, requiring multiple steps of distribution.

Watch the fourth example, the conversion of (P → Q) ∧ (Q → R) to DNF. Observe how the distributive law is applied multiple times to achieve the final form.

3. Conjunctive Normal Form (CNF)

Dually, a formula is in Conjunctive Normal Form (CNF) if it is a conjunction (product) of one or more disjunctions (sums) of literals. This is the "product of sums" (POS) form from digital logic.

For example, the formula $(P \lor \neg Q) \land (\neg P \lor R) \land (S)$ is in CNF.

The procedure to obtain CNF is very similar to that for DNF, with one key difference in the final step.

Eliminate Conditionals: Same as for DNF.
Apply De Morgan's Law: Same as for DNF.
Apply Distributive Law: Repeatedly apply the distributive law $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ to distribute all $\lor$ connectives over $\land$ connectives. The final result will be a conjunction of disjunctions.

Let's convert $\neg (P \to Q)$ to both CNF and DNF to see the difference.

Step 1 & 2 (Eliminate & Push Negation): $\neg (P \to Q) \equiv \neg (\neg P \lor Q) \equiv \neg (\neg P) \land \neg Q \equiv P \land \neg Q$
Final Form:
- DNF: The formula $P \land \neg Q$ is a conjunction of literals. It can be seen as a disjunction of one term. So, it is already in DNF.
- CNF: The formula $P \land \neg Q$ is a conjunction of literals. A literal is a disjunction of one term. So, this is also already in CNF.

This was a simple case. For a more complex conversion to CNF, let's analyze the steps in the following video. The audio is in Hindi, but the on-screen symbolic manipulation is universal and clearly demonstrates the application of the laws.

Conjunctive Normal Forms CNF with Examples - Logic - Discrete Mathematics

This video walks through a complex example of converting a formula to CNF. Focus on the logical laws being applied at each step written on the screen.

Watch the main example starting from the conversion. I will narrate the key steps for you: 01:36: The initial formula is p → (q ∧ r) ∧ (¬p → (¬q ∧ ¬r)). The first step replaces the implications (→) with their ¬ ∨ equivalents. 02:09: The formula is simplified using De Morgan's and double negation laws. 03:08: This is the critical step. The distributive law A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) is applied to distribute the outer ∨ over the inner ∧. The rest of the video involves repeated applications of the distributive law to break the expression down into the final CNF, which is a conjunction of several clauses (disjunctions).

4. Principal Normal Forms (PDNF and PCNF)

For any given formula, there can be many equivalent DNFs and CNFs. The Principal (or Canonical) Normal Forms are unique for any given formula.

Minterm: For a formula with $n$ variables, a minterm is a conjunction ( $\land$ ) that includes every one of the $n$ variables, either in its true form or negated. A minterm is true for exactly one combination of inputs. For variables P and Q, $P \land \neg Q$ is a minterm.
Principal DNF (PDNF): The PDNF of a formula is the disjunction ( $\lor$ ) of all the minterms that correspond to the rows where the formula's truth table evaluates to 'True'.
Maxterm: A maxterm is a disjunction ( $\lor$ ) that includes every one of the $n$ variables, either true or negated. A maxterm is false for exactly one combination of inputs. For P and Q, $P \lor \neg Q$ is a maxterm.
Principal CNF (PCNF): The PCNF of a formula is the conjunction ( $\land$ ) of all the maxterms that correspond to the rows where the formula's truth table evaluates to 'False'.

While you can always derive these from a truth table, you can also generate them algebraically from any DNF/CNF by using laws like $P \land T \equiv P$ and $Q \lor \neg Q \equiv T$ . For example, to convert the DNF term $(P \land Q)$ to a PDNF term over variables P, Q, R:

(P \land Q) \equiv (P \land Q) \land T \equiv (P \land Q) \land (R \lor \neg R) \equiv (P \land Q \land R) \lor (P \land Q \land \neg R)

This expansion ensures every term includes all variables, which is the defining property of the principal form.

Conclusion

In this lesson, we moved beyond the brute-force method of truth tables and into the more elegant and efficient world of algebraic manipulation. You now have the tools to standardize any propositional formula.

Key Takeaways:

Logical Equivalences are rules for rewriting formulas while preserving their truth value. De Morgan's and Distributive laws are the most critical for normalization.
Disjunctive Normal Form (DNF) is a "sum of products" (OR of ANDs).
Conjunctive Normal Form (CNF) is a "product of sums" (AND of ORs).
The conversion process is a systematic three-step procedure: eliminate conditionals, push negations inward, and then distribute.
Principal Normal Forms (PDNF/PCNF) are unique, canonical forms for any proposition, built from minterms or maxterms.

These normal forms are not just abstract concepts; they are the required input format for many algorithms, particularly automated theorem provers and SAT solvers, which are fundamental tools in both hardware and software verification.

In our next lesson, we will significantly expand our logical toolkit by moving from Propositional Logic to First-Order Logic. This will allow us to reason not just about true/false statements, but about objects, their properties (predicates), and quantities using quantifiers like "for all" ( $\forall$ ) and "there exists" ( $\exists$ ).

Recommended resources

1. The Power of Logical Equivalence

2. Disjunctive Normal Form (DNF)

3. Conjunctive Normal Form (CNF)

4. Principal Normal Forms (PDNF and PCNF)

Conclusion