Discrete Math Logic, Sets, Combinatorics Cheat Sheet

Key Facts

• The implication $p \to q$ is logically equivalent to $\neg p \lor q$ and is false only when $p$ is true and $q$ is false.
• De Morgan's laws are $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$.
• For sets, De Morgan's laws are $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$.
• The number of subsets of a set with $n$ elements is $2^n$, and the number of $k$-element subsets is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.
• The multiplication rule says that if one task has $m$ choices and a second independent task has $n$ choices, then both tasks have $mn$ choices.
• The inclusion-exclusion formula for two finite sets is $|A \cup B| = |A| + |B| - |A \cap B|$.
• For a finite simple graph $G=(V,E)$, the handshaking lemma is $\sum_{v \in V} \deg(v) = 2|E|$.
• A tree with $n$ vertices has exactly $n-1$ edges, is connected, and has no cycles.

Vocabulary

Proposition

A proposition is a statement that has a definite truth value, either true or false.

Biconditional

A biconditional $p \leftrightarrow q$ means that $p$ and $q$ have the same truth value.

Power Set

The power set of $A$, written $\mathcal{P}(A)$, is the set of all subsets of $A$.

Combination

A combination is a selection where order does not matter, counted by $\binom{n}{k}$.

Permutation

A permutation is an arrangement where order matters, counted by $P(n,k)=\frac{n!}{(n-k)!}$.

Connected Graph

A connected graph is a graph in which every pair of vertices is joined by at least one path.