Lecture notes for October 30 Lecture notes for October 30

Ordinary language statements like ``x > 3, x = y+3, x > x-1'' are not ``statements'' in the sense of KST because we cannot assign truth values.

But if we replace x by 4 in ``x > 3'' we get a statement. Similarly if we replace x by 1. Note that in the first case, ``4 > 3''is true whereas in the second case, ``1 > 3'' is false.

If Px represents ``x > 3'' then P4 is true, P1 is false, and Pelephant is meaningless. In considering Px we need to agree to what ``x''can be, i.e., to a universe of discourse for P.

Similarly, if Pxy is ``x = y+3'' and the universe of discourse for P is the set of pairs of integers, P4,1 is true, P3,1 is false and P[1/2],-[7/2] is not even considered.

If Px is ``x > x-1'' and the universe of discourse is the set of real numbers, R, observe that Px is true for every real number x R.

The expression P is called a predicate.

We have seen that one way to obtain a statement from a predicate is to replace the variables by particular elements of the universe of discourse. Another way is to quantify. The universal quantification of Px is the statement, ``Px is true for all x in the universe of discourse''. It is typically denoted "x Px, or in the extended notation of our text, (|:Px) or ("|:Px).

If Px is ``x > 3'' and the universe of discourse is Z, then "x Px is false. How do we know? There is an x, e.g., 2, such that Px is false.

If Px is ``x > x-1'' and the universe of discourse is Z, then "x Px is true.

The existential quantification of Px is the statement there exists an x in the universe of discourse such that Px is true. It is typically denoted $x Px, or in the extended notation of our text, (|:Px) or ($|:Px).

Let Qxy be the predicate ``x = y+1''. Take Z × Z to be the universe of discourse. Observe that "x $y Qxy which is parsed "x ($y Qxy) is true whereas $y "x Qxy which is parsed $y("x Qxy) is false.

A good reference for this is Rosen, Discrete Mathematics and Its Applications, Chapter 1.3. This is the textbook for both Math 1190 and Math 2320 and is readily available if you want to photocopy the section. It gives a good discussion from a semantic point of view of universal and existential quantification. Chapter 9 of Gries-Schneider provides the syntactic treatment which we will follow.

We start with Chapter 8 which treats quantification in general. Beware as this chapter is a mine field. We will make extensive use of some supplementary materials prepared in previous years by Professor Ganong for clarification.

(*| R:P)

x is a variable name, * an operator (in the examples, * is one of , , +, ·),R an expression of type Boolean, P an expression whose type depends upon *. In the case of and , P is of type Boolean.

Examples:


File translated from TEX by TTH, version 2.60.
On 28 Oct 2000, 22:43.