How to see that $(p\rightarrow q)\leftrightarrow(\lnot q\rightarrow\lnot p)$ is a tautology, without using truth table?

Question

Consider: Statement-I: $(p\land\lnot q)\land(\lnot p\land q)$ is a fallacy. Statement-II: $(p\rightarrow q)\leftrightarrow(\lnot q\rightarrow\lnot p)$ is a tautology. Which of these statements is true? If both are true then is statement-II a correct explanation of statement-I?

My attempt:

Statement-I: $(pq')(p'q)=0$. So, true.

Statement-II: $(p'+q)(q+p')+(pq')(q'p)$ [using the rules $p\rightarrow q=p'+q$ and $p\leftrightarrow q=pq+p'q'$]

So, statement-II becomes $p'q+q+qp'+pq'=p'q+q+pq'=q+pq'$, which is not a tautology. But the answer key says it is a tautology.

What's my mistake here?

Answer 1

If you take Venn diagrams, $p \to q$ can be represented as having the set for $p$ being included in the set for $q$. It is geometrically obvious that this is equivalent to the set for $\neg q$ being included in the set for $\neg p$.

As for your error, it's at the very beginning. If we write $P := p \to q$ and $Q := \neg q \to \neg p$:

$$(P \Leftrightarrow Q) \Leftrightarrow$$ $$((P \cap Q) \cup (\neg P \cap \neg Q)) \Leftrightarrow$$ $$(((p \to q) \cap (\neg q \to \neg p)) \cup (\neg (p \to q) \cap \neg (\neg q \to \neg p))) \Leftrightarrow$$ $$(((\neg p \cup q) \cap (q \cup \neg p)) \cup (\neg (\neg p \cup q) \cap \neg (q \cup \neg p))) \Leftrightarrow$$ $$(((\neg p \cup q) \cap (q \cup \neg p)) \cup ((p \cap \neg q) \cap (\neg q \cap p))) \Leftrightarrow$$ $$((\neg p \cup q) \cup (p \cap \neg q)) \Leftrightarrow$$ $$((\neg p \cup q) \cup \neg \neg(p \cap \neg q)) \Leftrightarrow$$ $$((\neg p \cup q) \cup \neg (\neg p \cup q)) \Leftrightarrow$$ $$A \cup \neg A \Leftrightarrow$$ $$True$$

Since De Morgan's laws of negation invert internal conjunction/disjunction operators.

PS: you can use \Leftrightarrow, \neg, \to, \cup, and \cap in your LaTeX.

Answer 2

$$(p\implies q) \iff (\neg q \implies \neg p)$$

$$((p\implies q) \implies (\neg q \implies \neg p)) \land ((\neg q \implies \neg p)\implies (p\implies q))$$

$$((\neg p \lor q) \implies (q \lor \neg p)) \land ((q \lor \neg p)\implies (\neg p\lor q))$$

$$(\neg(\neg p \lor q) \lor (q \lor \neg p)) \land (\neg(q \lor \neg p)\lor (\neg p\lor q))$$

$$(\neg(\neg p \lor q) \lor (q \lor \neg p)) $$

$$\text {tautology}$$

Answer 3

Just figured out that $(\lnot q\rightarrow\lnot p)$ is a contrapositive of $(p\rightarrow q)$ i.e. both are just the same thing. So, $(p\rightarrow q)\leftrightarrow(\lnot q\rightarrow\lnot p)$ is a tautology.