Discrete Mathematics for Computer Science

218 CHAPTER 3 Relations

3. Define the relation D on N so that n D m if and only if n I m. An upper bound of two
   natural numbers in D is a natural number that both divide. The smallest such natural
   number is called the least upper bound and is denoted as lub(, ). For example, 6 is the
   least upper bound of 2 and 3. A lower bound of two natural numbers in D is a natural
   number that divides both numbers. The largest such natural number is called the greatest
   lower bound and is denoted as glb(, ). For example, the greatest lower bound of^4 and
   6 is 2. Find:
   (a) lub(13, 29)
   (b) lub(12, 60)
   (c) glb(37, 12)
   (d) glb(48, 60)


4. In drawing computer images of scenes, one must be able to tell which objects hide or
   partially hide, other objects from view. Imagine a scene in two dimensions consisting
   of a set L of line segments of various lengths drawn parallel to the x-axis. The line seg-
   ments may intersect. For each of the following relations R on set L, is R antisymmetric?
   Transitive?
   (a) R(f, m) if there is at least one point on segment f that can look parallel to the y-axis
   and see a point on m (a line of sight may have zero length).
   (b) R(f, m) if no point of f can look parallel to the y-axis and see any point of m.


5. Carry out a selection sort (defined in Section 1.7.1) on the words able, cane, bell, after,
   stick, and belt. Explain how lexicographical ordering is used for each comparison.

6. Let T = {A, B, C, D, E, F), and define the partial order R on T as represented by the

following diagram:

A

B / C

D / E / F

(a) Identify all maximal, maximum, minimal, and minimum elements of the partial

order represented by the diagram.

(b) Find a linear order on T where R - IdT C S.

7. (a) Prove that logical equivalence is an equivalence relation on the set of all formulas
   of propositional logic.
   (b) Show that as long as we have infinitely many proposition letters, there are infinitely
   many equivalence classes. (Hint: Once you see the idea, this is pretty trivial.)
   (c) Show that for logical equivalence on the set of all formulas in which the only propo-
   sition letters are P1, P2 .. p., p, there are 22' equivalence classes.