离散数学随笔

Posted on Edited on

本文的编撰仅面向作者本人

1.6 Rules of Inference

  1. Modus ponens 假言推理 p & p->q => q
  2. Modus tollens 取拒式 !q & p->q => !p
  3. Hypothetical syllogism /,haɪpə'θɛtɪk, 'sɪlə,dʒɪz(ə)m/ 假言三段论 p->q & q->r => p->r
  4. Disjunctive syllogism 析取三段论 pVq & !p = p
  5. Addtion 附加律 p => pVq （附加在析取式中）
  6. Simplification 化简律 p&&q => p （合取条件的拆分）
  7. Resolution 消解律 pVq & !pVr => qVr 条件相斥必有一T
  8. ? Logical equivalence

$$ \begin{aligned} Step & Reason \ 1. xxx & Premise \ 2. xxx & Contrapositive,of,(1) \ 3. xxx & XXrule,using,(n),and,(m) \end{aligned} $$

Fallacies 谬误

  1. fallacy of affirming the conclusion 肯定结论的谬误 由结论推出条件
  2. fallacy of denying the hypothesis /haɪ'pɒθɪsɪs/ 否定假设的谬误 从否定条件推出否定结论

Rules of Inference for Quantified Statements 量化命题的推理规则

  1. Universal instantiation 全称实例 $\forall xP(x) \implies P(c)$
  2. Universal generalization 全称引入 $P(c)$ for an arbitrary $c \implies \forall xP(x)$
  3. Existential instantiaion 存在实例 $\exists xP(x) \implies P(c)$ for some element $c$
  4. Existencial generalization 存在引入 $P(c)$ for some element $c \implies \exists xP(x)$

Combining Rules of Inference for Propositions and Quantified Statements

  1. Universal modus ponens 全称假言推理 对某个全称实例应用假言推理
  2. Universal modus tollens 全称取拒式 对某个全称实例应用取拒式（否定结论推出否定条件）

1.7 Introduction to Proofs

  1. theorem /'θɪərəm/ 定理 （定理的证明有定义、其他定理、公理、推断规则）
  2. lemma /'lemə/ 引理 用于证明定理的其他定理
  3. corollary /kə'rɒlərɪ/ 推论 定理下的直接结论
  4. propositions 命题 偶尔用来称呼不重要的定理，或称事实、结论
  5. conjecture /kən'dʒektʃə/ 猜想 一旦找到证明，猜想就变成定理；也有可能被证伪

To Proof p->q (or to proof p)

  1. Trivial Proof : 平凡证明 if q is true then p->q is true.
  2. Vacuous Proof : 空证明 if p is false then p->q is true.
  3. Direct Proof : Assume p is true and show that q is true by using inferences, axioms, logical equivalences.
  4. Indirect Proof : not begin with the premises and not end with the conclusion
  5. Proof by contraposition 反证法 : Assume !q and show !p is true also. 直接证明法无效时尝试反证法
  6. Proof by Contradiction 归谬证明法 : To proof p, first find a r such that !p -> (r && !r) is true, therefore !p is false and p is true. 假设结论的否定为真，引出一个矛盾
  7. 反例证明法 : 指明一个反例，从而证伪

1.8 Proof Methods and Strategy 证明的方法和策略

  1. Proof by cases 分情形证明法 tautology : (p1Vp2V...pn)->q <-> (p1->q)&&(p2->q)&&...(pn->q) 类似分类讨论
  2. Exhaustive Proof 穷举证明法 当变量的取值比较少的时候，通过测试所有情形来证明。
  3. Without loss of generality (WLOG) 不失一般性 省略非常类似的情形（证明过程几乎相同）的证明

Existence Proof 存在性证明

To proof $\exists x P(x)$ :

  1. Constructive existence proof 构造性 : Find an explicit c, for which P(c) is true.
  2. Nonconstructive existence proof 非构造性证明 ： 不直接构造例子，但说明多种情况之一必有符合的例子；或若不存在，就得到某些矛盾。

Uniqueness Proof 唯一性证明

同时证明存在性和唯一性，即x符合某种期望，而若y!=x，则y不符合这种期望。也可以等价地证明若y符合这种期望，则y=x。

Set

  1. The cardinality of a finite set A 集合的基数，|A|
  2. finite 有限的 /faɪnaɪt/
  3. infinite 无限的 /'ɪnfɪnət/
  4. Power Set 幂集 P(A) The set of all subsets of a set A. $|P(A)| = 2^{|A|}$
  5. Cartesian Product 笛卡尔积 A x B x C的意义和(A x B) x C不一样！
  6. coordinate

