Discrete Mathematics — Comprehensive Lecture Notes

教材：K. Rosen, Discrete Mathematics and its Applications, 8th Edition 本笔记按课程顺序整理，涵盖第1–11次课所有内容，详细复述课件知识点。关键术语在首次出现时括号内给出中文翻译。

---

Chapter 1: Logic and Proofs（逻辑与证明）

---

Section 1.1 — Propositional Logic（命题逻辑）

Propositions（命题）

A proposition (命题) is a declarative sentence that is either true or false — not both.

Examples of propositions:

• "The Moon is made of green cheese." (false)
• "1 + 0 = 1" (true)
• "0 + 0 = 2" (false)

Examples that are NOT propositions:

• "Sit down!" — (a command, not declarative)
• "What time is it?" — (a question)
• "x + 1 = 2" — (contains a free variable, truth value undefined)

Propositional Variables（命题变量）

We use propositional variables $p,q,r,s,\dots$ to represent propositions.

• The proposition that is always true is denoted $T$ (tautology).
• The proposition that is always false is denoted $F$ (contradiction).

Compound propositions (组合命题) are built from simpler ones using logical connectives (逻辑联结词).

The Six Connectives

1. Negation（否定） — $\mathrm{\neg }p$ ("not p")

$p$	$\mathrm{\neg }p$
T	F
F	T

2. Conjunction（合取） — $p\wedge q$ ("p AND q")

$p\wedge q$ is true only when both $p$ and $q$ are true.

$p$	$q$	$p\wedge q$
T	T	T
T	F	F
F	T	F
F	F	F

3. Disjunction（析取） — $p\vee q$ ("p OR q")

This is the inclusive or (兼或): $p\vee q$ is true when at least one of $p$, $q$ is true.

$p$	$q$	$p\vee q$
T	T	T
T	F	T
F	T	T
F	F	F

4. Exclusive Or（异或） — $p\oplus q$ ("p XOR q")

$p\oplus q$ is true when exactly one of $p$, $q$ is true (but not both).

$p$	$q$	$p\oplus q$
T	T	F
T	F	T
F	T	T
F	F	F

5. Conditional Statement（条件命题/蕴含） — $p\to q$ ("if p, then q")

This is the most subtle connective. $p\to q$ is false only when $p$ is true and $q$ is false.

$p$	$q$	$p\to q$
T	T	T
T	F	F
F	T	T
F	F	T

• $p$ is called the hypothesis (假设) / antecedent (前件) / premise (前提).
• $q$ is called the conclusion (结论) / consequent (后件).

Key insight: When the hypothesis is false, the whole implication is vacuously true. Think of it as a contract: "If I am elected, I will lower taxes." The politician only breaks the promise when elected but does NOT lower taxes.

Many ways to say $p\to q$ in English:

• "if p, then q" / "p implies q" / "p only if q"
• "q if p" / "q whenever p" / "q follows from p"
• "p is sufficient for q" / "q is necessary for p"

Related conditionals derived from $p\to q$:

Name	Form	Equivalent to
Converse（逆命题）	$q\to p$	—
Inverse（反命题）	$\mathrm{\neg }p\to \mathrm{\neg }q$	—
Contrapositive（逆否命题）	$\mathrm{\neg }q\to \mathrm{\neg }p$	$p\to q$ ✓

$p\to q$ is logically equivalent to its contrapositive $\mathrm{\neg }q\to \mathrm{\neg }p$, but not to its converse or inverse.

6. Biconditional Statement（双条件命题） — $p\leftrightarrow q$ ("p if and only if q", "p iff q")

$p\leftrightarrow q$ is true when $p$ and $q$ have the same truth value.

$p$	$q$	$p\leftrightarrow q$
T	T	T
T	F	F
F	T	F
F	F	T

Note: $p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$

Precedence of Logical Operators（优先级）

From highest to lowest:

Operator	Precedence
$\mathrm{\neg }$	1 (highest)
$\wedge$	2
$\vee$	3
$\to$	4
$\leftrightarrow$	5 (lowest)

So $p\wedge q\vee r$ means $(p\wedge q)\vee r$.

Bit Operations（位运算）

In computers, bits (0 and 1) represent truth values (0 = False, 1 = True). Boolean operations correspond to logical operations:

• Bitwise OR ↔ $\vee$
• Bitwise AND ↔ $\wedge$
• Bitwise XOR ↔ $\oplus$

---

Section 1.2 — Applications of Propositional Logic

Key application: translating English sentences to logic.

Steps:

1. Identify atomic propositions and assign variables.
2. Determine logical connectives.

Example: "You can access the Internet from campus only if you are a student or you pay the fee."

• Let $a$ = "you can access the Internet from campus"
• Let $s$ = "you are a student"
• Let $p$ = "you pay the fee"
• Result: $a\to (s\vee p)$

System specifications (系统规范) must be consistent (自洽的) — no assignment of truth values should cause a contradiction.

Logic puzzles: use logic to determine truth from clues.

---

Section 1.3 — Logical Equivalences（逻辑等价式）

Two propositions are logically equivalent (逻辑等价) if they have the same truth value for every assignment of truth values to their variables. We write $p\equiv q$.

Key Equivalences Table

Law Name	Equivalences
Identity laws (恒等律)	$p\wedge T\equiv p$, $p\vee F\equiv p$
Domination laws (支配律)	$p\vee T\equiv T$, $p\wedge F\equiv F$
Idempotent laws (幂等律)	$p\vee p\equiv p$, $p\wedge p\equiv p$
Double Negation	$\mathrm{\neg }(\mathrm{\neg }p)\equiv p$
Commutative laws (交换律)	$p\vee q\equiv q\vee p$, $p\wedge q\equiv q\wedge p$
Associative laws (结合律)	$(p\vee q)\vee r\equiv p\vee (q\vee r)$
Distributive laws (分配律)	$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$
De Morgan's laws (德摩根律)	$\mathrm{\neg }(p\wedge q)\equiv \mathrm{\neg }p\vee \mathrm{\neg }q$, $\mathrm{\neg }(p\vee q)\equiv \mathrm{\neg }p\wedge \mathrm{\neg }q$
Absorption laws (吸收律)	$p\vee (p\wedge q)\equiv p$, $p\wedge (p\vee q)\equiv p$
Complement laws (互补律)	$p\vee \mathrm{\neg }p\equiv T$, $p\wedge \mathrm{\neg }p\equiv F$

Useful implications:

• $p\to q\equiv \mathrm{\neg }p\vee q$
• $p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$

Constructing Equivalence Proofs

To show $A\equiv B$, build a chain of equivalences $A\equiv \cdots \equiv B$, applying known laws at each step.

Example: Show $\mathrm{\neg }(p\to q)\equiv p\wedge \mathrm{\neg }q$:

$$\mathrm{\neg }(p\to q)\equiv \mathrm{\neg }(\mathrm{\neg }p\vee q)\equiv p\wedge \mathrm{\neg }q$$

Tautology (重言式/永真式): always true.
Contradiction (矛盾式/永假式): always false.
Contingency (可满足式): truth depends on variable values.

Dual（对偶式）

The dual $S^{\ast }$ of a formula $S$ (containing only $\wedge ,\vee ,\mathrm{\neg }$) is obtained by:

• Replacing each $\wedge$ with $\vee$ and vice versa
• Replacing each $T$ with $F$ and vice versa

Theorem: If $S\equiv T$, then $S^{\ast }\equiv T^{\ast }$.

Example: $S=(p\wedge \mathrm{\neg }q)\vee r\vee T$, so $S^{\ast }=(p\vee \mathrm{\neg }q)\wedge r\wedge F$.

Functionally Complete Operators（完全联结词组）

A set of operators is functionally complete (完全的) if every compound proposition can be expressed using only those operators.

Complete sets include:

• $\{\mathrm{\neg },\wedge \}$, $\{\mathrm{\neg },\vee \}$
• $\{|\}$ (NAND / Sheffer stroke 与非) — alone forms a complete set
• $\{\downarrow \}$ (NOR / Peirce arrow 或非) — alone forms a complete set

