Discrete Math Logic, Sets, Combinatorics Cheat Sheet

This cheat sheet covers the core tools of discrete mathematics: logic, sets, counting, and graph theory. These topics are the language of proof, algorithms, data structures, probability, and computer science theory. College students need a compact reference because many problems combine symbols, definitions, and formulas from several areas at once.

The most important ideas are translating statements into logical form, using set notation correctly, and selecting the right counting method. Logic depends on truth values, implications, quantifiers, and equivalences. Counting depends on product rules, permutations, combinations, inclusion-exclusion, and recurrences.

Graph theory focuses on vertices, edges, degrees, paths, connectivity, trees, and classic formulas such as $\sum_{v \in V} \deg(v) = 2|E|$ .

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.

Common Mistakes to Avoid

Confusing $p \to q$ with $q \to p$ is wrong because an implication and its converse do not usually have the same truth value.
Treating $A \cup B$ like $A \cap B$ is wrong because a union includes elements in either set, while an intersection includes only elements in both sets.
Using $\binom{n}{k}$ when order matters is wrong because combinations ignore order, while ordered selections require permutations such as $P(n,k)=\frac{n!}{(n-k)!}$ .
Forgetting to subtract overlap in inclusion-exclusion is wrong because elements in $A \cap B$ are counted twice in $|A|+|B|$ .
Assuming every graph with $n-1$ edges is a tree is wrong because a tree must also be connected and acyclic.

Practice Questions

1 Construct the truth table for $(p \to q) \land \neg q$ and determine when it is true.
2 A set $A$ has $8$ elements. How many subsets does $A$ have, and how many subsets have exactly $3$ elements?
3 How many length- $5$ passwords can be made from $26$ lowercase letters if repetition is allowed, and how many if repetition is not allowed?
4 Explain why a connected graph with $n$ vertices and $n-1$ edges cannot contain a cycle.

Understanding Discrete Math Logic, Sets, Combinatorics

A good way to solve a discrete math problem is to identify its structure before choosing a formula. Start by naming the objects involved. They may be statements, members of a collection, arrangements, or points joined by links.

Then decide what must be shown or counted. Small examples are useful because they expose hidden conditions. For a logic statement, make a truth table when only a few variables appear.

For a set problem, sketch overlapping regions and mark the universal set. For a counting problem, list outcomes for a tiny case.

This is not wasted time. It helps prevent a correct rule from being applied to the wrong situation.

Logic is especially important in proofs because ordinary language can be vague. Words such as every, some, only if, and unless carry precise meaning. A statement beginning with every requires attention to all allowed cases.

A statement beginning with some needs only one valid example. To disprove a universal claim, one counterexample is enough. To prove that two statements are equivalent, show that each one leads to the other.

Students often confuse a statement with its converse. If studying implies passing, it does not follow that passing implies studying.

Many proof errors come from making this reversal without noticing it. In programming, the same care matters when an if condition controls whether code runs.

Counting methods depend on whether order matters and whether choices can repeat. Choosing three students for a committee differs from assigning president, secretary, and treasurer to three students. The first treats the same group as one outcome.

The second gives different outcomes when roles change. Break complex counts into stages only when each stage has a clear number of available choices. If restrictions are present, it can be easier to count all outcomes first, then remove the invalid ones.

Inclusion and exclusion is useful when categories overlap, such as students enrolled in two clubs. The overlap must be handled carefully because those students appear in both initial totals. Probability uses these same counts when outcomes are equally likely.

Recurrences describe processes that grow step by step. A recurrence does not merely give an answer. It explains how the next value depends on earlier values.

This appears in savings plans, population models, tiling problems, and the running time of computer algorithms. Find starting values before using a recurrence, since the rule alone may allow many sequences. Graphs provide another model for real systems.

Vertices can represent people, cities, web pages, or tasks. Edges represent a relationship or connection. A path tracks possible movement through the system.

A cycle shows a route that returns to its start. Trees are useful for folder systems and decision processes because there is exactly one route between any two vertices.

When working with graphs, draw a neat labeled picture and check each connection once. A missing edge can change connectivity, degrees, and the entire conclusion.

Sign in to save

Sign in to save

Discrete Math Logic, Sets, Combinatorics Cheat Sheet

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Key Facts

Vocabulary

Common Mistakes to Avoid

Practice Questions

Understanding Discrete Math Logic, Sets, Combinatorics