问求4笔记

格与布尔代数

格：满足偏序关系的集合，满足三个公理：
[L1] Commutative law:
(1a) a ∧ b = b ∧ a (1b) a ∨ b = b ∨ a
[L2] Associative law:
(2a) (a ∧ b) ∧ c = a ∧ (b ∧ c) (2b) (a ∨ b) ∨ c = a ∨ (b ∨ c)
[L3] Absorption law:
(3a) a ∧ (a ∨ b) = a (3b) a ∨ (a ∧ b) = a

子格：满足格的定义并且在原格的运算下封闭

格同构：存在一个one to one的映射f，f (a ∧ b) = f (a) ∧ f (b) and f (a ∨ b) = f (a) ∨ f (b)

有界格：A lattice L is said to have a lower bound 0 if for any element x in L we have 0 《= x. Analogously, L is said to have an upper bound I if for any x in L we have x 《= I .

DISTRIBUTIVE LATTICES分布格： Distributive law:
(4a) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) (4b) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Join Irreducible Elements：
a = x ∨ y implies a = x or a = y.

Atoms：Those elements which immediately succeed 0, called atoms, are join irreducible.

补：Let L be a bounded lattice with lower bound 0 and upper bound I . Let a be an element of L. An element x in L is called a complement of a if a ∨ x = I and a ∧ x = 0

Theorem 14.9: Let L be a bounded distributive lattice. Then complements are unique if they exist.

互补格Complemented Lattices：
AlatticeLis said to be complemented if L is bounded and every element in L has a complement.

Theorem 14.10: Let L be a complemented lattice with unique complements. Then the join irreducible elements of L, other than 0, are its atoms.

Theorem 14.11: Let L be a finite complemented distributive lattice. Then every element a in L is the join of a unique set of atoms.

Boolean algebra
Let B be a nonempty set with two binary operations + and ∗, a unary operation’, and two distinct elements 0 and 1. Then B is called a Boolean algebra if the following axioms hold where a, b, c are any elements in B:
[B1] Commutative laws:
(1a) a + b = b + a (1b) a ∗ b = b ∗ a
[B2] Distributive laws:
(2a) a + (b ∗ c) = (a + b) ∗ (a + c) (2b) a ∗ (b + c) = (a ∗ b) + (a ∗ c)
[B3] Identity laws:
(3a) a + 0 = a (3b) a ∗ 1 = a
[B4] Complement laws:
(4a) a + a’ = 1 (4b) a ∗ a’ = 0

同构布尔代数：
Two Boolean algebras B and B’ are said to be isomorphic if there is a one-to-one correspondence f: B → B’
which preserves the three operations, i.e., such that, for any elements, a, b in B,
f (a + b) = f (a) + f (b), f (a ∗ b) = f (a) ∗ f (b) and f (a’ ) = f (a)’

some Theorem
(i) Idempotent laws:
(5a) a + a = a (5b) a ∗ a = a
(ii) Boundedness laws:
(6a) a + 1 = 1 (6b) a ∗ 0 = 0
(iii) Absorption laws:
(7a) a + (a ∗ b) = a (7b) a ∗ (a + b) = a
(iv) Associative laws:
(8a) (a + b) + c = a + (b + c) (8b) (a ∗ b) ∗ c = a ∗ (b ∗ c)

(i) (Uniqueness of Complement) If a + x = 1 and a ∗ x = 0, then x = a’.
(ii) (Involution law) (a’ )’ = a.
(iii) (9a) 0’ = 1. (9b) 1’ = 0.
(10a) (a + b)’ = a’ ∗ b’ . (10b) (a ∗ b)’ = a’ + b’.

代替定义：
A Boolean algebra B is a bounded, distributive and complemented lattice.

表示公理：
Theorem 15.6: The above mapping f: B → P (A) is an isomorphism.
Corollary 15.7: A finite Boolean algebra has 2n elements for some positive integer n.

A Boolean expression E is called a sum-of-products expression if E is a fundamental product or the sum of two or more fundamental products none of which is contained in another.

积之和表达式

质数表示

Consensus of Fundamental Products
Suppose Q is the consensus of P1 and P2. Then P1 + P2 + Q = P1 + P2.//把互补的变量同时从两个布尔表达式中去掉，剩下非互补的相乘

通过Consensus方法把积之和表达式化简为质数表示

把质数表示化简为最简表示

真值表书写

相邻变量：所有变量均相同，只有一个变量取反

数论初步：

第一数学归纳法

第二数学归纳法&良序

最大公约数

欧几里得算法求最大公约数

乘法逆
Suppose there is a b in Zn such that the equation
a * x = b
does not have a solution. Then a does not have a multiplicative inverse
in Zn.

Given a and n, if there exist integers x and y such that ax + ny = 1, then
gcd(a, n) = 1—that is, a and n are relatively prime.
a n互质，gcd(a,n)=1,x是a模n意义下的乘法逆，乘法逆唯一

Two positive integers j and k have greatest common divisor 1 (and thus are relatively prime) if and only if there are integers x and y such that jx + ky = 1.

For any positive integer n, an element a of Zn has a multiplicative inverse if and only if gcd(a, n) = 1.

For any prime p, every nonzero element a of Zp has an inverse.

