Elementary Foundations: An Introduction to Topics in Discrete Mathematics

by Jeremy Sylvestre

Read here Read at LibreTextsPDF
Publisher
University of Alberta Augustana
Subjects
Mathematics, Combinatorics and Discrete Mathematics
Licence
GNU Free Documentation License, as LibreTexts states it
Who can read
Tweens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Licensing
  6. 1: Symbolic language
  7. 1.1: Statements
  8. 1.2: Converting language to symbols
  9. 1.3: Logical Analysis
  10. 1.4: Tautologies and contradictions
  11. 1.5: Activities
  12. 1.6: Exercises
  13. 2: Logical equivalence
  14. 2.1: Equivalence
  15. 2.2: Propositional Calculus
  16. 2.3: Converse, Inverse, and Contrapositive
  17. 2.4: Activities
  18. 2.5: Exercises
  19. 3: Boolean algebra
  20. 3.1: Boolean Polynomials
  21. 3.2: Disjunctive Normal Form
  22. 3.3: Exercises
  23. 4: Predicate logic
  24. 4.1: Predicates and Quantifers
  25. 4.2: Manipulating quantified statements
  26. 4.3: Vacuously true statements
  27. 4.4: Activities
  28. 4.5: Exercises
  29. 5: Arguments
  30. 5.1: Basic
  31. 5.2: Standard Arguments
  32. 5.3: Substituting into an argument
  33. 5.4: Activities
  34. 6: Definitions and proof methods
  35. 6.1: Definitions
  36. 6.2: Common mathematical statements
  37. 6.3: Direct Proof
  38. 6.4: Reduction to Cases
  39. 6.5: Statements Involving Disjunction
  40. 6.6: Proving the contrapositive
  41. 6.7: Proof by counterexample
  42. 6.8: Proving biconditionals
  43. 6.9: Proof by Contradiction
  44. 6.10: Existence and Uniqueness
  45. 6.11: Activities
  46. 6.12: Exercises
  47. 7: Proof by mathematical induction
  48. 7.1: Principle of Mathematical Induction
  49. 7.2: An application to logic
  50. 7.3: Strong form of Mathematical Induction
  51. 7.4: Activities
  52. 8: Axiomatic systems
  53. 8.1: Basics and examples
  54. 8.2: Incompleteness of axiomatic systems
  55. 8.3: Exercises
  56. 9: Sets
  57. 9.1: Basics
  58. 9.2: Defining sets
  59. 9.3: Subsets and equality of sets
  60. 9.4: Complement, union, and intersection
  61. 9.5: Cartesian Product
  62. 9.6: Alphabets and words
  63. 9.7: Sets of sets
  64. 9.8: Activities
  65. 9.9: Exercises
  66. 10: Functions
  67. 10.1: Basics
  68. 10.2: Properties of Functions
  69. 10.3: Important Examples
  70. 10.4: Composition of functions
  71. 10.5: Inverses
  72. 10.6: Activities
  73. 10.7: Exercises
  74. 11: Recurrence and induction
  75. 11.1: Sequences
  76. 11.2: Recurrence Relations
  77. 11.3: Solving through Iteration
  78. 11.4: Inductive definitions
  79. 11.5: Activities
  80. 11.6: Exercises
  81. 12: Cardinality
  82. 12.1: Finite Sets
  83. 12.2: Properties of finite sets and their cardinality
  84. 12.3: Relative Sizes of Sets
  85. 12.4: Counting elements of finite sets with bijections
  86. 12.5: Activities
  87. 12.6: Exercises
  88. 13: Countable and uncountable sets
  89. 13.1: Basics and Examples
  90. 13.2: Properties
  91. 13.3: More about relative sizes of sets
  92. 13.4: Activities
  93. 14: Graphs
  94. 14.1: Basics and Examples
  95. 14.2: Properties of Graphs
  96. 14.3: Adding Information to Graphs
  97. 14.4: Important Examples
  98. 14.5: Activities
  99. 14.6: Exercises
  100. 15: Paths and connectedness
  101. 15.1: Motivation
  102. 15.2: Walks, trails, and paths
  103. 15.3: Connected Vertices, Graphs, and Components
  104. 15.4: Articulation vertices, bridges, and edge connectivity
  105. 15.5: Activities
  106. 15.6: Exercises
  107. 16: Trees and searches
  108. 16.1: Motivation
  109. 16.2: Basics
  110. 16.3: Identifying Trees
  111. 16.4: Depth-first and breadth-first searches
  112. 16.5: Spanning Trees
  113. 16.6: Binary Searches
  114. 16.7: Activities
  115. 16.8: Exercises
  116. 17: Relations
  117. 17.1: Basics
  118. 17.2: Operations on Relations
  119. 17.3: Properties of Relations
  120. 17.4: Graphing Relations
  121. 17.5: Activities
  122. 17.6: Exercises
  123. 18: Equivalence relations
  124. 18.1: Motivation
  125. 18.2: Basics and Examples
  126. 18.3: Classes, partitions, and quotients
  127. 18.4: Important examples
  128. 18.5: Graph for an equivalence relation
  129. 18.6: Activities
  130. 18.7: Exercises
  131. 19: Partially ordered sets
  132. 19.1: Motivation
  133. 19.2: Definition and properties
  134. 19.3: Graph for a partial order
  135. 19.4: Total Orders
  136. 19.5: Maximal/minimal Elements
  137. 19.6: Topological Sorting
  138. 19.7: Activities
  139. 19.8: Exercises
  140. 20: Counting
  141. 20.1: Motivation
  142. 20.2: Addition and subtraction rules
  143. 20.3: Multiplication Rule
  144. 20.4: Division Rule
  145. 20.5: Pigeonhole Principle
  146. 20.6: Activities
  147. 20.7: Exercises
  148. 21: Permutations
  149. 21.1: Factorials
  150. 21.2: Definition
  151. 21.3: Counting Permutations
  152. 21.4: Permutations of Subsets
  153. 21.5: Activities
  154. 22: Combinations
  155. 22.1: Motivation
  156. 22.2: Basics
  157. 22.3: Applications
  158. 22.4: Properties
  159. 22.5: Activities
  160. 22.6: Exercises
  161. 23: Binomial and multinomial coefficients
  162. 23.1: Bionomial Coefficients
  163. 23.2: Multinomial Coefficients
  164. 23.3: Applications
  165. 23.4: Exercises
  166. Back Matter
  167. Index
  168. Glossary
  169. Detailed Licensing