A proposition is a statement that is either true (T) or false (F). It cannot be both.

• "5 is a prime number." — This is a proposition. It is true.
• "2 + 2 = 5." — This is a proposition. It is false.
• "What time is it?" — Not a proposition. A question has no truth value.
• "x + 1 = 3" — Not a proposition by itself. It depends on x.

We use small letters like \( p, q, r \) to name propositions.

We join propositions with connectives. These are the main ones:

A truth table lists every possible combination of truth values. With 2 variables there are \( 2^2 = 4 \) rows. With \( n \) variables, \( 2^n \) rows.

• Tautology: always true. Example: \( p \lor \neg p \).
• Contradiction: always false. Example: \( p \land \neg p \).
• Contingency: sometimes true, sometimes false. Example: \( p \rightarrow q \).

Two formulas are logically equivalent (written \( \equiv \)) if they have the same truth table. The most important laws:

Start with the implication \( p \rightarrow q \):

• Converse: \( q \rightarrow p \) — swap the two sides.
• Inverse: \( \neg p \rightarrow \neg q \) — negate both sides.
• Contrapositive: \( \neg q \rightarrow \neg p \) — swap AND negate.

Key fact: only the contrapositive is equivalent to the original. The converse and inverse are equivalent to each other, but NOT to the original.

• \( \forall x \, P(x) \) — "for all x, P(x) is true" (universal quantifier).
• \( \exists x \, P(x) \) — "there exists at least one x for which P(x) is true" (existential quantifier).

Example: over integers, \( \forall x \, (x^2 \ge 0) \) is true. \( \exists x \, (x^2 = 2) \) is false over integers (no integer squared gives 2).

Negating quantified statements — the negation flips the quantifier and moves inside:

In these riddles, every person is one of two types: a knight (always tells the truth) or a knave (always lies). Your job: find who is who, or get correct information out of them.

The famous two-roads trick: You reach a fork. One road leads to the village, the other to danger. Two people stand there: one always truthful, one always a liar — but you do not know who is who. You may ask only ONE question to ONE of them.

Magic question: "If I asked the other person which road leads to the village, what would they say?" Then take the opposite road.

Why it works — both people give the same (wrong) answer:

• You asked the truth-teller: he truthfully reports the liar's lie → you hear the wrong road.
• You asked the liar: he lies about the truth-teller's true answer → you hear the wrong road.

One truth passed through one lie is always a lie. So the answer you hear is guaranteed wrong — just flip it. The same trick works with one person of unknown type: ask "If I asked YOU whether the left road leads to the village, what would you say?" A lie about a lie becomes the truth, so this answer is always correct.

Mathematical induction proves a statement \( P(n) \) for all \( n \) from some start: first prove the base case, then the inductive step — "if it holds before \( n \), it holds at \( n \)". In strong induction, the step may assume \( P(k) \) for ALL earlier values \( k \) (start \( \le k < n \)), not just for \( n-1 \). Stamp (postage) problems are the classic use.

Problem: Prove that every postage amount \( n \ge 56 \) cents can be formed using only 8-cent and 9-cent stamps.

Base cases — we need one full block of 8 numbers, from 56 to 63:

• \( 56 = 7 \times 8 \),   \( 57 = 6 \times 8 + 9 \),   \( 58 = 5 \times 8 + 2 \times 9 \),   \( 59 = 4 \times 8 + 3 \times 9 \)
• \( 60 = 3 \times 8 + 4 \times 9 \),   \( 61 = 2 \times 8 + 5 \times 9 \),   \( 62 = 8 + 6 \times 9 \),   \( 63 = 7 \times 9 \)

Inductive step: take any \( n \ge 64 \). Then \( n - 8 \ge 56 \), so by the strong induction hypothesis \( n - 8 \) can already be formed. Add one more 8-cent stamp to that formation — now we have \( n \). Done: the statement holds for every \( n \ge 56 \).

A set is a collection of distinct objects, called elements. Order does not matter, and repeats do not count. We write \( A = \{1, 2, 3\} \), and \( 2 \in A \) means "2 is an element of A".

• Cardinality \( |A| \): the number of elements. \( |\{1,2,3\}| = 3 \).
• Subset \( A \subseteq B \): every element of A is also in B.
• Empty set \( \emptyset \): the set with no elements. \( |\emptyset| = 0 \). It is a subset of every set.
• Universal set \( U \): the set of everything under discussion.

De Morgan's laws work for sets too: \( \overline{A \cup B} = \overline{A} \cap \overline{B} \) and \( \overline{A \cap B} = \overline{A} \cup \overline{B} \). This is the same idea as in logic — union acts like OR, intersection acts like AND.

The power set \( P(S) \) is the set of ALL subsets of S, including \( \emptyset \) and S itself.

