# Direct proof unclear

1. Oct 23, 2009

### njama

"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. Oct 23, 2009

### Werg22

Which proof system are you using?

3. Oct 24, 2009

### njama

Its called direct proof in propositional calculus.

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

Practically the direct proof is substituting implication in the expression, which I believe is not valid.

4. Oct 24, 2009

### Moo Of Doom

But from S, you should be able to prove S v X for any proposition X.

5. Oct 24, 2009

### njama

I do not understand. Please explain how.

6. Oct 24, 2009

### Moo Of Doom

I don't know how in your particular system, but there's often an axiom of disjunction introduction, similar to the conjunction elimination you've been doing so far:

(conj. elim.) (A ^ B) => A
(disj. intro.) A => (A v B)

7. Oct 25, 2009

### njama

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?

It is not. So why the proof 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.

8. Oct 25, 2009

### njama

Any help, please? Could somebody possibly explain my why the direct proof is valid?

Thank you.

9. Oct 25, 2009

### Moo Of Doom

(~P) ^ (P v Q) implies Q, but it is not equivalent to Q (since Q says nothing about whether or not P holds). Thus, you cannot simply substitute it for (~P) ^ (P v Q) in an expression.

The steps don't need to involve substituting the things into the original formula, but just noting what other statements follow from the premises.

10. Oct 25, 2009

### njama

Yes, the steps does not involve substituting, but it is same like substituting things.

I didn't manage to prove the expression above, because it is something wrong with this direct proof. Just look at my first post and see where I am stuck.

11. Oct 25, 2009

### Moo Of Doom

You were fine up to and including step 5.

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

Then here your next steps should be something like

(6) S -> (S v R) by disjunction introduction
(7) (S v R) ^ (~P) from (6) and (1)

And (7) is what you wanted to prove.

12. Oct 25, 2009

### njama

Thanks.

But you used premise ~P already in step (3).

Is it valid to use it again?

13. Oct 25, 2009

### Moo Of Doom

Of course. You can use a premise as often as you want. It remains true throughout the entire proof.

14. Oct 26, 2009

### njama

And does p,q,s have any truth value, for example. true or false through the process?

Do we suppose from the start that the premises are true?

15. Oct 26, 2009

### Moo Of Doom

Yes, in a direct proof one assumes the premises are true, and derives statements from that.

16. Oct 26, 2009

### njama

Thank you.

And can we prove it like this:

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

t(P->R) = T

t(Q->S)=T

t(~P)=T

t(P v Q)=T

Since the premises are true.

t(P)=F

From t(F v Q) =T, t(Q)=T

From t(T->S)=T, t(S)=T

From t(F->R) = T t(R)=T or t(R)=F

Substituting in the conclusion:

(T v R) ^ (T) <=> T ^ T <=> T

Is this valid?