# Need help with solving proposition logic formula, should be a tautology

I have the following formula:

$(((p \vee q) \rightarrow r) \wedge (p \rightarrow q))\rightarrow (q\rightarrow r)$

The truth table for this formula shows that this is a tautology. However, I get stuck simplifying this formula at a certain point. My steps are as follows:

First, I use implication elimination on all $\rightarrow$. The formula will then become:

$\neg ((\neg(p \vee q) \vee r) \wedge (\neg p \vee q)) \vee (\neg q\vee r)$

Then, I will use De Morgan on $\neg(p \vee q)$:

$\neg (((\neg p \wedge \neg q) \vee r) \wedge (\neg p \vee q)) \vee (\neg q \vee r)$

And then De Morgan on $\neg (((\neg p \wedge \neg q) \vee r) \wedge (\neg p \vee q))$:

$(\neg ((\neg p \wedge \neg q) \vee r) \vee \neg (\neg p \vee q)) \vee (\neg q \vee r)$

$((\neg (\neg p \wedge \neg q) \wedge \neg r) \vee \neg (\neg p \vee q)) \vee (\neg q \vee r)$

$(((\neg \neg p \vee \neg \neg q) \wedge \neg r) \vee \neg (\neg p \vee q)) \vee (\neg q\vee r)$

$(((p \vee q) \wedge \neg r) \vee \neg (\neg p \vee q)) \vee (\neg q \vee r)$

$(((p \vee q) \wedge \neg r) \vee (\neg \neg p \wedge \neg q)) \vee (\neg q \vee r)$

$(((p \vee q) \wedge \neg r) \vee (p \wedge \neg q)) \vee (\neg q \vee r)$

From here I have no ideas anymore what to do. All things seem to go into a dead end. For example, I tried to distribute $\neg r$ over $(p \vee q)$ in $((p \vee q) \wedge \neg r)$, and then I'd end up with:

$((\neg r \wedge p) \vee (\neg r \wedge q) \vee (p \wedge \neg q)) \vee (\neg q \vee r)$

With this, I also have no idea what to do.

It would be great if I'd get some help with how to proceed from here, how to get to the tautology.

• What are you trying to do? (you have already proved the tautology) – user58512 Mar 17 '13 at 10:08
• Really? Then I'm not seeing it (meaning I'm probably overlooking it). What I'm trying to do is to simplify it to T (=tautology) – Garth Marenghi Mar 17 '13 at 10:15
• yes by the truth table – user58512 Mar 17 '13 at 10:15
• Ah, okay. No, I should show it with a truth table, and also with simplifying the formula. – Garth Marenghi Mar 17 '13 at 10:16
• Got your review, I rejected it because it really says $p \vee q$ in the assignment. – Garth Marenghi Mar 17 '13 at 10:17

I'll go rather slowly, but I will omit some superfluous parentheses.

Denoting $(((p \vee q) \rightarrow r) \wedge (p \rightarrow q))\rightarrow (q \rightarrow r)$ by $(\star)$ we have \begin{align} (\star ) %% &= \neg ( ( \neg ( p \vee q ) \vee r ) \wedge ( \neg p \vee q ) ) \vee ( \neg q \vee r ) &\text{(unabbreviating)} \\ &= ( \neg ( \neg ( p \vee q ) \vee r ) \vee \neg ( \neg p \vee q ) ) \vee ( \neg q \vee r ) &\text{(de Morgan)} \\ %% &= ( ( \neg \neg ( p \vee q ) \wedge \neg r ) \vee ( \neg \neg p \wedge \neg q ) ) \vee ( \neg q \vee r ) &\text{(de Morgan)} \\ %% &= ( ( p \vee q ) \wedge \neg r ) \vee ( p \wedge \neg q ) \vee ( \neg q \wedge r ) &\text{(double negation)} \\ %% &= ( p \wedge \neg r ) \vee \color{red}{( q \wedge \neg r )} \vee ( p \wedge \neg q ) \vee \color{red}{( \neg q \vee r )} &\text{(distributivity)}\end{align} Note that \begin{align} \neg q \vee r &= \neg \neg \neg q \vee \neg \neg r &\text{(double negation)} \\ &= \neg ( \neg \neg q \wedge \neg r ) &\text{(de Morgan)} \\ &= \neg ( q \wedge \neg r ) &\text{(double negation)} \end{align} and so we have \begin{align} (\star) &= ( p \wedge \neg r ) \vee \color{red}{( q \wedge \neg r )} \vee ( p \wedge \neg q ) \vee \color{red}{( \neg q \vee r )} \\ &= ( p \wedge \neg r ) \vee \color{red}{( q \wedge \neg r )} \vee ( p \wedge \neg q ) \vee \color{red}{\neg ( q \wedge \neg r )} &\text{(by above)} \\ &= \top \vee ( p \wedge \neg r ) \vee ( p \wedge \neg q ) &\text{(s \vee \neg s = \top)} \\ &= \top &\text{(\top \vee s = \top)} \end{align}

• Thank you for your answer! I am so very sorry, but I made a mistake, and that is that at the end of $\neg ((\neg (p \vee q) \vee r) \wedge (\neg p \vee q)) \vee (\neg p \vee r)$, it shouldn't say $(\neg p \vee r)$ but $(\neg q \vee r)$. I will adjust my post, and once again, I'm sorry. – Garth Marenghi Mar 17 '13 at 12:15
• @GarthMarenghi: Virtually all of my answer will apply to the changed formula, I'll presently make some edits, but basically different formulas will have to be highlighted at the end. – user642796 Mar 17 '13 at 12:19
• This is amazing, you showed me what I did wrong and one thing I didn't think of! The thing I did wrong was this: I used De Morgan here: $(\neg (\neg (p \vee q) \vee r)$ to make $(\neg ((\neg p \wedge \neg q) \vee r)$, instead of NOT doing that and pushing the outer $\neg$ in. I just... didn't know! And the other thing was in the "Note that". I wouldn't have come up with that one. Brilliant :-), thanks – Garth Marenghi Mar 17 '13 at 12:37
• @GarthMarenghi: However you do the applications of de Morgan's laws should result in the same formula. If you go outside-in, then starting from the outermost negations may result in fewer applications of this law (because you might create double negations which can be duly crossed out and forgotten). As for the "Note that," it could have been avoided by using distributivity to compute $(q\wedge\neg r)\vee(\neg q\vee r)$, but the real crux is noticing that two terms had the same sentence symbols: this is often a clue that great simplifications are to be had! Anyways, I'm glad I helped!! – user642796 Mar 17 '13 at 13:04

$$(((p \vee q) \rightarrow r) \wedge (p \rightarrow q))\rightarrow (p\rightarrow r)$$

is implied by

$$((p \vee q) \rightarrow r)\rightarrow (p\rightarrow r)$$

is equivalent to

$$p \rightarrow (p \vee q)$$

is implied by

$$p \rightarrow p$$

is implied by

$$\top$$

• Thanks for your answer, though I have a bit hard time understanding it. For example, how are you able to leave $\wedge (p \rightarrow q)$ out from the first to the seconde line? As for being a late learner, well so am I ;-). I want to do AI and understand algorithms, but I couldn't even do algebra well. – Garth Marenghi Mar 17 '13 at 10:39
• I used: $A \land B \to C$ is implied by $A \to C$. This is because if you can prove $C$ using only $A$, you can certainly prove it using $A$ and $B$. – user58512 Mar 17 '13 at 10:42
• Thank you caveman for your help! – Garth Marenghi Mar 17 '13 at 12:38