Discrete Structures
Spring 2014
MP Johnson

Practice Exercises 1

Due: never, but you should do as many as possible!


1. Verify both de Morgan's rules. (This means: write out their truth tables, and observe
that the two things each of de Morgan's rules say are equal indeed have the same truth
value in all rows of the truth table.)


2. Translate the following sentences from English to predicate logic.
The domain that you are working over is X, the set of people. You may 
use the functions T(x), meaning that "x has take CMP 232," A(x), 
meaning that "x has gotten an 'A' in CMP 232," S(x), meaning that "x 
is a senior," and E(x,y), meaning that "x and y are the same person."

a) There are people who have taken CMP 232 and have gotten A's in 
CMP 232.

b) All seniors who have taken CMP 232 got A's in CMP 232

c) Only seniors get A's in CMP 232.


3. The binary logical connectives ∧ (and), ∨ (or), and -> (implies)
appear often in not only computer programs, but also everyday speech.
In computer chip designs, however, it is considerably easier to
construct these out of another operation, nand, which is simpler to
represent in a circuit. Here is the truth table for nand:

  P   |   Q   | P nand Q
------------------------
 true |  true | false
 true | false | true
false |  true | true
false | false | true

a) For each of the following expressions, find an equivalent
expression using only nand and -(not), as well as grouping parentheses 
to specify the order in which the operations apply. You may use A, B, 
and the operators any number of times.

i) A ∧ B
ii) A ∨ B
iii) A -> B

b) It is actually possible to express each of the above using only
nand, without needing to use -. Find an equivalent expression for (-A) 
using only nand and grouping parentheses.


4. Apply the proof of the irrationality of sqrt(2) to a) sqrt(3) and
b) sqrt(4). If the proof breaks down, indicate precisely why.
(Do not simply say that the result is false, if it is, explain
at what step the attempted proof fails (if it does).)


In all induction problems below, clearly state the statement P(n) to be 
proved, and clearly indicate the base case and the inductive assumption.

5. Prove by induction that for all nonnegative integers n:

SUM_{i=1 to n} i^3 = ( n*(n+1)/2 )^2

(This is cumbersome but follows the usual pattern--you just have to
be careful at each step. (Being neat helps!))


6. Prove by induction that, for all integers n>=1 and real numbers r!=1,

	SUM_{i=0}^n r^i = (r^(n+1) - 1) / (r-1).


7. Prove by induction that, for all integers n>=4, 2^n < n!.


8. Prove by induction that, for all integers n>=6, 2^n > n^2.


9. Prove by induction that, for all integers n>=1, 2 divides n^2 + n.


10. Prove by induction that, for all integers n>=1, 3 divides n^3 + 2n.


11. Prove by strong induction that every amount of postage of 12 cents 
or more can be formed using just 4-cent and 5-cent stamps.


12. What amounts of money can be formed using just two-dollar bills and 
five-dollar bills? Prove you answer by strong induction.


Exercises from the Rosen textbook (7th edition):

Note that there are solutions to all odd-numbered exercises in the back
of the book. Here I'm picking out particular exercises doing things we've
learned how to do in class, or solving things of a similar flavor to
things we've solved in class. For each of these, there are often multiple
similar problems nearby it in the text. Practice solving as many of these
as you need to become comfortable with them, comparing your solutions to
those in the back.

LOGIC:

section 1.1 exercises:

9,11, 
21,23, 
29,30,31

section 1.3 exercises:

16,18,19
35
61

section 1.4 exercises:

5,7,9,10
13,14
23,25
33

section 1.5 exercises:

1,3,7,9
45

section 1.7 exercises:

1,2,3,6,11,13

review questions (page 111):

7

supplementary exercises (page 111):

1,21,30,31


SETS:

section 2.1 exercises:

1

section 2.2 exercises:

1,3
52,53

section 2.4 exercises:

29,33


INDUCTION:

section 5.1 exercises:

1,3,4,6
11,15
21
31,32,33,34

section 5.2 exercises:

3,4,14