Offers an intensive introduction to discrete mathematics as it is used in computer science.

Topics include functions, relations, sets, propositional and predicate logic, simple circuit

logic, proof techniques, elementary combinatorics, and discrete probability.

Prerequisites: Mathematical preparation sufficient to take calculus at the college level.

• Fundamental structures: Functions (surjections, injections, inverses, composition);

relations (reflexivity, symmetry, transitivity, equivalence relations); sets (Venn

diagrams, complements, Cartesian products, power sets); pigeonhole principle;

cardinality and countability

• Basic logic: Propositional logic; logical connectives; truth tables; normal forms

(conjunctive and disjunctive); validity; predicate logic; limitations of predicate logic;

universal and existential quantification; modus ponens and modus tollens

• Digital logic: Logic gates, flip-flops, counters; circuit minimization

• Proof techniques: Notions of implication, converse, inverse, contrapositive, negation,

and contradiction; the structure of formal proofs; direct proofs; proof by

counterexample; proof by contraposition; proof by contradiction; mathematical

induction; strong induction; recursive mathematical definitions; well orderings

• Basics of counting: Counting arguments; pigeonhole principle; permutations and

combinations; recurrence relations

• Discrete probability: Finite probability spaces; conditional probability, independence,

Bayes’ rule; random events; random integer variables; mathematical expectation

DS1 Functions, relations, and sets 6 core hours

DS2 Basic logic 10 core hours

DS3 Proof techniques 9 core hours (of 12)

DS4 Basics of counting 5 core hours

DS6 Discrete probability 6 core hours

AR1 Digital logic and digital systems 3 core hours (of 6)

Elective topics 1 hour