Schaum's Outline of Discrete Mathematics, Fourth Edition

by Seymour Lipschutz, Marc Lipson

Overview

Study smarter and stay on top of your discrete mathematics course with the bestselling Schaum’s Outline—now with the NEW Schaum’s app and website!

Schaum’s Outline of Discrete Mathematics, Fourth Edition is the go-to study guide for more than 115,000 math majors and first- and second-year university students taking basic computer science courses. With an outline format that facilitates quick and easy review, Schaum’s Outline of Discrete Mathematics, Fourth Edition helps you understand basic concepts and get the extra practice you need to excel in these courses.

Coverage includes set theory; relations; functions and algorithms; logic and propositional calculus; techniques of counting; advanced counting techniques, recursion; probability; graph theory; directed graphs; binary trees; properties of the integers; languages, automata, machines; finite state machines and Turning machines; ordered sets and lattices, and Boolean algebra.

Features

• NEW to this edition: the new Schaum’s app and website!
• NEW to this edition: 20 NEW problem-solving videos online
• 467 solved problems, and hundreds of additional practice problems
• Outline format to provide a concise guide to the standard college course in discrete mathematics
• Clear, concise explanations of discrete mathematics concepts
• Expanded coverage of logic, the rules of inference and basic types of proofs in mathematical reasoning
• Increased emphasis on discrete probability and aspects of probability theory, and greater accessibility to counting techniques.
• Logic chapter emphasizes the IF-THEN and IF-THEN-ELSE sequencing that occurs in computer programming
• Computer arithmetic chapter covers binary and hexagon addition and multiplication
• Cryptology chapter includes substitution and RSA method
• Supports these major texts: Discrete Mathematics and Its Applications (Rosen), and Discrete Mathematics (Epp)
• Appropriate for the following courses: Introductory Discrete Mathematics and Discrete Mathematics

Product Details

ISBN-13:	9781264258802
Publisher:	McGraw Hill LLC
Publication date:	11/25/2021
Edition description:	4th ed.
Pages:	496
Product dimensions:	8.00(w) x 10.70(h) x 0.90(d)

About the Author

Seymour Lipschutz, Ph.D., was on the mathematics faculty of Temple University, and taught at the Polytechnic Institute of Brooklyn. He was also visiting professor in the Computer Science Department of Brooklyn College. His work in the Schaum’s Outline series includes Beginning Linear Algebra, Discrete Mathematics, Third Edition, and Linear Algebra, Sixth Edition.

Marc Lipson, Ph.D., is on the faculty of the University of Virginia. Previously, he taught at the University of Georgia, Northeastern University, and Boston University. He is the coauthor of the Schaum’s Outline of Probability, Third Edition.

Marc Lipson, Ph.D. (Philadelphia, PA), is on the mathematical faculty of the University of Georgia. He is co-author of Schaum's Outline of Discrete Mathematics.

Table of 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

Chapter 4 Logic and Prepositional 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 Counting: Permutations and Combinations 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 Discrete Probability Theory 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 131

7.8 Chebyshev's Inequality, Law of Large Numbers 136

Solved Problems 137

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

Chapter 11 Properties of the Integers 264

11.1 Introduction 264

11.2 Order and Inequalities, Absolute Value 265

11.3 Mathematical Induction 266

11.4 Division Algorithm 267

11.5 Divisibility, Primes 269

11.6 Greatest Common Divisor, Euclidean Algorithm 270

11.7 Fundamental Theorem of Arithmetic 273

11.8 Congruence Relation 274

11.9 Congruence Equations 278

Solved Problems 283

Supplementary Problems 299

Chapter 12 Languages, Automata, Grammars 303

12.1 Introduction 303

12.2 Alphabet, Words, Free Semigroup 303

12.3 Languages 304

12.4 Regular Expressions, Regular Languages 305

12.5 Finite State Automata 306

12.6 Grammars 310

Solved Problems 314

Supplementary Problems 319

Chapter 13 Finite State Machines and Turing Machines 323

13.1 Introduction 323

13.2 Finite State Machines 323

13.3 Gödel Numbers 326

13.4 Turing Machines 326

13.5 Computable Functions 330

Solved Problems 331

Supplementary Problems 334

Chapter 14 Ordered Sets and Lattices 337

14.1 Introduction 337

14.2 Ordered Sets 337

14.3 Hasse Diagrams of Partially Ordered Sets 340

14.4 Consistent Enumeration 342

14.5 Supremum and Infimum 342

14.6 Isomorphic (Similar) Ordered Sets 344

14.7 Well-Ordered Sets 344

14.8 Lattices 346

14.9 Bounded Lattices 348

14.10 Distributive Lattices 349

14.11 Complements, Complemented Lattices 350

Solved Problems 351

Supplementary Problems 360

Chapter 15 Boolean Algebra 368

15.1 Introduction 368

15.2 Basic Definitions 368

15.3 Duality 369

15.4 Basic Theorems 370

15.5 Boolean Algebras as Lattices 370

15.6 Representation Theorem 371

15.7 Sum-of-Products Form for Sets 371

15.8 Sum-of-Products Form for Boolean Algebras 372

15.9 Minimal Boolean Expressions, Prime Implicants 375

15.10 Logic Gates and Circuits 377

15.11 Truth Tables, Boolean Functions 381

15.12 Karnaugh Maps 383

Solved Problems 389

Supplementary Problems 403

Appendix A Vectors and Matrices 409

A.l Introduction 409

A.2 Vectors 409

A.3 Matrices 410

A.4 Matrix Addition and Scalar Multiplication 411

A.5 Matrix Multiplication 412

A.6 Transpose 414

A.7 Square Matrices 414

A.8 Invertible (Nonsingular) Matrices, Inverses 415

A.9 Determinants 416

A.10 Elementary Row Operations, Gaussian Elimination (Optional) 418

A.11 Boolean (Zero-One) Matrices 422

Solved Problems 423

Supplementary Problems 429

Appendix B Algebraic Systems 432

B.1 Introduction 432

B.2 Operations 432

B.3 Semigroups 435

B.4 Groups 438

B.5 Subgroups, Normal Subgroups, and Homomorphisms 440

B.6 Rings, Integral Domains, and Fields 443

B.7 Polynomials Over a Field 446

Solved Problems 450

Supplementary Problems 461

Index 467