Q23Discrete Mathematics

The Principal Disjunctive Normal Form (PDNF), often referred to as the Sum of Minterms, is a highly standardized canonical format for any Boolean logical expression. It mathematically forces the expression into a massive "OR" chain of several distinct "AND" groupings (minterms). Critically, every single minterm in a PDNF expression MUST explicitly contain every single variable present in the system, either in its normal or negated state. The most robust, error-free method to derive the PDNF is to construct an exhaustive Truth Table.

Step 1: Truth Table Construction

The proposition to evaluate is: $X=\neg (p\vee q)\leftrightarrow (p\wedge q)$. Because there are exactly two unique variables ($p$ and $q$), the truth table requires exactly $2^2=4$ rows to evaluate every possible Boolean combination.

| $p$ | $q$ | $(p\vee q)$ | $\neg (p\vee q)$ | $(p\wedge q)$ | $X=\neg (p\vee q)\leftrightarrow (p\wedge q)$ | |---|---|---|---|---|---| | T | T | T | F | T | F (False: F $\leftrightarrow$ T) | | T | F | T | F | F | T (True: F $\leftrightarrow$ F) | | F | T | T | F | F | T (True: F $\leftrightarrow$ F) | | F | F | F | T | F | F (False: T $\leftrightarrow$ F) |

(Note: The biconditional operator $\leftrightarrow$ evaluates to True only when both sides possess the exact identical truth value).

Step 2: Minterm Extraction

To construct the PDNF, we are mathematically interested only in the specific rows of the truth table where the final output expression ($X$) evaluated to True (T).

• Row 2: $p$ is True, $q$ is False. The output is True. To create a minterm (an AND statement) that evaluates to True for this specific row, we must use $p$ and the negation of $q$. Extracted Minterm 1: $(p\wedge \neg q)$
• Row 3: $p$ is False, $q$ is True. The output is True. To create a minterm for this row, we must use the negation of $p$ and the normal state of $q$. Extracted Minterm 2: $(\neg p\wedge q)$

Step 3: Final Synthesis

The final mathematical step is to combine all extracted minterms together using logical disjunction (the OR operator). This creates an expression that will output True if Minterm 1 is triggered OR if Minterm 2 is triggered.

The definitive Principal Disjunctive Normal Form is: PDNF = $(p\wedge \neg q)\vee (\neg p\wedge q)$

(Observation: This resulting PDNF is the exact boolean definition of the Exclusive-OR (XOR) logic gate, $p\oplus q$).

Significance of Canonical Forms: The PDNF (and its dual, the Principal Conjunctive Normal Form, or PCNF, built from maxterms corresponding to the False rows instead) is important precisely because it is unique: for a given truth table, there is exactly one PDNF expression, unlike ordinary simplified Boolean expressions which can often be written in several equivalent but syntactically different minimal forms. This uniqueness property makes PDNF invaluable for formally proving whether two logical expressions are truly equivalent — simply derive the PDNF of both and check if they match term-for-term — a technique used in digital logic verification and automated theorem proving. It also serves as the direct starting point for combinational circuit synthesis, since each minterm in the PDNF directly corresponds to one AND-gate term feeding into a final OR gate, giving an immediate (if not necessarily minimal) two-level Sum-of-Products hardware realization that can subsequently be simplified using Karnaugh maps or the Quine-McCluskey algorithm.