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.
Best Answer
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}$$