Table of Contents
Cover
A Beginner’s Guide to Discrete Mathematics (Second Edition)
Copyright
Preface
Readership
Outline of Topics
Problems and Exercises
Gender
Acknowledgments
Contents
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
Integers
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
Sets
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
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
Derangements
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
Independence
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
Graphs
Some Special Graphs
Degree
7.2 The Königsberg Bridges; Traversability
Modeling Road Systems
The Königsberg Bridges
Eulerization
7.3 Walks, Paths, and Cycles
Connectedness
Connectivity
7.4 Distances and Shortest Paths
Distance
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
Vectors
Lines; the Scalar Product
Matrices
Sums and Products
Transposition
8.2 Properties of the Matrix Product
Identity Elements
Commutativity
Inverses
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
Inverses
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
Amendments
10.4 Properties of Electoral Systems
Polls
The Condorcet Winner Condition
Independence of Irrelevant Alternatives
Monotonicity
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
Index