Set Operations

  1. Union /'junɪən/
  2. Intersection
  3. Complementation : complement 补集，必须有universal set U。A上一横杠
  4. Difference 不满足交换律，A-B
  5. Symmetric Difference 对称差 异或

Set Identities 集合恒等式

  1. 注意一下分配率，德摩根律（否定去括号）
  2. 其他不管啊太简单了
  3. Membership Tables 成员表，枚举任意元素属于各个集合情况，从而验证恒等式（和真值表类似）

Funtion (f maps A to B) (f is a mapping from A to B)

  1. assignment 指派，分配。 指定f(a)=b。
  2. domain 定义域 A
  3. codomain 陪域 B
  4. image 像 b is an image of a under f
  5. preimage 原像 可能是单个元素，也可能是一个集合。
  6. f(A) range 值域
  7. 等价的函数具有相同的domain & codomain & map each element to the same element of the codomain
  8. $f(S) = {f(s)|s\in S}$
  9. $(f_1+f_2)(x) = f_1(x)+f_2(x)$
  10. $(f_1*f_2)(x) = f_1(x)*f_2(x)$
  11. injection injective 单射 one-to-one 可在值域上定义反函数
  12. surjection surjective (or onto) 满射 映上 陪域中每个元素都能找到原像
  13. injective and surjective => bijection or one-to-one correspondence 双射 一一对应
  14. invertible 可逆的 Inverse Function 反函数
  15. Composition 复合函数 $f \circ g = f(g(x))$
  16. Factorial/fæk'tɔrɪəl/ Function 阶乘函数
  17. Partial Function 局部函数，对某个函数截取部分domain

Sequence 序列 ${a_n}$

A funtion from N or N+ to S
$$a_n = f(n)$$

  1. term 项
  2. Geometric Progression 几何级数 a*r^n, n=0,1... (a and r are real numbers)
  3. Arithmetic Progression 算术级数 （等差数列）
  4. Recurrence relation 递推关系
  5. a solution of a recurrence relation 满足递推关系的序列称为这个递推关系的一个解
  6. initial conditions 初始条件 递推关系生效前的所有terms
  7. solving the recurrence relation 找到通项公式 这样的公式叫closed formula闭公式
  8. iteration 迭代法，正向替换 working upward； 反向替换 working downward。 用于猜测formula，然后用the method of induction数学归纳法证明。
  9. Summation （序列的部分）总和
  10. in lexicographic order /,lɛksɪkə'græfɪk/ 字典序

Matrices 矩阵

  1. Boolean Product 布尔积 类似矩阵乘法，各项求交之后求并
  2. Boolean Powers 多次布尔积。 写作$A^{[n]}$, 记$A^{[n]}=I$

Algorithm

  1. pseudocode /'sju:doˌkod/ 伪代码
  2. Halt Problem 停机问题，无解
  3. Big-O f(x) of big-O of g(x)
  4. |f(x)| < |c*g(x)| (x > k) : the constants c and k are called witnesses. Only one pair of witnesses is needed.
  5. if f = O(g) && g = O(f), then the two functions are of the same order.
  6. polynomial /,pɒlɪ'nəʊmɪəl/ 多项式
  7. if |f(x)| > |C*g(x)| (x > k) : Big-Omega
  8. if f = O(g) && g = O(f), then f = θ(g) : Big-Theta; f(x) is of order g(x).
  9. brute-force 蛮力（算法）
  10. Tractable Problem ：P类问题，多项式时间内解决
  11. Intractable Problem
  12. Unsolvable Problem 无解的问题，例如Halt Problem
  13. Class NP: 可在多项式时间内验证一个解的问题
  14. NP Complete Class: NPC问题，所有的NP问题都能约化为NPC问题。

Number Theory and Cryptography 数论和密码学

/krɪp'tɑgrəfi/

  1. divisibility /di,vizi'biləti/ 可除性
  2. hexadecimal /,hɛksə'dɛsɪml/ 十六进制（的）
  3. modular /'mɑdjʊlɚ/ 模的
  4. congruence 同余 /'kɑŋgrʊəns/
  5. a divides b a除b， a is a factor or divisor of b, b is a multiple of a.
  6. quotient /'kwoʃnt/商; remainder /rɪ'mendɚ/余数
  7. -11 / 3 = -4 ... 1
  8. The notation a ≡ b (mod m) says that a is congruent to b modulo m. a ≡ b (mod m) is a congruence and that m is its modulus.
  9. doing arithmatic modulo m: $a+_mb = (a+b) \mod m; a*_mb = (a*b) \mod m$

