Die Druckversion wird nicht mehr unterstützt und kann Darstellungsfehler aufweisen. Bitte aktualisiere deine Browser-Lesezeichen und verwende stattdessen die Standard-Druckfunktion des Browsers.

Discrete Mathematics

Introduction

Discrete mathematics studies mathematical structures that are finite or countable rather than continuously varying. It supplies a language for reasoning about objects such as propositions, sets, integers, sequences, graphs, trees, algorithms, and finite-state systems. For university students in mathematics, computer science, engineering, data science, and related fields, it is especially important because digital systems are built from discrete states and because many algorithmic questions are naturally expressed through logic, counting, relations, and graphs.

In this aiMOOC, you learn how to define discrete structures precisely, prove claims about them, count possibilities without double-counting, model networks, reason recursively, and connect theory with computation. The central habit is rigorous reasoning: a plausible pattern is not yet a proof, and a correct result should follow from explicit definitions and justified steps.

The course is designed at university level. You should be comfortable with basic algebra and symbolic notation, but the essential concepts are introduced from first principles. The emphasis is not only on calculating an answer but also on explaining why the method is valid and when it can be transferred to a new problem.

The MIT OpenCourseWare lecture above introduces proofs in a discrete mathematics course for computer science. As you watch, notice how definitions, assumptions, and logical steps are separated from intuition.

Learning Goals

By the end of the course, you should be able to formulate propositions and quantified statements, construct and critique proofs, work fluently with sets and functions, classify relations, use counting principles, solve basic recurrence relations, reason with modular arithmetic, analyze graphs and trees, and explain how Boolean logic and finite-state models support computation.

You should also be able to choose an appropriate method. For example, a universal statement about positive integers may suggest induction, a problem involving overlapping categories may suggest inclusion-exclusion, and a routing problem may be modeled as a graph. Choosing the model is often as important as carrying out the calculation.

Logic and Mathematical Reasoning

Propositions and Connectives

A proposition is a declarative statement that is either true or false. Propositional logic combines propositions using connectives such as negation, conjunction, disjunction, implication, and biconditional. If propositions are represented by letters such as $p$ and $q$ , a truth table records the truth value of a compound proposition for every possible assignment of truth values to its components.

Logical equivalence means that two compound propositions have the same truth value under every assignment. Important equivalences include De Morgan's laws, double negation, distributive laws, and the equivalence between an implication and its contrapositive. These laws allow you to simplify logical expressions and to transform a statement into a form that may be easier to prove.

A useful discipline is to distinguish syntax from semantics. Syntax concerns whether an expression is well formed; semantics concerns what the expression means and when it is true. This distinction later reappears in formal languages, programming languages, and automated reasoning.

Predicates and Quantifiers

A predicate becomes a proposition when its variables are assigned values or quantified. The universal quantifier $\forall$ means “for every,” while the existential quantifier $\exists$ means “there exists.” The order of quantifiers matters. The statement $\forall x \exists y P (x, y)$ can mean something very different from $\exists y \forall x P (x, y)$ .

Negating quantified statements requires both changing the quantifier and negating the predicate. Thus the negation of “for every $x$ , $P (x)$ ” is “there exists an $x$ for which $P (x)$ is false.” This rule is essential when constructing counterexamples and contradiction proofs.

Proof Methods

A direct proof begins from the assumptions and derives the desired conclusion. A proof by contraposition proves an implication by establishing its logically equivalent contrapositive. A proof by contradiction assumes the negation of the desired conclusion and derives an impossibility. To disprove a universal statement, a single valid counterexample is sufficient.

Mathematical induction proves a statement indexed by the natural numbers by establishing a base case and an inductive step. In the inductive step, you assume the statement for a suitable earlier case and use that assumption to prove the next case. Strong induction allows the proof of the next case to rely on all earlier cases in the induction range.

The domino analogy is useful but incomplete: the base case corresponds to starting the chain, while the inductive implication guarantees that whenever one required case is established, the next one follows. A valid proof still requires a precise statement of the induction hypothesis and a logically complete step.

When reading or writing a proof, identify the claim, assumptions, definitions, intermediate statements, and conclusion. Ask whether each inference is justified. Testing small cases can reveal a false conjecture, but successful tests do not replace proof.

