2

If found a multiple choice question online:

If $(p \rightarrow q) $ is not a tautology and $ (q \rightarrow p) $ is not a tautology, then:

  1. $ p \lor q $ is not a tautology
  2. $ p \lor q $ is a tautology
  3. $ p \land q $ is a contradiction
  4. $ (p \rightarrow q) \rightarrow (q \rightarrow p) $ is a tautology
  5. None of the above

I realized that for $ p \rightarrow q $ and $ q \rightarrow p $ to not be tautologies, there has to be a case where $ p $ is true and $ q $ is false, and vice versa. So I eliminated choices $ 1, 2, 3 $. But I don't understand what choice $ 4 $ means?

Shaun
  • 44,997
talopl
  • 999
  • 2
    Hint: what happens if $\neg p\land q$? – J.G. Jun 25 '22 at 14:25
  • Off topic, but I think $(p \rightarrow q) \lor (q \rightarrow p)$ is a counter-intuitive tautology – Henry Jun 25 '22 at 14:29
  • Only $p=0, q=1$ gives false for $(p \rightarrow q) \rightarrow (q \rightarrow p)$. – zkutch Jun 25 '22 at 14:34
  • Hint: see principle of explosion – Couchy Jun 26 '22 at 05:15
  • Alternatively, since the question evidently expects us to use logical reasoning, and since the two given conditions are redundant (being given them neither narrows down nor expands the possibilities), then it must be permissible to directly use logical reasoning (for example, a truth table) to determine whether option 4 is true. So, after having eliminated the first three options, the rest of the problem is equivalent to this question (in italics), which may be more straightforward than the alternative (arguing using the two given conditions, as described by Graham below). – ryang Jun 26 '22 at 06:01

2 Answers2

1

But I don't understand what choice 4 means?

It means a counter example would have $p\to q$ be true but $q\to p$ be false.

The later may be false because $q\to p$ is not a tautology, and when it is false then $p\to q$ is ???

Graham Kemp
  • 129,094
0

You could also find the answer if we took some logical reasoning using DeMorgan's Laws: We see that $(p \to q) $ is not a tautology, and $(q \to p)$ is also not a tautology, then:

$$(p \to q) \to (q \to p) \qquad \text{Given} \\ \equiv (\lnot p \lor q) \to (\lnot q \lor p) \qquad p \to q \equiv \lnot p \lor q \\ \equiv \lnot (\lnot p \lor q) \lor (\lnot q \lor p) \qquad p \to q \equiv \lnot p \lor q \\ \equiv (p \land \lnot q) \lor (\lnot q \lor p) \qquad \text{Double Negation} \\ \ \equiv \big[ p \lor (\lnot p \lor q) \big] \land \big[ q \lor (\lnot p \lor q) \big] \qquad \text{Distributive Law} \\ \equiv [p \lor \lnot p \lor q] \land [\lnot p \lor q \lor q] \qquad \text{Associative Law} \\ \equiv [T \lor q] \land [\lnot p \lor q] \qquad \text{Negation Law} \\ \equiv T \land (\lnot p \lor q) \qquad \text{Domination Law} \\ \equiv (\lnot p \lor q) \qquad \text{Identity Law} \\ \equiv (p \to q) \qquad p \to q \equiv \lnot p \lor q $$

We see that we end up with the given fact that we have defined that $p \to q$ is not a tautology. Since we started with $(p \to q) \to (q \to p)$ and ended with $p \to q$, we can conclude that this statement is indeed NOT a tautology. $\square$

James
  • 742