6.2 Implications: Converse, Inverse, Contrapositive & Normal Forms (CNF/DNF)

Back to Discrete Mathematics Notes

📚Module 06: Propositional Logic & Inference RulesTopic 6.2: Implications: Converse, Inverse, Contrapositive & Normal Forms⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Driver's Licenses & Standardized Data Formats

Think of logical dependencies and canonical file serialization:

1. The 4 Faces of an Implication:
   • Original (Direct): "If you are in Paris ($p$), then you are in France ($q$)." (True).
   • Converse: "If you are in France ($q$), then you are in Paris ($p$)." (False! You could be in Nice or Lyon).
   • Inverse: "If you are not in Paris ($\neg p$), then you are not in France ($\neg q$)." (False! You could be in Marseille).
   • Contrapositive: "If you are not in France ($\neg q$), then you are not in Paris ($\neg p$)." (100% True! If you aren't in France, you cannot possibly be in Paris). Notice the golden law: An implication and its contrapositive always tell the exact same mathematical truth!
2. Normal Forms (CNF & DNF): Just as a database normalizes raw messy data into strict relational schemas, or a compiler converts source code into Intermediate Representation (IR), CNF (AND-of-ORs) and DNF (OR-of-ANDs) normalize arbitrary logic trees into standardized flat structures that SAT solvers can process in microsecond machine loops.

💻 Bridging to Computer Science: Proof by Contraposition & Automated Theorem Proving

In computer engineering:

• Proof by Contraposition: In algorithm analysis and complexity theory, proving $p \to q$ directly is often difficult. Proving the contrapositive $\neg q \to \neg p$ is mathematically identical and often straightforward.
• Automated Theorem Proving (SAT & SMT Solvers): Algorithms like DPLL (Davis-Putnam-Logemann-Loveland) and CDCL (Conflict-Driven Clause Learning) require propositional input strictly in Conjunctive Normal Form (CNF).
• Relational Query Optimizers: SQL engines convert complex nested WHERE filters into CNF clauses to prune database index scans.

📑Table of Contents

• 🔄 The Four Conditional Statements & Equivalence Square
  • Master Truth Table of Conditional Variations
• 🗣️ Master English Translation Dictionary for Implications
  • Master 10-Pattern English Translation Table
• 🪞 The Principle of Duality
• 📦 Canonical Normal Forms: CNF & DNF
• 📝 Step-by-Step Worked Examples
  • Example 1: Finding the Converse, Inverse & Contrapositive
  • Example 2: Converting a Formula to Conjunctive Normal Form (CNF)
  • Example 3: Extracting Canonical DNF & CNF from a Truth Table
• 🎯 Exam & Interview Pitfall Check

---

🔄 The Four Conditional Statements & Equivalence Square

Given a direct conditional implication $p \to q$, we can generate three related propositions:

📖Definition 6.4: Direct, Converse, Inverse & Contrapositivedefinition

Let $p$ be the antecedent (hypothesis) and $q$ be the consequent (conclusion):

1. Direct Implication: $$p \to q \quad (\text{If } p, \text{ then } q) \equiv \neg p \lor q$$
2. Converse: $$q \to p \quad (\text{If } q, \text{ then } p) \equiv \neg q \lor p$$
3. Inverse: $$\neg p \to \neg q \quad (\text{If not } p, \text{ then not } q) \equiv \neg(\neg p) \lor \neg q \equiv p \lor \neg q$$
4. Contrapositive: $$\neg q \to \neg p \quad (\text{If not } q, \text{ then not } p) \equiv \neg(\neg q) \lor \neg p \equiv q \lor \neg p \equiv \neg p \lor q$$

✓ Equivalence Pairs

Equivalences: Direct ≡ Contrapositive, and Converse ≡ Inverse.

The 4 Conditional Variations: The Two Independent Invariant Pairs

Proving which reflections share identical truth tables under all valuations

Invariant Pair 1

Direct & Contrapositive: p → q ≡ ¬q → ¬p

🎯

Dominant Architecture / DomainGuaranteed Logical Equivalence

• •Direct Implication: p → q (If p, then q).
• •Contrapositive: ¬q → ¬p (If not q, then not p).
• •Fundamental Invariant: They have IDENTICAL truth tables under all valuations!

"Denied consequence forces denied premise."

Invariant Pair 2

Converse & Inverse: q → p ≡ ¬p → ¬q

🔄

Dominant Architecture / DomainGuaranteed Logical Equivalence

• •Converse: q → p (If q, then p).
• •Inverse: ¬p → ¬q (If not p, then not q).
• •Transposed Truth: The Converse is identical to the Inverse of the original implication!

"Swapping direction creates an independent truth pair."

Master Truth Table of Conditional Variations

$p$	$q$	Direct ($p \to q$)	Converse ($q \to p$)	Inverse ($\neg p \to \neg q$)	Contrapositive ($\neg q \to \neg p$)
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$T$

Notice:

• Columns 3 and 6 are identical: $p \to q \equiv \neg q \to \neg p$.
• Columns 4 and 5 are identical: $q \to p \equiv \neg p \to \neg q$.
• $p \to q \not\equiv q \to p$ (An implication is never equivalent to its converse in general!).

---

🗣️ Master English Translation Dictionary for Implications

Mathematical implications appear in numerous natural language phrasings. In competitive exams (GATE), converting English specifications into symbolic logic is heavily tested.

Deciphering English Phrasing of p → q

Standardized translations mapping natural language constructs to antecedent p and consequent q

➡️

Direct Phrasing (p → q)

Standard Order

• 'If p, then q'
• 'p implies q'
• 'p is sufficient for q' (p guarantees q)
• 'p leads to q'

⬅️

Inverted Phrasing (p → q)

Target Listed First

• 'q if p'
• 'q whenever p'
• 'q is necessary for p' (Without q, p cannot happen: ¬q → ¬p)
• 'q follows from p'

⚠️

The 'Only If' Rule (p → q)

Frequent Trap

• 'p only if q' translates strictly to p → q!
• Contrast: 'p if q' translates to q → p.
• Rule of Thumb: The clause immediately following 'if' is ALWAYS the antecedent.

🚫

The 'Unless' Rule (¬q → p)

Conditional Disjunction

• 'p unless q' means 'If not q, then p' (¬q → p).
• By Implication Law: ¬(¬q) ∨ p ≡ q ∨ p.
• Example: 'You will fail unless you study' ≡ ¬(Study) → Fail.

Master 10-Pattern English Translation Table

English Pattern	Antecedent (Hypothesis)	Consequent (Conclusion)	Symbolic Translation	Common Student Misconception
"If $p$, then $q$"	$p$	$q$	$p \to q$	Standard forward conditional
"$p$ implies $q$"	$p$	$q$	$p \to q$	Standard forward conditional
"$q$ if $p$"	$p$	$q$	$p \to q$	Mistakenly writing $q \to p$ because $q$ comes first
"$p$ only if $q$"	$p$	$q$	$p \to q$	Confusing with "if"; writing $q \to p$ (Fatal error!)
"$p$ is sufficient for $q$"	$p$	$q$	$p \to q$	Having $p$ is enough to guarantee $q$
"$q$ is necessary for $p$"	$p$	$q$	$p \to q$	If $q$ does not hold, $p$ cannot hold ($\neg q \to \neg p$)
"$q$ whenever $p$"	$p$	$q$	$p \to q$	Every time $p$ occurs, $q$ must accompany it
"$q$ follows from $p$"	$p$	$q$	$p \to q$	$p$ is the origin / premise of $q$
"$q$ unless $\neg p$"	$p$	$q$	$p \to q$	"Unless" means "if not": $\neg(\neg p) \to q \equiv p \to q$
"$p$ is necessary and sufficient for $q$"	Both	Both	$p \leftrightarrow q$	Biconditional: $(p \to q) \land (q \to p)$

---

🪞 The Principle of Duality

📖Definition 6.5: Dual of a Compound Propositiondefinition

Let $A$ be a compound proposition containing only the connectives $\land, \lor$ and negation $\neg$. The dual of $A$ (denoted $A^*$) is obtained by:

1. Replacing every occurrence of $\land$ with $\lor$.
2. Replacing every occurrence of $\lor$ with $\land$.
3. Replacing every occurrence of $\mathbf{T}$ with $\mathbf{F}$, and $\mathbf{F}$ with $\mathbf{T}$.
4. Leaving all propositional variables and negations ($\neg$) completely unchanged!

• Example:
  • Original: $A = (p \lor \neg q) \land (r \lor \mathbf{F})$
  • Dual: $A^* = (p \land \neg q) \lor (r \land \mathbf{T})$

📐Theorem 6.3: Duality Theoremtheorem

If two compound propositions are logically equivalent:

$$A \equiv B$$

Then their duals are also guaranteed to be logically equivalent:

$$A^* \equiv B^*$$

Caution: The dual $A^*$ is NOT the negation $\neg A$! For instance:

• If $A = p \lor q$, the dual is $A^* = p \land q$.
• The negation is $\neg A = \neg(p \lor q) \equiv \neg p \land \neg q$.

---

📦 Canonical Normal Forms: CNF & DNF

In automated theorem proving, circuit design, and SAT solvers, arbitrary nested logical formulas must be transformed into standard canonical structures.

📖Definition 6.6: Literals, Minterms, Maxterms & Normal Formsdefinition

1. Literal: A propositional variable $p$ (positive literal) or its negation $\neg p$ (negative literal).
2. Conjunctive Normal Form (CNF): A formula is in CNF if it is a Conjunction of one or more Disjunctive Clauses: $$\text{CNF} = \bigwedge_{i=1}^{m} \left( \bigvee_{j=1}^{k_i} l_{i,j} \right) = (l_{1,1} \lor l_{1,2} \lor \dots) \land (l_{2,1} \lor l_{2,2} \lor \dots) \land \dots$$ (Product of Sums: Clauses connected by AND; literals inside connected by OR).
3. Disjunctive Normal Form (DNF): A formula is in DNF if it is a Disjunction of one or more Conjunctive Clauses: $$\text{DNF} = \bigvee_{i=1}^{m} \left( \bigwedge_{j=1}^{k_i} l_{i,j} \right) = (l_{1,1} \land l_{1,2} \land \dots) \lor (l_{2,1} \land l_{2,2} \land \dots) \lor \dots$$ (Sum of Products: Clauses connected by OR; literals inside connected by AND).
4. Canonical Minterm ($m_i$): A conjunction of $n$ literals containing every variable exactly once, evaluating to $T$ for exactly one row in the truth table.
5. Canonical Maxterm ($M_i$): A disjunction of $n$ literals containing every variable exactly once, evaluating to $F$ for exactly one row in the truth table. $$M_i \equiv \neg m_i$$

Architecture Flow

The 4-Step Normal Form Transformation Pipeline

Universal algebraic rewriting algorithm to convert any formula to CNF or DNF

✂️Step 1

Eliminate Conditionals

Replace p ↔ q with (p → q) ∧ (q → p). Replace a → b with ¬a ∨ b.

→

All → and ↔ Removed

📥Step 2

Push Negations Inward (NNF)

Apply De Morgan's laws ¬(a ∧ b) ≡ ¬a ∨ ¬b and ¬(a ∨ b) ≡ ¬a ∧ ¬b. Eliminate double negations ¬¬a ≡ a.

→

Negation Normal Form Reached

🔄Step 3

Distribute Operators

For CNF: Distribute ∨ over ∧ (a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)). For DNF: Distribute ∧ over ∨.

