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

  • 0
    You do *not* assume that $p$ is true.2011-04-29
  • 0
    Really? I was taught when proving things like this you can assume stuff..2011-04-29
  • 1
    Only if you assume all possible cases, but you cannot just assume whatever you like. Certainly, you can assume the truth of $p$ while just proving 1) implies 2), but firstly, this is a very restrictive method that only works because 2) is of a very special form, and secondly, it does not prove 2) implies 1)2011-04-29
  • 0
    I see, thanks for that2011-04-29
  • 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
    This shows that $(p\to q)\land(q\to(\neg p\lor r))$ implies $p\to(q\land r)$. Technically, to prove the equivalence you now either have to argue that all steps are "reversible", or prove the other implication as well.2011-04-30
  • 0
    Thanks, Amy, that's exactly what I was going for, I just wasn't sure about how I should write it down clearly and logically. This is exactly what I was looking for! @Arturo: My uni professor is a little strict about us being clear in our reasoning, however there has been no mention of reversible steps so I believe I would be safe to conclude the reasoning where Amy left off2011-04-30
  • 1
    @Arvin: The issue is that the argument given here only shows that the first formula implies the second. But your question states that you need to prove the two formulas are **logically equivalent**. That means that you *also* need to show that the second formula implies the first. So this answer (and your original answer in the post) is only *half* of the work needed.2011-04-30
  • 0
    ohh I see what you mean, so how would you prove the second also implies the second? by using the hint given i can change the second statement to be $\lnot p \lor (q \land r)$ but not sure what to do from there2011-04-30
  • 1
    Yes, Arvin. Your reasoning was "on the right track." But you need to prove the first statement follows from, or can be derived from, the second. Suggestion: Why don't you show what you can derive if you start with the second statement.2011-04-30
  • 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). $$

  • 0
    How did you expand (3) and (4)? That part confused me2011-04-29
  • 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
    @AmWhy No, it didn't come out in the format I wanted before, and I didn't know how to change it. The proofs looked something like this: "1) Kpq assumption 2) p K-out 3)q K-out 4) Kqp K-in 5) CKpqKqp C-in" instead of how they look now. I find the column format of the edited post easier to follow than the format of the last sentence, as I believe you follow writing with paragraphs and spaces more easily than the ancient writing style wherewehavenospacesnopunctuationandnoparagraphs. As another example, we could write all finite matrices like this (a, b, c, d). But then disnguishing a...2011-06-16
  • 0
    @AmWhy matrix from a vector isn't quite so intuitive. Since (a, b, c, d) looks like a vector with 4 spots for numbers, but it actually represents what more often gets called a 2x2 matrix, which can get thought of representing 2 column and 2 row vectors.2011-06-16
  • 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.