Disclaimer: The following lists the topics which we will cover. It is subject to change.

The section numbers are from the text,
      Discrete Mathematics and its Applications. Kenneth Rosen. Random House, New York, New York. 2006. Sixth Edition

(Last Updated: 11/03/09 )

1.1 Logic Propositions. Compound propositions. Connectives: negation, conjunction, disjunction, implication. Precedence. Converse. Contrapositive. Bits. Boolean Variables.

1.2 Logic Equivalence of propositions. Logical Equivalence. Tautology. Contradiction. Contingency. Laws of Logic.

1.3 Predicates Universal and Existential quantifiers. Universe of discourse. Logical Equivalences.

1.4 Predicates Nested quantifiers. Negating nested quantifiers.

2.1 Sets Universal set. Empty (null) set. Subsets. Venn Diagrams. Cardinality. Power Sets. Cartesian products. Truth sets of predicates.

2.2 Set Operations Union, intersection, complement, difference. Inclusion-Exclusion. Disjoint sets. Identities. Membership tables. Generalized union and intersections. Bit vector representation of finite sets.

2.3 Functions Domain. Co-domain. Range. Image. Pre-image. Image and Pre-image of a set. Injective, surjective and bijective functions. Composition and Inverses.

1.5-1.7 Proofs Rules of Inference. Fallacies. Rules of Inference wih Quatifiers. Theorems. Axioms. Postulates. Vacuous and trivial proofs. Direct and indirect proofs. Proof by contradiction. Proof by cases. Existence proofs. Non-constructive versus constructive proofs.

2.4 Sequences and Summations Sequences and strings. Indexed summations. Summations over sets. Geometic Progressions. (optional Cardinality)

3.4-3.5 Integers Integer division. Prime and composite numbers. Fundamental Theorem of arithmetic. GCD and LCM. Relative primality. Modular arithmetic. Cryptology(optional).

4.1-4.2 Induction Well-Ordering Property. Sum of geometric progression. Sum of Harmonic numbers. Second principle of mathematical induction.

4.3 Recursion Recursive (inductive) definitions. Recursively defined sets.

7.1-7.2 Recurrences Fibonacci numbers. Characteristic equations.

5.1 Counting Sum rule. Product rule. Inclusion-exclusion. Tree diagrams.

5.2 Counting Pigeonhole principle. Generalized pigeonhole principle.

5.3 Counting r-permutations. r-combinations.

5.4 Counting Binomial theorem. Binomial coefficients. Pascal's identity and triangle.

5.5 Generalized Permutations Permutations and combinations with repetition and indistinguishable objects.

6.1 Probability Finite probability. Combinations of events.

6.2 Probability Conditional probability. Independence. Bernoulli Trials. Binomial distribution.

7.5 Inclusion-exclusion Derangements.

11.1 Boolean Functions Boolean variables, expressions and functions. Boolean sum and products. Boolean identities. Duality.

11.2-11.3 Forms and Gates Sum of products. Minterms. Disjunctive and conjunctive normal form. Universality. Logic networks.

8.1-8.2 Relations Binary relations. Relations on a set. Properties: reflexive, symmetric, antisymmetric, and transitive. Composition of relations. n-ary relations.

Portions of the CMPE016 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited.