Notes on Discrete Mathematics - Computer Science

1 Notes on Discrete MathematicsJames Aspnes2018-06-26 19:31iCopyrightc 2004 2017 by James Aspnes. Distributed under a Creative Com-mons Attribution-ShareAlike International license: of contentsiiList of figuresxviiList of tablesxixList of algorithmsxxPrefacexxiSyllabusxxiiResour cesxxviInternet resourcesxxviiLecture schedulexxviii1 So why do I need to learn all this nasty Mathematics ? .. But isn t math hard? .. Thinking about math with your heart .. What you should know about math .. Foundations and logic .. Basic Mathematics on the real numbers .. Fundamental mathematical objects .. Modular arithmetic and polynomials.

2 Linear algebra .. Graphs .. Counting .. Probability .. Tools .. 82 Mathematical The basic picture .. Axioms, models, and inference rules .. Consistency .. What can go wrong .. The language of logic .. Standard axiom systems and models .. Propositional logic .. Operations on propositions .. Precedence .. Truth tables .. Tautologies and logical equivalence .. Inverses, converses, and contrapositives .. Equivalences involving true and false .. 21 Example .. Normal forms .. Predicate logic .. Variables and predicates .. Quantifiers.

3 Universal quantifier .. Existential quantifier .. Negation and quantifiers .. Restricting the scope of a quantifier .. Nested quantifiers .. Examples .. Functions .. Equality .. Uniqueness .. Models .. Examples .. Proofs .. Inference Rules .. Proofs, implication, and natural deduction .. The Deduction Theorem .. Natural deduction .. Inference rules for equality .. Inference rules for quantified statements .. Proof techniques .. Examples of proofs .. Axioms for even numbers .. A theorem and its proof .. A more general theorem.

4 Something we can t prove .. 513 Set Naive set theory .. Operations on sets .. Proving things about sets .. Axiomatic set theory .. Cartesian products, relations, and functions .. Examples of functions .. Sequences .. Functions of more (or less) than one argument .. Composition of functions .. Functions with special properties .. Surjections .. Injections .. Bijections .. Bijections and counting .. Constructing the universe .. Sizes and arithmetic .. Infinite sets .. Countable sets .. Uncountable sets .. Further reading .. 694 The real Field axioms.

5 Axioms for addition .. Axioms for multiplication .. Axioms relating multiplication and addition .. Other algebras satisfying the field axioms .. Order axioms .. Least upper bounds .. What s missing: algebraic closure .. Arithmetic .. Connection between the reals and other standard algebras .. Extracting information from reals .. 82 CONTENTSv5 Induction and Simple induction .. Alternative base cases .. Recursive definitions work .. Other ways to think about induction .. Strong induction .. Examples .. Recursively-defined structures .. Functions on recursive structures.

6 Recursive definitions and induction .. Structural induction .. 916 Summation Summations .. Formal definition .. Scope .. Summation identities .. Choosing and replacing index variables .. Sums over given index sets .. Sums without explicit bounds .. Infinite sums .. Double sums .. Products .. Other big operators .. Closed forms .. Some standard sums .. Guess but verify .. Ansatzes .. 1037 Asymptotic Definitions .. Motivating the definitions .. Proving asymptotic bounds .. General principles for dealing with asymptotic notation .. the difference between big-O, big- , andbig.

7 Simplify your asymptotic terms as much as possible . Use limits (may require calculus) .. Asymptotic notation and summations .. Pull out constant factors .. Bound using a known sum .. Geometric series .. Constant series .. Arithmetic series .. Harmonic series .. Bound part of the sum .. Integrate .. Grouping terms .. An odd sum .. Final Notes .. Variations in notation .. Absolute values .. Abusing the equals sign .. 1128 Number Divisibility .. The division algorithm .. Modular arithmetic and residue classes .. Arithmetic on residue classes .. Greatest common divisors.

8 The Euclidean algorithm for computinggcd(m,n).. The extended Euclidean algorithm .. Example .. Applications .. The Fundamental Theorem of Arithmetic .. Unique factorization and gcd .. More modular arithmetic .. Division inZm.. The Chinese Remainder Theorem .. The size ofZ mand Euler s Theorem .. RSA encryption .. 1299 Representing relations .. Directed graphs .. Matrices .. Operations on relations .. Composition .. Inverses .. Classifying relations .. Equivalence relations .. Why we like equivalence relations .. Partial orders .. Drawing partial orders .. Comparability.

9 Lattices .. Minimal and maximal elements .. Total orders .. Topological sort .. Well orders .. Closures .. Examples .. 15010 Types of graphs .. Directed graphs .. Undirected graphs .. Hypergraphs .. Examples of graphs .. Local structure of graphs .. Some standard graphs .. Subgraphs and minors .. Graph products .. Functions between graphs .. Paths and connectivity .. Cycles .. things about graphs .. and simple paths .. Handshaking Lemma .. of trees .. trees .. cycles .. 17211 Basic counting techniques .. Equality: reducing to a previously-solved case .. Inequalities: showing|A| |B|and|B| |A|.

10 Addition: the sum rule .. For infinite sets .. The Pigeonhole Principle .. Subtraction .. Inclusion-exclusion for infinite sets .. Combinatorial proof .. Multiplication: the product rule .. Examples .. For infinite sets .. Exponentiation: the exponent rule .. Counting injections .. Division: counting the same thing in two different Binomial coefficients .. Multinomial coefficients .. Applying the rules .. An elaborate counting problem .. reading .. Binomial coefficients .. Recursive definition .. Pascal s identity: algebraic proof .. Vandermonde s identity .. Combinatorial proof.