METHODS OF PROOF

DISCRETE STRUCTURES 1

Lecture 4

Introduction

• Methods of proof are important not only because they are used to prove mathematical theorems, but also for their many applications to computer science.

Introduction

• These applications include verifying that computer programs are correct, establishing that operating systems are secure, making inferences in the area of artificial intelligence, showing that system specifications are consistent, and so on.

Definition of Terms

• A theorem is a statement that can be shown to be true. Theorems are sometimes called propositions, facts, or results.
• A proof is a sequence of statements that form an argument (to demonstrate that a theorem is true).
• Axioms or postulates are the underlying assumptions about mathematical structures, the hypotheses of the theorem to be proved, and previously proved theorems.

Definition of Terms

• The rules of inference, which are the means used to draw conclusions from other assertions, tie together the steps of proof.
• Fallacies are forms of incorrect reasoning.
• A lemma (plural lemmas or lemmata) is a simple theorem used in the proof of other theorems. Complicated proofs are usually easier to understand when they are proved using a series of lemmas, where each lemma is proved individually.

Definition of Terms

• A corollary is a proposition that can be established directly from a theorem that has been proved.
• A conjecture is a statement whose truth value is unknown. When a proof of a conjecture is found, the conjecture becomes a theorem.

Rules of Inference

• Rules of inference for propositional logic provide the justification of the steps used to show that a conclusion follows logically from a set of hypotheses.
• The process of drawing a conclusion from a sequence of propositions is called deductive reasoning.

Rules of Inference

• Definition: An argument is a sequence of propositions written p₁�p₂��p_n�_____� q
• An argument form is called valid if whenever all the hypotheses are true, the conclusion is also true.
• A formal proof of validity for a given argument is defined to be a sequence of statements, each of which is either a premise of that argument or follows from preceding statements by an elementary valid arguments, and such that the last statement in the sequence is the conclusion of the argument whose validity is being proved.

Rules of Inference

• Modus Ponens (M.P.)
• Modus Tollens (M.T.)
• Hypothetical Syllogism (H.S.)
• Disjunctive Syllogism (D.S.)
• Constructive Dilemma (C.D.)
• Destructive Dilemma (D.D.)
• Simplification (Simp.)
• Conjunction (Conj.)
• Addition (Add.)
• Resolution (Res.)
• Absorption (Abs.)

​

​

Modus Ponens

• M.P. �p  q �p�_____� q
• Example: If it snows today, then we will go skiing. It is snowing today. Therefore, we will go skiing.

​

Modus Tollens

• M.T. �p  q� q�_____�  p
• Example: If you study hard, you will pass the course. You failed the course. Therefore, you did not study hard.

Hypothetical Syllogism

• H.S. �p  q�q  r�_____�p  r
• Example: If it rains today, then we will not have a barbecue today. If we do not have a barbecue today, then we will have a barbecue tomorrow. Therefore, if it rains today, then we will have a barbecue tomorrow.

​

Disjunctive Syllogism

• D.S.�p  q� p�_____� q
• Example: You either pass the exam or get kicked out. You failed the exam. Therefore, you will get kicked out.

​

Constructive Dilemma

• C.D.�(p  q)  (r  s)�p  r�_______________� q  s
• Example: If I eat too much, then I will get fat and if I exercise daily, then I will get fit. Either I eat too much or exercise daily. Therefore, either I will get fat or get fit.

Destructive Dilemma

• D.D.�(p  q)  (r  s)�q  s�_______________� p  r
• Example: If Mary arrived on time for the meeting, then she took the plane and if John arrived on time for the meeting, then he received the note. Either Mary did not take the plane or John did not receive the note. Therefore, Mary or John was late for the meeting.

Simplification

• Simp.�p  q�_______________� p
• Example: Kangaroos live in Australia and are marsupials. Therefore, kangaroos are marsupials.

Conjunction

• Conj.�p�q�_______� p  q
• Example: John is happy. Mary is sad. Therefore, John is happy but Mary is sad.

Addition

• Add.�p�________� p  q
• Example: Alice is a mathematics major. Therefore, Alice is either a mathematics major or a computer science major.

Resolution

• Res.�p  q�~p  r�_________� q  r
• Example: I pass the exam or I will get kicked out. I fail the exam or go to college. Therefore, I will either get kicked out or go to college.

