# Spiral Workbook for Discrete Mathematics

Harris Kwong, State University of New York (SUNY) Fredonia

Copyright Year: 2015

ISBN 13: 9781942341161

Publisher: Open SUNY

Language: English

## Formats Available

## Conditions of Use

Attribution-NonCommercial-ShareAlike

CC BY-NC-SA

## Reviews

The book does not cover graphs, discrete probability, random variables and expectations. It also does not cover some counting problems like combinations with repetition and permutations with indistinguishable objects. It does not cover all rules... read more

The book does not cover graphs, discrete probability, random variables and expectations. It also does not cover some counting problems like combinations with repetition and permutations with indistinguishable objects. It does not cover all rules of inference in propositional logic. I teach all these topics in CS 317 (Discrete Information Structures), a required course for computer science majors at my university. The indices are effective. There is no glossary, but this is not a problem because the topic indices are effective. Most other textbooks on discrete mathematics do not have a glossary either.

While most parts of the book are accurate, I do have concerns about some parts (theory as well as problems) as described next. In the problems on counting selections with certain balls on page 240, the problem descriptions should state that all balls of same color are distinguishable (they vary in design or diameter or weight or texture or something else). Without this, the answers in the book are overcounts. The hint ``use permutation if order matters, otherwise use combinations'' on page 242 is oversimplifying. What if a problem involves both permutations and combinations or involves neither permutations nor combinations? I have major concerns about the treatment of functions in the chapter on functions. Sometimes the author talks of functions and sometimes he talks of well-defined functions. Also he talks of functions assuming that they are well-defined functions. Then he talks of one-to-one functions, onto functions, inverse functions, composite functions, and constant functions without telling that they are well-defined functions. The concept of functions is enough, the concept of well-defined functions is unnecessary. Some of the tips are inaccurate, e.g. there is a tip on page 8 which says that an identity should be never proved by simplifying both sides simultaneously. What the author should say is that the proof of an identity should never equate two sides whose equality is not verified. One can prove an identity by simplifying two sides simultaneously as long as a question mark is included on equality sign in all steps except the one in which equality is established. The question mark on equality sign shows that we are not sure about equality and are in the process of confirming or denying it. There is a typo in theorem 8.2.4 on page 224. |A U B U B| in the theorem statement should be |A U B U C|.

It is easy to update this book with changing times or syllabi. Some exercies have only symbols, numbers and mathematical operators and mathematical terms with no mention of real world. Exercises 6.3 and 6.4 about one-to-one and onto functions fall in this category. My examples of relating these topics to real world include mapping people to e-mail addresses or companies of employment or web pages or social media accounts. The quantity of problems in some exercises is higher that what is needed to understand the concepts perfectly. More diversity in the problems will be more useful than more problems in some exercises. It will be good to mention that a bijection is also called ``one-to-one correspondence''. Inclusion of topological sorting after Hasse diagram in the chapter on relations will be useful.

Some statements are vague. On page 43, the author says that some proofs only require direct computation. I think what the author means is that some proofs involve only basic mathematical facts, laws, and transformations leading to the goal to be proved and do not use one of the standard proof methods which include vacuous proof, trivial proof, proof by contradiction, direct proof, and proof by cases. I think the author's point can be better explained by first explaining the standard proof methods and then telling that there are proofs that do not fall into any of these categories. The definition of a function on page 163 is spread over two bullets. The definition should be covered by one bullet. If a student reads only one of the two bullets, he/she will leave with an incorrect understanding of what functions are. Bullets should be ideally used for certain kinds of information like facts, opinions, goals, guidelines, and observations. If bullets are used for describing a multi-step procedure, then one bullet should be used for describing all steps of the same procedure. The author describes different steps of mathematical induction using different bullets. If a student does not read all bullets, he/she may have an incorrect understanding of mathematical induction. Spreading N related steps of the same procedure over N bullets may lead a student to think that there are N different one-step procedures. Though most of the book is very clear, there are parts where clarity should be improved. There are many places where the author has given extra information not found in other textbooks to avoid common misunderstanding among students. I applaud these efforts of the author. The author has related multiple representations at many places, like relating a set containing sets to cubes within cubes and I am sure that students will appreciate this. This certainly helps different learning and thinking styles. I found the notation for logical XOR very confusing. For XOR of propositions p and q, a dash below OR is put between p and q. Some students may think that this is OR of NOT or NOT of OR. I suggest using + within a circle for XOR or some other notation that does not combine existing notation in an ambiguous manner.

