0

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)

hmakholm left over Monica
  • 286,031
Asaf
  • 183
  • Why not just write a truth table for your first line, and see if the statement is always true? – JavaMan Nov 02 '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 02 '11 at 12:51
  • 1
    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 02 '11 at 13:20

3 Answers3

2

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.

Did
  • 279,727
1

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.

Pedja
  • 12,883
0

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

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

[r∨r]⇒r

Angela Pretorius
  • 10,200