# 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

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.

• Please write up your questions using proper formatting. It makes it much easier to see what issues you are having. Sep 29, 2015 at 4:52

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}

• On line 1, I am not understanding how the negation is acting upon the the stuff inside { }. I thought the negation was acting only acting on ${\neg(r\to p)}$ and not the the stuff inside { }. Sep 29, 2015 at 20:47
• @KapookyHandy I'm not sure I understand your question. Regardless of how big/complex your compound propositions are, we will always have $\Omega\to\Psi\equiv\neg\Omega\lor\Psi$. That is, $\Omega$ can be something big and complicated like your expression inside of the curly braces. How the negation acts "inside" of the curly braces is largely going to be due to De Morgan isn't it? Try to really work through each step of the proof I gave. See if you can pull it all together (btw, "dom" stands for "domination"). Sep 29, 2015 at 20:52
• okay I understand this. Sep 30, 2015 at 20:17


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$$

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.

• Yes, i have... :) Sep 30, 2015 at 20:18
• I did not downvote Oct 1, 2015 at 2:03