Proving $\{\neg(r\to p)\lor[(\neg q\to\neg p)\land(r\to q)]\}\to(\neg p\lor q)$ is a tautology without a truth table

Question

Hello! I'm having problems trying to figure out this. Here is what I did: I used implication relation and Demorgan's law to simplify this proposition. I then used associative and commutative laws because the operators were are disjuntions and conjunctions.

The picture below is basically proof of my attempt at trying to solve this. There is no need to follow along and attempt to correct my work. I fear that that may be too time consuming considering how rough my work is. Hints/answer is much appreciated.

EDIT: Once again, no need to correct my wrong. It's really rough. I'll keep it much neater next time.

Answer 1

The key here is largely going to be patience, but one point is worth remembering: always try to turn connectives into only $\lor, \land,$ and $\neg$. Then everything often "falls out" more or less. Since your compound proposition is quite large, start by writing out and denoting it $\text{LHS}$ like so:

$$\text{LHS}\equiv\Bigl\{\neg(r\to p)\lor\bigl[(\neg q\to\neg p)\land(r\to q)\bigr]\Bigr\}\to(\neg p\lor q)\tag{1}$$

Now, the goal is to show that $(1)$ is a tautology. To that end, let $\textbf{T}$ symbolize this as $\text{RHS}\equiv\textbf{T}$. That is, you want to show that $\text{LHS}\equiv\text{RHS}$. That being said, see if you can follow the argument outlined below: \begin{align} \text{LHS} &\equiv\Bigl\{\neg(r\to p)\lor\bigl[(\neg q\to\neg p)\land(r\to q)\bigr]\Bigr\}\to(\neg p\lor q)\tag{by definition}\\[0.5em] &\equiv \Bigl\{(r\to p)\land\bigl[\neg(\neg q\to\neg p)\lor\neg(r\to q)\bigr]\Bigr\}\lor(\neg p\lor q)\tag{$\substack{\text{DeMorgan &}}\\\eta\to\phi\equiv\neg\eta\lor\phi$}\\[0.5em] &\equiv \Bigl\{(\neg r\lor p)\land\bigl[(\neg q\land p)\lor(r\land\neg q)\bigr]\Bigr\}\lor(\neg p\lor q)\tag{$\substack{\text{DeMorgan &}}\\\eta\to\phi\equiv\neg\eta\lor\phi$}\\[0.5em] &\equiv \bigl[(\neg r\lor p)\lor(\neg p\lor q)\bigr]\land\Bigl\{(\neg q\land p)\lor(r\land\neg q)\lor(\neg p\lor q)\Bigr\}\tag{distributivity}\\[0.5em] &\equiv\bigl[(\neg p\lor p)\lor(\neg r\lor q)\bigr]\land\Bigl\{(\neg q\land p)\lor(r\land\neg q)\lor(\neg p\lor q)\Bigr\}\tag{associativity}\\[0.5em] &\equiv \textbf{T}\land\Bigl\{(\neg q\land p)\lor(r\land\neg q)\lor(\neg p\lor q)\Bigr\}\tag{neg. & dom.}\\[0.5em] &\equiv (\neg q\land p)\lor(r\land\neg q)\lor(\neg p\lor q)\tag{identity}\\[0.5em] &\equiv [\neg q\land(p\lor r)]\lor(\neg p\lor q)\tag{distributivity}\\[0.5em] &\equiv [\neg q\lor(\neg p\lor q)]\land[(p\lor r)\lor(\neg p\lor q)]\tag{distributivity}\\[0.5em] &\equiv [(\neg q\lor q)\lor\neg p]\land[(p\lor\neg p)\lor(r\lor q)]\tag{associativity}\\[0.5em] &\equiv [\textbf{T}\lor\neg p]\land[\textbf{T}\lor(r\lor q)]\tag{negation}\\[0.5em] &\equiv \textbf{T}\land\textbf{T}\tag{domination}\\[0.5em] &\equiv \textbf{T}\tag{identity}\\[0.5em] &\equiv \text{RHS} \end{align}

Answer 2

