4
$\begingroup$

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

  • 1
    Arvin, it's not inappropriate, in cases like this, when you are trying to prove a conditional, as in (2), to assume the antecedent. After all, you are to show that "IF$p$is true, then (q and r) is true. So your proof can proceed directly by assuming p, deriving both q and r from that assumption and from what you know in (1), connecting q and r through conjunction, and then concluding that, yes in fact, If p, then (q and r).2011-04-29

6 Answers 6

5

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

  • 0
    Hint: remember that if you have a "given" statement, or one that can logically follows from other the given, or from other derived statements, you can "build up" the statement by adding "$\lor x$", where "x" can be anything whatsoever. Why? Because if, for example, you know that, or have proven that "y" (is true), then no matter what "x" is, $x \lor y$ [or alternatively, $y \lor x$] will be true simply by virtue that "y" (is true).2011-04-30
1

Hint:

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

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

  • 1
    $(3)\equiv a\lor b$ (2 terms) and $(4)\equiv c \lor d\lor e$ (3 terms) hence $(3)\land(4)\equiv (a\land c)\lor(a\land d)\lor(a\land e)\lor(b\land c)\lor(b\land d)\lor(b\land e)$ ($2\times 3=6$ terms), by distributivity.2011-04-29
1

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. 
  • 0
    Fair enough...I should have let it go...I have revisited my own answers to edit/improve formatting, add details, etc. I'll delete my comment. [You don't need to delete yours...it's pretty self-explanatory, despite the ping t.o me...]2011-06-16
0

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

0

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.