Title | A Beginner's Guide to Discrete Mathematics |
---|---|

File Size | 1.7 MB |

Total Pages | 442 |

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 Scientiﬁc Notation Floating Point Numbers Rounding and Dropping Digits Simpliﬁed 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 Deﬁned 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 Deﬁnitions 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 Deﬁnition 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 Inﬁnite Sets One-to-One Correspondence Finite and Inﬁnite 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 Deﬁned 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 Classiﬁcation 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 Deﬁnitions 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

More Documents

**~: Disclaimer :~**

DOK.PUB is a document sharing platform where anyone can register and upload documents. If any content listed here are owned by you and want to remove it please send us removal request at *[email protected]*

© DOK.PUB 2022 All rights reserved

Made with by WebSpice