→

Flattened to 2 Levels

🧹Step 4

Simplify & Prune

Apply idempotent laws (p ∨ p ≡ p) and remove trivial clauses (p ∨ ¬p ≡ T in CNF).

---

📝 Step-by-Step Worked Examples

Example 1: Finding the Converse, Inverse & Contrapositive

Problem Statement: Consider the statement: "If a function is differentiable, then it is continuous." Let $p$: "A function is differentiable", and $q$: "A function is continuous."

1. Express the original statement symbolically.
2. State the Converse, Inverse, and Contrapositive in English and symbolic notation.
3. Determine the truth value of each statement.

Step-by-Step Solution:

1. Original Statement:

   • Symbolic: $p \to q$
   • Truth Value: True (Fundamental theorem of calculus).

2. The Three Variations:

   • Converse ($q \to p$):
     • English: "If a function is continuous, then it is differentiable."
     • Truth Value: False! (Counterexample: $f(x) = \vert x\vert$ at $x = 0$ is continuous, but not differentiable).
   • Inverse ($\neg p \to \neg q$):
     • English: "If a function is not differentiable, then it is not continuous."
     • Truth Value: False! (Counterexample: $f(x) = \vert x\vert$ is not differentiable at 0, yet it is continuous).
   • Contrapositive ($\neg q \to \neg p$):
     • English: "If a function is not continuous, then it is not differentiable."
     • Truth Value: True! (Logically equivalent to the original statement: $p \to q \equiv \neg q \to \neg p$).