\( A \times B \) is the set of all ordered pairs \( (a, b) \) where \( a \in A \) and \( b \in B \). Order matters here: \( (1,2) \ne (2,1) \).

If we just add \( |A| + |B| \), the elements in both sets get counted twice. So we subtract the overlap once:

A relation R on a set A is a subset of \( A \times A \). It is just a set of ordered pairs. If \( (a,b) \in R \) we write \( a \, R \, b \) and say "a is related to b".

Example: on \( A = \{1,2,3\} \), the relation "less than" is \( R = \{(1,2), (1,3), (2,3)\} \).

A relation that is reflexive + symmetric + transitive is an equivalence relation. It splits the set into disjoint groups called equivalence classes — every element belongs to exactly one class.

A relation that is reflexive + antisymmetric + transitive is a partial order. Classic examples: "≤" on numbers, "⊆" on sets, "divides" on positive integers. It is called "partial" because some pairs may not be comparable — for example, under "divides", 4 and 6 are not comparable (4 does not divide 6, and 6 does not divide 4).

A function \( f: A \to B \) sends every element of A (domain) to exactly one element of B (codomain).

• Injective (one-to-one): different inputs give different outputs. \( f(a_1) = f(a_2) \implies a_1 = a_2 \).
• Surjective (onto): every element of B is hit by at least one input.
• Bijective: both injective and surjective. Perfect pairing — a bijection has an inverse function \( f^{-1} \).

\( (g \circ f)(x) = g(f(x)) \) — apply f first, then g. Order matters!

Let \( |A| = m \) and \( |B| = n \). Each of the m elements of A independently picks one of n targets.

• Sum rule: if a task can be done in \( m \) ways OR in \( n \) other ways (no overlap), total = \( m + n \).
• Product rule: if a task has two steps, first step \( m \) ways AND second step \( n \) ways, total = \( m \times n \).

Quick check: "OR" means add, "AND then" means multiply.

Permutation = arrangement, order matters. Combination = selection, order does not matter.

If a word has \( n \) letters where one letter repeats \( n_1 \) times, another \( n_2 \) times, and so on, the number of distinct arrangements is:

If you put more than \( n \) pigeons into \( n \) holes, some hole gets at least 2 pigeons. General form: with \( N \) objects in \( k \) boxes, some box has at least \( \lceil N/k \rceil \) objects.

Theorem (Erdős–Szekeres): any sequence of more than \( (r-1)(s-1) \) DISTINCT numbers contains an increasing subsequence of length \( r \) OR a decreasing subsequence of length \( s \). (A subsequence keeps the original order but may skip elements.)

Proof sketch (pigeonhole with label pairs):

1. Give every position \( i \) a label pair \( (x_i, y_i) \): \( x_i \) = length of the longest increasing subsequence ENDING at \( i \), and \( y_i \) = length of the longest decreasing subsequence ending at \( i \).
2. Suppose (for contradiction) there is no increasing subsequence of length \( r \) and no decreasing one of length \( s \). Then every \( x_i \le r-1 \) and every \( y_i \le s-1 \). So there are at most \( (r-1)(s-1) \) possible label pairs — these are the pigeonholes.
3. We have more than \( (r-1)(s-1) \) elements (the pigeons), so two positions \( i < j \) must share the SAME label pair. But that is impossible: if \( a_i < a_j \), we can extend the increasing subsequence, so \( x_j \ge x_i + 1 \); if \( a_i > a_j \), then \( y_j \ge y_i + 1 \). Either way the two pairs differ. Contradiction — so a long subsequence must exist.

Two "repetition allowed" formulas:

• Permutation with repetition: pick \( r \) items from \( n \) types, order matters, repeats allowed: \( n^r \).
• Combination with repetition (stars and bars): pick \( r \) items from \( n \) types, order does not matter, repeats allowed: \( \binom{n + r - 1}{r} \).

A recurrence relation defines a sequence using its previous terms. Example: \( a_n = 2a_{n-1} \) with \( a_0 = 1 \) gives 1, 2, 4, 8, 16, … A recurrence needs initial conditions (base cases) to pin down the sequence.

Setting up a recurrence means asking: "How does the answer for size n depend on smaller sizes?"

Move n disks from peg A to peg C, one disk at a time, never putting a bigger disk on a smaller one. Plan: move the top \( n-1 \) disks to peg B, move the biggest disk to C, then move the \( n-1 \) disks from B to C. So:

For a recurrence like \( a_n = c_1 a_{n-1} + c_2 a_{n-2} \), use the characteristic equation method:

