1. **Problem statement:** Show the equivalences involving the XOR operator $p \oplus q$. --- ### (a) Show $p \oplus q \equiv \neg(p \leftrightarrow q)$ using a truth table. | $p$ | $q$ | $p \lor q$ | $p \land q$ | $(p \lor q) \land \neg(p \land q)$ | $p \leftrightarrow q$ | $\neg(p \leftrightarrow q)$ | |-----|-----|------------|-------------|-------------------------------------|---------------------|--------------------------| | T | T | T | T | F | T | F | | T | F | T | F | T | F | T | | F | T | T | F | T | F | T | | F | F | F | F | F | T | F | - Step 1: Compute $p \lor q$. - Step 2: Compute $p \land q$. - Step 3: Compute $\neg(p \land q)$. - Step 4: Compute $(p \lor q) \land \neg(p \land q)$. - Step 5: Compute $p \leftrightarrow q$. - Step 6: Compute $\neg(p \leftrightarrow q)$. The columns for $(p \lor q) \land \neg(p \land q)$ and $\neg(p \leftrightarrow q)$ match exactly, proving the equivalence. --- ### (b) Show $(p \lor q) \land \neg(p \land q) \equiv \neg(p \leftrightarrow q)$ using laws of logical equivalence. 1. Start with the left side: $$ (p \lor q) \land \neg(p \land q) $$ 2. Apply De Morgan's law to $\neg(p \land q)$: $$ (p \lor q) \land (\neg p \lor \neg q) $$ 3. Distribute $\land$ over $\lor$: $$ [(p \lor q) \land \neg p] \lor [(p \lor q) \land \neg q] $$ 4. Distribute inside each term: $$ [(p \land \neg p) \lor (q \land \neg p)] \lor [(p \land \neg q) \lor (q \land \neg q)] $$ 5. Simplify contradictions $p \land \neg p$ and $q \land \neg q$ to false: $$ [\text{False} \lor (q \land \neg p)] \lor [(p \land \neg q) \lor \text{False}] $$ 6. Simplify: $$ (q \land \neg p) \lor (p \land \neg q) $$ 7. Recall that $p \leftrightarrow q$ is $(p \land q) \lor (\neg p \land \neg q)$, so its negation is: $$ \neg(p \leftrightarrow q) \equiv \neg[(p \land q) \lor (\neg p \land \neg q)] $$ 8. Apply De Morgan's law: $$ \neg(p \land q) \land \neg(\neg p \land \neg q) $$ 9. Apply De Morgan's law again: $$ (\neg p \lor \neg q) \land (p \lor q) $$ 10. This matches the original expression, confirming: $$ (p \lor q) \land \neg(p \land q) \equiv \neg(p \leftrightarrow q) $$ --- ### (c) Express $p \oplus q$ as a clause using only $\lor$ and $\neg$. From step (b) and the equivalence: $$ p \oplus q \equiv (p \lor q) \land (\neg p \lor \neg q) $$ Rewrite $\land$ using De Morgan's law: $$ A \land B \equiv \neg(\neg A \lor \neg B) $$ So, $$ p \oplus q \equiv \neg(\neg(p \lor q) \lor \neg(\neg p \lor \neg q)) $$ Simplify inner negations: $$ \neg( (\neg p \land \neg q) \lor (p \land q) ) $$ But since only $\lor$ and $\neg$ are allowed, the clause form is: $$ \neg(\neg(p \lor q) \lor \neg(\neg p \lor \neg q)) $$ This is a compound proposition using only $\lor$ and $\neg$ operators. --- **Final answers:** - (a) Verified by truth table. - (b) Proven by logical equivalences. - (c) Clause form: $$ p \oplus q \equiv \neg(\neg(p \lor q) \lor \neg(\neg p \lor \neg q)) $$