Study Guides for Discrete Mathematics

Predicates and Quantifiers

When the propositional calculus is extended to include the quantifiers "For All" and "There Exists" we call the resulting logical system the predicate calculus.

 

Quantified expressions take on one of the following forms.

" x(P(x)) where P(x) is a logical expression or

$ x(Q(x)) where Q(x) is a logical expression.

 

" x(P(x)) means that P(x) is true for every value of x and

$ x(Q(x)) means that Q(x) is true for at least one value of x.

 

Examples:

Determine the truth-value of each of the following:

  1. " x($ y(x + y = 0)

    2. This statement is true since for any real number x we may let y = -x.

     

  2. " x($ y(x * y = 1)

x = 0 serves as a counterexample for this statement since 0 has no multiplicative inverse.

 

3. $ x(" y(x * y = 0)

This statement is true since 0*y = 0 for all y.

 

 

Negating expressions in Predicate Calculus:

To negate the universal quantifier,

Ø " x(P(x)) = $ x(Ø P(x))

In English: "It is not the case that P(x) is True for all x" is equivalent to saying "there is one x for which P(x) is False".

 

To negate the existential quantifier,

Ø $ x(Q(x)) = " x(Ø Q(x))

Similarly, "it is not the case that there is, at least, one x for which Q(x) is True" is equivalent to saying "Q(x) is False for all x".

 

 

Examples:

  1. Ø " x(2*x + 1 ¹ x) = $ x(2 * x + 1 = x)

    2.  

  2. Ø $ y(" x(x * y = 1)) = " y(Ø " x(x * y = 1)) = " y($ x(x * y ¹ 1))

 

Creating Logic Predicates from English Statements

Creating predicates from English statements (natural language statements) is generally not difficult. Many examples are given in the text. Perhaps the greatest difficulty in determining a proper translation into a predicate is in determining how much of the English statement should be converted to variables. An example will illustrate this question.

 

Example:

Translate the following statement into a logical expression.

All fourth-year CS majors at UVa will get good jobs next year.

Here are several possible translations.

1. P(x) means x is a fourth-year CS major at UVa. J(x) means x will get a good job..

" x(P(x) Þ J(x))

2. P(x) means x is a CS major at UVa. Y(x) is x’s class rank.

" x((P(x) /\ Y(4)) Þ J(x))

3. P(x, y) means x is a UVa. student in his/her yth year.

" x(P(x, 4) Þ J(x))

 

Many other formulations are possible.

When there are many possible formulations you will need to determine which form fits best for the problem at hand.

Another consideration is the element of time. Try to make your statements as time neutral as possible since truth-values in the real world vary with time. For example the statement "It is raining" has a value of True at some times and False at others. Sometimes it may be necessary to be explicit about the time reference.

For example, "If it rains tonight, the grass will be wet tomorrow morning."