Seymour Lipschutz, Marc Lipson Schaum's Outline of Discrete Mathematics McGraw Hill Osborne Media (2007) PDF

Preview

Summary

SCHAUM’S OUTLINE OF Theory and Problems of DISCRETE MATHEMATICS This page intentionally left blank SCHAUM’S OUTLINE OF Theory and Problems of DISCRETE MATHEMATICS Third Edition SEYMOUR LIPSCHUTZ, Ph.D. Temple University MARC LARS LIPSON, Ph.D. University of Virginia Schaum’s Outline Series McGRAW-H...

Description

SCHAUM’S OUTLINE OF

Theory and Problems of

DISCRETE MATHEMATICS

This page intentionally left blank

SCHAUM’S OUTLINE OF

Theory and Problems of

DISCRETE MATHEMATICS Third Edition SEYMOUR LIPSCHUTZ, Ph.D. Temple University

MARC LARS LIPSON, Ph.D. University of Virginia

Schaum’s Outline Series New York

Chicago

McGRAW-HILL San Francisco Lisbon London Madrid Mexico City Milan New Delhi San Juan Seoul Singapore Sydney Toronto

Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. All rights reserved. Manufactured in the United States of America. Except as permitted under the United States Copyright Act of 1976, no part of this publication may be reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the publisher. 0-07-151101-6 The material in this eBook also appears in the print version of this title: 0-07-147038-7. All trademarks are trademarks of their respective owners. Rather than put a trademark symbol after every occurrence of a trademarked name, we use names in an editorial fashion only, and to the benefit of the trademark owner, with no intention of infringement of the trademark. Where such designations appear in this book, they have been printed with initial caps. McGraw-Hill eBooks are available at special quantity discounts to use as premiums and sales promotions, or for use in corporate training programs. For more information, please contact George Hoare, Special Sales, at [email protected] or (212) 904-4069. TERMS OF USE This is a copyrighted work and The McGraw-Hill Companies, Inc. (“McGraw-Hill”) and its licensors reserve all rights in and to the work. Use of this work is subject to these terms. Except as permitted under the Copyright Act of 1976 and the right to store and retrieve one copy of the work, you may not decompile, disassemble, reverse engineer, reproduce, modify, create derivative works based upon, transmit, distribute, disseminate, sell, publish or sublicense the work or any part of it without McGraw-Hill’s prior consent. You may use the work for your own noncommercial and personal use; any other use of the work is strictly prohibited. Your right to use the work may be terminated if you fail to comply with these terms. THE WORK IS PROVIDED “AS IS.” McGRAW-HILL AND ITS LICENSORS MAKE NO GUARANTEES OR WARRANTIES AS TO THE ACCURACY, ADEQUACY OR COMPLETENESS OF OR RESULTS TO BE OBTAINED FROM USING THE WORK, INCLUDING ANY INFORMATION THAT CAN BE ACCESSED THROUGH THE WORK VIA HYPERLINK OR OTHERWISE, AND EXPRESSLY DISCLAIM ANY WARRANTY, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. McGraw-Hill and its licensors do not warrant or guarantee that the functions contained in the work will meet your requirements or that its operation will be uninterrupted or error free. Neither McGraw-Hill nor its licensors shall be liable to you or anyone else for any inaccuracy, error or omission, regardless of cause, in the work or for any damages resulting therefrom. McGraw-Hill has no responsibility for the content of any information accessed through the work. Under no circumstances shall McGraw-Hill and/or its licensors be liable for any indirect, incidental, special, punitive, consequential or similar damages that result from the use of or inability to use the work, even if any of them has been advised of the possibility of such damages. This limitation of liability shall apply to any claim or cause whatsoever whether such claim or cause arises in contract, tort or otherwise. DOI: 10.1036/0071470387

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.

This page intentionally left blank

For more information about this title, click here

CONTENTS

CHAPTER 1

CHAPTER 2

Set Theory

1

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 1.7 Classes of Sets, Power Sets, Partitions 1.8 Mathematical Induction Solved Problems Supplementary Problems

1 1 3 4 7 8 10 12 12 18

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 Solved Problems Supplementary Problems

CHAPTER 3

Functions and Algorithms 3.1 Introduction 3.2 Functions 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 Supplementary Problems vii

