maths.free › Discrete Math & Logic

Discrete Math & Logic

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.

გაკვეთილებიComment

Introductory Truth tables And, or, not, implies — and tautologies. 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

Chapters from Levin, Discrete Mathematics: An Open Introduction

Every section of the book, condensed into a lesson with its own practice problems.

1. Introduction and Preliminaries

What is Discrete Mathematics?Discrete Structures

2. Logic and Proofs

Mathematical StatementsImplicationsRules of LogicProofsProofs about Discrete StructuresChapter Summary

5. Sequences

Describing SequencesRate of GrowthPolynomial SequencesExponential SequencesProof by InductionStrong InductionChapter Summary

6. Discrete Structures Revisited

SetsFunctions

7. Additional Topics

Generating FunctionsIntroduction to Number Theory

Chapters from OpenStax Contemporary Mathematics

Every section of the book, condensed into a lesson with its own practice problems.

2. Logic

Statements and QuantifiersCompound StatementsConstructing Truth TablesTruth Tables for the Conditional and BiconditionalEquivalent StatementsDe Morgan’s LawsLogical Arguments

11. Voting and Apportionment

Voting MethodsFairness in Voting MethodsStandard Divisors, Standard Quotas, and the Apportionment ProblemApportionment MethodsFairness in Apportionment Methods

13. Math and...

Math and ArtMath and the EnvironmentMath and MedicineMath and MusicMath and Sports

Symbols used here

n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

Questions people ask

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.

სხვა კალათა

＋ 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∞ Frontiers