数论算法

TC 31.1

如果任意整数a和b 不都为0, 则 gcd(a, b)是a 与 b 的线性组合集{ax+by: x, y∈Z} 中的最小正元素。

欧几里得算法：对任意非负整数a和任意正整数b,gcd(a,b) = gcd(b,a mod b)

如果a>b>=l 并且EUCLID(a, b)执行了 k>=l 次递归调用，则a>=Fk+2,b>=Fk+1

(Lame定理) 对任意整数k>=l, 如果a>b>=l, 且b< Fk+1 则 EUCLID(a, b)的递归调用次数少于K次。

欧几里得算法的扩展形式

(拉格朗日定理） 如果(S, ))是一个有限群， (S’,)是(S, *)的一个子群，
则|s’| 是|s| 的一个约数。

如果 s’是有限群 S 的真子群，则 |S’|<= |S| /2。

求解模线性方程

对任意正整数 n, 如果 d=gcd(a, n), 则在 Zn 中，
< a >= < d >= { 0, d, 2d, .. ·, ((n/ d) —l)d}.因此，|< a >|= n/d

当且仅当 d|b 时，方程 ax=b(modn) 对于未知量x有解，这里 d=gcd(a, n)

方程ax=b(modn) 或者对模n有d个不同的解，或者无解，这里 d=gcd(a, n)

序列 ai mod n是周期性的，其周期为 |< a >| =n/d

令d=gcd(a, n), 假设对某些整数 x’ y’有 d=ax’+ny’。如果 d|b, 则方程 ax=b(modn) 有一个解的值为 X0 这里x0= x’(b/d) mod n

假设方程 ax=b(mod n) 有解（即 d|b, 这里 d= gcd(a, n), X0 是该方程的任意一个解。因此，该方程对模n恰有d个不同的解，分别为 x=x0+i(n/d)

对任意 n>1, 如果 gcd(a, n)=l, 则方程 ax=b(modn) 对模n有唯一解。如果 b=1, 则要求的x是a对模n的乘法逆元，这是一种常见的重要有趣情形。

如果p是一个奇素数且 e>=l, 则方程x^2=l(mod p^e)仅有两个解，即 x=l x=-1
如果对模n存在1的非平凡平方根，则n是合数。

密码学

凯撒密码：简单的密码移位
仿射密码：f(p)=ap+b mod 26,gcd(a,26)=1
多字母密码系统：
RSA加密系统：
利用大数分解的复杂性，找两个大质数p，q，n=pq，m=(p-1)(q-1),找到一个e，使得gcd(e,m)=1,我们可以找到D,$De=1(mod \phi n)$,n和e是公开的
发送人将$x^e$发送过去，接收者用$y^D$来解密(mod n).
M= SA(PA(M))
M= PA(SA(M))
发送者可以查看接收者的公钥，将信息M通过公钥进行加密，而接收者可以使用自己的私钥来解密被加密的消息
接收者想要回复信息，但不希望被伪造，因此可以在信息后面加上自己的签名，通过私钥对签名进行加密，发给发送者
发送者通过查看接受者的公钥，对消息进行解密，若签名能够通过核验，则非伪造（公开的，任何知道公钥的人均可解密）
若想要回复的信息是私密的，那么只需要对信息和签名分开加密，用对方的公钥对信息加密，用自己的私钥对签名进行加密。

编码学

奇偶校验位-只能检验单个错误，无纠错能力
最大似然解码
块代码
把m位二进制数编码成n位二进制数
哈密顿距离：所有位数值不同的个数之和
权：n位中数值为1的个数

Let C be a code with dmin = 2n + 1. Then C can correct any n or fewer errors. Furthermore, any 2n or fewer errors can be detected in C.

A group code is acode that is also a subgroup of [Z_{2}^{n}]

Let x and y be binary n-tuples. Then w(x + y) = d(x, y).

Let dmin be the minimum distance for a group code C. Then dmin is the minimum of all the nonzero weights of the nonzero codewords in C. That is, dmin = min{w(x) : x != 0}.

Linear Codes

Define the null space of a matrix H ∈ Mm×n(Z2) to be the set of all binary n-tuples x such that Hx = 0. We denote the null space of a matrix H by Null(H).

Let H be in [Mm×n(Z_2)]. Then the null space of H is a group code.

A code is a linear code if it is determined by the null space of some matrix[H ∈Mm×n(Z_2)] .

Parity-Check and Generator Matrices奇偶校验和发生器矩阵

一个m行n列的矩阵，如果最后m列是一个单位矩阵，那么这个矩阵是一个典型的奇偶校验矩阵

Let C be the code generated by G. Then y is in C if and only if Hy = 0. In particular, C is a linear code with canonical parity-check matrix H.

Let H be an m × n binary matrix. Then the null space of H is a single error-detecting code if and only if no column of H consists entirely of zeros.

Let H be a binary matrix. The null space of H is a single error-correcting code if and only if H does not contain any zero columns and no two columns of H are identical.

Let the m × n binary matrix H determine a linear code and let x be the received n-tuple. Write x as x = c + e, where c is the transmitted codeword and e is the transmission error. Then the syndrome Hx of the received codeword x is also the syndrome of the error e.