All answers should be explained. Most of these questions are asking for some form of proof, since you should take "show" and "determine" to be synonyms for "prove". However, you no longer have to follow the specific proof forms covered in the beginning of the course. Instead, proofs should involve useful prose to explain the steps. Refer to examples in class and in the book. Also, remember the general comment from the course grading guide: "Good style means giving a sound logical argument and a clear presentation, sufficient to convince someone who knows the same background material, but not the answer, that your answer is correct. Consider your audience to be a skeptical classmate. Good style also implies that an answer should be reasonably thorough, but reasonably concise."
Read Sections 1.6—1.7 on your own. This material is largely a restatement of concepts sprinkled throughout our coverage of logic and proofs.
Remember that Rosen provides solutions for the odd-numbered problems at the back of the book. Those provide useful examples for doing the homework problems.
The following problems total to 100 points.
(5 points) Rosen 6th ed., Section 1.6 #6
Use a direct proof to show that the product of two odd numbers is odd.
(10 points) Rosen 6th ed., Section 1.6 #18ab
Prove that if n is an integer and 3n+2 is even, then n is even using
(5 points) Rosen 6th ed., Section 1.7 #12
Prove or disprove that if a and b are rational numbers, then ab is also rational.
(10 points) Rosen 6th ed., Section 2.1 #20
Can you conclude that A=B if A and B are two sets with the same power set?
I.e., it is asking for a proof.
(10 points) Rosen 6th ed., Section 2.1 #30
Show that A×B≠B×A, when A and B are nonempty, unless A=B.
To make the premises clearer, you may want to rephrase this using "if" rather than "when", and "if not" rather than "unless".
(5 points) Rosen 6th ed., Section 2.2 #2a-d
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
(5 points) Rosen 6th ed., Section 2.2 #12
Prove the first absorption law from Table 1 by showing that if A and B are sets, then A∪(A∩B) = A.
(5 points) Rosen 6th ed., Section 2.2 #24
Let A, B, and C be sets. Show that (A-B)-C = (A-C)-(B-C).
You may reason directly from the definition of set-difference and set-equality. Alternately, you may use set identities. These two approaches are reminiscent of inference rules and algebraic identities we've previously used.
(5 points) Rosen 6th ed., Section 2.2 #40
The symmetric difference of A and B, denoted by A⊕B, is the set containing those elements in either A or B, but not in both A and B.
Determine whether the symmetric difference is associative; that is, if A, B, and C are sets, does it follow that A⊕(B⊕C) = (A⊕B)⊕C?
Briefly explain your answer. A Venn diagram might be useful to figure it out.
(5 points) Rosen 6th ed., Section 2.2 #46a-b
Let Ai = {…, -2, -1, 0, 1, …, i}. Find
Use the vocabulary/definitions at hand to provide concise answers.
(2 points) Rosen 6th ed., Section 2.2 #50b
Suppose that the universal set is U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Express the set {1, 3, 6, 10} with a bit string where the ith bit in the string is 1 if i is in the set and 0 otherwise.
(3 points) Rosen 6th ed., Section 8.3 #6
How can the matrix representing a relation R on a set A be used to determine whether the relation is asymmetric?
(5 points) Rosen 6th ed., Section 8.3 #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?
Briefly explain your answer.
(5 points) Rosen 6th ed., Section 8.4 #24
Suppose that the relation R is irreflexive. Is the relation R2 necessarily irreflexive?
(5 points) Rosen 6th ed., Section 8.4 #26b
Use Algorithm 1 to find the transitive closures of the relation {(b,c), (b,e), (c,e), (d,a), (e,b), (e,c)} on {a, b, c, d, e}.
(10 points) Rosen 6th ed., Section 8.5 #2a-e
Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack.
(5 points) Rosen 6th ed., Section 8.5 #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.