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 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  .

(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