Collect distinct objects under a membership rule.
Set operations formalize overlap, exclusion and composition.
Side 129
Discrete Mathematics
Mathematics for countable structure: objects that can be enumerated, connected, arranged, related and reasoned about without relying on continuous change.
objects→relations→counting→structure→proof
04lenses
16working concepts
V0content
SS-1.0standard
Discrete systems begin with clearly defined collections and relations.
Sets, functions and relations provide the basic language for structured finite problems.
Specify which ordered pairs are connected.
Equivalence and order relations impose reusable structure on collections.
Map each input to an output.
Injective, surjective and bijective mappings encode different forms of correspondence.
Divide a set into nonoverlapping blocks.
Partitions appear in classification, equivalence and combinatorial counting.
Combinatorics asks how many configurations are possible.
The main difficulty is often avoiding double-counting while respecting constraints.
Multiply independent stages of choice.
Sequential decisions produce a product when each stage offers a fixed number of possibilities.
Count ordered arrangements.
Order matters when positions or sequence distinguish outcomes.
Count unordered selections.
Binomial coefficients capture subsets of fixed size.
Correct overlapping counts.
Alternating additions and subtractions recover the size of unions with overlap.
Graphs turn relationships into mathematical objects.
Vertices and edges model networks while preserving enough structure for formal questions about paths and connectivity.
Trace a sequence of adjacent edges.
Reachability and shortest paths become graph properties rather than narrative descriptions.
Ask whether parts of the graph can reach one another.
Cuts reveal vulnerable bridges and decomposable structure.
Count local connections.
Degree distributions summarize local network structure without fully describing global organization.
Connect all vertices without cycles.
Trees give minimal connected structures and support recursive algorithms.
Discrete mathematics rewards constructive and combinatorial proof.
Proof techniques often mirror the finite structure of the object being studied.
Prove a base case and a recursive step.
Induction is especially natural for sequences, trees and recursively defined objects.
Assume the negation and derive impossibility.
This is powerful when direct construction is awkward.
More objects than containers force collision.
A simple counting principle can prove surprisingly strong existence claims.
Track a property that cannot change.
Invariants reveal impossible transitions and constrain algorithms or games.
Discrete mathematics is the grammar of finite and countable systems. Its methods connect logic, algorithms, networks, probability and computation by making combinatorial structure explicit.