I'm looking for the next step in my propositional logic homework, I seem to have gotten stuck and can't figure out where to go. Any guidance or perhaps some suggestion as to how to head the right direction? I've been beating my head against this problem for well over an hour.

Prove $(p \lor q) \land (\lnot p \lor r) \rightarrow (q \lor r)$ is a tautology.

$(p \lor q) \land (\lnot p \lor r) \rightarrow (q \lor r)$
$(p \lor q) \land \lnot(\lnot p \lor r) \lor(q \lor r)$ -- implication
$(p \lor q) \land (\lnot\lnot p \land \lnot r) \lor(q \lor r)$ -- demorgans
$(p \lor q) \land ( p \land \lnot r) \lor(q \lor r)$ -- double negation
$((p \lor q) \land ( p \land \lnot r)) \lor((p \lor q)\land(q \lor r))$ --distribution

And that's where I get stuck. I've tried using the associative laws to move things around but nothing seems to cancel out. Where did I get stuck/where would you go from here?

  • $\begingroup$ This is why logic instructors insist on using parentheses ... see Graham Kemp's answer to see what you did wrong $\endgroup$ – Bram28 Sep 28 '17 at 3:24

Prove $(p \lor q) \land (\lnot p \lor r) \rightarrow (q \lor r)$ is a tautology.

You are reading that as $(p \lor q)~\land~\big((\lnot p \lor r) \rightarrow (q \lor r)\big)$, which is not a tautology.

$A\wedge B\to C$ is conventionally read as $(A\wedge B)\to C$ due to operational precedence.

So, instead try to prove $\big((p \lor q) \land (\lnot p \lor r)\big)~ \rightarrow ~(q \lor r)$ is a tautology.

Which it is.

  • $\begingroup$ I was indeed reading it incorrectly. I never realized there was a "pemdas" for logical operators. Bookmarked your link for future use! $\endgroup$ – Podo Sep 28 '17 at 16:25

We can do it through some simple observations. The only way that an implication can be $0$ is if we have $1 \rightarrow 0$. Your expression $$((p \vee q) \wedge (\neg p \vee r)) \rightarrow (q \vee r)$$

gives us that $((p \vee q) \wedge (\neg p \vee r))$ must be $1$, and $(q \vee r)$ must be $0$.

The only way that $(q \vee r)$ can be $0$ is if both $r$ and $q$ is $0$. We then have that $((p \vee 0) \wedge (\neg p \vee 0))$ has to be $1$. For that to be true both $(p \vee 0)$ and $(\neg p \vee 0)$ has to be $1$ because of the and. This must then mean that $p$ has to be $1$ and $0$ at the same time which is a contradiction; which must mean it's impossible to get a $0$ from the entire expression, which must mean it's a tautology.


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.