MTH 220 DISCRETE MATHEMATICS

1. General Objectives: Throughout the course, students will be expected to demonstrate their understanding of Discrete Mathematics by being able to do each of the following:

1.1 Use mathematically correct terminology and notation.

1.2 Construct correct direct and indirect proofs.

1.3 Use division into cases in a proof.

1.4 Use counterexamples.

1.5 Apply logical reasoning to solve a variety of problems.

2. Propositional Logic

2.1 Write English sentences for logical expressions and vice-versa. Use standard notations of propositional logic.

2.2 Complete and use truth tables for expressions involving the following logical connectives: negation, conjunction, disjunction, conditional, and biconditional.

2.3 Define and use the terms: proposition (statement), converse, inverse, contrapositive, tautology, and contradiction.

2.4 Apply standard logical equivalences. Be able to prove that two logical expression are or are not logically equivalent.

2.5 Determine if a logical argument is valid or invalid. Apply standard rules of inference including (but not limited to) Modus Ponens, Modus Tollens, Transitivity, and Elimination.  Recognize fallacies such as the Converse Error and the Inverse Error.

3. Predicate Logic

3.1 Translate between English sentences and symbols for universally and existentially quantified statements, including statements with multiple quantifiers.

3.2 Write the negation of a quantified statement involving either one or two quantifiers.

3.3 Determine if a quantified statement involving either one or two quantifiers is true or false.

4. Elementary Number Theory

4.1 Construct correct direct and indirect (contradiction and contraposition) proofs involving concepts from elementary number theory such as even and odd integers, rational and irrational numbers, and divisibility.

4.2 Find a counter example to show that a proposed statement involving concepts from elementary number theory is false.

4.3 State and use the Quotient-Remainder Theorem (Division Algorithm) and use the mod function.

4.4 State and use the Fundamental Theorem of Arithmetic.

4.5 Apply the Euclidean Algorithm.

5. Mathematical Induction

5.1 State the Principle of Mathematical Induction.

5.2 Construct induction proofs involving summations, inequalities, and divisibility arguments.

6. Set Theory

6.1 Use set notation, including the notations for subsets, unions, intersections, differences, complements, cross (Cartesian) products, and power sets.

6.2 Prove that a proposed statement involving sets is true, or give a counterexample to show that it is false. In particular, be able to prove that a set is empty.

6.3 Understand and use the terms cardinality, finite, countably infinite, and uncountably infinite, and determine which of these characteristics is associated with a given set.

7. Combinatorics

7.1 Solve counting problems involving the multiplication rule, permutations, and combinations (with and without replacement).  Use standard notation.

7.2 Apply the Addition Rule and the Principle of Inclusion and Exclusion.

7.3 Use Pascal’s formula and Pascal’s Triangle.

7.4 Apply the Binomial Theorem.

7.5 Apply the Pigeonhole Principle.

7.6 Use the basic ideas of discrete probability.

8. Functions

8.1 Define and use the terms function, domain, codomain, range, image, inverse image (pre-image), and composition.

8.2 State the definitions of one-to-one functions (injections), onto functions (surjections), and one-to-one correspondences (bijections). Determine which of these characteristics is associated with a given function.

8.3 Prove that a given function in one-to-one, or give a counterexample to show that it is not.

8.4 Prove that a given function is onto, or give a counterexample to show that it is not.

8.5 Describe the connection between bijective functions and inverses. Be able to find the inverse of an invertible function.

8.6 Explain the connection between cardinality of sets and one-to-one correspondences, and be able to prove that two sets have the same cardinality.

8.7 Find and prove a big-O estimate of growth for a given function.

9. Relations

9.1 State the definitions of binary relation, reflexive, symmetric, transitive, equivalence relation, equivalence class, class representative, and partition.

9.2 Show that a binary relation on a set is an equivalence relation, or give a counterexample to show that it is not.

9.3 Given an equivalence relation on a set, find the equivalence classes of the relation and show that they form a partition of the set.

9.4 Show that congruence modulo m is an equivalence relation on the integers, and that congruence classes modulo m form a partition of the integers.

(revised 02/06)