Essential discrete mathematics for computer science

Metadata

• File: Essential discrete mathematics for computer science by Lewis, Zax (2019).pdf
• Zotero: View Item
• Type: Book
• Title: Essential discrete mathematics for computer science,
• Author: Lewis, Harry R.; Zax, Rachel;
• Publisher: Princeton University Press,
• Location: Princeton, New Jersey,
• Year: 2019
• ISBN: 978-0-691-17929-2

Abstract

Discrete mathematics is the basis of much of computer science, from algorithms and automata theory to combinatorics and graph theory. Essential Discrete Mathematics for Computer Science aims to teach mathematical reasoning as well as concepts and skills by stressing the art of proof. It is fully illustrated in color, and each chapter includes a concise summary as well as a set of exercises.—

Tags and Collections

• Keywords: 05 Finished; Computer Science; Discrete Mathematics; ECS020; Textbook

Comments

Practice Problem Answers The pigeonhole principle — Basic proof techniques — Proof by mathematical induction — Strong induction — Sets — Relations and functions — Countable and uncountable sets — Structural induction — Propositional logic — Normal forms — Logic and computers — Quantificational logic — Directed graphs — Digraphs and relations — States and invariants — Undirected graphs — Connectivity — Coloring — Finite automata — Regular languages — Order notation — Counting — Counting subsets — Series — Recurrence relations — Probability — Bayes’ theorem — Random variables and expectation — Modular arithmetic — Public key cryptography

Annotations

Notes

See: discrete mathematics

Ch. 1 - Pigeonhole Principle

• pigeonhole principle
• extended pigeonhole principle

Ch. 2 - Basic Proofs

• constructive proof
• nonconstructive proof
• lemma
• corollary
• basic logic
  • Implication: if p then q, $p⟹q$
  • Inverse: if not p then not q, $\neg p⟹\neg q$
  • Converse: if q then p, $q⟹p$
  • Contrapositive: if not q then not p, $\neg q⟹\neg p$
    • An implication is equivalent to its contrapositive. Its inverse is also equivalent to its converse.
  • Sometimes it may be easier to prove the contrapositive than the implication itself.
• proof by contradiction
• case analysis:
  • see Example 2.9

Ch. 3 - Proof by Mathematical Induction

• proof by induction
• Thue sequence

Ch. 4 - Strong Induction

• strong induction

Ch. 5 - Sets

• set
• power set
• ordered pair
• cross product

Ch. 6 - Relations and Functions

• relation
• function
• injection
• surjection
• bijection

Ch. 7 - Countable and Uncountable Sets

• countable set
• uncountable set

Ch. 8 - Structural Induction

• structural induction

Ch. 9 - Propositional Logic

• propositional logic

Too lazy to do the rest