南方科技大学 计算机科学与工程系 11812804 董正
[TOC]
A proposition is a declarative statement that is either true or false.
| 英文名 | 中文名 | 含义 |
|---|---|---|
| Tautology | 永真式 | Always true |
| Contradiction | 永假式 | Always false |
| Contingency | 偶然式 | Neither a tautology nor a contradiction |
| 表达式 | 英文名 | 中文名 |
|---|---|---|
| Negation | 否定联结词 | |
| Conjunction | 合取联结词 | |
| Disjunction | 析取联结词 | |
| Exclusive or | 异或联结词 | |
| Implication | 蕴含联结词 | |
| Biconditional | 等价联结词 |
- 真值表：
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
-
$p \to q$ is read in a variety of equivalent ways:- if p then q
- p implies q
- p is sufficient for q
- q is necessary for p
- q follows from p
- q unless $\lnot$p
- p only if q
-
The converse of
$p \to q$ is$q \to p$ . The contrapositive of$p \to q$ is$\lnot q \to \lnot p$ . The inverse of$p \to q$ is$\lnot p \to \lnot q$ .
| 表达式 | 英文名 | 中文名 |
|---|---|---|
| $p \land T \equiv p$ |
Identity laws | 同一律 (恒等律) |
| $p \lor T \equiv T$ |
Domination laws | 零律 (支配律) |
| $p \land p \equiv p$ |
Idempotent laws | 等幂律 (幂等律) |
| Double negation law | 双重否定律 | |
| $p \land q \equiv q \land p$ |
Commutative laws | 交换律 |
| $(p \lor q) \lor r \equiv p \lor (q \lor r)$ |
Associative laws | 结合律 |
| $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ |
Distributive laws | 分配律 |
| $\lnot (p \land q) \equiv \lnot p \lor \lnot q$ |
De Morgan's laws | 摩根律 |
| $p \lor (p \land q) \equiv p$ |
Absorption laws | 吸收律 |
| $p \land \lnot p \equiv F$ |
Negation laws | 否定律 |
| Useful law | 蕴含等值式 | |
| 逆否律 | ||
| 输出律 | ||
| 归谬律 |
- Constant: models a specific object
- Variable: represents object of specific type
- Predicate: represents properties or relations among objects
- A predicate is a statement
$P(x_1, x_2, \dots, x_n)$ that contains$n$ variables$x_1, x_2, \dots, x_n$ and becomes a proposition when specific values are substituted for the variables$x_i$ . - The universe (domain)
$D$ of the predicate variables$x_1, x_2, \dots, x_n$ is the set of all values that may be substituted in place of the variables. 论域 - The truth set of
$P(x_1, x_2, \dots, x_n)$ is the set of all values of the predicate variables$x_1, x_2, \dots, x_n$ such that the proposition$P(x_1, x_2, \dots, x_n)$ is true. 真值集
Examples:
- Example 1: (Predicates with one variable)
Let
$P(x)$ be the predicate$x^2 > x$ with universe of the real numbers.- What are the truth values of
$P(2)$ and$P(1)$ ? What is the truth set of$P(x)$ ? -
$P(2) \equiv T, P(1) \equiv F$ $x > 1$ or$x < 0$
- What are the truth values of
- Example 2: (Predicates with two variables)
Let
$Q(x, y)$ be the predicate$x = y + 3$ with universe of the real numbers.- What are the truth values of
$Q(1, 2)$ and$Q(3, 0)$ ? What is the truth set of$Q(x, y)$ ? -
$Q(1, 2) \equiv F, Q(3, 0) \equiv T$ $(a, a - 3)$ for all real numbers$a$
- What are the truth values of
-
Universal Quantifier 全称量词
$\forall$ - The universal quantification of
$P(x)$ is the proposition: "$P(x)$ is true for all values of$x$ in the universe of discourse." denoted by$\forall x \ P(x)$ , and is expressed as for every$x$ ,$P(x)$ .
- The universal quantification of
-
Existential Quantifier 存在量词
$\exist$ - The existential quantification of
$P(x)$ is the proposition: "There exists an element in the universe of discourse such that$P(x)$ is true." denoted by$\exist x \ P(x)$ , and is expressed as there is an$x$ such that$P(x)$ .
- The existential quantification of
-
Quantified Statement 量化命题的真值
Statement When true? When false? $\forall x \ P(x)$ $P(x)$ is true for all$x$ There is an $x$ where$P(x)$ is false$\exist x \ P(x)$ There is some $x$ for which$P(x)$ is true$P(x)$ is false for all$x$ $\forall x \ P(x)$ is true whenever$P(x_1) \land P(x_2) \land \dots \land P(x_n)$ is true$\exist x \ P(x)$ is true whenever$P(x_1) \lor P(x_2) \lor \dots \lor P(x_n)$ is true. -
Properties of Quantifiers 量词的性质
- The truth values of
$\forall x \ P(x)$ and$\exist x \ P(x)$ depend on both the propositional function$P(x)$ and the universe. - The quantifiers
$\forall$ and$\exists$ have higher precedence than all the logical operators. Example:$\forall x \ P(x) \lor Q(x)$ means$(\forall x \ P(x)) \lor Q(x)$ rather than$\forall x \ (P(x) \lor Q(x))$
- The truth values of
-
量词的摩根律
-
$\lnot \forall x \ P(x) \equiv \exists x \ \lnot P(x)$ - Sentence: Nothing is perfect.
translation:
$\lnot \exists x \ Perfect(x)$ translation:$\forall x \ \lnot Perfect(x)$ (Everything is imperfect.)
- Sentence: Nothing is perfect.
translation:
-
$\lnot \exists x \ P(x) \equiv \forall x \ \lnot P(x)$ - Sentence: Not all horses are white.
translation:
$\lnot \forall x \ (Horse(x) \to White(x))$ translation:$\exists x \ (Horse(x) \land \lnot White(x))$ (There is a horse that is not white.) logically equivalent to$\exists x \ \lnot (Horse(x) \to White(x))$
- Sentence: Not all horses are white.
translation:
$\lnot \forall x \exists y \ P(x, y) \equiv \exists x \forall y \ \lnot P(x, y)$
-
==$\forall$ 用
-
Sentence: All SUSTech students are smart.
-
universe: SUSTech students translation:
$\forall x \ Smart(x)$ - universe: all students
translation:
$\forall x \ (At(x, SUSTech) \to Smart(x))$ - Q: What about this?
$\forall x \ (At(x, SUSTech) \land Smart(x))$ This means every student is at SUSTech and is smart! - universe: people
translation:
$\forall x \ (Student(x) \land At(x, SUSTech) \to Smart(x))$
- universe: all students
translation:
-
Sentence: Someone at SUSTech is smart.
- universe: all SUSTech affiliates
translation:
$\exists x \ Smart(x)$ - universe: people
translation:
$\exists x \ (At(x, SUSTech) \land Smart(x))$ 存在一个人，他在南科大并且聪明
- universe: all SUSTech affiliates
translation:
-
Q: What about this?
$\exists x \ (At(x, SUSTech) \to Smart(x))$ This is even true if there is anyone who is not at SUSTech! 存在一个人，如果他在南科大，那么他聪明 明显意思不对 而且根据逻辑蕴含的真值表，不在南科大的人都能使命题为真
-
The order of nested quantifiers matters if quantifiers are of different type.
$\forall x \exists y \ P(x, y) \not\equiv \exists y \forall x \ P(x, y)$ -
The order of nested quantifiers does no matter if quantifiers are of the same type.
$\forall x \forall y \ P(x, y) \equiv \forall y \forall x \ P(x, y)$ $\exists x \exists y \ P(x, y) \equiv \exists y \exists x \ P(x, y)$ -
真值表
Statement When true? When false? $\forall x \forall y \ P(x, y)$ $P(x,y)$ is true for every pair$(x,y)$ There is a pair for which $P(x,y)$ is false$\forall x \exists y \ P(x, y)$ For every $x$ there is a$y$ for which$P(x,y)$ is trueThere is an $x$ such that$P(x,y)$ is false for every$y$ $\exists x \forall y \ P(x, y)$ There is an $x$ for which$P(x,y)$ is true for every$y$ For every $x$ there is a$y$ for which$P(x,y)$ is false$\exists x \exists y \ P(x, y)$ There is a pair $(x,y)$ for which$P(x,y)$ is true$P(x,y)$ is false for every pair$(x,y)$ -
例. Let
$L(x, y)$ be the statement "$x$ loves$y$ ", where the domain for both$x$ and$y$ consists of all people in the world. Use quantifiers to express each of these statement.(a) Everybody loves Jerry. (b) Everybody loves somebody. (c) There is somebody whom everybody loves. (d) Nobody loves everybody. (e) There is somebody whom Lydia does not love. (f) There is somebody whom no one loves. (g) There is exactly one person whom every body loves. (h) There are exactly two people whom Lynn loves. (i) Everyone loves himself or herself. (j) There is someone who loves no one besides himself or herself.
$\forall x \ L(x, Jerry)$ $\forall x \exists y \ L(x, y)$ $\exists y \forall x \ L(x, y)$ $\lnot \exists x \forall y \ L(x, y)$ $\exists y \ \lnot L(Lydia, y)$ $\exists y \lnot \exists x \ L(x, y)$ $\exists y(\forall x \ L(x, y) \land \forall z(\forall x \ L(x, z) \to z = y))$ $\exists x \exists y ((x\neq y)\land(\forall z \ L(Lynn, z) \to (z=x \lor z=y)))$ $\forall x \ L(x, x)$ $\exists x\forall y(L(x,y)\leftrightarrow x=y)$
- 公理: An axiom or postulate is a statement or proposition which is regarded as being established, accepted, or self-evidently true.
- 定理: A theorem is a statement that can be proved to be true.
- 引理: A lemma is a statement that can be proved to be true, and is used in proving a theorem or proposition.
- 推论: corollary
- 证明: A proof provides an argument supporting the validity of the statement, and may use premises, axioms, lemmas, results of other theorems, etc.
- In formal proofs, steps follow logically from the set of premises, axioms, lemmas, and other theorems.
- Informal proof: the steps of the proofs are not expressed in any formal language of logic. (实际中使用的语言说明+公式的证明方式就是informal proof)
| 中文名 | 英文名 | 内容 | 相关永真式 |
|---|---|---|---|
| 肯定前件式 (假言推理) |
Modus Ponens | ||
| 否定后件式(取拒式) | Modus Tollens | ||
| 假言三段论 | Hypothetical Syllogism | ||
| 选言三段论 (析取三段论) |
Disjunctive Syllogism | ||
| 附加律 | Addition | ||
| 化简律 | Simplification | ||
| 合取律 | Conjunction | ||
| 归结原理 (消解律) |
Resolution |
Example:
-
"It is not sunny this afternoon and it is colder than yesterday."
$\lnot p \land q$ "We will go swimming only if it is sunny."$r \to p$ "If we do not go swimming then we will take a canoe trip."$\lnot r \to s$ "If we take a canoe trip, then we will be home by sunset."$s \to t$ Show that all these lead to a conclusion: We will be home by sunset.$t$ p - It is sunny this afternoon. q - It is colder than yesterday. r - We will go swimming. s - We will take a canoe trip. t - We will be home by sunset.
-
Translation:
premises:
$\lnot p \land q$ ,$r \to p$ ,$\lnot r \to s$ ,$s \to t$ conclusion:$t$ -
Proof:
| 中文名 | 英文名 | 内容 |
|---|---|---|
| 全称实例 | Universal Instantiation (UI) | |
| 全称引入 | Universal Generalization (UG) | |
| 存在实例 | Existential Instantiation (EI) | |
| 存在引入 | Existential Generalization (EG) |
Example:
-
"A student in this class has not read the book."
$\exists x(C(x) \land \lnot B(x))$ "Everyone in this class passed the first exam."$\forall x (C(x)\to P(x))$ Show that all these lead to a conclusion: Someone who passed the first exam has not read the book.$\exists x (P(x)\land \lnot B(x))$ C(x) - x is in this class. B(x) - x has read the book. P(x) - x passed the first exam.
-
Translation:
premises:
$\exists x(C(x) \land \lnot B(x))$ ,$\forall x (C(x)\to P(x))$ conclusion:$\exists x (P(x)\land \lnot B(x))$ -
Proof:
- Direct Proof
$p \to q$ is proved by showing that if$p$ is true then$q$ follows - Proof by Contrapositive
Show the contrapositive:
$\lnot q \to \lnot p$ - Proof by Contradiction
Show that
$(p \land \lnot q)$ contradicts the assumptions - Proof by Cases Give proofs for all possible cases
- Proof of Equivalence
$p \leftrightarrow q$ is replaced with$(p \to q) \land (q \to p)$ - Vacuous Proof
To prove
$p \to q$ , suppose that$p$ (the hypothesis) is always false, then$p \to q$ is always true. - Trivial Proof
To prove
$p \to q$ , suppose that$q$ (the conclusion) is always true, then$p \to q$ is always true.
Example:
-
Prove that
$\sqrt[3]2$ is irrational. (informal proof)Suppose
$\sqrt[3]2$ is rational, then$\exists m,n \in Z$ such that$gcd(m,n)=1$ and$\sqrt[3]2=\frac mn$ . So$m^3=2n^3$ . Therefore$m$ is even, i.e.$\exists k\in Z,m=2k$ . Then$m^3=8k^3$ , and$n^3=4k^3$ . Hence,$n$ is also even, which means$m, n$ have a common factor 2, and contradicts to the assumption that$gcd(m,n) = 1$ . Thus,$\sqrt[3]2$ is irrational.
-
A set is an unordered collection of objects. These objects are called elements or members.
-
集合的表示方法
-
花名册方法 roster method
例:
$S={1, 2, 3,3.5},\ N={0,1,2,3,\dots}$ -
集合构造器 set builder
例:
$A={x \in N | x<5 }$ -
区间
例:
$(1,7]$
-
-
常用集合的符号
-
$\mathbb R$ : 实数集 -
$\mathbb N$ : 自然数集 -
$\mathbb N_+$ : 正整数集 -
$\mathbb Z$ : 整数集 -
$\mathbb Q$ : 有理数集 -
$\mathbb C$ : 复数集
-
-
集合相等
Two sets
$A, B$ are equal if and only if$\forall x(x\in A \leftrightarrow x\in B)$ -
空集 empty set/ null set
不含任何元素的集合，符号$\emptyset$或${}$
注意$\empty\neq{\empty}$
-
全集 universal set
The universal set is the set of all objects under consideration, denoted by
$U$ .
-
A set
$A$ is called to be a subset of$B$ if and only if every element of$A$ is also an element of$B$ $(\forall x(x \in A \to x \in B))$ , denoted by$A \subseteq B$ .$B$ 称作$A$的超集 -
真子集
If
$A \subseteq B$ , but$A \neq B$ , then we say$A$ is a proper subset of$B$ , denoted by$A \subset B$ $(\forall x(x \in A \to x \in B) \land \exists x(x \in B \land x \notin A))$ . -
$\emptyset \subseteq S$ 空集是任何集合的子集Proof: By definition, we need to prove
$\forall x(x \in \emptyset \to x \in S)$ . Since the empty set does not contain any element,$x \in \emptyset$ is always false. Then the implication is always true. -
$S \subseteq S$ -
$A=B \leftrightarrow A \subseteq B \land B \subseteq A$
-
Let
$S$ be a set. If there are exactly$n$ distinct elements in$S$ where$n$ is a nonnegative integer, we say that$S$ is a finite set and$n$ is the cardinality of$S$ , denoted by$|S|$ .例:
$|\emptyset|=0$ -
A set is infinite if it is not finite.
-
Given a set
$S$ , the power set of$S$ is the set of all subsets of the set$S$ , denoted by$\mathcal{P}(S)$ .$S$ 的子集组成的集合. -
$|S|=n\to |\mathcal{P}(s)|=2^n$ .含有$n$个元素的集合有$2^n$个子集.
-
元组 Tuple
The ordered n-tuple
$(a_1, a_2, \dots , a_n)$ is the ordered collection that has$a_1$ as its first element and$a_2$ as its second element and so on until$a_n$ as its last element. 有序n元组例: n维点坐标
2个元素的元组称为序偶
-
两个集合的笛卡尔积
Let
$A$ and$B$ be sets. The Cartesian product of$A$ and$B$ , denoted by$A \times B$ , is the set of all ordered pairs$(a, b)$ , where$a \in A$ and$b \in B$ . Hence$A \times B = {(a, b)| a \in A \land b \in B}$ .Example:
$A = {1,2}, B = {a,b,c}$ $A \times B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}$ -
$n$ 个集合的笛卡尔积The Cartesian product of the sets
$A_1,A_2, \dots ,A_n$ , denoted by$A_1 \times A_2 \times \dots \times A_n$ , is the set of ordered n-tuples$(a_1, a_2, \dots, a_n)$ where$a_i \in A_i$ for$i = 1, 2,\dots , n$ .$A_1 \times A_2 \times \dots \times A_n = {(a_1, a_2, \dots , a_n)|\ a_i \in A_i \ for\ i = 1, 2, \dots, n}$ Example:
$A={0,1}$ ,$B={1,2}$,$C={0,1,2}$$A \times B \times C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}$ -
性质
$A\times B\neq B\times A$ $|A\times B|=|A|\times|B|$
-
Union(并): The union of the sets
$A$ and$B$ , denoted by$A \cup B$ , is the set${x|x\in A \lor x\in B}$ .$\bigcup_{i=1}^{n} A_i=A_1\cup A_2\cup\dots\cup A_n$ -
Intersection(交): The intersection of the sets
$A$ and$B$ , denoted by$A \cap B$ , is the set${x|x\in A \land x\in B}$ .$\bigcap_{i=1}^{n} A_i=A_1\cap A_2\cap\dots\cap A_n$ Two sets
$A$ and$B$ are called disjoint if$A \cap B=\emptyset$ . -
Complement(补): If
$A$ is a set, then the complement of the set$A$ (with respect to$U$ ), denoted by$\bar{A}$ is the set$U - A$ ,$\bar{A}={x\in U|x\notin A}$. -
Difference(差): The difference of
$A$ and$B$ , denoted by$A - B$ , is the set containing the elements of$A$ that are not in$B$ .$A - B ={x|x\in A \land x\notin B} = A\cap \bar{B}$
| 内容 | 英文名 | 中文名 |
|---|---|---|
| $A\cup\empty=A$ |
Identity laws | 恒等律 |
| $A\cup U=U$ |
Domination laws | 支配律 |
| $A\cup A=A$ |
Idempotent laws | 幂等律 |
| Complementation law | 补律 | |
| $A\cup B=B\cup A$ |
Commutative laws | 交换律 |
| $A\cup(B\cup C)=(A\cup B)\cup C$ |
Associative laws | 结合律 |
| $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ |
Distributive laws | 分配律 |
| $\overline{A\cup B}=\bar{A}\cap\bar{B}$ |
De Morgan's laws | 摩根律 |
| $A\cup(A\cap B)=A$ |
Absorption laws | 吸收律 |
| $A\cup\bar{A}=U$ |
Complement laws | 互补律 |
| $ | A\cup B | = |
-
Prove that
$\overline{A\cap B}=\bar{A}\cup\bar{B}$ $A$ $B$ $\bar{A}$ $\bar{B}$ $\overline{A\cap B}$ $\bar{A}\cup\bar{B}$ 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1表示在集合中，0表示不在集合中
-
集合的计算机表示
例:
$U={1,2,3,4,5,6,7,8}$ ,$A={1,2,3,6,8}$ ,$B={2,4,5,6,7}$ 表示成比特串, A: 11100101, B: 01011110, 之后转为位运算
-
Let
$A$ and$B$ be two sets. A function from$A$ to$B$ , denoted by$f : A \to B$ , is an assignment of exactly one element of B to each element of A. We write$f(a) = b$ if$b$ is the unique element of$B$ assigned by the function$f$ to the element$a$ of$A$ . -
函数也称为映射(mapping)或变换(transformation)
-
函数的表示方式
- Explicitly state the assignments between elements of the two sets. eg.
$1\mapsto a$ - By a formula.
- Explicitly state the assignments between elements of the two sets. eg.
-
$(f_1+f_2)(x)=f_1(x)+f_2(x)$ $(f_1f_2)(x)=f_1(x)f_2(x)$ -
Let
$f$ be a function from$A$ to$B$ . We say that$A$ is the domain of$f$ and$B$ is the codomain(陪域) of$f$ . If$f(a) = b$ ,$b$ is called the image of$a$ and$a$ is a preimage of$b$ . The range of$f$ is the set of all images of elements of$A$ , denoted by$f(A)$ . We also say$f$ maps$A$ to$B$ . -
==子集的像==
For a function
$f : A \to B$ and$S \subseteq A$ , the image of$S$ is a subset of$B$ that consists of the images of the elements of$S$ , denoted by$f (S) (f (S) = {f(s)|s\in S})$ .
-
单射(一对一) Injective (One-to-One) Function
A function
$f$ is called one-to-one or injective, if and only if$f (x) = f (y)$ implies$x = y$ for all$x, y$ in the domain of$f$ . In this case,$f$ is called an injection.Contrapositive: A function is one-to-one if and only if
$f (x) \neq f (y)$ whenever$x \neq y$ .一个萝卜一个坑
-
满射(映上) Surjective (Onto) Function
A function
$f$ is called onto or surjective, if and only if for every$b \in B$ there is an element$a \in A$ such that$f (a) = b$ . In this case,$f$ is called a surjection.A function is onto if and only if all codomain elements are covered (
$f (A) = B$ ).把坑填满
-
双射(一一对应) Bijective Function (One-to-One Correspondence)
A function
$f$ is called bijective, if and only if it is both one-to-one and onto.
-
相关证明
目的 方法 To show that $f$ is injectiveShow that if $f (x) = f (y)$ for all$x, y \in A$ , then$x = y$ To show that $f$ is not injectiveFind specific element $x, y \in A$ such that$x \neq y$ and$f (x) = f (y)$ To show that $f$ is surjectiveConsider an arbitrary element $y \in B$ and find an element$x \in A$ such that$f (x) = y$ To show that $f$ is not surjectiveFind a specific element $y \in B$ such that$f (x) \neq y$ for all$x \in A$ -
For a function
$f : A \to B$ with$|A| = |B| = n$ ,$f$ is one-to-one if and only if$f$ is onto.
-
反函数
Let
$f : A \to B$ be a bijection. The inverse of$f$ is the function that assigns to an element$b$ belonging to$B$ the unique element$a$ in$A$ such that$f(a) = b$ , denoted by$f^{-1}$ . Hence,$f ^{-1}(b) = a$ when$f (a) = b$ . In this case,$f$ is called invertible. -
复合函数
Let
$f$ be a function from$B$ to$C$ and let$g$ be a function from$A$ to$B$ . The composition of the functions$f$ and$g$ , denoted by$f \circ g$ , is defined by$(f \circ g)(x) = f (g(x))$ .- Suppose that
$f$ is a bijection from$A$ to$B$ . Then$f \circ f^{-1} = I_B$ and$f^{-1}\circ f = I_A$ , Since$(f^{-1} \circ f )(a) = f ^{-1}(f (a)) = f ^{-1}(b) = a$ ,$(f \circ f^{-1})(b) = f (f ^{-1}(b)) = f (a) = b$ , where$I_A, I_B$ denote the identity functions on the sets$A$ and$B$ , respectively.
- Suppose that
-
取整函数
- The floor function assigns a real number
$x$ the largest integer that is$\leq x$ , denoted by$\lfloor x\rfloor$ - The ceiling function assigns a real number
$x$ the smallest integer that is$\geq x$ , denoted by$\lceil x\rceil$
- The floor function assigns a real number
-
阶乘函数
The factorial function
$f :\mathbb N \to\mathbb Z^+$ is the product of the first$n$ positive integers when$n$ is a nonnegative integer, denoted by$f (n) = n!$ .
-
序列
A sequence is a function from a subset of the set of integers (typically the set
${0, 1, 2, \dots}$ or${1, 2, 3, \dots}$ to a set$S$ . We use the notation$a_n$ to denote the image of the integer$n$ . (${a_n}$ represents the ordered list${a_1, a_2, a_3,\dots}$ ). -
等差数列(算术级数) arithmetic progression
An arithmetic progression is a sequence of the form
$a, a+d, a+2d, a+3d, \dots ,a+nd,\dots$ , where the initial term$a$ and common difference$d$ are real numbers. -
等比数列(几何级数) geometric progression
A geometric progression is a sequence of the form
$a, ar , ar^2,\dots, ar^n,\dots$ , where the initial term$a$ and the common ratio$r$ are real numbers. -
递推关系 recurrence relation
The
$n$ -th element of the sequence${a_n}$ is defined recursively in terms of the previous elements of the sequence and the initial elements of the sequence.
-
求和记号
$\Sigma$ The summation of the terms of a sequence is $$ \sum_{i=m}^na_i=a_m+a_{m+1}+a_{m+2}+\dots+a_n $$ The variable
$i$ is referred to as the index of summation and the choice of the letter$i$ is arbitrary.-
$m$ : lower limit -
$n$ : upper limit
-
线性:
-
常用求和公式
求和 闭形式 $\sum_{k=0}^nar^k,r\neq0$ $\frac{a(r^{n+1}-1)}{r-1},r\neq1$ $\sum_{k=1}^nk$ $\frac{n(n+1)}2$ $\sum_{k=1}^nk^2$ $\frac{n(n+1)(2n+1)}6$ $\sum_{k=1}^nk^3$ $\frac{n^2(n+1)^2}4$ $\sum_{k=0}^\infty x^k, x $\sum_{k=0}^\infty kx^{k-1}, x
- The sets
$A$ and$B$ have the same cardinality if there is a one-to-one correspondence between elements in$A$ and$B$ . - If there is a one-to-one function from
$A$ to$B$ , the cardinality of$A$ is less than or the same as the cardinality of$B$ , denoted by$|A| \leq |B|$ . Moreover, when$|A| \leq |B|$ and$A$ and$B$ have difference cardinalities, we say that the cardinality of$A$ is less than the cardinality of$B$ , denoted by$|A| < |B|$ . - 若$|A| \leq |B|$且$|B| \leq |A|$, 则$|A| = |B|$. 即如果存在一对一函数
$f$ 从$A$ 到$B$ 和$g$ 从$B$ 到$A$ , 则存在$A$ 和$B$ 之间的一一对应函数.
-
可数集合
A set that is either finite or has the same cardinality as the set of positive integers
$\mathbb Z^+$ is called countable. A set that is not countable is called uncountable.如果一个无限集$S$是可数的，用符号$\aleph_0$表示$S$的基数，写作$|S|=\aleph_0$，并说$S$有基数“阿里夫零”。
-
证明一个集合可数
- 找一个定义域是$\N_+$的一一对应函数
- 找一个方法能列出所有元素
-
The set of integers
$\Z$ is countable.The set of (positive) rational numbers is countable.
The set of finite strings
$S$ over a finite alphabet$A$ is countably infinite. -
The set of real numbers
$\R$ is uncountable.Proof by contradiction:
Assume that
$\R$ is countable. Then every subset of$\R$ is countable, in particular, the interval from 0 to 1 is countable. This implies that the elements of this set can be listed as$r_1, r_2, r_3,\dots$ , where$r_1 = 0.d_{11}d_{12}d_{13}d_{14}\dots$ $r_2 = 0.d_{21}d_{22}d_{23}d_{24}\dots$ $r_3 = 0.d_{31}d_{32}d_{33}d_{34}\dots$ all$d_{ij} \in{0,1,2\dots,9}$ .We want to show that not all real numbers in the interval between 0 and 1 are in this list.
Form a new number called
$r = 0.d_1d_2d_3d_4\dots$ , where$d_i = 2$ if$d_{ii} \neq 2$ , and$d_i = 3$ if$d_{ii} = 2$ .We claim that
$r$ is different from each number in the list. Each expansion is unique, if we exclude an infinite string of 9's.$r$ and$r_i$ differ in the$i$ -th decimal place for all$i$ .
-
Let
$f$ and$g$ be functions from the set of integers or the set of real numbers to the set of real numbers. We say that$f(n) = O(g(n))$ (reads:$f(n)$ is$O$ of $g(n)$), if there exist some positive constants$C$ and$x_0$ such that$|f (n)| \leq C|g(n)|$ , whenever$n > x_0$ . -
证明
$f$ 不是$O(g(n))$ 用反证法。 -
常见函数
函数 $O$ $1+2+\dots+n$ $O(n^2)$ $n!$ $O(n^n)$ $\log n!$ $O(n\log n)$ $\log_a n,a\geq 2$ $O(n)$ $n^a$ $O(n^b),a\leq b$ $n^a$ $O(2^n)$
|
证明多项式是O(最高次项)的:
-
函数的组合
-
If
$f_1(x)$ is$O(g_1(x))$ and$f_2(x)$ is$O(g_2(x))$ then$(f_1 + f_2)(x) = O(max(|g_1(x)|, |g_2(x)|))$ 证明: 三角不等式
$|a+b|\leq|a|+|b|$ -
If
$f_1(x)$ is$O(g_1(x))$ and$f_2(x)$ is$O(g_2(x))$ then$(f_1f_2)(x) = O(g_1(x)g_2(x))$
-
-
大$\Omega$记号
Let
$f$ and$g$ be functions from the set of integers or the set of real numbers to the set of real numbers. We say that$f (n) = \Omega (g(n))$ (reads:$f (n)$ is$\Omega$ of $g(n)$), if there exist some positive constants$C$ and$x_0$ such that$|f (n)| \geq C|g(n)|$ , whenever$n > x_0$ .$f (x)$ is$\Omega(g(x))$ if and only if$g(x)$ is$O(f (x))$ . -
大$\Theta$记号
Two functions
$f (n), g(n)$ have the same order growth if$f (n) = O(g(n))$ and$g(n) = O(f (n))$ . In this case, we say that$f (n) = \Theta(g(n))$ , which is the same as$g(n) = \Theta(f (n))$ .$C_1|g(x)|\leq|f(x)|\leq C_2|g(x)|$
-
An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.
-
A computational problem is a specification of the desired input-output relationship.
-
An instance of a problem is all the inputs needed to compute a solution to the problem.
-
A correct algorithm halts with the correct output for every input instance. We can then say that the algorithm solves the problem.
-
The number of machine operations(addition, multiplication, comparison, replacement, etc) needed in an algorithm is the time complexity of the algorithm, and amount of memory needed is the space complexity of the algorithm.
-
Input Size
若一个程序只有一个输入n, 其input size是需要的比特串长度, 即$\lceil\log_2(n+1)\rceil$.
-
NP完全性
P类问题：所有可以在多项式时间内求解的判定问题构成P类问题
NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题（能在多项式时间内验证解）
举例：旅行商问题
NP完全问题：NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)
P=NP? 至今仍未证明，是计算机一个极其重要的研究方向
- If
$a$ and$b$ are integers with$a\neq 0$ , we say that$a$ divides$b$ if there is an integer$c$ such that$b = ac$ , or equivalently$b\div a$ is an integer. In this case, we say that$a$ is a factor or divisor of$b$ , and$b$ is a multiple of$a$ . (We use the notations$a\mid b$ ,$a\not\mid b$ ) - 整除的性质
- if
$a\mid b$ and$a\mid c$ , then$a\mid(b + c)$ - if
$a\mid b$ then$a\mid bc$ for all integers$c$ - if
$a\mid b$ and$b\mid c$ , then$a\mid c$ 传递性 - 推论: If
$a, b, c$ are integers, where$a\neq 0$ , such that$a\mid b$ and$a\mid c$ , then$a\mid(mb + nc)$ whenever$m$ and$n$ are integers.
- if
-
If
$a$ is an integer and$d$ is a positive integer, then there are unique integers$q$ and$r$ , with$0\leq r < d$ , such that$a = dq + r$ . In this case,$d$ is called the divisor(除数),$a$ is called the dividend(被除数),$q$ is called the quotient(商), and$r$ is called the remainder(余数). -
In this case, we use the notations
$q = a \ div \ d$ and$r=a\textrm{ mod } d$ .
-
定义
If
$a$ and$b$ are integers and$m$ is a positive integer, then$a$ is congruent to$b$ modulo$m$ if$m$ divides$a - b$ , denoted by$a \equiv b\ (\textrm{mod }m)$ . This is called congruence and$m$ is its modulus. -
性质
- Let
$m$ be a positive integer. The integers$a$ and$b$ are congruent modulo$m$ if and only if there is an integer$k$ such that$a = b + km$ . - Let
$a$ and$b$ be integers, and let$m$ be a positive integer. Then$a \equiv b\ (\textrm{mod } m)$ if and only if$a \textrm{ mod } m = b \textrm{ mod } m$ . - Let
$m$ be a positive integer. If$a \equiv b\ (\textrm{mod } m)$ and$c \equiv d\ (\textrm{mod } m)$ , then$a + c \equiv b + d\ (\textrm{mod } m)$ and$ac \equiv bd\ (\textrm{mod } m)$ . - If
$a\equiv b\ (\textrm{mod }m)$ , then$ca\equiv cb\ (\textrm{mod }m)$ ,$a+c\equiv b+c\ (\textrm{mod }m)$ - Let
$m$ be a positive integer and let$a$ and$b$ be integers. Then$(a + b)\ \textrm{mod } m = ((a \textrm{ mod } m) + (b \textrm{ mod } m))\ \textrm{mod } m$ $ab \textrm{ mod } m = ((a \textrm{ mod } m)(b \textrm{ mod } m)) \ \textrm{mod } m$
- Let
-
定义
Let
$Z_m$ be the set of nonnegative integers less than$m$ :${0,1,\dots,m-1}$ -
$a+_m b=(a+b)\textrm{ mod }m$ -
$a\cdot_m b=ab\textrm{ mod }m$
-
-
性质: 交换环
- Closure(封闭性): if
$a, b \in Z_m$ , then$a +_m b$ ,$a \cdot_m b \in Z_m$ - Associativity(结合性): if
$a, b, c\in Z_m$ , then$(a +_m b) +_m c = a +_m (b +_m c)$ $(a \cdot_m b) \cdot_m c = a \cdot_m (b \cdot_m c)$ - Identity elements:
$a +_m 0 = a$ and$a \cdot_m 1 = a$ - Additive inverses: if
$a \neq 0$ and$a \in Z_m$ , then$m - a$ is an additive inverse of a modulo$m$ - Commutativity(交换性): if
$a, b \in Z_m$ , then$a +_m b = b +_m a$ ,$a\cdot_m b=b\cdot_m a$ - Distributivity(分配性): if
$a, b, c \in Z_m$ , then$a \cdot_m (b +_m c) = (a \cdot_m b) +_m (a \cdot_m c)$ $(a +_m b) \cdot_m c = (a \cdot_m c) +_m (b \cdot_m c)$
- Closure(封闭性): if
-
同余式可以逐项相加
若
$a_1\equiv b_1\ (\textrm{mod }m),a_2\equiv b_2\ (\textrm{mod }m),\dots,a_n\equiv b_n\ (\textrm{mod }m)$ 则$a_1+a_2+\dots+a_n\equiv b_1+b_2+\dots+b_n\ (\textrm{mod }m)$ -
同余式可以逐项相乘
-
同余式可以移项
若
$a+b\equiv c\ (\textrm{mod }m)$ 则$a\equiv b-c\ (\textrm{mod }m)$ -
同余式每一边都可以加减模的任意倍数 (同余式每一边都可以模
$m$ )若
$a\equiv b\ (\textrm{mod }m)$ 则$a\pm km\equiv b\ (\textrm{mod }m),a\equiv b\pm km \ (\textrm{mod }m),a\pm k_1m\equiv b\pm k_2m \ (\textrm{mod }m)$ -
同余式两边的数如有公约数，此公约数又和模互素，那么就可以把两边的数除以这个公约数
若
$ac\equiv bc\ (\textrm{mod }m)$ 且$\gcd(c, m)=1$ , 则$a\equiv b\ (\textrm{mod }m)$ -
同余式两边的数和模可以同时乘上一个整数
若
$a\equiv b\ (\textrm{mod }m)$ 则$ka\equiv kb\ (\textrm{mod }km)$ -
同余式可以两边同加或同乘一个整数
若
$a\equiv b\ (\textrm{mod }m)$ 则$ca\equiv cb\ (\textrm{mod }m)$ ,$a+c\equiv b+c\ (\textrm{mod }m)$ -
同余式两边的数和模可以同时被它们任一公约数除
若
$ka\equiv kb\ (\textrm{mod }km)$ 则$a\equiv b\ (\textrm{mod }m)$ -
如果同余式对于模
$m$ 成立，那么它对于$m$ 的任意约数相等的模$d$ 也成立若
$a\equiv b\ (\textrm{mod }m)$ ,$m=m_1d$ , 则$a\equiv b\ (\textrm{mod }d)$ -
如果同余式一边上的数和模能被某个数除尽，则同余式的另一边的数也能被这个数除尽
若
$a\equiv b\ (\textrm{mod }m)$ ,$k\mid a$ ,$k\mid m$ , 则$k\mid b$ -
同余式一边上的数与模的最大公约数，等于另一边上的数与模的最大公约数
若
$a\equiv b\ (\textrm{mod }m)$ 则$\gcd(a, m)=\gcd(b, m)$ -
同余式中系数可以取模 (由性质4推出)（我自己写的）
若
$ka\equiv b\ (\textrm{mod }m)$ 则$(k\textrm{ mod }m)a\equiv b\ (\textrm{mod }m)$ 实际上是左边减去了
$m$ 的某个倍数$cma$ 例：同余方程
$8x\equiv 2\ (\textrm{mod }3)$ $(8\textrm{ mod }3)x\equiv 2\ (\textrm{mod }3)\Rightarrow 2x\equiv 2\ (\textrm{mod }3)\Rightarrow x\equiv 1\ (\textrm{mod }3)$ 实际上是
$8x-6x\equiv 2\ (\textrm{mod }3)$ , 左边减去了$3$ 的一个倍数$6x$
-
Base-b Expansion
Let
$b > 1$ be an integer. Then if$n$ is a positive integer, it can be expressed uniquely in the form$n = a_kb^k + a_{k-1}b^{k-1} + \dots + a_1b + a_0$ , where$k$ is nonnegative,$a_i$ 's are nonnegative integers less than$b$ . The representation of$n$ is called the base-b expansion of$n$ and is denoted by$(a_ka_{k-1}\dots a_1a_0)_b$ . -
计算方式
To construct the base-b expansion of an integer
$n$ ,- Divide
$n$ by$b$ to obtain$n = bq_0 + a_0$ , with$0 \leq a_0 < b$ - The remainder
$a_0$ is the rightmost digit in the base-b expansion of$n$ . Then divide$q_0$ by$b$ to get$q_0 = bq_1 + a_1$ with$0 \leq a_1 < b$ -
$a_1$ is the second digit from the right. Continue by successively dividing the quotients by$b$ until the quotient is$0$
时间复杂度
$O(\log_b^3n)$ - Divide
-
二进制加法
时间复杂度
$O(n)$ ,$n$ 为位数 -
整数乘法
时间复杂度
$O(n^2)$ -
div 和 mod 算法
注意：少了
$a<0$ ,$r=0$ 的情况时间复杂度
$O(\log a\log d)$ , 有优化算法实现了$O(n^2), n=\max{\log a, \log d}$ -
模指数运算
计算
$b^n\textrm{ mod }m$ :$b^n=b^{a_{k-1}\cdot 2^{k-1}+\dots+a_1\cdot2+a_0}=b^{a_{k-1}\cdot2^{k-1}}\cdots b^{a_1\cdot 2}\cdot b^{a_0}$ Successively finds
$b \textrm{ mod } m$ ,$b^2 \textrm{ mod } m$ ,$b^4 \textrm{ mod } m$ ,$\dots$ ,$b^{2^{k-1}} \textrm{ mod } m$ , and multiplies together the terms$b^{2^j}$ where$a_j = 1$ .时间复杂度
$O(\log^2 m\log n)$
-
素数（质数）与合数的定义
A positive integer
$p$ that is greater than 1 and is divisible only by 1 and by itself is called a prime.A positive integer
$p$ that is greater than 1 and is not a prime is called a composite. -
算术基本定理
Every integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size.
-
If
$n$ is composite, then$n$ has a prime divisor less than or equal to$\sqrt n$ 证明：
- if n is composite, then it has a positive integer factor a such that
$1 < a < n$ by definition. This means that$n = ab$ , where$b$ is an integer greater than 1. - assume that
$a >\sqrt n$ and$b > \sqrt n$ . Then$ab > n$ , contradiction. So either$a \leq \sqrt n$ or$b \leq \sqrt n$ . - Thus,
$n$ has a divisor less than$\sqrt n$ . - By the Fundamental Theorem of Arithmetic, this divisor is either prime, or is a product of primes. In either case,
$n$ has a prime divisor less than$\sqrt n$ .
- if n is composite, then it has a positive integer factor a such that
-
最大公因数
Let
$a$ and$b$ be integers, not both 0. The largest integer$d$ such that$d\mid a$ and$d\mid b$ is called the greatest common divisor of$a$ and$b$ , denoted by$\gcd(a, b)$ .-
互质
The integers
$a$ and$b$ are relatively prime if their greatest common divisor is 1. -
A systematic way to find the gcd is factorization. Let
$a=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}$ ,$b=p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n}$ . Then$\gcd(a, b)=p_1^{\min(a_1, b_1)}p_2^{\min(a_2, b_2)}\cdots p_n^{\min(a_n, b_n)}$
-
-
最小公倍数
Let
$a$ and$b$ be integers. The least common multiple of$a$ and$b$ is the smallest positive integer that is divisible by both$a$ and$b$ , denoted by$\textrm{lcm}(a, b)$ .- Let
$a=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}$ ,$b=p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n}$ . Then$\textrm{lcm}(a, b)=p_1^{\max(a_1, b_1)}p_2^{\max(a_2, b_2)}\cdots p_n^{\max(a_n, b_n)}$
- Let
-
$ab=\gcd(a,b)\cdot\textrm{lcm}(a, b)$ -
欧几里得算法
- 引理: Let
$a = bq + r$ , where$a, b, q$ and$r$ are integers. Then$\gcd(a, b) = \gcd(b, r )$ .
public static int gcd(int x, int y) { if (y==0) return x; return gcd(y, x%y); }
- 引理: Let
-
贝祖定理 Bézout's Theorem
If
$a$ and$b$ are positive integers, then there exist integers$s$ and$t$ such that$\gcd(a, b) = sa + tb$ .$s$ 和$t$ 称为贝祖系数-
推论1. If
$a, b, c$ are positive integers such that$gcd(a, b) = 1$ and$a\mid bc$ , then$a\mid c$ . -
推论2. If
$p$ is prime and$p\mid a_1a_2 \cdots a_n$ , then$p\mid a_i$ for some$i$ . -
求贝祖系数: extended Euclidean algorithm
例:
$\gcd(503, 286) = 503s + 286t$ $503 = 1 \cdot 286 + 217$ $286 = 1 \cdot 217 + 69$ $217 = 3 \cdot 69 + 10$ $69 = 6 \cdot 10 + 9$ $10 = 1 \cdot 9 + 1$ 反代: 代入的是每一步的余数
$1 = 10 - 1 \cdot 9$ $= 7 \cdot 10 - 1 \cdot 69$ $= 7 \cdot 217 - 22 \cdot 69$ $= 29 \cdot 217 - 22 \cdot 286$ $= 29 \cdot 503 - 51 \cdot 286$
-
-
若
$m$ 为正整数，令$a, b$ 和$c$ 为整数，如果$ac\equiv bc\ (\textrm{mod }m)$ 且$\gcd(c, m)=1$ , 则$a\equiv b\ (\textrm{mod }m)$ .
-
定义
A congruence of the form
$ax \equiv b\ (\textrm{mod } m)$ , where$m$ is a positive integer,$a$ and$b$ are integers, and$x$ is a variable, is called a linear congruence.The solutions to a linear congruence
$ax \equiv b\ (\textrm{mod } m)$ are all integers$x$ that satisfy the congruence. -
$a$ 模$m$ 的逆An integer
$\bar a$ such that$a\bar a \equiv 1\ (\textrm{mod } m)$ is said to be an inverse of$a$ modulo$m$ .应用：解线性同余方程 One method of solving linear congruences makes use of an inverse
$\bar a$ if it exists. From$ax \equiv b\ (\textrm{mod } m)$ , it follows that$\bar aax \equiv\bar ab\ (\textrm{mod } m)$ and then$x \equiv\bar ab \ (\textrm{mod } m)$ .-
求
$a$ 模$m$ 的逆-
If
$a$ and$m$ are relatively prime integers and$m > 1$ , then an inverse of$a$ modulo$m$ exists. Furthermore, the inverse is unique modulo$m$ . ($Z_m$ 里有唯一的逆) -
求法：贝祖定理
Since
$\gcd(a,m) = 1$ , there are integers$s$ and$t$ such that$sa + tm = 1$ . Hence$sa + tm \equiv 1\ (\textrm{mod } m)$ . Since$tm \equiv 0\ (\textrm{mod } m)$ , it follows that$sa \equiv 1 \ (\textrm{mod } m)$ . This means that$s$ is an inverse of$a$ modulo$m$ .写出
$sa + tm \equiv 1\ (\textrm{mod } m)$ 的形式，$s$ 就是$\bar a$
-
-
-
解方程
Solve the congruence
$ax \equiv b\ (\textrm{mod } m)$ by multiplying both sides by$\bar a$ .例：$3x\equiv 4\ (\textrm{mod }7)$
贝祖定理找到
$-2\cdot 3+1\cdot 7=1$ 则
$\bar a=-2$ 两边乘
$-2$ 得$-6x\equiv -8\ (\textrm{mod }7)$ 取模化简
$x\equiv 6\ (\textrm{mod }7)$ 同余式两边可以同乘一个数，所以实际上是找一个数，乘完之后$x$系数能化为1，在这个例子中就是找几倍的3能模7=1.
$-6 \textrm{ mod } 7=1$ , 所以是-2倍，右边乘-2直接得$x\equiv -8(\textrm{mod }7)\equiv 6(\textrm{mod }7)$ 5倍也行
-
Let
$m_1,m_2, \dots ,m_n$ be pairwise relatively prime positive integers greater than$1$ and$a_1, a_2, \dots , a_n$ be arbitrary integers. Then the system$x\equiv a_1\ (\textrm{mod }m_1)$ $x\equiv a_2\ (\textrm{mod }m_2)$ $\cdots$ $x\equiv a_n\ (\textrm{mod }m_n)$ has a unique solution modulo
$m = m_1m_2 \dots m_n$ . -
Let
$M_k = \frac{m}{m_k}$ for$k = 1, 2, \dots , n$ and$m = m_1m_2 \dots m_n$ . Since$\gcd(m_k ,M_k ) = 1$ , there is an integer$y_k$ , an inverse of$M_k$ modulo$m_k$ such that$M_ky_k \equiv 1\ (\textrm{mod } m_k )$ . Let $$ x=a_1M_1y_1+a_2M_2y_2+\dots+a_nM_ny_n $$ It is checked that$x$ is a solution to the$n$ congruences.-
证明：$x$ 是一个解
Assume
$j,k\leq n$ , then for all$j\neq k$ ,$M_j\equiv 0\ (\textrm{mod }m_k)$ . So$x=a_kM_ky_k\ (\textrm{mod }m_k)\equiv a_k\ (\textrm{mod }m_k)$ holds for all$k=1,2,\dots,n$ . -
证明：$x$是唯一解
Suppose there are 2 solutions
$x, y$ , then$x\equiv a_i\ (\textrm{mod }m_i)$ ,$y\equiv a_i\ (\textrm{mod }m_i)$ ,$i=1,2,\dots,n$ . So$x\equiv y \ (\textrm{mod }m_i)$ , which means$m_i\mid x-y$ . Assume$p$ is a prime factor in the prime factorization of$m=\prod_{i=1}^nm_i$ . Since all$m_i$ 's are relatively prime,$p$ must be a factor of exactly one$m_i$ , say$p\mid m_j$ . And we know that$m_j\mid x-y$ , it then follows that$x-y$ has the factor$p$ in its prime factorization to a power at least as large as the power to which it appears in the factorization of$m_j$ . This holds for all$p$ , so$m\mid x-y$ , then$x\equiv y\ (\textrm{mod }m)$ . Thus, these 2 solutions are actually same, which means$x$ is a unique solution.补充解释:
$18\mid 36$ , 分解质因数$18=2\times3^2$ , 所以$36$分解质因数之后至少有$2$和$3^2$这两项, 当然次数可能更高 (at least as large as the power to which it appears in the factorization of 18)
-
-
例1:
$x\equiv 2\ (\textrm{mod }3)$ $x\equiv 3\ (\textrm{mod }5)$ $x\equiv 2\ (\textrm{mod }7)$ Let
$m=3\times5\times7=105$ ,$M_1=\frac m3=35, M_2=\frac m5=21, M_3=\frac m7=15$ .$35y_1\equiv 1\ (\textrm{mod }3)\Rightarrow2y_1\equiv1\ (\textrm{mod }3)\Rightarrow y_1=2$ $21y_2\equiv 1\ (\textrm{mod }5)\Rightarrow y_2=1$ $15y_3\equiv 1\ (\textrm{mod }7)\Rightarrow y_3=1$ $\therefore x=2\times35\times2+3\times21\times1+2\times15\times1=233$ $\therefore x\equiv 23\ (\textrm{mod }105)$ -
反代法 Back Substitution
题目同上
$x\equiv 2\ (\textrm{mod }3)\Rightarrow x=3k+2$ 代入第二个式子
$3k+2\equiv 3\ (\textrm{mod }5)\Rightarrow k\equiv 2\ (\textrm{mod }5)\Rightarrow k=5l+2\Rightarrow x=15l+8$ 代入第三个式子
$15l+8\equiv 2\ (\textrm{mod }7)\Rightarrow l\equiv 1\ (\textrm{mod }7)\Rightarrow l=7m+1\Rightarrow x=105m+23$ $\therefore x\equiv 23\ (\textrm{mod }105)$ -
例2:
$x\equiv 8\ (\textrm{mod }15)$ $x\equiv 2\ (\textrm{mod }21)$ 由第一个式子,
$x=15k+8$ ,$15=3\times5$ , 则$x\equiv 2\ (\textrm{mod }3),x\equiv 3\ (\textrm{mod }5)$ 由第二个式子,
$x=21l+2$ ,$21=3\times7$ , 则$x\equiv 2\ (\textrm{mod }3),x\equiv 2\ (\textrm{mod }7)$ 通过这种方式化为了例1
-
费马小定理 Fermat's Little Theorem
Let
$p$ be a prime, and let$x$ be an integer such that$x \not\equiv 0\ (\textrm{mod } p)$ . Then$x^{p-1} \equiv 1\ (\textrm{mod } p)$ .(
$x$ 不能被$p$ 整除)例: 化简
$7^{222}\ (\textrm{mod } 11)$ 由费马小定理知
$7^{10}\equiv 1\ (\textrm{mod }11)$ .$7^{222}\equiv(7^{10})^{22}\cdot7^2\equiv 49\ (\textrm{mod }11)\equiv 5\ (\textrm{mod }11)$ . -
欧拉函数 Euler's Totient Function
$\phi(n)$ $\phi(n)=$ the number of positive integers coprime(互质) to$n$ in$\mathbb Z_n$ .常用公式:
$\phi(p)=p-1$ $\phi(pq)=(p-1)(q-1)$ $\phi(p^i)=p^i-p^{i-1}$ -
欧拉定理 Euler's Theorem
Let
$n$ be a positive integer, and let$x$ be an integer such that$\gcd(x, n) = 1$ . Then $$ x^{\phi(n)}\equiv 1\ (\textrm{mod }n) $$
-
原根 Primitive Roots
A primitive root modulo a prime
$p$ is an integer$r \in\mathbb Z_p$ such that every nonzero element of$\mathbb Z_p$ is a power of$r$ . (取模之后) r 的 1 到 p-1 次方就会出现所有$\mathbb Z_p$ 例: 3是7的原根
$3^1=3, 3^2=2,3^3=6,3^4=4, 3^5=5, 3^6=1$ - There is a primitive root modulo
$n$ if and only if$n = 2, 4, p^e$ or$2p^e$ , where$p$ is an odd prime.
- There is a primitive root modulo
-
离散对数 Discrete Logarithm
The discrete logarithm of an integer
$y$ to the base$b$ is an integer$x$ , such that$b^x\equiv y\ (\textrm{mod }n)$ Discrete Logarithm Problem: Given
$n$ ,$b$ and$y$ , find$x$ . (NP问题)
Cryptography is the practice and study of techniques for secure communication in the presence of third parties called adversaries. - Ronald L. Rivest
-
所有古典密码，如移位密码和仿射密码，都是私钥密码系统，即 "Symmetric" cryptography.
-
RSA 密码
Pick two large primes,
$p$ and$q$ . Let$n = pq$ , then$\phi(n) = (p - 1)(q - 1)$ . Encryption and decryption keys$e$ and$d$ are selected such that$\gcd(e, \phi(n))=1$ $ed\equiv1\ (\textrm{mod }\phi(n))$
Public key:
$(e,n)$ Private key:
$d$ Encryption:
$C=M^e\textrm{ mod }n$ Decryption:
$M=C^d\textrm{ mod }n$ $p,q,\phi(n)$ 必须保密， 否则可以计算出$d$ 举例:
$p=5, q=11, n=pq=55, \phi(n)=(p-1)(q-1)=40, e=7, d=23$ Public key:
$(7, 55)$ Private key:
$23$ Encryption:
$M=28, C=M^7\textrm{ mod }55=52$ Decryption:
$M=C^{23}\textrm{ mod }55=28$ -
RSA 密码的正确性
Let
$p$ and$q$ be two odd primes, and define$n = pq$ . Let$e$ be relatively prime to$\phi(n)$ and let$d$ be the multiplicative inverse of$e$ modulo$\phi(n)$ . For each integer$x$ such that$0 \leq x < n$ , $$ x^{ed}\equiv x\ (\textrm{mod }n) $$ 证明: 分 4 种情况-
$\gcd(x,n)=1$ $x,n$ is relatively prime, so$x^{\phi(n)}\equiv1\ (\textrm{mod }n)$ . Known$ed\equiv1\ (\textrm{mod }\phi(n))$ , then$ed=k\phi(n)+1$ . Therefore,$x^{ed}\equiv x^{k\phi(n)+1}\equiv (x^{\phi(n)})^k\cdot x\equiv x\ (\textrm{mod }n)$ . -
$\gcd(x,n)=p$ w.l.o.g. assume that
$x=tp$ . Note that$n=pq$ , so$\gcd(x,q)=1$ . Thus,$x^{q-1}\equiv1\ (\textrm{mod }q)$ by Fermat's little theorem.If to prove
$x^{ed}\equiv x\ (\textrm{mod }n)$ , we can prove$n\mid x^{ed}-x=x(x^{ed-1}-1)$ .Consider
$x^{ed-1}-1$ . Known$ed\equiv1\ (\textrm{mod }\phi(n))$ , then$ed=k\phi(n)+1$ . So$x^{ed-1}\equiv x^{k\phi(n)}$ $\equiv x^{k(p-1)(q-1)}\equiv(x^{q-1})^{k(p-1)}\equiv1\ (\textrm{mod }q)$ . Then$x^{ed-1}-1\equiv 0\ (\textrm{mod }q)$ , which means$q\mid x^{ed-1}-1$ . Because$x=tp$ ,$n\mid x(x^{ed-1}-1)$ . So$x^{ed}\equiv x\ (\textrm{mod }n)$ . -
$\gcd(x,n)=q$ 同上 -
$\gcd(x,n)=n$ $0\leq x<n$ , so$x=0$ .$x^{ed}\equiv x\ (\textrm{mod }n)$ is always true.If consider
$x>n$ ,$x\equiv0\ (\textrm{mod }n)$ . Same result.
-
-
数字签名
RSA Signature:
$S=M^d\textrm{ mod }n$ RSA Verification:
$M=S^e\textrm{ mod }n$ 实际上是用 private key 加密，然后用 public key 解密，解密出正确结果，就能说明你的 private key 是对的，那么就可以认为这条消息确实是你发出的，因为你的 private key 是独有的.
-
迪菲-赫尔曼秘钥协商协议 Diffie-Hellman Key Exchange Protocol
假设两人用私钥密码系统通信，如何生成一个只有这两人知道的秘钥:
所以在没有传输重要信息的情况下，两个人生成了同一个数
$k$
To prove:
- Assume that a counterexample exists, i.e., There is some
$n > 0$ for which$P(n)$ is false. - Let
$m > 0$ be the smallest value for which$P(n)$ is false. (良序性公理) - Then use the fact that
$P(m')$ is true for all$0 \leq m' < m$ to show that$P(m)$ is true, contradicting the choice of$m$ . 一般取$m'=m-1$ .
举例: Use proof by smallest counterexample to show that,
Suppose that
Then there must be a smallest
For any nonnegative integer
Since
Thus,
Substituting
Adding
Thus,
Therefore,
-
证明过程
To prove:
$P(n)$ is true for all integers$n\geq b$ -
Show that
$P(b)$ is true. -
$\forall n>b$ show$P(n-1)\to P(n)$ or$P(b)\land P(b+1)\land\dots\land P(n-1)\to P(n)$ .(Weak Principle or Strong Principle)
-
Conclude on the basis of the principle of mathematical induction that
$P(n)$ is true for all$n\geq b$ .
-
-
基本步骤
- 基础步骤 Base Step
- 归纳假设 Inductive Hypothesis 通常与下一步合并
- 归纳步骤 Inductive Step
- 结论 Inductive Conclusion
-
证明数学归纳法的正确性
已知
$P(b)$ 为真，且对于所有正整数$k\leq b$ ，命题$P(k)\to P(k+1)$ 为真。假定至少存在一个正整数$n$ 使$P(n)$ 为假，那么使$P(n)$ 为假的正整数集合$S$ 非空。因此，根据良序性公理，$S$ 中必有一个最小元素，设为$m$ 。 可得$m>b$ 。因为$m-1$ 也为正整数且$m-1\geq b$ 且$m-1\not\in S$ ，所以$P(m-1)$ 为真。根据已知条件，$P(m-1)\to P(m)$。所以$P(m)$ 也为真，这与$m\in S$ 矛盾。因此，对所有正整数$n\geq b$ ，$P(n)$ 必为真。 -
例: 证明
$\forall n\geq0,2^{n+1}\geq n^2+2$ Let
$P(n)$ :$2^{n+1}\geq n^2+2$ -
For
$n=0,2^{0+1}=2\geq0^2+2=2$ -
Suppose that
$n>0$ and$P(n-1)$ is true, which means$2^n\geq(n-1)^2+2$ So
$2^n\cdot2\geq2(n-1)^2+4=n^2+2+(n-2)^2\geq n^2+2$ Therefore
$\forall n>0$ ,$P(n-1)\to P(n)$ . -
By mathematical induction,
$\forall n\geq0,2^{n+1}\geq n^2+2$ .
-
-
定义
$T(n)=f(n)T(n-1)+g(n)$ , 首项已知
-
$T(n)=rT(n-1)+a$ 通项公式
$T(n)=r^nT(0)+a\frac{r^n-1}{r-1}$ 迭代:
$T(n)=rT(n-1)+a$ $=r(rT(n-2)+a)+a=r^2T(n-2)+ra+a$ $=r^2(rT(n-3)+a)+ra+a=r^3T(n-3)+r^2a+ra+a$ $=\dots=r^iT(n-i)+a(r^{i-1}+r^{i-2}+\dots+r+1)$ 猜测
$i=n$ 时$T(n)=r^nT(0)+a\sum_{i=0}^{n-1}r^i=r^nT(0)+a\frac{r^n-1}{r-1}$ 之后数学归纳法证明（一般可省略）
$\triangle$ 直接求法:两边加
$\frac{a}{r-1}$ $T(n)+\frac{a}{r-1}=r(T(n-1)+\frac{a}{r-1})$ , 则$\frac{T(n)+\frac{a}{r-1}}{T(n-1)+\frac{a}{r-1}}=r$ , 设$c_n=T(n)+\frac{a}{r-1}$ , 则${c_n}$ 是首项$c_0=T(0)+\frac{a}{r-1}$ , 公比为$r$ 的等比数列. 所以$c_n=c_0r^{n}$ , 则$T(n)+\frac{a}{r-1}=r^nT(0)+\frac{ar^n}{r-1}$ .整理得
$T(n)=r^nT(0)+a\frac{r^n-1}{r-1}$ . -
$T(n)=rT(n-1)+g(n)$ 通项公式
$T(n)=r^nT(0)+\sum_{i=1}^nr^{n-i}g(i)$ ,$T(0)$ 已知-
$T(n)=AT(n-1)+B$ $T(n)=A^nT(0)+B\frac{A^n-1}{A-1}$ -
$T(n)=AT(n-1)+B^n$ $T(n)=A^nT(0)+\frac{A^nB-B^{n+1}}{A-B}$ Divide both sides by
$B^n$ , then we get$\frac{T(n)}{B^n}=\frac AB\cdot\frac {T(n-1)}{B^{n-1}}+1$ . Add$\frac{1}{\frac AB-1}=\frac{B}{A-B}$ to both sides, then$\frac{T(n)}{B^n}+\frac{B}{A-B}=\frac AB\cdot(\frac {T(n-1)}{B^{n-1}}+\frac{B}{A-B})$ . Let$a_n=\frac{T(n)}{B^n}+\frac{B}{A-B}$ , then${a_n}$ is a geometric progression with the initial term$a_0=T(0)+\frac{B}{A-B}$ and common ratio$\frac AB$ . So$a_n=a_0(\frac AB)^n$ , which means$\frac{T(n)}{B^n}+\frac{B}{A-B}=(\frac AB)^n(T(0)+\frac{B}{A-B})$ , so$T(n)=A^nT(0)+\frac{A^nB-B^{n+1}}{A-B}$ . -
$T(n)=AT(n-1)+Bn+C$ $T(n-1)=AT(n-2)+B(n-1)+C$ .Then
$T(n)-T(n-1)=A[T(n-1)-T(n-2)]+B$ .Let
$a_n=T(n)-T(n-1)$ , then$a_n=Aa_{n-1}+B$ , by 1 we know$a_n=A^{n-1}a_1+B\frac{A^{n-1}-1}{A-1}$ .Then
$T(n)-T(n-1)=A^{n-1}[T(1)-T(0)]+B\frac{A^{n-1}-1}{A-1}$ .Solve $\begin{cases}T(n)-T(n-1)=A^{n-1}[T(1)-T(0)]+B\frac{A^{n-1}-1}{A-1}\cr T(n-1)=\frac{T(n)-Bn-C}{A}\cr T(1)=AT(0)+B+C\end{cases}$ to get
$T(n)$ .
-
Suppose that we have a recurrence of the form
$$
T(n)=aT(\frac nb)+cn^d
$$
where
-
$T(n)=\begin{cases}T(1)&n=1\cr 2T(\frac n2)+n&n\geq2 \end{cases}$
Assume
$n$ is a power of$2$ .$T(n)=2T(\frac n2)+n$ $=2(2T(\frac n4)+\frac n2)+n=4T(\frac n4)+2n$ $=4(2T(\frac n8)+\frac n4)+2n=8T(\frac n8)+3n$ $=\dots=2^iT(\frac{n}{2^i})+in$ The iteration ends at
$i=\log_2n$ ,$T(n)=nT(1)+n\log_2n$ . -
$T(n)=\begin{cases}1&n=1\cr T(\frac n2)+1&n\geq2 \end{cases}$
$T(n)=T(\frac n2)+1$ $=T(\frac n4)+2$ $=T(\frac n8)+3$ $=\dots=T(\frac{n}{2^i})+i$ The iteration ends at
$i=\log_2n$ ,$T(n)=1+\log_2n$ . -
$T(n)=\begin{cases}1&n=1\cr T(\frac n2)+n&n\geq2 \end{cases}$
$T(n)=T(\frac n2)+n$ $=T(\frac n4)+\frac n2+n$ $=T(\frac n8)+\frac n4+\frac n2+n$ $=\dots=T(\frac {n}{2^i})+\frac{n}{2^{i-1}}+\frac{n}{2^{i-2}}+\dots+\frac n2+n$ The iteration ends at
$i=\log_2n$ ,$T(n)=1+2+2^2+\dots+\frac n2+n=2n-1$ . -
$T(n)=\begin{cases}1&n<3\cr 3T(\frac n3)+n&n\geq3 \end{cases}$
$T(n)=3T(\frac n3)+n$ $=3(3T(\frac n9)+\frac n3)+n=9T(\frac n9)+2n$ $=9(3T(\frac{n}{27})+\frac n9)+2n=27T(\frac{n}{27})+3n$ $=\dots=3^iT(\frac {n}{3^i})+in$ The iteration ends at
$i=\log_3n$ ,$T(n)=n+n\log_3n$ . -
$T(n)=\begin{cases}T(1)&n=1\cr 4T(\frac n2)+n&n\geq2 \end{cases}$
$T(n)=4T(\frac n2)+n$ $=4(4T(\frac n4)+\frac n2)+n=4^2T(\frac n4)+2n+n$ $=4^2(4T(\frac n8)+\frac n4)+2n+n=4^3T(\frac n8)+4n+2n+n$ $=\dots=4^iT(\frac {n}{2^i})+2^{i-1}n+2^{i-2}n+\dots+2n+n$ The iteration ends at
$i=\log_2n$ ,$T(n)=2n^2-n$ .
-
定义
A linear homogeneous relation of degree
$k$ with constant coefficients is a recurrence relation of the form$a_n=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k}$ , where$c_1, c_2, \dots , c_k$ are real numbers, and$c_k \neq 0$ .- 线性 linear: it is a linear combination of previous terms
- 齐次 homogeneous: all terms are multiples of
$a_j$ 's - k 阶 degree
$k$ :$a_n$ is expressed by the previous$k$ terms - 常系数 constant coefficients: coefficients are constants
-
特征方程与特征根
令
$a_n=r^n$ 代入递推式得$r^k-c_1r^{k-1}-c_2r^{k-2}-\dots-c_k=0$ . (characteristic equation)特征根: 特征方程的解，注意有的根可能具有高于 1 的重数
-
定理：若
$s_n$ 和$t_n$ 均为递推关系的解，则它们的线性组合也是解
Theorem 1. If the CE
Proof:
-
$a_n =\alpha_1 r_1^n +\alpha_2 r_2^n$ is a solution$r_1,r_2$ are the solutions of the CE, so$r_1^2=c_1r+c_2,r_2^2=c_1r+c_2$ .$c_1a_{n-1}+c_2a_{n-2}=c_1(\alpha_1r_1^{n-1}+\alpha_2r_2^{n-1})+c_2(\alpha_1r_1^{n-2}+\alpha_2r_2^{n-2})$ $ =\alpha_1r_1^{n-2}(c_1r_1+c_2)+\alpha_2r_2^{n-2}(c_1r_2+c_2)=\alpha_1 r_1^n +\alpha_2 r_2^n=a_n$So
$a_n =\alpha_1 r_1^n +\alpha_2 r_2^n$ is a solution. -
if
${a_n}$ is a solution, then$a_n$ must in the form$a_n =\alpha_1 r_1^n +\alpha_2 r_2^n$ Suppose
$a_0=C_0,a_1=C_1$ are the initial terms.So if
$a_n$ satisfies the form, must $\begin{cases}\alpha_1+\alpha_2=C_0\cr\alpha_1r_1+\alpha_2r_2=C_1\end{cases}$.Then
$\alpha_1=\frac{C_1-C_0r_2}{r_1-r_2},\alpha_2=\frac{C_0r_1-C_1}{r_1-r_2}$ .By induction, if we know the initial terms, then the recurrence has a unique solution.
From 1 we know
$\alpha_1 r_1^n +\alpha_2 r_2^n$ is a solution and we just calculated$\alpha_1,\alpha_2$ using the initial terms, so it is a unique solution.
Example 1: Solve
-
The CE is
$r^2-r-2=0$ .So the roots
$r_1=2,r_2=-1$ .Suppose
$a_n=\alpha_12^n+\alpha_2(-1)^n$ .Then
$a_0=\alpha_1+\alpha_2=2,a_1=2\alpha_1-\alpha_2=7$ , so$\alpha_1=3,\alpha2=-1$ .Therefore
$a_n=3\cdot2^n-(-1)^n$ .
Theorem 2. If the CE
Example 2: Solve
-
The CE is
$r^2-4r+4=0$ and has one root$r_0=2$ .Suppose
$a_n=\alpha_12^n+\alpha_2n2^n$ .Then
$a_0=\alpha_1=1,a_1=2\alpha_1+2\alpha_2=0$ , so$\alpha_1=1,\alpha_2=-1$ .Therefore
$a_n=(1-n)2^n$ .
Theorem 3. If the CE
Example 3:
-
The CE is
$r^3-6r^2+11r-6=(r-1)(r-2)(r-3)=0$ .So the roots
$r_1=1,r_2=2,r_3=3$ .Suppose
$a_n=\alpha_1+\alpha_22^n+\alpha_33^n$ .Then $\begin{cases}a_0=\alpha_1+\alpha_2+\alpha_3=2\cr a_1=\alpha_1+2\alpha_2+3\alpha_3=5\cr a_2=\alpha_1+4\alpha_2+9\alpha_3=15\end{cases}$.
So
$\alpha_1=1,\alpha_2=-1,\alpha_3=2$ .Therefore
$a_n=1-2^n+2\cdot3^n$ .
Example 4:
-
The CE is
$r^3+3r^2+3r+1=(r+1)^3=0$ and has only one root$r=-1$ with 3 multiplicites.Suppose
$a_n=\alpha_{1,0}(-1)^n+\alpha_{1,1}n(-1)^n+\alpha_{1,2}n^2(-1)^n$ .Then $\begin{cases}a_0=\alpha_{1,0}=1\cr a_1=-\alpha_{1,0}-\alpha_{1,1}-\alpha_{1,2}=-2\cr a_2=\alpha_{1,0}+2\alpha_{1,1}+4\alpha_{1,2}=-1 \end{cases}$.
So
$\alpha_{1,0}=1,\alpha_{1,1}=3,\alpha_{1,2}=-2$ .Therefore
$a_n=(1+3n-2n^2)(-1)^n$ .
-
A linear nonhomogeneous relation with constant coefficients may contain some terms
$F(n)$ that depend only on$n$ .$a_n=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k}+F(n)$ .The recurrence relation
$a_n=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k}$ is called the associated homogeneous recurrence relation. (相伴的齐次递推关系) -
If
$a_n = p(n)$ is any particular solution to the linear nonhomogeneous relation with constant coefficients$a_n=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k}+F(n)$ , then all its solutions are of the form$a_n=p(n)+h(n)$ , where$a_n = h(n)$ is any solution to the associated homogeneous recurrence relation$a_n=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k}$ .解 = 一个特解 + 相伴递推的通解
-
Example:
$a_n=3a_{n-1}+2n$ with$a_1=3$ The characteristic equation of the associated linear homogeneous recurrence relation is
$r-3=0$ . Thus, the solution to the original problem are all of the form$a_n = \alpha3^n + p(n)$ .Try
$p(n)=cn+d$ , then$cn + d = 3(c(n - 1) + d) + 2n$ , which means$(2c + 2)n + (2d - 3c) = 0$ .We get
$c=-1,d=-\frac32$ . Thus,$p(n)=-n-\frac32$ .So
$a_n=-n-\frac32+\alpha3^n$ .$a_1=-1-\frac32+3\alpha=3$ , then$\alpha=\frac{11}{6}$ .Therefore
$a_n=-n-\frac32+\frac{11}{6}3^n$ .为什么$a_n$ 的表达式是确定的，
$-n-\frac32$ 只是试出来的其中一个特解啊？假设用了什么奇怪的方法找到了另外一个特解，比如
$-n-\frac32+3^n$ . 验证一下没问题，然后代回表达式是$a_n=-n-\frac32+(\alpha+1)3^n$ . 然后代入$a_1$ 算出的$\alpha=\frac56$ ，最后结果还是这个. 由此可见特解确实是特解，但是这个特解不是随便就找到的，是有特定形式的，就这个题来说我们找到的是$\alpha=0$ 时的特解.
-
乘法原理
If a count of elements can be broken down into a sequence of dependent counts where the first count yields
$n_1$ elements, the second$n_2$ elements, and$k$ ^th^ count$n_k$ elements, then the total number of elements is$n=\prod_{i=1}^kn_i$ .若一个过程可以被分解为
$k$ 个任务，完成第$i$ 个任务有$n_i$ 种方式，那么完成该过程有$n=\prod_{i=1}^kn_i$ 种方式. -
加法原理
If a count of elements can be broken down into a set of independent counts where the first count yields
$n_1$ elements, the second$n_2$ elements, and$k$ ^th^ count$n_k$ elements, then the total number of elements is$n=\sum_{i=1}^k n_i$ .若完成一个过程有
$k$ 类方式，第$i$ 类方式有$n_i$ 种方法，那么完成该过程有$n=\sum_{i=1}^k n_i$ 种方法.
-
例：设置一个
$n$ 位的密码，只由数字和小写字母组成，并且至少有一位为数字，求有多少可能的密码所有$-$全是字母的:
$36^n-26^n$ 先找一位为数字，剩下随便:
$C_n^1\cdot10\cdot36^{n-1}$ 是错的, 纯数字的算了两遍, 如两位时 00, 01...10, 11...90...99 这些纯数字都数了两遍,应为 $C_n^1\cdot10\cdot36^{n-1}-10^n$
-
A tree is a structure that consists of a root, branches and leaves.
-
Can be useful to represent a counting problem and record the choices we made for alternatives. The count appears on the leaves. 叶节点个数为结果
-
例: 两队比赛，5局3胜，求共几种可能的比赛过程
-
鸽巢原理
If there are
$k +1$ objects and$k$ bins, then there is at least one bin with two or more objects.$k+1$ 个球放入$k$ 个盒子，至少一个盒子里有 2 个或以上的球.证明：反证，假设所有盒子都至多 1 个球，那么一共不超过
$k$ 个球，与已知条件矛盾. -
广义鸽巢原理 Generalized Pigeonhole Principle
If
$N$ objects are placed into$k$ bins, then there is at least one bin containing at least$\lceil N/k\rceil$ objects.
-
全排列 Permutation
A bijection from a set onto itself is called a permutation.
-
The Bijection Principle
Two sets have the same size if and only if there is a one-to-one function from one set onto the other. (bijection) See
$\S2.5.1$
-
例: Compute the number of increasing triples
$(i , j , k)$ with$1 \leq i < j < k \leq n$ :Claim: Number of increasing triples is exactly the same as number of 3-element subsets from
${1, 2, \dots, n}$ Why? Let
$X$ = set of increasing triples and$Y$ = set of 3-element subsets from${1, 2, \dots, n}$ Define:
$f : X \to Y$ by$f ((i , j , k)) = {i , j , k}$ Claim:
$f$ is a bijection so$|X| = |Y|$ Proof:
$f$ is one-to-one: if$(i , j , k) \neq (i', j', k') )\Rightarrow f ( (i , j , k) ) \neq f ( (i', j', k'))$ $f$ is onto: if$\gamma$ is a 3-element subset then it can be written as$\gamma={i , j , k}$ where$i < j < k$ , so$f ( (i , j , k) )=\gamma$
use a sum rule and then corrects for the overlapping elements.
解释: 计算
举例:
证明: 数学归纳法
Base case:
Inductive Hypothesis:
Inductive step:
Let
By induction,
例:
Let (a) onto functions from
Let
Therefore #(a)=
-
A list of
$k$ distinct elements chosen from a set$N$ is called a$k$ -element permutation of$N$ .对集合中
$k$ 个元素的有序安排称为$k$ 排列.特别地,
$k=|N|$ 时称全排列 (Permutaion). -
If
$n$ is a positive integer and$k$ is an integer with$1 \leq k \leq n$ , then there are$P(n,k)=A_n^k=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}(0\leq k\leq n)$ $k$ -element permutations with$n$ distinct elements.
-
组合
从一个集合中无序选取
$k$ 个元素称为$k$ 组合. -
For integers
$n$ and$k$ with$0 \leq k \leq n$ , the number of$k$ -element subsets of an$n$ -element set is$C(n,k)=C_n^k=\binom nk=\frac{P(n.k)}{k!}=\frac{n!}{k!(n-k)!}$ $\binom nk$ is also called binomial coefficient. -
基本性质
$\binom nk=\binom{n}{n-k}$ $\binom nn=\binom n0=1$
For any integer
证明: 数学归纳法
-
当
$n=0$ 时$(x+y)^0=1=\sum_{i=0}^0\binom nix^{n-i}y^i$ -
假设
$n=k$ 时成立，即$(x+y)^k=C_k^0x^k+C_k^1x^{k-1}y+\dots+C_k^rx^{k-r}y^r+\dots+C_k^ky^k$ -
则当
$n=k+1$ 时，$(x+y)^{k+1}=(x+y)^k(x+y)$ $=C_k^0x^{k+1}+C_k^1x^{k}y+\dots+C_k^rx^{k-r+1}y^r+\dots+C_k^kxy^k$ $\ \ +C_k^0x^ky+C_k^1x^{k-1}y^2+\dots+C_k^rx^{k-r}y^{r+1}+\dots+C_k^ky^{k+1}$ $=C_k^0x^{k+1}+(C_k^0+C_k^1)x^ky+(C_k^1+C_k^2)x^{k-1}y^2+\dots+(C_k^{r}+C_k^{r+1})x^{k-r}y^{r+1}+\dots+C_k^ky^{k+1}$ -
i.
$C_k^{i}+C_k^{i+1}=C_{k+1}^{i+1}$ ii.
$C_{k}^0=C_{k+1}^0=1$ ,$C_k^k=C_{k+1}^{k+1}=1$ -
由 i. ii. 上式
$=C_{k+1}^0x^{k+1}+C_{k+1}^1x^ky+\dots+C_{k+1}^{r+1}x^{k-r}y^{r+1}+\dots+C_{k+1}^{k+1}y^{k+1}$ 则
$(x+y)^{k+1}=\sum_{i=0}^{k+1}\binom {k+1}ix^{k+1-i}y^i$ 成立 -
由归纳法,
$(x+y)^n=\sum_{i=0}^n\binom nix^{n-i}y^i,n\geq0$
推广: Trinomial coefficient
再推广
-
$\sum_{k=0}^n\binom nk=2^n$ 证明:
$(1+1)^n$ 组合证明：一个
$n$ 元素集合有$2^n$ 个子集.$\binom nk$ 表示含$k$ 个元素的子集的个数，所以$\sum_{k=0}^n\binom nk=2^n$ . -
$\sum_{k=0}^n(-1)^k\binom nk=0$ 证明:
$(-1+1)^n$ -
$\sum_{k=0}^n2^k\binom nk=3^n$ 证明:
$(1+2)^n$ -
$\sum_{k=0}^na^k\binom nk=(a+1)^n$ -
杨辉三角 Pascal's Triangle
$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ 代数证明：代入公式
组合证明：设
$|T|=n,a\in T$ . 对于任意一个$T$ 的$k$ 元素子集来说，要么是$a$ 与$a$ 之外的$k-1$ 个元素， 要么都是$a$ 之外的$k$ 个元素，即$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ . -
范德蒙德恒等式
$\binom{m+n}{k}=\sum_{i=0}^k\binom{m}{k-i}\binom ni,k\leq m\ or\ k\leq n$ 证明：设
$|S_1|=m,|S_2|=n$ ，两集合无重复元素. 从$S_1\cup S_2$ 中取$k$ 个元素，即$\binom{m+n}{k}$ ，可以看做先从$S_1$ 里取$i$ 个，再从$S_2$ 里取$k-i$ 个，其中$0\leq i\leq k$ . 然后使用乘法原理. -
$\binom{2n}{n}=\sum_{i=0}^n\binom ni^2$ 证明: 范德蒙德恒等式
-
$\binom{n+1}{k+1}=\sum_{i=k}^n\binom ik$ 证明：设
$\binom{n+1}{k+1}$ 表示长度为$n+1$ 的比特串中，含$k+1$ 个 1 的比特串的个数. 考虑最后一个 1 出现的位置，最后一个 1 只可能出现在第$k+1,k+2,\dots,n+1$ 位，对于每种情况，要把剩下$k$ 个 1 安排在最后一个 1 之前，即$\sum_{i=k}^n\binom ik$ .
-
The generating funciton for the sequence
$a_0,a_1,\dots,a_k,\dots$ of real numbers is the infinite series$G(x)=a_0+a_1x+a_2x^2+\dots+a_kx^k+\dots=\sum_{k=0}^\infin a_kx^k$ . 注意从 0 开始 -
A finite sequence
$a_0,a_1,\dots,a_n$ can be easily extended by setting$a_{n+1}=a_{n+2}=\dots=0$ .The generating function
$G(x)$ of this infinite sequence${a_n}$ is a polynomial of degree$n$ , i.e.,$G(x)=a_0+a_1x+\dots+a_nx^n$ .-
Example: The generating fuction for
$a_0,a_1,\dots,a_m$ where$a_k=C(m,k)$ $G(x)=C(m,0)+C(m,1)x+\dots+C(m,m)x^m=(1+x)^m$
-
-
普通生成函数之间的运算
Let
$f(x)=\sum_{k=0}^\infin a_kx^k,g(x)=\sum_{k=0}^\infin b_kx^k$ . Then$f(x)+g(x)=\sum_{k=0}^\infin (a_k+b_k)x^k$ $f(x)g(x)=\sum_{k=0}^\infin(\sum_{j=0}^ka_jb_{k-j})x^k$ -
常用生成函数
例1：求不定方程
-
将该问题转化为
$(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)$ 中$x^{17}$ 的系数.上式
$=\frac{x^2(x^4-1)}{x-1}\cdot\frac{x^3(x^4-1)}{x-1}\cdot\frac{x^4(x^4-1)}{x-1}=\frac{x^9(x^4-1)^3}{(x-1)^3}=x^9(x^2+1)^3(x+1)^3$ (平方差公式)现在从这三部分里拼一个
$x^{17}$ 出来. 第一部分是$x^9$ ，第二部分能提供$x^2,x^4,x^6$ ，第三部分能提供$x$ ,$x^2,x^3$ . 唯一的方式是$9+6+2$ . 所以系数是$1\times1\times C(3,2)=3$ .有 3 组满足条件的解.
-
广义二项式系数
设
$u$ 是实数且$k$ 是非负整数。那么广义二项式系数$\binom uk$ 定义为 $$ \binom uk=\begin{cases}\frac{u(u-1)\dots(u-k+1)}{k!}&k>0\cr1&k=0\end{cases} $$$\binom{-n}{r}=(-1)^rC(n+r-1,r)$ -
广义二项式定理
设
$x$ 是实数，$|x|<1$，$u$ 是实数，那么 $$ (1+x)^u=\sum_{k=0}^\infin\binom uk x^k $$ 当$u$ 为正整数时变成二项式定理，因为若$k>u$ ,$\binom uk=0$ .
-
二元关系的定义
- Let
$A$ and$B$ be two sets. A binary relation from$A$ to$B$ is a subset of a Cartesian product$A\times B$ . 关系是一个集合- Let
$R \subseteq A \times B$ denote$R$ is a set of ordered pairs of the form$(a, b)$ where$a \in A$ and$b \in B$ . We use the notation$a\ R\ b$ to denote$(a, b) \in R$ , and$a\ \not R\ b$ to denote$(a, b) \notin R$ .
- Let
- Let
-
二元关系的表示
-
We can graphically represent a binary relation
$R$ as: if$a\ R\ b$ , then we draw an arrow from$a$ to$b$ :$a \to b$ -
We can also represent a binary relation
$R$ by a table showing the ordered pairs of$R$ . -
Represent by a matrix. $$ M_R=\begin{bmatrix}1&1\1&0\0&1 \end{bmatrix} $$
-
Represent by a directed graph.
-
- Relations represent one to many relationships between elements in
$A$ and$B$ .
-
Relation on a set
A relation on the set
$A$ is a relation from$A$ to itself.The number of binary relations on a set
$A$ , where$|A| = n$ is$2^{n^2}$ . -
自反关系 Reflexive Relation
A relation
$R$ on a set$A$ is called reflexive if$(a, a) \in R$ for every element$a \in A$ .-
Example:
$R_{div}={(a,b):a\mid b}$ on$A={1,2,3,4}$ .Then
$R_{div}={(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}$ $R_{div}$ is reflexive because$(1,1),(2,2),(3,3),(4,4)\in R_{div}$ .
矩阵表示：对角线全 1 $$ M_{R_{div}}=\begin{bmatrix}1&1&1&1\0&1&0&1\0&0&1&0\0&0&0&1 \end{bmatrix} $$
-
The number of reflexive relations on a set
$A$ with$|A| = n$ is$2^{n(n-1)}$ .对角线全 1 的 01 矩阵有几种？
对角线确定，剩下
$n^2-n$ 个位置，每个位置是 0 或 1，乘法法则$2^{n(n-1)}$
-
-
Irreflexive Relation
A relation
$R$ on a set$A$ is called irreflexive if$(a, a) \notin R$ for every element$a \in A$ .矩阵表示：对角线全 0
-
对称关系 Symmetric Relation
A relation
$R$ on a set$A$ is called symmetric if$(b, a) \in R$ whenever$(a, b) \in R$ for all$a, b \in A$ .$(a,b)$ 和$(b,a)$ 要么都有，要么都没有矩阵表示：对称矩阵
-
反对称关系 Antisymmetric Relation
A relation
$R$ on a set$A$ is called antisymmetric if$(a,b) \in R$ and$(b,a) \in R$ implies$a = b$ for all$a, b \in A$ .矩阵表示：除了对角线之外不能有对称的 1，如
$MR_{div}$ -
传递关系 Transitive Relation
A relation
$R$ on a set$A$ is called transitive if$(a, b) \in R$ and$(b, c) \in R$ implies$(a, c) \in R$ for all$a, b, c \in A$ .
-
$S\circ R$ Let
$R$ be a relation from a set$A$ to a set$B$ and$S$ be a relation from$B$ to$C$ . The composite of$R$ and$S$ is the relation consisting of the ordered pairs$(a, c)$ where$a \in A$ and$c \in C$ and for which there is$a,b \in B$ such that$(a, b) \in R$ and$(b, c) \in S$ . We denote the composite of$R$ and$S$ by$S \circ R$ .$S\circ R$ 是先$R$ 后$S$ -
Example:
$A={1,2,3},B={0,1,2},C={a,b}$ $R={(1,0),(1,2),(3,1),(3,2) },S={(0,b),(1,a),(2,b) }$ Then
$S\circ R={(1,b),(3,a),(3,b) }$ -
矩阵表示: 两矩阵相乘
$M_R=\begin{bmatrix}1&0&1\0&0&0\0&1&1 \end{bmatrix},M_S=\begin{bmatrix}0&1\1&0\0&1 \end{bmatrix}$
$S\circ R=M_R\odot M_S=\begin{bmatrix}0&1\0&0\1&1 \end{bmatrix}$
-
-
$R^n$ Let
$R$ be a relation on$A$ . The powers$R^n$ , for$n = 1, 2, 3, \dots$ , is defined inductively by$R^1=R$ and$R^{n+1}=R^n\circ R$ .-
Example:
$A={1,2,3,4}$ and$R={(1,2),(2,3),(2,4),(3,3) }$ $R^1=R$ $R^2=R\circ R={(1,3),(1,4),(2,3),(3,3) }$ $R^3=R^2\circ R={(1,3),(2,3),(3,3) }$ $R^4=R^3\circ R={(1,3),(2,3),(3,3) }$ $R^n={(1,3),(2,3),(3,3) }$ for$n\geq3$ . 证明：数学归纳法
-
-
The relation
$R$ on a set$A$ is transitive if and only if$R^n \subseteq R$ for$n = 1, 2, 3, \dots$ Proof:
-
$R^n\subseteq R\to R$ is transitiveIn particular
$R^2\subseteq R$ . So if$(a,b)\in R$ and$(b,c)\in R$ , then$(a,c)\in R^2\subseteq R$ . Therefore$R$ is transitive. -
$R$ is transitive$\to R^n\subseteq R$ Prove by induction:
For
$n=1$ ,$R^1\subseteq R$ is true.Suppose when
$n=k$ ,$R^k\subseteq R$ .Then for
$n=k+1$ ,$R^{k+1}=R^k\circ R$ . Consider an arbitrary pair$(a,b)\in R^{k+1}$ , so there exists an element$x$ s.t.$(a,x)\in R$ and$(x,b)\in R^k$ . Because$R^k\subseteq R$ ,$(x,b)\in R$ . Known that$R$ is transitive, then$(a,b)\in R$ . Therefore$R^{k+1}\subseteq R$ .By induction
$R^n\subseteq R$ . -
Therefore
$R^n\subseteq R\leftrightarrow R$ is transitive
-
-
If
$R$ is transitive, then$R^n$ is also transitive.证明：见 7.3 节 Theorem 2
An
- The sets
$A_i$ 's are called the domains of$R$ . - The degree of
$R$ is$n$ . -
$R$ is functional in domain$A_i$ if it contains at most one n-tuple$(\dots, a_i ,\dots)$ for any value$a_i$ within domain$A_i$ .
-
选择 Selection Operator
Let
$A$ be any$n$ -ary domain$A = A_1\times\dots\times A_n$ , and let$C:A\to{T,F}$ be any condition (predicate) on elements ($n$ -tuples) of$A$ .The selection operator
$s_C$ is the operator that maps any ($n$ -ary) relation$R$ on$A$ to the$n$ -ary relation of all$n$ -tuples from$R$ that satisfy$C$ .$\forall R\subseteq A,s_C(R)={a\in R\mid s_C(a)=T }$ -
投影 Projection Operators
Let
$A = A_1\times\dots\times A_n$ be any$n$ -ary domain, and let${i_k}=(i_1,i_2,\dots,i_m)$ be a sequence of indices all falling in the range$1$ to$n$ . i.e., where$1 \leq i_k \leq n$ for all$1 \leq k \leq m$ .Then the projection operator on
$n$ -tuples$P_{{i_k}}:A\to A_{i_1}\times\dots\times A_{i_m}$ is defined by$P_{{i_k}}(a_1,\dots,a_n)=(a_{i_1},\dots,a_{i_m})$ .举例：$P_{1,3}$ 作用在一张表上，保留表的第一列和第三列，其他删除
-
连接 Join Operator
Puts two relations together to form a sort of combined relation.
If the tuple
$(A,B)$ appears in$R_1$ , and the tuple$(B, C)$ appears in$R_2$ , then the tuple$(A,B, C)$ appears in the join$J(R_1, R_2)$ . ($A,B, C$ can also be sequences of elements rather that single elements.) (inner join)
-
Let
$R$ be a relation on a set$A$ . A relation$S$ on$A$ with property$P$ is called the closure of$R$ with respect to$P$ if$S$ is subset of every relation$Q (S \subseteq Q)$ with property$P$ that contains$R (R \subseteq Q)$ .$S$ is the minimal set containing$R$ satisfying the property$P$ . -
分类
自反闭包 reflexive closures
对称闭包 symmetric closures
传递闭包 transitive closures
-
Example:
$R={(1,2),(1,3),(2,2) }$ on$A={1,2,3}$ . What is the symmetric closure$S$ of$R$ ?$S={(1,2),(2,1),(1,3),(3,1),(2,2) }$ （加入尽可能少的tuple使其成为一个对称关系）
-
Finding a transitive closure corresponds to finding all pairs of elements that are connected with a directed path. 有向图中的所有连通点对组成传递闭包
-
有向图中的路径
A path from
$a$ to$b$ in the directed graph$G$ is a sequence of edges$(x_0, x_1), (x_1, x_2),\dots, (x_{n-1}, x_n)$ in$G$ , where$n$ is nonnegative and$x_0 = a$ and$x_n = b$ . A path of length$n \geq 1$ that begins and ends at the same vertex is called a circuit or cycle. -
Theorem 1
Let
$R$ be relation on a set$A$ . There is a path of length$n$ from$a$ to$b$ if and only if$(a, b) \in R^n$ .证明：数学归纳法
$n=1$ 时，根据关系的有向图表示法，从$a$ 到$b$ 存在一条长为 1 的路径，当且仅当$(a,b)\in R$ .设
$n=k$ 时定理为真。那么$n=k+1$ 时，$a,b$ 间存在长为$k+1$ 的路径，当且仅当存在一个点$x$ 使得$a,x$ 间存在长为 1 的路径并且$x,b$ 间存在长为$k$ 的路径。根据 base case 和 i.h., 可知$(a,x)\in R,(x,b)\in R^k$ , 等价于$(a,b)\in R^{k+1}$ .由归纳法，定理成立。
注释：现在知道
$n=1$ 和$n=k$ 时成立，而且这个定理是充要。$a,b$ 之间有长$k+1$ 的路径$\leftrightarrow$ 必须有那么一个点$x$ 使得$a,x$ 路径长为 1 并且$b,x$ 路径长为$k$ $\leftrightarrow$ 由两条已知，存在一个点$x$ 使得$(a,x)\in R,(x,b)\in R^k\leftrightarrow(a,b)\in R^{k+1}$ (根据关系的合成，这就是$(a,b)\in R_{k+1}$ 的充要条件) 可以看到全程都是双向箭头充要条件 -
连通性关系
Let
$R$ be a relation on a set$A$ . The connectivity relation$R^\ast$ consists of all pairs$(a, b)$ s.t. there is a path (of any length) between$a$ and$b$ in$R$ . $$ R^\ast=\bigcup_{k=1}^\infin R^k=\bigcup_{k=1}^n R^k $$ 解释：$R^\ast$ 就是所有在$R$ 里连通的点对组成的集合-
Let
$A$ be a set with$n$ elements, and$R$ a relation on$A$ . If there is a path from$a$ to$b$ with$a\neq b$ , then there exists a path of length$\leq n - 1$ . If$a=b$ , path length$\leq n$ .证明：别走环
-
$R^\ast=\bigcup_{k=1}^n R^k$ 由上述引理
-
-
Theorem 2
The transitive closure of a relation
$R$ equals the connectivity relation$R^\ast$ .证明: 由定义知
$R\subseteq R^\ast$ . 需要证明: i.$R^\ast$ 是传递的 ii. 对于一切包含$R$ 的传递关系$S$ , 有$R^\ast\subseteq S$ i. If
$(a, b) \in R^\ast$ and$(b, c) \in R^\ast$ , by definition, there are paths from$a$ to$b$ and from$b$ to$c$ in$R$ . Thus, there is a path from$a$ to$c$ in$R$ . This means that$(a, c) \in R^\ast$ .ii. Suppose that
$S$ is a transitive relation containing$R$ . Then$S^n\subseteq S$ . Prove$S^n$ is also transitive: Suppose$(a,b),(b,c)\in S^n\subseteq S$ . By theo.1, there is a path from$a$ to$b$ with length$n$ and a path from$b$ to$c$ with length$n$ . So there exists$d$ s.t there is a path from$b$ to$d$ with length$1$ and a path from$d$ to$c$ with length$n-1$ . Then again by theo.1,$(b,d)\in S$ . Because$S$ is transitive,$(a,d)\in S$ . Therefore we have a path from$a$ to$d$ to$c$ with length$n$ . Then by theo.1,$(a,c)\in S^n$ . Thus,$S^n$ is transitive.Because
$S^\ast=\bigcup_{k=1}^\infin S^k$ and$S^k\subseteq S$ ,$S^\ast\subseteq S$ . Known that$R\subseteq S$ , then$R^\ast\subseteq S^\ast$ , because all connected pairs in$R$ is also in$S$ . Therefore$R^\ast\subseteq S^\ast\subseteq S$ .$\square$ -
传递闭包的矩阵
$M_{R^\ast}=M_R\lor M_R^{[2]}\lor M_R^{[3]}\lor\dots\lor M_R^{[n]}$ 沃舍尔算法:
解释：对于每一对点
$i,j$ ，遍历剩下的点$k$ ，如果$(i,k)$ 连通并且$(k,j)$ 连通，那么说明$(i,j)$ 连通，矩阵的相应位置置为 1.
-
A relation
$R$ on a set$A$ is called an equivalence relation if it is reflexive, symmetric, and transitive. 同时满足举例：$R:$ 绝对值相等的整数对集合
自反
$|a|=|a|$ . 对称$|a|=|b|\leftrightarrow|b|=|a|$ . 传递$|a|=|b|,|b|=|c|$ 则$|a|=|c|$ . -
如果两个元素
$a,b$ 由于等价关系而关联，则称它们是等价的。记法$a\sim b$ 表示对某个特定等价关系来说，$a$ 和$b$ 是等价的元素。 -
如何把一个关系搞成等价关系：1. 自反闭包 2. 对称闭包 3. 传递闭包，三步完成之后就出来个等价关系
-
等价类 Equivalence Class
Let
$R$ be an equivalence relation on a set$A$ . The set of all elements that are related to an element$a$ of$A$ is called the equivalence class of$a$ , denoted by$[a]_R$ . When only one relation is considered, we use the notation$[a]$ .$[a]_R={b\mid(a,b)\in R}$ . 其中$b$ 称为这个等价类的代表元. 一个等价类中的任何元素都可作为代表元.举例:
$R:$ 绝对值相等的整数对集合,$[a]_R={a,-a}$
-
Let R be an equivalence relation on a set A. The following statements are equivalent:
$a\ R\ b$ $[a]=[b]$ $[a]\cap[b]\neq\empty$
证明:
-
$1\to2$ 假设
$x\in[a]$ ，那么$(a,x)\in R$ 。因为$(a,b)\in R$ ，$R$ 是对称的，所以$(b,a)\in R$ 。又因为$R$ 是传递的，所以$(b,x)\in R$ ，所以$x\in [b]$ 。因此$[a]\subseteq[b]$ 。同理可得$[b]\subseteq[a]$ ，所以$[a]=[b]$ . -
$2\to3$ 因为
$[a]=[b]$ , 所以$[a]\cap[b]=[a]=[b]$ . 因为$R$ 是自反的，所以$(a,a)\in R$ ，也就是说至少有$a\in[a]$ . 所以$[a]$ 一定不为空. 所以$[a]\cap[b]\neq\empty$ . -
$3\to1$ $[a]\cap[b]\neq\empty$ 那么存在元素$c\in[a],c\in[b]$ . 所以$(a,c)\in R,(b,c)\in R$ . 根据对称性和传递性,$(a,b)\in R$ 即$a\ R \ b$ .
-
划分
Let
$S$ be a set. A collection of nonempty subsets of$S$ $A_1,A_2,\dots,A_k$ is called a partition of S if:$A_i\cap A_j=\empty,i\neq j$ and$S=\bigcup_{i=1}^k A_k$ .
- 设
$R$ 是定义在集合$S$ 上的等价关系。那么$R$ 的等价类构成$S$ 的划分。反过来，给定集合$S$ 的划分${A_i\mid i\in I}$ ，则存在一个等价关系$R$ ， 它以集合$A_i$ 作为它的等价类。
关于划分的补充说明：
-
覆盖与划分
设
$S$ 是非空集合，$\pi={A_1,A_2,\dots,A_k}$,$A_i\neq\empty$ 且满足$\forall A_i\in\pi,A_i\subseteq S$ 和$S=\bigcup_{i=1}^k A_k$ ，则称$\pi$ 是$S$ 的一个覆盖。若
$\pi={A_1,A_2,\dots,A_k}$ 为$S$ 的一个覆盖且$A_i\cap A_j=\empty,i\neq j$ ，则称$\pi$ 是$S$ 的一个划分，$A_i$ 为$S$ 的划分块。 -
商集
设
$R$ 是$S$ 上的等价关系,$R$ 的所有等价类组成的集合${[x]_R\mid x\in S}$ 叫做$S$ 关于$R$ 的商集. 记作$S/ R$ . -
设
$R$ 是$S$ 上的等价关系,$S$ 关于$R$ 的商集$S/ R$ 是$S$ 的一个划分.例：设
$A={1,2,3,4,5},R={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4),(5,5) }$ .则
$R$ 的等价类有$[1]=[2]={1,2},[3]=[4]={3,4},[5]={5}$ .所以
$A/ R={{1,2},{3,4},{5} }$ . 是$S$ 的一个划分. -
有序对
$(a,b)\in R$ 当且仅当$a,b$ 在同一个划分块中。通过该定理，已知划分可以求出对应的等价关系。
-
偏序
A relation
$R$ on a set$S$ is called a partial ordering, or partial order, if it is reflexive, antisymmetric, and transitive. A set$S$ together with a partial ordering$R$ is called a partially ordered set, or poset, denoted by$(S, R)$ . Members of$S$ are called elements of the poset.-
Example:
$(\mathbb Z,\leq)$ reflexive:$a\leq a$ . antisymmetric:$a\leq b, b\leq a$ , must$a=b$ . transitive:$a\leq b\leq c$ .$(\mathbb Z^+,\mid)$ reflexive:$a\mid a$ . antisymmetric:$a\mid b, b\mid a$ , must$a=b$ . transitive:$a\mid b\mid c$ .
-
-
可比性
The elements
$a$ and$b$ of a poset$(S,\preccurlyeq)$ are comparable if either$a \preccurlyeq b$ or$b \preccurlyeq a$ . Otherwise,$a$ and$b$ are called incomparable.解释: 首先
$\preccurlyeq$ 不是$\leq$ . 看上面偏序的定义,$(S,\preccurlyeq)$ 中的$\preccurlyeq$ 表示一个关系. 回忆一下关系的定义里，$(a,b)\in R$ 可以记作$a\ R\ b$ . 所以$a\preccurlyeq b$ 意思是$(a,b)\in \preccurlyeq$ 不是$a$ 小于等于$b$ . 读作$a$ 排在$b$ 前面($a$ precedes$b$ ). 所以为什么要用一个看上去会被误解的符号，多捞哦，而且居然还可以读作$a$ 小于等于$b$ .注:
$\preccurlyeq$ \preccurlyeq$\succcurlyeq$ \succcurlyeq$\curlyeqprec$ \curlyeqprec$\curlyeqsucc$ \curlyeqsucc这几个符号的意思是表示前驱后继，包含相等 为什么是precede(在前)和succeed(继后)，因为哈塞图-
举例:
$S={1,2,3,4,5,6}$ ,$\preccurlyeq$ 表示整除$\mid$ $2,4$ 可比，$2,5$ 不可比
-
-
全序 Total Ordering
If
$(S,\preccurlyeq)$ is a poset and every two elements of$S$ are comparable,$S$ is called a totally ordered or linearly ordered set, and$\preccurlyeq$ is called a total order or a linear order(线序). A totally ordered set is also called a chain(链).线序：哈塞图是一条线
例：$(\mathbb Z,\leq)$
-
字典序 Lexicographic Ordering
Given two posets
$(A_1,\preccurlyeq_1)$ and$(A_2,\preccurlyeq_2)$ , the lexicographic ordering on$A_1 \times A_2$ is defined by specifying that$(a_1, a_2)$ is less than$(b_1, b_2)$ , i.e.,$(a_1, a_2) \prec (b_1, b_2)$ , either if$a_1 \prec_1 b_1$ or if$a_1 = b_1$ then$a_2 \prec_2 b_2$ .
-
定义
A Hasse diagram is a visual representation of a partial ordering that leaves out edges that must be present because of the reflexive and transitive properties.
-
极大元与极小元
$a$ is a maximal (resp. minimal) element in poset$(S,\preccurlyeq)$ if there is no$b \in S$ such that$a \prec b$ (resp.$a \succ b$ ).-
Example:
$({2,4,5,10,12,20,25},\mid)$ maximal:
$12,20,25$ minimal:$2,5$
-
-
最大元与最小元
$a$ is the greatest (resp. least) element of the poset$(S,\preccurlyeq)$ if$b \preccurlyeq a$ (resp.$a \preccurlyeq b$ ) for all$b \in S$ . -
上界与下界
$u \in S$ is called an upper bound (resp. lower bound) of$A$ if$a \preccurlyeq u$ (resp.$u \preccurlyeq a$ ) for all$a \in A$ .最小上界(上确界)与最大下界(下确界):
$x \in S$ is called the least upper bound (resp. greatest lower bound) of$A$ if$x$ is an upper bound (resp. lower bound) that is less than any other upper bound (resp. lower bound) of$A$ .-
Example: Find the greatest lower bound and the least upper bound of the sets
$A={3,9,12}$ and$B={1,2,4,5,10}$ , if they exist, in the poset$(\mathbb Z^+, \mid)$ .$A:$ 上确界 36 下确界 3$B:$ 上确界 20 下确界 1 -
$\gcd$ 和$\textrm{lcm}$ 可以被定义成在偏序集$(\mathbb Z^+, \mid)$ 中的下确界和上确界.
-
-
格 Lattice
A partial ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice.
-
定义
$(S,\preccurlyeq)$ is a well-ordered set if it is a poset such that$\preccurlyeq$ is a total ordering and every nonempty subset of$S$ has a least element.良序是全序的一种，全序不一定是良序，举例
$(\mathbb Z,\leq)$ : 负整数是一个子集但是没有最小元. -
良序归纳原理 The Principle of Well-Ordering Induction
Suppose that
$S$ is a well-ordered set. For every$y \in S$ , if$P(x)$ is true for all$x \in S$ with$x \prec y$ implies$P(y)$ is true (Inductive Step), then$P(x)$ is true for all$x \in S$ .证明: 假设
$P(x)$ 不对所有$x$ 成立，那么$\exists y\in S$ 使得$P(y)$ 为假。于是集合$A={x\in S\mid\lnot P(x) }$ 是非空的。因为$S$ 是良序的，所以集合$A$ 有最小元素$a$ 。根据$a$ 是选自集合$A$ 的最小元素，可知对所有的$x\in S$ 且$x\prec a$ 都有$P(x)$ 成立。由归纳步骤可得$P(a)$ 为真，与$P(a)$ 为假矛盾。所以$P(x)$ 对所有$x\in S$ 成立。注：使用良序归纳法证明时不需要基础步骤。因为若
$x_0$ 为良序集的最小元素，则不存在$x\prec x_0$ ，由空证明知$P(x_0)$ 为真。
-
定义
Given a partial ordering
$R$ , find a total ordering$\preccurlyeq$ such that$a \preccurlyeq b$ whenever$a\ R\ b$ .$\preccurlyeq$ is said compatible with$R$ . -
每个有穷非空偏序集
$(S,\preccurlyeq)$ 至少有一个极小元. -
算法 (BFS求拓扑序)
每次从入度为0的点开始，加入拓扑序并且删除它所有的出边。
-
图 Graph
A graph
$G = (V, E)$ consists of a nonempty set$V$ of vertices (or nodes) and a set$E$ of edges. Each edge has either one or two vertices associated with it, called its endpoints (端点). An edge is said to be incident to (or connect) its endpoints. incident to: 关联 -
简单图 Simple Graph
A graph in which at most one edge joins each pair of distinct vertices (vs. multiple edges) and no edge joins a vertex to itself (= loop)
多重图 (multigraph)：有多重边
伪图 (pseudograph): 有多重边或环
-
完全图 Complete graph
$K_n$ A graph with
$n$ vertices that has an edge between each pair of vertices.边数:
$\frac{n(n-1)}{2}$
-
邻接 adjacent
Two vertices
$u, v$ in an undirected graph$G$ are called adjacent (邻接) (or neighbors) in$G$ if there is an edge$e$ between$u$ and$v$ . Such an edge$e$ is called incident with the vertices$u$ and$v$ and$e$ is said to connect$u$ and$v$ . -
邻居 neighborhood
The set of all neighbors of a vertex
$v$ of$G = (V, E)$ , denoted by$N(v)$ , is called the neighborhood of$v$ . If$A$ is a subset of$V$ , we denote by$N(A)$ the set of all vertices in$G$ that are adjacent to at least one vertex in$A$ . -
度 degree
The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes two to the degree of that vertex. The degree of the vertex
$v$ is denoted by$\deg(v)$ .
-
握手定理 Handshaking Theorem
If
$G = (V, E)$ is an undirected graph with$m$ edges, then$2m=\sum_{v\in V}\deg(v)$ .伪图也成立
证明：这还用证？一条边贡献两个度
-
An undirected graph has an even number of vertices of odd degree.
证明：总度数是偶数（握手定理）
-
-
定义
An directed graph
$G = (V, E)$ consists of$V$ , a nonempty set of vertices, and$E$ , a set of directed edges. Each edge is an ordered pair of vertices. The directed edge$(u, v)$ is said to start at$u$ and end at$v$ . -
邻接到
$v$ , 从$u$ 邻接Let
$(u, v)$ be an edge in$G$ . Then$u$ is the initial vertex of the edge and is adjacent to$v$ and$v$ is the terminal vertex of this edge and is adjacent from$u$ . The initial and terminal vertices of a loop are the same. -
入度和出度
The in-degree of a vertex
$v$ , denoted by$\deg^-(v)$ , is the number of edges which terminate at$v$ . The out-degree of$v$ , denoted by$\deg^+(v)$ , is the number of edges with$v$ as their initial vertex. Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of the vertex.
- Let
$G = (V, E)$ be a graph with directed edges. Then$\sum_{v\in V}\deg^-(v)=\sum_{v\in V}\deg^+(v)=|E|$ .
-
完全图 Complete Graph
A complete graph on
$n$ vertices, denoted by$K_n$ , is the simple graph that contains exactly one edge between each pair of distinct vertices. -
圈图 Cycle
A cycle
$C_n$ for$n \geq 3$ consists of$n$ vertices$v_1,v_2,\dots,v_n$ , and edges${v_1,v_2},{v_2,v_3},\dots,{v_{n-1},v_n}$ . -
轮图 Wheel
A wheel
$W_n$ is obtained by adding an additional vertex to a cycle$C_n$ . -
$n$ 立方体图An
$n$ -dimensional hypercube, or$n$ -cube,$Q_n$ is a graph with$2^n$ vertices representing all bit strings of length$n$ , where there is an edge between two vertices that differ in exactly one bit position.边数:
$n2^{n-1}$
-
定义
A simple graph
$G$ is bipartite if$V$ can be partitioned into two disjoint subsets$V_1$ and$V_2$ such that every edge connects a vertex in$V_1$ and a vertex in$V_2$ .An equivalent definition of a bipartite graph is a graph where it is possible to color the vertices red or blue so that no two adjacent vertices are of the same color.
判断：不能有奇数边的环
-
完全二分图
A complete bipartite graph
$K_{m,n}$ is a graph that has its vertex set partitioned into two subsets$V_1$ of size$m$ and$V_2$ of size$n$ such that there is an edge from every vertex in$V_1$ to every vertex in$V_2$ . -
匹配 Matching
Matching the elements of one set to elements in another. A matching is a subset of
$E$ s.t. no two edges are incident with the same vertex.A maximum matching (最大匹配) is a matching with the largest number of edges.
A matching
$M$ in a bipartite graph$G = (V, E)$ with bipartition$(V_1,V_2)$ is a complete matching (完全匹配) from$V_1$ to$V_2$ if every vertex in$V_1$ is the endpoint of an edge in the matching, or equivalently, if$|M|=|V_1|$ . -
霍尔婚姻定理 Hall's Marriage Theorem
The bipartite graph
$G = (V, E)$ with bipartition$(V_1,V_2)$ has a complete matching from$V_1$ to$V_2$ if and only if$|N(A)| \geq |A|$ for all subsets$A$ of$V_1$ .证明: 强归纳法
-
必要性
设从
$V_1$ 到$V_2$ 存在一个完全匹配$M$ 。那么，若$A\subseteq V_1$ ，对于$A$ 中的每个顶点$v\in A$ ，在$M$ 中存在一条边连接$v$ 和$V_2$ 中的某个顶点。因此，在$V_2$ 中与$V_1$ 的顶点相邻的点的个数至少与$V_1$ 中顶点个数一样多，即$|N(A)|\geq |A|$ 。 -
充分性
基础步骤：若
$|V_1|=1$ ，则$V_1$ 只包含一个顶点$v_0$ ，因为$N({v_0})\geq|{v_0}|=1$ ，所以至少有一条边连接顶点$v_0$ 和一个顶点$w_0\in V_2$ 。任何一条这样的边都是从$V_1$ 到$V_2$ 的一个完全匹配。归纳假设：令
$k$ 是一个正整数。若$G=(V,E)$ 是带有二部划分$(V_1,V_2)$ 的二分图，且$|V_1|=j\leq k$ ，则对于所有$A\subseteq V_1$ ，若满足$|N(A)|\geq|A|$ ，就存在一个$V_1$ 到$V_2$ 的完全匹配。（强归纳法的假设）归纳步骤：假设
$H=(W,F)$ 是由二部划分$(W_1,W_2)$ 构成的二分图且$|W_1|=k+1$ 。分两种情况讨论 ($\geq$ 分成$>$ 和$=$ )。-
假设对所有满足
$1\leq j\leq k$ 的整数$j$ ，$W_1$ 中每个含有$j$ 个元素的子集中的顶点都至少与$W_2$ 中的$j+1$ 个顶点相邻 ($>$ 的情况)。选择一个顶点$v\in W_1$ 和$w\in N({v})$ ，根据假设，一定存在这样的$v,w$ 。从$H$ 中删除$v,w$ 以及所有与它们关联的边，得到一个二部划分为$(W_1-{v},W_2-{w})$ 的二分图$H'$ 。因为$|W_1-{v}|=k$ ，所以由归纳假设可知存在一个从$W_1-{v}$ 到$W_2-{w}$ 的完全匹配。在这个匹配中加入从$v$ 到$w$ 的边，就得到一个从$W_1$ 到$W_2$ 的完全匹配。 -
假设对所有满足
$1\leq j\leq k$ 的整数$j$ ，存在一个含有$j$ 个顶点的子集$W_1'$ ，且在$W_2$ 中恰好有$j$ 个邻居和这些顶点相邻。令$W_2'$ 是这些邻点的集合。由归纳假设可知存在一个从$W_1'$ 到$W_2'$ 的完全匹配。从$W_1,W_2$ 中删除这$2j$ 个顶点以及与它们相关联的边，就得到一个二部划分为$(W_1-W_1',W_2-W_2')$ 的二分图$K$ 。接下来证明在
$K$ 中，对于$W_1-W_1'$ 的所有子集$A$ 满足$|N(A)|\geq |A|$ 。反证法：如果不成立，则存在一个关于$W_1-W_1'$ 的含有$t$ 个顶点的子集$B$ ，其中$1\leq t\leq k+1-j$ ，并且$B$ 中的顶点在$W_2-W_2'$ 中的邻点少于$t$ 个。那么$W_1$ 中存在一个有$j+t$ 个顶点的子集，这个子集包含$B$ 中的这$t$ 个顶点和$W_1'$ 中的$j$ 个顶点 ($B\cup W_1'$ )。由于$W_1'$ 在$W_2$ 中恰有$j$ 个邻点，所以这$j+t$ 个顶点在$W_2$ 中的邻点少于$j+t$ 个，这与对于$W_1$ 的所有子集$A$ 满足$|N(A)|\geq |A|$ 矛盾。所以不存在这样的$B$ 。因此对于$W_1-W_1'$ 的所有子集$A$ 满足$|N(A)|\geq |A|$ 。所以，根据归纳假设，$K$ 有一个完全匹配。把这个完全匹配与
$W_1'$ 到$W_2'$ 的完全匹配合并，就得到了一个从$W_1$ 到$W_2$ 的完全匹配。所以$k+1$ 时成立。
归纳结论：若对于所有
$A\subseteq V_1$ 有$|N(A)|\geq |A|$ ，则存在一个从$V_1$ 到$V_2$ 的完全匹配。 -
-
-
子图 Subgraph
A subgraph of a graph
$G = (V, E)$ is a graph$(W, F)$ , where$W \subseteq V$ and$F \subseteq E$ . A subgraph$H$ of$G$ is a proper subgraph (真子图) of$G$ if$H \neq G$ . -
导出的子图
$G=(V,E)$ 是一个简单图。图$(W,F)$ 是由顶点$V$ 的子集$W$ 导出的子图，其中边集$F$ 包含$E$ 中的一条边当且仅当这条边的两个端点都在$W$ 中。 -
并图 Union of Graphs
The union of two simple graphs
$G_1 = (V_1, E_1)$ and$G_2 = (V_2, E_2)$ is the simple graph with vertex set$V_1 \cup V_2$ and edge set$E_1 \cup E_2$ , denoted by$G_1 \cup G_2$ .
-
邻接表 Adjacency List
An adjacency list can be used to represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph.
-
邻接矩阵 Adjacency Matrix
Suppose that
$G = (V, E)$ is a simple graph with$|V| = n$ . Arbitrarily list the vertices of$G$ as$v_1,v_2,\dots,v_n$ . The adjacency matrix$A_G$ of$G$ , is the$n \times n$ zero-one matrix with$1$ as its$(i , j)-th$ entry when$v_i$ and$v_j$ are adjacent, and$0$ as its$(i , j)-th$ entry when they are not adjacent.$A_G=[a_{ij}]{n\times n}$, where $a{ij}=\begin{cases}1&(v_i,v_j)\in E\cr0&otherwise \end{cases}$.
Adjacency matrices can also be used to represent graphs with loops and multiple edges. The matrix is no longer a zero-one matrix.
-
关联矩阵 Incidence Matrix
Let
$G = (V, E)$ be an undirected graph with vertices$v_1,v_2,\dots,v_n$ and edges$e_1,e_2,\dots,e_m$ . The incidence matrix with respect to the ordering of$V$ and$E$ is the$n \times m$ matrix $M = [m_{ij} ]{n\times m}$, where $m{ij}=\begin{cases}1&e_j\ is \ incident \ with\ v_i\cr0&otherwise \end{cases}$.
-
定义
The simple graphs
$G_1 = (V_1, E_1)$ and$G_2 = (V_2, E_2)$ are isomorphic (同构的) if there is a one-to-one and onto (bijective) function from$V_1$ to$V_2$ with the property that$a$ and$b$ are adjacent in$G_1$ if and only if$f (a)$ and$f (b)$ are adjacent in$G_2$ , for all$a$ and$b$ in$V_1$ . Such a function is called an isomorphism (同构).说人话：两个图把点挪挪能整成完全一样的外观，就是同构的
注：同构指的是一个一一对应函数
Example:
-
图形不变量 Graph Invariants
在图的同构中保持不变的属性.
例：顶点数，边数，所有顶点的度
作用：判断两个图不是重构的。常用的是度，列出两个图所有顶点的度序列看是否匹配。
Example:
这两个图，点数一样，边数一样，都是4个度为2的顶点和4个度为3的顶点。
但是它们不同构，因为
$G$ 里所有度为2的点的邻点都是度为3的，而$H$ 不是。
-
定义
Let
$n$ be a nonnegative integer and$G$ an undirected graph. A path of length$n$ from$u$ to$v$ in$G$ is a sequence of$n$ edges$e_1,e_2,\dots,e_n$ of$G$ for which there exists a sequence$x_0 = u, x_1,\dots, x_{n-1}, x_n = v$ of vertices such that$e_i$ has the endpoints$x_{i-1}$ and$x_i$ for$i = 1,\dots,n$ . The path is a circuit (回路) if it begins and ends at the same vertex, i.e., if$u = v$ and has length greater than zero. A path or circuit is simple if it does not contain repeating vertices.Length of a path = # of edges on path.
注：除了通路之外还有顶点和边交替的序列，叫做路径 (walk) 以及闭合路径 (closed walk)。不经过重复边的路径叫路线 (trail)。书上关于简单通路的定义是不经过重复边，可以半路拐出去走个圈再拐回来，这实际上是路线。书上的解释是，当你使用路线这个术语时，简单通路就表示不经过重复点的路线。难受不难受，不能统一定义？？
-
If there is a path between two distinct vertices
$x$ and$y$ of a graph$G$ , then there is a simple path between$x$ and$y$ in$G$ .Proof: delete loops
-
The existence of a simple circuit of length
$k$ is isomorphic invariant.
- Two vertices are connected if there is a path between them.
- An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph.
- There is a simple path between every pair of distinct vertices of a connected undirected graph.
-
强连通性
A directed graph is strongly connected (强连通) if there is a path from
$a$ to$b$ and a path from$b$ to$a$ whenever$a$ and$b$ are vertices in the graph. -
弱连通性
A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph, which is the undirected graph obtained by ignoring the directions of the edges in the directed graph.
-
连通分支 (连通分量) Connected Components
A connected component of a graph G is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G.
注: 1. 连通 2. 最大
在有向图里就是强连通分量 (SCC)
-
割点与割边
Sometimes the removal from a graph of a vertex and all incident edges disconnect the graph. Such vertices are called cut vertices (割点). Similarly we may define cut edges (割边 or 桥).
-
边割集与边连通度
A set of edges
$E'$ is called an edge cut (边割集) of$G$ if the subgraph$G - E'$ is disconnected. The edge connectivity$\lambda(G)$ is the minimum number of edges in an edge cut of$G$ .边连通度：最小边割集的边数
-
$n$ 个顶点的图的边连通度满足$0\leq\lambda(G)\leq n-1$ -
$n$ 个顶点的完全图$\lambda(K_n)=n-1$ 充要条件
-
-
点割集与点连通度
点集
$V'$ 是$V$ 的子集，若$G-V'$ 是不连通的，则称$V'$ 是点割集或分割集。非完全图的点连通度$\kappa(G)$ 是最小点割集的顶点数。不可分割图：不含割点的图，例如
$K_n,n\geq3$ 。对于完全图$K_n$ ，$\kappa(K_n)=n-1$。若
$\kappa(G)\geq k$ ，称图$G$ 是$k$ 连通的。 -
点连通度与边连通度的关系
$\kappa(G)\leq\lambda(G)\leq\min_{v\in V}\deg(v)$ - 不连通图
$\kappa(G)=\lambda(G)=0$ - 完全图
$\kappa(K_n)=\lambda(K_n)=n-1$
-
Let
$G$ be a graph with adjacency matrix$A$ with respect to the ordering$v_1,v_2,\dots,v_n$ of vertices. The number of different paths of length$r$ from$v_i$ to$v_j$ , where$r > 0$ is positive, equals the$(i , j)$ -th entry of$A^r$ .证明：数学归纳法
邻接矩阵
$A$ 的第$(i,j)$ 项表示$v_i,v_j$ 之间长度为 1 的通路的个数。设
$A^r$ 的第$(i,j)$ 项表示$v_i,v_j$ 之间长度为$r$ 的通路的个数。那么$A^{r+1}=A^rA$ 的第$(i,j)$ 项等于$\sum_{k=1}^n b_{ik}a_{kj}$ .$b_{ik}$ 是$v_i$ 到$v_k$ 长度为$r$ 的通路的个数，$a_{kj}$ 是$v_k$ 到$v_j$ 长度为 1 的通路的个数。根据乘法原理和加法原理，$A^{r+1}$ 的第$(i,j)$ 项是$v_i,v_j$ 之间长度为$r+1$ 的通路的个数。由归纳法，定理成立。
-
定义
Let
$G^\alpha$ be an weighted graph, with a weight function$\alpha : E \to R$ on its edges. If$P = e_1e_2 \dots e_k$ is a path, then its weight is$\alpha(P) =\sum_{i=1}^k\alpha(e_i)$ . The minimum weighted distance between two vertices is$d(u,v)=\min{\alpha(P)\mid P:u\to v}$ . -
迪杰斯特拉算法 Dijkstra's Algorithm
堆优化堆优化堆优化堆优化堆优化堆优化
-
定义
An Euler circuit in a graph
$G$ is a simple circuit containing every edge of$G$ . An Euler path in$G$ is a simple path containing every edge of$G$ .解释：哥尼斯堡七桥问题 (欧拉回路)，一笔画问题 (欧拉通路)
-
欧拉回路的充要条件
A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.
解释：
-
必要性：每次经过一个点都给这个点贡献两个度，起点也是，因为最后回来了
-
充分性：构造欧拉回路的算法
-
-
欧拉通路的充要条件
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.
-
定义
A simple path in a graph
$G$ that passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph$G$ that passes through every vertex exactly once is called a Hamilton circuit. -
狄拉克定理 Dirac's Theorem
If
$G$ is a simple graph with$n \geq 3$ vertices such that the degree of every vertex in$G$ is at least$\frac n2$ , then$G$ has a Hamilton circuit. -
欧尔定理 Ore's Theorem
If
$G$ is a simple graph with$n \geq 3$ vertices such that$\deg(u) + \deg(v) \geq n$ for every pair of nonadjacent vertices, then$G$ has a Hamilton circuit.狄拉克定理是欧尔定理的一个推论。
这两条定理都只是充分条件。
-
求哈密顿通路/回路是一个NP完全问题，例：旅行商问题。
-
A graph is called planar if it can be drawn in the plane without any edges crossing. Such a drawing is called a planar representation of the graph.
解释：一个图可以画成没有交叉的边，就是平面图
-
欧拉公式
Let
$G$ be a connected planar simple graph with$e$ edges and$v$ vertices. Let$r$ be the number of regions in a planar representation of$G$ . Then$r = e - v + 2$ .证明：数学归纳法
基础情况：$r=1, e=1, v=2$
归纳假设：设有
$k$ 条边的平面图满足$r_k=e_k-v_k+2$ .归纳步骤：设
${a_{k+1},b_{k+1} }$ 是为了获得$G_{k+1}$ 而添加到$G_k$ 上的新边。那么有两种情况，第一种情况是$a_{k+1}, b_{k+1}$ 都在$G_k$ 中。那么这两个顶点必然在一个公共面$R$ 的边界上，否则${a_{k+1},b_{k+1} }$ 就会与其他边交叉。在这种情况下$r_{k+1}=r_k+1,v_{k+1}=v_k,e_{k+1}=e_k+1$ 。因为$r_k=e_k-v_k+2$ ，两边同时加 1 就得到$r_{k+1}=e_{k+1}-v_{k+1}+2$ 。第二种情况是新边的两个顶点之一不在$G_k$ 中，假设是$b_{k+1}$ 。为了不交叉，$b_{k+1}$ 必须在一个边界上有$a_{k+1}$ 的面内部。在这种情况下，$r_{k+1}=r_k,v_{k+1}=v_k+1,e_{k+1}=e_k+1$，仍然可得$r_{k+1}=e_{k+1}-v_{k+1}+2$ 。结论：由归纳法，$r = e - v + 2$。
-
面的度 The Degree of Regions
The degree of a region is defined to be the number of edges on the boundary of this region. When an edge occurs twice on the boundary, it contributes two to the degree.
解释：比如右上角那个面
$R$ 的度是 8，${a_{k+1},b_{k+1} }$ 贡献 2 个度。 -
推论 1
If
$G$ is a connected planar simple graph with$e$ edges and$v$ vertices, where$v \geq 3$ , then$e \leq 3v - 6$ .Proof: The degree of every region is at least 3.
The sum of the degrees of the regions is exactly twice the number of edges in the graph, which means
$2e=\sum\deg(R)\geq 3r$ . And we have$r=e-v+2$ , therefore$e\leq 3v-6$ . -
推论 2
If
$G$ is a connected planar simple graph, then$G$ has a vertex of degree not exceeding 5.Proof by contradiction:
Suppose all vertexes have degree more than 5. By handshaking theorem,
$2e\geq 6v$ and$e\geq 3v$ , which contradicts to corollary 1.这个定理可以显然地推出六色定理。
-
推论 3
In a connected planar simple graph has
$e$ edges and$v$ vertices with$v \geq 3$ and no circuits of length three, then$e \leq 2v - 4$ .Proof: The degree of every region is at least 4, because no circuits of length 3.
-
柏拉图多面体 Platonic Solids
-
同胚 homomorphic
If a graph is planar, so will be any graph obtained by removing an edge
${u,v}$ and adding a new vertex$w$ together with edges${u,w}$ and${w,v}$ . Such an operation is called an elementary subdivision (初等细分). The graphs$G_1 = (V_1, E_1)$ and$G_2 = (V_2, E_2)$ are called homomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions.解释：初等细分就是你找一条边，在边上画个新点给他变成两条边。当然你点在外面也行，图的结构跟画法无关，还是可以给你拽回来。
-
库拉图斯基定理 Kuratowski's Theorem
A graph is nonplanar if and only if it contains a subgraph homomorphic to
$K_{3,3}$ or$K_5$ .
-
着色
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.
-
着色数 chromatic number
The chromatic number of a graph is the least number of colors needed for a coloring of this graph, denoted by
$\chi(G)$ .
-
一些特殊图的着色数
$\chi(K_n)=n,\chi(K_{m,n})=2,\chi(C_n)=\begin{cases}2&n\ is \ even,n\geq 4\cr3&n\ is \ odd,n\geq 3 \end{cases}$
- The chromatic number of a planar graph is no greater than four.
- 证明：1976 年由计算机穷举证明，至今没有演绎推理
- 五色定理用归纳法很好证
-
A tree is a connected undirected graph with no simple circuits.
-
Theorem. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.
-
有根树 Rooted Tree
A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.
-
树的结点分类
parent, child, sibling (兄弟)
ancestor (祖先), descendant (后代)
leaf, internal vertex
-
子树
subtree with
$a$ as its root: consists of$a$ and its descendants and all edges incident to these descendants.
-
定义
A rooted tree is called an
$m$ -ary tree if every internal vertex has no more than$m$ children. The tree is called a full$m$ -ary tree if every internal vertex has exactly$m$ children. In particular, an$m$ -ary tree with$m = 2$ is called a binary tree. -
有序根树
A binary tree is an ordered rooted tree where the children of each internal vertex are ordered. In a binary tree, the first child is called the left child, and the second child is called the right child.
-
性质
A full
$m$ -ary tree with(i)
$n$ vertices,$i = \frac{(n - 1)}{m}$ ,$l=\frac{(m - 1)n + 1}{m}$ (ii)$i$ internal vertices,$n = mi + 1$ ,$l = (m - 1)i + 1$ (iii)$l$ leaves,$n = \frac{ml-1}{m - 1}$ ,$i = \frac{l- 1}{m - 1}$ 解释：$n = mi + 1$.
$i$ 个内部结点，每个有$m$ 个孩子，想象一下从上而下，最后差一个根节点。 -
层与高度
The level of a vertex
$v$ in a rooted tree is the length of the unique path from the root to this vertex. 深度 depthThe height of a rooted tree is the maximum of the levels of the vertices.
-
平衡树
A rooted
$m$ -ary tree of height$h$ is balanced if all leaves are at levels$h$ or$h - 1$ . -
叶结点个数
There are at most
$m^h$ leaves in an$m$ -ary tree of height$h$ .深度为
$i$ 的层最多$m^i$ 个结点。
- A binary tree is an ordered rooted tree where each internal tree has two children, the first is called the left child and the second is the right child. The tree rooted at the left child of a vertex is called the left subtree of this vertex, and the tree rooted at the right child of a vertex is called the right subtree of this vertex.
-
Let
$T$ be an ordered rooted tree with root$r$ . If$T$ consists only of$r$ , then$r$ is the preorder traversal of$T$ . Otherwise, suppose that$T_1,T_2, \dots ,T_n$ are the subtrees of$r$ from left to right in$T$ . The preorder traversal begins by visiting$r$ , and continues by traversing$T_1$ in preorder, then$T_2$ in preorder, and so on, until$T_n$ is traversed in preorder.总结：根左右
-
二叉树的前序遍历
void preorder(Node root) { if (root==null) return; print(root.val); preorder(root.left); preorder(root.right); }
-
Let
$T$ be an ordered rooted tree with root$r$ . If$T$ consists only of$r$ , then$r$ is the inorder traversal of$T$ . Otherwise, suppose that$T_1,T_2, \dots ,T_n$ are the subtrees of$r$ from left to right in$T$ . The inorder traversal begins by traversing$T_1$ in inorder, then visiting$r$ , and continues by traversing$T_2$ in inorder, and so on, until$T_n$ is traversed in inorder.左根右
-
二叉树的中序遍历
void inorder(Node root) { if (root==null) return; inorder(root.left); print(root.val); inorder(root.right); }
-
Let
$T$ be an ordered rooted tree with root$r$ . If$T$ consists only of$r$ , then$r$ is the postorder traversal of$T$ . Otherwise, suppose that$T_1,T_2, \dots ,T_n$ are the subtrees of$r$ from left to right in$T$ . The postorder traversal begins by traversing$T_1$ in postorder, then$T_2$ in postorder, and so on, after$T_n$ is traversed in postorder,$r$ is visited.左右根
-
二叉树的后序遍历
void postorder(Node root) { if (root==null) return; postorder(root.left); postorder(root.right); print(root.val); }
前序：第一次经过一个结点时就列出这个结点
中序：第一次经过叶结点时列出，第二次经过内部结点时列出
后序：第二次经过结点时列出
- An inorder traversal of the tree representing an expression produces the original expression when parentheses are included except for unary operation.
- 规则：访问左子树时加左括号，访问完右子树时加右括号
- 结果:
$(((x+y)\uparrow2)+((x-4)/3))$
-
The preorder traversal of expression trees leads to the prefix form of the expression (Polish notation).
-
Operators precede their operands in the prefix notation. Parentheses are not needed as the representation is unambiguous.
运算符在前运算数在后，不需要括号
-
Prefix expressions are evaluated by working from right to left. When we encounter an operator, we perform the operation with the two operands to the right.
-
计算
-
The postorder traversal of expression trees leads to the postfix form of the expression (reverse Polish notation).
-
Operators follow their operands in the post x notation. Parentheses are not needed as the representation is unambiguous.
运算数在前运算符在后，不需要括号
-
Post fix expressions are evaluated by working from left to right. When we encounter an operator, we perform the operation with the two operands to the left.
-
计算
代码实现：遍历 + 一个运算数栈
- Let
$G$ be a simple graph. A spanning tree of$G$ is a subgraph of$G$ that is a tree containing every vertex of$G$ . - Theorem. A simple graph is connected if and only if it has a spanning tree.
具体见 DSAA
DFS 求生成树
具体见 DSAA
BFS 求生成树
-
定义
A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges.
-
Prim 算法
堆堆堆堆堆堆堆堆堆堆堆堆堆堆堆堆堆堆
-
Kruskal 算法
并查集并查集并查集并查集并查集并查集并查集路径压缩路径压缩路径压缩路径压缩路径压缩路径压缩