Discrete Mathematics Cheatsheet

Set Theory

Basic Definitions

Set	A well-defined collection of distinct objects, considered as an object in its own right.
Element	An object in a set. Denoted by ∈ (e.g., x ∈ A means x is an element of set A).
Subset	A set A is a subset of B (A ⊆ B) if every element of A is also in B.
Proper Subset	A set A is a proper subset of B (A ⊂ B) if A ⊆ B and A ≠ B.
Universal Set (U)	The set containing all elements under consideration.
Empty Set (∅)	The set containing no elements. Also denoted by {}.

Set Operations

Union (∪)	A ∪ B = {x \| x ∈ A or x ∈ B}
Intersection (∩)	A ∩ B = {x \| x ∈ A and x ∈ B}
Difference (-)	A - B = {x \| x ∈ A and x ∉ B}
Complement (A’)	A’ = {x \| x ∈ U and x ∉ A}
Symmetric Difference (⊕)	A ⊕ B = (A - B) ∪ (B - A)
Cartesian Product (×)	A × B = {(a, b) \| a ∈ A and b ∈ B}

Set Identities

Identity Laws:
A ∪ ∅ = A
A ∩ U = A

Domination Laws:
A ∪ U = U
A ∩ ∅ = ∅

Idempotent Laws:
A ∪ A = A
A ∩ A = A

Complementation Law:
(A’)’ = A

Commutative Laws:
A ∪ B = B ∪ A
A ∩ B = B ∩ A

Associative Laws:
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C

Logic

Propositional Logic

Proposition	A declarative statement that is either true or false, but not both.
Conjunction (∧)	p ∧ q is true if both p and q are true; otherwise, it is false.
Disjunction (∨)	p ∨ q is true if either p or q (or both) are true; it is false only if both are false.
Negation (¬)	¬p is true if p is false, and false if p is true.
Implication (→)	p → q is false only when p is true and q is false; otherwise, it is true. Also called a conditional statement.
Biconditional (↔)	p ↔ q is true if p and q have the same truth value (both true or both false).

Logical Equivalences

De Morgan’s Laws:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Distributive Laws:
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

Implication Equivalence:
p → q ≡ ¬p ∨ q

Biconditional Equivalence:
p ↔ q ≡ (p → q) ∧ (q → p)

Commutative Laws:
p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p

Associative Laws:
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Predicate Logic

Predicate	A statement involving variables. P(x) is the predicate P at x.
Quantifiers	Symbols that express the extent to which a predicate is true over a range of elements.
Universal Quantifier (∀)	∀x P(x) means P(x) is true for all x in the domain.
Existential Quantifier (∃)	∃x P(x) means there exists at least one x in the domain for which P(x) is true.
Negation of Quantifiers	¬(∀x P(x)) ≡ ∃x ¬P(x) ¬(∃x P(x)) ≡ ∀x ¬P(x)

Relations

Basic Definitions

Relation	A subset of A × B, where A and B are sets. Represents a relationship between elements of A and B.
Binary Relation	A relation from a set A to itself (a subset of A × A).
Reflexive Relation	A relation R on A is reflexive if (a, a) ∈ R for all a ∈ A.
Symmetric Relation	A relation R on A is symmetric if (a, b) ∈ R implies (b, a) ∈ R.
Transitive Relation	A relation R on A is transitive if (a, b) ∈ R and (b, c) ∈ R implies (a, c) ∈ R.
Equivalence Relation	A relation that is reflexive, symmetric, and transitive.

Properties of Relations

Irreflexive: A relation R on A is irreflexive if (a, a) ∉ R for all a ∈ A.

Antisymmetric: A relation R on A is antisymmetric if (a, b) ∈ R and (b, a) ∈ R implies a = b.

Partial Order: A relation that is reflexive, antisymmetric, and transitive.

Total Order: A partial order where for every a, b ∈ A, either (a, b) ∈ R or (b, a) ∈ R.

Closures of Relations

Reflexive Closure	The smallest reflexive relation containing R. Add (a, a) for all a not already in the relation.
Symmetric Closure	The smallest symmetric relation containing R. If (a, b) ∈ R, add (b, a) to the relation.
Transitive Closure	The smallest transitive relation containing R. Computed using Warshall’s Algorithm.

Graph Theory

Basic Definitions

Graph	A pair G = (V, E) where V is a set of vertices and E is a set of edges connecting these vertices.
Directed Graph (Digraph)	A graph where edges have a direction. Edges are ordered pairs (u, v).
Undirected Graph	A graph where edges have no direction. Edges are unordered pairs {u, v}.
Adjacent Vertices	Two vertices are adjacent if they are connected by an edge.
Degree of a Vertex	The number of edges incident to the vertex. In digraphs, indegree is the number of incoming edges, and outdegree is the number of outgoing edges.
Path	A sequence of vertices connected by edges.

Graph Properties

Connected Graph: A graph where there is a path between every pair of vertices.

Complete Graph (Kn): A graph where every pair of distinct vertices is connected by an edge.

Cycle: A path that starts and ends at the same vertex.

Tree: A connected graph with no cycles.

Bipartite Graph: A graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

Planar Graph: A graph that can be drawn in the plane without any edges crossing.

Graph Representations

Adjacency Matrix	A matrix representing the graph’s connections. A[i][j] = 1 if there is an edge from vertex i to vertex j, and 0 otherwise.
Adjacency List	A list of adjacent vertices for each vertex in the graph.

Catalog / Discrete Mathematics Cheatsheet

Discrete Mathematics Cheatsheet

Discrete Mathematics Cheatsheet

Set Theory

Basic Definitions

Set Operations

Set Identities

Logic

Propositional Logic

Logical Equivalences

Predicate Logic

Relations

Basic Definitions

Properties of Relations

Closures of Relations

Graph Theory

Basic Definitions

Graph Properties

Graph Representations