Skip to main content
Elsevier
View Cart

Discrete Mathematics With Logic

  • 1st Edition - July 20, 2023
  • Latest edition
  • Authors: Martin Milanic, Brigitte Servatius, Herman Servatius
  • Language: English

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… Read more

World Book Day celebration

Where learning shapes lives

Up to 25% off trusted resources that support research, study, and discovery.

Explore resources

Description

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

Readership

Students in undergraduate & graduate programs taking courses on Discrete Math, typically taught in Mathematics and Computer Science departments

Table of contents

  • 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

Product details

  • Edition: 1
  • Latest edition
  • Published: July 26, 2023
  • Language: English

About the authors

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

View book on ScienceDirect

Read Discrete Mathematics With Logic on ScienceDirect