Purchase textbook

Discrete Mathematics With Logic,

Edition 1

Editors: By Martin Milanic, Brigitte Servatius and Herman Servatius

Publication Date: 26 Jul 2023

0 Reviews

Conformance

PDF/UA-1
The publication was certified on 20250710
For queries regarding accessibility information, contact [email protected]

Ways Of Reading

This e-publication is accessible to the full extent that the file format and types of content allow, on a specific reading device, by default, without necessarily including any additions such as textual descriptions of images or enhanced navigation.

Navigation

The contents of the PDF have been tagged to permit access by assistive technologies as per PDF-UA-1 standard.
Page breaks included from the original print source

Additional Accessibility Information

The language of the text has been specified (e.g., via the HTML or XML lang attribute) to optimise text-to-speech (and other alternative renderings), both at the whole document level and, where appropriate, for individual words, phrases or passages in a different language.

Note

This product relies on 3rd party tooling which may impact the accessibility features visible in inspection copies. All accessibility features mentioned would be present in the purchased version of the title.

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.

Key Features

Provides a class-tested reference used on multiple years
Includes many exercises and helpful guided solutions to aid student comprehension and practice
Appropriate for undergraduate courses and for students with no background in algebra or computational skills

About the author

By Martin Milanic, University of Primorska, Koper, Slovenia; Brigitte Servatius, Professor, Worcester, Massachusetts, US and Herman Servatius, Professor, Worcester, Massachusetts, US

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