Propositional Satisfiability（命题可满足性）

A compound proposition is satisfiable (可满足的) if at least one assignment of truth values makes it true. If no such assignment exists, it is unsatisfiable (不可满足的).

SAT problem: determining satisfiability is NP-complete. Many real-world problems (e.g., Sudoku) can be encoded as SAT problems and solved by SAT solvers.

---

Section 1.3 (Supplement) — Propositional Normal Forms（范式）

Propositional Formula（命题公式）

Formal definition:

1. Each propositional variable and $T,F$ are formulas.
2. If $A$ is a formula, so is $(\mathrm{\neg }A)$.
3. If $A$ and $B$ are formulas, so are $(A\wedge B)$, $(A\vee B)$, $(A\to B)$, $(A\leftrightarrow B)$.
4. Only strings formed by finitely many applications of the above rules are formulas.

Literals（文字）

A literal (文字) is a propositional variable or its negation. E.g., $p$ and $\mathrm{\neg }p$ are literals.

DNF — Disjunctive Normal Form（析取范式）

A formula is in DNF if it is a disjunction of conjunctive clauses (合取子句), where each conjunctive clause is a conjunction of literals.

$$\text{DNF form: }(l_{11}\wedge \cdots \wedge l_{1n})\vee \cdots \vee (l_{k1}\wedge \cdots \wedge l_{km})$$

Example: $(p\wedge q)\vee (p\wedge \mathrm{\neg }q)\vee \mathrm{\neg }p$ is in DNF.

CNF — Conjunctive Normal Form（合取范式）

A formula is in CNF if it is a conjunction of disjunctive clauses (析取子句), where each disjunctive clause is a disjunction of literals.

$$\text{CNF form: }(l_{11}\vee \cdots \vee l_{1n})\wedge \cdots \wedge (l_{k1}\vee \cdots \wedge l_{km})$$

How to convert a formula to CNF/DNF:

1. Eliminate $\to$ and $\leftrightarrow$ using equivalences.
2. Move $\mathrm{\neg }$ inward: apply De Morgan's laws and double negation until $\mathrm{\neg }$ only precedes atoms.
3. Use distributive laws to expand to the desired form.

Example: Convert $\mathrm{\neg }((p\wedge \mathrm{\neg }q)\vee \mathrm{\neg }r)$ to CNF:

$$\mathrm{\neg }(p\wedge \mathrm{\neg }q)\wedge (\mathrm{\neg }\mathrm{\neg }r)\text{[De Morgan]}$$$$\mathrm{\neg }(p\wedge \mathrm{\neg }q)\wedge r\text{[Double neg]}$$$$(\mathrm{\neg }p\vee q)\wedge r\text{[De Morgan]}$$$$(\mathrm{\neg }p\vee r)\wedge (q\vee r)\text{[Distributive]}$$

Minterms（极小项/最小项）

A minterm (极小项) is a conjunction of literals in which each variable appears exactly once (positive or negative).

For $n$ variables there are $2^n$ distinct minterms. We write $m_j$ for the minterm that is true when the binary representation of $j$ gives the values of the variables.

For variables $p,q,r$:

$j$	minterm $m_j$	true when
0	$\mathrm{\neg }p\wedge \mathrm{\neg }q\wedge \mathrm{\neg }r$	$p=F,q=F,r=F$
1	$\mathrm{\neg }p\wedge \mathrm{\neg }q\wedge r$	$p=F,q=F,r=T$
2	$\mathrm{\neg }p\wedge q\wedge \mathrm{\neg }r$
3	$\mathrm{\neg }p\wedge q\wedge r$
4	$p\wedge \mathrm{\neg }q\wedge \mathrm{\neg }r$
5	$p\wedge \mathrm{\neg }q\wedge r$
6	$p\wedge q\wedge \mathrm{\neg }r$
7	$p\wedge q\wedge r$	$p=T,q=T,r=T$

Properties of minterms:

1. Each minterm is true for exactly one assignment.
2. The conjunction of two different minterms is always $F$.
3. The disjunction of all minterms is $T$.

Full Disjunctive Normal Form（主析取范式）

The full disjunctive normal form (主析取范式) of a function $f$ is the disjunction of all minterms for which $f$ is true.

Notation: $f=\sum m(j,k,\dots ,l)$

How to find from a truth table: select the minterms corresponding to rows where the function is true.

Example: If $f$ is true for assignments (T,T,T), (T,F,T), (F,F,T):

$$f=m_7\vee m_5\vee m_1=\sum m(1,5,7)$$

Maxterms（极大项）and Full CNF（主合取范式）

A maxterm $M_i=\mathrm{\neg }{m}_i$ is a disjunction of literals.

Converting between forms: if $f=\sum m(j,k,\dots )$, let $g$ be the disjunction of all remaining minterms.
Then $f=\prod M(\text{indices not in }f)$ — the full conjunctive normal form (主合取范式).

---

Section 1.4 — Predicate Logic（谓词逻辑）

Propositional logic cannot express arguments like "All men are mortal; Socrates is a man; therefore Socrates is mortal." We need predicate logic (谓词逻辑), also called first-order logic.

Propositional Functions（命题函数）

A propositional function $P(x)$ becomes a proposition when variables are bound. E.g., $P(x) = $ "x > 0". Then $P(3)$ is true, $P(-1)$ is false.

Quantifiers（量词）

Universal Quantifier（全称量词） $\mathrm{\forall }$: "$\mathrm{\forall }xP(x)$" means "For all $x$ in the domain, $P(x)$."

• True when $P(x)$ is true for every element of the domain.
• False when there exists at least one counterexample (反例) $c$ for which $P(c)$ is false.
• When domain $=\{x_1,\dots ,x_n\}$: $\mathrm{\forall }xP(x)\equiv P(x_1)\wedge P(x_2)\wedge \cdots \wedge P(x_n)$

Existential Quantifier（存在量词） $\mathrm{\exists }$: "$\mathrm{\exists }xP(x)$" means "There exists an $x$ such that $P(x)$."

• True when $P(x)$ is true for at least one element.
• When domain $=\{x_1,\dots ,x_n\}$: $\mathrm{\exists }xP(x)\equiv P(x_1)\vee P(x_2)\vee \cdots \vee P(x_n)$

Uniqueness Quantifier（唯一性量词） $\mathrm{\exists }!$: "$\mathrm{\exists }!xP(x)$" means "There is exactly one $x$ such that $P(x)$."

This can be expressed as: $\mathrm{\exists }x(P(x)\wedge \mathrm{\forall }y(P(y)\to y=x))$

Precedence: quantifiers have higher precedence than all logical operators.
So $\mathrm{\forall }xP(x)\vee Q(x)$ means $(\mathrm{\forall }xP(x))\vee Q(x)$.

Bound vs. Free Variables（约束变量 vs. 自由变量）

• A variable is bound (约束的) if it is quantified.
• A variable is free (自由的) if it is not quantified.
• The scope (作用域) of a quantifier is the part of the expression to which it applies.

All variables must be bound for the expression to be a proposition.

De Morgan's Laws for Quantifiers

$$\mathrm{\neg }\mathrm{\forall }xP(x)\equiv \mathrm{\exists }x\mathrm{\neg }P(x)$$$$\mathrm{\neg }\mathrm{\exists }xP(x)\equiv \mathrm{\forall }x\mathrm{\neg }P(x)$$

To negate a universal statement, turn it into an existential statement that the property fails somewhere (and vice versa).

Translating English to Logic

Key patterns:

• "All/every/each S are P" → $\mathrm{\forall }x(S(x)\to P(x))$
• "Some/there exists an S that is P" → $\mathrm{\exists }x(S(x)\wedge P(x))$
  (Warning: do NOT use $\to$ with $\mathrm{\exists }$, it has a different meaning!)

Example: "No CS student is a Math student."

$$\mathrm{\forall }x(C(x)\to \mathrm{\neg }E(x))\text{or equivalently}\mathrm{\neg }\mathrm{\exists }x(C(x)\wedge E(x))$$

Logical Equivalences with Quantifiers

If $x$ does not occur in $A$:

$$\mathrm{\forall }xP(x)\vee A\equiv \mathrm{\forall }x(P(x)\vee A)$$$$\mathrm{\exists }xP(x)\wedge A\equiv \mathrm{\exists }x(P(x)\wedge A)$$

---

Section 1.5 — Nested Quantifiers（嵌套量词）

Nested quantifiers (嵌套量词): one quantifier is within the scope of another.

Example: "Every real number has an additive inverse":

$$\mathrm{\forall }x\mathrm{\exists }y(x+y=0)$$

Order of Quantifiers Matters!

$\mathrm{\forall }x\mathrm{\exists }yP(x,y)$: "For each $x$, there is a $y$..." — the $y$ may depend on $x$.
$\mathrm{\exists }y\mathrm{\forall }xP(x,y)$: "There is one $y$ that works for all $x$" — much stronger.

These are generally NOT equivalent.

Statement	When true	When false
$\mathrm{\forall }x\mathrm{\forall }yP(x,y)$	$P(x,y)$ true for every pair	Some pair makes $P$ false
$\mathrm{\forall }x\mathrm{\exists }yP(x,y)$	For each $x$, some $y$ works	Some $x$ has no working $y$
$\mathrm{\exists }x\mathrm{\forall }yP(x,y)$	One $x$ works for all $y$	Every $x$ fails for some $y$
$\mathrm{\exists }x\mathrm{\exists }yP(x,y)$	Some pair satisfies $P$	$P$ false for every pair

Negating Nested Quantifiers

Apply De Morgan's laws repeatedly, moving $\mathrm{\neg }$ inward:

$$\mathrm{\neg }\mathrm{\forall }x\mathrm{\exists }yP(x,y)\equiv \mathrm{\exists }x\mathrm{\forall }y\mathrm{\neg }P(x,y)$$

---

Section 1.6 — Rules of Inference（推理规则）

Valid Arguments（有效论证）

An argument (论证) in propositional logic is a sequence of propositions; all but the last are premises (前提), and the last is the conclusion (结论).

An argument is valid (有效的) if whenever all premises are true, the conclusion is also true — i.e., $(p_1\wedge p_2\wedge \cdots \wedge p_n)\to q$ is a tautology.

Rules of Inference for Propositions

Rule Name	Form	Tautology
Modus Ponens (假言推理)	$p$, $p\to q$ $⊢$ $q$	$(p\wedge (p\to q))\to q$
Modus Tollens (取拒式)	$\mathrm{\neg }q$, $p\to q$ $⊢$ $\mathrm{\neg }p$	$(\mathrm{\neg }q\wedge (p\to q))\to \mathrm{\neg }p$
Hypothetical Syllogism (假言三段论)	$p\to q$, $q\to r$ $⊢$ $p\to r$
Disjunctive Syllogism (析取三段论)	$p\vee q$, $\mathrm{\neg }p$ $⊢$ $q$
Addition (附加律)	$p$ $⊢$ $p\vee q$
Simplification (化简律)	$p\wedge q$ $⊢$ $p$
Conjunction (合取律)	$p$, $q$ $⊢$ $p\wedge q$
Resolution (消解律)	$p\vee r$, $\mathrm{\neg }p\vee q$ $⊢$ $q\vee r$

Rules of Inference for Quantified Statements

Rule	Name
$\mathrm{\forall }xP(x)$ $⊢$ $P(c)$ for arbitrary $c$	Universal Instantiation (UI) (全称实例)
$P(c)$ for arbitrary $c$ $⊢$ $\mathrm{\forall }xP(x)$	Universal Generalization (UG) (全称引入)
$\mathrm{\exists }xP(x)$ $⊢$ $P(c)$ for some element $c$	Existential Instantiation (EI) (存在实例)
$P(c)$ for some $c$ $⊢$ $\mathrm{\exists }xP(x)$	Existential Generalization (EG) (存在引入)

Universal Modus Ponens (全称假言推理) combines UI and Modus Ponens:

$$\mathrm{\forall }x(P(x)\to Q(x)),P(a)⊢Q(a)$$

Building valid arguments: Write each step as either a premise or a consequence of previous steps by a named rule.

---

Section 1.7 — Introduction to Proofs（证明方法）

Terminology

• Theorem (定理): a statement proven true using definitions, other theorems, axioms, and rules of inference.
• Lemma (引理): a "helping theorem" used in the proof of a larger result.
• Corollary (推论): a result that follows directly from a theorem.
• Conjecture (猜想): a statement believed to be true but not yet proven.
• Axiom (公理): a statement assumed to be true.

Even and Odd Integers

$n$ is even if $\mathrm{\exists }k(n=2k)$.
$n$ is odd if $\mathrm{\exists }k(n=2k+1)$.
Every integer is either even or odd (but not both).

A real number $r$ is rational if $r=p/q$ for some integers $p,q$ with $q\ne 0$.

Proof Methods for $p\to q$

1. Direct Proof（直接证明法）: Assume $p$ is true, then show $q$ follows.

Example: Prove "if $n$ is odd, then $n^2$ is odd."
Proof: Assume $n=2k+1$. Then $n^2=4k^2+4k+1=2(2k^2+2k)+1$, which is odd. $◻$

2. Proof by Contraposition（反证法/逆否证明）: Prove $\mathrm{\neg }q\to \mathrm{\neg }p$ instead (equivalent to $p\to q$).

Example: Prove "if $n^2$ is odd, then $n$ is odd."
Proof: (Contrapositive) Assume $n$ is even, so $n=2k$. Then $n^2=4k^2=2(2k^2)$ is even. $◻$

3. Proof by Contradiction（归谬证明法）: Assume $\mathrm{\neg }p$ (or $\mathrm{\neg }q$) and derive a contradiction.

Example: Prove $\sqrt{2}$ is irrational.
Proof: Assume $\sqrt{2}=a/b$ in lowest terms. Then $2=a^2/b^2$, so $a^2=2b^2$, meaning $a$ is even. Write $a=2c$, then $4c^2=2b^2$, so $b^2=2c^2$, meaning $b$ is even. But then $a$ and $b$ share a factor of 2, contradicting "lowest terms." $◻$

Example: Prove there is no largest prime.
Proof: Assume primes $p_1,p_2,\dots ,p_n$ are all primes. Let $q=p_1{p}_2\cdots p_n+1$. None of $p_1,\dots ,p_n$ divides $q$ (remainder 1 each time). So $q$ is either prime itself or has a prime factor not in the list — contradiction. $◻$

4. Trivial Proof（平凡证明）: If $q$ is known to be true, then $p\to q$ is true.

5. Vacuous Proof（空证明）: If $p$ is known to be false, then $p\to q$ is true.

Biconditional Proofs

To prove $p\leftrightarrow q$: prove $p\to q$ AND $q\to p$ separately.

---

Section 1.8 — More Proof Strategies

Proof by Cases（分情形证明）

Use the tautology $(p_1\vee p_2\vee \cdots \vee p_n)\to q\equiv [(p_1\to q)\wedge (p_2\to q)\wedge \cdots \wedge (p_n\to q)]$.

Prove $q$ is true in each possible case.

Without Loss of Generality (WLOG) (不失一般性): when cases are symmetric, prove one and state the other follows similarly.

Existence Proofs（存在性证明）

Prove $\mathrm{\exists }xP(x)$.

• Constructive (构造性): find an explicit $c$ such that $P(c)$ is true.
  Example: 1729 = ${10}^3+9^3={12}^3+1^3$ (can be written as sum of cubes in two ways).

• Nonconstructive (非构造性): prove existence indirectly (often by contradiction), without finding the element.
  Example: Prove $\mathrm{\exists }$ irrational $x,y$ such that $x^y$ is rational.
  Consider ${\sqrt{2}}^{\sqrt{2}}$: if rational, done ($x=y=\sqrt{2}$). If irrational, let $x={\sqrt{2}}^{\sqrt{2}}$, $y=\sqrt{2}$; then $x^y=2$, rational. $◻$

Disproof by Counterexample（反例否证）

To disprove $\mathrm{\forall }xP(x)$, find one $c$ such that $P(c)$ is false.

