Homework

Homework is given out every week and due the following Tuesday. You'll receive a preliminary handout each Monday, with the final version handed out each Thursday and then posted here.

Homework on recurrence equations

This homework was never due. My solutions may be found here:

Homework on relations

This homework was due August 26. My solutions may be found here:
  1. Give an example of a binary relation that is both symmetric and antisymmetric.
  2. State the definition of total order, or linear order. How many linear orders are there on an n-element set A?
  3. Find an example of a set X and binary relations R and S on X such that R and S are symmetric but R ° S is not symmetric.
  4. The symmetric difference of two sets A and B is the set A ⊕ B consisting of the elements of A or B which are not in both A and B. Define a relation ~ on sets so that A ~ B if and only if A ⊕ B is the empty set.
    1. Is ~ reflexive?
    2. Is ~ symmetric, antisymmetric, both, or neither?
    3. Is ~ transitive?
    4. Is ~ an equivalence relation, a partial order, both, or neither?
  5. On the set Z of integers, consider the relations ≡4 and ≡6, respectively the relations for modular arithmetic modulo 4 and modulo 6. Thinking of these relations as sets, find:
    1. ≡4 ∪ ≡6.
    2. ≡4 ∩ ≡6.
    Can you describe these as equivalence modulo some other number?
  6. Let R be the binary relation on the set of people given by R(a,b) iff a is a parent of b. Then we know that R2 = R ° R is the relation "a is a grandparent of b". Similarly describe:
    1. R3.
    2. the transitive closure of R.
  7. [Preorders.] A preorder on a set X is a binary relation on X that is both reflexive and transitive. If « is a preorder on X, then define an equivalence relation ≡ on X by saying that x ≡ y if both x « y and y « x. Then define a relation ≤ on X/≡ by saying that [x] ≤ [y] if x « y.
    1. Show that ≤ is really well-defined. That is, if x ≡ x′ and y ≡ y′, then x « y if and only if x′ « y′. Thus, whether [x] ≤ [y] or not won't depend on which representatives you choose for the equivalence classes.
    2. Show that ≤ is a partial order on X/≡.
  8. Let X be a set. Show that ⊆ is a partial order on the power set of X. What condition must X satisfy for ⊆ to be a total (or linear) order?
  9. Consider the poset (partially ordered set) described by the following Hasse diagram: 
    A B
|/|
C D
|/|
E F
    1. What are the maximal elements of the poset?
    2. What are the minimal elements of the poset?
    3. Which is true: A ≤ D, D ≤ A, both, or neither?
  10. Consider the recurrence equation an+2 = 4an+1 − 4an. Show that an = 2n(1 + n) is a solution of this recurrence equation.

Homework on counting

