Page 648 - Discrete Mathematics and Its Applications

9.6 Partial Orderings 627

EXAMPLE 22 Is the poset (Z , |) a lattice?
+
Solution: Let a and b be two positive integers. The least upper bound and greatest lower bound
of these two integers are the least common multiple and the greatest common divisor of these
integers, respectively, as the reader should verify. It follows that this poset is a lattice. ▲

EXAMPLE 23 Determine whether the posets ({1, 2, 3, 4, 5}, |) and ({1, 2, 4, 8, 16}, |) are lattices.

Solution: Because 2 and 3 have no upper bounds in ({1, 2, 3, 4, 5}, |), they certainly do not have
a least upper bound. Hence, the first poset is not a lattice.
Every two elements of the second poset have both a least upper bound and a greatest lower
bound. The least upper bound of two elements in this poset is the larger of the elements and the
greatest lower bound of two elements is the smaller of the elements, as the reader should verify.
Hence, this second poset is a lattice. ▲

EXAMPLE 24 Determine whether (P (S), ⊆) is a lattice where S is a set.

Solution: Let A and B be two subsets of S. The least upper bound and the greatest lower bound
of A and B are A ∪ B and A ∩ B, respectively, as the reader can show. Hence, (P (S), ⊆) is a
lattice. ▲

EXAMPLE 25 The Lattice Model of Information Flow In many settings the flow of information from one
person or computer program to another is restricted via security clearances. We can use a lattice
model to represent different information flow policies. For example, one common information
flow policy is the multilevel security policy used in government and military systems. Each
piece of information is assigned to a security class, and each security class is represented by a
pair (A, C) where A is an authority level and C is a category. People and computer programs
are then allowed access to information from a specific restricted set of security classes.
The typical authority levels used in the U.S. government are unclassified (0), confidential (1),
secret (2), and top secret (3). (Information is said to be classified if it is confidential, secret,
There are billions of
or top secret.) Categories used in security classes are the subsets of a set of all compartments
pages of classified U.S.
government documents. relevant to a particular area of interest. Each compartment represents a particular subject area.
For example, if the set of compartments is {spies, moles, double agents}, then there are eight
different categories, one for each of the eight subsets of the set of compartments, such as
{spies, moles}.
We can order security classes by specifying that (A 1 ,C 1 ) (A 2 ,C 2 ) if and only if
A 1 ≤ A 2 and C 1 ⊆ C 2 . Information is permitted to flow from security class (A 1 ,C 1 ) into
security class (A 2 ,C 2 ) if and only if (A 1 ,C 1 ) (A 2 ,C 2 ). For example, information is
permitted to flow from the security class (secret, {spies, moles}) into the security class
(top secret, {spies, moles, double agents}), whereas information is not allowed to flow from
the security class (top secret, {spies, moles}) into either of the security classes (secret, {spies,
moles, double agents}) or (top secret, {spies}).
We leave it to the reader (see Exercise 48) to show that the set of all security classes with
the ordering defined in this example forms a lattice. ▲

Topological Sorting

Suppose that a project is made up of 20 different tasks. Some tasks can be completed only after
others have been finished. How can an order be found for these tasks? To model this problem
we set up a partial order on the set of tasks so that a ≺ b if and only if a and b are tasks where b