Sets, Functions, and Relations

Sets and Operations

A set is a collection of distinct objects. If $A$ and $B$ are sets, their union $A \cup B$ contains elements in at least one of the sets, their intersection $A \cap B$ contains elements common to both, and their difference $A ∖ B$ contains elements in $A$ but not in $B$ . The complement of a set is defined relative to a specified universe.

The Cartesian product $A \times B$ is the set of ordered pairs $(a, b)$ with $a \in A$ and $b \in B$ . The power set $𝒫 (A)$ contains every subset of $A$ . If a finite set has $n$ elements, then its power set has $2^{n}$ elements because each element can independently be included or excluded.

Set identities can be proved elementwise. To prove two sets are equal, a standard strategy is to prove mutual inclusion: every element of the first set belongs to the second, and every element of the second belongs to the first.

Functions

A function assigns each element of its domain exactly one output in its codomain. An injective function never maps two distinct domain elements to the same output. A surjective function reaches every element of the codomain. A bijection is both injective and surjective.

Bijections are especially important in discrete mathematics because they establish equal cardinalities and create counting arguments. If you can place the objects in one set in one-to-one correspondence with objects in a second set, then the two sets have the same cardinality, even if their descriptions look very different.

Relations and Partial Orders

A binary relation on a set $A$ is a subset of $A \times A$ . Important properties include reflexivity, symmetry, antisymmetry, and transitivity. An equivalence relation is reflexive, symmetric, and transitive; it partitions a set into equivalence classes. A partial order is reflexive, antisymmetric, and transitive; it represents a consistent notion of ordering that need not compare every pair of elements.

A Hasse diagram suppresses loops and edges implied by transitivity to display the structure of a finite partially ordered set. Divisibility provides a standard example: one integer can precede another when it divides the other.

Counting and Combinatorics

Sum and Product Rules

The sum rule applies when a task can be completed in one of several mutually exclusive ways: add the numbers of possibilities. The product rule applies when a procedure consists of successive choices: multiply the numbers of options at each stage. Many counting problems can be solved by first describing the objects as sequences of decisions and then applying these two rules carefully.

A permutation counts ordered arrangements; a combination counts selections where order does not matter. For $n$ distinct objects, there are $n!$ permutations. The number of ways to choose $k$ objects from $n$ without regard to order is the binomial coefficient $(\binom{n}{k})$ .

Pascal's triangle displays binomial coefficients and makes the identity $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ visually apparent. The same coefficients occur in the expansion of $(x + y)^{n}$ , linking algebraic expansion with combinatorial selection.

Inclusion-Exclusion and the Pigeonhole Principle

When categories overlap, simply adding their sizes double-counts the intersection. For two finite sets, $| A \cup B | = | A | + | B | - | A \cap B |$ . The inclusion-exclusion principle generalizes this correction to more sets by alternating sums of intersection sizes.

The pigeonhole principle says that if more objects than containers are distributed among the containers, then some container receives at least two objects. Its generalized form gives a lower bound on the maximum occupancy. Although the principle is simple, it can prove non-obvious existence statements without identifying the object that must exist.

Recursion and Recurrence Relations

A recursive definition describes an object in terms of smaller instances of the same kind. A recurrence relation specifies terms of a sequence using earlier terms together with enough initial conditions to determine the sequence.

The Fibonacci sequence, for example, satisfies $F_{n} = F_{n - 1} + F_{n - 2}$ for suitable indices with initial values such as $F_{0} = 0$ and $F_{1} = 1$ . The recurrence describes a local rule, while a closed form attempts to express $F_{n}$ directly as a function of $n$ .

For linear homogeneous recurrences with constant coefficients, a characteristic equation can often be used to find a closed form. In algorithm analysis, recurrences also describe running times of recursive procedures. The mathematical task is then to derive or bound the growth of the sequence.

Recursive definitions and induction are natural partners: recursive structure tells you how larger objects are built from smaller ones, while structural or ordinary induction can prove properties that are preserved by this construction.

Number Theory and Modular Arithmetic

