Download A Beginner's Guide to Discrete Mathematics PDF

TitleA Beginner's Guide to Discrete Mathematics
File Size1.7 MB
Total Pages442
Table of Contents
A Beginner’s Guide to Discrete Mathematics (Second Edition)
	Outline of Topics
	Problems and Exercises
1. Properties of Numbers
	1.1 Numbers
		Sets and Number Systems
		Factors and Divisors
		Exponents and Logarithms
		Absolute Value, Floor, and Ceiling
	1.2 Sums
		Sum Notation
		Some Properties of Sums
	1.3 Bases
		Arithmetic in Various Bases
		Change of Base
	1.4 Scientific Notation
		Floating Point Numbers
		Rounding and Dropping Digits
		Simplified Floating Point Arithmetic
	1.5 Arithmetic in Computers
		Storing Numbers in Computers
		Floating Point Arithmetic on Computers
2. Sets and Data Structures
	2.1 Propositions and Logic
		Propositions and Truth Tables
		Tautologies, Theorems and Logical Equivalence
		The Laws of Logic
	2.2 Elements of Set Theory
		Operations on Sets
		Properties of the Operations
	2.3 Proof Methods in Set Theory
		Method of Truth Tables
		Venn Diagrams
		Syllogisms and Venn Diagrams
	2.4 Some Further Set Operations
		Symmetric Difference
		Cartesian Product
	2.5 Mathematical Induction
		The Principle of Mathematical Induction
		The Well-Ordering Principle
		Some Applications
3. Boolean Algebras and Circuits
	3.1 Boolean Algebra
		Boolean Algebras Defined
		Some Theorems about Boolean Algebras
	3.2 Boolean Forms
		Disjunctive Forms
		Minimal Forms and Prime Implicants
		The Disjunctive Normal Form
	3.3 Finding Minimal Disjunctive Forms
		Karnaugh Maps
		Two-Variable Karnaugh Maps
		Three-Variable and Four-Variable Maps
	3.4 Digital Circuits
		Doing Arithmetic with Circuits
		The Building Blocks
		Half Adders
		Full Adders
		General Circuits
4. Relations and Functions
	4.1 Relations
		First Definitions
		New Relations from Old
		Relations on a Set
	4.2 Some Special Kinds of Relations
		Equivalence Relations
		Order Relations
		Predecessor-Successor Relations
	4.3 Functions
		Definition of a Function
		One-One and onto Functions
		Inverse Functions
5. The Theory of Counting
	5.1 Events
		Experiments and Events
		Set Language
		The Multiplication Principle. Tree Diagrams
	5.2 Unions of Events
		The Rule of Sum
		Using Venn Diagrams
		Inclusion and Exclusion
	5.3 One-to-One Correspondences and Infinite Sets
		One-to-One Correspondence
		Finite and Infinite Sets
		Countable Sets
	5.4 Arrangement Problems
		Sequences on a Set
		Combining Arrangements with the Multiplication Principle
		Arrangements with Repetitions
	5.5 Selections
		An Illustrative Example
		Problems Combining Different Methods
		Symmetry of the Choice Function
		Pascal's Triangle
		Selections from Multisets
	5.6 The Binomial Theorem and Its Applications
		The Binomial Theorem
		Consequences of the Theorem
	5.7 Some Further Counting Results
		Principle of Inclusion and Exclusion
		Counting Powers
		The Pigeonhole Principle
6. Probability
	6.1 Probability Measures
		Probability Distributions
		Nonuniform Experiments
		Nonuniform Probabilities
	6.2 Repeated Experiments
		Stochastic Processes
		Tree Diagrams
		Bernoulli Trials and Binomial Experiments
		The Birthday Coincidence
	6.3 Counting and Probability
		Choosing Marbles
		Card Problems
		Choosing a Committee
		Derangement Problems
	6.4 Conditional Probabilities
		Conditional Probability Defined
		The Conditional Probability Formula
		A Summation Formula
	6.5 Bayes' Formula and Applications
		Bayes' Formula
		Tree Diagrams
		Box Diagrams
		Medical Testing
		The Monty Hall Problem
