maths.free › Discrete Math & Logic
Discrete Math & Logic
Counting, logic, truth tables, sets and proof.
Zvidzidzo
truth table of p and q
Core
Sums and induction
Closed forms for sums, and how induction proves them.
sum of k for k = 1 to n
Core
Proof by induction
Base case, inductive step, strong induction, and the well-ordering principle.
sum of k for k = 1 to n
Core
Algorithms and growth of functions
Big-O notation, comparing growth rates, and what "efficient" means.
limit of (2^n)/(n!) as n -> oo
Introductory
Predicate logic and quantifiers
Predicates, "for all" and "there exists", negating quantified statements, and why the order of quantifiers matters.
truth table of not (p and q) iff (not p or not q)
Core
Direct proof, contrapositive and contradiction
The three basic ways to prove an implication, when to reach for each, and how to write the proof.
truth table of (p -> q) iff (not q -> not p)
Core
Strong induction and the well-ordering principle
Assuming every earlier case, recursive definitions, and the least-element principle behind all induction.
fib(20)
Core
Relations: equivalence relations and partial orders
Reflexive, symmetric, antisymmetric and transitive relations; equivalence classes and partitions; partial orders and Hasse diagrams.
-7 mod 3
Core
Functions and cardinality
Injective, surjective and bijective functions; counting functions between finite sets; countable and uncountable sets.
5^3
Introductory
Counting: rules, choices and bijections
The sum and product rules, permutations and combinations, stars and bars, and counting one set by matching it with another.
how many ways to choose 3 from 10
Core
The pigeonhole principle
If more objects than boxes, two share a box; the generalised form with ceilings; and how to choose the boxes.
ceiling(25/6)
Core
Solving linear recurrence relations
Setting up recurrences, the characteristic equation, repeated roots, and non-homogeneous terms.
solve r^2 - 5r + 6 = 0
Introductory
Graphs: degrees, paths and connectivity
Vertices and edges, the handshake lemma, walks, paths and cycles, connected components, and the adjacency matrix.
7 choose 2
Core
Trees and spanning trees
Characterisations of trees, why a tree has n - 1 edges, rooted and binary trees, spanning trees and how to count them.
det [[3,-1,-1],[-1,3,-1],[-1,-1,3]]
Core
Euler and Hamilton paths
Walks using every edge once, Euler's degree condition, walks visiting every vertex once, and why the second is so much harder.
6!/2
Core
Graph colouring
Proper colourings, chromatic number, bipartite graphs, greedy colouring and the chromatic polynomial.
expand k*(k-1)*(k-2)
Core
Boolean algebra and logic circuits
The laws of Boolean algebra, sum-of-products form, simplification, and building adders from gates.
truth table of (p and q) or (not p and r)
Core
Finite automata and regular languages
Deterministic and nondeterministic automata, regular expressions, the subset construction and the pumping lemma.
fib(12)
Advanced
Asymptotic analysis, recursion trees and the master theorem
Big O, Omega and Theta, counting steps with sums, divide-and-conquer recurrences, recursion trees and the master theorem.
limit of (n log n)/n^2 as n -> oo
Advanced
Decision problems, satisfiability and reductions
Decision problems, polynomial time, certificates and the class NP, Boolean satisfiability, and what a reduction proves.
truth table of (p or q) and (not p or r) and (not q or not r)
The mathematics of the finite and the exact: how many ways, which statements follow from which, and what a proof actually needs. Truth tables are built row by row.
More lessons
Introduction and Preliminaries
Logic and Proofs
Logic
Sequences
Additional Topics
Voting and Apportionment
Discrete structures
Zvimwe zvezvidzidzo izvi zvakagadzirirwa kubva kune zvakavhurika zvinyorwa: Levin, Discrete Mathematics: An Open Introduction, OpenStax Contemporary Mathematics, Wikipedia. Ichi chidzidzo chinopa zita remutauro wayo uye chinoratidza chikonzero chekugadzirwa kwake.
Mazita anoshandiswa pano
Tinya chero chiratidzo kuti uone chirevo chakazara, vhidhiyo, uye kuti chii chinoreva chero chiratidzo.
Mabvunzo vanhu vanobvunza
What makes mathematics "discrete"?
It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.
How does a proof by induction work?
Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.
What order should I take these lessons in?
Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.
Is discrete mathematics the same as the maths of computer science?
Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.
Do I need calculus for this course?
No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.
Dzvanya kana kudhonza pane peji re solver: pazuva rimwe nerimwe, pfungwa, mhedzisiro yakachengetwa kusvika iwe unobvunza. _Kugadzirisa →
Other branches
＋ Arithmetic𝑥 Algebra△ Geometry∿ Trigonometryƒ Precalculusσ Statistics & Probability∫ Calculus⊞ Linear Algebraℕ Number Theoryẏ Differential Equations∇ Multivariable Calculusε Real Analysis⋔ Combinatorics & Graph Theory∈ Set Theory & Logic𝔾 Abstract Algebra𝑃 Probability Theory≈ Numerical Methodsℂ Complex Analysis◎ Topologyμ Measure Theory‖·‖ Functional Analysisκ Differential Geometryπ₁ Algebraic Topology→ Category Theory∂ Partial Differential Equations≋ Fluid Dynamics∞ Frontiers