Schaum's Outline of Discrete Mathematics, Third Edition ...

1 schaum SOUTLINEOFT heoryandProblemsofDISCRETEMATHEMATICSS earch ON Google "EME Technologies"This page intentionally left blank Search ON Google "EME Technologies" schaum SOUTLINEOFT heoryandProblemsofDISCRETEMATHEMATICST hirdEditionSEYMOUR LIPSCHUTZ, UniversityMARC LARS LIPSON, of VirginiaSchaum s Outline SeriesMcGRAW-HILLNew York Chicago San Francisco Lisbon London MadridMexico City Milan New Delhi San JuanSeoul Singapore Sydney TorontoSearch ON Google "EME Technologies"Copyright 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. All rights reserved. Manufactured in the United States of as permitted under the United States Copyright Act of 1976, no part of this publication may be reproduced or distributed in any formor 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: trademarks are trademarks of their respective owners.

2 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 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 trainingprograms. For more information, please contact George Hoare, Special Sales, at 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 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 copyof the work, you may not decompile, disassemble, reverse engineer, reproduce, modify, create derivative works based upon, transmit, dis-tribute, disseminate, sell, publish or sublicense the work or any part of it without McGraw-Hill s prior consent.

3 You may use the work foryour own noncommercial and personal use; any other use of the work is strictly prohibited. Your right to use the work may be terminatedif you fail to comply with these terms. THE WORK IS PROVIDED AS IS. McGRAW-HILL AND ITS LICENSORS MAKE NO GUARANTEES OR WARRANTIES AS TOTHE ACCURACY, ADEQUACY OR COMPLETENESS OF OR RESULTS TO BE OBTAINED FROM USING THE WORK, INCLUD-ING ANY INFORMATION THAT CAN BE ACCESSED THROUGH THE WORK VIA HYPERLINK OR OTHERWISE, ANDEXPRESSLY DISCLAIM ANY WARRANTY, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO IMPLIED WAR-RANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. McGraw-Hill and its licensors do not warrant orguarantee that the functions contained in the work will meet your requirements or that its operation will be uninterrupted or error McGraw-Hill nor its licensors shall be liable to you or anyone else for any inaccuracy, error or omission, regardless of cause, in thework or for any damages resulting therefrom.

4 McGraw-Hill has no responsibility for the content of any information accessed through thework. Under no circumstances shall McGraw-Hill and/or its licensors be liable for any indirect, incidental, special, punitive, consequentialor 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 suchdamages. This limitation of liability shall apply to any claim or cause whatsoever whether such claim or cause arises in contract, tort or oth-erwise. DOI: ON Google "EME Technologies"We hope you enjoy thisMcGraw-Hill eBook! Ifyou d like more information about this book,its author, or related books and websites,please click to learn more?Search ON Google "EME Technologies"PREFACED iscrete mathematics, the study of finite systems, has become increasingly important as the computer agehas advanced. The digital computer is basically a finite structure, and many of its properties can be understoodand interpreted within the framework of finite mathematical systems.

5 This book, in presenting the more essentialmaterial, may be used as a textbook for a formal course in Discrete mathematics or as a supplement to all first three chapters cover the standard material on sets, relations, and functions and algorithms. Nextcome chapters on logic, counting, and probability. We then have three chapters on graph theory : graphs, directedgraphs, 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 chapter on functions and algorithms includes a discussion of cardinality and countable sets, and chapters on graph theory include discussions on planarity, traversability, minimal paths, and Warshall s andHuffman s algorithms. We emphasize that the chapters have been written so that the order can be changed withoutdifficulty and without loss of chapter begins with a clear statement of pertinent definitions, principles, and theorems with illustrativeand other descriptive material.

6 This is followed by sets of solved and supplementary problems. The solvedproblems serve to illustrate and amplify the material, and also include proofs of theorems. The supplementaryproblems furnish a complete review of the material in the chapter. More material has been included than can becovered in most first courses. This has been done to make the book more flexible, to provide a more useful bookof reference, and to stimulate further interest in the LipschutzMarc Lars LipsonvCopyright 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use. Search ON Google "EME Technologies"This page intentionally left blank Search ON Google "EME Technologies"CONTENTSCHAPTER 1 Set and Elements, of Sets, Sets, Counting of Sets, Power Sets, Induction12 SolvedProblems12 SupplementaryProblems18 CHAPTER Representatives of of of Ordering Relations33 SolvedProblems34 SupplementaryProblems40 CHAPTER 3 Functions and , Onto, and Invertible Functions, Exponential and Logarithmic , Indexed Classes of Defined and of Algorithms57 SolvedProblems60 SupplementaryProblems66viiFor more information about this title, click hereSearch ON Google "EME Technologies"viiiCONTENTSCHAPTER 4 Logic and Propositional and Compound Logical and Truth and of and Biconditional Functions.