Uniqueness Proofs（唯一性证明）

To prove $\mathrm{\exists }!xP(x)$:

1. Existence: find an element $x$ satisfying $P(x)$.
2. Uniqueness: show that if $y\ne x$ also satisfies $P$, we get a contradiction.

Proof Strategies

• Forward reasoning: start from axioms/premises, derive conclusion.
• Backward reasoning: to prove $q$, find a statement $p$ with $p\to q$ that you can prove.
• If direct proof fails, try contrapositive or contradiction.

Open Problems (undecided conjectures)

• Fermat's Last Theorem (费马大定理): $x^n+y^n=z^n$ has no integer solutions with $xyz\ne 0$ for $n>2$. (Proved by Andrew Wiles, 1990s)
• Goldbach's Conjecture (哥德巴赫猜想): every even integer $>2$ is the sum of two primes. (Still open)
• 3x+1 Conjecture (Collatz): repeatedly applying $x\mapsto x/2$ (if even) or $x\mapsto 3x+1$ (if odd) always reaches 1.

Additional Proof Methods (Preview)

• Mathematical Induction (数学归纳法): covered in Chapter 5.
• Structural Induction (结构归纳法): for recursively defined sets.
• Cantor Diagonalization (康托尔对角线方法): proving uncountability.
• Combinatorial Proofs (组合证明): using counting arguments.

---

Chapter 2: Basic Structures（基本结构）

---

Section 2.1 — Sets（集合）

A set (集合) is an unordered collection of distinct objects. Objects in a set are called elements (元素) or members (成员).

Notation: $a\in A$ means $a$ is an element of $A$; $a\notin A$ means $a$ is not.

Describing Sets

Roster method (列举法): list elements explicitly.
$S=\{a,b,c,d\}$, $O=\{1,3,5,7,9\}$

Set-builder notation (描述法): $S=\{x\mid P(x)\}$ — all $x$ satisfying property $P$.
$O=\{x\in {\mathbb{Z}}^{+}\mid x\text{ is odd and }x<10\}$

Important Sets

Symbol	Set
$\mathbb{N}$	Natural numbers $\{0,1,2,3,\dots \}$
$\mathbb{Z}$	Integers $\{\dots ,-2,-1,0,1,2,\dots \}$
${\mathbb{Z}}^{+}$	Positive integers $\{1,2,3,\dots \}$
$\mathbb{Q}$	Rational numbers
$\mathbb{R}$	Real numbers
$\mathbb{C}$	Complex numbers

Universal set (全集) $U$: contains all objects under consideration.
Empty set (空集) $\mathrm{\varnothing }$ (also written $\{\}$): contains no elements.

Russell's Paradox (罗素悖论): Let $S=\{x\mid x\notin x\}$. Is $S\in S$? Either answer leads to contradiction. This motivates axiomatic set theory.

Subsets, Equality, Power Sets

• $A\subseteq B$ (subset, 子集): every element of $A$ is also in $B$.
  Equivalently, $\mathrm{\forall }x(x\in A\to x\in B)$.
• $A=B$ (equality): $A\subseteq B$ and $B\subseteq A$.
• $A\subset B$ (proper subset, 真子集): $A\subseteq B$ but $A\ne B$.
• $\mathrm{\varnothing }\subseteq S$ for every set $S$; $S\subseteq S$ for every set $S$.

Cardinality (基数) $|A|$: the number of distinct elements in a finite set $A$.
$|\mathrm{\varnothing }|=0$, $|\{1,2,3\}|=3$, $|\{\mathrm{\varnothing }\}|=1$.

Power set (幂集) $\mathcal{P}(A)$: the set of all subsets of $A$.
If $|A|=n$, then $|\mathcal{P}(A)|=2^n$.
Example: $A=\{a,b\}$, $\mathcal{P}(A)=\{\mathrm{\varnothing },\{a\},\{b\},\{a,b\}\}$.

Tuples and Cartesian Product

An ordered $n$-tuple (有序$n$元组) $(a_1,a_2,\dots ,a_n)$: an ordered collection where position matters.
2-tuples are called ordered pairs (序偶).

Cartesian product (笛卡尔积) $A\times B=\{(a,b)\mid a\in A\text{ and }b\in B\}$.

Example: $A=\{a,b\}$, $B=\{1,2,3\}$:

$$A\times B=\{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\}$$

A relation (关系) from $A$ to $B$ is a subset of $A\times B$ (more in Chapter 9).

---

Section 2.2 — Set Operations（集合运算）

Set operations are analogous to logical operations (Boolean Algebra).

Operation	Definition	Analogy
Union (并集) $A\cup B$	$\{x\mid x\in A\vee x\in B\}$	$\vee$
Intersection (交集) $A\cap B$	$\{x\mid x\in A\wedge x\in B\}$	$\wedge$
Complement (补集) $\overline{A}$	$\{x\in U\mid x\notin A\}$	$\mathrm{\neg }$
Difference (差集) $A-B$	$\{x\mid x\in A\wedge x\notin B\}=A\cap \overline{B}$	—
Symmetric Difference (对称差) $A\oplus B$	$(A-B)\cup (B-A)$	$\oplus$

If $A\cap B=\mathrm{\varnothing }$, $A$ and $B$ are disjoint (不相交).

Inclusion-Exclusion (容斥原理): $|A\cup B|=|A|+|B|-|A\cap B|$

Set Identities

Mirror image of logical equivalences — just replace $\wedge \leftrightarrow \cap$, $\vee \leftrightarrow \cup$, $\mathrm{\neg }\leftrightarrow \bar{\cdot }$, $T\leftrightarrow U$, $F\leftrightarrow \mathrm{\varnothing }$.

Key: De Morgan's Laws for sets:

$$\overline{A\cup B}=\overline{A}\cap \overline{B},\overline{A\cap B}=\overline{A}\cup \overline{B}$$

Proving Set Identities

1. Element-chasing: show each side is a subset of the other.
2. Set-builder + propositional logic: convert to logical statements and use known equivalences.
3. Membership table: like a truth table but with "in set" (1) / "not in set" (0).

Computer Representation of Sets

Represent subset $A$ of $U=\{u_1,\dots ,u_n\}$ as a bit string of length $n$:

• Bit $i$ = 1 if $u_i\in A$, else 0.

Set operations become bitwise operations:

• Union → bitwise OR
• Intersection → bitwise AND
• Complement → bitwise NOT

---

Section 2.3 — Functions（函数）

Definition: A function $f:A\to B$ assigns to each element of $A$ exactly one element of $B$.

• $A$ = domain (定义域)
• $B$ = codomain (陪域)
• $f(a)=b$: $b$ is the image (像) of $a$; $a$ is the preimage (原像) of $b$
• Range (值域): the set of all images $\{f(a)\mid a\in A\}\subseteq B$

Formally: $\mathrm{\forall }a(a\in A\to \mathrm{\exists }!b(b\in B\wedge f(a)=b))$

Types of Functions

Injection（单射） (one-to-one): $f(a)=f(b)\Rightarrow a=b$ for all $a,b\in A$.
Different inputs give different outputs.

Surjection（满射） (onto): for every $b\in B$, there exists $a\in A$ with $f(a)=b$.
Every element of the codomain is an image.

Bijection（双射） (one-to-one correspondence): both injective AND surjective.

Inverse Functions（反函数）

If $f:A\to B$ is a bijection, its inverse $f^{-1}:B\to A$ is defined by $f^{-1}(b)=a$ iff $f(a)=b$.
Inverse exists if and only if $f$ is a bijection.

Function Composition（函数复合）

Given $g:A\to B$ and $f:B\to C$, the composition $(f\circ g):A\to C$ is defined by $(f\circ g)(x)=f(g(x))$.

Note: $f\circ g\ne g\circ f$ in general.

Floor and Ceiling Functions

• Floor (下取整) $\lfloor x\rfloor$: largest integer $\le x$.
• Ceiling (上取整) $\lceil x\rceil$: smallest integer $\ge x$.

