Discrete Mathematics Cheat Sheet

Updated 2026-05-19

Next Topic: Divide and Conquer Algorithms Cheat Sheet

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. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Propositional Logic — Connectives and Truth ValuesTable 2: Logical Equivalence LawsTable 3: Predicate Logic and QuantifiersTable 4: Set Theory — Operations and LawsTable 5: Relations — Types and PropertiesTable 6: Functions — Types and PropertiesTable 7: Proof MethodsTable 8: Mathematical InductionTable 9: Counting PrinciplesTable 10: Permutations and CombinationsTable 11: Sequences, Series, and Sigma NotationTable 12: Recurrence RelationsTable 13: Number TheoryTable 14: Discrete ProbabilityTable 15: Graph Theory FundamentalsTable 16: Generating Functions

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
Negation (NOT)	$\neg p$	• Flips the truth value • $\neg p$ is true when $p$ is false
Conjunction (AND)	$p \wedge q$	True only when both $p$ and $q$ are true.
Disjunction (OR)	$p \vee q$	True when at least one of $p$ or $q$ is true.
Exclusive Or (XOR)	$p \oplus q$	True when $p$ and $q$ have different truth values.
Implication (IF…THEN)	$p \to q$	• False only when $p$ is true and $q$ is false • false premise implies anything.
Biconditional (IFF)	$p \leftrightarrow q$	• True when $p$ and $q$ have the same truth value • equivalent to $(p \to q) \wedge (q \to p)$ .

Table 1: Propositional Logic — Connectives and Truth Values

Connective	Example	Description
Negation (NOT)	$\neg p$	• Flips the truth value • $\neg p$ is true when $p$ is false
Conjunction (AND)	$p \wedge q$	True only when both $p$ and $q$ are true.
Disjunction (OR)	$p \vee q$	True when at least one of $p$ or $q$ is true.
Exclusive Or (XOR)	$p \oplus q$	True when $p$ and $q$ have different truth values.
Implication (IF…THEN)	$p \to q$	• False only when $p$ is true and $q$ is false • false premise implies anything.
Biconditional (IFF)	$p \leftrightarrow q$	• True when $p$ and $q$ have the same truth value • equivalent to $(p \to q) \wedge (q \to p)$ .