Previous person gave back to me at the last minute so I am in a bind and need it done quickly.

5. Prove the following: If n is an odd integer then n2 is an odd integer. (This is #4, pg. 8, week 3 of the notes.)

6. Assume that n is a positive integer. Use the proof by contradiction method to prove and explain:

If 3n + 2 is an even integer then n is an even integer. (This is #3, pg. 11, week 3 of the notes.)

7. Let A = {1,2,3,5} and B = {2,6}, with the universal set U = {1,2,3,4,5,6,7,8,9}.

Compute

(a) A – B

(b) A2 (this is the cross product)

(c) A B ⊕

(d) A (B – A) ∩

(e) A

8. (10 pts.) A bit string is a string of bits (0’s and 1’s). The length of a bit string is the number of bits in the string. An example, of a bit string of length four is 0010. An example, of a bit string of length five is 11010. Use the Rule of Products to determine the following:

(a) How many bit strings are there of length eight? Explain

(b) How many bit strings are there of length eight which begin with a 1 and end with a 0? Explain

(c) How many bit strings are there of length eight with even parity (an even number of 1’s)? Explain

For your information question 8 part a could have been stated the following way. Computers use bit strings of length 8, called bytes, to represent the characters (letters both upper case and lower case, punctuation symbols, [, {, the integers 0 through 9 etc) on a key board. The Extended ASCII code is one such coding system. Some examples of this code are: “a” is represented by 01100001, “A” is represented by 01000001 and “{“ is represented by 01111011 and the number 1 is represented by 00000001. How may such symbols can be described using a byte?

9. (10 points) “If a < .7 and b < .7 then a + b <1”

a. Write the converse of this statement. Is the converse true? Explain.

b. Write the contrapositive of this statement. Is the contrapositive true? Explain.

10. (10 points ) Express the following in English and then determine if each statement is true: Explain fully.

(a) ∃x∈Z (x2 = 4).

(b) ∀ y∈R (y 5) ≥

(c) ∀x∈R ∃y∈R x + y = 3.

11. How many bit strings of length n are palindromes? Hint: Consider two cases n is even and n is odd. Note a palindrome is a “string” of letters or numbers which read the same “frontwards” and backwards”. Examples: MOM, 1101011, 10111101 are palindromes.

1

Week 3: Section 1.4 Predicates and Quantifiers

Assume that the universe of discourse is all the people who are participating in

this course. Also, let us assume that we know each person in the course. Consider the

following statement: “She/he is over 6 feet tall”. This statement is not a proposition

since we cannot say that it either true or false until we replace the variable (she/he) by a

person’s name. The statement “She/he is over 6 feet tall” may be denoted by the symbol

P(n) where n stands for the variable and P, the predicate, “is over six feet tall”. The

symbol P (or lower case p) is used because once the variable is replaced (by a person’s

name in this case) the above statement becomes a proposition.

For example, if we know that Jim is over 6 feet tall, the statement “Jim is over six

feet tall” is a (true) proposition. The truth set of a predicate is all values in the domain

that make it a true statement. Another example, consider the statement, “for all real

numbers x, x2 –5x + 6 = (x – 2) (x – 3)”. We could let Q(x) stand for x2 –5x + 6 = (x – 2)

(x – 3). Also, we note that the truth values of Q(x) are indeed all real numbers.

Quantifiers:

There are two quantifiers used in mathematics: “for all” and “there exists”. The

symbol used “for all” is an upside down A, namely, . The symbol used for “there

exists” is a backwards E, namely, . We realize that the standard, every day usage of the

English language does not necessarily coincide with the Mathematical usage of English,

so we have to clarify what we mean by the two quantifiers.

For all For every For each For any

There exists at least one There exists There is Some

The table indicates that the mathematical meaning of the universal quantifier, for

all, coincides with our everyday usage of this term. However, the mathematical meaning

of the existential quantifier does not. When we use the word “some” in everyday

language we ordinarily mean two or more; yet, in mathematics the word “some” means at

least one, which is true when there is exactly one.

The Negation of the “For all “Quantifier:

Consider the statement “All people in this course are over 6 feet tall.” Assume it

is false (I am not over six feet tall). How do we prove it is false? All we have to do is to

point to one person to prove the statement is false. That is, all we need to do is give one

counterexample. We need only show that there exists at least one person in this class

who is not over 6 feet tall. Here is a more formal procedure.

Example 1:

Let P(n)stand for “people in this course are over 6 feet tall”, then the sentence

“All people in this course are over 6 feet tall” can be written as: “ n P(n)”. The negative,

“ ( n P(n))”, is equivalent to: “ n( P(n))”. So, in English the negative is, “There is

(there is at least one/ there exists/ some) a person in this room who is not over 6 feet tall.”

2

Example 2:

How would one negate the sentence: “Every person in this course is over six feet

tall and is taking the course C Programming”.

Answer:

Let P(n) stand for “people in this course are over 6 feet tall” and let Q(n) stand for

“person n is taking the course C Programming”. Then, the given sentence in symbolic

form is n( P(n) Q(n)).

Next, ( n( P(n) Q(n))) n( (P(n) Q(n))) Why?

n( P(n) Q(n)) [Note: the use of DeMorgan’s law]

In English we have:

There is a person in this course who is not over six feet tall or who is not taking

the course C Programming OR Some people in this course are not over six feet tall or are

not taking the course C Programming.

The Negation of the “There exists” Quantifier:

Example 3:

How would you prove that the statement “ There is a person in this course over 7

feet tall.” is false?

Answer:

Surely, one would have to demonstrate that no one in the room is over seven feet

tall. In other words in logical symbols we have:

( (nP(n))) is equivalent to n( P(n)) .

Can you write the negatives of the following expressions using logic?

1. All people in this course are interesting and informative.

2. Some people in this course are having fun. (Note, the word “some” in

mathematics means there is at least one, or there exists.)

3. All people in this course are over 6 feet tall or wear glasses.

4. For all real numbers x, the equation x2 + 6x + 5 = 0 is true.

Some thoughts on using multiple quantifiers

In week 1 we reviewed some of the basic laws we saw in high school algebra. For

example, we saw that for all real numbers a and b, a + b = b + a (the commutative law

for addition). Of course, what this means is that for every real number a and for every

real number b, we have a + b = b + a. If it is understood that a and b are real numbers, we

could use quantifier notation and say a and b, a + b = b + a. So, using the “for all”

quantifier multiple times is a easy process. The following two examples illustrate that

“mixing” quantifiers makes life more difficult.

3

Example 4.

In the following assume a and b are real numbers:

“ a, b where a + b = 1”.

In English this says: “For all real numbers a there exists a real number b such that

a + b = 1.” This statement is true since, for example, if a = 5 there does exist a real

number b, which makes a + b = 1 true. Just take b = -4 the 5 + (-4) = 1. Of course this

can be done for any real number a, just take b = -(a -1). and a + b = 1 becomes

a + (-(a – 1)) = 1, which is of course true.

Example 5.

In the following assume a and b real numbers.

“ b, a where a + b = 1”.

In English this says “There exists a real number b, such that, for all real numbers

a we have a + b = 1”. This statement is false since, for example, if b = 4 then a + b = 1

becomes a + 4 = 1. Is this true for every single real number a? The equation a + 4 = 1 is

not true for all real numbers a it is true only for the real number a = -3

Methods of Proving Theorems

Why??

Almost nothing in undergraduate, and some graduate, mathematics courses

creates FEAR more than when an instructor announces that the students will be required

to do proofs. Yet, we all prove statements frequently. To illustrate, we may be required to

explain some fact to a child, a high school student, or a colleague. Our explanation is

going to vary depending on what that person knows. When you have successfully

explained the fact you have “proven it”. All a proof is, is a logical, detailed explanation

of why a statement is true. Our explanation will vary depending on to whom we are

speaking. Just like there can be multiple correct directions for going from one location to

another, there are often different proofs for the same mathematical statement.

In any course we take, we are always trying to improve our problem-solving

abilities. In order to solve a problem, we must first make sure we have a clear idea of

what the problem is, what the assumptions are (ie. the “givens”), and what we are trying

to accomplish. This is precisely what we do in mathematical proofs. Spending some time

thinking about proof techniques will enhance our problem solving abilities.

Another purpose of these notes is to help us to be able to read proofs contained in

a textbook that we might be studying. Since a proof is a logical, detailed explanation of a

statement, it helps to clear up any ambiguity we may have on the concept. It gets right to

“the basics”, the core definitions, of what we are studying. If we can read and understand

a proof, we have mastered the key ideas of that concept. The ACM/IEEE

recommendation on Discrete Structures recommends 12 lecture hours on proofs. In the

material that follows I try to make the topic easy to follow.

4

Methods of Proving If … then … types of Theorems

All theorems in mathematics, or any application of mathematics, can be expressed

as a “If … then …” statement(s). Therefore, the text and the notes below discuss

methods of proving “If … then …” statements.

Example 6:

The distributive law for numbers should really read as follows:

If a, b and c are any three real numbers then, a(b + c) = ab + ac.

Example 7:

The commutative law for sets ( under the operation of ) should be stated as:

If A and B are any two sets then A B = B A. [Note: This example will make more

sense after you have studied sets].

Example 8:

The basic matrix algebra law A(BC) = (AB)C should really read as follows:

If A, B and C are matrices whose entries are real numbers of orders m x n, n x p and p x l

respectively then, A(BC) = (AB)C. [Note: This example will make more sense after you

have studied matrices].

You should be able to take each of the logic and set laws given in the notes and write

them in “If … then …” format.

Warning, before you proceed here are a few definitions that we need to know because

they will be used in virtually all of our examples. It is important that you learn the

definitions as given, not some alternate form of the definitions. They will be repeated

again as we need them.

Even integer: An even integer is any integer that can be expressed in the form

2n for some integer n.

Odd integer: An odd integer is any integer that can be expressed in the form

2n + 1 for some integer n.

Divides: Let x and y be integers with x 0. We say that x divides y

(notation x | y) if there exists an integer k such that y = kx.

Some examples:

1) Is 6 an even integer?

Yes, 6 is an even integer since 6 = 2 times 3.

2) Is -8 an even integer?

Sure, since -8 = 2 times (some integer, namely, -4).

5

3) Is 0 an even integer?

Yes, because 0 = 2 (some integer, which is???).

4) Comments on the definition of Divides . Note: in elementary school, if we were

asked whether 3 divides evenly into 15, we would think of

15

3

= what number?

Since

15

3

= 5, we would say yes, 3 divides 15. This gives us the above definition of

Divides: 3 divides 15 because 15 = 3 x (the integer, 5). When you see

x | y, think of

y

x

. That is, x divides evenly into y iff

y

x

= k for some integer k.

The Direct Method of proof of P C Statements.

As we know from our discussions in logic “If P then C” statements or “P implies

C” statements are frequently written in logical notation as P C.

Recall that P stands for the premise (or hypothesis) of the statement and C stands

for the conclusion. The Direct Method of proof of P C statements is based on the

definition of P C. Look at the two cases where P is true in the definition. If P is true

then the complete statement P C is true when C is true. So to prove a statement of

the type P C true assume P is true and prove C is true. To do this start with P

being true and end with C being true. This is called the direct method of proof of a

P C statement. So, to use the direct method we start with the assumption P is true and

we show that it (naturally) follows that C is true using axioms, definitions, previously

established results, and rules of inference.

Example 8.

Prove the following: If x is any even integer and if y is any even integer then xy

is an even integer.

First, I will comment on some key ideas in proof techniques and then proceed with the

proof.

Comments:

Most proofs depend on basic definitions and concepts. Do not proceed any

further until you truly understand these essential ideas. A major reason for

wanting to prove something is because it will force us to learn these key

concepts. (Certainly, people probably smarter than us did the proof of this

statement many years ago.) In this example, the key definition is that of an even

integer. What is the definition of an even integer? I am not asking what we think

the definition may be but, what is the definition. We may have to look it up. Here

is a form of the definition of even integer: An even integer is any integer that

can be expressed in the form 2n for some integer n.

6

Next do you truly understand the definition? Can you give some examples and

explain them? For example, 6 is an even integer. Why? Is 0 an even integer?

Why? (Answer: yes, because 0 = 2(0), that is, 0 can be written as 2 times an

integer.)

What method of proof will you try? Usually try the direct method first.

What is the process for this method? What is the assumption, the premise? What

are you trying to prove? Write the assumption(s) and the conclusion(s) out. This

will focus you attention on what you are trying to do.

Give reasons for each step in your proof. If you cannot give a reason for a

particular step it is most likely wrong.

Relax, with practice you will get most proofs most of the time.

Now I will repeat the statement and prove it. Before you look at my proof try one of

your own.

Example 8 (the proof):

If x is any even integer and if y is any even integer, then xy is an even integer.

Answer:

Proof: (Direct)

Assume x and y are even integers is true (this is the premise, P). Start with this.

Next, write down specifically what you want to do. To prove: xy is an even integer is

true. You want to prove that xy is an even integer, so you must show that xy can be

expressed as 2 times some integer. End with this.

Start with P being true

x and y are even integers implies that x = 2n and y = 2m for some integers n and m.

Why?

this implies that xy = (2n)(2m) Why?

this implies that xy = 2(2nm) Why?

this implies that xy is an even integer. Why? End with C is true

DONE.

Some people like to use logical notation so they would write the above as:

x and y are even integers x = 2n and y = 2m for some integers n and m. Why?

xy = (2n)(2m) Why?

xy = 2(2nm) Why?

xy is an even integer. Why?

DONE.

Example 9.

Prove the following: Let a, b, and c be integers. Then if a | b and a | c, then

a |(b + c).

Comments.

7

The sentence “Let a, b, and c be integers” is just another way of saying let a, b,

and c be any integers or for all integers a, b, and c. The statement we are trying to

prove is “if a | b and a | c, then a |(b + c)”. What is the premise? What is the

conclusion?

Before we begin, we need to understand what x | y means. Assume x and y are

integers where x 0. Read x | y as x “divides” y, which means x divides evenly

into y, no remainder. So, 2 | 8 and 3 | 36 but 2 does not divide 5. Therefore, x | y

means

y

x

= some integer, say k, that is y = kx. A formal definition follows.

Definition: Let x and y be integers with x 0. We say that x divides y if there

exists an integer k such that y = kx.

Example 10:

Let a, b, and c be any integers (a not equal to 0). If a | b, then a | bc. (This is

exercise 6 below).

First, I will outline the direct proof of this statement and then I’ll repeat the

outline and do the proof.

Proof: (Direct):

Assume: P is true, namely, a | b. Start here.

To prove: C is true, namely, a | bc End here

Outline:

Start a | b

bc = a (some integer). How did I know to write this? See below in green.

a | bc END

Since this is the last step, then what is the most likely second last step? By

definition of divides it is bc = a (some integer). I’ll put this in the above and see if it

helps me to get where I’m going.

Now I’ll do the proof, that is, fill in the blanks in the above

Start a|b b = ak for some integer k. This is the definition of “divides”.

How can I go from here to the statement in red below? Simple just

multiple both sides by c. to get

bc = (ak)c. OR bc = a(kc). Note: I’ve rearranged the terms a bit and used

parentheses, ( ). Is it clear I have the form below so I’m done.

bc = a (some integer).

a|bc END

Example 10:

Let a, b, and c be integers. Then if a | b and a | c, then a |(b + c).

Try it yourself first like the outline above. What is the first step, the last, the second last?

Proof: (Direct)

Assume a | b and a | c is true.

8

To prove a |(b + c) (is true). That is, we want to prove that (b + c) = a (some integer).

a | b and a | c b = ak for some integer k and

c = al for some integer l. This is the definition of divides.

b + c = ak + al Simply add both sides of the above equations.

b + c = a(k + l) The distributive law.

b + c = a(some integer) The sum of 2 integers is an integer.

a |(b + c) This is the definition of divides.

So in summary the direct method of proof of P C Statements can be outlined the

following way. All you have to do is know basic definitions and fill in the blanks as

illustrated below.

Proof: (Direct)

Assume: P is true. Start here.

To prove: C is true End here

Outline:

Start P is true means

Once you know the last step, C is true, you frequently can write the

2nd last step and maybe even the 3rd last step

C is true END

Exercises:

Prove the following using the direct method of proof:

1. If x is any even integer and if y is any even integer then x + y is an even integer.

2. If x is any odd integer and if y is any odd integer then xy is an odd integer.

3. If n is an even integer then n2 is an even integer.

4. If n is an odd integer then n2 is an odd integer.

5. If n is an even positive integer then 7n + 4 is an even integer.

6. Let a, b, and c be any integers. If a | b, then a | bc.

7. Let a, b, and c be any integers. If a | b and b | c, then a | c.

8. Let a, b, and c be any integers . If ac | bc, then a | b.

9. If a is an odd integer then 8|(a2 – 1)

9

The “Proof by Contradiction” method of proof of P C Statements.

An If … then … (that is an P C) statement is either true or false. If a P C

statement is not false then it must be true. So if we assume that a P C statement is false

and find that this cannot happen (get a contradiction) then the given P C statement

must be true. In the following identity I will use the conventional P C in place of

P C.

The proof by contradiction method of proof is based on the identity:

( )P C P C . How? To use the “proof by contradiction” method of a proof on a

P C statement, we assume P is true, C is false, and prove that this gives a contradiction.

Note: The usual place to start using this method is generally the false part of the

“assumption” that C is false. Why?

Example 11:

Let n be an integer. Use the proof by contradiction method of proof to prove the

following: “If n3 + 5 is an odd integer then n is an even integer”.

Answer:

So to prove a statement of the form P C using the proof by contradiction method the

process is:

Assume (1) P is true and assume (2) C is false (note this is 2 different assumptions) and

then show that this gives a contradiction. The usual contradiction is to the assumption

that P is true

So the outline of any proof by contradiction usually is:

START with C is false

.

.

.

this contradicts the assumption that P is true

END

Now I will outline the proof of this example. To do so I must understand what C

is (n is a even integer) and what P is (n3 + 5 is an odd integer).

Proof: (by contradiction)

Assume n is even is false and also assume n3 + 5 is odd is true and show that this

gives a contradiction (the contradiction will most likely be to the assumption that n3 + 5

is odd is true)

10

Outline:

Start n is even is false

n3 + 5 = 2(some integer) (c)

n3 + 5 is an even integer (b)

this contradicts the assumption that n3 + 5 is odd is true (a)

END

NOTE I wrote the “start line” first then I knew what I wanted to prove,

namely, line (a) so I wrote this at the bottom. For line (a) to be contradicted n3 + 5

had to be even so line (b) had to occur so I wrote this down and for line (b) to

happen line(c) had to happen.

Now I’ll do the proof using the above outline

Start n is even is false

n is an odd integer

n = 2x + 1 for some integer x (definition of odd integer)

n3 + 5 = (2x + 1)3 + 5 (this is a key step. Line (b) tells me I want to talk

about n3 + 5 so I wrote what n3 + 5 is)

n3 + 5 = 8×3 + 12×2 + 6x + 1 + 5

n3 + 5 = 2(4×3 + 6×2 + 3x + 3)

Note: I did this to get the above expression in the form of the next line (line (c)).

n3 + 5 = 2(some integer) (c)

n3 + 5 is an even integer (b)

this contradicts the assumption that n3 + 5 is odd is true (a)

END

Now try to put reasons next to each step. The reason for step b is simply the definition

of even integer. The reason for another step might be simply basic algebra.

Example 12:

Assume that n is an integer. Use the “proof by contradiction” method of proof to

prove: “If 3n + 4 is even then n is even”.

11

Outline

Proof: (by contradiction)

Assume n is even is false and also assume 3n + 4 is even is true and show that this gives

a contradiction (the contradiction will most likely be to the assumption that 3n + 4 is even

is true)

Outline

Start n is even is false

3n + 4 = 2(some integer) + 1 (c)

3n + 4 is an odd integer (b)

this contradicts the assumption that 3n + 4 is even is true (a)

END

NOTE I wrote the “start line” first then I knew what I wanted to prove,

namely, line (a) so I wrote this at the bottom. For line (a) to be contradicted 3n + 4

had to be odd so line (b) had to occur so I wrote this down and for line (b) to

happen line(c) had to happen.

Can you fill in the steps to the above?

More exercises:

Use the proof by contradiction method of proof to prove the following:

1. If n2 is an even integer then n is an even integer.

2. If n2 is an odd integer then n is an odd integer.

3. If n is an integer and 3n + 2 is even then n is even.

4. If n is any integer and n3 + 7 is odd then n is even.

5. If n2 is not divisible by 3, then n is not divisible by 3.

6. If xy is an odd integer then (both) x and y are odd integers. Some hints for this

one. When you assume that x and y are odd integers is false this means (by

DeMorgan’s law) that x is not odd or y is not odd, that is, x is even or y is even.

So use three situations/cases.

Case 1. x even, y odd, Case 2. x odd, y even and Case 3. x even and y even.

In each case there is a contradiction to xy is odd.

7. If n is any integer then n2 – 4 is not divisible by 4.

12

How to prove iff Theorems.

From the material in logic we know that “iff” means “if and only if” and the

logical symbol, or is often used in place of iff. From the chart Common

Implications and Equivalences (notes week 2, table 4), we know that

( ) ( ) ( )p q p q q p is a tautology, a statement, that is always true. In other

words:

p iff q is equivalent to saying if p then q and if q then p or

p iff q is equivalent to saying if p then q and conversely.

That is, to prove an iff theorem one must prove two if … then … theorems.

In exercise 3 page 8 you proved: If n is an even integer then n2 is an even integer

and for exercise 1 page 11 you proved the converse of this statement namely, “ If n2 is an

even integer then n is an even integer”. The two statements combined could be expressed

as: “n is an even integer iff n2 is an even integer”.

Example 13.

Prove: n is an even integer iff n2 is an even integer.

Proof:

I will outline the proof. To do this I will state each part of the proof and skip

enough space to do each part, so I will not forget each part.

I must prove two statements:

1. If n is an even integer then n2 is an even integer (You proved this in exercise 3 page 8

using the direct method of proof) AND

2. If n2 is an even integer then n is an even integer (You proved this part in exercise 1

page 11 using the proof by contradiction method of proof).

Note: sometimes both parts of an iff statement can be proved using the same method of

proof and sometimes different methods must be used.

Example 14.

Let a and b be any two real numbers. Prove the following:

ab = 0 iff a = 0 or b = 0.

Proof:

We must prove the following two statements:

(a) If ab = 0 then a = 0 or b = 0

and

(b) If a = 0 or b = 0 then ab = 0.

To prove part (a) we use the direct method of proof.

13

Assume that ab = 0 and prove that a = 0 or b = 0. To prove a = 0 or b = 0 we

need only show that one of the two parts of this or statement is true. Why? To do this

assume that a 0 show that when this happens b must be equal to 0. Why does this

work? Since a 0 then 1/a exists. Why? Now multiply both sides of ab = 0 by 1/a to

obtain b = 0. This proves part (a).

To prove part (b) we use the direct method of proof.

Assume a = 0 or b = 0 To prove ab =0. Here we have to show that whether we

assume that a = 0 or we assume that b = 0 the conclusion, ab =0 follows. So we have two

cases/situations.

Case I.

Assume that a = 0 and prove that ab = 0. This follows from the definition of the

multiplication of a number by 0 that we all learned in elementary algebra.

Case II.

Assume that b = 0 and prove that ab = 0. Again, this follows from the definition

of the multiplication of a number by 0.

Here are some additional exercises.

1. n is an odd integer iff n2 is an odd integer.

2. Let n be a positive integer. Prove: n is an odd integer iff n3 + 6 is an odd

integer.

3. Let n be a positive integer. Prove: n is odd iff 5n + 6 is odd.

4. Prove the following: The equation ax2 + bx + c = 0 has a unique solution if and

only if the discriminant b2 – 4ac = 0. Hint. First express the iff statement as two if …

then… statements and then prove each using the direct method of proof. For each if

… then … statement carefully write down your assumption and what you are trying to

prove.

5. x is an odd integer iff x2 + 2x + 1 is even

Proof by contraposition

Another valid method of proof is that where one proves the contrapositive. We

know that the statement (P C) ( C P) is a tautology. So for this method,

instead of proving P C true, we prove C P true. Use the direct method of proof

to do this. That is, assume C true and then prove that P is true.

How do we prove a statement is false?

Finally how does one show/prove that a statement is false? Consider the following

sentence: “Every person taking this course is over six feet tall”. To prove this statement is

incorrect we need only show that there is at least one person taking the course who is not

over six feet tall. This is called giving a counterexample (to the given statement). Look

up this term in the index of the text for more examples.

14

Warning: (Counter) examples are used to prove theorems/statements false but examples

cannot be used to prove theorems true.

Some “do’s” and “don’ts” for proofs:

1. Always try the direct method of proof first. It usually works.

2. Always outline carefully what your assumptions are and what you are trying to

prove. This will focus your attention on what you are given and where you are

going.

3. Clearly specify the method of proof you are using, again this will focus your

attention on the correct process.

4. Keep in mind that a proof is only a detailed explanation. If you don’t understand

what you have written then it is most likely wrong.

5. Above all else, RELAX; the worst that can happen is that you cannot complete

the proof. That’s OK, hopefully by writing down part of the proof you have

focused you attention on the basic definitions and or concepts that you are

studying.

6. If you are stuck partly through a proof, again that’s OK; in fact, it is good to

realize that you are stuck. Try another approach.

In section 1.8 of the text skip to the material titled Methods of Proving

Theorems. Read this material carefully. Concentrate on the examples and the two

principle methods of proving If … then … theorems. These methods are: the direct

method and the proof by contradiction method. After you have studied the material in

the text continue to read the following. Since any if … then …statement is equivalent to

its contrapositive another approach would be to write the contrapositive of the given

statement and to prove it using one of the above two methods.

Warning: the literature is a little confusing concerning the names of the above two

methods. In some texts the proof by contradiction method is called the indirect

method. I will stick to the terms used in our text.