## Math 220: Discrete Mathematics Study Guide for Exam 2

The second midterm exam is on Wednesday, April 4, during the regular class period.

A proof-writing workshop, led by Kate Finnerty, will be held on Thursday, March 29, 8:30-10:03pm in Seeley Mudd 204.

This exam is cumulative and does include chapters covered on the previous exam. However, it will emphasize material covered since the last midterm. The following is a chapter by chapter guide intended to help you organize the material we have covered in class as you study for your exam. It is only intended to serve as a guideline, and may not explicitly mention everything that you need to study.

3.4: (Divisibility:) You should understand the definition and notation for congruence modulo an integer, and how this is used in proofs. Know how to state and prove the divisibility tests for integers between 2 and 10, excluding 7. You should also know how to extend these ideas to similar divisibility tests for other integers, such as 11, 12, and 25.

5.1-5.3: (Relations:) Know the general defintion of a relation, and what it means for a relation to be reflexive, transitive, symmetric and antisymmetric, and how to prove or disprove these properties. Be able to determine whether a relation is an equivalence relation or partial order relation (or neither). Know what an equivalence class is, and how to find the partition of a set into equivalence classes. Know how to determine if a partial order is a total order, and how to draw a Hasse diagram for a partial order on a set.

6.1-6.2: (Functions:) Know the definition of a function as a particular kind of relation. Be able to find the domain, range and codomain of a function. You should be able to prove whether a function is one-to-one, onto, both or neither. Know how a bijective function is used to compare the number of elements in two finite sets. You should also know how to compose two functions, and what properties carry over to this composition. Know what it means for a function to be invertible, what the inverse function is, and the properties of the inverse. You should also know what we mean by the image and inverse image of a set under a function (even in the case where the function is not invertible).

2.3: (Pigeonhole Principle:) Know the various forms of the pigeonhole principle discussed in class, and how to use this do determine the number of objects needed to satisfy certain conditions. Also know how this is used in non-constructive proofs of existence.

4.2: (Fund. Principle of Counting:) Know the Fundamental (or Multiplicative) Principle of Counting and how it relates to Cartesian products. Practice setting up combinatorial problems as a series of stages with multiple possibilities at each stage, and use this to count all possibilites. Know how to compute the permutation numbers P(n,k).

Please be sure to review homework and example problems for the chapters given above!

As before, the following practice exams is only intended to help you review for the exam. It certainly does not cover everything that might appear on the actual exam, so please make sure you do study all topics discussed in class! However, this should provide you with a sense of the different types of questions you may encounter.

Below is a list of relevant additional practice problems. These do not include problems already assigned for homework, which you should certainly be able to solve.

Section Suggested Problems
4.2 1, 2, 3, 6, 7, 8a
3.4 3, 4, 6a, 7, 8, 11
5.1 3, 6, 8, 9, 11, 15, 17
5.2 1, 2, 3, 4
5.3 1, 6
6.1 2, 4, 5, 6, 11
6.2 2, 5, 6a-d, 7, 8, 10, 14
2.3 3, 7

Maintained by ynaqvi and last modified 03/31/18