下载文档原格式
《离散数学》期末复习大纲一、数理逻辑[复习知识点]1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论6、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出现）7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足）8、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩、量词分配）和置换规则（置换规则、换名规则）9、一阶逻辑前束范式（定义、求法）本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与解释、求前束范式。
[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。
2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。
3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。
4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。
5、掌握命题逻辑的推理理论。
6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；掌握命题的符号化。
7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。
8、掌握求一阶逻辑前束范式的方法。
二、集合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）3、集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。
10.语言和有限自动机Language and Finite－State Machine §10.1 语言Languages由符号以一定规则组成单词word，由单词以一定规则（语法）组成句子sentences。
以一定规则给句子的含义作出解释叫语义。
Grammars文法G＝（V，S，v0，→）短语结构文法phrase structure grammarV是有限符号集，S⊆V，S终止符号集v0∈V－S，初始符号，→是V*上的有限产生关系product relation。
w，w’∈V*, w→w’是产生规则，w叫左边，w’叫右边。
N＝V－S，非终止符号集。
例1. S={John,Jill,drives,jogs,carelessly,rapidly,frequently}N={sentence, noun, verbphrase,verb,adverb}V=N∪S，v0＝sentence.sentence→noun verbphrasenoun→Johnnoun→Jillverbphrase→verb adverbverb→drivesverb→jogsadverb→carelesslyadverb→rapidlyadverb→frequentlysentencenoun verbphraseJill verbphraseJill verb adverbJill drives adverbJill drives frequently例2．正则文法，3型文法。
G=(V,S,v0,→),V＝{v0,w,a,b,c},S={a,b,c},1．v0→aw. 2. w→bbw. 3. w→c.G能接受的语句是v0→aw→ab2w→……→ab2n w→ab2n c.简记为v0 ab2n cG确定的语言L(G)={ ab2n c|n∈N}＝a(bb)*c.例3．0型文法。
G=(V,S,v0,→),V＝{v0,w,a,b,c},S={a,b,c},1. v0→av0b.2. v0b→bw.3. abw→c.v0→av0b→aav0bb→a n v0b n→a n bwb n－1＝a n－1abwb n－1→a n－1cb n－1简记为v0 a n－1cb n－1G能接受的语句是a n cb n，n≥0.L(G)={ a n cb n | n≥0}形式文法的分类0型文法type 0：规则无限制.无限制文法。
离散数学是数学中的一个重要分支，与连续数学相对应。
离散数学的研究对象是不连续的离散结构，如集合、图论、布尔代数等。
在离散数学中，有限域和编码理论是两个重要的概念。
有限域是一种特殊的代数结构，也称为Galois域，以法国数学家Évariste Galois命名。
有限域的定义是一个包含有限个元素的域，其中包含加法和乘法运算。
有限域的特点是，其元素的数目必须是一个素数的幂。
有限域由Galois域理论构建而成，Galois域理论是代数学中的一个重要分支，主要研究方程的根与域之间的关系。
有限域在编码理论中有着广泛的应用。
编码理论是研究如何在信息传输过程中进行编码和解码的学科。
在信息传输中，为了保证信息的完整性和可靠性，常常需要对信息进行编码加密，以防止信息的丢失和损坏。
而有限域可以提供一种有效的编码方式，提高信息的传输效率。
在编码理论中，有限域的一项重要应用是RS编码（Reed-Solomon codes），也称为纠删码。
RS编码是一种具有纠错能力的编码方式，它可以对传输过程中可能发生的错误进行检测和纠正。
RS编码的原理是利用有限域上的多项式运算，将信息数据进行编码，然后通过添加额外的校验码进行冗余和纠错。
在接收端，通过对接收到的编码数据进行解码和纠错，可以恢复原始的信息数据。
RS编码在计算机存储和通信领域有着广泛的应用。
在存储领域，如硬盘、闪存等存储介质，为了保证数据的安全和可靠，常常使用RS编码进行冗余校验。
在通信领域，如无线通信、光通信等，RS编码可以用于提高数据传输的可靠性和抗干扰能力。
除了RS编码，有限域还有其他的编码应用。
在无线传感器网络和分布式存储系统中，矩阵编码和置换编码等也是常用的编码方式。
而这些编码方式都离不开有限域的数学理论基础。
总结起来，离散数学中的有限域和编码理论是两个密不可分的概念。
有限域作为一个代数结构，提供了一种有效的编码方式，可以用于提高信息传输的可靠性和抗干扰能力。
11.群和编码Group and coding§11.1 二进编码和查错coding of binary information and error detection Alphabet 字母集。
B ＝{0,1}.message 从有限alphabet 中选取有限多个符号组成的一个序列。
word m 个0和1组成的一个序列。
B ＝B ×B ×……×B （m 个）。
B m 的加法⊕：(x 1,x 2,…,x m )⊕(y 1,y 2,…,y m )=(x 1+y 1 ,x 2+y 2,…,x m +y m )B m 中共有2m 个元素, B m 的阶是2m 。
0＝(0,0,……,0).由于disterbance （noise ）x ≠x t 。
用编码方法查错、纠错。
取n>m ，一一对应e ：B m →B n ，称e是（m,n）编码函数。
b∈B m，e(b)∈B n叫做b的码词Code worde(b)比b多几位0，1用来查错和纠错。
将要发出的word b编码得到x=e(b),发送后接收到x t，如果没有干扰，x＝x t，b＝e-1(x t). 如果有干扰，x和x t有≤k位出错，即有1位到k位错误。
x的权（weight）：x含有1的个数，记做|x|.奇偶校验码parity check code：如果b＝b1b2…b m，令e(b)＝b1b2…b m b m+1,b m+1=0, if |b|是偶数，b m+1=1, if |b|是奇数。
b m+1=0, 当且仅当b含有偶数个1。
m＝3e(000)=0000e(001)=0011e(010)=0101e(011)=0110e(100)=1001e(101)=1010e(110)=1100e(111)=1111对任意b，e(b)的权总是偶数。
设b=111，x＝e(b)=1111.如果接收到有一位错x t＝1101，x t的权是奇数，发现有错。
x t的权是偶数，无法判断有错。
例3．（m，3m）编码函数：e：B m→B3m，b＝b1b2…b m，e(b)＝b1b2…b m b1b2…b m b1b2…b m.e(000)=000000000e(001)=001001001e(010)=010010010e(011)=011011011e(100)=100100100e(101)=101101101e(110)=110110110e(111)=111111111可以发现一位或两位错误。
海明距离δ(x,y)：Hamming distance设x，y∈B m，δ(x,y) =|x⊕y|δ(x,y)等于x，y中对应不相等的位置的个数。
例4．求海明距离x=110110, y=000101x=001100, y=010110解. （a）δ(x,y)=4.(b) δ(x,y)=3.定理1. 设x,y,z∈Bm，则δ(x,y) =δ(y,x).δ(x,y)≥0.δ(x,y)=0 iff x=y.δ(x,y)≤δ(x,z)＋δ(z,y)证明.(d) |a⊕b|≤|a|+|b|.δ(x,y)=|x⊕0⊕y |=|x⊕z⊕z⊕y|≤|x⊕z|+|z⊕y|=δ(x,y)+δ(x,y)一个编码函数e：B m→B n的最小距离minimun distance：min{δ(e(x),e(y)) | x,y∈B m}.例5．e(00)=00000e(01)=01110e(10)=00111e(11)=11111min{δ(e(x),e(y))}=2.定理2. 一个（m，n）编码e：B m→B n能查出至多k位错误当且仅当最小海明距离≥k＋1。
证明. 设最小海明距离≥k＋1。
发出x＝e(b), 收到x t，x≠x t，δ(x, x t)≤k，则x t不是一个编码，查出错误。
反之. 设最小海明距离＝r≤k。
δ(x, x t)＝r，x t可能是另一个编码无法判断错误。
例6.e(000)=000000000e(001)=001001001e(010)=010010010e(011)=011011011e(100)=100100100e(101)=101101101e(110)=110110110e(111)=111111111能查几位错？群编码Group codes一个编码函数e：B m→B n叫做群编码，如果Ran(e)=e(B m)={e(b) | b∈B m }是B n的一个子群。
例7.（1）e(000)=000000000e(001)=001001001e(010)=010010010e(011)=011011011e(100)=100100100e(101)=101101101e(110)=110110110e(111)=111111111是群编码。
(2)e(000)=000000e(001)=001100e(010)=010011e(011)=011111e(100)=100101e(101)=101001e(110)=110110e(111)=111010也是群编码。
定理3. 设e ：B m →B n 是一个群编码，则e 的最小海明距离等于非零元的最小权。
证明. 设δ是e 的最小海明距离，η是非零元的最小权。
δ＝δ(x,y), η＝|z|.δ(x,y) =|x ⊕y|≥η。
η＝|z|＝|z ⊕0|＝δ(z,0)≥δ。
因此δ＝η。
例8. 例7（1）δ＝3.（2）δ＝2.例9. 布尔矩阵的加法和乘法：101111010110011011011011100101111110⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⊕=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦1011001110111001⎡⎤⎡⎤⎡⎤⎢⎥*⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎢⎥⎣⎦＝定理4.布尔矩阵的乘法对加法满足分配律：设D ，E 是m ×p 布尔矩阵，F 是p ×n 布尔矩阵，则(D ⊕E)*F=(D*F)⊕(E*F).定理5. 设非负整数m<n, r=m-n, H 是n ×r 布尔矩阵。
f H ：B n →B r , f H (x)=x*H. 则f H 是群B n 到B r 内的同态映射。
证明. 任意x ，y ∈B n, f H (x ⊕y)＝(x ⊕y)*H =(x*H)⊕(y*H)= f H (x)⊕ f H (y).推论1. N={x ∈B n | x*H=0}是B n 的正规子群。
令m<n, r=m-n, H 是n ×r 布尔矩阵111212122212H 100010001r r m m mr h h h h h h h h h ⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦L L M M M L L L M M M L ＝r ＝n －m 行 令e H ：B m → B ne H (b 1b 2…b m )＝b 1b 2…b m x 1x 2…x r ，x 1＝b 1h 11+b 2h 21+…+b m h m1，x 2＝b 1h 12+b 2h 22+…+b m h m2，x r ＝b 1h 1r +b 2h 2r +…+b m h mr ，定理6. 令x ＝y 1y 2…y m x 1…x r ，则x*H=0当且仅当存在b ∈B m ,x=e H (b).证明. ⇒ 设x*H=0y 1h 11+y 2h 21+…+y m h m1+x 1=0y 1h 12+y 2h 22+…+y m h m2+x 2=0y 1h 1r +y 2h 2r +…+y m h mr +x r =0两边同加x i ，y 1h 11+y 2h 21+…+y m h m1+x 1+x 1 =0+x 1y 1h 11+y 2h 21+…+y m h m1 =x 1y 1h 12+y 2h 22+…+y m h m2=x 2y 1h 1r +y 2h 2r +…+y m h mr =x rx= e H (y).设存在b ∈B m , x=e H (b).x 1＝b 1h 11+b 2h 21+…+b m h m1，x 2＝b 1h 12+b 2h 22+…+b m h m2，x r ＝b 1h 1r +b 2h 2r +…+b m h mr ，b 1h 11+b 2h 21+…+b m h m1＋x 1＝0b 1h 12+b 2h 22+…+b m h m2＋x 2＝0，b 1h 1r +b 2h 2r +…+b m h mr ＋x r ＝0即x*H=0.推论2. e H (B m )={ e H (b) | b ∈B m }是B n 的子群。
e H 是群编码。
证明. e H (B m )=ker(f H ).例11．m ＝2，n ＝5， 给出群编码e H ：B 2→B 5,110011100010001H ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦解. e H (00)=00 x 1x 2x 3,x 1= x 2= x 3=0, e H (00)=00000.e H (01)=01x 1x 2x 3,x 1=0, x 2=1, x 1=1,e H (01)=01011e H (10)=10110,e H (11)=11101.δ＝3. 可查2位。
§11.2解码和纠错Decoding and error correction例1设奇偶编码e：B m→B m+1,令d：B m+1→B m是解码函数，任意y＝y1y2…y m y m+1,d(y)= y1y2…y m .d(e(b)=b.d◦e=1Bm.d可以解码，不能纠错。
设编码e：B m→B n,令d：B n→B m是e的解码函数，如果传送x＝e(b),接收x t，至多k位错，d(x t)=b,就称d为e的k位纠错解码，也称（e，d）k位纠错。
例2（m, 3m）编码，定义解码函数d：B3m→B m，对y＝y1y2…y m y m+1…y2m y2m＋1…y3m,d(y)= z1z2…z m,z i =1 if{z i,z i+m,z i+2m}含有至少2个1.z i =0 if{z i,z i+m,z i+2m}含有少于2个1.d是1位纠错解码最大似然解码函数maximum likelihood decoding function设编码e：B m→B n,令d：B n→B m是e的解码函数，列出B m中所有2m个元素：x(1), x(2), ……，m2x（）,如果接收的是x t，找出第一个x(s),使δ(x(s), x t)=min1≤i≤2m{δ(x(i), x t)}.取d(x t)=e-1(x(s))=b.称d为e的最大似然解码函数。
d与列出B m中2m个元素的次序有关。