23 23 24 25 27 28 30 31 33 34 40

43 43 43 46 47 50 52 55 56 57 60 66

viii

CHAPTER 4

CONTENTS

Logic and Propositional Calculus 4.1 Introduction 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 Solved Problems Supplementary Problems

CHAPTER 5

CHAPTER 6

70 70 71 72 74 74 75 75 76 77 79 82 86

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 Solved Problems Supplementary Problems

88 88 89 91 93 94 95 95 96 103

Advanced Counting Techniques, Recursion 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8

Introduction Combinations with Repetitions Ordered and Unordered Partitions Inclusion–Exclusion Principle Revisited Pigeonhole Principle Revisited Recurrence Relations Linear Recurrence Relations with Constant Coefficients Solving Second-Order Homogeneous Linear Recurrence Relations 6.9 Solving General Homogeneous Linear Recurrence Relations Solved Problems Supplementary Problems

CHAPTER 7

70

Probability 7.1 7.2 7.3 7.4 7.5 7.6 7.7

Introduction Sample Space and Events Finite Probability Spaces Conditional Probability Independent Events Independent Repeated Trials, Binomial Distribution Random Variables

107 107 107 108 108 110 111 113 114 116 118 121

123 123 123 126 127 129 130 132

CONTENTS

7.8 Chebyshev’s Inequality, Law of Large Numbers Solved Problems Supplementary Problems

CHAPTER 8

Graph Theory 8.1 Introduction, Data Structures 8.2 Graphs and Multigraphs 8.3 Subgraphs, Isomorphic and Homeomorphic Graphs 8.4 Paths, Connectivity 8.5 Traversable and Eulerian Graphs, Bridges of Königsberg 8.6 Labeled and Weighted Graphs 8.7 Complete, Regular, and Bipartite Graphs 8.8 Tree Graphs 8.9 Planar Graphs 8.10 Graph Colorings 8.11 Representing Graphs in Computer Memory 8.12 Graph Algorithms 8.13 Traveling-Salesman Problem Solved Problems Supplementary Problems

CHAPTER 9

Directed Graphs 9.1 Introduction 9.2 Directed Graphs 9.3 Basic Definitions 9.4 Rooted Trees 9.5 Sequential Representation of Directed Graphs 9.6 Warshall’s Algorithm, Shortest Paths 9.7 Linked Representation of Directed Graphs 9.8 Graph Algorithms: Depth-First and Breadth-First Searches 9.9 Directed Cycle-Free Graphs, Topological Sort 9.10 Pruning Algorithm for Shortest Path Solved Problems Supplementary Problems

CHAPTER 10

Binary Trees 10.1 Introduction 10.2 Binary Trees 10.3 Complete and Extended Binary Trees 10.4 Representing Binary Trees in Memory 10.5 Traversing Binary Trees 10.6 Binary Search Trees 10.7 Priority Queues, Heaps 10.8 Path Lengths, Huffman’s Algorithm 10.9 General (Ordered Rooted) Trees Revisited Solved Problems Supplementary Problems

ix

135 136 149

154 154 156 158 159 160 162 162 164 166 168 171 173 176 178 191

201 201 201 202 204 206 209 211 213 216 218 221 228

235 235 235 237 239 240 242 244 248 251 252 259

x

CHAPTER 11

CONTENTS

Properties of the Integers 11.1 Introduction 11.2 Order and Inequalities, Absolute Value 11.3 Mathematical Induction 11.4 Division Algorithm 11.5 Divisibility, Primes 11.6 Greatest Common Divisor, Euclidean Algorithm 11.7 Fundamental Theorem of Arithmetic 11.8 Congruence Relation 11.9 Congruence Equations Solved Problems Supplementary Problems

CHAPTER 12

Languages, Automata, Grammars 12.1 Introduction 12.2 Alphabet, Words, Free Semigroup 12.3 Languages 12.4 Regular Expressions, Regular Languages 12.5 Finite State Automata 12.6 Grammars Solved Problems Supplementary Problems

CHAPTER 13

Finite State Machines and Turing Machines 13.1 Introduction 13.2 Finite State Machines 13.3 Gödel Numbers 13.4 Turing Machines 13.5 Computable Functions Solved Problems Supplementary Problems