Divisibility is written $a ∣ b$ when there is an integer $k$ such that $b = a k$ . A prime is an integer greater than one whose positive divisors are only one and itself. The greatest common divisor of two integers can be computed efficiently with the Euclidean algorithm, which repeatedly replaces a pair by a smaller remainder pair.

Two integers are congruent modulo $m$ when they leave the same remainder upon division by $m$ . Equivalently, $a \equiv b (\mod m)$ means that $m$ divides $a - b$ . Congruence respects addition and multiplication, allowing large computations to be reduced to smaller residue classes.

Modular arithmetic models cyclic phenomena such as clocks, checksums, hash-table indexing, and many cryptographic constructions. In public-key cryptography such as RSA, number-theoretic ideas including modular exponentiation and properties of primes are central. At this level, the goal is to understand the mathematics of congruence and inverses rather than to treat a simplified classroom example as a secure implementation.

Graph Theory and Trees

Graphs as Models

A graph consists of vertices and edges. In an undirected graph, an edge connects two vertices without orientation; in a directed graph, an edge has a direction. Graphs can model communication networks, roads, dependencies, social links, molecular structures, and state transitions.

The degree of a vertex in an undirected graph is the number of incident edges. The handshake lemma states that the sum of all vertex degrees equals twice the number of edges. Consequently, every finite undirected graph has an even number of odd-degree vertices.

Euler's analysis of the Seven Bridges of Königsberg helped establish graph-theoretic reasoning: the physical geometry can be abstracted to vertices and edges while preserving the connectivity information relevant to the problem. An Euler trail uses every edge exactly once; an Euler circuit returns to its starting point.

Paths, Connectivity, Coloring, and Representation

A walk may repeat vertices and edges; a path is typically taken to have no repeated vertices. Connectivity asks whether vertices can reach one another through paths. A cycle is a closed path. In weighted graphs, shortest-path and minimum-spanning-tree problems attach numerical costs to edges and seek globally efficient structures.

Graph coloring assigns labels such as colors to vertices so that adjacent vertices satisfy a constraint. Coloring models scheduling conflicts, frequency assignment, register allocation, and other resource-separation problems.

Graphs can be represented by adjacency lists or adjacency matrices. Representation affects algorithmic cost: a sparse graph often benefits from adjacency lists, while a matrix provides constant-time adjacency tests at the cost of storing all possible vertex pairs.

Trees

A tree is a connected undirected graph with no cycles. Equivalent characterizations are extremely useful: a finite tree with $n$ vertices has exactly $n - 1$ edges, and there is a unique simple path between every pair of vertices.

Rooted trees impose a parent-child hierarchy. Binary trees restrict each node to at most two children. Trees appear in search algorithms, file systems, syntax analysis, decision procedures, hierarchical data, and spanning-tree constructions.

Boolean Algebra and Finite-State Models

Boolean algebra treats values such as true and false, or one and zero, together with operations corresponding to logical connectives. The same algebra underlies digital logic. An AND gate realizes conjunction, an OR gate realizes disjunction, and a NOT gate realizes negation.

A finite-state machine has a finite set of states and transition rules. It can model a protocol, controller, parser component, game position, or sequential circuit. A deterministic finite automaton processes an input string one symbol at a time and updates its state according to a transition function.

The key modeling insight is that a complicated process can sometimes be analyzed by identifying only the information that must be remembered at each step. In the automaton above, states encode parity information about symbols already read rather than storing the entire input history.

A Strategy for Solving Discrete Problems

Start by identifying the objects, assumptions, and exact question. Translate informal language into a mathematical structure such as a set, function, relation, recurrence, or graph. Work through small cases to test your interpretation, but distinguish experimental evidence from proof. Choose a method that matches the structure: bijection for equal cardinalities, induction for recursively indexed claims, inclusion-exclusion for overlaps, modular arithmetic for cyclic constraints, or graph algorithms for connectivity and optimization.

Then justify each step and test boundary cases. If a result is surprising, solve the problem in a second way when possible. In counting, alternative derivations can expose overcounting; in proof, a contrapositive may reveal the essential implication; in graph problems, changing the representation may simplify the algorithm.

Applications and Connections

