Math 3503 - Discrete Structures P.

Math 3503 - Discrete Structures Midterm, Fall 1990

Work carefully. Be sure to think and plan before you start writing. Don't get stuck on any one problem - go on and come back ...

1. (6) What is a proposition? Give an example of something which is a proposition and of something which is not a proposition.

2. (10) Give truth tables for the five fundamental connectives.

3. (5) Give the truth table for

   

4. (6) Let . Circle the true statements.
   1. 
   2. 
   3. 
   4. 
   5. 
   6. 

5. (4) What is the power set of ?

6. (8) Show that if , then .

7. (5) What is a function? What is a 1-1 function? What is an onto function?

8. (15) Which of the following are functions? Which are relations but not functions? Of those which are functions, which are one-to-one? Which are onto? Of those which are relations, which are equivalence relations? (If domains are not clear, assume N, the natural numbers.)
   1. with domain
   2. 
   3. 
   4. { (a, b) | a and b are both evenly divisible by 5 }
   5. 
   6. with domain and range

9. (8) Find the symmetric closure, the transitive closure, and the transitive closure of the symmetric closure of:

10. (20) Prove by induction that:
    1. 

    2. is divisible by 4, for any positive natural number n.

    3. Postage of 18 cents or more can be made using only 7-cent and 4-cent stamps.

    4. Show that n straight lines divide the plane into regions. Assume that no two lines are parallel and that no three lines have a common point.

11. (16) Sort according to Big-Oh:

    

• About this document ...