Examples: $\lfloor 2.7\rfloor =2$, $\lceil 2.1\rceil =3$, $\lfloor -2.7\rfloor =-3$.

Useful identity: $\lfloor 2x\rfloor =\lfloor x\rfloor +\lfloor x+1/2\rfloor$ (proof by cases on $\{x\}<1/2$ vs $\ge 1/2$).

Factorial（阶乘）

$f(n)=n!=1\cdot 2\cdot 3\cdots n$, with $0!=1$.

Stirling's approximation: $n!\approx \sqrt{2\pi n}(n/e{)}^n$.

---

Section 2.4 — Sequences and Summations（序列与求和）

A sequence (序列) is a function from a subset of integers to a set $S$. We write $\{a_n\}$.

Geometric progression (等比数列/级数): $a,ar,a{r}^2,a{r}^3,\dots$ with initial term $a$ and common ratio (公比) $r$.

Arithmetic progression (等差数列): $a,a+d,a+2d,\dots$ with initial term $a$ and common difference (公差) $d$.

Recurrence Relations（递推关系）

A recurrence relation (递推关系) expresses $a_n$ in terms of previous terms.

Fibonacci sequence (斐波那契数列): $f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}$.
Values: $0,1,1,2,3,5,8,13,21,\dots$

Solving a recurrence: find a closed formula (闭公式). Method: iteration (forward or backward substitution).

Example: $a_n=a_{n-1}+3$, $a_1=2$:

$$a_n=2+3(n-1)$$

Financial application: compound interest. $P_n=(1.11{)}^n\cdot P_0$. With $P_0=10000$ and 30 years: $P_{30}\approx \mathrm{\$}228,993$.

Summations（求和）

$$\sum _{j=m}^n{a}_j=a_m+a_{m+1}+\cdots +a_n$$

Geometric series: $\sum _{j=0}^{n}a{r}^j=\frac{a(r^{n+1}-1)}{r-1}$ for $r\ne 1$; $=a(n+1)$ for $r=1$.

Useful formulas:

Sum	Formula
$\sum _{k=1}^{n}k$	$\frac{n(n+1)}{2}$
$\sum _{k=1}^n{k}^2$	$\frac{n(n+1)(2n+1)}{6}$
$\sum _{k=1}^n{k}^3$	${\left(\frac{n(n+1)}{2}\right)}^2$
$\sum _{k=0}^n{r}^k$ ($r\ne 1$)	$\frac{r^{n+1}-1}{r-1}$

---

Section 2.5 — Cardinality of Sets（集合的基数）

Definition: $|A|=|B|$ iff there exists a bijection from $A$ to $B$.
$|A|\le |B|$ iff there exists an injection from $A$ to $B$.

Countable set (可数集): either finite, or has the same cardinality as ${\mathbb{Z}}^{+}$.
The cardinality of a countably infinite set is ${\mathrm{\aleph }}_0$ ("aleph null").

An infinite set is countable iff its elements can be listed as a sequence $a_1,a_2,a_3,\dots$

Uncountable set (不可数集): infinite but not countable (e.g., $\mathbb{R}$).

Showing Sets are Countably Infinite