7 Of Quantified Statements79 SolvedProblems82 SupplementaryProblems86 CHAPTER 5 Techniques of Counting Pigeonhole Inclusion Exclusion Diagrams95 SolvedProblems96 SupplementaryProblems103 CHAPTER 6 Advanced Counting Techniques, with and Unordered Exclusion Principle Principle Recurrence Relations with Constant Second-Order Homogeneous Linear General Homogeneous Linear Recurrence Relations116 SolvedProblems118 SupplementaryProblems121 CHAPTER Space and Probability Repeated Trials, Binomial Variables132 Search ON Google "EME Technologies" s Inequality, Law of Large Numbers135 SolvedProblems136 SupplementaryProblems149 CHAPTER 8 Graph , Data and , Isomorphic and Homeomorphic , and Eulerian Graphs, Bridges of K and Weighted , Regular, and Bipartite Graphs in Computer Problem176 SolvedProblems178 SupplementaryProblems191 CHAPTER 9 Directed Representation of Directed s Algorithm, Shortest Representation of Directed Algorithms.

8 Depth-First and Breadth-First Cycle-Free Graphs, Topological Algorithm for Shortest Path218 SolvedProblems221 SupplementaryProblems228 CHAPTER 10 Binary and Extended Binary Binary Trees in Binary Search Queues, Lengths, Huffman s (Ordered Rooted) Trees Revisited251 SolvedProblems252 SupplementaryProblems259 Search ON Google "EME Technologies"xCONTENTSCHAPTER 11 Properties of the and Inequalities, Absolute , Common Divisor, Euclidean Theorem of Equations278 SolvedProblems283 SupplementaryProblems299 CHAPTER 12 Languages, Automata, , Words, Free Expressions, Regular State 13 Finite State Machines and Turing State del Functions330 SolvedProblems331 SupplementaryProblems334 CHAPTER 14 Ordered Sets and Diagrams of Partially Ordered and (Similar) Ordered , Complemented Lattices350 SolvedProblems351 SupplementaryProblems360 Search ON Google "EME Technologies"CONTENTSxiCHAPTER 15 Boolean Algebras as Form for Form for Boolean Boolean Expressions, Prime Gates and Tables, Boolean Maps383 SolvedProblems389 SupplementaryProblems403 APPENDIX AVectors and Addition and Scalar (Nonsingular) Matrices, Row Operations, Gaussian Elimination (Optional) (Zero-One)

9 Matrices422 SolvedProblems423 SupplementaryProblems429 APPENDIX BAlgebraic , Normal Subgroups, and , Internal Domains, and Over a Field446 SolvedProblems450 SupplementaryProblems461 Index467 Search ON Google "EME Technologies"This page intentionally left blank Search ON Google "EME Technologies" schaum SOUTLINE OFTheory and Problems ofDISCRETEMATHEMATICSS earch ON Google "EME Technologies"This page intentionally left blank Search ON Google "EME Technologies"CHAPTER 1 Set INTRODUCTIONThe concept of asetappears in all mathematics. This chapter introduces the notation and terminology of settheory which is basic and used throughout the text. The chapter closes with the formal definition of mathematicalinduction, with SETS AND ELEMENTS, SUBSETSA setmay be viewed as any well-defined collection of objects, called theelementsormembersof the usually uses capital letters,A,B,X,Y,..,to denote sets, and lowercase letters,a,b,x,y.

10 , to denoteelements of sets. Synonyms for set are class, collection, and family. Membership in a set is denoted as follows:a Sdenotes thatabelongs to a setSa, b Sdenotes thataandbbelong to a setSHere is the symbol meaning is an element of. We use to mean is not an element of. Specifying SetsThere are essentially two ways to specify a particular set. One way, if possible, is to list its members separatedby commas and contained in braces { }.Asecond way is to state those properties which characterized the elementsin the set. Examples illustrating these two ways are:A={1,3,5,7,9}andB={x|xis an even integer,x>0}That is,Aconsists of the numbers 1, 3, 5, 7, 9. The second set, which reads:Bis the set ofxsuch thatxis an even integer andxis greater than 0,denotes the setBwhose elements are the positive integers. Note that a letter, usuallyx, is used to denote a typicalmember of the set; and the vertical line | is read as such that and the comma as and.