Matemática Discreta

Read and build compound statements, truth tables, quantifiers and valid arguments.

1. Statements and Connectives
2. Truth Tables
3. The Conditional and the Biconditional
4. Logical Equivalence and De Morgan's Laws
5. Quantifiers
6. Negating Quantified Statements
7. Nested Quantifiers
8. Valid Arguments and Rules of Inference

Test claims with counterexamples, then set up direct, contrapositive, case-by-case and contradiction arguments.

1. Disproving with a Counterexample
2. Direct Proof
3. Proof by Contrapositive
4. Proof by Cases
5. Proof by Contradiction

Describe collections precisely, combine them, and study functions between them.

1. Sets and Set-Builder Notation
2. Set Operations
3. Power Sets and Cartesian Products
4. Functions Between Sets
5. One-to-One and Onto Functions
6. Bijections and Inverse Functions

Describe how elements are related, sort them into classes, and put them in order.

1. Relations and Their Properties
2. Equivalence Relations and Partitions
3. Partial Orders and Hasse Diagrams

Count arrangements and selections without listing them: rules, complements, inclusion–exclusion, stars and bars, and pigeonholes.

1. The Sum and Product Rules
2. Counting the Complement
3. Inclusion–Exclusion
4. The Division Rule: Repeated Letters and Round Tables
5. Pascal's Identity and Counting Arguments
6. Lattice Paths and Binary Strings
7. Stars and Bars
8. The Pigeonhole Principle
9. Derangements

Prove statements for every whole number, set up and solve recurrence relations, and compare how fast functions grow.

1. Induction for Divisibility and Inequalities
2. Strong Induction
3. Setting Up Recurrence Relations
4. Solving Recurrences by Unrolling
5. Linear Recurrences with Distinct Roots
6. Linear Recurrences with a Repeated Root
7. Growth Rates and Big-O

Model connections with graphs: degrees, paths and circuits, trees, shortest routes, coloring and planarity.

1. Graphs, Degrees and the Handshake Lemma
2. Complete, Bipartite and Cycle Graphs
3. Walks, Paths, Cycles and Connectivity
4. Adjacency Matrices and Counting Walks
5. Graph Isomorphism
6. Euler Paths and Circuits
7. Hamilton Paths and Cycles
8. Trees
9. Minimum Spanning Trees
10. Shortest Paths with Dijkstra's Algorithm
11. Graph Coloring
12. Planar Graphs and Euler's Formula