Chapter 01: Logic concepts

Methods of proof

Mathematical statements can typically be phrased as an implication, may be complex statements themselves that involve conjunctions (and), disjunctions (or), negations, quantifiers, even implications. There are various ways in which an implication can be proven true, and there is no hard and fast rule that dictates which proof method to use given a particular problem.

Direct proof

A direct proof is one of the most familiar forms of proof. We use it to prove statements of the form ”if then ” or ” implies ” which we can write as . The method of the proof is to takes an original statement , which we assume to be true, and use it to show directly that another

statement is true. So a direct proof has the following steps:

  • Assume the statement is true.

  • Use what we know about and other facts as necessary to deduce that another statement is true, that is show is true.

Example

Let show that, .

Proof by contrapositive

Proof by contrapositive, or proof by contraposition, is a rule of inference used in proofs, where one infers a conditional statement from its contrapositive. In other words, the conclusion "if , then " is inferred by constructing a proof of the claim "if not , then not " instead. More often than not, this approach is preferred if the contrapositive is easier to prove than the original conditional statement itself. We show insted of .

Example

let show that is not divisible by is even.

Proof by contraduction

Proof by contradiction (also known as indirect proof) is a common proof technique that is based on a very simple principle: something that leads to a contradiction can not be true, and if so, the opposite must be true. To show that is true, we suppose that is false and than is true. We show that , when is true. So is true. As is true then is true.

Example

Show that does not admit an inverse in .

By induction

A proof by induction is just like an ordinary proof in which every step must be justified. Let be a logical statement for each . The principe of mathematical induction states that is true all if is true, and for all .

Example

Show that for all , we have .

By giving a counter example

A proof by counter example is not technically a proof. It is merely a way of showing that a given statement cannot possibly be correct by showing an instance that contradicts a universal statement. To show that a proposition is false, we must show that is true.

Example

Show that the proposition:

  1. is false.

  2. with , is false.

To watch the video click here.

PreviousPreviousNextNext
HomepageHomepagePrintPrint Dr. Hind BOUREDJI Public Domain licenceCreated with Scenari (new window)