← 2015 Paper 2

UPSC 2015 Maths Optional Paper 2 Q5c — Step-by-Step Solution

10 marks · Section B

Boolean algebra · Numerical Analysis · asked 15× in 14 yrs · Read the full method →

Question

Find the principal (or canonical) disjunctive normal form in three variables $p,q,r$ for the Boolean expression $((p\wedge q)\to r)\vee((p\wedge q)\to\neg r)$. Is the given Boolean expression a contradiction or a tautology?

Technique

Reduce $(A\to r)\vee(A\to\neg r)=\neg A\vee r\vee\neg r=\text{True}$ symbolically; principal DNF of a tautology is the disjunction of all minterms.

Solution

Recall. $a\to b\equiv\neg a\vee b$. The expression has 3 variables $p,q,r$ giving $2^3=8$ rows.

Step 1 — Simplify symbolically

Let $A=p\wedge q$. Then expression $=(A\to r)\vee(A\to\neg r)=(\neg A\vee r)\vee(\neg A\vee\neg r)=\neg A\vee r\vee\neg r=\neg A\vee\text{True}=\text{True}$.

So the expression is a tautology (true for all 8 valuations).

Step 2 — Principal DNF

A tautology’s principal DNF (canonical sum-of-products with all variables) is the disjunction of all $2^3=8$ minterms.

Minterms (one per row of the truth table):

Step 3 — Principal DNF (full sum)

Answer