Except rare instances like considering functions and well-defined functions as sometimes different and sometimes same, the book is highly consistent.

The book is very modular and this has lead to a clear index at the start of the book. One may often find relevant pages faster by using the front index than the back index. My concern is that there are more modules (sections and subsections of chapters and the resulting exercise sets) than necessary and this can affect students' understanding, self-perception of preparedness, and mental stress. For example, onto functions and one-to-one functions are presented as separate modules. It will be easier for students to understand these if they are in the same module. If different properties of functions are presented in different modules, students may think of satisfaction or dissatisfaction of those properties separately. They may even think that those properties are mutually exclusive. If different related properties are mentioned in the same module, students may think of their combinations in addition to separate satisfaction or dissatisfaction of each property. This will be more intellectually enriching for students. If a student learns the module on say onto functions, solving all problems, then the student may feel that he/she has done a lot, but what has really happened is that the student learnt one definition very well. So students who estimate preparedness using study time or quantity of problems solved may consider themselves highly prepared for an exam which is not true when there are many other modules to be studied. Creating N modules for N related terms that can be presented in one module can stress students more because students may consider one module as easier to study than N modules.

The order in which topics are presented respects their dependency. This is very good. There is room for moving information among chapters for better learning without disturbing the order of dependency of topics or the order of chapters. For example, some rules of inference from propositional logic are mentioned in the chapter on proof methods. These rules should be moved to the chapter on logic. Distribution of information in a book can affect how students store it (how they chunk it) and process it. Number of pages of individual chapters can be reduced considerably, e.g. six pages (157-162) are used to just convey what functions are. Similarly, four pages are used to convey what biconditional statements are. This is much more than necessary and students may get low intellectual return per time spent or page read. I found some instructions like ``Be sure to describe it correctly and properly'' on page 188 unnecessary. Perhaps such a general instruction can be given at the start for all problems instead of individual problems. Extra instructions for individiual problems should be more specific.

Some students may find it more convenient if different chapters are presented as different pdf files or all theory, all exercises, and all solutions are presented in three separate pdf files. I do not consider this necessary. I could navigate the book fast. It will be useful to separate different truth assignments in truth tables with separating horizontal lines for easier reading.

The English is very good. Mathematical expressions and equations do not end with a period like sentences in English. I suggest removing these periods. I found some of these in examples of incorrect proofs. There is an extra ``a'' in the definition of reflexive relations on page 201. That should be removed.

(I think this criterion is less relevant to engineering, mathematics and computer science, and more relevant to other disciplines which include geography, economics, politics, religious studies, architecture, history, healthcare, law, and linguistics.) The book does not have content that will offend any population. The topic of the book neither requires nor prohibits inclusion of races, ethnicities, and backgrounds in examples and problems.

The author has clearly put in a tremendous effort in this book. The best features of the book are innovative problems, examples, and explanations, along with tips for students to avoid many common mistakes and present their answers better. I will gladly recommend specific exercises from this book to students who want extra problems for extra practice.

This book covers the main topics in a discrete mathematics text. It does not include an analysis of algorithms, graphs, trees, and other topics that would be of interest to computer science students. The presentation of logic and the techniques... read more

This book covers the main topics in a discrete mathematics text. It does not include an analysis of algorithms, graphs, trees, and other topics that would be of interest to computer science students. The presentation of logic and the techniques for writing proofs are thorough and nicely laid out. The problems presented to the students have sufficient variety. New definitions could be included in the summary of the section in which they are presented.

The mathematical content is accurate, though there are a few instances where definitions in this text deviate a bit from those presented in mathematics textbooks. For example, I have read mathematical books that define a function, f, with domain A and co-domain B as a subset of AxB satisfying two properties: for every element of A, a, there exists an element of B, b, such that (a, b) is an element of f, and if (a, b) and (a, c) are elements of f, then b = c. In this textbook, the graph of a function is defined this way (sort of), but functions are not presented as a collection of ordered pairs when initially being defined. These differences can be used to point out the importance of learning definitions and terminology, and using those definitions to create and explore conjectures.

