1 David Liben-Nowell Department of Computer Science Carleton College Discrete Mathematics for Computer Science or (A Bit of) The Math that Computer Scientists Need to Know VP AND EDITORIAL DIRECTOR Laurie Rosatone SENIOR DIRECTOR Don Fowley ACQUISITIONS EDITOR Linda Ratts EDITORIAL MANAGER Gladys Soto CONTENT MANAGEMENT DIRECTOR Lisa Wojcik CONTENT MANAGER Nichole Urban SENIOR CONTENT SPECIALIST Nicole Repasky PRODUCTION EDITOR Rajeshkumar Nallusamy PHOTO RESEARCHER Billy Ray COVER PHOTO CREDIT © slobo/Getty Images, Inc. This book was set in TeXGyrePagella 10/12 by SPi Global and printed and bound by Strategic Content Imaging. This book is printed on acid free paper. ∞ Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/ citizenship. Copyright © 2018, John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923 (Web site: www.copyright.com). Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201) 748-6011, fax (201) 748-6008, or online at: www.wiley.com/go/permissions. Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return shipping label are available at: www.wiley.com/go/returnlabel. If you have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative. ISBN: 978-1-118-06553-2 (PBK) ISBN: 978-1-119-07073-3 (EVALC) Library of Congress Cataloging in Publication Data: Liben-Nowell, David, author. Title: Discrete mathematics for computer science / by David Liben-Nowell. Description: Hoboken, NJ : John Wiley & Sons, 2017. | Includes index. | Identifiers: LCCN 2017025007 (print) | LCCN 2017035974 (ebook) | ISBN 9781119397199 (pdf) | ISBN 9781119397113 (epub) | ISBN 9781118065532 (pbk.) Subjects: LCSH: Computer science—Mathematics. Classification: LCC QA76.9.M35 (ebook) | LCC QA76.9.M35 L53 2017 (print) | DDC 004.01/51—dc23 LC record available at https://lccn.loc.gov/2017025007 The inside back cover will contain printing identification and country of origin if omitted from this page. In addition, if the ISBN on the back cover differs from the ISBN on this page, the one on the back cover is correct. To MDSWM, with never-ending appreciation, and in loving memory of my grandfather, Jay Liben, who brought more joy, curiosity, and kvetching to this world than anyone else I know. Contents 1 On the Point of this Book 101 2 Basic Data Types 201 2.1 Why You MightCare 202 2.2 Booleans, Numbers,and Arithmetic 203 2.3 Sets: UnorderedCollections 222 2.4 Sequences, Vectors,and Matrices: OrderedCollections 237 2.5 Functions 253 2.6 Chapter ataGlance 270 3 Logic 301 3.1 Why You MightCare 302 3.2 An Introduction toPropositional Logic 303 3.3 Propositional Logic: Some Extensions 317 3.4 An Introduction toPredicateLogic 331 3.5 PredicateLogic: NestedQuantifiers 349 3.6 Chapter ataGlance 362 6 4 Proofs 401 4.1 Why You MightCare 402 4.2 Error-CorrectingCodes 403 4.3 Proofs and Proof Techniques 423 4.4 Some Examplesof Proofs 441 4.5 Common ErrorsinProofs 458 4.6 Chapter ataGlance 469 5 Mathematical Induction 501 5.1 Why You MightCare 502 5.2 Proofs by MathematicalInduction 503 5.3 Strong Induction 521 5.4 RecursivelyDefinedStructuresand StructuralInduction 533 5.5 Chapter ataGlance 546 6 Analysis of Algorithms 601 6.1 Why You MightCare 602 6.2 Asymptotics 603 6.3 AsymptoticAnalysisofAlgorithms 617 6.4 RecurrenceRelations: Analyzing RecursiveAlgorithms 631 6.5 RecurrenceRelations: The MasterMethod 647 6.6 Chapter ataGlance 657 7 Number Theory 701 7.1 Why You MightCare 702 7.2 Modular Arithmetic 703 7.3 Primalityand RelativePrimality 717 7.4 MultiplicativeInverses 734 7.5 Cryptography 745 7.6 Chapter ataGlance 756 7 8 Relations 801 8.1 Why You MightCare 802 8.2 Formal Introduction 803 8.3 Propertiesof Relations: Reflexivity,Symmetry,and Transitivity 818 8.4 SpecialRelations: EquivalenceRelations and Partial/TotalOrders 833 8.5 Chapter ataGlance 850 9 Counting 901 9.1 Why You MightCare 902 9.2 Counting Unionsand Sequences 903 9.3 UsingFunctions to Count 926 9.4 Combinations and Permutations 944 9.5 Chapter ataGlance 965 10 Probability 1001 10.1 Why You MightCare 1002 10.2 Probability,Outcomes,and Events 1005 10.3 Independence and Conditional Probability 1021 10.4 Random Variablesand Expectation 1041 10.5 Chapter ataGlance 1067 11 Graphs and Trees 1101 11.1 Why You MightCare 1102 11.2 Formal Introduction 1103 11.3 Paths,Connectivity, and Distances 1129 11.4 Trees 1147 11.5 WeightedGraphs 1164 11.6 Chapter ataGlance 1177 12 Index 1201