This homework was due August 20. My solutions may be found here:
  1. Suppose that you're picking out an outfit for the day. You can choose the green pants, the blue pants, or the black pants: 3 possible choices of pants. You can also choose the green shirt, the blue shirt, the white shirt, or the grey shirt: 4 possible choices of shirt. But you know that mixing a green item with a blue item will look bad. Does the product rule for counting directly apply to tell you how many different outfits you could wear? If not, how can you figure this number out anyway?
  2. Suppose that you know the sum rule for only 2 options. Use induction to prove that the sum rule also holds for any natural number k ≥ 2 of options. [Hint: Break up n + 1 options into n options and 1 option.]
  3. [Binomial theorem.] This question explains why the binomial coefficients are called that. Use induction to prove that
    n
    (x + y)n = Σ C(n,i) xi yn−i.
    i=0
    (The formula "x + y" is a binomial.)
  4. Prove that if n is a natural number, then C(2n,2) = 2C(n,2) + n2:
    1. using algebra and the formula for the binomial coefficient in terms of factorials.
    2. using a combinatorial argument applied to the meaning of the binomial coefficient in terms of sets.
  5. Let A and B be sets of sizes m and n, respectively.
    1. Give a formula for the number of functions from A to B. Briefly explain why it's correct.
    2. Give a formula for the number of one-to-one functions from A to B. Briefly explain why it's correct.
    3. Give a formula for the number of invertible functions from A to B. Briefly explain why it's correct.
  6. Prove that if n, r, and k are natural numbers, with k ≤ r ≤ n, then C(n,r) C(r,k) = C(n,k) C(n − k,r − k).
  7. How many different strings can be made by rearranging the letters in the word "MISSISSIPPI"? [Hint: Don't solve this problem by listing them all!]
    1. A bookshelf contains 12 books in a row. How many ways can you choose 5 of these books subject to the condition that you never choose a pair of books that are right next to each other on the shelf?
    2. Generalise this to the case of n books on the shelf and choosing k books. Given a value of n, what condition on k is necessary so that the answer doesn't just come out to zero?
  9. A hideous alien being with 3 feet is searching for socks in the dark. The monster has 27 black socks, 33 grey socks, and 12 navy blue socks. How many socks must it pull out of the drawer to be sure that it has 3 socks of the same colour?
  10. Consider a Cartesian plane (that is, with coordinates) and a pentagon in it whose vertices all have integer coordinates. Show that there is a pair of distinct vertices such that the midpoint of the line joining these two vertices also has integer coordinates.

Homework on reasoning and induction

This homework was due August 12. My solutions may be found here:
  1. Suppose that f: A → B and g: B → C are functions, and consider their composition g ° f: A → C.
    1. If f and g are one-to-one, does it follow that g ° f is one-to-one? If not, give a counterexample.
    2. If f and g are onto, does it follow that g ° f is onto? If not, give a counterexample.
    3. If f and g are invertible, does it follow that g ° f is invertible? If not, give a counterexample.
    4. Show that, if g ° f is one-to-one, then f is one-to-one. Give an example where g ° f is one-to-one but g is not.
    5. Show that, if g ° f is onto, then g is onto. Give an example where g ° f is onto but f is not.
    6. Show that, if g ° f is invertible, then f is one-to-one and g is onto. Give an example where g ° f is invertible, but f is not onto and g is not one-to-one.
  2. Let f be a function from A to B. Suppose that if f−1(S) = f−1(T), then S = T, whenever S and T are subsets of B. Such a function is called an epimorphism. Show that epimorphisms and surjections are the same thing; that is, every epimorphism is a surjection, and evey surjection is an epimorphism.
  3. Suppose that p implies q. That is, if you know p, then you can deduce q. What is the converse of this implication? What is the contrapositive? Which of these can you assume to be correct?
  4. [Disjunctive syllogism.] Show that (p ∨ q) and ¬p together imply q. That is, if you know p ∨ q and you know ¬p, then you can deduce q.
  5. [Resolution.] Show that p ∨ q and ¬p ∨ r together imply q ∨ r.
  6. [Modus tollens.] Show that p → q and ¬q together imply ¬p.
  7. [Hypothetical syllogism.] Show that p → q and q → r together imply p → r.
  8. Show that ∀x P(x) ∨ ∀y Q(y) implies ∀x (P(x) ∨ Q(x)). Is the converse also correct?
  9. Prove that the square of an even number is even:
    1. using a direct proof.
    2. using an indirect proof.
    3. using a proof by contradiction.
    Mention all properties of numbers and all rules of inference that you use in your proof.
  10. Prove that if n is an integer not divisible by 3, then n2 − 1 is divisible by 3. Mention all properties of numbers and all rules of inference that you use in your proof.
  11. [Telescoping sums.] Prove by induction that
    n
    Σ (ai − ai−1) = an − a0.
    i=1
    [Hint: Use the recursive definition of summation (Σ).]
  12. Prove by induction that the sum of the first n odd positive integers is n2. [Hint: Use summation and a formula for the kth odd positive integer.]
  13. Prove by induction that the sum of the angles of a polygon with n sides is (n − 2)180°, for n ≥ 3 an integer. You may use the fact from geometry that the sum of the angles of a triangle is 180°. [Hint: You can divide a polygon with n sides into a triangle and a polygon with n − 1 sides, if n − 1 ≥ 3.]
  14. If Fn is the nth Fibonacci number, show that Fn2 − Fn−1Fn+1 = (−1)n.
  15. Give a recursive definition of the set of all polynomials in a single variable x.

Homework on logic and sets

This homework was due August 5. My solutions may be found here:
  1. State De Morgan's laws. Use truth tables to show why they're correct.
  2. Assume that P is a compound proposition obtained from p1,...,pn by using only negation (NOT, or ¬), disjunction (OR, or ∨), and conjunction (AND, or ∧). State the definition of the dual P* of P.
  3. Assume that P and Q are logically equivalent compound propositions obtained from p1,...,pn by using only negation, disjunction, and conjunction. Show that the duals P* and Q* are also logically equivalent. [Hint: You may want to use De Morgan's laws.]
  4. State the definitions of tautology and contradiction.
  5. Show that (p ∧ (p → q)) → q is a tautology using:
    1. truth tables.
    2. logical equivalences.
  6. [Disjunctive normal form.] A compound proposition is in disjunctive normal form if it obtained by taking the disjunction of conjunctions of the variables and their negations, with one conjunction for each combination of truth values for which the proposition is true. [Hint: Consider individual rows of the truth table.]
    1. Let p1,...,pn be propositions. Given arbitrary truth values t1,...,tn, find a compound proposition which is true exactly when the proposition pi has the truth value ti. [Hint: This can be done using only conjunctions (AND, or ∧) of the propositions pi and their negations.]
    2. Suppose now that a truth table in n propositional variables is specified. Use part 1 to construct a compound proposition with this truth table. [Hint: This can be done using only disjunctions (OR, or ∨) of compound propositions of the form you found in part 1.]
    3. Use parts 1 and 2 to explain why the disjunctive normal form of a truth table always exists.
    4. What is the disjunctive normal form of p → q?
  7. We define the logical operators NAND, or ↑, and NOR, or ↓, by p ↑ q := ¬(p ∧ q) and p ↓ q := ¬(p ∨ q).
    1. Find a proposition equivalent to ¬p using only ↓.
    2. Find a proposition equivalent to p ∧ q using only ↑.
  8. [Functional completeness.] A collection of logical operators is called functionally complete if every truth table in n propositional variables is the truth table of a compound proposition which uses only those logical operators.
    1. Show that ¬, ∧, and ∨ form a functionally complete collection of logical operators. [Hint: Use disjunctive normal form.]
    2. Show that ¬ and ∧ alone form a functionally complete collection of logical operators. [Hint: Use De Morgan's laws.]
    3. Show that ↑ by itself forms a functionally complete collection of logical operators. [Hint: Use problem 7.]
  9. How many different truth tables of compound propositions are there involving n propositional variables? List those involving two propositions p and q. Do you have descriptive names (such as "p AND q") for all of them?
    1. Show that ∀x P(x) ∨ ∀x Q(x) and ∀x ∀y (P(x) ∨ Q(y)) are logically equivalent. [Hint: The new variable y is necessary to combine the quantifications correctly.]
    2. Show that ∀x P(x) ∨ ∃x Q(x) and ∀x ∃y (P(x) ∨ Q(y)) are logically equivalent.
  11. [Prenex normal form.] A proposition is in prenex normal form if it consists of a string of quantifiers (universal or existential) followed by a compound proposition involving no quantifiers.
    1. Put the following statements in prenex normal form:
      1. ¬∀x P(x);
      2. ¬∃x P(x);
      3. ∀x P(x) ∧ ∀x Q(x);
      4. ∀x P(x) ∧ ∃x Q(x);
      5. ∃x P(x) ∧ ∃x Q(x);
      6. ∀x P(x) ∨ ∀x Q(x);
      7. ∀x P(x) ∨ ∃x Q(x);
      8. ∃x P(x) ∨ ∃x Q(x).
      [Hint: Use problem 10 for some of these.]
    2. Show how to transform an arbitrary statement into a statement in prenex normal form. [Hint: Use disjunctive normal form.]
    3. Express ∃!x P(x) ("There exists a unique x such that ...") in prenex normal form. [Hint: You will need to use the statement "x = y".]
  12. Describe a procedure for listing all the subsets of a finite set.
  13. If A,B,C are finite sets, then |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|. Draw a Venn diagram illustrating this; then explain in words why it is true without using the diagram.
  14. Let Ak := {1,2,...,k} for k = 1,2,3,.... In terms of n, find:
    1. A1 ∪ A2 ∪ A3 ∪ ··· ∪ An;
    2. A1 ∩ A2 ∩ A3 ∩ ··· ∩ An;
    3. A2 ∪ A3 ∪ ··· ∪ An (assuming n ≥ 2);
    4. A2 ∩ A3 ∩ ··· ∩ An (assuming n ≥ 2).
  15. State the definitions of domain, codomain and range of a function.
  16. State the definitions of when a function is injective (or one-to-one), surjective (or onto), and bijective (or invertible):
    1. in words;
    2. in logical notation (with quantifiers).
Go back to the MATH 112 homepage.
This web page was written in 2003 by Toby Bartels. Toby reserves no legal rights to it.

Although the page has been preserved in its original form, the files linked from it have been converted to DjVu using Any2DjVu; they can be viewed on almost any operating system using DjVuLibre.

The permanent URI of this web page is http://tobybartels.name/MATH112/2003/homework/.

HTML 5