Key Takeaway: Never confuse the converse with the contrapositive: the contrapositive is guaranteed to share the truth value of the original theorem, while the converse is an independent statement.

---

Example 2: Converting a Formula to Conjunctive Normal Form (CNF)

Problem Statement: Convert the formula $\phi = \neg(p \to q) \lor (r \to p)$ into Conjunctive Normal Form (CNF).

Step-by-Step Solution:

1. Step 1: Eliminate all implications ($\to$)

   • Replace $p \to q$ with $(\neg p \lor q)$: $$\phi = \neg(\neg p \lor q) \lor (\neg r \lor p)$$

2. Step 2: Push negations inward using De Morgan's Law

   • Apply De Morgan to $\neg(\neg p \lor q)$: $$\neg(\neg p \lor q) \equiv (\neg\neg p \land \neg q) \equiv (p \land \neg q)$$
   • The expression becomes: $$\phi = (p \land \neg q) \lor (\neg r \lor p)$$

3. Step 3: Distribute $\lor$ over $\land$ to achieve CNF

   • Let $K = (\neg r \lor p)$. We distribute $K$ over $(p \land \neg q)$: $$(p \land \neg q) \lor K \equiv (p \lor K) \land (\neg q \lor K)$$
   • Substitute $K = (\neg r \lor p)$ back into both clauses: $$\text{Clause 1} = p \lor (\neg r \lor p) \equiv (p \lor p \lor \neg r) \equiv (p \lor \neg r)$$ $$\text{Clause 2} = \neg q \lor (\neg r \lor p) \equiv (p \lor \neg q \lor \neg r)$$

