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$).