1. Guess \( a_n = r^n \). Substitute to get \( r^2 = c_1 r + c_2 \), i.e. \( r^2 - c_1 r - c_2 = 0 \).
2. Find the roots \( r_1, r_2 \).
3. If roots are distinct: \( a_n = \alpha \, r_1^n + \beta \, r_2^n \). If there is a repeated root r: \( a_n = (\alpha + \beta n) r^n \).
4. Use the initial conditions to find \( \alpha, \beta \).

The Fibonacci sequence: \( F_n = F_{n-1} + F_{n-2} \), \( F_0 = 0, F_1 = 1 \): 0, 1, 1, 2, 3, 5, 8, 13, …

Its characteristic equation is \( r^2 - r - 1 = 0 \), with roots \( \varphi = \frac{1+\sqrt{5}}{2} \approx 1.618 \) (the golden ratio) and \( \psi = \frac{1-\sqrt{5}}{2} \approx -0.618 \). Applying the same method gives Binet's formula:

Since \( |\psi| < 1 \), the \( \psi^n \) part shrinks to almost nothing. So \( F_n \approx \varphi^n / \sqrt{5} \) — Fibonacci grows exponentially, and the ratio \( F_{n+1}/F_n \) approaches the golden ratio.

A graph \( G = (V, E) \) has a set of vertices (nodes) V and a set of edges E connecting pairs of vertices. Key terms:

• Degree deg(v): number of edges touching vertex v.
• Path: a sequence of vertices connected by edges, no vertex repeated.
• Cycle: a path that starts and ends at the same vertex.
• Connected graph: there is a path between every pair of vertices.
• Simple graph: no self-loops, no repeated edges.
• Complete graph \( K_n \): every pair of vertices is connected. It has \( \binom{n}{2} = \frac{n(n-1)}{2} \) edges.

Every edge touches exactly 2 vertices, so it adds 2 to the total degree:

• Euler path: uses every EDGE exactly once. Exists in a connected graph iff it has exactly 0 or 2 odd-degree vertices.
• Euler circuit: Euler path that returns to the start. Exists iff ALL vertices have even degree.
• Hamiltonian path: visits every VERTEX exactly once. No simple degree condition — checking is hard (NP-complete).

The famous Königsberg bridge problem started graph theory: can you walk crossing each of the 7 bridges exactly once? All 4 land areas have odd degree — more than 2 odd vertices — so Euler proved it is impossible.

A graph is bipartite if its vertices split into two groups, and every edge goes between the groups (never inside a group). Key fact: a graph is bipartite iff it has no odd-length cycle. The complete bipartite graph \( K_{m,n} \) has \( m \times n \) edges.

Graph coloring: assign colors to vertices so that neighbors get different colors. The minimum number of colors needed is the chromatic number \( \chi(G) \). Bipartite = 2-colorable, so \( \chi = 2 \) (if it has at least one edge). For \( K_n \), \( \chi = n \). For a cycle: even cycle needs 2 colors, odd cycle needs 3.

A tree is a connected graph with NO cycles. Equivalent facts (any one implies the others):

• A tree with \( n \) vertices has exactly \( n - 1 \) edges.
• Between any two vertices there is exactly ONE path.
• Adding any edge creates exactly one cycle; removing any edge disconnects it.

A spanning tree of a connected graph G is a tree that contains all vertices of G. To get one, delete \( |E| - (n-1) \) edges (breaking all cycles). A rooted tree picks one vertex as root; then we can talk about parent, child, leaf (no children), height, and levels.

We say \( a \mid b \) ("a divides b") if \( b = ka \) for some integer k. Example: \( 3 \mid 12 \), but \( 5 \nmid 12 \).

A prime is an integer greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, … The number 1 is NOT prime. The fundamental theorem of arithmetic: every integer greater than 1 has a unique prime factorization. Example: \( 360 = 2^3 \times 3^2 \times 5 \).

Quick primality check for small n: test divisibility by primes up to \( \sqrt{n} \). For 97: \( \sqrt{97} \approx 9.8 \), test 2, 3, 5, 7 — none divide it, so 97 is prime.

GCD (greatest common divisor) is the largest number dividing both a and b. LCM (least common multiple) is the smallest positive number both divide. They connect by a beautiful identity:

The Euclidean algorithm finds gcd fast: replace the bigger number by its remainder when divided by the smaller. Repeat until the remainder is 0. The last non-zero remainder is the gcd.

\( a \equiv b \pmod{m} \) means m divides \( a - b \) — in other words, a and b leave the same remainder when divided by m. Example: \( 17 \equiv 2 \pmod{5} \) because both leave remainder 2.

Congruences behave nicely with + and ×: if \( a \equiv b \) and \( c \equiv d \pmod m \), then \( a + c \equiv b + d \) and \( ac \equiv bd \pmod m \). This lets us reduce numbers BEFORE multiplying — the key trick for big powers.

To compute \( a^n \bmod m \) for big n, look for a repeating pattern of powers, or use repeated squaring.