Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
You do not assume that $p$ is true. –  Phira Apr 29 '11 at 9:06
    
Really? I was taught when proving things like this you can assume stuff.. –  Arvin Apr 29 '11 at 12:37
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) –  Phira Apr 29 '11 at 12:48
    
I see, thanks for that –  Arvin Apr 29 '11 at 13:23
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). –  amWhy Apr 29 '11 at 20:07

6 Answers 6

up vote 6 down vote accepted

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

share|improve this answer
    
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. –  Arturo Magidin Apr 30 '11 at 2:48
    
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 off –  Arvin Apr 30 '11 at 3:16
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. –  Arturo Magidin Apr 30 '11 at 3:24
    
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 there –  Arvin Apr 30 '11 at 4:29
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. –  amWhy Apr 30 '11 at 12:51

Hint:

  1. Expand (1) in $\land$ and $\lor$.
  2. Simplify...
share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
How did you expand (3) and (4)? That part confused me –  Arvin Apr 29 '11 at 12:34
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. –  Did Apr 29 '11 at 20:14

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.
share|improve this answer
    
@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... –  Doug Spoonwood Jun 16 '11 at 0:18
    
@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. –  Doug Spoonwood Jun 16 '11 at 0:23
    
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...] –  amWhy Jun 16 '11 at 0:48

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.