Discrete Mathematics With Logic

Discrete Mathematics provides key concepts and a solid, rigorous foundation in mathematical reasoning. Appropriate for undergraduate as well as a starting point for more advanced class, the resource offers a logical progression through key topics without assuming any background in algebra or computational skills and without duplicating what they will learn in higher level courses. The book is designed as an accessible introduction for students in mathematics or computer science as it explores questions that test the understanding of proof strategies, such as mathematical induction.

For students interested to dive into this subject, the text offers a rigorous introduction to mathematical thought through useful examples and exercises.

Cover image
Title page
Table of Contents
Copyright
Dedication
Preface
Chapter 1: Discreteness
1.1. What is discrete mathematics?
1.2. The Multiplicative Principle
1.3. Binomial coefficients
1.4. Pascal's Triangle
1.5. Binary numbers
1.6. Base conversion
1.7. Case study: Towers of Hanoi
1.8. Case study: The Binomial Theorem
1.9. Case study: The Guarini Problem
1.10. Case study: Red rum and murder
1.11. Case study: Tit for tat, nim
1.12. Summary exercises
Chapter 2: Basic set theory
2.1. Introduction to sets
2.2. The power set
2.3. Set operations
2.4. Set identities
2.5. Double inclusion
2.6. Russell's paradox
2.7. Case study: Polyhedra
2.8. Case study: The missing region problem
2.9. Case study: Soma
2.10. Summary exercises
Chapter 3: Working with finite sets
3.1. Cardinality of finite sets
3.2. Bit vectors and ordering subsets
3.3. Inclusion/exclusion
3.4. Multiple Cartesian products and strings
3.5. Lexicographical order
3.6. Ordering permutations
3.7. Delisting permutations†
3.8. Case study: Wolf-Goat-Cabbage
3.9. Case study: The Gray code
3.10. Case study: The forgetful waitress problem
3.11. Summary exercises
Chapter 4: Formal logic
4.1. Statements and truth value
4.2. Logical operations
4.3. Implications
4.4. Double implication
4.5. Working with Boolean algebra
4.6. Boolean functions
4.7. DNF and CNF†
4.8. Case study: Classic logic puzzles
4.9. Case study: Spies
4.10. Case study: Pirates and cannonballs
4.11. Summary exercises
Chapter 5: Induction
5.1. Predicate logic
5.2. Existential and universal quantification
5.3. The theory of induction
5.4. Induction practice
5.5. Strong induction
5.6. Sets versus logic
5.7. Case study: Decoding the Gray code
5.8. Case study: The 14–15 puzzle
5.9. Case study: Towers of Hanoi
5.10. Case study: The Fibonacci numbers
5.11. Summary exercises
Chapter 6: Set structures
6.1. Relations
6.2. Functional relations
6.3. Counting functions on finite sets
6.4. Working with functional relations
6.5. Functions on infinite sets†
6.6. Cardinality of infinite sets†
6.7. Symmetry, reflexivity, transitivity
6.8. Orderings and equivalence
6.9. Case study: The developer's problem
6.10. Case study: Wolf-Goat-Cabbage II
6.11. Case study: The non-transitive dice
6.12. Case study: The developer's problem II
6.13. Case study: The missing region problem II
6.14. Summary exercises
Chapter 7: Elementary number theory
7.1. Primality, the Sieve of Eratosthenes
7.2. Common divisors, the Euclidean Algorithm
7.3. Extended Euclidean Algorithm
7.4. Modular arithmetic
7.5. Multiplicative inverses
7.6. The Chinese Remainder Theorem
7.7. Case study: Diophantus
7.8. Case study: The Indian formulas
7.9. Case study: Unique prime factorization
7.10. Summary exercises
Chapter 8: Codes and cyphers
8.1. Exponentials modulo n
8.2. Prime modulus
8.3. Cyphers and codes
8.4. RSA encryption
8.5. Little-o notation
8.6. Fast exponentiation
8.7. Case study: A Little Fermat proof
8.8. Case study: The Prüfer code
8.9. Summary exercises
Chapter 9: Graphs and trees
9.1. Graphs
9.2. Trees
9.3. Searching and sorting
9.4. Planarity
9.5. Eulerian graphs
9.6. Hamiltonian graphs
9.7. Case study: Fáry's theorem
9.8. Case study: Towers of Hanoi
9.9. Case study: Anchuria
9.10. Summary exercises
Selected answers and solutions
Chapter 1 – Discreteness
Chapter 2 – Basic set theory
Chapter 3 – Working with finite sets
Chapter 4 – Formal logic
Chapter 5 – Induction
Chapter 6 – Set structures
Chapter 7 – Elementary number theory
Chapter 8 – Codes and cyphers
Chapter 9 – Graphs and trees
Index

MM

Martin Milanic

Martin Milanič received his Ph.D. from Rutgers University in 2007. After a postdoctoral stay at Bielefeld University, he joined the University of Primorska in Slovenia, where he designed a higher-level course on graph algorithms and has been teaching various courses related to discrete mathematics. His main areas of research are structural and algorithmic graph theory. He has written over 80 papers (with over 100 coauthors). In 2017 he was awarded with Zois Recognition, the Slovenian national award for important achievements in science.

Affiliations and expertise

University of Primorska, Koper, Slovenia

BS

Brigitte Servatius

Both Herman and Brigitte Servatius obtained Ph.D. degrees from Syracuse University. Despite the fact that they entered their fifth decade of marriage, they have kept a bit of their individual mathematical identity. Herman’s interests are in geometry, algebra, and computer science, and Brigitte’s interests are in combinatorics and matroids. Their common interest is combinatorial group theory. Brigitte designed a discrete mathematics course at WPI (Worcester Polytechnic Institute, USA) for advanced mathematics students as an alternative to calculus back in 1987. It has grown into a popular course and is now cross-listed in mathematics and computer science. Discrete Mathematics developed over the many years of teaching the course at WPI to our (mostly) engineering students. Our next-generation coauthor ensures freshness.

Affiliations and expertise

Professor, Worcester, Massachusetts, US

HS

Herman Servatius

Both Herman and Brigitte Servatius obtained Ph.D. degrees from Syracuse University. Despite the fact that they entered their fifth decade of marriage, they have kept a bit of their individual mathematical identity. Herman’s interests are in geometry, algebra, and computer science, and Brigitte’s interests are in combinatorics and matroids. Their common interest is combinatorial group theory. Brigitte designed a discrete mathematics course at WPI (Worcester Polytechnic Institute, USA) for advanced mathematics students as an alternative to calculus back in 1987. It has grown into a popular course and is now cross-listed in mathematics and computer science. Discrete Mathematics developed over the many years of teaching the course at WPI to our (mostly) engineering students. Our next-generation coauthor ensures freshness.

Affiliations and expertise

Professor, Worcester, Massachusetts, US

Purchase options

LIMITED OFFER

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Institutional subscription on ScienceDirect

Resources

Martin Milanic

Brigitte Servatius

Herman Servatius