CHAPTER 14

Ordered Sets and Lattices 14.1 Introduction 14.2 Ordered Sets 14.3 Hasse Diagrams of Partially Ordered Sets 14.4 Consistent Enumeration 14.5 Supremum and Infimum 14.6 Isomorphic (Similar) Ordered Sets 14.7 Well-Ordered Sets 14.8 Lattices 14.9 Bounded Lattices 14.10 Distributive Lattices 14.11 Complements, Complemented Lattices Solved Problems Supplementary Problems

264 264 265 266 267 269 270 273 274 278 283 299

303 303 303 304 305 306 310 314 319

323 323 323 326 326 330 331 334

337 337 337 340 342 342 344 344 346 348 349 350 351 360

CONTENTS

CHAPTER 15

Boolean Algebra 15.1 Introduction 15.2 Basic Definitions 15.3 Duality 15.4 Basic Theorems 15.5 Boolean Algebras as Lattices 15.6 Representation Theorem 15.7 Sum-of-Products Form for Sets 15.8 Sum-of-Products Form for Boolean Algebras 15.9 Minimal Boolean Expressions, Prime Implicants 15.10 Logic Gates and Circuits 15.11 Truth Tables, Boolean Functions 15.12 Karnaugh Maps Solved Problems Supplementary Problems

APPENDIX A

Vectors and Matrices A.1 Introduction A.2 Vectors A.3 Matrices A.4 Matrix Addition and Scalar Multiplication A.5 Matrix Multiplication A.6 Transpose A.7 Square Matrices A.8 Invertible (Nonsingular) Matrices, Inverses A.9 Determinants A.10 Elementary Row Operations, Gaussian Elimination (Optional) A.11 Boolean (Zero-One) Matrices Solved Problems Supplementary Problems

APPENDIX B

Algebraic Systems B.1 Introduction B.2 Operations B.3 Semigroups B.4 Groups B.5 Subgroups, Normal Subgroups, and Homomorphisms B.6 Rings, Internal Domains, and Fields B.7 Polynomials Over a Field Solved Problems Supplementary Problems

Index

xi

368 368 368 369 370 370 371 371 372 375 377 381 383 389 403

409 409 409 410 411 412 414 414 415 416 418 422 423 429

432 432 432 435 438 440 443 446 450 461

467

This page intentionally left blank

SCHAUM’S OUTLINE OF

Theory and Problems of

DISCRETE MATHEMATICS

This page intentionally left blank

CHAPTER 1

Set Theory 1.1

INTRODUCTION

The concept of a set appears in all mathematics. This chapter introduces the notation and terminology of set theory which is basic and used throughout the text. The chapter closes with the formal definition of mathematical induction, with examples. 1.2

SETS AND ELEMENTS, SUBSETS

A set may be viewed as any well-defined collection of objects, called the elements or members of the set. One usually uses capital letters, A, B, X, Y, . . . , to denote sets, and lowercase letters, a, b, x, y, . . ., to denote elements of sets. Synonyms for “set” are “class,” “collection,” and “family.” Membership in a set is denoted as follows: a ∈ S denotes that a belongs to a set S a, b ∈ S denotes that a and b belong to a set S Here ∈ is the symbol meaning “is an element of.” We use  ∈ to mean “is not an element of.” Specifying Sets There are essentially two ways to specify a particular set. One way, if possible, is to list its members separated by commas and contained in braces { }. A second way is to state those properties which characterized the elements in the set. Examples illustrating these two ways are: A = {1, 3, 5, 7, 9} and B = {x | x is an even integer, x > 0} That is, A consists of the numbers 1, 3, 5, 7, 9. The second set, which reads: B is the set of x such that x is an even integer and x is greater than 0, denotes the set B whose elements are the positive integers. Note that a letter, usually x, is used to denote a typical member of the set; and the vertical line | is read as “such that” and the comma as “and.”

EXAMPLE 1.1 (a) The set A above can also be written as A = {x | x is an odd positive integer, x < 10}. (b) We cannot list all the elements of the above set B although frequently we specify the set by B = {2, 4, 6, . . .} where we assume that everyone knows what we mean. Observe that 8 ∈ B, but 3 ∈ / B. 1 Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.

2

SET THEORY

