Direct Proof Indirect Proof Contradiction Philosophy Essay

For this mini project, we have been given a project title to be discussed that is Types of proof in Logic which are direct proof, indirect proof, contradiction and contrapositive. Mathematical logic is a subfield of mathematics that close up to computer science and philosophical logic. This topic is divided into two parts which are the study of mathematical of logic and the applications of logic in computer science and to other areas of mathematics. This topic also covering the study of the expressive power of formal systems and the deductive power of formal proof systems.

In the field of information technology, logic have been used for a long time and the emergence of Mathematical logic is in the mid-19th century as a subfield of mathematics which is free from traditional study of logic. Before this emergence, logic was studied together with rhetoric, through the syllogism, and with philosophy. The explosion of fundamental results and accompanied by vigorous debate over the foundations of mathematics occured in the first half of the 20th century.

The history of logic is the study of the development of the science of valid inference. Meanwhile, only in three traditions that are China, India and Greece development of many cultures have employed intricate systems of reasoning, and logical methods are evident in all human thought, an explicit analysis of the principles of reasoning. With these, only the treatment of logic descending from the Greek tradition, particularly Aristotelian logic, found wide application and acceptance in science and mathematics. Logic was known as dialectic or analytic in Ancient Greece.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

Islamic and medieval European logicians did further development for Aristotle’s logic thus it was getting a high point in the mid-fourteenth century. Between the fourteenth century and the beginning of the nineteenth century, there was largely one of decline and neglect, and is generally regarded as barren by historians of logic. Logic was back in the mid-nineteenth century, logic was revived.

INTRODUCTION

Logic is the study of reasoning, it is specially concerned with whether reasoning is correct. Furthermore, logic focuses on the relationship among statements as opposed to the content of any particular statement. Technically, logic is one of no help in determining whether any of these statements is true. Logic is essential in reading and developing proofs. Logical methods are used in mathematics to prove theorems and in computer science to prove that programs do what they are alleged to do.

Contraposition is one of the types of proof in logic. It was described as a logical relationship between two propositions, or statements. Meanwhile, direct proof can show the sum of two integers numbers is always even.

RESULTS OF THE RESEARCH

The example of Direct Proof and Counterexample

To determine whether a mathematical statement is correct or not, we must understand what the statement means. We can do so by looking at the definitions below:

D E F I N I T I O N S

Even

An integer n is even, if and only if, n = 2k for some integer k. Symbolically, if n is an integer, then

n is even http://users.csc.tntech.edu/~srini/DM/symgifs/2way.gif  http://users.csc.tntech.edu/~srini/DM/symgifs/fs.gifan integer k such that n = 2k.

Odd

An integer n is odd, if and only if, n = 2k + 1 for some integer k. Symbolically, if n is an integer, then

n is odd http://users.csc.tntech.edu/~srini/DM/symgifs/2way.gif  http://users.csc.tntech.edu/~srini/DM/symgifs/fs.gifan integer k such that n = 2k + 1

Prime

An integer n is prime, if and only if, n > 1 and for all positive integers p and q, if n = p * q, then p = 1 or q = 1. Symbolically, if n is a positive integer, then

 n is prime http://users.csc.tntech.edu/~srini/DM/symgifs/2way.gif  http://users.csc.tntech.edu/~srini/DM/symgifs/fa.gifpositive integers p and q, if n = p * q then p = 1 or q = 1.

Composite

An integer n is composite, if and only if, n = p * q for some positive integers p and q with p http://users.csc.tntech.edu/~srini/DM/symgifs/noteq.gif1 and q http://users.csc.tntech.edu/~srini/DM/symgifs/noteq.gif1. Symbolically, if n is an integer, then

 n is composite http://users.csc.tntech.edu/~srini/DM/symgifs/2way.gifhttp://users.csc.tntech.edu/~srini/DM/symgifs/fs.gifpositive integers p and q such that n = p * q 

and phttp://users.csc.tntech.edu/~srini/DM/symgifs/noteq.gif1 and q http://users.csc.tntech.edu/~srini/DM/symgifs/noteq.gif1.

DIRECT PROOF AND INDIRECT PROOF

Obtaining a conclusion logically by combining the axioms, definitions, and earlier theorems is actually the direct proof. To establish that the sum of two even integers is always even. (Look at the example provided).

Direct proof in mathematics and logic is a way of showing the truth or falsehood of a given statement by a combination of certain facts, without making any further assumptions. To obtain a statement that is directly prove a conditional statement of the form “If p, then q”, it is necessary to consider the situations in which the statement p is true. Logical deduction is employed to reason from assumptions to conclusion. The type of logic employed is almost invariably first-order logic, employing the quantifiers for all and there exists. Common proof rules used are modus ponens and universal instantiation.

Another proof is an indirect proof may start with certain hypothetical situations and then continue to eliminate the uncertainties in each of these situations until an inescapable conclusion is forced. For example instead of showing directly p → q, one proves its contrapositive ~q → ~p (one assumes ~q and shows that it leads to ~p). Since p → q and ~q → ~p are equivalent by the principle of transposition (see law of excluded middle), p → q is indirectly proved. Proof methods that are not direct include proof by contradiction. Direct proof methods include proof by exhaustion, proof by infinite descent, and proof by induction.

Proving conditional assertions: The direct method

Method: To prove “If P, then Q”  assume P is true and deduce that Q must be true as well.  This form of proof is called the direct method.

Note:  In the process of proving Q, you would expect to use other facts that you know as well as the assumption that P is true.