​

Absorption

• Abs.�p  q�___________� p (p  q)
• Example: If there’s smoke, there’s fire. Therefore, if there’s smoke, then there’s smoke and there’s fire.

Example

• Show that the hypotheses “It is not sunny this afternoon and it is colder than yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset.”

• Let p: “It is sunny this afternoon.”�q: “It is colder than yesterday.”�r: “We will go swimming.”�s: “We will take a canoe trip.”�t: “We will be home by sunset.”

�Step Reason

1. p  q Hypothesis
2. r  p Hypothesis
3. r  s Hypothesis
4. s  t Hypothesis
5. p Simp. 1
6. r M.T. 2,5
7. s M.P. 3,6

__________

 t M.P. 4,7

Exercise

• What rule of inference is used in each of these arguments?
• Jerry is a mathematics major and a computer science major. Therefore, Jerry is a mathematics major.
• If it is rainy, then the pool will be closed. It is rainy. Therefore, the pool is closed.
• If it snows today, the university will close. The university is not closed today. Therefore, it did not snow today.
• If I go swimming, then I will stay in the sun too long. If I stay in the sun too long, then I will sunburn. Therefore, if I go swimming, then I will sunburn.

Exercise

• Construct a formal proof of validity for each of the following arguments:
• Randy works hard. If Randy works hard, then he is a dull boy. If Randy is a dull boy, then he will not get the job. Therefore, Randy will not get the job.
• If either algebra is required or geometry is required, then all students will study mathematics. Algebra is required and trigonometry is required. Therefore, all students will study mathematics.

Exercise

• Construct a formal proof of validity for each of the following arguments:
• Either Gonzales attended the meeting or Gonzales was not invited to the meeting. If the directors wanted Gonzales at the meeting, then Gonzales was invited to the meeting. Gonzales did not attend the meeting. If the directors did not want Gonzales at the meeting and Gonzales was not invited to the meeting, then Gonzales is on his way out of the company. Therefore, Gonzales is on his way out of the company.

Exercise

• Construct a formal proof of validity for the following arguments:
• If either Gertrude or Herbert wins, then both Jane and Kenneth lose. Gertrude wins. Therefore Jane loses.

Exercise

• Construct a formal proof of validity for the following arguments:
• If rain continues, then the river rises. If rain continues and the river rises, then the bridge will wash out. If continuation of the rain would cause the bridge to wash out, then a single road is not sufficient for the town. Either a single road is sufficient for the town or the traffic engineers have made a mistake. Therefore, the traffic engineers have made a mistake.

Rules of Replacement

Any of the following logically equivalent expressions may replace each other whenever they occur:

• De Morgan’s Theorem (De M.)�~(p  q)  (~p  ~q)�~(p  q)  (~p  ~q)
• Commutation (Com.)�(p  q)  (q  p)�(p  q)  (q  p)
• Association (Assoc.)�[p  (q  r)]  [(p  q)  r]�[p  (q  r)]  [(p  q)  r]

Rules of Replacement

• Distribution (Dist.)�[p  (q  r)]  [(p  q)  (p  r)]�[p  (q  r)]  [(p  q)  (p  r)]
• Double Negation (D.N.)�p  ~~p
• Transposition (Trans.)�(p  q)  (~q  ~p)
• Material Implication (M.I.)�(p  q)  (~p  q)

Rules of Replacement

