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?

$(p→q)↔(¬q→¬p) $ is a tautology. Check it with truth table. — Mauro ALLEGRANZA, Nov 23 '20 at 15:00
Why fallacy in this context ? A fallacy is an invalid argument. I is a formula. — Mauro ALLEGRANZA, Nov 23 '20 at 15:02
@MauroALLEGRANZA Using truth tables would be a lengthy approach (I have edited the title now). This question is from a competitive exam. I am looking to solve it as quickly as possbile. — aarbee, Nov 23 '20 at 15:04
$p \to q$ is $\lnot p \lor q$ and $\lnot q \lor \lnot p$ is $q \lor \lnot p$ — Mauro ALLEGRANZA, Nov 23 '20 at 15:05
@MauroALLEGRANZA indeed, in the correct way. If truth table is the only option, I would adopt it. But I guess there are other, quicker approaches available e.g. Lion Heart's answer below. — aarbee, Nov 23 '20 at 15:07

score 1 · Answer 1 · answered Nov 23 '20 at 15:04

1

$$(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}$$

answered Nov 23 '20 at 15:04

Lion Heart

7,073

Thanks. Any chance you could point out mistake in my approach? – aarbee Nov 23 '20 at 15:11

score 1 · Accepted Answer · answered Nov 23 '20 at 15:14

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.

Thanks for the answer, but not able to see my error. Mind pointing it out specifically? — aarbee, Nov 23 '20 at 15:21
$(p′+q)(q+p′)+(pq′)(q′p)$ is correct, but all that follows is wrong. You seem to want to develop, but shouldn't. $A \cap A$ simplifies to $A$, use that. It becomes $(p′+q)+(pq′)$ then using $\neg \neg p \Leftrightarrow p$ on the second term, you get $(p′+q)+(p'+q)'$, which is an evident tautology $A \cup \neg A$ — Tristan Duquesne, Nov 23 '20 at 15:34

score 0 · Answer 3 · answered Nov 23 '20 at 15:31

0

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.

answered Nov 23 '20 at 15:31

aarbee

8,246

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

3 Answers3