Discrete Mathematics

Ivela emva: Algebra

Inkqubo

1. Logic and proof

   25 Iinkqubo
   ⊢What is Discrete Mathematics?⊢Discrete Structures⊢Discrete mathematics⊢Truth tables⊢Mathematical Statements⊢Statements and Quantifiers⊢Compound Statements⊢Constructing Truth Tables⊢Truth Tables for the Conditional and Biconditional⊢Implications⊢Equivalent Statements⊢De Morgan’s Laws⊢Rules of Logic⊢Logical Arguments⊢Predicate logic and quantifiers⊢Proofs⊢Direct proof, contrapositive and contradiction⊢Proofs about Discrete Structures⊢Chapter Summary∈Propositional calculus∈Logical connective∈Truth table∈First-order logic∈Quantifier (logic)∈Predicate (mathematical logic)
   Ngena ukuze uthathe isifundo

2. Induction and sequences

   11 Iinkqubo
   ⊢Sums and induction⊢Proof by induction⊢Proof by Induction⊢Strong Induction⊢Strong induction and the well-ordering principle⊢Describing Sequences⊢Polynomial Sequences⊢Exponential Sequences⊢Chapter Summary∈Well-order∈Peano axioms
   Ngena ukuze uthathe isifundo

3. Sets, relations and functions

   20 Iinkqubo
   ⊢Sets⊢Relations: equivalence relations and partial orders⊢Functions⊢Functions and cardinality⊢Introduction to Number Theory⊢Cryptography∈Cartesian product∈Power set∈Binary relation∈Equivalence relation∈Partial order∈Function (mathematics)∈Injective function∈Surjective function∈Bijection∈Composite function∈Inverse function∈Cardinal number∈Countable set∈Uncountable set
   Ngena ukuze uthathe isifundo

4. Counting

   16 Iinkqubo
   ⊢Counting: rules, choices and bijections⊢The pigeonhole principle⊢Voting Methods⊢Fairness in Voting Methods⊢Standard Divisors, Standard Quotas, and the Apportionment Problem⊢Apportionment Methods⊢Fairness in Apportionment Methods⋔Enumerative combinatorics⋔Permutation⋔Combination⋔Binomial coefficient⋔Pascal's triangle⋔Pigeonhole principle⋔Inclusion–exclusion principle⋔Bijective proof⋔Double counting (proof technique)
   Ngena ukuze uthathe isifundo

5. Recursion and recurrence relations

   7 Iinkqubo
   ⊢Recursion⊢Recurrence relation⊢Solving linear recurrence relations⊢Generating Functions⋔Recurrence relation⋔Generating function⋔Catalan number
   Ngena ukuze uthathe isifundo

6. Graphs and trees

   18 Iinkqubo
   ⊢Graphs: degrees, paths and connectivity⊢Trees and spanning trees⊢Euler and Hamilton paths⊢Graph colouring⋔Graph theory⋔Graph (discrete mathematics)⋔Degree (graph theory)⋔Path (graph theory)⋔Cycle (graph theory)⋔Connectivity (graph theory)⋔Tree (graph theory)⋔Spanning tree⋔Eulerian path⋔Hamiltonian path⋔Bipartite graph⋔Planar graph⋔Graph coloring⋔Adjacency matrix
   Ngena ukuze uthathe isifundo

7. Boolean algebra and automata

   7 Iinkqubo
   ⊢Binary number⊢Boolean algebra⊢Boolean algebra and logic circuits⊢Formal language⊢Automata theory⊢Finite automata and regular languages∈Turing machine
   Ngena ukuze uthathe isifundo

8. Algorithms and complexity

   15 Iinkqubo
   ⊢Algorithms and growth of functions⊢Algorithm⊢Rate of Growth⊢Big O notation⊢Asymptotic analysis, recursion trees and the master theorem⊢Sorting algorithm⊢Computational complexity theory⊢Decision problems, satisfiability and reductions⊢Math and Art⊢Math and the Environment⊢Math and Medicine⊢Math and Music⊢Math and Sports∈Computability theory∈Halting problem
   Ngena ukuze uthathe isifundo

Ixabiso

Uvavanyo lweenkcukacha