Discrete mathematics provides foundations for algorithm design, data structures, databases, computer networks, cryptography, compilers, formal verification, scheduling and optimization, and error-correcting codes. The same concepts also appear in economics, linguistics, biology, and social science whenever relationships, finite configurations, or combinatorial possibilities matter.

The transfer skill is modeling. A university exercise may mention committees, strings, bridges, processors, courses, or encrypted messages, but the underlying mathematical structure may be the same. Learning to recognize that structure lets you reuse a small collection of powerful ideas across many fields.

Interactive Tasks

Quiz: Test Your Knowledge

Which method is designed to prove a statement for every natural number by establishing a base case and an inductive step? (Mathematical induction) (!Contradiction) (!Enumeration) (!Differentiation)

Which type of function is both injective and surjective? (Bijection) (!Predicate) (!Recurrence) (!Partition)

Which relation property requires that if a is related to b and b is related to c then a is related to c? (Transitivity) (!Symmetry) (!Reflexivity) (!Antisymmetry)

Which counting principle corrects for elements counted in overlapping sets? (Inclusion exclusion) (!Product rule) (!Pigeonhole principle) (!Mathematical induction)

What does the pigeonhole principle guarantee when more objects than containers are used? (Some container has multiple objects) (!Every container is empty) (!Every object has its own container) (!All containers have equal size)

What is true of every finite tree? (It has one fewer edge than vertices) (!It contains a cycle) (!Every vertex has degree two) (!It is a complete graph)

Which graph concept describes a route that uses every edge exactly once? (Euler trail) (!Vertex coloring) (!Complete graph) (!Independent set)

What does congruence modulo m compare? (Remainders under division) (!Lengths of vectors) (!Areas of polygons) (!Derivatives of functions)

Which structure specifies sequence terms using earlier terms? (Recurrence relation) (!Truth table) (!Power set) (!Adjacency list)

Which representation records graph adjacency in a table of vertex pairs? (Adjacency matrix) (!Hasse diagram) (!Venn diagram) (!Truth table)

Memory Game

Bijection	A function that is both one-to-one and onto
Contrapositive	A logically equivalent reversal and negation of an implication
Bipartite graph	A graph whose vertices can be split into two parts with edges only across the parts
Recurrence relation	A rule defining sequence terms from earlier terms
Congruence	Equality of remainders with respect to a modulus
Invariant	A property that remains unchanged during a process

Drag and Drop

Match the correct terms.	Topic
Proof by contradiction	Assume the desired conclusion is false and derive an impossibility
Mathematical induction	Prove a base case and then prove that one valid case forces the next
Inclusion exclusion	Correct a count when categories overlap
Breadth first search	Explore an unweighted graph layer by layer from a starting vertex
Euclidean algorithm	Repeatedly use remainders to compute a greatest common divisor

Match each method with the description that best captures when or how it is used. After matching, explain one case in which choosing the wrong method would make a problem harder.

Crossword Puzzle

Bijection	What one-word term names a function that is both injective and surjective?
Induction	What proof method uses a base case and an inductive step?
Graph	What structure consists of vertices connected by edges?
Recurrence	What one-word term names a rule that defines sequence terms from earlier terms?
Congruence	What modular arithmetic relation means two integers have the same remainder?
Tautology	What proposition is true under every assignment of truth values?

LearningApps

Cloze Text

A statement that is true for every truth assignment is a

. A one-to-one and onto function is a

. A relation that is reflexive, symmetric, and transitive is an

. The principle that corrects double-counting among overlapping sets is

. A proof method that moves from a base case through an inductive step is

. A connected graph with no cycles is a

. Arithmetic based on remainders uses

. A rule that defines sequence terms from earlier terms is a

. A property preserved throughout an algorithmic process is an

. A graph route that uses every edge exactly once is an

.

Open-Ended Tasks

Easy

Truth table laboratory: Choose two propositions from an everyday university context, build truth tables for at least three compound statements, and explain which pairs are logically equivalent.
Set operations poster: Create a visual poster showing union, intersection, difference, and complement for three sets, and write a short explanation of one De Morgan law in set notation.
Graph walk study: Draw a graph of locations on your campus or in a familiar public place, mark several walks and paths, and explain the difference between them.
Counting diary: Record four real situations involving choices during one day and identify whether the sum rule, product rule, permutations, or combinations best models each situation.

