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

The first midterm exam is on Friday, February 23, during the regular class period.

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.

1.1 - 1.3: (Sets:) Be able to read and use the notation for sets discussed in these chapters. Know the definitions of cardinality, subset, power set, intersection, union, disjoint, nested, complement and Cartesian product, and be able to find the elements of a described set. You should also know (and be able to apply) De Morgan's Laws, the Distributive Laws and the various counting theorems given in these sections. Know how to verify whether a given collection is a partition and be able to construct an appropriate partition that might be useful for counting the elements of a set.

1.4- 1.6: (Logic:) You should be comfortable reading and using the symbols for "not", "and", "or", "there exists", "for all" and "implies". You should be able to interpret compound statements made up of given simple statements, and construct truth tables to show all possible truth values of a statement or the equivalence between two statements. You should also be able to construct statements that take on certain true/false values in a truth table. Know the statements of De Morgan's Laws and the Distributive Laws, and how to use them in proofs. Know what we mean by tautology, contradiction, converse, contrapositive, necessary and sufficient. Be able to find the negations of given statements and prove or disprove statements involving quantifiers or implications.

2.1 - 2.2: (Proof Techniques:) Make sure you are familiar with the proof techniques discussed in class, which include direct proof from the definition, using the contrapositive or a contradiction, and proof by induction. You should be know how to prove the following theorems from the book: 2.1.2, 2.1.3, 2.1.4, 2.1.7, 2.1.8, 2.1.9, 2.1.10, 2.1.11, 2.1.12, 2.2.4, 2.2.5. You should also be familiar with the proofs from the class and homework examples.

3.1-3.2: (Divisibility:) Know the definitions of divisor, multiple, divides, prime, composite, and gcd. You must know the statements and proofs of the following theorems: 3.1.3, 3.1.4, 3.1.7, 3.1.8, 3.1.9 (the Division Algorithm), 3.1.11, 3.1.12. You should also know how to use the Euclidean Algorithm (Theorem 3.2.1) to find greatest common divisors.

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

The following practice exams is intended to help you review for the exam and give you a sense of the format of the exam. It certainly does not cover all topics 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 could encounter, including computational problems, proof problems and true/false problems.

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

Section Suggested Problems
1.1 1, 4, 5, 9, 10
1.2 1, 3, 5, 8, 10, 12
1.3 3, 6, 8
1.4 2, 3, 4, 5, 9, 11, 12, 13, 14
1.5 1, 3, 4
1.6 1, 3, 8, 10
2.1 6, 9, 11
2.2 2, 6a, 7, 10
3.1 6, 13, 18, 20, 21
3.2 1, 9, 10