Discrete mathematics is the branch of mathematics dealing with countable, distinct structures — integers, graphs, logic statements, and finite sets — rather than continuous quantities. It underpins nearly all of theoretical computer science: algorithm correctness proofs, cryptography, database design, and formal verification all rely on its tools. The key insight for practitioners is that discrete math is not a collection of unrelated topics — propositional logic, set theory, counting, and graph theory are deeply interconnected, and fluency in one area accelerates understanding of the others.
What This Cheat Sheet Covers
This topic spans 16 focused tables and 153 indexed concepts, 128 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Propositional Logic — Connectives and Truth Values
Propositions are statements with a definite truth value. These six logical connectives are the building blocks for compound statements and are foundational to Boolean circuits, database queries, and formal proofs.
| Connective | Example | Description | |
|---|---|---|---|
$\neg p$ | • Flips the truth value • $\neg p$ is true when $p$ is false | ||
$p \wedge q$ | True only when both $p$ and $q$ are true. | ||
$p \vee q$ | True when at least one of $p$ or $q$ is true. | ||
$p \oplus q$ | True when $p$ and $q$ have different truth values. | ||
$p \to q$ | • False only when $p$ is true and $q$ is false • false premise implies anything. | ||
$p \leftrightarrow q$ | • True when $p$ and $q$ have the same truth value • equivalent to $(p \to q) \wedge (q \to p)$. | ||
$p \vee \neg p$ | Compound proposition that is always true regardless of variable values. | ||
$p \wedge \neg p$ | Compound proposition that is always false. | ||
$p \to q$ (neither always T/F) | A proposition that is neither a tautology nor a contradiction. | ||
$q \to p$ (of $p \to q$) | • Swaps hypothesis and conclusion • not logically equivalent to the original | ||
$\neg q \to \neg p$ (of $p \to q$) | • Negates and swaps • logically equivalent to the original implication | ||
$\neg p \to \neg q$ (of $p \to q$) | • Negates both sides without swapping • logically equivalent to the converse, not the original |