1. **Problem Statement:** Find the PCNF (Principal Conjunctive Normal Form) and PDNF (Principal Disjunctive Normal Form) of the formula $$ (p \to (q \wedge r)) \wedge (\neg p \to (\neg q \wedge \neg r)) $$ without constructing the truth table. 2. **Recall the definitions and rules:** - Implication: $$ a \to b \equiv \neg a \vee b $$ - PCNF is a conjunction of clauses (disjunctions of literals) that is logically equivalent to the formula. - PDNF is a disjunction of minterms (conjunctions of literals) that is logically equivalent to the formula. 3. **Rewrite implications using equivalences:** $$ (p \to (q \wedge r)) \wedge (\neg p \to (\neg q \wedge \neg r)) $$ $$ \equiv (\neg p \vee (q \wedge r)) \wedge (p \vee (\neg q \wedge \neg r)) $$ 4. **Distribute to get CNF form:** Use distributive laws: $$ (\neg p \vee q) \wedge (\neg p \vee r) \wedge (p \vee \neg q) \wedge (p \vee \neg r) $$ This is the PCNF. 5. **Find PDNF:** PDNF is a disjunction of all minterms where the formula is true. Analyze the formula: - The formula is true when either $p$ is true and $q,r$ are true, or $p$ is false and $q,r$ are false. So the satisfying assignments are: - $p=1, q=1, r=1$ - $p=0, q=0, r=0$ Corresponding minterms: - $p \wedge q \wedge r$ - $\neg p \wedge \neg q \wedge \neg r$ Thus, the PDNF is: $$ (p \wedge q \wedge r) \vee (\neg p \wedge \neg q \wedge \neg r) $$ 6. **Summary:** - PCNF: $$ (\neg p \vee q) \wedge (\neg p \vee r) \wedge (p \vee \neg q) \wedge (p \vee \neg r) $$ - PDNF: $$ (p \wedge q \wedge r) \vee (\neg p \wedge \neg q \wedge \neg r) $$ These forms represent the original formula equivalently without constructing the full truth table.