Zm = {0...m-1}

  1. Closure 封闭性
  2. Associativity 结合律
  3. Commutativity 交换律
  4. Identity element 单位元 （加法0，乘法1）
  5. Additive inverse 加法逆元
  6. Distributivity 分配率
  7. 判定同余式，左边减右边是m的倍数。

Prime

  1. composite /kɑm'pɑzɪt/ 合数
  2. divisible by 7 能被7整除
  3. Mersenne Primes 梅森素数：满足2的素数次方减一的素数。检验2的素数次方减一是否素数是容易的，由此得到已知的最大素数。$2^{11}-1不是素数$
  4. Prime Number Theorem: 不超过x的素数个数大约是(x / ln x)，任取一个不超过n的数，则这个数是素数的概率是1/lnx。
  5. 对两个互质的数a,b:ak+b可以生成无限个素数。
  6. 存在由任意个素数组成的等差数列（Arithmetic Progression）
  7. 现阶段没有发现高效生成素数的算法f(n)
  8. 不存在多项式函数f(n)使得其值一定是素数
  9. Goldbach’s Conjecture 哥德巴赫猜想：所有大于2的偶数都能表示为两个素数的和。
  10. Conjecture: There are infinitly many primes of the form $n^2+1$.
  11. The Twin Prime Conjecture: 相差2的素数有无限多组

Great Commom Divisor /dɪ'vaɪzɚ/

  1. relatively prime 互质数
  2. pairwise relatively prime 两两互质
  3. Prime Factorizations /,fæktərai'zeiʃən/ 质因数分解
  4. Least Common Multiple 最小公倍数 lcm(a,b)
  5. Euclidean /ju:'klidiən/ 欧几里得的
  6. Bézout’s Theorem 贝祖定理 gcd(a,b) = sa+tb. （求s、t用扩展欧几里得）
  7. if gcd(a,b)=1 && a|bc, then a|c; Therefore, a ≡ b (mod m) if ac ≡ bc (mod m) && gcd(c,m)=1.

Solving Congruences

  1. linear congruences 线性同余方程 ax≡b ( mod m)
  2. an inverse of A modulo m 模m下a的乘法逆元
  3. 逆元存在的充要条件：若gcd(a,m)=1, 则存在a在模m下的乘法逆元。 Proof: Since gcd(a,m)=1, there are integers s and t such that sa+tm=1. Hence, sa+tm ≡ 1 ( mod m), and it follows that sa ≡ 1 ( mod m). 用扩展欧几里得求出s即逆元。
  4. coefficient /koʊəˈfɪʃənt/ 系数
  5. Chinese Remainder Theorem: 对于模数两两互质的同余方程组（一条方程的形式为$x≡a_i (\mod m_i), m>1$）,在$模M=\prod\limits_{i=1}^n m_i系$中有且仅有唯一解。一个解的构造为$x = \sum\limits_{i=1}^n a_i M_i y_i$, 其中$M_i = M\div m_i, y_i*M_i≡1 (\mod m_i)$。如此构造后，对任意的i，都满足同余方程$x ≡ a_i M_i y_i ≡ a_i (\mod m_i)$。模系下的唯一性待证 练习30。
  6. Fermat’s Little Theorem： $有质数p，有整数a不是p的倍数，则a^{p-1}≡1(\mod p)$
  7. 利用费马小定理可以简化$a^q \mod p$的运算，其中q很大。可以将q替换为$(q \mod (p-1))$
  8. 满足$b^{n-1}≡1(\mod n)$的非质数n成为以b为基的伪质数 Pseudoprimes to the base b。（苏豆）
  9. 因为在一定范围内的对于某个基的pseudoprimes总是很少，所以可以进行质数近似判定测试。可惜，对于某些数n，对于所有基b满足gcd(b,n)=1，总是能通过伪素数测试，即$b^{n-1}≡1(\mod n)$，这些数称为Carmichael Numbers（卡麦抠 卡米切尔）。 Carmichael Numbers有无穷多个。
  10. 欧拉定理：费马小定理的推广。$有互质整数a,n.则a^{\phi(n)}≡1 (\mod n)$，而a在模n意义下存在逆元的充要条件就是a,n互质，从而得到推论：若a的逆元存在，则为$a^{\Phi(n)-1}$。
  11. Discrete Logarithms (模p意义下的)离散对数 对已知质数p，在模p意义下存在唯一一个primitive root $r$ 原始根，使得$r^n$取遍所有模p意义下所有非零数。 对任意$a\in [1,p-1]$，若有$r^e≡a(\mod p), e \in [1, p-1]$ ，则即$\log_r a=e$
  12. 求discrete logarithms $\log_r a$(模质数p意义下)没有找到多项式时间的算法。这个问题是密码学的一部分。