7. Graph Theory
	7.1 Introduction to Graphs
		Some Special Graphs
	7.2 The Königsberg Bridges; Traversability
		Modeling Road Systems
		The Königsberg Bridges
	7.3 Walks, Paths, and Cycles
	7.4 Distances and Shortest Paths
		Weighted Distance
		Shortest Paths
	7.5 Trees
		Spanning Trees; The Minimal Spanning Tree
	7.6 Hamiltonian Cycles
		Modeling Road Systems Again
		Which Graphs are Hamiltonian?
	7.7 The Traveling Salesman Problem
		Approximation Algorithms
8. Matrices
	8.1 Vectors and Matrices
		Lines; the Scalar Product
		Sums and Products
	8.2 Properties of the Matrix Product
		Identity Elements
	8.3 Systems of Linear Equations
		Matrix Representation of Equations
		Elementary Operations
		The Solution Algorithm
	8.4 More About Linear Systems and Inverses
		Classification of Systems of Equations
		Calculating the Inverse
		Using the Inverse
	8.5 Adjacency Matrices
		Representing a Relation by a Matrix
		Conjunction of Adjacency Matrices
		Adjacency Matrices of Graphs
9. Number Theory and Cryptography
	9.1 Some Elementary Number Theory
		Primes and Divisors
		Greatest Common Divisors and the Euclidean Algorithm
		Reversing the Euclidean Algorithm
	9.2 Modular Arithmetic
		Basic Definitions
		Simultaneous Congruences
	9.3 An Introduction to Cryptography
		Secret Writing
		Physical Secrecy
		The Caesar Cipher
		The Vigenère Method
	9.4 Substitution Ciphers
		Generating Substitution Ciphers
		Substitution Ciphers with a Keyword
		Letter Frequencies
		An Example
	9.5 Modern Cryptography
		The RSA System
		Binary Expressions and Powers
		Public Key Cryptosystems
		Security of RSA
	9.6 Other Cryptographic Ideas
		Signature Systems
		Avoiding the Key Exchange
		Tossing a Coin
	9.7 Attacks on the RSA System
		Using the Chinese Remainder Theorem
		Belonging to an Exponent
		Fermat Factorization
10. The Theory of Voting
	10.1 Simple Elections
		Simple Elections
		Sequential Voting
		The Hare Method
		The Condorcet Method
		Point Methods
	10.2 Multiple Elections
		The Generalized Hare Method
		Approval Voting
		The Single Transferable Vote
	10.3 Fair Elections
		Five Candidates, Five Winners
		Sequential Pairwise Voting
		Manipulating the Vote
	10.4 Properties of Electoral Systems
		The Condorcet Winner Condition
		Independence of Irrelevant Alternatives
		Pareto Condition
		Arrow's Impossibility Theorem
Solutions to Practice Exercises
	Chapter 1
	Chapter 2
	Chapter 3
	Chapter 4
	Chapter 5
	Chapter 6
	Chapter 7
	Chapter 8
	Chapter 9
	Chapter 10
Answers to Selected Exercises
	Section 1.1
	Section 1.2
	Section 1.3
	Section 1.4
	Section 1.5
	Section 2.1
	Section 2.2
	Section 2.3
	Section 2.4
	Section 2.5
	Section 3.1
	Section 3.2
	Section 3.3
	Section 3.4
	Section 4.1
	Section 4.2
	Section 4.3
	Section 5.1
	Section 5.2
	Section 5.3
	Section 5.4
	Section 5.5
	Section 5.6
	Section 5.7
	Section 6.1
	Section 6.2
	Section 6.3
	Section 6.4
	Section 6.5
	Section 7.1
	Section 7.2
	Section 7.3
	Section 7.4
	Section 7.5
	Section 7.7
	Section 8.1
	Section 8.2
	Section 8.3
	Section 8.4
	Section 8.5
	Section 9.1
	Section 9.2
	Section 9.3
	Section 9.4
	Section 9.5
	Section 9.6
	Section 9.7
	Section 10.1
	Section 10.2
	Section 10.3
	Section 10.4

Similer Documents