210 TEST TOPICS  2006 Feb 14  MATH 210 :  DISCRETE MATH  Dr. Luft

REVIEW 1     Sections 1.0 through 2.0
Be able to state De Morgan's laws in set algebra.
          (AuB)'  =  A'nB'     and     (AnB)'  =  A'uB'
Be able to state the contrapositive law in set algebra.
          A c B   iff   B' c A'
Use a truth table to prove statements in set algebra.
Describe the Cartesian product of two finite sets.  (List the ordered pairs.)
Construct the inverse of a given relation.
Decide whether a given relation is a function.
Prove that congruence (mod m) is an equivalence relation.
Compute arithmetic expressions modulo m.
Prove parts abcd for the Theorem on composed functions.
Given a relation: tell whether it is reflexive, symmetric, antisymmetric, transitive.
     If a relation is a partial order, draw its Hasse diagram.
     If a relation is an equivalence, describe its equivalence classes.
Be able to state the contrapositive law in propositional calculus.
          A --> B   iff   ¬B --> ¬A
Know the difference between contrapositive and converse.

REVIEW 2    Sections 2.1 through 3.2
Prove theorems by mathematical induction.
Quantifiers and Negation
The Multiplication Rule
Permutations, combinations, and committees
Coefficients in a binomial expansion
Count the possible ordered and unordered samples of size k from a set of size n.
(?Count subsets, relations, functions, one-to-one functions?)

REVIEW 3    Sections 4.0 through 5.2
Decide whether a graph has an Euler cycle.
Draw a graph, given its adjacency matrix or its cost matrix.
Spanning Trees and Minimal Spanning Trees.
Pre-, In-, Post-order Searches
Construct the minimal spanning tree for a graph and find its (total) cost.
Prove Euler's theorem by induction.
Apply Euler's theorem to a planar connected graph.
Apply the edge-vertex inequality to determine whether a graph is planar.
Use a truth table to prove a law of Propositional Calculus

REVIEW FOR THE FINAL EXAMINATION (Subject to change)
Selected topics from the above.
Use a truth table to prove statements in propositional calculus.
Simplify an expression in the propositional calculus.
Simplify an expression in Boolean Algebra.
(Be able to apply De Morgan's laws in set algebra, propositional calculus, and Boolean algebra.)
Prove (or disprove) that a specific function is (or is not) one-to-one or onto.
Boolean Algebra:  simplify an expression; find a minterm expansion.