Discrete Structures

Mathematics

Author: Laurie Lacey
Publisher: SUNY Schenectady County Community College
Source: LibreTexts
Language: EN
Category: Basic Sciences

Read online Download PDF (open licence)

Contents· 112 sections

01: Introduction to Writing Proofs in Mathematics
1.01: Statements and Conditional Statements
1.02: Constructing Direct Proofs
1.S: Introduction to Writing Proofs in Mathematics (Summary)
02: Logical Reasoning
2.01: Statements and Logical Operators
2.02: Logically Equivalent Statements
2.03: Open Sentences and Sets
2.04: Quantifiers and Negations
2.05: Structures and Languages
2.5.01: Summing Up Looking Ahead
2.5.02: Naively
2.5.03: Languages
2.5.04: Terms and Formulas
2.5.05: Induction
2.5.06: Sentences
2.5.07: Structures
2.5.08: Truth in a Structure
2.5.09: Substitutions and Substitutability
2.5.10: Logical Implication
2.S: Logical Reasoning (Summary)
03: Constructing and Writing Proofs in Mathematics
3.01: Direct Proofs
3.02: More Methods of Proof
3.03: Proof by Contradiction
3.04: Using Cases in Proofs
3.05: The Division Algorithm and Congruence
3.06: Review of Proof Methods
3.S: Constructing and Writing Proofs in Mathematics (Summary)
04: Mathematical Induction
4.01: The Principle of Mathematical Induction
4.02: Other Forms of Mathematical Induction
4.03: Induction and Recursion
4.S: Mathematical Induction (Summary)
Supplementary Notes: Sequences, Definitions
Supplementary Notes: Sequences, Arithmetic and Geometric
Supplementary Notes: Recurrence Relations
05: Set Theory
5.01: Sets and Operations on Sets
5.02: Proving Set Relationships
5.03: Properties of Set Operations
5.04: Cartesian Products
5.05: Indexed Families of Sets
5.S: Set Theory (Summary)
06: Functions
6.01: Introduction to Functions
6.02: More about Functions
6.03: Injections Surjections and Bijections
6.04: Composition of Functions
6.05: Inverse Functions
6.06: Functions Acting on Sets
6.S: Functions (Summary)
07: Equivalence Relations
7.01: Relations
7.02: Equivalence Relations
7.03: Equivalence Classes
7.04: Modular Arithmetic
7.S: Equivalence Relations (Summary)
08: Topics in Number Theory
8.01: The Greatest Common Divisor
8.02: Prime Numbers and Prime Factorizations
8.03: Linear Diophantine Equations
8.S: Topics in Number Theory (Summary)
09: Finite and Infinite Sets
9.01: Finite Sets
9.02: Countable Sets
9.03: Uncountable Sets
9.S: Finite and Infinite Sets (Summary)
10: Graph Theory
10.01: Prelude to Graph Theory
10.02: Definitions
10.03: Planar Graphs
10.04: Coloring
10.05: Euler Paths and Circuits
10.06: Matching in Bipartite Graphs
10.07: Weighted Graphs and Dijkstra's Algorithm
10.08: Trees
10.09: Tree Traversal
10.10: Spanning Tree Algorithms
10.11: Transportation Networks and Flows
10.12: Data Structures for Graphs
10.E: Graph Theory (Exercises)
10.S: Graph Theory (Summary)
11: Counting
11.01: Additive and Multiplicative Principles
11.02: Binomial Coefficients
11.03: Combinations and Permutations
11.04: Combinatorial Proofs
11.05: Stars and Bars
11.06: Advanced Counting Using PIE
11.E: Counting (Exercises)
11.S: Counting (Summary)
12: Boolean Algebra
12.01: Posets Revisited
12.02: Lattices
12.03: Boolean Algebras
12.04: Atoms of a Boolean Algebra
12.05: Finite Boolean Algebras as n-tuples of 0's and 1's
12.06: Boolean Expressions
12.07: A Brief Introduction to Switching Theory and Logic Design
13: Monoids and Automata
13.01: Monoids
13.02: Free Monoids and Languages
13.03: Automata Finite-State Machines
13.04: The Monoid of a Finite-State Machine
13.05: The Machine of a Monoid
14: Group Theory and Applications
14.01: Cyclic Groups
14.02: Cosets and Factor Groups
14.03: Permutation Groups
14.04: Normal Subgroups and Group Homomorphisms
14.05: Coding Theory Group Codes