Kukuh Setiawan. Theme images by centauria. Powered by Blogger.

Tuesday, February 10, 2009

logic direct proof


Method of Direct Proof

The most important form of direct proof is the syllogism, which has been around as a principle of logic since the days of Aristotle. The reasoning behind this form of proofs is as follows. Suppose it is known that

If the light is on, then all is well.


If he is there, then the light in on.

By most primitive of logical notions you would conclude

If he is there, then all is well.

This kind of reasoning is called syllogistic reasoning. It is important to note that the validity of the above argument (or this kind of arguments) resides only in its form and not its contents, in its structure and not its truth. To see why this is the case, let us formalize the notion.


Let p, q, and r be any three propositions. The proposition

((p → q) ∧ (q → r)) → (p → r)

has a truth value of T, no matter what be the truth values of p, q and r.

One conclusion we can draw from the above statement is that to utter logically valid argument, to make sense we need not know what what the hell we are talking about. Just pick any three propositions p, q and r and remark

If p implies q and q implies r, then p implies r

and we will be making sense, though perhaps not be recognized sensible!

Because of this property, the syllogism is the most frequent logical form found in mathematics (as well as in everyday life.) To recognize its validity, consider the following example:

To show that n is true proposition it suffice to do two things:

1. Find a proposition m such that m → n is true.

2. Show m is true.

Now suppose we have accomplished 1 and 2, then the claim that n must be true proposition can be shown using following argument: Because of (2), the possibilities for the implication m → n are restricted to only two rows of the truth table for implication. And, because of (1), only one row remains pertinent. But in this row, n is true. And we are done.

Now let me support my statement about "this" being most frequent logical form in mathematics by saying something about the fundamental problem of mathematics and then we will jump directly into the proofs (or precisely demonstrations). Given two propositions (or mathematical statements, if you haven't visited my logic page yet) P and Q, each of which may be true or false, a fundamental problem in mathematics is to show (i.e. to demonstrate - see logic page) that following statement (implication):

if P is true, then Q is true

is true.

There are, of course, many many reasons (approximately equals to the number of present and past mathematicians), but for me the very basic reason to prove that the above implication is true is as follows:

Suppose we have two statements, P and Q. And we want B to be true but it is not easy to verify the truth of Q (or in the worst case, we don't know how to verify the truth of Q.) In contrast, we know P is true (or it is easy verify the truth of P.) One way to do this is to prove the statement:

If P is true, then Q is true

In other words, show the implication:

If P is true, then Q is true

is true.

Now if we know that P is true (or can verify that P is true), then we will know that Q is true.

[If you have no idea what the hell I am talking about or need to refresh some fundamental concepts of logic, you are most welcome to visit my logic page.]

Let us formalize (a little bit) the above discussion. Suppose P and Q are propositions that are either true or false. The problem is to prove that

P implies Q

is true. In order to do so,

1. Assume that proposition P is true. [Make it an axiom temporarily.]

2. Using this assumption [and all other theorems and axioms] try to deduce proposition Q.

Once Q is deduced in this manner you have completed the proof of (P implies Q).

It is very very important to understand what you have done. You have NOT shown that proposition Q is true. Please let me repeat this again: YOU HAVE NOT SHOWN THAT PROPOSITION Q IS TRUE. You have only shown that proposition Q is true if proposition P is true. [Whether proposition P is true is irrelevant here and more importantly whether proposition Q is really true is also completely irrelevant.] What you have really shown to be true is (P implies Q). Let me repeat this again: All you have shown is "P implies Q is TRUE." Not p is true - Not q is true BUT p implies q is true.

At this point, you might want to refresh the idea of "Deduction Theorem."

Write comments


Label 2


Contact Us


Email *

Message *