Maggie Johnson Handout #5

CS103A

Methods of Proof I

Key Topics

* What is a Proof?

* Formal vs. Informal Proofs

* Proofs with Identity

* Carryover to Other Predicates

* Formal Proofs & Fitch

* Proofs of Nonconsequence

· Is this a valid argument?

The President of the United States must be at least 35 years old.

Bill is at least 35 years old.

Therefore, Bill is President of the United States.

· Proof: a step-by-step demonstration that a conclusion follows from some premises.

Premises

a. If my glasses are on the kitchen table, then I saw them at breakfast.

b. I was reading the newspaper in the living room or I was reading the newspaper in the kitchen.

c. If I was reading the newspaper in the living room, then my glasses are on the coffee table.

d. I did not see my glasses at breakfast.

e. If I was reading my book in bed, then my glasses are on my bed table.

f. If I was reading the newspaper in the kitchen, then my glasses are on the kitchen table.

Conclusion: My glasses are on the coffee table.

Some intermediate conclusions - how did we arrive at these?

g. The glasses are not on the kitchen table

h. I did not read the newspaper in the kitchen

i. I read the newspaper in the living room

· Formal Proof vs. Informal Proofs

Remember: All proofs must be rigorous, i.e., each step in a proof must provide definitive evidence that the intermediate conclusion follows from things already established.

Formal Proof: Every step in the proof is provided (i.e., no steps are left out), a fixed set of rules are used as explanations of intermediate conclusions; usually presented in a highly stylized, formal way.

Informal Proof: Usually stated in English, in paragraph form; less formal and the more obvious steps are left out. (Which steps can be left out?)

(We will be much more exact about these categories later…)

· Proofs with Identity

= Elim: If b = c then whatever holds for b, holds for c.

= Intro: b = b is always true (reflexivity)

Symmetry of Identity: If b = c, then c = b.

Transitivity of Identity: If a = b and b = c, then a = c.

· Carryover to Other Predicates

In the blocks FOL:

Larger is transitive; SameRow is reflexive and symmetric

Inverses: b is larger than c, so c is smaller then b; larger and smaller are "inverses", so are right/left. They refer to the same relation but in opposite directions.

· Proofs of Nonconsequence

Proving that a conclusion does not follow from the premises.

An invalid argument is one where there is some circumstance that make the premises true but the conclusion false - we just have to find the circumstance. This is called a counterexample.