Notes on Discrete Mathematics 1st Edition by James Aspnes, Ton Toai ISBN 9782020123112 2020123118
Original price was: $50.00.$35.00Current price is: $35.00.
Notes on Discrete Mathematics 1st Edition by James Aspnes, Ton Toai- Ebook PDF Instant Download/Delivery: 9782020123112, 2020123118
Full download Notes on Discrete Mathematics 1st Edition after payment
Product details:
ISBN 10: 2020123118
ISBN 13: 9782020123112
Author: James Aspnes, Ton Toai
“Notes on Discrete Mathematics” by James Aspnes is a concise and well-organized text designed to introduce the fundamental concepts of discrete mathematics, which are crucial for computer science and related fields. The book is often used as lecture notes or a supplementary text for undergraduate courses.
Key Features:
Core Topics Covered:
Logic and Proof Techniques (including induction and contradiction)
Set Theory and Functions
Relations and Partial Orders
Graph Theory (basic definitions and properties)
Combinatorics and Counting Principles
Number Theory basics relevant to computation
Recurrence Relations and Generating Functions
Approach:
Focuses on clarity and precision in definitions and theorems.
Provides examples and exercises to reinforce understanding.
Emphasizes the mathematical foundations needed for theoretical computer science.
Format:
Originally developed as lecture notes, the book is structured for easy navigation and quick reference.
Suitable for self-study or as a complement to a formal course.
Audience:
Undergraduate students in computer science, mathematics, or related disciplines.
Anyone seeking a solid foundation in discrete mathematics for algorithms, cryptography, or theoretical computing.
Table of contents:
1 Introduction
1.1 So why do I need to learn all this nasty mathematics?
1.2 But isn’t math hard?.
1.3 Thinking about math with your heart
1.4 What you should know about math.
1.4.1 Foundations and logic
1.4.2 Basic mathematics on the real numbers
1.4.3 Fundamental mathematical objects
1.4.4 Modular arithmetic and polynomials
1.4.5 Linear algebra
1.4.6 Graphs
1.4.7 Counting
1.4.8 Probability
1.4.9 Tools
2 Mathematical logic
2.1 The basic picture
2.1.1 Axioms, models, and inference rules
2.1.2 Consistency
2.1.3 What can go wrong
2.1.4 The language of logic
2.1.5 Standard axiom systems and models
2.2 Propositional logic
2.2.1 Operations on propositions
2.2.1.1 Precedence
2.2.2 Truth tables.
2.2.3 Tautologies and logical equivalence
2.2.3.1 Inverses, converses, and contrapositives
2.2.3.2 Equivalences involving true and false
Example
2.2.4 Normal forms
2.3 Predicate logic
2.3.1 Variables and predicates
2.3.2 Quantifiers
2.3.2.1 Universal quantifier
2.3.2.2 Existential quantifier
2.3.2.3 Negation and quantifiers
2.3.2.4 Restricting the scope of a quantifier
2.3.2.5 Nested quantifiers
2.3.2.6 Examples
2.3.3 Functions
2.3.4 Equality
2.3.4.1 Uniqueness
2.3.5 Models
2.3.5.1 Examples
2.4 Proofs
2.4.1 Inference Rules
2.4.2 Proofs, implication, and natural deduction.
2.4.2.1 The Deduction Theorem
2.4.2.2 Natural deduction
2.4.3 Inference rules for equality
2.4.4 Inference rules for quantified statements
2.5 Proof techniques
2.6 Examples of proofs
2.6.1 Axioms for even numbers
2.6.2 A theorem and its proof
2.6.3 A more general theorem
2.6.4 Something we can’t prove
3 Set theory
3.1 Naive set theory
3.2 Operations on sets
3.3 Proving things about sets
3.4 Axiomatic set theory
3.5 Cartesian products, relations, and functions
3.5.1 Examples of functions
3.5.2 Sequences
3.5.3 Functions of more (or less) than one argument
3.5.4 Composition of functions
3.5.5 Functions with special properties
3.5.5.1 Surjections
3.5.5.2 Injections
3.5.5.3 Bijections
3.5.5.4 Bijections and counting
3.6 Constructing the universe
3.7 Sizes and arithmetic
3.7.1 Infinite sets
3.7.2 Countable sets
3.7.3 Uncountable sets
3.8 Further reading
4 The real numbers
4.1 Field axioms
4.1.1 Axioms for addition
4.1.2 Axioms for multiplication
4.1.3 Axioms relating multiplication and addition.
4.1.4 Other algebras satisfying the field axioms
4.2 Order axioms
4.3 Least upper bounds
4.4 What’s missing: algebraic closure
4.5 Arithmetic.
4.6 Connection between the reals and other standard algebras
4.7 Extracting information from reals.
5 Induction and recursion
5.1 Simple induction
5.2 Alternative base cases
5.3 Recursive definitions work
5.4 Other ways to think about induction
5.5 Strong induction
5.5.1 Examples
5.6 Recursively-defined structures
5.6.1 Functions on recursive structures
5.6.2 Recursive definitions and induction
5.6.3 Structural induction
6 Summation notation
6.1 Summations.
6.1.1 Formal definition
6.1.2 Scope
6.1.3 Summation identities.
6.1.4 Choosing and replacing index variables.
6.1.5 Sums over given index sets
6.1.6 Sums without explicit bounds
6.1.7 Infinite sums
6.1.8 Double sums
6.2 Products.
6.3 Other big operators
6.4 Closed forms
6.4.1 Some standard sums
6.4.2 Guess but verify
6.4.3 approach.
7 Asymptotic notation
7.1 Definitions.
7.2 Motivating the definitions
7.3 Proving asymptotic bounds
7.4 General principles for dealing with asymptotic notation
7.4.1 Remember the difference between big-O, big-Ω, and big-
7.4.2 Simplify your asymptotic terms as much as possible
7.4.3 Use limits (may require calculus)
7.5 Asymptotic notation and summations
7.5.1 Pull out constant factors.
7.5.2 Bound using a known sum.
7.5.2.1 Geometric series
7.5.2.2 Constant series
7.5.2.3 Arithmetic series
7.5.2.4 Harmonic series
7.5.3 Bound part of the sum
7.5.4 Integrate
7.5.5 Grouping terms
7.5.6 An odd sum.
7.5.7 Final notes
7.6 Variations in notation
7.6.1 Absolute values
7.6.2 Abusing the equals sign
8 Number theory
8.1 Divisibility
8.2 The division algorithm
8.3 Modular arithmetic and residue classes.
8.3.1 Arithmetic on residue classes
8.4 Greatest common divisors
8.4.1 The Euclidean algorithm for computing ged(m, n)
8.4.2 The extended Euclidean algorithm
8.4.2.1 Example
8.4.2.2 Applications
8.5 The Fundamental Theorem of Arithmetic
8.5.1 Unique factorization and ged
8.6 More modular arithmetic
8.6.1 Division in Zm
8.6.2 The Chinese Remainder Theorem.
8.6.3 The size of Z and Euler’s Theorem
8.7 RSA encryption.
9 Relations
9.1 Representing relations
9.1.1 Directed graphs.
9.1.2 Matrices
9.2 Operations on relations
9.2.1 Composition
9.2.2 Inverses
9.3 Classifying relations
9.4 Equivalence relations.
9.4.1 Why we like equivalence relations.
9.5 Partial orders
9.5.1 Drawing partial orders.
9.5.2 Comparability
9.5.3 Lattices
9.5.4 Minimal and maximal elements
9.5.5 Total orders.
9.5.5.1 Topological sort
9.5.6 Well orders
9.6 Closures
9.6.1 Examples
10 Graphs
10.1 Types of graphs.
10.1.1 Directed graphs.
10.1.2 Undirected graphs
10.1.3 Hypergraphs
10.2 Examples of graphs.
10.3 Local structure of graphs
10.4 Some standard graphs
10.5 Subgraphs and minors
10.6 Graph products
10.7 Functions between graphs
10.8 Paths and connectivity
10.9 Cycles
10.10Proving things about graphs.
10.10.1 Paths and simple paths
10.10.2 The Handshaking Lemma
10.10.3 Characterizations of trees
10.10.4Spanning trees
10.10.5 Eulerian cycles
11 Counting
11.1 Basic counting techniques
11.1.1 Equality: reducing to a previously-solved case.
11.1.2 Inequalities: showing |A| ≤ |
Band |B|
≤ |
A|
11.1.3 Addition: the sum rule.
11.1.3.1 For infinite sets
11.1.3.2 The Pigeonhole Principle
11.1.4 Subtraction
11.1.4.1 Inclusion-exclusion for infinite sets
11.1.4.2 Combinatorial proof
11.1.5 Multiplication: the product rule
11.1.5.1 Examples
11.1.5.2 For infinite sets
11.1.6 Exponentiation: the exponent rule
11.1.6.1 Counting injections
11.1.7 Division: counting the same thing in two different v
11.1.7.1 Binomial coefficients.
11.1.7.2 Multinomial coefficients
11.1.8 Applying the rules
11.1.9 An elaborate counting problem
11.1.10 Further reading
11.2 Binomial coefficients
11.2.1 Recursive definition
11.2.1.1 Pascal’s identity: algebraic proof
11.2.2 Vandermonde’s identity
11.2.2.1 Combinatorial proof.
11.2.2.2 Algebraic proof.
11.2.3 Sums of binomial coefficients
11.2.4 The general inclusion-exclusion formula
11.2.5 Negative binomial coefficients
11.2.6 Fractional binomial coefficients
11.2.7 Further reading
11.3 Generating functions
11.3.1 Basics
11.3.1.1 A simple example
11.3.1.2 Why this works
11.3.1.3 Formal definition.
11.3.2 Some standard generating functions
11.3.3 More operations on formal power series and generatir functions
11.3.4 Counting with generating functions.
11.3.4.1 Disjoint union
11.3.4.2 Cartesian product
11.3.4.3 Repetition
Example: (0/11)*
Example: sequences of positive integers
11.3.4.4 Pointing
11.3.4.5 Substitution
Example: bit-strings with primes
Example: (0/11)* again
11.3.5 Generating functions and recurrences
11.3.5.1 Example: A Fibonacci-like recurrence
11.3.6 Recovering coefficients from generating functions
11.3.6.1 Partial fraction expansion and Heaviside’s cover-up method
Example: A simple recurrence
Example: Coughing cows
Example: A messy recurrence
11.3.6.2 Partial fraction expansion with repeated roots Solving for the PFE directly Solving for the PFE using the extended cover-up
method
11.3.7 Asymptotic estimates
11.3.8 Recovering the sum of all coefficients
11.3.8.1 Example
11.3.9 A recursive generating function
11.3.10Summary of operations on generating functions
11.3.11 Variants
11.3.12 Further reading.
12 Probability theory
12.1 Events and probabilities
12.1.1 Probability axioms
12.1.1.1 The Kolmogorov axioms.
12.1.1.2 Examples of probability spaces
12.1.2 Probability as counting
12.1.2.1 Examples
12.1.3 Independence and the intersection of two events
12.1.3.1 Examples
12.1.4 Union of events
12.1.4.1 Examples
12.1.5 Conditional probability
12.1.5.1 Conditional probabilities and intersections of non-independent events
12.1.5.2 The law of total probability
12.1.5.3 Bayes’s formula
12.2 Random variables.
12.2.1 Examples of random variables.
12.2.2 The distribution of a random variable
12.2.2.1 Some standard distributions
12.2.2.2 Joint distributions
Examples
12.2.3 Independence of random variables
12.2.3.1 Examples
12.2.3.2 Independence of many random variables
12.2.4 The expectation of a random variable
12.2.4.1 Variables without expectations
12.2.4.2 Expectation of a sum
Example
12.2.4.3 Expectation of a product
12.2.4.4 Conditional expectation
Examples
12.2.4.5 Conditioning on a random variable.
12.2.5 Markov’s inequality
12.2.5.1 Example
12.2.5.2 Conditional Markov’s inequality
12.2.6 The variance of a random variable
12.2.6.1 Multiplication by constants
12.2.6.2 The variance of a sum
12.2.6.3 Chebyshev’s inequality
Application: showing that a random variable is close to its expectation
Application: lower bounds on random variables
12.2.7 Probability generating functions
12.2.7.1 Sums
12.2.7.2 Expectation and variance
12.2.8 Summary: effects of operations on expectation and variance of random variables
12.2.9 The general case
12.2.9.1 Densities
12.2.9.2 Independence
12.2.9.3 Expectation
13 Linear algebra
13.1 Vectors and vector spaces
13.1.1 Relative positions and vector addition
13.1.2 Scaling
13.2 Abstract vector spaces
13.3 Matrices
13.3.1 Interpretation
13.3.2 Operations on matrices
13.3.2.1 Transpose of a matrix
13.3.2.2 Sum of two matrices
13.3.2.3 Product of two matrices
13.3.2.4 The inverse of a matrix
Example
13.3.2.5 Scalar multiplication.
13.3.3 Matrix identities
13.4 Vectors as matrices
13.4.1 Length..
13.4.2 Dot products and orthogonality.
13.5 Linear combinations and subspaces
13.5.1 Bases
13.6 Linear transformations
13.6.1 Composition
13.6.2 Role of rows and columns of M in the product Ma
13.6.3 Geometric interpretation
.13.6.4 Rank and inverses
13.6.5 Projections
13.7 Further reading
14 Finite fields
14.1 A magic trick
14.2 Fields and rings
14.3 Polynomials over a field
14.4 Algebraic field extensions
14.5 Applications.
14.5.1 Linear-feedback shift registers
14.5.2 Checksums
14.5.3 Cryptography.
People also search for:
last minute notes on discrete mathematics
miguel a lerma notes on discrete mathematics
notes on discrete mathematics and number theory
notes on discrete mathematics james aspnes
notes on number theory and discrete mathematics abbreviation