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:

• ("| R:P) also written (Ù| R:P).
This interprets as ``For all values of x in the universe of discourse such that R holds, P holds''. In our informal examples we understand what is meant by replacing x by a value. We will need to wait until we define free occurrences of variables to obtain a better formal defintion.

Let the universe of discourse be Z, the set of integers.
("| n is odd : n2 is odd ) is true.
("| n is odd : true) is true.
("| true : n2 is odd ) is false.
("| false : n2 is odd ) is true.
If we write ("| :P) we abbreviate ("| true:P) or what is often written "x P.

• (\$x  | R:P) also written (\$x  | R:P).
This interprets as ``For some values of x in the universe of discourse such that R holds, P holds''.

Let the universe of discourse be Z, the set of integers.
(\$| n > 0 : n2 = 4) is true.
(\$| n > 0 : n2 = -1) is false.
(\$| true : n2 = -1) is false.
(\$| false : n2 = 4) is false.
If we write (\$| :P) we abbreviate (\$| true:P) or what is often written \$x P.

• (å| R:P) also written (+ x | R:P).
This interprets as the sum obtained by adding the values of P obtained by replacing x in P (actually free occurrences of x in P) with each of the values of x for which R holds.
(å| 1 £ k £ 3 : k2) is 12 + 22 + 32.
(å| 1 £ k £ n : k) is 1 + 2 + 3 + ¼+n.

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