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  a | b and b | c, then a | c.
Proof.
Suppose  a | b and b | c.
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 a | c, by definition of divisibility. ■


(b)  (10 points)  If A and B are sets, then  2^A⋃2^B⊆ 2^(A⋃B) .
Proof.
Suppose x∈2^A⋃2^B.
This means x∈2^A or x∈2^B, by definition of union.
Thus x⊆A or x⊆B , by definition of power set.
If  x⊆A, then also  x⊆A⋃B, which means  x∈2^(A⋃B).
If  x⊆B, then also  x⊆A⋃B, which means  x∈2^(A⋃B).
Either way,  x∈2^(A⋃B).
This has shown that if  x∈2^A⋃2^B, then  x∈2^(A⋃B).
Therefore   2^A⋃2^B⊆ 2^(A⋃B) . ■

(c) (5 points) Present a counterexample which disproves  2^(A⋃B) ⊆ 2^A⋃2^B .

Counterexample:
Let A = {1} and B = {2}.
Then 2^(A⋃B) = 2^{1, 2} = {∅, {1}, {2}, {1, 2} }
Also 2^A⋃2^B = {∅, {1}} ⋃ {∅, {2}} = {∅, {1}, {2} }.
From this, you can see that  2^(A⋃B) ⊆ 2^A⋃2^B  is not a true statement.

(2)  (5 points)  Write a truth table for the expression  (¬ (x → y)) ∨ (¬ (y→x)) .

x    y    x → y   y→x     (¬ (x → y)) ∨ (¬ (y→x))
---------------------------------------------------------------
T   T        T           T                         F
T   F        F           T                         T
F  T         T           F                         T
F  F         T           T                         F


(3) Suppose A = {0, 2} and B = {0, x}. Write out the following sets by listing their elements (if any) between curly braces.

(a) (3 points)     A △ B = {2, x}

(b) (3 points)   A × B = { (0,0), (0,x), (2,0), (2,x) }

(c) (3 points)     2^A - 2^B ={ {2}, {0,2} }

(d) (3 points)     {x∈A : | x | ≤1} ={0}

(e)  (3 points)   {x⊆A : | x | ≤1} ={∅, {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
| A⋂B |= (3)(8)(7)(2)

| A⋃B | = | A | +| B | -| A⋂B |= 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 A⋃B = A, then B⊆A.

Proof.
Suppose x∈B.
Then of course  x∈A⋃B.
But since  A⋃B = A, the above line becomes  x∈A.
Thus we have shown that if  x∈B then   x∈A.
This means  B⊆A. ■


(b) (5 points)   Prove or present a counterexample:   If  A, and B are sets for which  A × B = B × A, then A = B.

Here is a counterexample. Let A = ∅ and B = {1}.
Then    A × B = {(a, b) : a∈A and b∈B} = ∅ (Because A is empty).
Also    B × A = {(b, a) :   b∈B and a∈A} = ∅ (Because A is empty).
Then  A × B = ∅ = B × A, but  A≠B.

(7) (5 points)  How many positive divisors does 194,481 have? (Hint: 194,481= 21^4.)

Let's look at the prime factorization:194,481= 21^4 = (3 · 7)^4 = 3^47^4
Thus, any divisor of 194,481 must have form 3^x7^y, where 0≤x, y≤4. There are 5 choices for x and 5 for y so by the multiplication principle, the number of possible divisors is (5)(5) = 25