This course presents a survey of topics in discrete mathematics most relevant to students studying computer science. At the end of the semester, all students will be able to do the following:

1. Construct basic mathematical arguments using propositional logic, including structures such as quantified statements,
normal form constructions, and Boolean algebra constructions.

2. Carry out set-theoretic operations to describe and compare unordered collections.

3. Relate sets to functions; use functions to describe complexity as well as basic and recursive sequences and progressions.

4. Select and use an appropriate proof strategy for a potential or known theorem.

5. Carry out operations on different integer representations and construct valid arguments for statements related to
modular arithmetic.

6. Construct valid arguments for statements related to counting and discrete probability.

Major topics covered:

1. Logic and Predicates
a) Propositional Logic: construct compound propositions for various logic statements and natural language propositions.
b) Propositional Equivalencies (Identities): use the identity laws to show propositional equivalencies and verify their truth 
    values.
c) Truth Tables: construct truth tables for compound propositions and use them as a tool for proving equivalencies.
d) Normal Forms: transform compound propositions into conjunctive normal form and disjunctive normal forms, including 
    the canonical normal forms.
e) Minimization: reduce the number of propositional variables and operators of a compound proposition to an equivalent 
    proposition.
f) Predicates and Quantifiers: construct compound propositions for various logic statements involving predicates and 
   quantified statements.
g) Rules of Inferences: use the laws of inference to derive a given conclusion from a set of propositions.
h) Boolean Algebra and Circuits: use Boolean algebra.

2. Set Theory
a) Sets and Operations: define set structures using different notations and define and use operations on sets.
b) Subsets and Powersets: define subsets of a set and construct the powerset.
c) Set Identities and Equality: use the identity laws of sets to show two sets are equal.

3. Functions
a) Function Types: define one-to-one, onto, and one-to-one correspondence functions using propositional logic; given a 
    function proves that it is any of the three and whether it has an inverse or not.
b) Sequences: determine that a given sequence is an arithmetic or geometric progression and identify the associated 
    constants.
c) Recursive Definitions and Recurrences: construct recursive definitions for relations and sets; define the recurrence relation of sequences with its initial condition(s).
d) Summations: understand the recursive and iterative properties of summations.
e) Cardinality of sets, countability, and diagonalization given a finite set determine the cardinality; given an infinite set, 
    determine whether it is countable or uncountable.
f) Given a growth function, determine its best Big-O complexity class.

4. Proof Strategies
a) Be able to form a valid argument from a set of assumptions using each of the following proof strategies: direct, 
    contraposition, and contradiction.
b) Be able to form a valid argument using each of the following proof strategies: construction and counterexample.
c) Induction: prove a property holds for a discrete infinite set with the smallest value.
d) Given incorrect proof, identify the error.
e) Be able to select an appropriate proof strategy for any given theorem.

5. Number Theory
a) Divisibility and Modular Arithmetic: given two numbers find their divisor and remainder; use properties of divisibility and 
    modular arithmetic in a proof.
b) Congruence Relations: prove the identity laws for congruence relations.
c) Integer Representations (base conversions): given an integer in one base, convert it to another base with a special focus on base 2, 8, 10, and 16.
d) Bitwise Operations: apply logic operators on bit strings.
e) Primes and Composites: identify whether a number is prime or composite; identify the prime factors of a composite 
    number.
f) Euclidean Algorithm: trace through the Euclidean algorithm to find the GCD.

6. Counting
a) Rules of Counting: use the product and sum rules to determine the cardinality of a set.
b) The Pigeonhole Principle: apply the Pigeonhole principle to show that there are more than one items that share a given property.
c) Permutations and Combinations: determine the number of tuples or subsets of a set.
d) Binomial Coefficients and Pascal’s Triangle: find the coefficients for a binomial expansion.

7. Probability
a) Probability Theory (Laplace): define the sample space and the event space and apply the basic rules of probability.
b) Basic Rules of Probability: apply the sum, product, conditional, and independence rules.
c) Distributions: compute the probability of events in a uniform distribution.
d) Random Variables: explain potential events using the concept of a random variable.
e) Expected Value: compute the expected value in a given trial.
f) Variance (time permitting): compute the variance.
g) Bayes’ Theorem (time permitting): apply the Bayes’ formula.