4. Step 4: Combine into final CNF

   $$\phi \equiv (p \lor \neg r) \land (p \lor \neg q \lor \neg r)$$
   • Notice that $(p \lor \neg r)$ absorbs $(p \lor \neg r \lor \neg q)$ by the Absorption Law: $$(p \lor \neg r) \land ((p \lor \neg r) \lor \neg q) \equiv (p \lor \neg r)$$
   • Minimal CNF: $(p \lor \neg r)$.

---

Example 3: Extracting Canonical DNF & CNF from a Truth Table

Problem Statement: Given the function $F(p, q, r)$ with truth table minterm list $\sum m(1, 3, 5, 7)$ (which corresponds to $F = r$):

1. Write the Canonical DNF (Sum of Minterms).
2. Write the Canonical CNF (Product of Maxterms).

Step-by-Step Solution:

1. Canonical DNF ($\sum m$):
   • The function is True for rows $1, 3, 5, 7$:
     • Row 1 ($001$): $\neg p \land \neg q \land r$
     • Row 3 ($011$): $\neg p \land q \land r$
     • Row 5 ($101$): $p \land \neg q \land r$
     • Row 7 ($111$): $p \land q \land r$
   • Canonical DNF: $$F = (\neg p \land \neg q \land r) \lor (\neg p \land q \land r) \lor (p \land \neg q \land r) \lor (p \land q \land r)$$
2. Canonical CNF ($\prod M$):
   • The function is False for rows $0, 2, 4, 6$:
     • Row 0 ($000$): $p \lor q \lor r$
     • Row 2 ($010$): $p \lor \neg q \lor r$
     • Row 4 ($100$): $\neg p \lor q \lor r$
     • Row 6 ($110$): $\neg p \lor \neg q \lor r$
   • Canonical CNF: $$F = (p \lor q \lor r) \land (p \lor \neg q \lor r) \land (\neg p \lor q \lor r) \land (\neg p \lor \neg q \lor r)$$

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: How does "p only if q" differ from "p if q"? Key Focus Points:

• "p only if q" means that $q$ is a necessary condition for $p$. If $q$ does not happen, $p$ cannot happen ($\neg q \to \neg p \equiv p \to q$).
• "p if q" means that $q$ is the hypothesis, which translates to $q \to p$.
• They are converses of each other! When both hold simultaneously, we write "$p$ if and only if $q$" ($p \leftrightarrow q$).

Question 2: Can a formula have multiple valid CNF representations? Key Focus Points: Yes! Conjunctive Normal Form is not unique unless canonical maxterms are enforced. For example, $(p \lor q) \land (p \lor \neg q)$ and $p$ are both valid CNFs representing the same boolean function.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Translating "p unless q" as p ∧ ¬q Why it fails: "Unless" introduces an exception, which acts as a conditional disjunction: "I will go for a walk unless it rains" means "If it does NOT rain, I will go for a walk" ($\neg q \to p \equiv p \lor q$). Translating it as a conjunction ($p \land \neg q$) is completely incorrect!

Trap 2: Exponential blowup when converting DNF to CNF Why it fails: Direct algebraic distribution of $k$ DNF clauses of size $m$ into CNF generates $m^k$ clauses (exponential size explosion). Real-world SAT solvers use the Tseitin Transformation, which introduces auxiliary variables to convert any formula to an equisatisfiable 3-CNF in linear time $O(n)$!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic6.1 Propositions, Connectives, Truth Tables & Logical EquivalencesNext Topic →6.3 Rules of Inference, Validity Proofs & Resolution Refutation