1. "A direct proof is a proof in which the truth of the premises of a theorem are shown to directly imply the truth of the theorem's conclusion."

Here are the premises:
(P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q)

and the conclusion:

(S v R) ^ (~P)

Now what I do not understand why we are using expressions that are implications are not equivalency?

Let me start the prrof.

(1) ~P premise
(2) P v Q premise
(3) From discjunctive simplification we got:
(P v Q) ^ (~P) -> Q
(4) (Q->S) premise
(5) From detachment i.e (Q->S) ^ Q -> S
(6) P -> R premise
(7) from (6) ~P v R

And I didn't come up with the conclusion? What is the problem with this direct proof?

Shouldn't I use equivalent expressions and not implications?   2.

3. If the problem statement uses implications, then you should use implications. I think what's throwing you off here is the ~P, since it looks like you don't really need it beyond having it show back up in the conclusion.  4. Originally Posted by MagiMaster
If the problem statement uses implications, then you should use implications. I think what's throwing you off here is the ~P, since it looks like you don't really need it beyond having it show back up in the conclusion.
What really trows me off is substituting implications as they were equivalences. For example. the following proof needs to be done:

(p -> r) ^ (q -> s) ^ (p v q ) => (s v r)

The proof goes like (1)-(5) steps doing this:

(p->r) ^ (~p->q) ^ (q->s) => (s v r) (this is valid because (p v q) <=> ~p -> q)

Now they do:

(p->r)^(~p->s) => (s v r) (substituting (~p->q) ^ (q->s) -> (~p ->s) which is not equivalency)

Now

(p->r) ^ (~s -> p) => (s v r) (using ~p -> s <=> ~s -> p)

(~s -> r) => (~s ->r)

How is the second and third steps valid?  5. Can you be more specific? They look fine ot me. You can still have transitivity without having commutitivity. ((p -> q) ^ (q -> r)) -> (p -> r) still works without equivalence. Anyway, if the implications are throwing you off, you showed a transformation to get rid of them.  6. Originally Posted by MagiMaster
Can you be more specific? They look fine ot me. You can still have transitivity without having commutitivity. ((p -> q) ^ (q -> r)) -> (p -> r) still works without equivalence. Anyway, if the implications are throwing you off, you showed a transformation to get rid of them.
I don't know how to explain you.

But the real problem is not every time implication works as same as equivalency.

For ex.

The first proof.

(P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (S v R) ^ (~P) (tautology)

When substituting (P v Q) ^ (~P) -> Q

like

(P -> R) ^ (Q -> S) ^ Q-> (S v R) ^ (~P) is not tautology

That's the problem.  7. I guess I'm still not understanding the problem exactly, but maybe it's due to having transitivity but not commutativity, so you might have (a->b)^(a->c)^(b->d)^(c->e), so (a->d) and (a->e), but it doesn't say anything about how d and e relate to each other.  8. Originally Posted by MagiMaster
I guess I'm still not understanding the problem exactly, but maybe it's due to having transitivity but not commutativity, so you might have (a->b)^(a->c)^(b->d)^(c->e), so (a->d) and (a->e), but it doesn't say anything about how d and e relate to each other.
Lets say the expression we need to prove is:

(~p v q) ^ (s v p) ^ (~q) -> s

using a direct proof.

(~p v q), (s v p), (~q) - premises

s - conclusion

Ok. Here is how to direct proof goes like:

(1) ~p v q Premise
(2) ~q Premise
(3) ~p Disjunctive simplification, (1),(2)
(4) s v p Premise
(5) s Disjunctive simplification (3),(4) #

Disjunctive simplification is: (p v q) ^ (~q) -> p

The expression is:

(~p v q) ^ (s v p) ^ (~q) -> s

Now, analog to the steps of the direct proof:

(~p v q) ^ (~q) ^ (s v p) -> s

(3) Disjunctive simplification of (~p v q) ^ (~q) -> (~p)

(~p) ^ (s v p) -> s

(4) Disjunctive simplification of (~p) ^ (s v p) -> s

s -> s #

Do you understand now what I am talking about??  9. Well, I follow both of those, but I still don't see the problem.  10. Originally Posted by MagiMaster
Well, I follow both of those, but I still don't see the problem.
Ok, my question is:

(P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (S v R) ^ (~P)

Would be correct to substitute

(~P) ^ (P v Q ) -> Q as it is equivalent expression to Q as follows (because of disjunctive simplification):

(P -> R) ^ (Q -> S) ^ Q -> (S v R) ^ (~P)

?? Is this valid?  11. I think I see the problem. I think you need to substitute (~p)^(q) for (p v q)^(~p). While (p v q)^(~p) implies (q), it's not equivalent, so you can't plug it in to the left side of some other implication and expect the implication to remain unchanged. At least, that's my understanding.  12. Originally Posted by MagiMaster
I think I see the problem. I think you need to substitute (~p)^(q) for (p v q)^(~p). While (p v q)^(~p) implies (q), it's not equivalent, so you can't plug it in to the left side of some other implication and expect the implication to remain unchanged. At least, that's my understanding.
Exactly. Sometimes it works, but not necessarily works...

That's what direct proof does.

But still can't understand. In my text book says:

(1) A proof must end in a finite number of steps.

(2) Each step must be either a premise or a proposition that is implied from previous steps using any valid equivalence or implication.

(3) For a direct proof, the last step must be the conclusion of the theorem.

The (2) says that.  Anyone to try to prove:

(P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (S v R) ^ (~P)

with direct proof ?  14. No, that's not what 2 says. It says you need a chain of implications, but you can't just make a substitution like that in the middle of such a chain. You could make a different chain that includes that substitution though.  15. Originally Posted by MagiMaster
No, that's not what 2 says. It says you need a chain of implications, but you can't just make a substitution like that in the middle of such a chain. You could make a different chain that includes that substitution though.
Could you please give me an example?

Thank you.  16. You have:
- (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (S v R) ^ (~P)
And:
- (~P) ^ (P v Q) -> (Q)
So:
- (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (P -> R) ^ (Q -> S) ^ (Q)
But not:
- (P -> R) ^ (Q -> S) ^ (Q) -> (S v R) ^ (~P)

On the other hand:
- (~P) ^ (P v Q) <=> (~P) ^ (Q)
So:
- (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) <=> (P -> R) ^ (Q -> S) ^ (~P) ^ (Q)
And this works now:
- (P -> R) ^ (Q -> S) ^ (~P) ^ (Q) -> (S v R) ^ (~P)

Or sticking with just implications:
- (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (P -> R) ^ (Q -> S) ^ (Q)
And:
- (P -> R) ^ (Q -> S) ^ (Q) -> (P -> R) ^ (Q) ^ (S)  Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement