Maggie Johnson                                                                                                Handout #16

CS103A

 

Introduction to Quantification

 

Key Topics

 

·        Predicates Revisited

·        Well-Formed Formulas

·        The “Game” with Quantifiers

·        The Four Aristotelian Forms

·        Translations

                                                                                                                                               

 

We have been working with predicates since the beginning of our studies in logic.  Predicate symbols are used to express some property of objects or some relation between objects.  Our discussion of predicates has been limited to those that refer to specific objects, e.g., Boy(Elliot) or tet(b) where b is an actual entity in Tarski’s World.  We will now expand this notion to allow variables to be used with predicates.  So, we can now refer to Boy(x) or Apple(y) where the value of x and y may not be known.

 

In general, we think of logic using predicates and variables (i.e., predicate logic) as a more “powerful” language.  We can manipulate the variables within a predicate in a way that is just not possible with propositional logic.  In fact, predicate logic is expressive enough to form the basis of a number of useful programming languages including Prolog, and SQL (structured-query language).  Predicate logic is also used in reasoning systems or “expert” systems, such as medical-diagnosis programs and theorem-proving programs.

 

When we work with predicate logic, the variables take on an important role.  It is by defining a value for these variables that we can actually assign a true or false value to the predicate.  For example, Apple(y) is true if and only if y is an apple.  If y happens to a plum, then Apple(y) is false.

 

The collection of values that can replace a variable in a predicate is called the universe or domain of discourse of the predicate.  In an arity-one predicate, if a value from the universe can be substituted for the variable to make it true, we say the value satisfies the predicate.  If a set of n values exists which can be substituted for the variables in an arity-n predicate, the set satisfies the predicate.  The predicate is said to be satisfiable.  If all sets of n values satisfy the predicate, it is said to be valid.

 

When all the variables in a predicate have been assigned values, the resulting statement has a truth value.  However, there is another important way to assign truth values to  predicates called quantification.  Quantified sentences are so called because they allow us to talk about quantities of things.

 

Consider a predicate from algebra  P(a,b):  a + b = b + a.  How can P(a,b) be regarded as a proposition?  No matter what values we substitute for a and b, this predicate is always true.  So the truth of the statement does not depend on the values of a or b at all, but on the fact that the statement is true for all values.  We say that the variables a and b have been quantified universally, and we indicate this fact with the symbol " meaning "for all": "a "b P(a,b).  The predicate P is true for all values of a and b in the universe.  Note that it is standard practice to  not explicitly state universal quantifiers if they apply to the entire predicate, unless it helps to avoid confusion.  So, in the previous example we could have said just P(a,b).

 

Consider another predicate from algebra  S(a,b): For every a there is a  b  such that a+b = 0 and b+a = 0.  In this case, a has been quantified but has b?  Given the value of a, we can find one value of b that makes the predicate true.  Again, we do not care what the actual value is, we just care that one exists.  In this case, we say that b is quantified existentially, i.e., the predicate can be made true by proper selection of the value.  We indicate this with the symbol $, so we say "a $b S(a,b) which translates to "for all a, there exists b such that S(a,b)". Note that changing the order of the quantifiers changes things considerably: $b "a S(a,b) means there is some value of b which can be chosen so as to make S true no matter what value of a is chosen.

 

If all the variables in a predicate have been quantified, we can determine if it is true.

 

Example

                                                                                                            

            What is the truth value of "x P(x) where P(x) is the statement x + 1 > x and the             universe of the predicate is all real numbers?

 

            Since P(x) is true for all real numbers, the quantification is true.

 

Example

                                                                                                            

            What is the truth value of "x P(x) where P(x) is the statement x = x + 1 and the             universe of the predicate is all real numbers?

 

            Since P(x) is false for all real numbers, the quantification is  false.

 

 

            Summary of Quantifiers in Arity-One Predicates

 

            Statement         When true?                                           When false?

            "x P(x)            P(x) is true for all x                               an x exists where P(x) is false

            $x P(x)             There is an x where P(x) is true P(x) is false for all x

 

A variable that has been either quantified or has been substituted into a predicate is called  a bound variable.  Variables that have not been bound are free.  With the "binding" of a variable, it becomes possible to determine the truth value of the predicate. 

 

Typically, we use quantifiers to make conditional claims like the following:

 

"x (Professor(x) ® Smart(x))

            $x (Professor(x) ^ Smart(x))

 

The first translates to: Every professor is smart.  Or, to be more exact, if you pick anything at all, you’ll find it is either not a professor or that it is smart (or maybe both).  The second has a different meaning: Some professor is smart, or, there is at least one smart professor. 

 

Some students new to predicate logic wonder why “Every professor is smart” cannot be represented as

 

            "x (Professor(x) ^ Smart(x))

 

But this does not have the same meaning as “Every professor is smart”.  Do you know why?

 

One of the most powerful features of predicate logic is its ability to capture real-world facts in a precise, compact way.  This is one of the reasons why it has been used in artificial intelligence as a knowledge representation scheme.  We will practice a great deal with translation from English sentences into quantified predicates, variables and Boolean connectives.

 

 

Well-Formed Formulas

 

Apple(y) or Boy(x) are examples of atomic well-formed formulas (wff’s).  An atomic wff is any n-ary predicate followed by n terms where the terms can be variables or constants. 

 

The following examples are wff’s, but they are not atomic:

 

"x (Professor(x) ® Smart(x))

            $x (Professor(x) ^ Smart(x))

 

A wff is formed as follows:

 

  1. If P is a wff, then so is ~P.
  2. If P1, …, Pn are wffs, so is (P1 ^…^Pn).
  3. If P1, …, Pn are wffs, so is (P1 v…v Pn).
  4. If P and Q are wffs, so is (P ® Q).
  5. If P and Q are wffs, so is (P « Q).
  6. If P is a wff, and v is a variable, then "v P is a wff and any occurrence of v in "v P is said to be bound.
  7. If P is a wff, and v is a variable, then $v P is a wff and any occurrence of v in $v P is said to be bound.

 

A sentence is a wff with no free variables.  To determine if a wff is a sentence we often have to consider the scope of a quantifier.  Parentheses are essential in helping to define this.  For example, the first wff below is a sentence since x is bound, but the second is not since the x in Smart(x) is free.

 

            $x (Professor(x) ^ Smart(x))

            $x  Professor(x) ^ Smart(x)

 

A sentence of the form "x S(x) is true if and only if the wff S(x) is satisfied by every object in the domain of discourse.

 

A sentence of the form $x S(x) is true if and only if the wff S(x) is satisfied by some object in the domain of discourse.

 

 

The Four Aristotelian Forms:

 

 

Translations

 

As we mentioned earlier, one of the most powerful aspects of predicate logic and quantifiers is how they allow us to capture real-world facts in a concise form.  But it takes practice in learning how to do these translations.

 

Lewis Carroll (the author of Alice in Wonderland) wrote several books on symbolic logic.  He gives many examples of reasoning using quantifiers:

 

Example

 

            All lions are fierce.

            Some lions do not drink coffee.

            Some fierce creatures do not drink coffee.

 

            If P(x) denotes "x is a lion";  Q(x) denotes "x is fierce"; and R(x) denote "x drinks             coffee", we can express the 3 statements above using quantifiers and P(x), Q(x),            and R(x) (assuming the universe is the set of all creatures).

 

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

            $x (P(x) ^ ~R(x))

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

 

 

Problem

 

P(x): “X is a professor”

Q(x): “X is ignorant”

R(x): “X is vain”

 

Express the following statements using quantifiers, logical connectives and P(x), Q(x), and R(x), where the universe is the set of all people.

 

a) No professors are ignorant.

 

b) All ignorant people are vain.

 

c) No professors are vain.

 

 

Historical Notes

 

The formal concept of a quantifier was introduced into the symbolic logic of George Boole by the American philosopher, logician and engineer Charles Sanders Peirce (1839 - 1914).  He was the founder of pragmatism, a branch of philosophy which attempts to bring philosophical and intellectual pursuits into the realm of the practical.  Peirce made his living working for  the US Coast Survey doing gravity research, but his primary interests were in logic and philosophy.  He was a very gifted scientist and logician; he was also ambidextrous such that he could write a question with one hand, and write the answer simultaneously with the other.