Class 11: Predicates

Held: Wednesday, 5 February 2003

Summary: Today we expand Boolean propositions to predicates which can include facts about other values (such as integers).

Related Pages:

• EBoard.

Notes:

• Sorry about the late cancellation of yeserday's class. I got a call at 3 p.m. that Daniel (youngest child) was sick.
• Are there questions on Homework 4?
• Read IEEE reals for tomorrow.

Overview:

• Expanding our worldview: Numbers and Predicates.
• Evalutaing Predicates.
• Three-Valued Boolean Logic and Short-Circuit Conditionals.
• Quantification.
• Bound and Unbound Variables.
• Substittuion.

Expanding Our Worldview

• So far, we've focused on Boolean propositions. Propositions are statements about Boolean variables.
• As we write programs, we'd like to make statements about other types of values.
• We'll start with a few simple other types:
  • Integers
  • Natural numbers (non-negative integers)
  • Set of integers
• In additional to Boolean variables in our Boolean expressions, we will also permit atomic comparison expresions on these types and expressions involving these types, such as x+z<y.
  • A proposition that includes such expressions is a predicate.
• We evaluate predicates similarly to the way we evalaute propositions.
  • And we need a state that assigns values to each variable.

Three Value Boolean Logic

• Unfortunately, as soon as we allow math, we can get some results that are neither true nor false.
  • For example, what is the value of x/y>2 when y is 0?
• We can extend the valid Boolean values from {T,F} to {T,F,U}, where U stands for undefined.
• We now need to go back and redefine all of our operations to include U.
  • Essentially, almost any operation with U as a parameter is U.
• We should also add two operators, which we often call the short circuit operators (and Gries calls the conditional operators), cand and cor
• The definitions of these follow left-to-right evaluation.
  • In cand, if the first argument is F, the value is F. If the first argument is U, the value is U. Otherwise, the value is gthe value of the second argument.
  • In cor, if the first argument is T, the value is T. If the first argument is U, the value is U. Otherwise, the value is gthe value of the second argument.

Quantification

• Consider a predicate, P, with a variable, i, such as i<10*x.
• We can substitute a particular value, such as 2, in for i:
  • 2<10*x.
• We may ocasionally make claims about the particular ranges of i for which P holds.
  • It holds for all i between 1 and 10.
  • It holds for at least one i between 1 and 10.
  • It holds for no i between 1 and 10.
  • It holds for all even i.
  • And so on and so forth.
• Three quantifiers help with such claims.
  • Existential (E in Gries, backwards E in most books): For at least one value in a particular range, P that value substituted in for i holds.
  • Universal (A in Gries, upside-down A in most books): For all values in a particular range, P with that value subsittuted in for i holds.
  • Counting (N in Gries): There are n values in a particular range for which P using one of those values holds.

Bound and Unbound Variables

• One issue that quantifiers range is the relationship of the quantification variables to the variables that appear around them.
• You'd like to be able to quantify without worrying about affecting unexpected things.
• You'd also like to be able to quantify clearly.

Substitution

• Key to the previous topics is the idea of substitution.
• Easy to get mostly right. Hard to get perfectly right.