Elementary Foundations: An Introduction to Topics in Discrete Mathematics

Combinatorics and Discrete Mathematics Mathematics

Author: Jeremy Sylvestre
Publisher: University of Alberta Augustana
Source: LibreTexts
License: GNU FDL
Language: EN
Category: Basic Sciences

Read online Download PDF (open licence)

Contents· 160 sections

01: Symbolic language
1.01: Statements
1.02: Converting language to symbols
1.03: Logical Analysis
1.04: Tautologies and contradictions
1.05: Activities
1.06: Exercises
02: Logical equivalence
2.01: Equivalence
2.02: Propositional Calculus
2.03: Converse Inverse and Contrapositive
2.04: Activities
2.05: Exercises
03: Boolean algebra
3.01: Boolean Polynomials
3.02: Disjunctive Normal Form
3.03: Exercises
04: Predicate logic
4.01: Predicates and Quantifers
4.02: Manipulating quantified statements
4.03: Vacuously true statements
4.04: Activities
4.05: Exercises
05: Arguments
5.01: Basic
5.02: Standard Arguments
5.03: Substituting into an argument
5.04: Activities
06: Definitions and proof methods
6.01: Definitions
6.02: Common mathematical statements
6.03: Direct Proof
6.04: Reduction to Cases
6.05: Statements Involving Disjunction
6.06: Proving the contrapositive
6.07: Proof by counterexample
6.08: Proving biconditionals
6.09: Proof by Contradiction
6.10: Existence and Uniqueness
6.11: Activities
6.12: Exercises
07: Proof by mathematical induction
7.01: Principle of Mathematical Induction
7.02: An application to logic
7.03: Strong form of Mathematical Induction
7.04: Activities
08: Axiomatic systems
8.01: Basics and examples
8.02: Incompleteness of axiomatic systems
8.03: Exercises
09: Sets
9.01: Basics
9.02: Defining sets
9.03: Subsets and equality of sets
9.04: Complement union and intersection
9.05: Cartesian Product
9.06: Alphabets and words
9.07: Sets of sets
9.08: Activities
9.09: Exercises
10: Functions
10.01: Basics
10.02: Properties of Functions
10.03: Important Examples
10.04: Composition of functions
10.05: Inverses
10.06: Activities
10.07: Exercises
11: Recurrence and induction
11.01: Sequences
11.02: Recurrence Relations
11.03: Solving through Iteration
11.04: Inductive definitions
11.05: Activities
11.06: Exercises
12: Cardinality
12.01: Finite Sets
12.02: Properties of finite sets and their cardinality
12.03: Relative Sizes of Sets
12.04: Counting elements of finite sets with bijections
12.05: Activities
12.06: Exercises
13: Countable and uncountable sets
13.01: Basics and Examples
13.02: Properties
13.03: More about relative sizes of sets
13.04: Activities
14: Graphs
14.01: Basics and Examples
14.02: Properties of Graphs
14.03: Adding Information to Graphs
14.04: Important Examples
14.05: Activities
14.06: Exercises
15: Paths and connectedness
15.01: Motivation
15.02: Walks trails and paths
15.03: Connected Vertices Graphs and Components
15.04: Articulation vertices bridges and edge connectivity
15.05: Activities
15.06: Exercises
16: Trees and searches
16.01: Motivation
16.02: Basics
16.03: Identifying Trees
16.04: Depth-first and breadth-first searches
16.05: Spanning Trees
16.06: Binary Searches
16.07: Activities
16.08: Exercises
17: Relations
17.01: Basics
17.02: Operations on Relations
17.03: Properties of Relations
17.04: Graphing Relations
17.05: Activities
17.06: Exercises
18: Equivalence relations
18.01: Motivation
18.02: Basics and Examples
18.03: Classes partitions and quotients
18.04: Important examples
18.05: Graph for an equivalence relation
18.06: Activities
18.07: Exercises
19: Partially ordered sets
19.01: Motivation
19.02: Definition and properties
19.03: Graph for a partial order
19.04: Total Orders
19.05: Maximal minimal Elements
19.06: Topological Sorting
19.07: Activities
19.08: Exercises
20: Counting
20.01: Motivation
20.02: Addition and subtraction rules
20.03: Multiplication Rule
20.04: Division Rule
20.05: Pigeonhole Principle
20.06: Activities
20.07: Exercises
21: Permutations
21.01: Factorials
21.02: Definition
21.03: Counting Permutations
21.04: Permutations of Subsets
21.05: Activities
22: Combinations
22.01: Motivation
22.02: Basics
22.03: Applications
22.04: Properties
22.05: Activities
22.06: Exercises
23: Binomial and multinomial coefficients
23.01: Bionomial Coefficients
23.02: Multinomial Coefficients
23.03: Applications
23.04: Exercises