Standard

Proof workshop: Prove one implication directly and again by contraposition, then compare which proof exposes the mathematical structure more clearly.
Recurrence experiment: Implement or tabulate a recursively defined sequence, compare recursive and direct computation for several inputs, and explain the growth pattern you observe.
Network coloring project: Model a scheduling or resource-conflict problem as a graph, propose a vertex coloring, and justify why adjacent conflicts receive different resources.
Relation classifier: Interview classmates about a relation arising in courses, prerequisites, collaboration, or classification, formalize the relation, and test whether it is reflexive, symmetric, antisymmetric, and transitive.

Advanced

Algorithm invariant investigation: Choose an iterative algorithm, identify a plausible invariant, test it on examples, and write a proof showing why it holds before and after every iteration.
RSA mathematics model: Build a small non-secure classroom model of modular arithmetic used in public-key cryptography, explain modular inverses and exponentiation, and state clearly why toy parameters are not secure.
Graph optimization case study: Visit or research a real transport, communication, or logistics network, formulate a shortest-path or spanning-tree question, solve a simplified instance, and evaluate the assumptions of your model.
Discrete mathematics explainer video: Produce a five-minute teaching video that connects one theorem from the course with a computing application, including a worked example, a visual representation, and a proof or correctness argument.

Learning Assessment

Model selection assessment: Given a new problem involving schedules, passwords, and network routes, identify the appropriate discrete structures for each part and justify why competing models are less suitable.
Proof critique assessment: Analyze a flawed proof, locate the first unjustified inference, repair the argument, and explain why checking examples alone cannot establish the original universal claim.
Counting transfer assessment: Solve an overlapping-category counting problem in two different ways, reconcile the answers, and explain exactly where overcounting would occur in a naive solution.
Graph reasoning assessment: Model a dependency system as a directed graph, determine whether cycles create a problem, and propose a valid ordering or explain why none exists.
Recurrence analysis assessment: Derive a recurrence from a recursive process, compute initial terms, propose a growth estimate or closed form, and justify the connection between the process and the recurrence.
Modular arithmetic assessment: Use congruence to solve a cyclic scheduling or checksum problem, justify every transformation, and verify the result by substitution.
Synthesis assessment: Compare induction, invariants, and recursion as three ways of reasoning about repeated structure, and give one original example where at least two of them interact.

Evidence of Learning

Evidence type	What strong evidence looks like
Knowledge	You define core structures precisely and distinguish related concepts such as implication and equivalence, injection and surjection, walk and path, and tree and general graph.
Proof skill	You construct valid direct, contrapositive, contradiction, and induction arguments and can diagnose missing assumptions or unjustified steps.
Modeling skill	You translate real or computational situations into sets, relations, recurrences, graphs, Boolean expressions, or finite-state models and explain why the abstraction preserves the relevant information.
Computational product	You create correct truth tables, counting models, graph representations, recurrence tables, modular calculations, or small programs and document how the output supports a mathematical conclusion.
Communication product	You present a mathematical argument in clear English with definitions, notation, diagrams, examples, and a conclusion that another learner can check.
Transfer achievement	You recognize when a familiar method applies in an unfamiliar context and justify the transfer rather than relying only on surface similarities.

OERs on the Topic

For an open university-level treatment connected to computer science, explore MIT OpenCourseWare: Mathematics for Computer Science. Its materials connect proofs, sets, functions, relations, graphs, number theory, counting, and discrete probability.

The Wikimedia Commons files embedded throughout this aiMOOC can be opened on their file-description pages to inspect authorship and licensing information before reuse or adaptation.

Linked Learning Areas

Discrete Mathematics

Discrete mathematics connects abstract reasoning with practical problem solving. Logic supports proofs and digital circuits; sets, functions, and relations organize data and structure; combinatorics counts possible configurations; recurrences model repeated processes; number theory supports modular computation; graphs and trees model networks and hierarchies; and finite-state systems formalize computation with limited memory. Together, these areas form a foundation for advanced study in mathematics and computer science.