direct proof unclear

[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?

:confused:

Please help

[Werg22]

Which proof system are you using?

[njama]

Which proof system are you using?

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.

[Moo Of Doom]

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

[njama]

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

I do not understand. Please explain how.

[Moo Of Doom]

I don't know how in your particular system, but there's often an axiom of disjunction introduction (http://en.wikipedia.org/wiki/Disjunction_introduction), similar to the conjunction elimination you've been doing so far:

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

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

[njama]

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

Thank you.

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

[njama]

(~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.

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.

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

[njama]

Thanks.

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

Is it valid to use it again?

[Moo Of Doom]

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

[njama]

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

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?

[Moo Of Doom]

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

[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?