Maggie Johnson                                                                                                Handout #19

CS103A

 

Methods of Proof for Quantifiers

 

Key Topics

 

·        Valid Steps

·        Existential Instantiation

·        General Conditional Proof

·        Proofs with Mixed Quantifiers

                                                                                                                                               

 

More Practice...

 

1) If "x $y P(x, y) is true, does it necessarily follow that $x "y P(x, y) is true?

 

 

 

 

 

2) Express the following statement using quantifiers: Every student in this class has taken some course in every department in the School of Engineering.  (You have been busy!)

 

 

 

 

Valid Quantifier Steps

 

Universal Elimination or Instantiation: Suppose we have established "x S(x), and we know that b names an object in the domain of discourse.  We may then infer S(b).

 

Existential Introduction or Generalization:  Suppose you have established a claim of the form S(b), then we may infer $x S(x).

 

"x (Tet(x) ® Green(x))

"x (Green(x) ® Smaller(x, a))

Tet(t)

$x (Green(x) ^ Smaller(x,a))

 

 

Existential Instantiation

 

This technique allows us to prove claims when given an existential statement.

 

            $x  InSchool(x)

 

We may not infer that Elliot is in school or Caroline is in school from this statement.  We can, however, assign a temporary name to someone who is in school (at least one such student exists).  As long as we are careful to not use a name already used in the premises or the conclusion, we can name the object.

 

If we have proven $x  P(x), then we can give a name, say m, to one of the objects satisfying P(x) as long as the name is not already in use.  We may then assume S(m) and proceed with the proof.

 

"x (Tet(x) ®Green(x))

"x (Green(x) ® Smaller(x, a))

$x Tet(x)

$x (Green(x) ^ Smaller(x,a))

 

 

General Conditional Proof

 

To show that every element in a set satisfies a particular property, suppose an element x is a particular but arbitrarily chosen element of the set, and show that x satisfies that property.  The point of having x be arbitrarily chosen (or generic) is to make the proof general, i.e., you are making no special assumptions about x that are not also true of all the other elements of S.  So, whatever you prove about x, you can prove about any other element in the set.  You must be careful to keep the objects generic.

 

The basic idea then is: Suppose we want to prove "x (P(x) ® Q(x)) from some premises.  We choose a name not in use, say m, and assume P(m), and then prove Q(m).  If you are able to do this without making any assumptions about m in particular, then you can infer the desired result.

 

            Prove: The sum of two even integers is even.

 

            That is: "integers m and n, if m and n are even, then m+n is even.

 

Suppose m and n are particular but arbitrarily chosen even integers, we must show that m+n is also even.  To do so, we use the definition of an even integer (m = 2r for some integer r and n = 2s for some integer s; note that we use different letters because we don't want to set up a special case). 

 

                        Statement                                 Reason

                        m+n = 2r + 2s                          substitution

 

                        m+n = 2(r + s)                          factor out the two

 

 

r+s is an integer k                     r is an integer and s is an integer and the sum of any two integers is an integer.

 

                        m + n = 2(k)                             substitution

 

                        m + n is even                            definition of an even number.

 

                        Therefore, the sum of any two even numbers is also even.

 

Universal Introduction or Generalization allows us to introduce a new name, say m, to stand for a completely arbitrary member of the domain of discourse.  We then go on to prove the sentence S(m).  We can then conclude "x S(x).

 

Any proof using general conditional proof can be converted into a proof using universal introduction and conditional proof.  First, introduce a new name and think of it as standing for an arbitrary member of the domain of discourse.  Then, prove P(m) ® Q(m) using conditional proof.  But then since m is an arbitrary member of the domain, we can use universal introduction to prove "x (P(x) ® Q(x)).  Formal deductive systems use these two techniques to avoid having an explicit rule of general conditional proof.

 

Is the following a valid argument?

 

"y (Cube(y) v Dodec(y))

"x (Cube(x) ® Large(x))

$x ~Large(x)

$x Dodec(x)

 

 

Proofs with Mixed Quantifiers

 

Care must be taken in introducing new names into a proof when doing existential instantiation, general conditional proof, and universal generalization.

 

$y (tet(y) ^ "x (cube(x) ® smaller(x,y)))

"x (cube(x) ® $y (tet(y) ^ smaller(x,y)))

 

premise: there is some tet that is larger than every cube

conclusion: every cube is smaller than some tet.

 

What if we flip the premise and conclusion around, is the argument still valid?

 

"x (cube(x) ® $y (tet(y) ^ smaller(x,y)))

$y (tet(y) ^ "x (cube(x) ® smaller(x,y)))

 

Translate the following into FOL, and then reorder the premises so the conclusion follows logically (from Lewis Carroll).

 

  1. I trust every animal that belongs to me.
  2. Dogs gnaw bones.
  3. I admit no animals into my study unless they beg when told to do so.
  4. All the animals in the yard are mine.
  5. I admit every animal that I trust to my study.
  6. The only animals that are really willing to beg when told to do so are dogs.

 

Therefore, All the animals in the yard gnaw bones.

 

 

"x "y "z ((P(x,y) ^ P(y,z)) ® P(x,z))

"x "y (P(x,y) ® P(y,x))

$x $y P(x,y)

"x P(x,x)

 

Proof (?): We apply existential instantiation to the third premise: let m and n be arbitrary objects in the domain of discourse such that P(m,n) is true.  By the second premise and modus ponens, we have P(n,m).  Where do we go next?