# Got stuck doing a proof with logical equivalences

I have to show that $(p\lor q)\land (\neg p\lor r)\rightarrow (q\lor r)$ is a tautology. I have :

$(p \lor q) \land (\neg p \lor r) \to (q \lor r) \equiv \neg((p \lor q) \land (\neg p \lor r)) \lor (q \lor r)$ implication proof

$\equiv \neg(p \lor q) \lor \neg(\neg p \lor r) \lor (q \lor r)$ De Morgan

$\equiv (\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r)$ De Morgan

I don't know how to proceed from here. Can anybody check and see if I messed up or point me to a right step?

Thanks!

• There are eight possible truth value assignments for the variables. ($2^3$), In such a case, use a truth table to show that every row of truth-value assignments, when evaluating your expression, yields "true". So the right most column will show 8 rows of T (T for true, or 1 if you use 1 for true.) – Namaste Jan 24 '18 at 0:31
• assignments (p, q, r): (T, T, T), (T, T, F), (T, F, T), (T, F, F), (F, T, T), (F, T, F), (F, F, T), (F, F, F) – Namaste Jan 24 '18 at 0:34
• Note you can write your last statement as follows: $$(\lnot p \land \lnot q) \lor (p\land \lnot r) \lor q \lor r$$ Then (1) whenever q, or r are true, the statement is true (that happens in six of the truth value assignments, ignoring p.) – Namaste Jan 24 '18 at 0:42
• P and not p is a contradiction. P or not p is a tautology. The last line you worked out should tell you what to assume. – smokeypeat Jan 24 '18 at 5:35
• I got it using that comment @amWhy. Thank you so much! – Dart Feld Jan 28 '18 at 4:21

$$(\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r) \overset{Association}{\equiv}$$

$$(\neg p \land \neg q) \lor (p \land \neg r) \lor q \lor r \overset{Commutation}{\equiv}$$

$$q \lor (\neg p \land \neg q) \lor r \lor (p \land \neg r) \overset{Reduction \ x \ 2}{\equiv}$$

$$q \lor \neg p \lor r \lor p \overset{Complement}{\equiv}$$

$$\top \lor q \lor r \overset{Annihilation}{\equiv}$$

$$\top$$

So here I used:

Reduction

$P \land (\neg P \lor Q) \equiv P \land Q$

$P \lor (\neg P \land Q) \equiv P \lor Q$

If Reduction is not in your arsenal of equivalence principles, here's how you can do Reduction in terms of other elementary equivalences:

Reduction

$$P \lor (\neg P \land Q) \Leftrightarrow \text{ (Distribution)}$$

$$(P \lor \neg P) \land (P \lor Q) \Leftrightarrow \text{ (Complement)}$$

$$\top \land (P \lor Q) \Leftrightarrow \text{ (Identity)}$$

$$P \lor Q$$

• Your step (using reduction)neglects $\land \lnot q \lor (p \land \lnot r) = (\lnot q \lor p) \land (\lnot q \lor r)$. (You distributed $\lnot p$ from $(\lnot p \land \lnot q)$ over $(p \land \lnot q),$ but you never distributed $\lnot q$ over $(p\land \lnot q)$. – Namaste Jan 24 '18 at 15:22
• @amWhy I apply Reduction twice ... let me make this more clear .... – Bram28 Jan 24 '18 at 15:27
• @amWhy I completely disagree. I merely inserted an explicit Commutation step, which is something we often leave out when doing algebra, so in essence it really is still the same answer. In fact, I believe you just didn't see the Reductions I was doing: you keep asking about what I do with the terms $\neg q \lor p$ and $\neg q \lor \neg r$ and I what I do with them is that I reduce them. Indeed, contrary to what you wrote, I did not do any Distribution here, just a direct Reduction. So if anyone is in error here it's you. – Bram28 Jan 24 '18 at 16:13
• I think the separate step was important, in terms of illucidating a bit better for the OP what is going on, especially when they haven't encountered as "reduction". Any way, I'd be happy to remove my downvote, but either you or I would need to edit your post again for me to do so. oops, I just added "tautologically true" as a tag to your last line: $\top$. I hope that's okay with you. – Namaste Jan 24 '18 at 16:22
• Note, when I evaluate answers, one thing I am rather good at is putting myself in the shoes of the asker, and evaluate how accessible the answer is. And yes, distribution is involve, as you show in you demonstration of Reduction. Distribution is implicit in and essential to the Reduction rule. One cannot justify the use of reduction without the implicit use of distribution, as you show in your proof of reduction. One can, however, prove the statement without any knowledge of reduction. – Namaste Jan 24 '18 at 16:33

Assume the premise $(p\lor q)\land (\neg p\lor r)$.
There are two cases, p and $\neg p$.
In the first case, conclude r.
In the second case, conclude q.
So from both cases, conclude $q \lor r.$

• how would I assume that premise? is there some sort of negation involved in that? – Dart Feld Jan 24 '18 at 4:01
• @JorgeSepúlveda. What nonlogic course are you taking?? Take it as a given or case 1 of one case. – William Elliot Jan 24 '18 at 8:03
• Assuming the premise as you suggest, and proving the the conclusion, does not prove that the statement is a tautology, it just proves the original statement. It's the OP's task to determine if the entire statement is in fact, a tautology, not merely logically deductible. – Namaste Jan 24 '18 at 16:25
• logically deductible and tautological are equivalent for the propositional calculus. Otherwise use a truth table. – William Elliot Jan 24 '18 at 19:01

Here a proof using mainly (1) contraposition (2) exportation rule ( twice) (3) and the domination law :

P OR True is equivalent to True.

Remark : I use True and False as propositional constants ( True = the proposition that is equivalent to any tautology, False = the proposition that is equivalent to any antilogy).

(PvQ) & (~PvR) --> (QvR)

↔ ~ ( QvR) --> ~ [ (PvQ) & (~PvR) ]

↔ (~Q & ~R) --> [ ~ (PvQ) v ~ ( ~P v R) ]

↔ (~Q & ~R) --> [ (PvQ) --> ~ ( ~P v R) ]

↔ [ (~Q & ~R) & (PvQ)] --> ~ ( ~P v R)

↔ [ (~Q&~R & P) v (~Q & ~R & Q) ] --> ~ ( ~P v R)

↔ [ (~Q&~R & P) v False ] --> ~ ( ~P v R)

↔ (~Q&~R & P) --> ~ ( ~P v R)

↔ (~Q&~R & P) --> P & ~ R

↔ ~Q --> [ (P& ~R) --> (P & ~ R ) ]

↔ ~Q --> True

↔ Q v True

↔ True