This is from a Discrete Mathematics term test question.

Q4. Which of the following statements is/are logically equivalent to $p \iff q$?

Note: $\sim$ means the negation of

(I) $(\sim p \lor q) \land (p \lor \sim q)$

(II) $(\sim p \land \sim q) \lor (p \land q)$

(III) $(\sim p \lor \sim q) \land (p \lor q)$

(IV) $(\sim p \land q) \lor (p \land \sim q)$

The answer is (I) and (II). I could easily get the first one since $p \iff q \equiv (p \to q) \land (q \to p)$.

As this is MCQ, I definitely avoid truth tables. I also want to avoid using a lot of equivalent laws to save time and reduce sources of error. However for (II), I cannot think of simple way other than applying distributive law into 4 terms like into $$((\sim p \land \sim q) \lor p) \land ((\sim p \land \sim q) \lor q)$$ then another round of distributive law to simplify to $$((\sim p \lor p) \land (p \lor \sim q)) \land ((\sim p \lor q) \land (\sim q \lor q))$$, which feels very tedious to me especially since I might mess the ordering up since some of these properties might not be commutative. Does anyone have a solution to this problem?

  • $\begingroup$ $p \iff q$ is true only when both $p$ and $q$ have the same truth values. It is fairly easy to see that option II satisfies that. $\endgroup$ – Anurag A Sep 28 '18 at 4:57
  • $\begingroup$ So is the general idea to get the possible set of truth values that the original statement allows, for this case (p,q) only can be (T,T) and (F,F) , then do a substitution test to see whether it evaluates as True? $\endgroup$ – Prashin Jeevaganth Sep 28 '18 at 5:02

Using double distribution : \begin{align}(\lnot p \land \lnot q)\lor(p\land q) &\equiv (\lnot p \lor p) \land (\lnot p \lor q) \land (\lnot q \lor p) \land (\lnot q \lor q) \\ &\equiv (\lnot p \lor q) \land (\lnot q \lor p) \\ &\equiv p\iff q \end{align}.

Hope that help!

  • $\begingroup$ That is what I wanted to avoid actually... $\endgroup$ – Prashin Jeevaganth Sep 28 '18 at 5:06
  • $\begingroup$ Only way I know how without using a logic table. Sometimes, this is consider as an equivalence for $\iff$. $\endgroup$ – Zamarion Sep 28 '18 at 5:12
  • $\begingroup$ I mean brute force is one thing, but I think I want to free up the carelessness factor during examination pressure $\endgroup$ – Prashin Jeevaganth Sep 28 '18 at 5:13
  • $\begingroup$ Yes, I understand, having done this course myself. Sometimes there kind of computation can get tedious, but this one is only three step. Anyway, sorry I couldn't help much. $\endgroup$ – Zamarion Sep 28 '18 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.