SCHAUM'S ouTlines DISCRETE MATHEMATICS Third Edition SEYMOUR LIPSCHUTZ MARC LIPSON Hundreds of fully solved problems New chapters on computer arithmatic and cryptology Covers all course fundamentals- supplements any course text TRUSTED BY MORE THAN 40 MILLION STUDENTS Use WiththeseouDisrete Mathematies Discrete Mathematics
PREFACE Discrete mathematics,the study of finite systems,has become increasingly important as the computer age has advanced.The digital computer is basically a finite structure,and many of its properties can be understood and interpreted within the framework of finite mathematical systems.This book,in presenting the more essential material,may be used as a textbook for a formal course in discrete mathematics or as a supplement to all current texts. The first three chapters cover the standard material on sets,relations,and functions and algorithms.Next come chapters on logic,counting,and probability.We then have three chapters on graph theory:graphs,directed graphs,and binary trees.Finally there are individual chapters on properties of the integers,languages,machines, ordered sets and lattices,and Boolean algebra,and appendices on vectors and matrices,and algebraic systems. The chapter on functions and algorithms includes a discussion of cardinality and countable sets,and complexity. The chapters on graph theory include discussions on planarity,traversability,minimal paths,and Warshall's and Huffman's algorithms.We emphasize that the chapters have been written so that the order can be changed without difficulty and without loss of continuity. Each chapter begins with a clear statement of pertinent definitions,principles,and theorems with illustrative and other descriptive material.This is followed by sets of solved and supplementary problems.The solved problems serve to illustrate and amplify the material,and also include proofs of theorems.The supplementary problems furnish a complete review of the material in the chapter.More material has been included than can be covered in most first courses.This has been done to make the book more flexible,to provide a more useful book of reference,and to stimulate further interest in the topics. SEYMOUR LIPSCHUTZ MARC LARS LIPSON Copyright2007,1997,1976 by The McGraw-Hill Companies,Inc.Click here for terms of use
PREFACE Discrete mathematics, the study of finite systems, has become increasingly important as the computer age has advanced. The digital computer is basically a finite structure, and many of its properties can be understood and interpreted within the framework of finite mathematical systems. This book, in presenting the more essential material, may be used as a textbook for a formal course in discrete mathematics or as a supplement to all current texts. The first three chapters cover the standard material on sets, relations, and functions and algorithms. Next come chapters on logic, counting, and probability. We then have three chapters on graph theory: graphs, directed graphs, and binary trees. Finally there are individual chapters on properties of the integers, languages, machines, ordered sets and lattices, and Boolean algebra, and appendices on vectors and matrices, and algebraic systems. The chapter on functions and algorithms includes a discussion of cardinality and countable sets, and complexity. The chapters on graph theory include discussions on planarity, traversability, minimal paths, and Warshall’s and Huffman’s algorithms. We emphasize that the chapters have been written so that the order can be changed without difficulty and without loss of continuity. Each chapter begins with a clear statement of pertinent definitions, principles, and theorems with illustrative and other descriptive material. This is followed by sets of solved and supplementary problems. The solved problems serve to illustrate and amplify the material, and also include proofs of theorems. The supplementary problems furnish a complete review of the material in the chapter. More material has been included than can be covered in most first courses. This has been done to make the book more flexible, to provide a more useful book of reference, and to stimulate further interest in the topics. Seymour Lipschutz Marc Lars Lipson v Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use
For more information about this title,click here CONTENTS CHAPTER 1 Set Theory y 1.1 Introduction 1.2 Sets and Elements,Subsets 1.3 Venn Diagrams 1.4 Set Operations 1.5 Algebra of Sets,Duality > 1.6 Finite Sets,Counting Principle P 1.7 Classes of Sets,Power Sets,Partitions 10 1.8 Mathematical Induction 12 Solved Problems 12 Supplementary Problems 18 CHAPTER 2 Relations 23 2.1 Introduction 2.2 Product Sets 2.3 Relations 2.4 Pictorial Representatives of Relations 2.5 Composition of Relations 2.6 Types of Relations 2.7 Closure Properties 2.8 Equivalence Relations 2.9 Partial Ordering Relations 334357283013460 Solved Problems Supplementary Problems CHAPTER 3 Functions and Algorithms 43 3.1 Introduction 43 3.2 Functions 43 3.3 One-to-One,Onto,and Invertible Functions 3.4 Mathematical Functions,Exponential and Logarithmic Functions 3.5 Sequences,Indexed Classes of Sets 3.6 Recursively Defined Functions 3.7 Cardinality 3.8 Algorithms and Functions 3.9 Complexity of Algorithms Solved Problems 1702567606 Supplementary Problems vii
CONTENTS CHAPTER 1 Set Theory 1 1.1 Introduction 1 1.2 Sets and Elements, Subsets 1 1.3 Venn Diagrams 3 1.4 Set Operations 4 1.5 Algebra of Sets, Duality 7 1.6 Finite Sets, Counting Principle 8 1.7 Classes of Sets, Power Sets, Partitions 10 1.8 Mathematical Induction 12 Solved Problems 12 Supplementary Problems 18 CHAPTER 2 Relations 23 2.1 Introduction 23 2.2 Product Sets 23 2.3 Relations 24 2.4 Pictorial Representatives of Relations 25 2.5 Composition of Relations 27 2.6 Types of Relations 28 2.7 Closure Properties 30 2.8 Equivalence Relations 31 2.9 Partial Ordering Relations 33 Solved Problems 34 Supplementary Problems 40 CHAPTER 3 Functions and Algorithms 43 3.1 Introduction 43 3.2 Functions 43 3.3 One-to-One, Onto, and Invertible Functions 46 3.4 Mathematical Functions, Exponential and Logarithmic Functions 47 3.5 Sequences, Indexed Classes of Sets 50 3.6 Recursively Defined Functions 52 3.7 Cardinality 55 3.8 Algorithms and Functions 56 3.9 Complexity of Algorithms 57 Solved Problems 60 Supplementary Problems 66 vii For more information about this title, click here
viii CONTENTS CHAPTER 4 Logic and Propositional Calculus 70 4.1 Introduction 70 4.2 Propositions and Compound Statements 4.3 Basic Logical Operations 4.4 Propositions and Truth Tables 4.5 Tautologies and Contradictions 4.6 Logical Equivalence 4.7 Algebra of Propositions 4.8 Conditional and Biconditional Statements 4.9 Arguments 4.10 Propositional Functions,Quantifiers 4.11 Negation of Quantified Statements 012445567936 Solved Problems Supplementary Problems CHAPTER 5 Techniques of Counting 88 5.1 Introduction 5.2 Basic Counting Principles 5.3 Mathematical Functions 5.4 Permutations 5.5 Combinations 5.6 The Pigeonhole Principle 5.7 The Inclusion-Exclusion Principle 5.8 Tree Diagrams 88999459 Solved Problems Supplementary Problems 103 CHAPTER 6 Advanced Counting Techniques,Recursion 107 6.1 Introduction 107 6.2 Combinations with Repetitions 107 6.3 Ordered and Unordered Partitions 108 6.4 Inclusion-Exclusion Principle Revisited 108 6.5 Pigeonhole Principle Revisited 110 6.6 Recurrence Relations 111 6.7 Linear Recurrence Relations with Constant Coefficients 113 6.8 Solving Second-Order Homogeneous Linear Recurrence Relations 114 6.9 Solving General Homogeneous Linear Recurrence Relations 116 Solved Problems 118 Supplementary Problems 121 CHAPTER 7 Probability 123 7.1 Introduction 123 7.2 Sample Space and Events 123 7.3 Finite Probability Spaces 126 7.4 Conditional Probability 127 7.5 Independent Events 129 7.6 Independent Repeated Trials,Binomial Distribution 130 7.7 Random Variables 132
viii CONTENTS CHAPTER 4 Logic and Propositional Calculus 70 4.1 Introduction 70 4.2 Propositions and Compound Statements 70 4.3 Basic Logical Operations 71 4.4 Propositions and Truth Tables 72 4.5 Tautologies and Contradictions 74 4.6 Logical Equivalence 74 4.7 Algebra of Propositions 75 4.8 Conditional and Biconditional Statements 75 4.9 Arguments 76 4.10 Propositional Functions, Quantifiers 77 4.11 Negation of Quantified Statements 79 Solved Problems 82 Supplementary Problems 86 CHAPTER 5 Techniques of Counting 88 5.1 Introduction 88 5.2 Basic Counting Principles 88 5.3 Mathematical Functions 89 5.4 Permutations 91 5.5 Combinations 93 5.6 The Pigeonhole Principle 94 5.7 The Inclusion–Exclusion Principle 95 5.8 Tree Diagrams 95 Solved Problems 96 Supplementary Problems 103 CHAPTER 6 Advanced Counting Techniques, Recursion 107 6.1 Introduction 107 6.2 Combinations with Repetitions 107 6.3 Ordered and Unordered Partitions 108 6.4 Inclusion–Exclusion Principle Revisited 108 6.5 Pigeonhole Principle Revisited 110 6.6 Recurrence Relations 111 6.7 Linear Recurrence Relations with Constant Coefficients 113 6.8 Solving Second-Order Homogeneous Linear Recurrence Relations 114 6.9 Solving General Homogeneous Linear Recurrence Relations 116 Solved Problems 118 Supplementary Problems 121 CHAPTER 7 Probability 123 7.1 Introduction 123 7.2 Sample Space and Events 123 7.3 Finite Probability Spaces 126 7.4 Conditional Probability 127 7.5 Independent Events 129 7.6 Independent Repeated Trials, Binomial Distribution 130 7.7 Random Variables 132
CONTENTS ix 7.8 Chebyshev's Inequality,Law of Large Numbers 135 Solved Problems 136 Supplementary Problems 149 CHAPTER 8 Graph Theory 154 8.1 Introduction,Data Structures 154 8.2 Graphs and Multigraphs 156 8.3 Subgraphs,Isomorphic and Homeomorphic Graphs 158 8.4 Paths,Connectivity 159 8.5 Traversable and Eulerian Graphs,Bridges of Konigsberg 160 8.6 Labeled and Weighted Graphs 162 8.7 Complete,Regular,and Bipartite Graphs 162 8.8 Tree Graphs 164 8.9 Planar Graphs 166 8.10 Graph Colorings 168 8.11 Representing Graphs in Computer Memory 171 8.12 Graph Algorithms 173 8.13 Traveling-Salesman Problem 176 Solved Problems 178 Supplementary Problems 191 CHAPTER 9 Directed Graphs 201 9.1 Introduction 201 9.2 Directed Graphs 201 9.3 Basic Definitions 202 9.4 Rooted Trees 204 9.5 Sequential Representation of Directed Graphs 206 9.6 Warshall's Algorithm,Shortest Paths 209 9.7 Linked Representation of Directed Graphs 211 9.8 Graph Algorithms:Depth-First and Breadth-First Searches 213 9.9 Directed Cycle-Free Graphs,Topological Sort 216 9.10 Pruning Algorithm for Shortest Path 218 Solved Problems 221 Supplementary Problems 228 CHAPTER 10 Binary Trees 235 10.1 Introduction 235 10.2 Binary Trees 235 10.3 Complete and Extended Binary Trees 237 10.4 Representing Binary Trees in Memory 239 10.5 Traversing Binary Trees 240 10.6 Binary Search Trees 242 10.7 Priority Queues,Heaps 244 10.8 Path Lengths,Huffman's Algorithm 248 10.9 General(Ordered Rooted)Trees Revisited 251 Solved Problems 252 Supplementary Problems 259
CONTENTS ix 7.8 Chebyshev’s Inequality, Law of Large Numbers 135 Solved Problems 136 Supplementary Problems 149 CHAPTER 8 Graph Theory 154 8.1 Introduction, Data Structures 154 8.2 Graphs and Multigraphs 156 8.3 Subgraphs, Isomorphic and Homeomorphic Graphs 158 8.4 Paths, Connectivity 159 8.5 Traversable and Eulerian Graphs, Bridges of Königsberg 160 8.6 Labeled and Weighted Graphs 162 8.7 Complete, Regular, and Bipartite Graphs 162 8.8 Tree Graphs 164 8.9 Planar Graphs 166 8.10 Graph Colorings 168 8.11 Representing Graphs in Computer Memory 171 8.12 Graph Algorithms 173 8.13 Traveling-Salesman Problem 176 Solved Problems 178 Supplementary Problems 191 CHAPTER 9 Directed Graphs 201 9.1 Introduction 201 9.2 Directed Graphs 201 9.3 Basic Definitions 202 9.4 Rooted Trees 204 9.5 Sequential Representation of Directed Graphs 206 9.6 Warshall’s Algorithm, Shortest Paths 209 9.7 Linked Representation of Directed Graphs 211 9.8 Graph Algorithms: Depth-First and Breadth-First Searches 213 9.9 Directed Cycle-Free Graphs, Topological Sort 216 9.10 Pruning Algorithm for Shortest Path 218 Solved Problems 221 Supplementary Problems 228 CHAPTER 10 Binary Trees 235 10.1 Introduction 235 10.2 Binary Trees 235 10.3 Complete and Extended Binary Trees 237 10.4 Representing Binary Trees in Memory 239 10.5 Traversing Binary Trees 240 10.6 Binary Search Trees 242 10.7 Priority Queues, Heaps 244 10.8 Path Lengths, Huffman’s Algorithm 248 10.9 General (Ordered Rooted) Trees Revisited 251 Solved Problems 252 Supplementary Problems 259