# Trying to show Tautology

I'm trying to show that this current sentence is tautologic:

[(p∨q)∧(p⇒r)∧(q⇒r)]⇒r


Now I did some calculations and reached this

(¬p∧¬q)∨(p∧¬r)∨(q∧¬r)∨r


Now I'm trying to use Absorption bad unfortunately it does not apply for when you are dealing with a Negation. How should I approach this (final solution is not necessary, more interested in knowing the tools I should use and/or what am I missing)

-
Why not just write a truth table for your first line, and see if the statement is always true? –  JavaMan Nov 2 '11 at 12:45
not allowed to use truth table, this is a task I have to do, and it is why I don't want to see the final answer but just the way I need to solve it (tools,equations, whatever) –  Asaf Nov 2 '11 at 12:51
That looks like a task for the homework tag. –  Henning Makholm Nov 2 '11 at 13:19
Use one of the distributive laws on $(q\land\lnot r)\lor r$ to get $(q\lor r)\land(\lnot r\lor r)$; this simplifies to $(q\lor r)\land\top$ and then to $q\lor r$. With repeated simplifications of this type you can reduce it to $r\lor\lnot r$ and thence to $\top$. –  Brian M. Scott Nov 2 '11 at 13:20

Let $s$ denote $p\lor q$. Then $\lnot s$ is $\lnot p\land \lnot q$ and $(p\land \lnot r)\lor(q\land \lnot r)$ is $(p\lor q)\land \lnot r$ hence one is looking at $(\lnot s)\lor(s\land \lnot r)\lor r$. This is also $(\lnot s\lor r)\lor(s\land \lnot r)$. But if $t$ is $(\lnot s\lor r)$, $\lnot t$ is $s\land \lnot r$ hence one is considering $t\lor \lnot t$, which is a tautology.

-

After I applied $(p\Rightarrow r) \Leftrightarrow (\lnot p \lor r)$ and $(q\Rightarrow r) \Leftrightarrow (\lnot q \lor r)$ I have reduced sentence to the following expression:

$((q\Rightarrow p)\land r)\Rightarrow r$

Now let's denote: $T(r)$ as truth value of $r$

$a)$ if $T(r)=\bot \Rightarrow T((q\Rightarrow p)\land r)=\bot$

so we have $\bot \Rightarrow \bot$ which is $\top$

$b)$ if $T(r)=\top \Rightarrow T((q\Rightarrow p)\land r)=T(q \Rightarrow p)$

so we have: $T(q \Rightarrow p)\Rightarrow \top$

which is always $\top$ doesn't matter what value of $T(q \Rightarrow p)$ is.

-
what does ⊥ mean ? False ? –  Asaf Nov 4 '11 at 10:32
yes,that is common notation.. –  pedja Nov 4 '11 at 10:37

[(p∨q)∧(p⇒r)∧(q⇒r)]⇒r

[(p∧(p⇒r)∧(q⇒r))∨[(q∧(q⇒r)∧(p⇒r)]⇒r

[r∨r]⇒r

-