Jon Pierre Fortney - Discrete Mathematics for Computer Science: An Example-Based Introduction

Discrete Mathematics for Computer Science

First Edition published 2021

by CRC Press

6000 Broken Sound Parkway NW, Suite 300, Boca Raton, FL 33487-2742

and by CRC Press

2 Park Square, Milton Park, Abingdon, Oxon, OX14 4RN

2021 Jon Pierre Fortney

CRC Press is an imprint of Taylor & Francis Group, LLC

The right of Jon Pierre Fortney to be identified as author of this work has been asserted by him in accordance with sections 77 and 78 of the Copyright, Designs and Patents Act 1988.

Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, access

Trademark notice: Product or corporate names may be trademarks or registered trademarks and used only for identification and explanation without intent to infringe.

Library of Congress Cataloging-in-Publication Data

Names: Fortney, Jon Pierre, author.

Title: Discrete mathematics for computer science : an example-based introduction / Jon Pierre Fortney.

Description: First edition. | Boca Raton : C&H/CRC Press, 2021. | Includes bibliographical references and index.

Identifiers: LCCN 2020034984 (print) | LCCN 2020034985 (ebook) | ISBN 9780367549886 (hardback) | ISBN 9781003091479 (ebook).

Subjects: LCSH: Computer science--Mathematics.

Classification: LCC QA76.9.M35 F67 2021 (print) | LCC QA76.9.M35 (ebook) | DDC 004.01/51--dc23

LC record available at https://lccn.loc.gov/2020034984

LC ebook record available at https://lccn.loc.gov/2020034985

ISBN: 978-0-367-54988-6 (hbk)

ISBN: 978-0-367-54989-3 (pbk)

ISBN: 978-1-003-09147-9 (ebk)

Typeset in Computer Modern font

by KnowledgeWorks Global Ltd.

To Ron Ryan Noval

One of the major challenges of teaching mathematics at the community college or small liberal arts college level is finding books that are genuinely appropriate for the student population. Writing this book for the discrete mathematics for computer science course at Zayed University happened because I was completely unable to find any textbook on the market that both (1) covered the material I needed to cover and (2) was written at a level appropriate for my students. Often textbooks cover a huge range of material, usually far more material than even good students can fully assimilate and understand in a single semester. On some level this is not surprising; textbooks are written by experts in the topic who deeply understand the nuances of the field and want to make everything as precise and clear as possible, while still illustrating the subtleties and complexities of the topic. Unfortunately, the meaning of the word clear depends on the individual. Books that are extremely precise and that delve into subtleties or nuance are completely inappropriate for many college level students. I believe students benefit most with a clear, clean, uncluttered, down-to-earth exposition of the material.

This book is intended for a first- or second -year discrete mathematics course for computer science majors. In it I cover many of the most important mathematical topics that future computer science majors need to be aware of. The first contains the answers to all the end-of-chapter problems in the book.

This book has several features that make it essentially unique among discrete mathematics books, particularly discrete mathematics books aimed at computer science majors. It is written with students at community colleges or small liberal arts colleges in mind. The language in this book is very straightforward. Sentences are not complex and, as much as possible, the vocabulary and explanations are kept simple. Whenever definitions or explanations are made, they are quickly followed by examples to aid students in their understanding. Words being defined are always given in bold face. Paragraphs are kept short and the amount of prose a student is required to read between examples is kept to a minimum. All of this not only strongly reinforces the definition or explanation, but also aids students to fully understand the written content. Indeed, this textbook would be ideal for international students and non-native English speakers. Furthermore, students without much mathematical maturity or abstract thinking ability need numerous examples to help them bridge the gap between concrete and abstract thought. They also need a significant amount of practice to help them both learn and internalize the material. I have attempted to provide both numerous examples and practice problems for students to do just this. There are over 200 worked examples scattered throughout the book, boxed for easy reference. There are also over 200 end-of-chapter problems, many of which include multiple parts, which provide students ample practice opportunities. The answers to these problems are provided in , allowing students to check their work.

Another strategy I have used is to relate the mathematical topics back to computer science as much as is reasonably possible. At the level the textbook is written, many of the examples drawn from computer science are necessarily quite superficial and simple, but they still provide students interested in computer science motivation to understand the mathematics. Making the mathematics relevant to their future classes and lives is essential in encouraging students to learn the material. Explaining the importance and relevance of algorithms in explores the relation between binary numbers, Boolean algebra, and circuit design.

As written, I believe the entire book can be easily covered in a single semester. If used in a school that follows the quarter system, if necessary, .

Finally, I would like to express my appreciation to both Ron Noval and Rene Hinojosa for their ongoing support throughout the writing of this book. I would also like to thank my many past students who offered invaluable comments on the various drafts of this book and who pointed out innumerable typos.

Jon Pierre Fortney
June 2020

Algorithms play an extremely important role in both computer science and mathematics. Algorithms are detailed instructions on how to carry out some specific task. Computer programs are implementations of algorithms, so it is very important that computer science majors and programmers have a good understanding of how algorithms work. Deciding on an algorithm is generally the first step of writing a computer program. Because algorithms will be used throughout this book we begin by introducing some of the basic concepts and ideas related to algorithms.

An algorithm is a finite sequence of well-defined steps to perform some task such that

• each step is a clear instruction that can be done in a finite amount of time,