• Material Equivalence (M.E.)�(p  q)  [(p  q)  (q  p)]�(p  q)  [(p  q)  (~p  ~q)]
• Exportation (Exp.)�[(p  q)  r  [p  (q  r)]
• Tautology (Taut.)�p  (p  p)�p  (p  p)

• Either the Attorney General has imposed a strict censorship or if Black mailed the letter then Davis received a warning. If our lines of communication have not been broken down completely, then if Davis received a warning then Emory was informed about the matter. If the Attorney General has imposed a strict censorship, then our lines of communication have been broken down completely. Our lines of communication have not been broken down completely. Therefore, if Black mailed the letter, then Emory was informed about the matter.

Rules of Inference for Quantified Statements

• Universal instantiation (U.I.)
• Universal generalization (U.G.)
• Existential instantiation (E.I.)
• Existential generalization (E.G.)

Universal Instantiation

• used to conclude that P(c) is true, where c is a particular member of the universe of discourse, given the premise _x P(x).
• Example: “All women are wise.”�“Lisa is a woman.”�“Therefore, Lisa is wise.”

Universal Generalization

• states that _x P(x) is true, given the premise that P(c) is true for all elements c in the universe of discourse.
• Universal generalization is used when we show that _x P(x) is true by taking an arbitrary element c from the universe of discourse and showing that P(c) is true. The element c that we select must be an arbitrary, and not a specific, element of the universe of discourse. Universal generalization is used implicitly in many proofs in mathematics and is seldom mentioned explicitly.

Existential Instantiation

• allows us to conclude that there is an element c in the universe of discourse for which P(c) is true if we know that _x P(x) is true.
• We cannot select an arbitrary value of c here, but rather it must be a c for which P(c) is true. Usually we have no knowledge of what c is, only that it exists.

Existential Generalization

• used to conclude that _x P(x) is true when a particular element c with P(c) true is known.
• That is, if we know one element c in the universe of discourse for which P(c) is true, then we know _x P(x) is true.

Table 1. Rules of Inference for Quantified Statements

Exercise

• Show that the premises “Everyone in this class has taken a course in computer science” and “Maria is a student in this class” imply the conclusion “Maria has taken a course in computer science.”

Exercise

• Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book.”

Direct Proof

• The implication pq can be proved by showing that if p is true, then q must also be true.
• This shows that the combination p true and q false never occurs.
• A direct proof assumes that p is true and then, using p as well as other axioms, definitions, and previously derived theorems, shows directly that q is true.

Example

• Definition: The integer n is even if there exists an integer k such that n=2k and it is odd if there exists an integer k such that n=2k+1. (Note that an integer is either even or odd.)
• Give the direct proof of the theorem “If n is an odd integer, then n² is an odd integer.”

• Solution: Assume that the hypothesis of this implication is true, namely, suppose that n is odd. Then n=2k+1, where k is an integer. It follows that �n²=(2k + 1)^2�=4k² + 4k + 1�=2(2k² + 2k) + 1�Therefore, n² is an odd integer (it is one more than twice an integer).

Indirect Proof

• Since the implication pq is equivalent to its contrapositive, q  p, the implication pq can be proved by showing that its contrapositive, q  p, is true.
• This related implication is usually proved directly, but any proof technique can be used. An argument of this type is called an indirect proof.

Example

• Give an indirect proof of the theorem “If 3n+2 is odd, then n is odd.”
• Solution: Assume that the conclusion of this implication is false; namely, assume that n is even. Then n=2k for some integer k. It follows that �3n+2 = 3(2k)+2 �= 6k+2 �= 2(3k+1)�so 3n+2 is even (since it is a multiple of 2) and therefore not odd. �Because the negation of the conclusion of the implication implies that the hypothesis is false, the original implication is true.

Proof by Contradiction

• A proof of contradiction establishes that the proposition pq by assuming that the hypothesis p is true and that the conclusion q is false and then, using p and q as well as other axioms, definitions, and previously derived theorems, derives a contradiction.

Example

• Give a proof by contradiction of the theorem “If 3n+2 is odd, then n is odd.”
• Solution: We assume that 3n+2 is odd and that n is not odd, so that n is even. Then n=2k for some integer k. It follows that �3n+2 = 3(2k)+2 �= 6k+2 �= 2(3k+1)�This contradicts the assumption that 3n+2 is odd, completing the proof.

Example

• Prove, by contradiction, the following statement:�For all real numbers x and y, �if x+y  2, then either x  1 or y  1.
• Proof: Suppose that the conclusion is false. Then, x < 1 and y < 1. (Remember that negating and or results in an and.). From the properties of inequality in Algebra, we may add these inequalities to obtain�x + y < 2�At this point, we have derived the contradiction pp, where p: x + y  2.

Exercise

• Prove that the square of an even number is an even number using either
• a direct proof
• an indirect proof
• a proof by contradiction
• Prove that the sum of two rational numbers is rational. (Definition: A real number r is rational if there exists integers p and q with q0 such that r = p/q. A real number that is not rational is called irrational.)