Homework


Please prepare to explain your answers in class.

Sets

Appendix A1: Exercises 1, 3, 5, 7, 9, 11(d),(e), 17. 

Relations

  1. Can a relation R in a set A be both symmetric and antisymmetric?
  2. Let A = {1, 2, 3}.  Give an example of a relation R in A such that R is neither symmetric nor antisymmetric.
  3. Show that the relation Q on the set A = { (a, b) | a, b are integers and b is not 0} is an equivalence relation where Q is defined as (a,b)Q(c,d) if and only if ad = bc.
  4. Prove that any integer that is a square must have one of the following for its units digit: 0, 1, 4, 5, 6, 9.
  5. Prove that any fourth power must have one of 0, 1, 5, 6 for its units digit.
  6. Determine whether or not the 328th day and the 104th day of the year fall on the same day of the week.
  7. Show that if R is an antisymmetric relation, so is R-1.
  8. Show that if R is a symmetric relation, then R intersection R-1 = R.
  9. Show that if R and S are an antisymmetric relations, then so is R intersection S.  What about R union S?

Functions

  1. Let X = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, Y = { true, false }.
    1. How many surjective functions are there from X to Y?
    2. How many surjective functions are there from Y to X?
    3. How many surjective functions are there from Y to Y?
  2. If f is a surjective function from X to Y, what can we say about |X| relative to |Y|?
  3. Let X = { 1, 2, 3 }, Y = { A, B, C, D }.
    1. How many injective functions are there from X to Y?
    2. How many injective functions are there from Y to X?
    3. How many injective functions are there from X to X?
  4. If f is an injective function from X to Y, what can we say about |X| relative to |Y|?
  5. If f is an bijective function from X to Y, what can we say about |X| relative to |Y|?
  6. Let X be a finite set.  How many bijective functions are there from X to X ?
  7. How many unary operators are there for true-false logic?  That is, how many functions are there from { true, false } to { true, false } ?  List them.

Propositional logic

  1. How many binary operators are there for true-false logic?
  2. Is the following a tautology: ( ( (p or q) implies r] and (~p) ) implies (q implies r)?  Use a truth table as a proof.
  3. Consider the propositions:
    1. p: David is playing pool.
    2. q: David is inside.
    3. r: David is doing his homework.
    4. s: David is listening to music.
  4. Translate the following sentences into symbolic notation using p, q, r, s, ~, or, and, and parentheses only.
    1. Either David is playing pool or he is inside.
    2. Neither is David playing pool, nor is he doing his homework.
    3. David is playing pool and not doing his homework.
    4. David is inside doing his homework, not playing pool.
    5. David is inside doing his homework while listening to music, and he is not playing pool.
    6. David is not listening to music, nor is he playing pool, neither is he doing his homework.
    7. If David is playing pool and listening to music, then he is not doing his homework.
  5. Using the specifications of p, q, r, and s above, translate the following propositions into acceptable English:
    1. (~p) and (~q).
  6. Restate the following as implications "If ..., then ..."
    1. A necessary condition that a given quadrelateral ABCD be a rectangle is that it be a parallelogram.
    2. A sufficient condition that ABCD be a rectangle is that it be a square.
    3. A necessary condition that a given integer n be divisible by 9 is that it is divisible by 3.
    4. A sufficient condition that a given integer n be divisibile by 9 is that it be divisible by 18.
    5. A sufficient condition for n to be divisible by 9 is that the sum of the digits be divisible by 9.
  7. State the converse, opposite, and contrapositive to the following:
    1. If triangle ABC is a right triangle, then |AB|2 + |BC|2 = |AC|2.
  8. Determine whether each of the following inferences is valid or faulty. If the inference is valid, produce some evidence that confirms its validity. If the inference is faulty, produce a combination of truth values that confirms or indicates a fallacy.
    9. The governor will call a special session only if the Senate cannot reach a compromise.
    If a majority of the Cabinet are in agreement, then the governor will call a special session.
    The Senate can reach a compromise.
    Hence, a majority of the Cabinet are in agreement.
    The governor will call a special session only if the Senate cannot reach a compromise.
     If a majority of the Cabinet are in agreement, then the governor will call a special session.
     The Senate can reach a compromise.
     Hence, a majority of the Cabinet are not in agreement.
    The governor will call a special session only if the Senate cannot reach a compromise.
    If a majority of the Cabinet are in agreement, then the governor will call a special session.
    The Senate can reach a compromise.
    Hence, the governor will not call a special session.
    The new people in the neighborhood have a nice dog.
    They also have a nice car.
    Hence, they must be nice people.
  9. Determine whether each of the folllowing inference patterns is valid or invalid.   If the inference is valid, produce some evidence that confirms its validity.  If the inference is invalid, indicate a combination of truth values that produces a counterexample.
r implies s
~ s
Therefore, ~r.

(p and q) implies ~t
w or r
w implies p
r implies q
Therefore, (w or r) implies ~t.

~r implies (s implies ~t)
~r or w
~p implies s
~w
Therefore, t implies p.

~p
p implies q
q implies r
Therefore, ~r.
  1. Are the following arguments valid?  Give evidence for your answer.
If Joe or Abe needs a vacation, then Ted deserves an assistant.
Hence, if Joe needs a vacation, then Ted deserves an assistant.

If Joe is a mathematician, then he is ambitious.
          If Joe is an early riser, then he does not like oatmeal.
          If Joe is ambitious, then he is an early riser.
Hence, if Joe is a mathematician, then he does not like oatmeal.

If Clifton does not live in France, then he does not speak French.
         Clifton does not drive a Nissan.
         If Clifton lives in France, then he rides a bicycle.
         Either Clifton speaks French or he drives a Nissan.
         Hence, Clifton rides a bicycle.

Proving Implications

Pigeon-Hole Principle

Appendix A.4, exercises 2 - 6, 8.

First-Order Logic

Mathematical Induction

  1. Appendix 2, exercises 1 (Can you also give a geometric proof?), 2, 7, 9, 12, 23, 24, 25.
  2. Prove by mathematical induction that 11n+2 + 122n+1 is divisible by 133.
  3. Let S be a set with n elements.  Using mathematical induction, show that |P(S)| = 2n.

Two Basic Counting Principles

Section 5.1

Simple Arrangements & Selections

Section 5.2

Arrangements & Selections with Repetitions

Section 5.3

Distributions

Section 5.4

Binomial Identities

Section 5.5

Generating Function Models

Section 6.1

Calculating Coefficients of Generating Functions

Recurrence Relation Models