• Positive even integers $E$: bijection $f(n)=2n$ from ${\mathbb{Z}}^{+}$ to $E$. ✓
• Integers $\mathbb{Z}$: list as $0,1,-1,2,-2,3,-3,\dots$ ✓
• Positive rationals ${\mathbb{Q}}^{+}$: use the diagonal enumeration of ${\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$ (Cantor's diagonal argument for countability). ✓
• Finite strings over a finite alphabet: list by length, then lexicographically. ✓
• Set of all Java programs: countable (Java programs are finite strings from finite alphabet). ✓

Properties of countable sets:

1. No infinite set has smaller cardinality than a countable set.
2. Union of finitely many countable sets is countable.
3. Union of countably many countable sets is countable.

Hilbert's Grand Hotel (David Hilbert)

A hotel with countably infinite rooms, all occupied: we can still accommodate a new guest! Move guest in room $n$ to room $n+1$ for all $n$, freeing room 1.

Cantor Diagonalization（康托尔对角线论证）

Theorem: The set of real numbers in $(0,1)$ is uncountable.

Proof: Assume $A=(0,1)$ is countable. List all elements: $r_1,r_2,r_3,\dots$ in decimal form:

$$r_1=0.d_{11}{d}_{12}{d}_{13}\dots$$$$r_2=0.d_{21}{d}_{22}{d}_{23}\dots$$$$r_3=0.d_{31}{d}_{32}{d}_{33}\dots$$

Construct $x=0.x_1{x}_2{x}_3\dots$ where:

$$x_i=\{\begin{array}{ll}3& \text{if }{d}_{ii}\ne 3\\ 4& \text{if }{d}_{ii}=3\end{array}$$

Then $x$ differs from every $r_i$ in at least the $i$-th decimal digit, so $x\notin \{r_1,r_2,\dots \}$. Contradiction! $◻$

Corollary: $|\mathbb{R}|=|(0,1)|={\mathrm{\aleph }}_1>{\mathrm{\aleph }}_0$.

The Continuum Hypothesis (连续统假设) asserts there is no cardinality $\alpha$ with ${\mathrm{\aleph }}_0<\alpha <{\mathrm{\aleph }}_1$. (Proved independent of ZFC axioms by Gödel and Cohen.)

Schröder-Bernstein Theorem: If $|A|\le |B|$ and $|B|\le |A|$, then $|A|=|B|$.

Cantor's Theorem: $|\mathcal{P}(A)|>|A|$ for any set $A$ — the power set always has strictly greater cardinality.

Computability: Since the set of Java programs is countable but the set of functions ${\mathbb{Z}}^{+}\to {\mathbb{Z}}^{+}$ is uncountable, there must exist uncomputable functions (不可计算函数).

---

Section 2.6 — Matrices（矩阵）

A matrix (矩阵) is a rectangular array of numbers. An $m\times n$ matrix has $m$ rows and $n$ columns.

Matrix Arithmetic

Addition: $A+B=[a_{ij}+b_{ij}]$ (matrices must have same dimensions).

Multiplication: $AB=C$ where $c_{ij}=\sum _{k=1}^p{a}_{ik}{b}_{kj}$ ($A$ is $m\times p$, $B$ is $p\times n$).
Note: matrix multiplication is not commutative in general.

Identity matrix (单位矩阵) $I_n$: $n\times n$ matrix with 1's on diagonal, 0's elsewhere.
$A{I}_n=I_{m}A=A$ for $m\times n$ matrix $A$.

Transpose (转置) $A^t$: rows and columns swapped, $[A^t{]}_{ij}=a_{ji}$.

A matrix is symmetric (对称矩阵) if $A=A^t$.

Zero-One Matrices

A zero-one matrix has entries only 0 or 1.

Boolean operations:

• Join $A\vee B$: entry-wise OR.
• Meet $A\wedge B$: entry-wise AND.
• Boolean product $A\odot B$: $c_{ij}=(a_{i1}\wedge b_{1j})\vee (a_{i2}\wedge b_{2j})\vee \cdots \vee (a_{ik}\wedge b_{kj})$.

Boolean powers: $A^{[r]}=A\odot A\odot \cdots \odot A$ ($r$ times), $A^{[0]}=I_n$.

---

Chapter 3: Algorithms（算法）

---

Section 3.1 — Algorithms

Definition: An algorithm is a finite set of precise instructions for performing a computation or solving a problem.

Properties of a good algorithm:

• Input: well-defined input values.
• Output: produces correct output.
• Correctness: produces the right answer.
• Finiteness: terminates after finite steps.
• Effectiveness: each step can be performed exactly.
• Generality: works for all valid inputs.

Searching Algorithms

Linear Search (线性搜索): scan each element from left to right.
Complexity: $\mathrm{\Theta }(n)$ in the worst case.

Binary Search (二分搜索): requires a sorted list.

1. Compare target with middle element.
2. If equal, found. If target is larger, search upper half. If smaller, search lower half.
3. Repeat until the list has 1 element.

Pseudocode:

procedure binary_search(x, a[1..n]):
  i := 1; j := n
  while i < j:
    m := ⌊(i+j)/2⌋
    if x > a[m] then i := m+1
    else j := m
  if x = a[i] then return i
  else return 0

Complexity: $\mathrm{\Theta }(\log n)$ — much better than linear search.

Sorting Algorithms

Bubble Sort (冒泡排序): make passes through the list, swapping adjacent elements that are out of order.
Worst-case complexity: $\mathrm{\Theta }(n^2)$.

Insertion Sort (插入排序): build the sorted array one element at a time.
Worst-case complexity: $\mathrm{\Theta }(n^2)$.

Greedy Algorithms（贪心算法）

A greedy algorithm makes the locally "best" choice at each step. Does not always give the globally optimal solution.

Example: Making change with U.S. coins (quarters, dimes, nickels, pennies). Always pick the largest denomination that fits. This is optimal for standard U.S. coins.

Failure example ("Asiarons" 1, 7, 10): greedy gives 15 = 10+1+1+1+1+1 (6 coins), but optimal is 7+7+1 (3 coins).

Greedy Scheduling: to schedule the most talks (no overlap), always choose the talk with the earliest finishing time among compatible ones. (This is optimal.)

Halting Problem（停机问题）

Claim: There is no algorithm that can always determine whether an arbitrary program halts.

Proof by contradiction: Assume procedure $H(P,I)$ exists. Construct $K(P)$: if $H(P,P)$ says "loops forever," $K(P)$ halts; if $H(P,P)$ says "halts," $K(P)$ loops. Then $K(K)$ leads to contradiction. ∴ $H$ cannot exist.

The halting problem is unsolvable (不可解的).

---

Section 3.2 — The Growth of Functions

Big-O Notation（大O记号）

Definition: $f(x)$ is $O(g(x))$ if there exist constants $C$ and $k$ such that $|f(x)|\le C|g(x)|$ whenever $x>k$.

• $C$ and $k$ are called witnesses (凭证).
• Big-O gives an upper bound on the growth rate.
• We say "$g$ asymptotically dominates $f$."

Example: Show $f(x)=x^2+2x+1$ is $O(x^2)$.
When $x>1$: $x^2+2x+1\le x^2+2x^2+x^2=4x^2$. Take $C=4$, $k=1$.

Polynomial: If $f(x)=a_n{x}^n+\cdots +a_0$ with $a_n\ne 0$, then $f(x)$ is $O(x^n)$.
(The leading term dominates.)

Common Big-O estimates:

• $\sum _{j=1}^{n}j$ is $O(n^2)$
• $n!$ is $O(n^n)$
• $\log (n!)$ is $O(n\log n)$

Big-Omega Notation（大Ω记号）

$f(x)$ is $\mathrm{\Omega }(g(x))$ if there exist $C,k$ such that $|f(x)|\ge C|g(x)|$ for all $x>k$.

Big-Omega gives a lower bound. Note: $f(x)$ is $\mathrm{\Omega }(g(x))$ iff $g(x)$ is $O(f(x))$.

Big-Theta Notation（大Θ记号）

$f(x)$ is $\mathrm{\Theta }(g(x))$ if $f(x)$ is $O(g(x))$ and $f(x)$ is $\mathrm{\Omega }(g(x))$.

Equivalently, there exist $C_1,C_2,k$ such that $C_1|g(x)|\le |f(x)|\le C_2|g(x)|$ for $x>k$.

• $f$ and $g$ are said to be of the same order.
• Example: $\sum _{j=1}^{n}j=\frac{n(n+1)}{2}$ is $\mathrm{\Theta }(n^2)$.

Useful Hierarchies

In order of growth (slowest to fastest):

$$1<\log \log n<\log n<(\log n{)}^c<n^d<n\log n<n^2<n^3<\cdots <2^n<3^n<\cdots <n!$$

Key inequalities:

• (log $n$)${}^c$ is $O(n^d)$ for any $c,d>0$ — but $n^d$ is NOT $O((\log n{)}^c)$.
• $n^d$ is $O(b^n)$ for $b>1$ — but $b^n$ is NOT $O(n^d)$.
• If $c>b>1$: $b^n$ is $O(c^n)$ but NOT vice versa.

---

Section 3.3 — Complexity of Algorithms

Time complexity (时间复杂度): number of operations (comparisons, arithmetic) as a function of input size.
Space complexity (空间复杂度): memory usage (studied in later courses).

We focus on worst-case complexity (最坏情况复杂度) — an upper bound that holds for all inputs.

Complexity of Key Algorithms

Algorithm	Worst-case	Notes
Finding maximum	$\mathrm{\Theta }(n)$
Linear search	$\mathrm{\Theta }(n)$
Binary search	$\mathrm{\Theta }(\log n)$	sorted list required
Bubble sort	$\mathrm{\Theta }(n^2)$
Insertion sort	$\mathrm{\Theta }(n^2)$
Matrix multiplication ($n\times n$)	$O(n^3)$
Boolean matrix product	$O(n^3)$	bit operations

Binary modular exponentiation: computing $b^{n}modm$ uses $O((\log m{)}^2\log n)$ bit operations — very efficient.

Complexity Classes

• Class P (多项式时间类): problems solvable in polynomial time $O(n^k)$.
• Class NP: solutions can be verified in polynomial time, but finding a solution may not be polynomial.
• NP-complete (NP完全): hardest problems in NP; if any one has a polynomial algorithm, all NP problems do.
• Unsolvable (不可解): no algorithm exists (e.g., halting problem).

SAT (satisfiability) is the first NP-complete problem (Cook, 1971).
Big open question: P = NP? — generally believed to be NO.

Intuition on complexity:
For $n=50$, computing $50!$ via brute force requires $1.5\times {10}^{65}$ multiplications (≈ $5\times {10}^{46}$ years), while Gaussian elimination needs $\sim 6\times {10}^6$ multiplications ($\sim 6\times {10}^{-5}$ seconds at ${10}^{11}$ ops/sec).

---

Chapter 4: Number Theory（数论）

---

Section 4.1 — Divisibility and Modular Arithmetic

Divisibility（整除性）

$a\mid b$ ("$a$ divides $b$"): there exists integer $c$ such that $b=ac$.
We say $a$ is a factor (因子) or divisor (因数) of $b$; $b$ is a multiple (倍数) of $a$.

Theorem (Properties of divisibility):
If $a\mid b$ and $a\mid c$, then:

1. $a\mid (b+c)$
2. $a\mid bc$ for any integer $c$
3. If $a\mid b$ and $b\mid c$, then $a\mid c$

Corollary: $a\mid b$ and $a\mid c$ implies $a\mid (mb+nc)$ for any integers $m,n$.

Division Algorithm（带余除法）

For any integer $a$ and positive integer $d$, there exist unique integers $q$ and $r$ with $0\le r<d$ such that:

$$a=dq+r$$

• $d$ = divisor，$a$ = dividend（被除数），$q=a\mathrm{div}d$ = quotient（商），$r=a\mathrm{mod}d$ = remainder（余数）.

Examples:

• $101=11\times 9+2$, so $101\mathrm{div}11=9$, $101\mathrm{mod}11=2$.
• $-11=3\times (-4)+1$, so $-11\mathrm{div}3=-4$, $-11\mathrm{mod}3=1$.

Congruence（同余）

$a\equiv b(\mathrm{mod}m)$: $m\mid (a-b)$. We say $a$ is congruent to $b$ modulo $m$.
Two integers are congruent mod $m$ iff they have the same remainder when divided by $m$.

Theorem: $a\equiv b(\mathrm{mod}m)$ iff $a=b+km$ for some integer $k$.

Theorem (Congruence preserves operations):
If $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$, then:

$$a+c\equiv b+d(\mathrm{mod}m),ac\equiv bd(\mathrm{mod}m)$$

Corollary:
$(a+b)modm=((amodm)+(bmodm))modm$
$abmodm=((amodm)(bmodm))modm$

Caution: Dividing both sides of a congruence by an integer does NOT always preserve congruence. (E.g., $6\equiv 4(\mathrm{mod}2)$ but $3\not\equiv 2(\mathrm{mod}2)$.)

Arithmetic Modulo $m$

${\mathbb{Z}}_m=\{0,1,\dots ,m-1\}$ with operations ${+}_m$ and ${\cdot }_m$ (modular addition and multiplication).

Properties: closure, associativity, commutativity, identity elements (0 for ${+}_m$, 1 for ${\cdot }_m$), distributivity.

Additive inverse of $a$ in ${\mathbb{Z}}_m$ is $m-a$.

---

Section 4.2 — Integer Representations

Any positive integer $n$ can be uniquely expressed in base $b$ ($b>1$):

$$n=a_k{b}^k+a_{k-1}{b}^{k-1}+\cdots +a_{1}b+a_0$$

where $0\le a_i<b$ and $a_k\ne 0$.

Key bases:

• Binary (二进制): base 2, digits = $\{0,1\}$
• Octal (八进制): base 8, digits = $\{0,\dots ,7\}$
• Hexadecimal (十六进制): base 16, digits = $\{0,\dots ,9,\text{A},\dots ,\text{F}\}$

Conversions:

• Decimal → base $b$: repeatedly divide by $b$; remainders (right to left) give the digits.
• Binary ↔ Octal: group binary digits in 3s (right to left).
• Binary ↔ Hex: group binary digits in 4s.

Algorithms for Integer Operations

Binary addition: $O(n)$ bit operations for two $n$-bit integers.
Binary multiplication: $O(n^2)$ bit operations.

Binary Modular Exponentiation (快速模幂): to compute $b^{n}modm$:

• Write $n$ in binary: $n=(a_{k-1}\cdots a_1{a}_0{)}_2$.
• Use repeated squaring: compute $b,b^2,b^4,\dots ,b^{2^{k-1}}(\mathrm{mod}m)$.
• Multiply the terms where $a_i=1$.
• Total: $O((\log m{)}^2\log n)$ bit operations.

---

Section 4.3 — Primes and GCD

Prime Numbers（质数）

A positive integer $p>1$ is prime (质数) if its only positive factors are 1 and $p$. Otherwise it is composite (合数).

Fundamental Theorem of Arithmetic (算术基本定理): Every positive integer $>1$ can be written uniquely as a product of primes (in nondecreasing order).

Sieve of Eratosthenes (埃拉托斯特尼筛法): to find all primes up to $n$:

1. List all integers from 2 to $n$.
2. Strike out all multiples of 2 (except 2 itself), then of 3, then of 5, etc.
3. Stop when you've processed all primes up to $\sqrt{n}$.

Theorem (Euclid): There are infinitely many primes.
Proof: Assume finite list $p_1,\dots ,p_n$. Let $q=p_1{p}_2\cdots p_n+1$. Since $q$ is not divisible by any $p_i$, either $q$ is prime or has a prime factor not in the list. Contradiction. $◻$

Mersenne primes (梅森质数): primes of the form $2^p-1$ where $p$ is prime.

Prime Number Theorem (质数定理): The number of primes $\le x$ is approximately $x/\ln x$.

Goldbach's Conjecture (哥德巴赫猜想): every even integer $>2$ is the sum of two primes. (Unproved.)

Twin Prime Conjecture (孪生质数猜想): infinitely many pairs of primes differing by 2. (Unproved, but Zhang Yitang proved there are infinitely many prime pairs differing by $<70,000,000$.)

Greatest Common Divisor (GCD)（最大公因数）

$gcd(a,b)$ = largest integer $d$ such that $d\mid a$ and $d\mid b$.

Integers $a$ and $b$ are relatively prime (互质) if $gcd(a,b)=1$.

Using prime factorizations: if $a=\prod p_i^{a_i}$ and $b=\prod p_i^{b_i}$, then
$gcd(a,b)=\prod p_i^{min(a_i,b_i)}$.

Least Common Multiple (LCM) (最小公倍数): $\mathrm{lcm}(a,b)=\prod p_i^{max(a_i,b_i)}$.

Key relationship: $\mathrm{lcm}(a,b)\cdot gcd(a,b)=a\cdot b$.

Euclidean Algorithm（欧几里得算法）

Key lemma: $gcd(a,b)=gcd(b,amodb)$.

Algorithm: repeatedly replace $(a,b)\leftarrow (b,amodb)$ until $b=0$; then $gcd=a$.

Example: $gcd(287,91)$:

$$287=3\cdot 91+14\Rightarrow gcd(287,91)=gcd(91,14)$$$$91=6\cdot 14+7\Rightarrow gcd(91,14)=gcd(14,7)$$$$14=2\cdot 7+0\Rightarrow gcd(14,7)=7$$

Time complexity: $O(\log b)$ divisions.

Bézout's Theorem（贝祖定理）

If $a$ and $b$ are positive integers, there exist integers $s$ and $t$ such that:

$$gcd(a,b)=sa+tb$$

$s$ and $t$ are called Bézout coefficients (贝祖系数). The equation is Bézout's identity.

Finding Bézout coefficients: work backwards through the Euclidean algorithm.

Example: Express $gcd(252,198)=18$ as a linear combination:

• $252=1\cdot 198+54$
• $198=3\cdot 54+36$
• $54=1\cdot 36+18$
• $36=2\cdot 18$

Working back: $18=54-1\cdot 36=54-(198-3\cdot 54)=4\cdot 54-198=4(252-198)-198=4\cdot 252-5\cdot 198$.

Lemma: If $gcd(a,b)=1$ and $a\mid bc$, then $a\mid c$.
Lemma: If $p$ is prime and $p\mid a_1{a}_2\cdots a_n$, then $p\mid a_i$ for some $i$.

---

Section 4.4 — Solving Congruences & Cryptography

Linear Congruences（线性同余方程）

A linear congruence is of the form $ax\equiv b(\mathrm{mod}m)$.

An inverse of $a$ modulo $m$ is an integer $\overline{a}$ such that $\overline{a}a\equiv 1(\mathrm{mod}m)$.

Theorem 1: If $gcd(a,m)=1$, then an inverse of $a$ modulo $m$ exists and is unique modulo $m$.

Proof: By Bézout's theorem, there exist $s,t$ with $sa+tm=1$. Then $sa\equiv 1(\mathrm{mod}m)$, so $s$ is an inverse.

Finding inverses: use the Euclidean algorithm to find Bézout coefficients.

Solving $ax\equiv b(\mathrm{mod}m)$: Find inverse $\overline{a}$ of $a(\mathrm{mod}m)$, then $x\equiv \overline{a}b(\mathrm{mod}m)$.

Example: Solve $3x\equiv 4(\mathrm{mod}7)$.
Inverse of 3 mod 7: $7=2\cdot 3+1$, so $-2\cdot 3+1\cdot 7=1$, hence $\overline{a}=-2\equiv 5$.
$x\equiv (-2)(4)=-8\equiv 6(\mathrm{mod}7)$.

Chinese Remainder Theorem（中国剩余定理 / 秦九韶定理）

Theorem (CRT): Given pairwise relatively prime moduli $m_1,\dots ,m_n$ and arbitrary integers $a_1,\dots ,a_n$, the system:

$$x\equiv a_1(\mathrm{mod}{m}_1),x\equiv a_2(\mathrm{mod}{m}_2),\dots ,x\equiv a_n(\mathrm{mod}{m}_n)$$

has a unique solution modulo $m=m_1{m}_2\cdots m_n$.

Construction: Let $M_k=m/m_k$. Find $y_k$ (inverse of $M_k$ mod $m_k$). Then:

$$x=a_1{M}_1{y}_1+a_2{M}_2{y}_2+\cdots +a_n{M}_n{y}_n(\mathrm{mod}m)$$

Sun-Tsu's problem: $x\equiv 2(\mathrm{mod}3)$, $x\equiv 3(\mathrm{mod}5)$, $x\equiv 2(\mathrm{mod}7)$.
$m=105$, $M_1=35,M_2=21,M_3=15$.
Inverses: $y_1=2$ (since $35\cdot 2=70\equiv 1(\mathrm{mod}3)$), $y_2=1$, $y_3=1$.
$x=2\cdot 35\cdot 2+3\cdot 21\cdot 1+2\cdot 15\cdot 1=140+63+30=233\equiv 23(\mathrm{mod}105)$.

Back Substitution is an alternative method: rewrite first congruence as equality, substitute into next, etc.

Fermat's Little Theorem（费马小定理）

Theorem: If $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$.
Equivalently, $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$.

Example: Find $7^{222}mod11$.
By FLT: $7^{10}\equiv 1(\mathrm{mod}11)$. Then $7^{222}=7^{22\cdot 10+2}=(7^{10}{)}^{22}\cdot 7^2\equiv 1^{22}\cdot 49\equiv 5(\mathrm{mod}11)$.

Euler's Theorem (欧拉定理) generalizes this: if $gcd(a,n)=1$, then $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$, where $\varphi (n)$ is Euler's totient function (the number of integers $\le n$ relatively prime to $n$).

Pseudoprimes（伪质数）

If $2^{n-1}\equiv 1(\mathrm{mod}n)$ but $n$ is composite, $n$ is a pseudoprime to the base 2.

A Carmichael number (卡米切尔数) satisfies $b^{n-1}\equiv 1(\mathrm{mod}n)$ for all $b$ with $gcd(b,n)=1$, yet is composite. Example: $561=3\cdot 11\cdot 17$.

Primitive Roots（原根）

A primitive root modulo a prime $p$ is an integer $r\in {\mathbb{Z}}_p^{\ast }$ such that every nonzero element of ${\mathbb{Z}}_p$ is a power of $r$ (mod $p$).

Every prime $p$ has a primitive root.

$g$ is a primitive root mod $m$ iff the multiplicative order of $g$ mod $m$ equals $\varphi (m)$.

Discrete Logarithm（离散对数）

If $r$ is a primitive root mod $p$ and $r^e\equiv a(\mathrm{mod}p)$, then $e$ is the discrete logarithm of $a$ modulo $p$ to base $r$, written ${\log }_{r}a=e$.

Asymmetry: Given $r$ and $e$, computing $a=r^{e}modp$ is easy. But given $r$ and $a$, finding $e$ (discrete log) is believed to be computationally hard — no polynomial-time algorithm is known. This hardness underpins many cryptographic protocols.

---

Section 4.5 — Applications of Number Theory

Hashing Functions（哈希函数）

A hashing function $h$ assigns memory location $h(k)$ to a record with key $k$.

Common: $h(k)=kmodm$ (maps to $\{0,1,\dots ,m-1\}$).

Collision (碰撞): when two keys map to the same location. Resolved by linear probing: $h(k,i)=(h(k)+i)modm$.

Pseudorandom Numbers（伪随机数）

Linear congruential method: given modulus $m$, multiplier $a$, increment $c$, seed $x_0$:

$$x_{n+1}=(a{x}_n+c)modm$$

The sequence is periodic with period at most $m$.

Example: $m=9,a=7,c=4,x_0=3$: generates $3,7,8,6,1,2,0,4,5,3,\dots$ (period 9).

Check Digits（校验码）

UPC (Universal Product Code): 12-digit code. Check digit $x_{12}$ satisfies:

$$3x_1+x_2+3x_3+\cdots +3x_{11}+x_{12}\equiv 0(\mathrm{mod}10)$$

ISBN-10: 10-digit code. Check digit $x_{10}$ satisfies:

$$\sum _{i=1}^{10}i\cdot x_i\equiv 0(\mathrm{mod}11)(x_{10}\text{ may be 10 = X})$$

These check digits detect single-digit errors and transposition errors.

Public Key Cryptography and RSA

Private key cryptosystem: encryption and decryption keys are related; knowing one lets you find the other. All parties must share the secret key.

Public key cryptosystem (公钥密码系统): encryption key is public; decryption key is kept private. Knowing how to encrypt does NOT help decrypt.

RSA Cryptosystem (Rivest–Shamir–Adleman, 1976):

Setup (Key generation):

1. Choose two large primes $p$ and $q$.
2. Compute $n=pq$ and $\varphi (n)=(p-1)(q-1)$.
3. Choose $e$ with $gcd(e,\varphi (n))=1$ (public exponent).
4. Find $d$ = inverse of $e$ modulo $\varphi (n)$ (private key).

Public key: $(n,e)$. Private key (解密密钥): $d$.

Encryption: $C=M^{e}modn$.
Decryption: $M=C^{d}modn$.

Why it works: $C^d=M^{ed}=M^{k\varphi (n)+1}=(M^{\varphi (n)}{)}^k\cdot M\equiv 1^k\cdot M=M(\mathrm{mod}n)$ (by Euler's Theorem, assuming $gcd(M,n)=1$).

Security: relies on the fact that factoring large $n=pq$ is computationally infeasible (no known efficient algorithm for numbers with hundreds of digits).

Example: Key $(2537,13)$, $2537=43\times 59$.
Encrypt "STOP" = 1819 1415:
$C_1={1819}^{13}mod2537=2081$, $C_2={1415}^{13}mod2537=2182$.
Ciphertext: 2081 2182.

Decrypt with $d=937$:
$M=C^{937}mod2537$.

Diffie-Hellman Key Exchange（密钥交换协议）

Alice and Bob agree on prime $p$ and primitive root $a$.

• Alice chooses secret $k_1$, sends $a^{k_1}modp$ to Bob.
• Bob chooses secret $k_2$, sends $a^{k_2}modp$ to Alice.
• Shared secret: $(a^{k_2}{)}^{k_1}modp=(a^{k_1}{)}^{k_2}modp=a^{k_1{k}_2}modp$.

Security: finding $k_1$ from $a^{k_1}modp$ is the discrete logarithm problem — believed hard.

Digital Signatures（数字签名）

To prove a message came from Alice:

• Alice encrypts (signs) with her private key $d$: $S=M^{d}modn$.
• Anyone can verify with Alice's public key $e$: $S^e\equiv M(\mathrm{mod}n)$.

Combining encryption and signature:

• Use recipient Bob's public key for confidentiality (only Bob can read).
• Use Alice's private key for authentication (proves it's from Alice).

---

Summary of Key Formulas

Chapter 1 — Logic

Concept	Formula
Contrapositive	$p\to q\equiv \mathrm{\neg }q\to \mathrm{\neg }p$
De Morgan (prop)	$\mathrm{\neg }(p\wedge q)\equiv \mathrm{\neg }p\vee \mathrm{\neg }q$
De Morgan (quant)	$\mathrm{\neg }\mathrm{\forall }xP(x)\equiv \mathrm{\exists }x\mathrm{\neg }P(x)$
Conditional	$p\to q\equiv \mathrm{\neg }p\vee q$
Biconditional	$p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$

Chapter 2 — Sets and Functions

Concept	Formula
Power set size	$
Inclusion-Exclusion	$
Geometric series	$\sum _{k=0}^n{r}^k=\frac{r^{n+1}-1}{r-1}$
Sum of first $n$ integers	$\frac{n(n+1)}{2}$

Chapter 3 — Algorithms

Algorithm	Complexity
Binary search	$\mathrm{\Theta }(\log n)$
Bubble/Insertion sort	$\mathrm{\Theta }(n^2)$
Matrix multiply	$O(n^3)$

Chapter 4 — Number Theory

Concept	Formula
Division algorithm	$a=dq+r$, $0\le r<d$
Congruence	$a\equiv b(\mathrm{mod}m)$ iff $m\mid (a-b)$
Bézout's identity	$gcd(a,b)=sa+tb$
lcm-gcd relation	$\mathrm{lcm}(a,b)\cdot gcd(a,b)=ab$
Fermat's Little Thm	$a^{p-1}\equiv 1(\mathrm{mod}p)$ for prime $p$, $p\nmid a$
Euler's Theorem	$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ for $gcd(a,n)=1$
RSA encrypt	$C=M^{e}modn$
RSA decrypt	$M=C^{d}modn$

---

End of Comprehensive Lecture Notes
Covers: Lectures 1–11 | Sections 1.1–1.8, 2.1–2.6, 3.1–3.3, 4.1–4.5