Page 659 - Discrete Mathematics and Its Applications

638 9 / Relations

∗ 48. Show that if L is a finite distributive lattice, then an ele- 49. Show that the game of Chomp with cookies arranged in
ment of L has at most one complement. an m × n rectangular grid, described in Example 12 in
The game of Chomp, introduced in Example 12 in Section 1.8, Section 1.8, is the same as the game of Chomp on the
can be generalized for play on any finite partially ordered set poset (S, |), where S is the set of all positive integers that
m−1 n−1
(S, ) with a least element a. In this game, a move consists of divide p q , where p and q are distinct primes.
selecting an element x in S and removing x and all elements 50. Show that if (S, ) has a greatest element b, then a win-
larger than it from S. The loser is the player who is forced to ning strategy for Chomp on this poset exists. [Hint: Gen-
select the least element a. eralize the argument in Example 12 in Section 1.8.]

Computer Projects

Write programs with these input and output.

1. Given the matrix representing a relation on a finite set, de- 10. Given the matrix representing a relation on a finite set,
termine whether the relation is reflexive and/or irreflexive. find the matrix representing the reflexive closure of this
2. Given the matrix representing a relation on a finite set, relation.
determine whether the relation is symmetric and/or anti-
symmetric. 11. Given the matrix representing a relation on a finite set,
find the matrix representing the symmetric closure of this
3. Given the matrix representing a relation on a finite set, relation.
determine whether the relation is transitive.
4. Given a positive integer n, display all the relations on a set 12. Given the matrix representing a relation on a finite set,
with n elements. find the matrix representing the transitive closure of this
relation by computing the join of the Boolean powers of
∗ 5. Given a positive integer n, determine the number of tran-
sitive relations on a set with n elements. the matrix representing the relation.
∗ 6. Given a positive integer n, determine the number of equiv- 13. Given the matrix representing a relation on a finite set,
alence relations on a set with n elements. find the matrix representing the transitive closure of this
∗ 7. Given a positive integer n, display all the equivalence re- relation using Warshall’s algorithm.
lations on the set of the n smallest positive integers.
14. Given the matrix representing a relation on a finite set, find
8. Given an n-ary relation, find the projection of this relation the matrix representing the smallest equivalence relation
when specified fields are deleted.
containing this relation.
9. Given an m-ary relation and an n-ary relation, and a set of
common fields, find the join of these relations with respect 15. Given a partial ordering on a finite set, find a total ordering
to these common fields. compatible with it using topological sorting.

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

1. Display all the different relations on a set with four ele- corresponds to direct links in a particular transportation
ments. or communications network or use a randomly generated
2. Display all the different reflexive and symmetric relations relation.
on a set with six elements. 6. Compute the number of different equivalence relations on a
3. Display all the reflexive and transitive relations on a set set with n elements for all positive integers n not exceeding
with five elements. 20.
∗ 4. Determine how many transitive relations there are on a set 7. Display all the equivalence relations on a set with seven
with n elements for all positive integers n with n ≤ 7. elements.
5. Find the transitive closure of a relation of your choice on ∗ 8. Display all the partial orders on a set with five elements.
a set with at least 20 elements. Either use a relation that ∗ 9. Display all the lattices on a set with five elements.