Is $(p \lor q) \to (\neg p \to (p \lor q))$ a tautology?

Question

This question came up in a recent assignment. I was asked to find a logically equivalent alternative to the statement in the title from the options below.

(p ∨ q) ∨ ¬p
(¬p & ¬q) ∨ (p ∨ q)
(p & q) ∨ (p ∨ q)
(¬p & ¬q) ∨ (¬p & q)

No matter how many times I redo this question I always come up with both options 1 and 2 being a logical equivalent. Have I missed something somewhere or is there an error in the question?

As a rule, if $A$ is true then $B\rightarrow A$ is true for any $B.$ — Thomas Andrews, Apr 18 '19 at 15:03
So $A\rightarrow (B\rightarrow A)$ is a tautology for all $A,B.$ — Thomas Andrews, Apr 18 '19 at 15:04
Hello and welcome to MSE. Generally, people on the site prefer the use of MathJax formatting when it comes to both questions and answers. For future reference, please be sure to see this helpful guide. — CardioidAss22, Apr 18 '19 at 15:09
@MauroALLEGRANZA I have and have checked it with multiple truth table calculators. — Damian Jacobs, Apr 18 '19 at 15:15
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $\checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?. — Shaun, Apr 18 '19 at 15:39

Mauro ALLEGRANZA · Answer 1 · 2019-04-18T15:27:21.977

0

Hint

Rewrite $(¬p \to (p \lor q))$ as $(p \lor (p \lor q))$ using Material Implication.

Then use Associativity and Idempotency to simplify it to : $p \lor q$.

What you get is :

$(p \lor q) \to (p \lor q)$.

edited Apr 18 '19 at 15:27

answered Apr 18 '19 at 15:02

Mauro ALLEGRANZA

94,169

Thank you very much for the link to that table, it lays out everything very clearly which I don't have anywhere in my textbooks. – Damian Jacobs Apr 18 '19 at 15:33

score 0 · Answer 2 · answered Apr 18 '19 at 15:08

0

rewrite (p ∨ q) -> [¬p -> (p ∨ q)] as (¬(p ∨ q))∨[¬p -> (p ∨ q)] as p-> q ac be rewritten as (¬p) ∨q

so (¬(p ∨ q))∨[¬p -> (p ∨ q)]=(¬(p ∨ q))∨((¬(¬p))∨(p ∨ q) can be written as (¬(p ∨ q))∨(p∨(p∨q))

or (¬(p ∨ q))∨(p∨q) which is a tautology

answered Apr 18 '19 at 15:08

Chandra Sangala

11

Thank you this really clears things up and then I assume you can take it one step further and write (¬(p ∨ q))∨(p∨q) as (¬p & ¬q) ∨ (p ∨ q) – Damian Jacobs Apr 18 '19 at 15:23
Yes,that is correct – Chandra Sangala Apr 18 '19 at 15:24

score 0 · Answer 3 · answered Apr 18 '19 at 15:35

0

Let $r=p\lor q$. Suppose the negation of your proposition; that is, consider $$\lnot(r\to(\lnot p\to r)).$$ The only way an implication can be false is if the first part is true while its conclusion is false, so we have $r$ and $\lnot(\lnot p\to r)$, but by the same token, we have $\lnot p$ and $\lnot r$, which contradicts $r$. Hence your proposition must be a tautology.

answered Apr 18 '19 at 15:35

Shaun

44,997

1

Thats a really nice simplification of the problem thank you, hadn't thought about it in such a way. – Damian Jacobs Apr 18 '19 at 15:37
You're welcome, @DamianJacobs :) – Shaun Apr 18 '19 at 15:39

Is $(p \lor q) \to (\neg p \to (p \lor q))$ a tautology?

3 Answers3