Validate my reasoning for this logical equivalence

Question

I've basically worked out how to do this question but not sure about my reasoning:

Question:

Show
1) $(p \rightarrow q) \land (q \rightarrow (\lnot p \lor r))$
is logically equivalent to:
2) $p \rightarrow (q \land r)$

and I am given this equivalence as a hint: $u \rightarrow v$ is logically equivalent to $(\lnot u) \lor v)$

My reasoning:

From statement (1): $(\lnot p \lor r)$ is equivalent to $(p \rightarrow r)$ (By the hint given)
Hence statement (1) becomes: $(p \rightarrow q) \land (q \rightarrow (p \rightarrow r))$
We assume $p$ is true, therefore $q$ is true
So $p$ also implies $r$

Therefore $p$ implies $q$ and $p$ also implies $r$
Hence $p \rightarrow (q \land r)$

I understand the basic ideas but I'm really confused as to how I can write it all down logically and clearly

Answer 1

Arvin: your reasoning about the proof is valid.

1) $(p \rightarrow q) \land (q \rightarrow (\lnot p \lor r))$
2) $p \rightarrow q $
3) $q \rightarrow (\lnot p \lor r)$
4) Assume $p$
5) $q$ \from 2 and 4
6) $\lnot p \lor r$ \from 3, 5
7) $p \rightarrow r$ \from 6
8) $r$ \from 4 and 7
9) $q \land r$ \from 5 and 8
10) $p \rightarrow (q \land r)$ \from 4-9

Is that what you were hoping to do? Now your job be to be sure that you understand why each step is justified, for example, Modus Ponens was used 3 times. Technically, in justifying step 10, one needs to refer to the "sub-proof" starting from line 5 and extending to 9. (I would normally indent all that follows from the assumption, and perhaps the assumption itself; you leave the subproof as soon as you recognize the assumption in the conclusion: the "if" part, p. The key is to not make the mistake of concluding only (p and r). What the proof demonstrates is that if p, then (q and r). You can make the substitution of line 7 for six earlier on in the proof, though some strict professors (and authors) scoff at making a direct substitution of an assertion with an equivalent expression while it is still embedded in a larger expression, so I held off to make that substitution until the expression given by 6 was independent (no longer the conclusion of a conditional). If the "then" part of your original "given" was $q \rightarrow (p \rightarrow r)$, then there is no need to use the equivalent expression $\lnot p \lor r$. You can simply skip the substitution and go directly from q, which follows if p is true, to $p \rightarrow r$.

Answer 2

What rules of inference do you have at work here? Do you have any axioms also at work here? In a natural deduction context, amWhy's proof above doesn't seem quite correct in that it uses a discharaged hypothesis at line 8 (it's very close though!). What needs to get done comes as assume p again a second time. Then since we have (p->r) we have p by modus ponens, and we'll get r again. So, in such a context amy's proof would go something more like:

1) ((p→q)∧(q→(¬p∨r))) assumption
2) (p→q) from 1
3) (q→(¬p∨r)) from 1
4)  | p hypothesis
5)  | q from 2 and 4
6)  | (¬p∨r) from 3, 5
7) (p→r) from 4 through 6
8)  | p hypothesis
9)  | r from 7 and 8
10) | q from 8 and 2
11) | (q∧r) from 9 and 10
12) (p->(q^r)) from 8 through 11

That gives you that 1) in the original post implies 2). Now you also need to show that 2) implies 1). I'll take for granted one of the corresponding rules of inference to one of De Morgan laws [from ~(~x v y), we may immediately infer (x^~y)].

1) (p->(q^r)) assumption
2)  | p hypothesis
3)  | (q^r) from 2 and 1
4)  | q from 3
5) (p->q) from 2 through 4
6)  | q hypothesis
7)  || ~(~p v r) hypothesis
8)  || (p^~r) from 7 via De Morgan's laws
9)  || p from 8
10) || ~r from 8
11) || (q^r) from 9 and 1
12) || r from 11
13) || (r^~r) from 10 and 12
14) | (~p v r) from 7 through 13
15) (q->(~p v r)) from 6 through 14.
16) ((p->q)^(q->(~p v r))) from 5 and 15.

Answer 3

Hint:

1. Expand (1) in $\land$ and $\lor$.
2. Simplify...

Answer 4

You always have the solution to break down everything to pieces and to compare the results. For example, $(1)\equiv(3)\land(4)$ with $$ (3)\equiv(p\to q)\equiv(\lnot p)\lor q, $$ and $$ (4)\equiv q \to (\lnot p \lor r)\equiv(\lnot q) \lor (\lnot p) \lor r. $$ Expanding $(3)\land(4)$ into six factors and canceling the impossible factor $q\land (\lnot q)$ yields $$ (1)\equiv((\lnot p)\land (\lnot q))\lor(\lnot p)\lor((\lnot p)\land r)\lor(q\land (\lnot p))\lor(q\land r). $$ The four first terms are equivalent to $\lnot p$, hence $$ (1)\equiv(\lnot p)\lor(q\land r)\equiv(p\to(q\land r))\equiv(2). $$

Answer 5

There are several routes to a proof, I will list two:

1) You can make a list of all cases. Since you have three variables, there are 8 possibilites for them to have the values true/false.

You can make a table with column titles: $p,q,r,p \to q, \lnot q \lor p, \dots$ and enter the truth values, then compare the columns for the two expression you want to be equivalent.

2) As indicated by the hint, you can transform all occurences of $\to$ to $\lor$.

Then you can use the distributivity to bring both expression to a normal form, for example to conjunctive normal form http://en.wikipedia.org/wiki/Conjunctive_normal_form

Answer 6

Here is yet another way to do this, this time using the Dijkstra-Scholten-Gries-etc. calculational proof format. We will start with the most complex side, then (as in other answers to this question) expand $P \rightarrow Q$ to $\lnot P \lor Q$, and then simplify and see where that leads us. \begin{align} & (p \rightarrow q) \land (q \rightarrow \lnot p \lor r) \\ \equiv & \;\;\;\;\;\text{"expand $\rightarrow$, twice"} \\ & (\lnot p \lor q) \land (\lnot q \lor \lnot p \lor r) \\ \equiv & \;\;\;\;\;\text{"simplify: factor out $\lnot p$, using the fact that $\lor$ distributes over $\land$"} \\ & \lnot p \lor (q \land (\lnot q \lor r)) \\ \equiv & \;\;\;\;\;\text{"simplify: use $q$ in other side of $\land$"} \\ & \lnot p \lor (q \land (\lnot \textrm{true} \lor r)) \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \lnot p \lor (q \land r) \\ \equiv & \;\;\;\;\;\text{"reintroduce $\rightarrow$ -- inspired by the shape of our goal"} \\ & p \rightarrow q \land r \\ \end{align}

This proves the equivalence.