Fundamental computer science questions with solution
Note remember page numbers
What is the negation of each of these propositions?
a) Steve has more than 100 GB free disk space on his
laptop.
b) Zach blocks e-mails and texts from Jennifer.
c) 7 · 11 · 13 = 999.
d) Diane rode her bicycle 100 miles on Sunday.
6. Suppose that SmartphoneA has 256 MB RAM and 32 GB
ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the
resolution of its camera is 4 MP; and Smartphone C has
128 MB RAM and 32 GB ROM, and the resolution of
its camera is 5 MP. Determine the truth value of each of
these propositions.
a) Smartphone B has the most RAM of these three smartphones.
b) Smartphone C has more ROM or a higher resolution
camera than Smartphone B.
c) Smartphone B has more RAM, more ROM, and a
higher resolution camera than Smartphone A.
d) If Smartphone B has more RAM and more ROM than
Smartphone C, then it also has a higher resolution
camera.
e) Smartphone A has more RAM than Smartphone B if
and only if Smartphone B has more RAM than Smartphone A.
7. Suppose that during the most recent fiscal year, the annual revenue of Acme Computer was 138 billion dollars
and its net profit was 8 billion dollars, the annual revenue
of Nadir Software was 87 billion dollars and its net profit
was 5 billion dollars, and the annual revenue of Quixote
Media was 111 billion dollars and its net profit was
13 billion dollars. Determine the truth value of each of
these propositions for the most recent fiscal year.
a) Quixote Media had the largest annual revenue.
b) Nadir Software had the lowest net profit and Acme
Computer had the largest annual revenue.
c) Acme Computer had the largest net profit or Quixote
Media had the largest net profit.
d) If Quixote Media had the smallest net profit, then
Acme Computer had the largest annual revenue.
e) Nadir Software had the smallest net profit if and only
if Acme Computer had the largest annual revenue.
8. Let p and q be the propositions
p : I bought a lottery ticket this week.
q : I won the million dollar jackpot.
Express each of these propositions as an English sentence.
a) ¬p b) p ∨ q c) p → q
d) p ∧ q e) p ↔ q f ) ¬p → ¬q
g) ¬p ∧ ¬q h) ¬p ∨ (p ∧ q)
9. Let p and q be the propositions “Swimming at the New
Jersey shore is allowed” and “Sharks have been spotted
near the shore,” respectively. Express each of these compound propositions as an English sentence.
a) ¬q b) p ∧ q c) ¬p ∨ q
d) p → ¬q e) ¬q → p f ) ¬p → ¬q
g) p ↔ ¬q h) ¬p ∧ (p ∨ ¬q)
10. Let p and q be the propositions “The election is decided”
and “The votes have been counted,” respectively. Express
each of these compound propositions as an English sentence.
a) ¬p b) p ∨ q
c) ¬p ∧ q d) q → p
e) ¬q → ¬p f ) ¬p → ¬q
g) p ↔ q h) ¬q ∨ (¬p ∧ q)
11. Let p and q be the propositions
p : It is below freezing.
q : It is snowing.
Write these propositions using p and q and logical connectives (including negations).
a) It is below freezing and snowing.
b) It is below freezing but not snowing.
c) It is not below freezing and it is not snowing.
d) It is either snowing or below freezing (or both).
e) If it is below freezing, it is also snowing.
f ) Either it is below freezing or it is snowing, but it is
not snowing if it is below freezing.
g) That it is below freezing is necessary and sufficient
for it to be snowing.
12. Let p, q, and r be the propositions
p : You have the flu.
q : You miss the final examination.
r : You pass the course.
Express each of these propositions as an English sentence.
a) p → q b) ¬q ↔ r
c) q → ¬r d) p ∨ q ∨ r
e) (p → ¬r) ∨ (q → ¬r)
f ) (p ∧ q) ∨ (¬q ∧ r)
13. Let p and q be the propositions
p : You drive over 65 miles per hour.
q : You get a speeding ticket.
Write these propositions using p and q and logical connectives (including negations).
a) You do not drive over 65 miles per hour.
b) You drive over 65 miles per hour, but you do not get
a speeding ticket.
c) You will get a speeding ticket if you drive over
65 miles per hour.
d) If you do not drive over 65 miles per hour, then you
will not get a speeding ticket.
e) Driving over 65 miles per hour is sufficient for getting
a speeding ticket.
f ) You get a speeding ticket, but you do not drive over
65 miles per hour.
g) Whenever you get a speeding ticket, you are driving
over 65 miles per hour.
14. Let p, q, and r be the propositions
p : You get an A on the final exam.
q : You do every exercise in this book.
r : You get an A in this class.
Write these propositions using p, q, and r and logical
connectives (including negations
Represent each of these relations on {1, 2, 3}with a matrix
(with the elements of this set listed in increasing order).
a) {(1, 1), (1, 2), (1, 3)}
b) {(1, 2), (2, 1), (2, 2), (3, 3)}
c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
d) {(1, 3), (3, 1)}
2. Represent each of these relations on {1, 2, 3, 4} with a
matrix (with the elements of this set listed in increasing
order).
a) {(1, 2),(1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
b) {(1, 1), (1, 4), (2, 2), (3, 3), (4, 1)}
c) {(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2),
(3, 4), (4, 1), (4, 2), (4, 3)}
d) {(2, 4),(3, 1), (3, 2), (3, 4)}
3. List the ordered pairs in the relations on {1, 2, 3} corresponding to these matrices (where the rows and columns
correspond to the integers listed in increasing order).
a)
⎡
⎣
101
010
101
⎤
⎦ b)
⎡
⎣
010
010
010
⎤
⎦
c)
⎡
⎣
111
101
111
⎤
⎦
4. List the ordered pairs in the relations on {1, 2, 3, 4} corresponding to these matrices (where the rows and columns
correspond to the integers listed in increasing order).
a)
⎡
⎢
⎢
⎣
1101
1010
0111
1011
⎤
⎥
⎥
⎦
b)
⎡
⎢
⎢
⎣
1110
0100
0011
1001
⎤
⎥
⎥
⎦
c)
⎡
⎢
⎢
⎣
0101
1010
0101
1 0 1 0
⎤
⎥
⎥
⎦
5. How can the matrix representing a relation R on a set A
be used to determine whether the relation is irreflexive?
6. How can the matrix representing a relation R on a set A
be used to determine whether the relation is asymmetric?
7. Determine whether the relations represented by the matrices in Exercise 3 are reflexive, irreflexive, symmetric,
antisymmetric, and/or transitive.
8. Determine whether the relations represented by the matrices in Exercise 4 are reflexive, irreflexive, symmetric,
antisymmetric, and/or transitive.
9. How many nonzero entries does the matrix representing
the relation R on A = {1, 2, 3,..., 100} consisting of the
first 100 positive integers have if R is
a) {(a, b) | a>b}? b) {(a, b) | a = b}?
c) {(a, b) | a = b + 1}? d) {(a, b) | a = 1}?
e) {(a, b) | ab = 1}?
10. How many nonzero entries does the matrix representing
the relation R on A = {1, 2, 3,..., 1000} consisting of
the first 1000 positive integers have if R is
a) {(a, b) | a ≤ b}?
b) {(a, b) | a = b ± 1}?
c) {(a, b) | a + b = 1000}?
d) {(a, b) | a + b ≤ 1001}?
e) {(a, b) | a = 0}?
11. How can the matrix for R, the complement of the
relation R, be found from the matrix representing R,
when R is a relation on a finite set A?
12. How can the matrix for R−1, the inverse of the
relation R, be found from the matrix representing R,
when R is a relation on a finite set A?
13. Let R be the relation represented by the matrix
MR =
⎡
⎣
011
110
101
⎤
⎦ .
Find the matrix representing
a) R−1. b) R. c) R2.
14. Let R1 and R2 be relations on a set A represented by the
matrices
MR1 =
⎡
⎣
010
111
100
⎤
⎦ and MR2 =
⎡
⎣
010
011
111
⎤
⎦ .
Find the matrices that represent
a) R1 ∪ R2. b) R1 ∩ R2. c) R2 ◦ R1.
d) R1 ◦ R1. e) R1 ⊕ R2.
15. Let R be the relation represented by the matrix
MR =
⎡
⎣
010
001
110
⎤
⎦ .
Find the matrices that represent
a) R2. b) R3. c) R4.
The 5-tuples in a 5-ary relation represent these attributes
of all people in the United States: name, Social Security
number, street address, city, state.
a) Determine a primary key for this relation.
b) Under what conditions would (name, street address)
be a composite key?
c) Under what conditions would (name, street address,
city) be a composite key?
10. What do you obtain when you apply the selection operator sC, where C is the condition Room = A100, to the
database in Table 7?
11. What do you obtain when you apply the selection operator sC, where C is the condition Destination = Detroit,
to the database in Table 8?
12. What do you obtain when you apply the selection operator sC, where C is the condition (Project = 2) ∧
(Quantity ≥ 50), to the database in Table 10?
13. What do you obtain when you apply the selection operator sC, where C is the condition (Airline = Nadir) ∨
(Destination = Denver), to the database in Table 8?
14. What do you obtain when you apply the projection P2,3,5
to the 5-tuple (a, b, c, d, e)?
15. Which projection mapping is used to delete the first,
second, and fourth components of a 6-tuple?
16. Display the table produced by applying the projection
P1,2,4 to Table 8.
17. Display the table produced by applying the projection
P1,4 to Table 8.
18. How many components are there in the n-tuples in the
table obtained by applying the join operator J3 to two
tables with 5-tuples and 8-tuples, respectively?
19. Construct the table obtained by applying the join
operator J2 to the relations in Tables 9 and 10.
20. Show that if C1 and C2 are conditions that elements of the n-ary relation R may satisfy, then
sC1∧C2 (R) = sC1 (sC2 (R)).
21. Show that if C1 and C2 are conditions that elements of the n-ary relation R may satisfy, then
sC1 (sC2 (R)) = sC2 (sC1 (R)).
22. Show that if C is a condition that elements of
the n-ary relations R and S may satisfy, then
sC(R ∪ S) = sC(R) ∪ sC(S).
23. Show that if C is a condition that elements of
the n-ary relations R and S may satisfy, then
sC(R ∩ S) = sC(R) ∩ sC(S).
24. Show that if C is a condition that elements of
the n-ary relations R and S may satisfy, then
sC(R − S) = sC(R) − sC(S).
25. Show that if R and S are both n-ary relations, then
Pi1,i2,...,im (R ∪ S) = Pi1,i2,...,im (R) ∪ Pi1,i2,...,im (S).
26. Give an example to show that if R and S are both n-ary
relations, then Pi1,i2,...,im (R ∩ S) may be different from
Pi1,i2,...,im (R) ∩ Pi1,i2,...,im (S).
27. Give an example to show that if R and S are both n-ary
relations, then Pi1,i2,...,im (R − S) may be different from
Pi1,i2,...,im (R) − Pi1,i2,...,im (S).
28. a) What are the operations that correspond to the query
expressed using this SQL statement?
SELECT Supplier
FROM Part_needs
WHERE 1000 ≤ Part_number ≤ 5000
b) What is the output of this query given the database in
Table 9 as input?
29. a) What are the operations that correspond to the query
expressed using this SQL statement?
SELECT Supplier, Project
FROM Part_needs, Parts_inventory
WHERE Quantity ≤ 10
b) What is the output of this query given the databases
in Tables 9 and 10 as input?
30. Determine whether there is a primary key for the relation
in Example 2.
31. Determine whether there is a primary key for the relation
in Example 3.
32. Show that an n-ary relation with a primary key can be
thought of as the graph of a function that maps values of
the primary key to (n − 1)-tuples formed from values of
the other domains.
TABLE 9 Part_needs.
Supplier Part_number Project
23 1092 1
23 1101 3
23 9048 4
31 4975 3
31 3477 2
32 6984 4
32 9191 2
33 1001 1
TABLE 10 Parts_inventory.
Part_number Project Quantity Color_code
1001 1 14 8
1092 1 2 2
1101 3 1 1
3477 2 25 2
4975 3 6 2
6984 4 10 1
9048 4 12 2
9191 2 80 4
Suppose that the relation R on the finite set A is represented by the matrix MR. Show that the matrix that
represents the symmetric closure of R is MR ∨ Mt
R.
14. Show that the closure of a relation R with respect to a
property P, if it exists, is the intersection of all the relations with property P that contain R.
15. When is it possible to define the “irreflexive closure”
of a relation R, that is, a relation that contains R, is irreflexive, and is contained in every irreflexive relation
that contains R?
16. Determine whether these sequences of vertices are paths
in this directed graph.
a) a, b, c, e
b) b, e, c, b, e
c) a, a, b, e, d, e
d) b, c, e, d, a, a, b
e) b, c, c, b, e, d, e, d
f ) a, a, b, b, c, c, b, e, d
a b c
e
d
17. Find all circuits of length three in the directed graph in
Exercise 16.
18. Determine whether there is a path in the directed graph in
Exercise 16 beginning at the first vertex given and ending
at the second vertex given.
a) a, b b) b, a c) b, b
d) a, e e) b, d f ) c, d
g) d,d h) e, a i) e, c
19. Let R be the relation on the set {1, 2, 3, 4, 5} containing
the ordered pairs(1, 3),(2, 4),(3, 1),(3, 5),(4, 3),(5, 1),
(5, 2), and (5, 4). Find
a) R2. b) R3. c) R4. d) R5. e) R6. f ) R∗.
20. Let R be the relation that contains the pair (a, b) if a
and b are cities such that there is a direct non-stop airline
flight from a to b. When is (a, b) in
a) R2? b) R3? c) R∗?
21. Let R be the relation on the set of all students containing the ordered pair (a, b) if a and b are in at least one
common class and a = b. When is (a, b) in
a) R2? b) R3? c) R∗?
22. Suppose that the relation R is reflexive. Show that R∗ is
reflexive.
23. Suppose that the relation R is symmetric. Show that R∗
is symmetric.
24. Suppose that the relation R is irreflexive. Is the
relation R2 necessarily irreflexive?
25. Use Algorithm 1 to find the transitive closures of these
relations on {1, 2, 3, 4}.
a) {(1, 2), (2,1), (2,3), (3,4), (4,1)}
b) {(2, 1), (2,3), (3,1), (3,4), (4,1), (4, 3)}
c) {(1, 2), (1,3), (1,4), (2,3), (2,4), (3, 4)}
d) {(1, 1), (1,4),(2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)}
26. Use Algorithm 1 to find the transitive closures of these
relations on {a, b, c, d, e}.
a) {(a, c), (b, d), (c, a), (d, b), (e, d)}
b) {(b, c), (b, e), (c, e), (d, a), (e, b), (e, c)}
c) {(a, b), (a, c), (a, e), (b, a), (b, c), (c, a), (c, b), (d, a),
(e, d)}
d) {(a, e), (b, a), (b, d), (c, d), (d, a), (d, c), (e, a), (e, b),
(e, c), (e, e)}
27. Use Warshall’s algorithm to find the transitive closures
of the relations in Exercise 25.
28. Use Warshall’s algorithm to find the transitive closures
of the relations in Exercise 26.
29. Find the smallest relation containing the relation
{(1, 2), (1, 4), (3, 3), (4, 1)} that is
a) reflexive and transitive.
b) symmetric and transitive.
c) reflexive, symmetric, and transitive.
30. Finish the proof of the case when a = b in Lemma 1.
31. Algorithms have been devised that use O(n2.8) bit operations to compute the Boolean product of two n × n zero–
one matrices.Assuming that these algorithms can be used,
give big-O estimates for the number of bit operations usingAlgorithm 1 and using Warshall’s algorithm to find the
transitive closure of a relation on a set with n elements.
∗32. Devise an algorithm using the concept of interior vertices
in a path to find the length of the shortest path between
two vertices in a directed graph, if such a path exists.
33. Adapt Algorithm 1 to find the reflexive closure of the
transitive closure of a relation on a set with n elements.
34. Adapt Warshall’s algorithm to find the reflexive closure of
the transitive closure of a relation on a set with n elements.
35. Show that the closure with respect to the property P of
the relation R = {(0, 0), (0, 1), (1, 1), (2, 2)} on the set
{0, 1, 2} does not exist if P is the property
a) “is not reflexive.”
b) “has an odd number of elements.”
1. Which of these relations on {0, 1, 2, 3} are equivalence
relations? Determine the properties of an equivalence relation that the others lack.
a) {(0, 0), (1, 1), (2, 2), (3, 3)}
b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
d) {(0, 0), (1, 1),(1, 3), (2, 2), (2, 3), (3, 1), (3, 2),
(3, 3)}
e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),
(2, 2), (3, 3)}
2. Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack.
a) {(a, b) | a and b are the same age}
b) {(a, b) | a and b have the same parents}
c) {(a, b) | a and b share a common parent}
d) {(a, b) | a and b have met}
e) {(a, b) | a and b speak a common language}
3. Which of these relations on the set of all functions from Z
to Z are equivalence relations? Determine the properties
of an equivalence relation that the others lack.
a) {(f, g) | f (1) = g(1)}
b) {(f, g) | f (0) = g(0) or f (1) = g(1)}
c) {(f, g) | f (x) − g(x) = 1 for all x ∈ Z}
d) {(f, g) | for some C ∈ Z, for all x ∈ Z, f (x) −
g(x) = C}
e) {(f, g) | f (0) = g(1) and f (1) = g(0)}
4. Define three equivalence relations on the set of students
in your discrete mathematics class different from the relations discussed in the text. Determine the equivalence
classes for each of these equivalence relations.
5. Define three equivalence relations on the set of buildings
on a college campus. Determine the equivalence classes
for each of these equivalence relations.
6. Define three equivalence relations on the set of classes offered at your school. Determine the equivalence classes
for each of these equivalence relations.
7. Show that the relation of logical equivalence on the set
of all compound propositions is an equivalence relation.
What are the equivalence classes of F and of T?
8. Let R be the relation on the set of all sets of real numbers
such that SRT if and only if S and T have the same
cardinality. Show that R is an equivalence relation. What
are the equivalence classes of the sets {0, 1, 2} and Z?
9. Suppose that A is a nonempty set, and f is a function that
has A as its domain. Let R be the relation on A consisting
of all ordered pairs (x, y) such that f (x) = f (y).
a) Show that R is an equivalence relation on A.
b) What are the equivalence classes of R?
10. Suppose that A is a nonempty set and R is an equivalence
relation on A. Show that there is a function f with A as its
domain such that (x, y) ∈ R if and only if f (x) = f (y).
11. Show that the relation R consisting of all pairs(x, y)such
that x and y are bit strings of length three or more that
agree in their first three bits is an equivalence relation on
the set of all bit strings of length three or more.
12. Show that the relation R consisting of all pairs (x, y) such
that x and y are bit strings of length three or more that
agree except perhaps in their first three bits is an equivalence relation on the set of all bit strings of length three
or more.
13. Show that the relation R consisting of all pairs(x, y)such
that x and y are bit strings that agree in their first and third
bits is an equivalence relation on the set of all bit strings
of length three or more.
14. Let R be the relation consisting of all pairs (x, y) such
that x and y are strings of uppercase and lowercase English letters with the property that for every positive integer n, the nth characters in x and y are the same letter,
either uppercase or lowercase. Show that R is an equivalence relation.
15. Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if
a + d = b + c. Show that R is an equivalence relation.
16. Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if
ad = bc. Show that R is an equivalence relation.
17. (Requires calculus)
a) Show that the relation R on the set of all differentiable
functions from R to R consisting of all pairs (f, g)
such that f
(x) = g
(x) for all real numbers x is an
equivalence relation.
b) Which functions are in the same equivalence class as
the function f (x) = x2?
18. (Requires calculus)
a) Let n be a positive integer. Show that the relation
R on the set of all polynomials with real-valued
coefficients consisting of all pairs (f, g) such that
f (n)(x) = g(n)(x) is an equivalence relation. [Here
f (n)(x) is the nth derivative of f (x).]
b) Which functions are in the same equivalence class as
the function f (x) = x4, where n = 3?
19. Let R be the relation on the set of all URLs (or Web addresses) such that xRy if and only if the Web page at
x is the same as the Web page at y. Show that R is an
equivalence relation.
20. Let R be the relation on the set of all people who have
visited a particular Web page such that xRy if and only
if person x and person y have followed the same set of
links starting at this Web page (going from Web page to
Web page until they stop using the Web). Show that R is
an equivalence relation.
In Exercises 21–23 determine whether the relation with the
directed graph shown is an equivalence relation.
21.
a b
c d
22.
a b
d c
23.
a b
d c
24. Determine whether the relations represented by these
zero–one matrices are equivalence relations.
a)
⎡
⎣
111
011
111
⎤
⎦ b)
⎡
⎢
⎢
⎣
1010
0101
1010
0101
⎤
⎥
⎥
⎦
c)
⎡
⎢
⎢
⎣
1110
1110
1110
0001
⎤
⎥
⎥
⎦
25. Show that the relation R on the set of all bit strings such
that sRt if and only if s and t contain the same number
of 1s is an equivalence relation.
26. What are the equivalence classes of the equivalence relations in Exercise 1?
27. What are the equivalence classes of the equivalence relations in Exercise 2?
28. What are the equivalence classes of the equivalence relations in Exercise 3?
29. What is the equivalence class of the bit string 011 for the
equivalence relation in Exercise 25?
30. What are the equivalence classes of these bit strings for
the equivalence relation in Exercise 11?
a) 010 b) 1011 c) 11111 d) 01010101
31. What are the equivalence classes of the bit strings
in Exercise 30 for the equivalence relation from
Exercise 12?
32. What are the equivalence classes of the bit strings
in Exercise 30 for the equivalence relation from
Exercise 13?
33. What are the equivalence classes of the bit strings in Exercise 30 for the equivalence relation R4 from Example 5 on the set of all bit strings? (Recall that bit strings s
and t are equivalent under R4 if and only if they are equal
or they are both at least four bits long and agree in their
first four bits.)
34. What are the equivalence classes of the bit strings in Exercise 30 for the equivalence relation R5 from Example 5
on the set of all bit strings? (Recall that bit strings s and
t are equivalent under R5 if and only if they are equal or
they are both at least five bits long and agree in their first
five bits.)
35. What is the congruence class [n]5 (that is, the equivalence class of n with respect to congruence modulo 5)
when n is
a) 2? b) 3? c) 6? d) −3?
36. What is the congruence class [4]m when m is
a) 2? b) 3? c) 6? d) 8?
37. Give a description of each of the congruence classes
modulo 6.
38. What is the equivalence class of each of these strings with
respect to the equivalence relation in Exercise 14?
a) No b) Yes c) Help
39. a) What is the equivalence class of (1, 2) with respect to
the equivalence relation in Exercise 15?
b) Give an interpretation of the equivalence classes for
the equivalence relation R in Exercise 15. [Hint: Look
at the difference a − b corresponding to (a, b).]
40. a) What is the equivalence class of (1, 2) with respect
to the equivalence relation in Exercise 16?
b) Give an interpretation of the equivalence classes for
the equivalence relation R in Exercise 16. [Hint: Look
at the ratio a/b corresponding to (a, b).]
41. Which of these collections of subsets are partitions of
{1, 2, 3, 4, 5, 6}?
a) {1, 2},{2, 3, 4},{4, 5, 6} b) {1}, {2, 3, 6}, {4}, {5}
c) {2, 4, 6}, {1, 3, 5} d) {1, 4, 5}, {2, 6}
42. Which of these collections of subsets are partitions of
{−3, −2, −1, 0, 1, 2, 3}?
a) {−3, −1, 1, 3}, {−2, 0, 2}
b) {−3, −2, −1, 0}, {0, 1, 2, 3}
c) {−3, 3}, {−2, 2}, {−1, 1}, {0}
d) {−3, −2, 2, 3}, {−1, 1}
43. Which of these collections of subsets are partitions of the
set of bit strings of length 8?
a) the set of bit strings that begin with 1, the set of bit
strings that begin with 00, and the set of bit strings
that begin with 01
b) the set of bit strings that contain the string 00, the set
of bit strings that contain the string 01, the set of bit
strings that contain the string 10, and the set of bit
strings that contain the string 11
c) the set of bit strings that end with 00, the set of bit
strings that end with 01, the set of bit strings that end
with 10, and the set of bit strings that end with 11
d) the set of bit strings that end with 111, the set of bit
strings that end with 011, and the set of bit strings that
end with 00
e) the set of bit strings that contain 3k ones for some
nonnegative integer k; the set of bit strings that contain 3k + 1 ones for some nonnegative integer k; and
the set of bit strings that contain 3k + 2 ones for some
nonnegative integer k.
44. Which of these collections of subsets are partitions of the
set of integers?
a) the set of even integers and the set of odd integers
b) the set of positive integers and the set of negative integers
the set of integers divisible by 3, the set of integers
leaving a remainder of 1 when divided by 3, and the
set of integers leaving a remainder of 2 when divided
by 3
d) the set of integers less than −100, the set of integers
with absolute value not exceeding 100, and the set of
integers greater than 100
e) the set of integers not divisible by 3, the set of even
integers, and the set of integers that leave a remainder
of 3 when divided by 6
45. Which of these are partitions of the set Z × Z of ordered
pairs of integers?
a) the set of pairs (x, y), where x or y is odd; the set
of pairs (x, y), where x is even; and the set of pairs
(x, y), where y is even
b) the set of pairs (x, y), where both x and y are odd;
the set of pairs (x, y), where exactly one of x and y
is odd; and the set of pairs (x, y), where both x and y
are even
c) the set of pairs (x, y), where x is positive; the set of
pairs (x, y), where y is positive; and the set of pairs
(x, y), where both x and y are negative
d) the set of pairs (x, y), where 3 | x and 3 | y; the set
of pairs (x, y), where 3 | x and 3 | y; the set of pairs
(x, y), where 3 | x and 3 | y; and the set of pairs
(x, y), where 3 | x and 3 | y
e) the set of pairs (x, y), where x > 0 and y > 0; the
set of pairs (x, y), where x > 0 and y ≤ 0; the set of
pairs (x, y), where x ≤ 0 and y > 0; and the set of
pairs (x, y), where x ≤ 0 and y ≤ 0
f ) the set of pairs (x, y), where x = 0 and y = 0; the set
of pairs (x, y), where x = 0 and y = 0; and the set of
pairs (x, y), where x = 0 and y = 0
46. Which of these are partitions of the set of real numbers?
a) the negative real numbers, {0}, the positive real
numbers
b) the set of irrational numbers, the set of rational
numbers
c) the set of intervals [k, k + 1], k = ..., −2, −1, 0,
1, 2,...
d) the set of intervals (k, k + 1), k = ..., −2, −1, 0,
1, 2,...
e) the set of intervals (k, k + 1], k = ..., −2, −1, 0,
1, 2,...
f ) the sets {x + n | n ∈ Z} for all x ∈ [0, 1)
47. List the ordered pairs in the equivalence relations produced by these partitions of {0, 1, 2, 3, 4, 5}.
a) {0}, {1, 2}, {3, 4, 5}
b) {0, 1}, {2, 3}, {4, 5}
c) {0, 1, 2}, {3, 4, 5}
d) {0}, {1}, {2}, {3}, {4}, {5}
48. List the ordered pairs in the equivalence relations produced by these partitions of {a, b, c, d, e, f, g}.
a) {a, b}, {c, d}, {e, f, g}
b) {a}, {b}, {c, d}, {e, f }, {g}
c) {a, b, c, d}, {e, f, g}
d) {a, c, e, g}, {b, d}, {f }
A partition P1 is called a refinement of the partition P2 if
every set in P1 is a subset of one of the sets in P2.
49. Show that the partition formed from congruence classes
modulo 6 is a refinement of the partition formed from
congruence classes modulo 3.
50. Show that the partition of the set of people living in the
United States consisting of subsets of people living in the
same county (or parish) and same state is a refinement of
the partition consisting of subsets of people living in the
same state.
51. Show that the partition of the set of bit strings of length 16
formed by equivalence classes of bit strings that agree on
the last eight bits is a refinement of the partition formed
from the equivalence classes of bit strings that agree on
the last four bits.
In Exercises 52 and 53, Rn refers to the family of equivalence
relations defined in Example 5. Recall that s Rn t, where s
and t are two strings if s = t or s and t are strings with at least
n characters that agree in their first n characters.
52. Show that the partition of the set of all bit strings formed
by equivalence classes of bit strings with respect to the
equivalence relation R4 is a refinement of the partition
formed by equivalence classes of bit strings with respect
to the equivalence relation R3.
53. Show that the partition of the set of all identifiers in C
formed by the equivalence classes of identifiers with respect to the equivalence relation R31 is a refinement of
the partition formed by equivalence classes of identifiers
with respect to the equivalence relation R8. (Compilers
for “old” C consider identifiers the same when their names
agree in their first eight characters, while compilers in
standard C consider identifiers the same when their names
agree in their first 31 characters.)
54. Suppose that R1 and R2 are equivalence relations on a
set A. Let P1 and P2 be the partitions that correspond to
R1 and R2, respectively. Show that R1 ⊆ R2 if and only
if P1 is a refinement of P2.
55. Find the smallest equivalence relation on the set
{a, b, c, d, e} containing the relation {(a, b), (a, c),
(d, e)}.
56. Suppose that R1 and R2 are equivalence relations on the
set S. Determine whether each of these combinations
of R1 and R2 must be an equivalence relation.
a) R1 ∪ R2 b) R1 ∩ R2 c) R1 ⊕ R2
57. Consider the equivalence relation from Example 2,
namely, R = {(x, y) | x − y is an integer}.
a) What is the equivalence class of 1 for this equivalence
relation?
b) What is the equivalence class of 1/2 for this equivalence relation?
) Show that there is exactly one greatest element of a
poset, if such an element exists.
b) Show that there is exactly one least element of a poset,
if such an element exists.
41. a) Show that there is exactly one maximal element in a
poset with a greatest element.
b) Show that there is exactly one minimal element in a
poset with a least element.
42. a) Show that the least upper bound of a set in a poset is
unique if it exists.
b) Show that the greatest lower bound of a set in a poset
is unique if it exists.
43. Determine whether the posets with these Hasse diagrams
are lattices.
a)
a
b
d
c
e
f
g
b)
a
b
d
c
e
f g
h
c)
a
b
d
c
e
f g
h
i
44. Determine whether these posets are lattices.
a) ({1, 3, 6, 9, 12}, |) b) ({1, 5, 25, 125}, |)
c) (Z, ≥)
d) (P (S), ⊇), where P (S) is the power set of a set S
45. Show that every nonempty finite subset of a lattice has a
least upper bound and a greatest lower bound.
46. Show that if the poset (S, R) is a lattice then the dual
poset (S, R−1) is also a lattice.
47. In a company, the lattice model of information flow is used
to control sensitive information with security classes represented by ordered pairs (A, C). Here A is an authority
level, which may be nonproprietary (0), proprietary (1),
restricted (2), or registered (3).A category C is a subset of
the set of all projects {Cheetah, Impala, Puma}. (Names
of animals are often used as code names for projects in
companies.)
a) Is information permitted to flow from (Proprietary,
{Cheetah, Puma}) into (Restricted, {Puma})?
b) Is information permitted to flow from (Restricted,
{Cheetah}) into (Registered, {Cheetah, Impala})?
c) Into which classes is information from (Proprietary,
{Cheetah, Puma}) permitted to flow?
d) From which classes is information permitted to flow
into the security class (Restricted, {Impala, Puma})?
48. Show that the set S of security classes (A, C) is a lattice,
where A is a positive integer representing an authority
class and C is a subset of a finite set of compartments,
with (A1, C1) (A2, C2) if and only if A1 ≤ A2 and
C1 ⊆ C2. [Hint: First show that(S, )is a poset and then
show that the least upper bound and greatest lower bound
of (A1, C1) and (A2, C2) are (max(A1, A2), C1 ∪ C2)
and (min(A1, A2), C1 ∩ C2), respectively.]
∗49. Show that the set of all partitions of a set S with the relation P1 P2 if the partition P1 is a refinement of the
partition P2 is a lattice. (See the preamble to Exercise 49
of Section 9.5.)
50. Show that every totally ordered set is a lattice.
51. Show that every finite lattice has a least element and a
greatest element.
52. Give an example of an infinite lattice with
a) neither a least nor a greatest element.
b) a least but not a greatest element.
c) a greatest but not a least element.
d) both a least and a greatest element.
53. Verify that (Z+× Z+, ) is a well-ordered set, where
is lexicographic order, as claimed in Example 8.
54. Determine whether each of these posets is well-ordered.
a) (S, ≤), where S = {10, 11, 12,...}
b) (Q ∩ [0, 1], ≤) (the set of rational numbers between
0 and 1 inclusive)
c) (S, ≤), where S is the set of positive rational numbers
with denominators not exceeding 3
d) (Z−, ≥), where Z− is the set of negative integers
A poset (R, ) is well-founded if there is no infinite decreasing sequence of elements in the poset, that is, elements
x1, x2,...,xn such that ···≺ xn ≺···≺ x2 ≺ x1. A poset
(R, ) is dense if for all x ∈ S and y ∈ S with x ≺ y, there
is an element z ∈ R such that x ≺ z ≺ y.
55. Show that the poset (Z, ), where x ≺ y if and only if
|x| < |y| is well-founded but is not a totally ordered set.
56. Show that a dense poset with at least two elements that
are comparable is not well-founded.
57. Show that the poset of rational numbers with the usual
“less than or equal to” relation, (Q, ≤), is a dense poset.
∗58. Show that the set of strings of lowercase English letters with lexicographic order is neither well-founded nor
dense.
59. Show that a poset is well-ordered if and only if it is totally
ordered and well-founded.
60. Show that a finite nonempty poset has a maximal element.
61. Find a compatible total order for the poset with the Hasse
diagram shown in Exercise 32.
62. Find a compatible total order for the divisibility relation
on the set {1, 2, 3, 6, 8, 12, 24, 36}.
63. Find all compatible total orderings for the poset
({1, 2, 4, 5, 12, 20}, |} from Example 26.
64. Find all compatible total orderings for the poset with the
Hasse diagram in Exercise 27.
65. Find all possible orders for completing the tasks in the
development project in Example 27.
TERMS
binary relation from A to B: a subset of A × B
relation on A: a binary relation from A to itself (i.e., a subset
of A × A)
S ◦ R: composite of R and S
R−1: inverse relation of R
Rn: nth power of R
reflexive: a relation R on A is reflexive if (a, a) ∈ R for all
a ∈ A
symmetric: a relation R on A is symmetric if(b, a) ∈ R whenever (a, b) ∈ R
antisymmetric: a relation R on A is antisymmetric if a = b
whenever (a, b) ∈ R and (b, a) ∈ R
transitive: a relation R on A is transitive if (a, b) ∈ R and
(b, c) ∈ R implies that (a, c) ∈ R
n-ary relation on A1, A2,...,An: a subset of A1× A2 ×
···× An
relational data model: a model for representing databases using n-ary relations
primary key: a domain of an n-ary relation such that an ntuple is uniquely determined by its value for this domain
composite key: the Cartesian product of domains of an n-ary
relation such that an n-tuple is uniquely determined by its
values in these domains
selection operator: a function that selects the n-tuples in an
n-ary relation that satisfy a specified condition
projection: a function that produces relations of smaller degree from an n-ary relation by deleting fields
join: a function that combines n-ary relations that agree on
certain fields
directed graph or digraph: a set of elements called vertices
and ordered pairs of these elements, called edges
loop: an edge of the form (a, a)
closure of a relation R with respect to a property P: the relation S (if it exists) that contains R, has property P, and
is contained within any relation that contains R and has
property P
path in a digraph: a sequence of edges (a, x1), (x1, x2), . . . ,
(xn−2, xn−1), (xn−1, b)such that the terminal vertex of each
edge is the initial vertex of the succeeding edge in the sequence
circuit (or cycle) in a digraph: a path that begins and ends at
the same vertex
R∗ (connectivity relation): the relation consisting of those
ordered pairs (a, b) such that there is a path from a to b
equivalence relation: a reflexive, symmetric, and transitive
relation
equivalent: if R is an equivalence relation, a is equivalent to
b if aRb
[a]R (equivalence class of a with respect to R): the set of all
elements of A that are equivalent to a
[a]m (congruence class modulo m): the set of integers congruent to a modulo m
partition of a set S: a collection of pairwise disjoint nonempty
subsets that have S as their union
partial ordering: a relation that is reflexive, antisymmetric,
and transitive
poset (S, R): a set S and a partial ordering R on this set
comparable: the elements a and b in the poset (A, ) are
comparable if a b or b a
incomparable: elements in a poset that are not comparable
total (or linear) ordering: a partial ordering for which every
pair of elements are comparable
totally (or linearly) ordered set: a poset with a total (or linear)
ordering
well-ordered set: a poset (S, ), where is a total order
and every nonempty subset of S has a least element
Use Theorem 4 to determine whether the graphs in Example 11 are bipartite.
Solution: We first consider the graph G. We will try to assign one of two colors, say red and
blue, to each vertex in G so that no edge in G connects a red vertex and a blue vertex. Without
loss of generality we begin by arbitrarily assigning red to a. Then, we must assign blue to c, e,
f , and g, because each of these vertices is adjacent to a. To avoid having an edge with two blue
endpoints, we must assign red to all the vertices adjacent to either c, e, f , or g. This means that
we must assign red to both b and d (and means that a must be assigned red, which it already has
been). We have now assigned colors to all vertices, with a, b, and d red and c, e, f , and g blue.
Checking all edges, we see that every edge connects a red vertex and a blue vertex. Hence, by
Theorem 4 the graph G is bipartite.
Next, we will try to assign either red or blue to each vertex in H so that no edge in H
connects a red vertex and a blue vertex. Without loss of generality we arbitrarily assign red to a.
Then, we must assign blue to b, e, and f , because each is adjacent to a. But this is not possible
because e and f are adjacent, so both cannot be assigned blue. This argument shows that we
cannot assign one of two colors to each of the vertices of H so that no adjacent vertices are
assigned the same color. It follows by Theorem 4 that H is not bipartite. ▲
Theorem 4 is an example of a result in the part of graph theory known as graph colorings.
Graph colorings is an important part of graph theory with important applications. We will study
graph colorings further in Section 10.8.
Another useful criterion for determining whether a graph is bipartite is based on the notion
of a path, a topic we study in Section 10.4. A graph is bipartite if and only if it is not possible
to start at a vertex and return to this vertex by traversing an odd number of distinct edges. We
will make this notion more precise when we discuss paths and circuits in graphs in Section 10.4
(see Exercise 63 in that section).
Paul Erd˝os, born in Budapest, Hungary, was the son of two high school mathematics teachers. He was a child prodigy; at age 3 he could multiply three-digit numbers in his head, and at 4 he
discovered negative numbers on his own. Because his mother did not want to expose him to contagious diseases,
he was mostly home-schooled. At 17 Erd˝os entered E˝otv˝os University, graduating four years later with a Ph.D.
in mathematics. After graduating he spent four years at Manchester, England, on a postdoctoral fellowship. In
1938 he went to the United States because of the difficult political situation in Hungary, especially for Jews.
He spent much of his time in the United States, except for 1954 to 1962, when he was banned as part of the
paranoia of the McCarthy era. He also spent considerable time in Israel.
Erd˝os made many significant contributions to combinatorics and to number theory. One of the discoveries
of which he was most proud is his elementary proof (in the sense that it does not use any complex analysis) of the prime number
theorem, which provides an estimate for the number of primes not exceeding a fixed positive integer. He also participated in the
modern development of the Ramsey theory.
Erd˝os traveled extensively throughout the world to work with other mathematicians, visiting conferences, universities, and
research laboratories. He had no permanent home. He devoted himself almost entirely to mathematics, traveling from one mathematician to the next, proclaiming “My brain is open.” Erd˝os was the author or coauthor of more than 1500 papers and had more
than 500 coauthors. Copies of his articles are kept by Ron Graham, a famous discrete mathematician with whom he collaborated
extensively and who took care of many of his worldly needs.
Erd˝os offered rewards, ranging from $10 to $10,000, for the solution of problems that he found particularly interesting, with the
size of the reward depending on the difficulty of the problem. He paid out close to $4000. Erd˝os had his own special language, using
such terms as “epsilon” (child), “boss” (woman), “slave” (man), “captured” (married), “liberated” (divorced), “Supreme Fascist”
(God), “Sam” (United States), and “Joe” (Soviet Union). Although he was curious about many things, he concentrated almost all
his energy on mathematical research. He had no hobbies and no full-time job. He never married and apparently remained celibate.
Erd˝os was extremely generous, donating much of the money he collected from prizes, awards, and stipends for scholarships and to
worthwhile causes. He traveled extremely lightly and did not like having many material possessions.
Finding an assignment of jobs to employees can be thought of as finding a matching in the
graph model, where a matching M in a simple graph G = (V , E) is a subset of the set E of
edges of the graph such that no two edges are incident with the same vertex. In other words, a
matching is a subset of edges such that if {s,t} and {u, v} are distinct edges of the matching,
then s, t, u, and v are distinct. A vertex that is the endpoint of an edge of a matching M is said to
be matched in M; otherwise it is said to be unmatched. A maximum matching is a matching
with the largest number of edges. We say that a matching M in a bipartite graph G = (V , E)
with bipartition (V1, V2) is a complete matching from V1 to V2 if every vertex in V1 is the
endpoint of an edge in the matching, or equivalently, if |M|=|V1|. For example, to assign jobs
to employees so that the largest number of jobs are assigned employees, we seek a maximum
matching in the graph that models employee capabilities. To assign employees to all jobs we
seek a complete matching from the set of jobs to the set of employees. In Example 14, we found
a complete matching from the set of jobs to the set of employees for Project 1, and this matching
is a maximun matching, and we showed that no complete matching exists from the set of jobs
to the employees for Project 2.
We now give an example of how matchings can be used to model marriages
Comments
Post a Comment