Learn computing fundamentals, programming, algorithms, systems, and software engineering.
Discrete mathematics is the study of structures that are separate and countable — whole objects rather than continuous quantities. While calculus studies smooth change, discrete mathematics studies sets, logic, graphs, and counting. It is the natural language of computer science because computers themselves deal in discrete values: bits, integers, and finite structures. This lesson introduces the core ideas: propositional logic and truth tables, Boolean algebra and De Morgan’s laws, sets and their operations, basic combinatorics, a first look at graphs, and how mathematicians prove that a claim is actually true. Each of these reappears constantly in algorithms, programming, databases, networks, and cryptography. The goal is not to memorize rules but to learn how computer scientists reason precisely about truth, structure, and correctness.
Discrete means made of distinct, separate parts. The integers 0, 1, 2, ... are discrete; the real number line is continuous. Computers are discrete machines, so they use discrete mathematics.
A proposition is a statement that is either true or false — never both. Logical operators combine propositions into new ones.
| Operator | Symbol | Meaning |
|---|---|---|
| AND | ∧ | True only when both are true |
| OR | ∨ | True when at least one is true |
| NOT | ¬ | Flips true to false and back |
| Implication | → | If A then B |
| Biconditional | ↔ | A if and only if B |
A truth table lists every possible combination of inputs and shows the result. It is the reliable way to check whether a logical expression does what you think.
| A | B | A AND B | A OR B |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | F |
De Morgan’s laws show how to move a NOT inside parentheses. They are essential for simplifying logic and for writing correct conditions in code.
Example: "It is not true that (it is raining AND cold)" is the same as "(it is not raining) OR (it is not cold)."
A set is an unordered collection of distinct elements. Sets are the foundation of databases, collections in programming, and many algorithms.
| Operation | Notation | Meaning |
|---|---|---|
| Union | A ∪ B | Everything in A or B |
| Intersection | A ∩ B | Only what is in both A and B |
| Difference | A − B | In A but not in B |
| Complement | A′ | Everything not in A |
Counting is the difference between permutations and combinations: in a permutation order matters; in a combination it does not.
Choosing a president, VP, and secretary from 5 people is a permutation (5×4×3 = 60). Choosing 3 members for a committee is a combination (C(5,3) = 10).
A graph is a set of vertices connected by edges. Graphs model networks, maps, social connections, and dependencies.
A proof is a logical argument that establishes a claim is always true. Computer scientists use a few standard techniques to reason about correctness.
| Technique | Idea |
|---|---|
| Direct proof | Show the claim follows straight from the assumptions |
| Contradiction | Assume the opposite and show it leads to nonsense |
| Contrapositive | Prove the equivalent "not B implies not A" |
| Induction | Prove a base case, then the next case from the previous |
Python’s and/or/not map directly to logical AND/OR/NOT, and set objects provide union, intersection, and difference.
For every combination of A and B, not (A and B) equals (not A) or (not B).
True True True True False True False True True False False True
How many 3-person committees from 5 people?
10