Maggie Johnson Handout #21

CS103A

Formal Proofs and Quantifiers

Key Topics

· Universal Quantifier Rules

· Existential Quantifier Rules

· Strategies

Practice Exercises

How would you translate the following?

1. There are at least two cubes.
2. There are at most two cubes.
3. There are exactly two cubes.

Universal Quantifier Rules in Formal Proofs

"x (P(x) ® Q(x))

"z (Q(z) ® R(z))

"x (P(x) ® R(x))

"x Cube(x)

"x Small(x)

"x (Cube(x) ^ Small(x))

"x ~Cube(x)

"x ~(Cube(x) ^ Small(x))

Existential Quantifier Rules

"x (P(x) ® Q(x))

"z (Q(x) ® R(x))

$x P(x)

$x (Q(x) ^ R(x)

Strategies

• Convince yourself that the conclusion is indeed true by studying the premises and understanding their meaning:

§ Make sure you understand all the terms used in the premises and conclusion - get your definitions ready.

§ We typically prove general conclusions about a set of objects. One way to understand what is to be proven is by proving the conclusion for a particular element of the set. Convince yourself that the conclusion is true for this element (and if you find that it is not, you have just disproven the conclusion). This will also give you insight into how to do the general proof.

§ Try giving an informal proof of the conclusion - explain it to a friend.

§ Identify the formal rules implicit in your informal proof – this takes some practice.

Universal Elimination

"x P(x) Watch for: application of a general claim

… to a specific individual

P(m)

Universal Introduction

m

Watch for: proving a claim for an arbitrary

element of the domain.

…

P(m)

"x P(x)

Existential Elimination

m

$x P(x) Watch for: any reference to an object whose existence is guaranteed by an existential claim.

P(m)

…

Q

Q

Existential Introduction

P(m) Watch for: a reference to a specific object being

… used to support a claim for “some” object.

$x P(x)

(Note: this is the one where you need to include the $x P(x) claim as the last line in the subproof. We then repeat this line in the outer proof.)

• It can help to get the structure of the proof in place, i.e., the subproofs and obvious steps and then try and fill in the holes.

• Working backwards from the goal can be useful in proving universal claims especially of the form "x (P(x) ® Q(x)).

• If all else fails, try a proof by contradiction.

$x (Cube(x) ^ Small(x))

$x Cube(x) ^ $x Small(x)

"x (Dodec(x) ® SameCol(x,a))

SameCol(a,c)

"x (Dodec(x) ® SameCol(x,c))