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. ![■](HTMLFiles/1F03Asol_7.gif)
(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
. ![■](HTMLFiles/1F03Asol_24.gif)
(c) (5 points) Present a counterexample which disproves
.
Counterexample:
Let A = {1} and B = {2}.
Then ![2^(A⋃B) = 2^{1, 2} = {∅, {1}, {2}, {1, 2} }](HTMLFiles/1F03Asol_26.gif)
Also
.
From this, you can see that
is not a true statement.
(2) (5 points) Write a truth table for the expression
.
x y
![(¬ (x → y)) ∨ (¬ (y→x))](HTMLFiles/1F03Asol_32.gif)
---------------------------------------------------------------
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 3-letter 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 length-4 lists can be made if repetition is allowed?
(10)(10)(10)(10) = 10,000
(b) (5 points) How many length-4 lists can be made if repetition is not allowed?
(10)(9)(8)(7) = 5,040
(c) (5 points) How many length-4 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 length-4 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 length-4 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 length-4 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
. ![■](HTMLFiles/1F03Asol_52.gif)
(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![= 21^4 = (3 · 7)^4 = 3^47^4](HTMLFiles/1F03Asol_61.gif)
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