CSci 420/520: Homework 1

Discrete Math

Due Wednesday, September 7th by 1pm.

Summary

This is a little review assignment for discrete math concepts.

Questions

1. P({1,2,3}) = ?
2. P(∅) = ?
3. Given A = {a,b,c,d}, B = {b,c,z}:
   1. A ∩ B = ?
   2. A ∪ B = ?
   3. A \ B = ?
   4. #( A × B ) = ?
   5. Give two sets that partition B.
4. Given the relations A = {(a,b),(b,d),(c,d),(d,e)}, B = {(a,c),(c,e),(d,d)}, X = {a,b,c,d,e}. Assume A and B are functions from X to X:
   1. What is the definition domain of B?
   2. Is A partial or total? Why?
   3. Is A onto? Why or why not?
   4. #B = ?
   5. B^T = ?
   6. A;B = ?
   7. A ∪ B = ?
   8. ( A ∪ B )⁺ = ?
5. Using quantification, but not the # operator, write an expression that states that the set S has at least two elements.
6. Simplify the Boolean expression (p ∧ ¬q) ⇒ (¬p ∨ q) using the laws of Boolean logic. Refer to the laws in Table 12.2 of Tucker and Noonan. You will also need the "Law of Double Negation", which states ¬¬p ⇔ p.
7. Use a truth table to prove that your simplified equation is logically the same as the original. Each column in the truth table should only involve one new operator on the previous columns.
8. Write a set comprehension for the function whose domain and range are the natural numbers, and that maps each natural number to the the product of the number and its predecessor. Use only one free variable in your answer.
9. Prove by induction that . Be sure to state the basis, inductive hypothesis, and inductive step, and to justify each step.

Grading

100 points total. Harder questions will be worth more.

Turn in your answers in class. Remember, a messy paper indicates sloppy thinking.