Discrete Structures 
Test #1

October 8, 2003

Name____________________ 
R. Hammack

Score ______

(1) Write proofs of the following statements. Be sure to work strictly from the definitions.
(a) (10 points) If a, b, and c are integers for which and , then .
Proof.
Suppose and .
By definition of divisibility, there are integers x and y for which ax = b and by = c.
Then c = by = (ax)y = a(xy).
Thus there is an integer z = xy for which az = c.
Then , by definition of divisibility.
(b) (10 points) If A and B are sets, then .
Proof.
Suppose .
This means or , by definition of union.
Thus or , by definition of power set.
If , then also , which means .
If , then also , which means .
Either way, .
This has shown that if , then .
Therefore .
(c) (5 points) Present a counterexample which disproves .
Counterexample:
Let A = {1} and B = {2}.
Then
Also .
From this, you can see that is not a true statement.
(2) (5 points) Write a truth table for the expression .
x y

T T T T F
T F F T T
F T T F T
F F T T F
(3) Suppose and . Write out the following sets by listing their elements (if any) between curly braces.
(a) (3 points) {2, x}
(b) (3 points) { (0,0), (0,x), (2,0), (2,x) }
(c) (3 points) { {2}, {0,2} }
(d) (3 points) {0}
(e) (3 points) {, {0}, {2}}
(4) This problem concerns 3letter codes made from the letters A, B, C, ... , Z of the English alphabet (repetition OK).
(a) (5 points) How many such codes can be made?
(26)(26)(26) = 17,576
(b) (5 points) How many such codes are there that do not have two consecutive letters the same?
(26)(25)(25) = 16, 250
(5) The problems on this page concern lists made from the symbols {A, B, C, D, E, F, G, H, I, J}.
(a)(5 points) How many length4 lists can be made if repetition is allowed?
(10)(10)(10)(10) = 10,000
(b) (5 points) How many length4 lists can be made if repetition is not allowed?
(10)(9)(8)(7) = 5,040
(c) (5 points) How many length4 lists can be made if repetition is not allowed, and the list must begin with a vowel?
(3)(9)(8)(7) = 1,512
(d) (5 points) How many length4 lists can be made if repetition is not allowed, and the list must end with a vowel?
(7)(8)(9)(3) = 1,512
(e) (5 points) How many length4 lists can be made if repetition is not allowed, and the list must begin with a vowel or end with a vowel?
A = set of such lists beginning with a vowel. A = (3)(9)(8)(7) = 1,512
B = set of such lists ending with a vowel. B = (7)(8)(9)(3) = 1,512
= (3)(8)(7)(2)
= 1,512 + 1, 512  336 = 2,688
(f) (5 points) How many length4 lists can be made if repetition is not allowed, and the list contains exactly one A?
Let A be the set of such lists of form A _ _ _
Let B be the set of such lists of form _ A _ _
Let C be the set of such lists of form _ _ A _
Let D be the set of such lists of form _ _ _ A
By the multiplication principle, each of these sets contains (9)(8)(7) = 504 lists.
Also, the sets are pairwise disjoint, so the addition principle applies to give us a total of
504 +504 +504 +504 = 2,016 such lists
(6)
(a) (5 points) Prove or present a counterexample: If , then .
Proof.
Suppose .
Then of course .
But since , the above line becomes .
Thus we have shown that if then .
This means .
(b) (5 points) Prove or present a counterexample: If A, and B are sets for which , then .
Here is a counterexample. Let A = and B = {1}.
Then (Because A is empty).
Also (Because A is empty).
Then , but .
(7) (5 points) How many positive divisors does 194,481 have? (Hint: 194,481.)
Let's look at the prime factorization:194,481
Thus, any divisor of 194,481 must have form , where . There are 5 choices for x and 5 for y so by the multiplication principle, the number of possible divisors is (5)(5) = 25