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.

Contents:

• Preface
• Acknowledgments
• Mathematical Reasoning and Basic Logic
• Relations, Functions, Partial Functions, Equinumerosity
• Equinumerosity, the Pigeonhole Principle, Countable Sets, Infinite Sets
• Equivalence Relations and Partitions
• Partial Orders, Lattices, Well-Founded Orderings, Boolean Algebras
• Some Counting Problems; Binomial and Multinomial Coefficients
• Unique Prime Factorization in ℤ and GCDs; Public Key Cryptography; RSA
• An Introduction to Discrete Probability
• Graphs, Part I: Basic Notions
• Graphs, Part II: More Advanced Notions
• Mathematical Reasoning and Logic, A Deeper View
• Bibliography
• Index
• Symbol Index

Readership: Undergraduate students in mathematics and computer science.