Remember that the integer n is even if there is an integer m for which n = 2m.

Theorem

If n is even, then n2 is even.

Narrative proof by the direct method

Suppose that n is even. Then by definition of “even” there is an integer m for which n = 2m. Then http://www.abstractmath.org/MM/MMFormsProof_files/eq0002M.gif . 2m2 is an integer because m is an integer, so by definition of “even”, n2 is even.

Examples of Indirect Proof

Sum of 2n even numbers is even, where n > 0. Prove the statement using an indirect proof.

The first step of an indirect proof is to assume that ‘Sum of even integers is odd.’

That is, 2 + 4 + 6 + 8 + . . . .+ 2n = an odd number

⇒2 (1 + 2 + 3 + 4 + . . . + n) = an odd number

⇒2 Ã- = an odd number

⇒n(n + 1) = an odd number, a contradiction, because n(n + 1) is always an even number. Thus, the statement is proved using an indirect proof.

Prove the following statement using an indirect proof:

ΔLMN has at most one right angle.

Assume ΔLMN has more than one right angle. That is, assume that angle L and angle M are both right angles. If M and N are both right angles, then m∠L = m∠M = 90 . m∠L + m∠M + m∠N = 180 [The sum of the measures of the angles of a triangle is 180.] Substitution gives 90 + 90 + m∠N = 180. Solving gives m∠N = 0. This means that there is no ΔLMN, which contradicts the given statement. So, the assumption that ∠L and ∠M are both right angles must be false.Therefore, ΔLMN has at most one right angle.

CONTRADICTION AND CONTRAPOSITIVE

p and http://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char3A.pngp are shown to be true as a statement of contradiction (also known as reduction), which is proving a statement by showing its negation is true and logically deducing an absurd statement. That is, in attempting to prove q , one may assume http://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char3A.pngq and attempt to obtain a statement of the form http://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char3A.pngr , where r is a statement that is assumed or known to be true.

It may cause someone to become confused. This is especially the case when such proofs are nested; i.e., a proof by contradiction appears within a proof by contradiction. Some mathematicians prefer to use a direct proof, which is easier to follow in general. It should be pointed out that something good can be said for proof by contradiction: If one wants to prove a statement of the form phttp://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char29.pngq , using the technique of proof by contradiction gives an additional hypothesis with which to work.

Contrapositive may give an implication of the form phttp://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char29.pngq

(“p implies q”) the contrapositive of this implication is http://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char3A.pngqhttp://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char29.pnghttp://planetmath.org/js/jsmath/fonts/cmsy10/alpha/144/char3A.pngp (“not q implies not p”).

Lets take one example, it is true proposition : “All flowers are plants”. We can restate that as : “If something is a flower, it is a plant”. The contrapositive is : ” If something is not a plant, then it is not a flower”. In mathematics and logic, the contrapositive is assured to be true, as long as the original proposition was true. If the proposition is not true, then the contrapositive will always be not true as well.

The contradiction is “There exists a flower that is not a plant”. If the contradiction is true, the original proposition is false and of course the contradiction is false.

SIMPLE PROOF BY CONTRADICTION

Suppose that it is given that

(A to B)and neg B

If A is true, then B is true, and given that B is not true. A must not be true by contradiction. were A is not true (assuming that we are dealing with concrete statements that are either true or not true), and we have that

(A to B) to (neg B to neg A)

We can apply the same process the other way round:

We also know that B is either true or not true. If B is not true, then A is also not true. However, it has just been given that A is true, so assuming that B is not true leads to contradiction and must be false. Therefore, B must be true, and we have proved that:

(neg B to neg A) to (A to B)

Combining the two proved statements gives:

(A to B) iff (neg B to neg A)

Which makes them logically equivalent.

SIMPLE PROOF BY CONTRAPOSITIVE

If something is in A, it must be in B, as well:

(A to B)

It is also clear that anything that is not within B cannot be within A, either. This statement, is the contrapositive.

(neg B to neg A)

Therefore we can say that,

(A to B) ≡ (neg B to neg A)

To conclude, for ANY statement where A implies B, then not-B ALWAYS implies not-A.

CONCLUSIONS AND RECOMMENDATIONS

As conclusions, this topic of types of proof helps us to think and link what we have learnt in the module of discrete mathematics in computer science and information technology. From the given topic, we have been doing some research about direct proof, indirect proof, contradiction and contrapositive. Furthermore, by doing this mini project we have to investigate the application of the types of proof in computer science also in the areas of information technology.

For examples, a student is assigned a program to compute shortest paths between cities. The student must do a program that must be able to accept as input an arbitrary number of cities and the distances between the cities directly connected by roads and produce as output the shortest paths between the cities. After the student writes the program, it is easy to test it for a small number cities. The student also can do brute-force solutions to find the paths. But for a large numbers of cities the brute-force technique would take too long. The student will have to use logic to prove that the program is correct. These types of proof are used in mathematics to prove theorems and in computer science to prove that programs do what they are alleged to do. After doing this mini project we can see how it can be applied in computer programming.

For the recommendation to improve the learning of this topic, both of us think that lecturer should give more examples and ways how to solve the problems while in the lectures so that students can understand the topic on that time. Moreover, lecturers can show the application of this topic in computer programming by doing some programming that related to the topic in the lectures so that students can be more clear how to use it in computer programming. Specials thanks to Prof. Dr. Haslina for giving guidelines to us to do well in this mini project of discrete mathematics.