The textbook covers traditional material included in a discrete mathematics class. It includes examples and problems that are typically used in other textbooks in this field. This textbook does not include examples that are particularly modern, or that reference "pop culture" which helps with longevity.

The text is very well written. The material on formulating proofs is extremely well written, and could be incorporated into any course that helps students make the transition from computational mathematics to abstract mathematics. The explanations are clear, the examples highlight what students should do and what they should avoid. Common mistakes are pointed out with clear explanations and examples. The format of the mathematical steps involved in solving a problem makes it easy to follow along and understand the calculations being presented. There are a few proofs that include the word "obviously" as a reason, however, and it would be helpful to have all definitions presented similarly to how theorems are stated (blocked to stand out and labeled as such).

Consistent terminology and notation is used throughout the book.

The sections are broken up into subsections that fit a particular topic and do not include an excessive amount of material.

Each subsection presents a topic and explores the ideas in more depth. The sequence of subsections in a chapter follows a natural progression that is typical for a discrete mathematics textbook. Each chapter is well-organized and the content being discussed builds on previously presented ideas.

Some of the "hands-on exercises" are split over two pages, making it difficult to understand the task needing to be practiced (for example, exercise 6.2.1). The experience of scrolling through the pdf file was as expected. Leaving space between the hands-on exercise problems reflect that it is a workbook that will be printed, but if a student only accesses the text as a pdf file, the space is not needed. There are pros and cons to each arrangement.

The explanations and presentation of material use correct grammar and spelling. I did not see any glaring errors (grammatical or typographical).

This is a standard mathematics textbook without references to "pop culture" or terminology that could be considered offensive. It does not contain images of events or people with the potential for being problematic in the future. On the other hand, having specific examples of how the concepts being introduced are relevant to computer science (for example, RSA encryption, hash functions etc...) could help motivate students to learn this material.

Overall, I thought that the foundations of mathematics are well-presented. The advice to students in the Introduction could be shared in every math class! The material is clearly presented, there are ample hands-on exercises, and students would benefit from reading this textbook. Including a few applications of the material being covered would strengthen the textbook, and including topics related to an analysis of algorithms (and big-Oh notation), graphs and trees would complete the topics presented in a typical discrete mathematics class.

## Table of Contents

- 1 An Introduction
- 2 Logic
- 3 Proof Techniques
- 4 Sets
- 5 Basic Number Theory
- 6 Functions
- 7 Relations
- 8 Combinatorics

## Ancillary Material

## About the Book

This is a text that covers the standard topics in a sophomore-level course in discrete mathematics: logic, sets, proof techniques, basic number theory, functions, relations, and elementary combinatorics, with an emphasis on motivation. It explains and clarifies the unwritten conventions in mathematics, and guides the students through a detailed discussion on how a proof is revised from its draft to a final polished form. Hands-on exercises help students understand a concept soon after learning it. The text adopts a spiral approach: many topics are revisited multiple times, sometimes from a different perspective or at a higher level of complexity. The goal is to slowly develop students' problem-solving and writing skills.

Open SUNY Textbooks is an open access textbook publishing initiative established by State University of New York libraries and supported by SUNY Innovative Instruction Technology Grants. This initiative publishes high-quality, cost-effective course resources by engaging faculty as authors and peer-reviewers, and libraries as publishing service and infrastructure. The pilot launched in 2012, providing an editorial framework and service to authors, students and faculty, and establishing a community of practice among libraries. Participating libraries in the 2012- 2013 pilot include SUNY Geneseo, College at Brockport, College of Environmental Science and Forestry, SUNY Fredonia, Upstate Medical University, and University at Buffalo, with support from other SUNY libraries and SUNY Press. More information can be found at http://textbooks.opensuny.org.

## About the Contributors

### Author

**Harris Kwong** is a mathematics professor at SUNY Fredonia. He was born and raised in Hong Kong. After finishing high school there, he came to the United States to further his education. He received his B.S. and M.S. degrees from the University of Michigan, and Ph.D. from the University of Pennsylvania. His research focuses on combinatorics, number theory, and graph theory. His work appears in many international mathematics journals. Besides research articles, he also contributes frequently to the problems and solutions sections of Mathematics Monthly, Mathematics Magazine, College Journal of Mathematics, and Fibonacci Quarterly. He gives thanks and praises to God for his success.