(c) Let E = {x | x 2 − 3x + 2 = 0},

[CHAP. 1

F = {2, 1} and G = {1, 2, 2, 1}. Then E = F = G.

We emphasize that a set does not depend on the way in which its elements are displayed. A set remains the same if its elements are repeated or rearranged. Even if we can list the elements of a set, it may not be practical to do so. That is, we describe a set by listing its elements only if the set contains a few elements; otherwise we describe a set by the property which characterizes its elements. Subsets Suppose every element in a set A is also an element of a set B, that is, suppose a ∈ A implies a ∈ B. Then A is called a subset of B. We also say that A is contained in B or that B contains A. This relationship is written A⊆B

or

B⊇A

Two sets are equal if they both have the same elements or, equivalently, if each is contained in the other. That is: A = B if and only if A ⊆ B and B ⊆ A If A is not a subset of B, that is, if at least one element of A does not belong to B, we write A  ⊆ B.

EXAMPLE 1.2 Consider the sets: A = {1, 3, 4, 7, 8, 9}, B = {1, 2, 3, 4, 5}, C = {1, 3}. Then C ⊆ A and C ⊆ B since 1 and 3, the elements of C, are also members of A and B. But B ⊆ A since some of the elements of B, e.g., 2 and 5, do not belong to A. Similarly, A ⊆ B. Property 1: It is common practice in mathematics to put a vertical line “|” or slanted line “/” through a symbol to indicate the opposite or negative meaning of a symbol. Property 2: The statement A ⊆ B does not exclude the possibility that A = B. In fact, for every set A we have A ⊆ A since, trivially, every element in A belongs to A. However, if A ⊆ B and A  = B, then we say A is a proper subset of B (sometimes written A ⊂ B). Property 3: Suppose every element of a set A belongs to a set B and every element of B belongs to a set C. Then clearly every element of A also belongs to C. In other words, if A ⊆ B and B ⊆ C, then A ⊆ C. The above remarks yield the following theorem. Theorem 1.1: Let A, B, C be any sets. Then: (i) A ⊆ A (ii) If A ⊆ B and B ⊆ A, then A = B (iii) If A ⊆ B and B ⊆ C, then A ⊆ C Special symbols Some sets will occur very often in the text, and so we use special symbols for them. Some such symbols are: N = the set of natural numbers or positive integers: 1, 2, 3, . . . Z = the set of all integers: . . . , −2, −1, 0, 1, 2, . . . Q = the set of rational numbers R = the set of real numbers C = the set of complex numbers Observe that N ⊆ Z ⊆ Q ⊆ R ⊆ C.

CHAP. 1]

SET THEORY

3

Universal Set, Empty Set All sets under investigation in any application of set theory are assumed to belong to some fixed large set called the universal set which we denote by U unless otherwise stated or implied. Given a universal set U and a property P, there may not be any elements of U which have property P. For example, the following set has no elements: S = {x | x is a positive integer, x 2 = 3} Such a set with no elements is called the empty set or null set and is denoted by ∅ There is only one empty set. That is, if S and T are both empty, then S = T , since they have exactly the same elements, namely, none. The empty set ∅ is also regarded as a subset of every other set. Thus we have the following simple result which we state formally. Theorem 1.2: For any set A, we have ∅ ⊆ A ⊆ U.

Disjoint Sets Two sets A and B are said to be disjoint if they have no elements in common. For example, suppose A = {1, 2},

B = {4, 5, 6},

and

C = {5, 6, 7, 8}

Then A and B are disjoint, and A and C are disjoint. But B and C are not disjoint since B and C have elements in common, e.g., 5 and 6. We note that if A and B are disjoint, then neither is a subset of the other (unless one is the empty set).

1.3 VENN DIAGRAMS A Venn diagram is a pictorial representation of sets in which sets are represented by enclosed areas in the plane. The universal set U is represented by the interior of a rectangle, and the other sets are represented by disks lying within the rectangle. If A ⊆ B, then the disk representing A will be entirely within the disk representing B as in Fig. 1-1(a). If A and B are disjoint, then the disk representing A will be separated from the disk representing B as in Fig. 1-1(b).

Fig. 1-1

4

SET THEORY

[CHAP. 1

However, if A and B are two arbitrary ...