Page 210 - Discrete Mathematics and Its Applications

Computer Projects 189

Computer Projects

Write programs with the specified input and output.

1. Given subsets A and B of a set with n elements, use bit 6. Given a bijection f from the set {1, 2,...,n} to itself, find
strings to find A, A ∪ B, A ∩ B, A − B, and A ⊕ B. f −1 .
2. Given multisets A and B from the same universal set, find 7. Given an m × k matrix A and a k × n matrix B, find AB.
n
A ∪ B, A ∩ B, A − B, and A + B (see preamble to Exer- 8. Given a square matrix A and a positive integer n, find A .
cise 61 of Section 2.2). 9. Given a square matrix, determine whether it is symmetric.
3. Given fuzzy sets A and B, find A, A ∪ B, and A ∩ B (see 10. Given two m × n Boolean matrices, find their meet and
preamble to Exercise 63 of Section 2.2). join.
4. Given a function f from {1, 2,...,n} to the set of integers, 11. Given an m × k Boolean matrix A and a k × n Boolean
determine whether f is one-to-one. matrix B, find the Boolean product of A and B.
5. Given a function f from {1, 2,...,n} to itself, determine 12. Given a square Boolean matrix A and a positive integer n,
[n]
whether f is onto. find A .

Computations and Explorations

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

1. Given two finite sets, list all elements in the Cartesian prod- you determine a formula for the number of such functions?
uct of these two sets. (We will find such a formula in Chapter 8.)
2. Given a finite set, list all elements of its power set.
3. Calculate the number of one-to-one functions from a set S ∗ 5. Develop a collection of different rules for generating the
to a set T , where S and T are finite sets of various sizes. Can terms of a sequence and a program for randomly selecting
you determine a formula for the number of such functions? one of these rules and the particular sequence generated
(We will find such a formula in Chapter 6.) using these rules. Make this part of an interactive program
4. Calculate the number of onto functions from a set S to a that prompts for the next term of the sequence and deter-
set T , where S and T are finite sets of various sizes. Can mines whether the response is the intended next term.

Writing Projects

Respond to these with essays using outside sources.

1. Discuss how an axiomatic set theory can be developed to 4. Define the recently invented EKG sequence and describe
avoid Russell’s paradox. (See Exercise 46 of Section 2.1.) some of its properties and open questions about it.
5. Look up the definition of a transcendental number. Explain
2. Research where the concept of a function first arose, and
how to show that such numbers exist and how such num-
describe how this concept was first used.
bers can be constructed. Which famous numbers can be
3. Explain the different ways in which the Encyclopedia of shown to be transcendental and for which famous numbers
Integer Sequences has been found useful. Also, describe is it still unknown whether they are transcendental?
a few of the more unusual sequences in this encyclopedia 6. Expand the discussion of the continuum hypothesis in the
and how they arise. text.