I would treat this as a simplification problem: start with the left hand side of the statement, and work towards the right hand side.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\equiv}{\leftrightarrow} \newcommand{\then}{\rightarrow} \newcommand{\followsfrom}{\leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

This leads to the following straightforward calculation:

$$\calc \lnot(r\then p) \;\lor\; \big((\lnot q\then\lnot p) \land (r\then q)\big) \op\equiv\hints{write all $\;\psi \then \phi\;$ as $\;\lnot \psi \lor \phi\;$; remove $\;\lnot \lnot {}\;$} \hint{-- usually $\;\then\;$ is not easy to calculate with} \lnot(\lnot r \lor p) \;\lor\; \big((q \lor \lnot p) \land (\lnot r \lor q)\big) \op\equiv\hints{simplify left hand part using DeMorgan;} \hints{simplify right hand part by extracting common $\;{} \lor q\;$} \hint{-- note that we can leave out one pair of parentheses} (r \land \lnot p) \;\lor\; (\lnot p \land \lnot r) \;\lor\; q \op\equiv\hint{simplify by extracting common $\;{} \land \lnot p\;$} \big((r \;\lor\; \lnot r) \land \lnot p\big) \;\lor\; q \op\equiv\hint{simplify using excluded middle} (\true \land \lnot p) \;\lor\; q \op\equiv\hint{simplify} \lnot p \;\lor\; q \endcalc$$

This completes the proof of the original statement, since we've proven the stronger statement $$ \lnot(r\then p) \;\lor\; \big((\lnot q\then\lnot p) \land (r\then q)\big) \;\;\equiv\;\; \lnot p \;\lor\; q$$

Answer 3

First we prove that $$ \{\neg(r\to p)\lor[(\neg q\to\neg p)\land(r\to q)]\}\iff \neg p \lor q $$ Let $A\iff\{\neg(r\to p)\lor[(\neg q\to\neg p)\land(r\to q)]\}$. Then \begin{align} A&\iff\{\neg(\neg r\lor p)\lor[(\neg q\to\neg p)\land(r\to q)]\}\tag1 \\ &\iff\{(r\land\neg p)\lor[(\neg q\to\neg p)\land(r\to q)]\}\tag2 \\ &\iff\{(r\land\neg p)\lor[(p\to q)\land(r\to q)]\}\tag3 \\ &\iff\{(r\land\neg p)\lor(p\to q)\}\land\{(r\land\neg p)\lor(r\to q)\}\tag4 \\ &\iff\{(r\land\neg p)\lor(\neg p\lor q)\}\land\{(r\land\neg p)\lor(\neg r\lor q)\}\tag5 \\ &\iff\{[r\lor(\neg p\lor q)]\land[\neg p\lor(\neg p\lor q)]\}\land\{[r\lor(\neg r\lor q)]\land[\neg p\lor(\neg r\lor q)]\}\tag6 \\ &\iff\{[r\lor(\neg p\lor q)]\land[\neg p\lor q]\}\land\{[(r\lor(\neg r)\lor q]\land[\neg p\lor(\neg r\lor q)]\}\tag7 \\ &\iff\{[r\lor(\neg p\lor q)]\land[\neg p\lor q]\}\land\{1\land[\neg p\lor(\neg r\lor q)]\}\tag8 \\ &\iff\{[r\lor(\neg p\lor q)]\land[\neg p\lor(\neg r\lor q)]\}\land[\neg p\lor q]\tag9 \\ &\iff\{[r\lor(\neg p\lor q)]\land\{\neg r\lor(\neg p\lor q)\}\land[\neg p\lor q]\tag{10} \\ &\iff\{0\lor(\neg p\lor q)\}\land[\neg p\lor q]\tag{11} \\ &\iff(\neg p\lor q)\land(\neg p\lor q)\tag{12} \\ &\iff\neg p\lor q \end{align} $(1)$ is for $r\to p\iff \neg r\lor p$.

$(2)$ is for De Morgan's law and double negation.

$(3)$ is for $(\neg q\to\neg p)\iff (p\to q)$.

$(4)$ is for distributivity.

$(5)$ is for $r\to q\iff \neg r\lor q$.

$(6)$ is for distributivity.

$(7)$ is for idempotence of disjunction and associativity.

$(8)$ is for $r\lor \neg r\iff 1$.

$(9)$ is for $1\land B\iff B$.

$(10)$ is for associativity and commutativity.

$(11)$ is for distributivity and $r\land \neg r\iff 0$.

$(12)$ is for idempotence of conjunction.

So $$ \{\{\neg(r\to p)\lor[(\neg q\to\neg p)\land(r\to q)]\}\to(\neg p\lor q)\}\iff\{(\neg p\lor q)\to(\neg p\lor q)\} $$ Since \begin{align} \{(\neg p\lor q)\to(\neg p\lor q)\}&\iff\{\neg[(\neg p\lor q)]\lor(\neg p\lor q)\} \\ &\iff\{(p\land \neg q)\lor(\neg p\lor q)\} \\ &\iff\{[(p\lor(\neg p\lor q)]\land [\neg q\lor(\neg p\lor q)]\} \\ &\iff\{[(p\lor\neg p)\lor q)]\land [(\neg q\lor q)\lor \neg p)]\} \\ &\iff\{(1\lor q)\land (1\lor \neg p)\} \\ &\iff\{1\land 1\} \\ &\iff 1 \end{align} $\{(\neg p\lor q)\to(\neg p\lor q)\}$ is tautology. So $$ \{\neg(r\to p)\lor[(\neg q\to\neg p)\land(r\to q)]\}\to(\neg p\lor q)\iff 1 $$ It is tautology too.