Mathematical Foundations and Aspects of Discrete Mathematics

This book is an introduction to discrete mathematics with a strong emphasis on formal reasoning. Beginning with the fundamentals of propositional and predicate logic, it develops proof techniques through deduction trees, truth tables, and formal semantics. The first chapter is devoted entirely to logical reasoning, providing a foundation for the rest of the text, which covers standard topics such as sets, functions, relations, induction, and recursion, as well as more advanced material like number theory, graph theory, and discrete probability.

Highlights of this book include an initial chapter that provides a gentle introduction to basic logic, including proof trees and templates, written from the perspective of a master logician. For the more advanced audience, another chapter provides a deeper look into basic logic by providing details on Gentzen-style deduction trees, first-order theories, the simply-typed λ-calculus, and Kripke models for intuitionistic logic. Other highlights include the inclusion–exclusion principle, the Möbius inversion formula, the RSA cryptosystem, and a thorough discussion on network flow problems, including the Max-Flow Min-Cut theorem and the Ford and Fulkerson algorithm. Each chapter concludes with a detailed summary and a comprehensive set of problems, making the book especially suitable for undergraduate students in mathematics and theoretical computer science.

Professor Jean Gallier has been with the Department of Computer and Information Science at the University of Pennsylvania for over 40 years. He holds a PhD in Computer Science from UCLA and is a world-renowned expert in computational logic. He also holds a joint appointment in the Department of Mathematics at the University of Pennsylvania. In addition to his seminal work on Horn satisfiability, he is well known for his mathematical textbooks on geometric modeling, linear algebra, and differential geometry. He is the author of 12 books, a listing of which can be found at https://www.cis.upenn.edu/~jean/home.html.

Jocelyn Quaintance is a mathematician with over thirty years of experience. She began her career by focusing on enumerative combinatorics. This resulted in the publication of Combinatorial Identities for Stirling Numbers: The Unpublished Notes of H W Gould (World Scientific, 2016, ISBN 978-981-4725-26-2, pp. xv + 260). The success of the Gould publication stimulated her interest in writing mathematical textbooks for a wide audience of students, scientists, engineers, mathematicians, and computer scientists. With her co-author Jean Gallier, she has fulfilled this goal and published over six textbooks on topics as varied as differential geometry, Lie groups, linear algebra, optimization, homological algebra, harmonic analysis, and group representations. She is currently a part-time lecturer in the Department of Computer and Information Science at the University of Pennsylvania, where she co-teaches MCIT CIS 5150: Mathematical Foundations of Machine Learning with Jean Gallier. In her spare time, she enjoys drawing whimsical animal portraits and cooking holiday meals.