离散数学知识点

1、说明：定义：红色表示。定理性质：橙色表示 公式：蓝色表示。算法：绿色表示 页码：灰色表示数理逻辑：1 .命题公式：命题， 联结词（，），合式公式，子公式2 .公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3 .范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4 .联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5 .推理理论：重言蕴含式，有效结论，P规则，T规则，CP规则，推理6 .谓词与量词：谓词，个体词，论域，全称量词，存在量词7 .项与公式：项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8 .公式语义：解释，赋值，有效的，可满足

2、的，不可满足的9 .前束范式：前束范式10 .推理理论：逻辑蕴含式，有效结论，-规则（US）, +规则（UG）,-规则（ES）, +规则（EG）,推理集合论：1 .集合：集合，外延性原理，空集，全集，富集，文氏图，交，并，差，补，对称 差2 .关系：序偶，笛卡尔积，关系，domR, ranR,关系图，空关系，全域关系，恒等关系3 .关系性质与闭包：自反的，反自反的，对称的，反对称的，传递的，自反闭包r（R）,对称 闭包s（R）,传递闭包t（R）4 .等价关系：等价关系，等价类，商集，划分5 .偏序关系 偏序，哈斯图，全序（线序），极大元/极小元，最大元/最小元，上界/下界6 .函数：函数，常函

3、数，恒等函数，满射，入射双射，反函数，复合函数7 .集合基数：基数，等势，有限集/无限集，可数集，不可数集代数结构：1 .运算及其性质：运算，封闭的，可交换的，可结合的，可分配的，吸收律，塞等的，幺元, 零元，逆元2 .代数系统：代数系统，子代数，积代数，同态，同构。3 .群与子群：半群,子半群，元素的富，独异点，群，群的阶数，子群，平凡子群，陪集，拉格朗日（Lagrange）定理4 .阿贝尔群和循环群： 阿贝尔群（交换群），循环群，生成元5 .环与域：环，交换环，含幺环，整环，域6 .格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限 布尔代数的表示定理图论：1 .图的

4、基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、 补图，握手定理，图的同构2 .图的连通性：通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路（圈），点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图(二分图)3 .图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵4 .欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图5 .无向树与根树：无向树，生成树，最小生成树，Kruskal,根树，m叉树，最优二叉树，Huffman算法6 .平面图：平面图，面，欧拉公式， Kur

5、atoski定理数理逻辑：命题：具有确定真值的陈述句。否定词符号 ：设p是一个命题，p称为p的否定式。p是真的当且仅当 p是假的。p是真的当且仅当 p是假的。【定义1.1】合取词符号 ：设p, q是两个命题，命题 p并且q”称为p, q的合取，记以p q ,读作p且q。p q是真的当且仅当p和q都是真的。【定义1.2】析取词符号 ：设p, q是两个命题，命题 p或者q”称为p, q的析取，记以p q,读作p或q。p q是真的当且仅当p, q中至少有一个是真的。【定义1.3】蕴含词符号：设p, q是两个命题，命题"如果p ,则q”称为p蕴含q ,记以p q。pq是假的当且仅当p是真的而

6、q是假的。【定义1.4】等价词符号：设p, q是两个命题，命题p当且仅当q”称为p等价q ,记以p q。pq是真的当且仅当p, q或者都是真的，或者都是假的。【定义1.5】合式公式：(1)命题常元和变元符号是合式公式；(2)若A是合式公式，则(A)是合式公式，称为 A的否定式；(3)若A, B是合式公式，则 (A B), (A B), (A B), (A B)是合式公式；(4)所有合式公式都是有限次使用(1), (2), (3)、(4)得到的符号串。子公式：如果X是合式公式 A的一部分，且X本身也是一个合式公式，则称X为公式 A的子公式。【定义1.6】赋值(指派，解释)：设是命题变元集合，则称

7、函数 v:1 , 0是一个真值赋值。【定义1.8】真值表：公式A在其所有可能的赋值下所取真值的表，称为A的真值表。【定义1.9】重言式(永真式)：任意赋值v, v匚A矛盾式(永假式)：任意赋值v,有v七A【定义1.10】等值式：若等彳式A B是重言式，则称 A与B等值，记作 A Bo【定义2.1】 基本等值式双重否定律AA募等律A AA, AAA交换律A BB A, A B B A结合律(A B)C A (B C), (A B) C A (B C)分配律A (BC) (A B) (A C), A (B C) (A B) (A C)德摩根律(A B) A B , (A B) A B吸收律A (A

8、 B) A, A (A B) A零律A, A同一律A排中律A矛盾律A蕴涵等值式A等价等值式A假言易位AA, A AAAB ABB (A B) (B A)BBA等价否定等值式A B A B归谬论(A B) (A B) A置换规则： 设X是公式 A的子公式，XY。将A中的X (可以是全部或部分 X)用Y来置换,所得到的公式B,则A B文字 : 设 A (命题变元集), 则 A 和后者称为负文字。【定义2.2】A 都称为命题符号A 的文字，其中前者称为正文字，析取范式：形如Ai A2 An (n 1)的公式称为析取范式，其中A(i=1,n是由文字组成的合取范式。合取范式： 形为Ai A2 An (n

9、 1)的公式称为合取范式，其中 Ai,An都是由文字组成的析取式。 【定义2.3】极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【定义 2.4】主析取范式：给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。主合取范式：给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。【定义2.5】公式的真值表中真值为F 的指派所对应的极大项的合取，即为此公式的主合取范式。真值函数：称 F:0,1n0,1 为 n 元真值函数.【定义2.6】联结词的

10、完备集：设 C 是联结词的集合，若对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C 中的联结词，则称C 是联结词的完备集。【定义 2.7】，理 2.6 】， ， , ， ， ， 是联结词的完备集。【定异或 P Q ：(P Q)c条件否定P c Q：(P Q)与非 P Q：(P Q)或非P Q:(P Q)【定义2.8】 , J都是联结词的完备集【定理2.7】 重言蕴含式：当且仅当P Q是一个重言式时，称 P重言蕴含Q,记为P Qo 有效结论：设A、C是两个命题公式，若 A C,称C是A的有效结论。【定义3.1】推理定律 重言蕴涵式1. A (A B)附加律2. (A B) A化简律3

11、. (A B) A B假言推理4. (A B) B A拒取式5. (A6. (AB) B AB) (B C) (A C)7. (AB) (B8. (AB) (CC) (A C)D) (A C) (B D)(A B) ( A B) B9. (AB) (C D) ( B D)(A析取三段论假言三段论等价三段论构造性二难构造性二难( 特殊形式)C) 破坏性二难形式系统: 一个形式系统I 由下面四个部分组成：(1) 非空的字母表，记作A(I).(2) A(I) 中符号构造的合式公式集，记作E(I).(3) E(I) 中一些特殊的公式组成的公理集，记作AX(I).(4) 推理规则集，记作R(I).记 I

12、=< A(I),E(I),Ax(I),R(I)>,其中 <A(I),E(I)>是 I 的形式语言系统，<Ax(I),RI)> 是 I 的形式演算系统 .自然推理系统: 无公理 , 即 AX(I)=公理推理系统: 推出的结论是系统中的重言式, 称作定理【定义3.2】P 规则： 在推导过程中,可以随时添加前提。T规则：在推导过程中，可以引入公式 S,它是由其前题的一个或多个公式借助重言、蕴含而得到的。推理(证明)：从前提Ai,A2,Ak到结论B的推理是一个公式序列Ci,C2,C.其中G(1 il)是某个Aj, 或者可由序列中前面的公式应用推理规则得到, 并且Cl

13、 = B。 【定义3.3】CP规则(演绎定理)：若R|- S,则 |- R S,其中 为命题公式的集合。个体词：用于表示命题中主语部分的符号或符号串。个体常元表示确指个体。个体变元表示不确指个体。个体域: 个体变元的取值范围，常用D 表示。量词：限定个体数量特性的词。全称量词： 对所有的存在量词： 有些谓词语言：用符号串表示个体、谓词、量词和命题个体变元符号：x， y， z，个体常元符号：a， b， c，函数符号：f， g ，谓词符号：P, Q, R,命题常元符号：，量词符号：，连接词符号：, , ,辅助符号：), (【定义 4.1】项 : (1)个体常元和变元是项；(2)若f是n元函数符号，

14、t1,，tnl1项，则f(t1,，悔项;4.2】(3) 仅仅有限次使用(1)， (2)产生的符号串是项。原子公式：若P是一个元谓词符号，t1,tn是项，则P(t1,tn漫原子公式。【定义4.3】合式公式：(1) 原子公式是公式；(2)若A是合式公式，则(A)是合式公式；(3)若 A, B 是公式，则(A B), (A B), A B), (AB)是公式；(4) 若 A 是公式，x 是变元，则xA，xA 是公式；(5)仅仅有限次使用14得到的符号串才是合式公式。【定义4.4】设公式的一个子公式为x A或 x A。则称：指导变元：x 是 或 的指导变元。辖域： A 是相应量词的辖域。约束出现：辖域

15、中x的一切出现，以及(x)中的x称为x在 中的约束出现。自由出现：变元的非约束出现。约束变元：约束出现的变元。自由变元：自由出现的变元。【定义4.5】封闭的：一个公式A 是封闭的，若其中不含自由变元。【定义4.6】变元换名：( 1)换名的范围是量词的指导变元, 及其相应辖域中的变元，其余部分不变。( 2) 换名时最好选用辖域中未出现的变元名。变元代入：代入对自由变元进行。不能改变约束关系。解释： 谓词语言的一个解释I= (D,)包括：(1) 非空集合D ，称之为论域；(2) 对应于每一个个体常元a，(a) D ；(3) 对应于每一个n 元函数符号f 都有一个函数(f):DnD；(4) 对应于每

16、一个n 元谓词符号A 都有一个n 元关系 (A)Dn。 【定义 4.7】赋值：解释I中的赋值v为每一个个体变元x指定一个值v(x ) D,即设 V为所个体变元的集合，则赋值v 是函数 v:V D.可满足的：给定公式A,若在某一解释中至少有一种赋值使A取值为1,则称A为可满足的。否则称 A 是不可满足的。等值式 AB： 若 A B 是有效的【定义 5.1】几类等值式( 1)命题公式的推广e.g. P(x)Q(x) P(x) Q(x)( 2)否定深入x P(x)x( P(x)xP(x) x (P(x)( 3)量词作用域的扩张与收缩 设 B 中不含 x 的自由出现，则x(A(x)B)x A(x)Bx

17、(A(x)B)x A(x)Bx(A(x)B)x A(x)Bx(BA(x)Bx A(x)x(A(x)B)x A(x)Bx(A(x)B)x A(x)Bx(A(x)B)x A(x)Bx(B A(x)(4)量词分配等值式x(A(x) B(x) x(A(x) B(x)(5)多个量词的使用x y A(x,y)x y A(x,y)置换规则：设(A)是含A的公式，B x A(x)x A(x) x B(x)x A(x) x B(x)y x A(x,y)y x A(x,y)那么，若A B,则(A)(B)换名规则：设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体

18、变项符号，其余部分不变，设所得公式为A ,则A A.前束范式：如果谓词公式 A有如下形状：Q1x1QnxnM,其中Qix或者是 x,或者是xi, i=1 ,，n, M是不含量词的公式，Q*Q n*称为首标，M称为母式。【定义5.2】前束范式存在定理：对于任意谓词公式，都存在与它逻辑等价的前束范式。【定理5.1】前束范式的算法：步1.对约束出现的变元进行必要的换名，使得约束出现的变元互不相同且不与任何自由变元同名。步2.将所有的否定号深入到量词后面。步3.将量词符号移至公式最外层。逻辑蕴含式A C:当且仅当A C是有效的。几类逻辑蕴涵式第一组命题逻辑推理定理的代换实例如，xF(x) yG(y)

19、xF(x)第二组基本等值式生成的推理定理如， xF(x)xF(x),xF(x) xF(x)xF(x) x F(x), x F(x)xF(x)第三组其它常用推理定律xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x) xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)推理规则-规则(US):或l#(c) x,y个体变项，c个体常项x个体变项+规则(UG):-规则(ES):x个体变项，c个体常项K)x,y个体+规则(EG):或变项，c个体常项或先用ES,再用US自然推理系统N :L1 .字母表.同一阶语言L的字母表2 .合式公式.同L的合式

20、公式3 .推理规则：(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则(7)拒取式(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理规则(11)合取引入规则(12)-规则13 3)+规则(14)-规则15 5) +规则 【定义5.3】集合论:A B x ( x A x B )【定义6.1】A = BABBA【定义6.2】A BA B A B【定义6.3】A ? B x ( x A x B )空集：不含有任何元素的集合【定义6.4】空集是任何集合的子集。【定理6.1】募集P(A) = x | x A 【定义6.5】如果 |A|=n ,则

21、|P(A)|=2 n全集E:包含了所有元素的集合【定义6.6】并AB = x | x A x B交AB = x | xAxB差(相对补)A B = x | x A x B【定义6.7】 对称差A B = (A B) (B A)【定义6.8】 补(绝对补)A = E A = x|x A【定义6.9】 广义并 A = x | z ( z A x z)【定义6.10】 广义交 A = x |z ( z A x z )【定义6.11】集合恒等式1.只涉及一个运算的算律:交换A B=B AA B=B AA B=B A结合(A B) C=A (B C)(A B) C=A (B C)(A B) C=A (B

22、 C)募等A A=AA A=A2.涉及两个不同运算的算律:与与分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A (B C)=(A B) (A C)吸收A (A B)=AA (A B)=A3.涉及补运算的算律:D.M律A (B C)=(A B) (A C)A (B C)=(A B) (A C)(B C)= BC(B C)= BC双重否定A=A4.涉及全集和空集的算律:E补元律A A=A A=E零律A =A E=E同一律A =AA E=A否定=EE=序偶(有序对)：由两个元素 x和y,按照一定的顺序组成的二元组，记作 <x,y>.【定义7.1】笛卡儿积：设A,B为集合，A

23、与B的笛卡儿积记作 A B定义为A B = <x,y>| x A y B.【定义 7.2】 笛卡尔积性质：A=或B=时，A B= “ ”不满足结合律A (B C) = (A B) (A C)关系：(两个定义)(1) 序偶的一个集合, 确定了一个二元关系R。 R 中任一序偶<x,y>, 可记作<x, y> R 或xRy【定义7.3】(2) 笛卡尔积的子集：R A B 【定义 7.4】空关系 :全域关系：A XB恒等关系Ia = <x,x>| x S【定义7.5】关系矩阵：若A=x1, x2,xm, B=y1, y2,yn, R是从A到B的关系，R的

24、关系矩阵是布尔矩阵 MR = rij m n, 其中rij= 1< xi, yj> R.关系图：若A=xi,x2,xm,R是从A上的关系，R的关系图是Gr=<A,R>,其中A为结点集，R为边集.如果<x,x>属于关系R,在图中就有一条从x到xj的有向边.前域(定义域) dom(R) = x| y.<x,y> R值域 ran(R) =y| x.<x,y> R域 fld(R) = domR ranR【定义 7.6】逆关系 R 1 = <y, x> | <x, y> R 【定义7.7】互逆 ( R 1) 1 = R(

25、RS) 1 = R 1S 1(R S) 1 = R 1 S 1(A B) 1 = B A(R - S) 1 = R 1 - S 1复合关系R S = <x, z> | y (<x, y> R <y, z> S) 【定义7.8】(R S) P=R (S P) Rm = R R R设 R X Y,S Y Z, 则 (R S) 1 = S1 R 1 【定理 7.2 】R 在 A 上的 限制 R?A = <x,y> | xRy N0A在R下的像RA=ran(R?A)【定义7.9】自反的：若 xGA,者消<x,x> R,则称R是自反的反自反的：

26、若xGA,都有<x,x> R,则称R是反自反的.【定义7.11】对称的：对任意x,y A,满足，若<x,y> R,则<y,x> R反对称的：对任意x,y A,满足，若<x,y> R且<y,x> R,则x=y【定义7.12】传递的：对任意的x,y,z A,满足若<x,y> R且<y,z> R,则<x,z> R,则称R是传递的【定义7.13】 自反闭包(对称、传递)：设R是A上的二元关系，如果有另一个关系R满足：R'是自反(对称、传递)的 ； R' R; 对于任何自反的关系R”, 若 R

27、" R, 则有 R" R'.则称关系R'为R的自反闭包.记为r(R)(对称闭包 s(R)和传递闭包t(R)。【定义7.14】设 R 为 A 上的关系, 则有(1) r(R)=R U I a(2) s(R尸RU R(3) t(R)=R U R2U R3U (若 |A|=n,则 t(R)=R UR2U U Rn )等价关系：设 R 为集合 A 上的一个二元关系。若 R 是自反的, 对称的 , 传递的 , 则称 R 为 A上的等价关系【定义 7.15】等价类：设R为集合A上的等价关系，对a A,定义:aR= x|x A且<a,x> R称之为元素a关于

28、R 的等价类。【定义7.16】给定A上的等价关系 R,对于a,b A有<a,b>当且仅当aR=bR定理17.4】商集：设R是A上的等价关系，定义 A/R=a R|a A称之为A关于R的商集.【定义7.17】划分：设A为非空集合，若A的子集族 兀(兀P(A)满足：(1) 兀(2) x y(x,y ttAx刊 xry=)(3) Utt = A则称兀是A的一个划分，称兀中的元素为 A的划分块.【定义7.18】给定集合A 上的等价关系R, 则商集 A/R 是 A 的一个划分.集合A的一个划分Tt诱导出A上的一个等价关系R. R定义为R= <x,y>| x,y A且x,y在n的同

29、一分块中设R和R为非空集合 A上的一个等价关系，则R1 = R 2当且仅当A/R1 = A/R 2.偏序 ： 设 A 是一个集合. 如果 A 上的二元关系R 是自反的,反对称的和传递的, 则称 R 是 A 上. 记 R 为 “ ” ,且称序偶<A, > 为 偏序集 。 【定义7.19】 【定义 7.22】全序 (线序) ： 设 <A, > 为偏序集, 若对任 意的 x,y A 满足 : x y 或 y x 则称 为全序关系.<A, > 为全序集.【定义7.21 】覆盖：设<A, >为偏序集，若x,y A, x y,x y且没有其它元素z满足x z

30、,z y,则称y覆盖x.记covA= <x,y> |x,y A 且 y 覆盖 x【定义 7.23】 哈斯图：作图规则 用小元圈代表元素; 若x y且x y,则将彳表y的小元圈画在代表 x的小元圈之上；若<x,y> covA,则在x,y之间用直线连接。你极小元 /极大元：设 <A, >为偏序集, B A(1)对b B,若B中不存在x满足：b x且x b则称b为B的极小元.(2)对b B,若B中不存在x满足：b x且b x则称b为B的极大元.最小元/最大元：设<A, >为偏序集,B A,若有某个b B(1)对于B中每一个元素 x都有b x,则称b为B

31、的最小元.(2)对于B中每一个元素x都有x b,则称b为B的最大元.【定义7.24】下界 / 上界： 设 <A, >为偏序集, B A(1)若有a A,且又t x B满足a x,则称a为B的下界。进一步：设a为B的下界，若B的所有下界y均有y a,则称a为B的下确界，记为glb B。若有a A,且又t x B满足x a,则称a为B的上界。进一步：设a为B的上界，若B的所有上界y均有a y,则称a为B的上确界，记为lub B。【定义 7.25】函数：设X,丫为两个集合,f X Y,若又t x X, !(唯一的)y Y,满足：<x,y> f,则称f为函数记为：f:X Y 定

32、义域 : domf=X值域：ranf (有时记为f(X)=f(x)|x X【定义8.1】函数相等：设f和g者B是从A到B的函数，若对彳J意x A,有f(x)=g(x),则称f和g相等.记为f=g【定义8.2】函数的个数：设f:A B,|A|=m, |B|=n. 记B A=f|f: A B, 则 | B A |= n m满射 (到上映射)： 设 f: X Y, 若 ranf = Y, 则称 f 为满射的.入射(单射)(一对一映射)：设f: X Y,对xi, x2 X,满足:若xi x2,则f(xi)f(x2)，称f为入射的 .双射(对应映射)：设f：X Y,若f既是满射的，又是入射的.则称f是双

33、射的.【定义8.6】常函数：设f:AB,如果存在c GB使得对所有的x S都有f(x)=c,则称f:AfB是常函数.恒等函数：称A上的恒等关系Ia为A上的恒等函数，对所有的xS都有Ia(x)=x.单调递增：设<A, ?>, <B, ?>为偏序集，f:AfB,如果对任意的xi, *S, xi?x2,就有f(xi)? f(x2),则称 f 为单调递增的；严格单调递增：如果对任意的xi, x2S, xi?x2,就有f(xi) ?f(x2),则称f为严格单调递增的.类似的也可以定义单调递减和 严格单调递减的函数特征函数：设A为集合，对于任意的 A' A, A'的

34、特征函数a ' :Af0,i定义为A'(a)=i, a S'； A'(a)=0,aS A'自然映射：设R是A上的等价关系，令g:AfA/R； g(a)=a, aS称g是从 A到商集 A/R的自然映射【定义 8.7】复合函数： 设 f:X Y,g:Y Z,定义：f g = <x,z>|x X 且 z Z 且可找到 y 丫使 y=f(x),z=g(y)称 f g 为 f 与 g 的复合函数.设 f:A - B, g:B - C如果f:A-B,g:B-C是满射的，则fg:A-C也是满射的(2) 如果f:AfB,g:BfC是单射的，则fg:A f C

35、也是单射的如果f:AfB,g:BC是双射的，则fg:A f C也是双射的【定理8.2】反函数(逆函数)：设f:X 丫是一个双射函数，那么f-i是丫 X的双射函数.称f -i为f的反函数.互逆 (f -i ) -i=f设f:A-B是双射的，则f 1f = Ib,f f i = Ia【定理8.5】基数： 用来衡量集合大小的一个概念. 对于有限集合集来说, 集合的基数就是其中所含元素的个数.等势的：设A, B是集合，如果存在着从 A到B的双射函数，就称A和B是等势的，记作A-B.如果A不与B等势，则记作A?B. 注：通常将A的基数记为|A|.【定义8.8】N % Z 弋 Q 弋 NXN任何实数区间都

36、与实数集合R 等势0,1么 R康托定理(1) N ? R ；(2) 对任意集合A 都有 A? P(A). 【定义 8.7 】有限集(有穷集)/无限集(无穷集) ：设A为一个集合.若存在某个自然数n,使彳导A与集合0,1,n1等势，则称A是有限的.若集合A不是有限的，则称A是无限的.【定义8.11】： 实数集 R 的基数记作, 即 cardR = 【定义 8.12】可数集(可列集)：设A为集合，若card A< 0,则称A为可数集或可列集。【定义8.14】与自然数集N 等势的任意集合称为可数的. 其基数为0结论：(1) A为可数的当且仅当可排列成A=a1,a2,，a n,的形式.(2) 任

37、一无限集必含有可数子集.(3) 可数集的任何无限子集是可数的.(4) 可数个两两不相交的可数集合的并集, 仍是一个可数集.(5) N N 是可数集.(6) 有理数的全体组成的集合是可数集.(7) 全体实数构成的集合R是不可数的.基数的常识： 对于有穷集合A, 基数是其元素个数n， |A| = n; 没有最大的基数。将已知的基数按从小到大的顺序排列就得到：0, 1,2,，n,，0,，代数结构运算： 对于集合A， f 是从 An 到 A 的函数，称f 为集合 A 上的一个n 元运算。【定义 9.1 】交换律：已知<A , *> ,若x, y 6 A,有x*y=y*x ,称*在A上是可交

38、换的。【定义9.3】结合律：已知<A, *> ,若 x, y, z A,有x* (y*z) = (x*y) *z,称*在A上是可结合的。【定义9.4】募等律：已知A, *，若x A, x*x=x则称满足募等律。【定义9.5】分配律： 设 <A,*, >，若 x, y, z6A 有：x*(y Az)= (x*y) (x*z) ; (y z)*x=(y*x) (z*x) 称运算*对是可分配的。【定义9.6】吸收律：设，是定义在集合 A上的两个可交换二元运算，若又t x,y A,都有:x (x y) = x ； x (xy) = x 则称运算和 满足吸收律.【定义9.7】单位

39、元 (幺元): 设 *是 A 上二元运算，el, er ,e A左幺元：若 x A,有el*x=x ,称el为运算*的左幺元；右幺元：若 x A,有x*e=x,称a为运算*的右幺元；若 e 既是左幺元又是右幺元，称e 为运算 *的幺元 【定义 9.8】设*是A上的二元运算，具有左幺元 el ,右幺元er,则el=er=e定理9.1】零元：设*是A上二元运算，l, r,A左零元：若 x A,有l*x= l ,称l为运算*的左零元；右零元：若x A,有x* r= r,称r为运算*的右零元；若 既是左零元又是右零元，称为运算*的零元。【定义 9.9】设*是A上的二元运算，具有左零元l ,右零元r,则

40、l=r=【定理9.2】逆元：设*是A上的二元运算，e是运算*的幺元，若x*y=e那对于运算*, x是y的左逆元，y是 x 的右逆元 存在逆元(x o?T£ ?6 6 ? a£ ?心？?a? 3? a? 6 ?心?£-x 6? 6 ?心？£ ?6 ? 6 ?心？£?【定义9.10】对于可结合运算o,如果元素x有左逆元1 ,右逆元 r,则l=r=x 【定理9.4】消去律：已知<A, *>，若 x, y, z A,有(1) 若 x*y = x*z 且 x ,则 y=z ； (左消去律)(2) 若 y*x = z*x 且 x ,则 y=z；

41、 ( 右消去律)那么称*满足消去律。【定义 9.11 】代数系统：设 A 为非空集合，为 A 上运算的集合,称 <A, >为一个代数系统.【定义9.12】同类型的代数系统：如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同类型的代数系统.【定义 9.13】子代数：设V=<S, f1, f2,，f是代数系统，B是S的非空子集，如果B对f1, f2,，鄱是封闭的，且B和S含有相同的代数常数，则称<B, f1, f2,，fk>V的子代数系统，简称子代数【定义 9.14】最大的子代数：就是 V 本身最小的子代数：如果令V中所有代数常

42、数构成的集合是B,且B对V中所有的运算都是封闭的，则 B 就构成了V 的最小的子代数平凡的子代数:最大和最小的子代数称为V 的平凡的子代数真子代数：若 B 是 S 的真子集，则B 构成的子代数称为V 的真子代数.因子代数：设 V1=<A, ?>和 V2=<B, >是同类型的代数系统，?和为二元运算，在集合A B 上如下定义二元运算 ？，<a i,bi >,<a 2,b2> A B,有 <a i,bi>?<a2,b2>=<a i?a2, bi b2> 称 v=<a b,? >为Vi与V2的积代数，记作

43、 Vi V2.这时也称 Vi和V2为V的因子代数.【定义9.i5设Vi=<A,?>和V2=<B,>是同类型的代数系统，ViV2=<AB,?>是它们的积代数.(1) 如果 ? 和 运算是可交换(可结合、幂等)的，那幺?运算也是可交换(可结合、幂等)的(2) 如果ei 和e2(i 和2)分别为? 和 运算的单位元(零元)，那幺<ei, e2>(< i,2>)也是?运算的单位元(零元)(3) 如果 x 和 y 分别为?和运算的可逆元素，那幺<x,y >也是?运算的可逆元素，其逆元就是<x i, y i> 【定理 9.

44、5 】同态:设Vi=<A,°>和V2=<B,> 是同类型的代数系统，f:AB，对x,y A 有f(x°y) =f(x)f(y),则称 f 是 Vi 到 V2 的同态映射，简称同态(1) f 如果是单射，则称为单同态 。(2)如果是满射，则称为 满同态，这时称V2是Vi的同态像， 记作Vi V2(3)如果是双射，则称为 同构，也称代数系统 Vi同构于V2,记作Vi V2 如果Vi=V2,则称作 自同态。【定义9.i6半群： 设 V=<S, ° > 是代数系统，° 为二元运算，如果° 运算是可结合的，则称V 为半

45、群。独异点：设V=<S,。>是半群，若eS是关于。运算的单位元，则称 V是含幺半群，也叫做独异点。 有时也将独异点V 记作 V=<S, ° ,e>.群£破V=<G,。>是独异点，e G关于。运算的单位元，若 a G,a1 G,则称V是群（Group）.通常将群记作G. 【定义 10.1 】群的阶数：设 <G, >是一个群有限群：如果 G 是有限集，那么称<G, > 为有限群阶数：|G| 为该有限群的阶数；无限群：如果 G 是无限集，则称<G, > 为无限群。平凡群：阶数为 1 （即只含单位元）的群称为平

46、凡群【定义10.2】群的性质：设 <G, >是一个群。（ 1）非平凡群中不可能有零元.（ 2）对于a,b G, 必存在唯一的x G, 使得 a x =b.（ 3）对于a,b,c G 若 : a b = a c 或 b a = c a 则必有 b=c （ 消去律 ） 。（ 4）运算表中的每一行或每一列都是一个置换。（ 5）除幺元e 外 , 不可能有任何别的幂等元。e n0元素的募£0设G是群，a6G, n8,则a的n次募an an 1an 0【定（a 1）mn 0, n m义 10.3】元素的阶：设G是群，a 0,使得等式ak=e 成立的最小正整数k 称为元素a 的阶，记作

47、|a|= k，称a为k阶元。若不存在这样的正整数k,则称a为无限阶元。【定义10.4】11帚运算性质：（1） as G （a ） =a（2） a, b 6 G （ab） 1=b 1a 1（3） a£ G anam = an+m, n, m£ Z（4） a 6 G （an） m = anm, n, rn Z（5）若G为交换群，则（ab）n = anbn.【定理10.1 1元素的阶的性质：G为群，a6G且| a尸 r.设k是整数，则（1） ak = e 当且仅当r | k （r 整除 k）（2 ）| a 1| = | a| 【定理 10.3 】子群： 设 G 是群， H 是 G

48、 的非空子集，如果 H 关于 G 中的运算构成群，则称H 是 G 的子群 ,记作H<Go真子群：若H是G的子群，且 H G,则称H是G的真子群，记作 H<G.平凡子群：对任彳5群G都存在子群.G和e都是G的子群，称为 G的平凡子群.【定义10.5】子群判定定理 6?£G为群，H是G的非空子集，则 H是G的子群当且仅当 a,b6H 有 ab6H;1 a6H 有 a 6H。Le理 10.4】子群判定定理二：设G为群，H是G的非空子集.H是G的子群当且仅当a, b H有ab 16 H.【定理 10.5 】子群判定定理三：设G为群，H是G的非空有穷子集，则 H是G的子群当且仅当a

49、, b6 H有ab H 【定理10.6】 生成子群：设G为群，a6G,令H=ak| k8,则H是G的子群，称为由 a生成的子群，记作<a>.o 设 <H, >是群 <G, >的一个子群,a G 则 :左陪集£oaH := aH ,由a所确定的H在G中的左陪集右陪集 £oHa:=Ha陪集是左陪集与右陪集的统称. 【定义 10.6】陪集性质：设H是群G的子群，则 He = H a G 有 a£Ha a,b£G有：a£Hb ab16 HHa=Hb 在G上定义二元关系 Ra, b G < a, b> R

50、ab 16 H则R是G上的等价关系，且 a R = Ha. |Ha|=|H|【定理 10.7 】 【定理 10.8 】拉格朗日定理：设G是有限群，H是G的子群，则|G尸|H| G:H其中G:H是H在G中的不同右陪集(或左陪集) 数，称为H 在 G 中的指数. 【定理 10.10 】推论：(1)设G是n阶群，则aG I a|是n的因子，且an = e.（2） 对阶为素数的群 G,必存在a G使得G = <a>.阿贝尔群(交换群)： 若群 G 中的运算是可交换的，则称G 为交换群或阿贝尔群。循环群：设G是群，若存在a£G使得G=ak| kZ则称G是循环群，记作G=<a&

51、gt;,称a为G的生成元 .n阶循环群：设G=< a>是循环群，若 a是n阶元，则 G = a0=e, a1, a2,，an 1无限循环群：若a是无限阶元，则 G = a0=e, a"，a'2,【定义10.71循环群的生成元：设G=<a>是循环群(1)若G是无限循环群，则 G只有两个生成元，即a和a1.若G是n阶循环群，则 G含有(n)个生成元.对于任何小于n且与n互质的数60,1,，n-1,ar是G的生成元.【定理10.11循环群的子群： 设G=<a>是循环群，则 G的子群仍是循环群；(2)若G=<a>是无限循环群，则 G的子

52、群除e以外都是无限循环群；(3)若G=<a>是n阶循环群，则对 n的每个正因子d, G恰好含有一个d阶子群。【定理10.12环：设<R,+, 是代数系统，+和是二元运算.如果满足以下条件：(1) <R,+> 构成交换群；<R, 构成半群；(3)运算关于+运算适合分配律，则称<R,+, 是一个环.【定义10.11 环的运算性质： 设R+, 是环，则(1) a£ R, a0 = 0 a = 0(2) a,b R, (a) b= a( b) = ab(3) a,b, c R,a(bc) = ab ac, (b c)a = ba ca、/au si

53、晒ai, a2,，an, bi, b2,bmC R(n,m 2)1/11 加1【定理 10.14】设R,+, ,是环交换环：若环中乘法 适合交换律，则称 R是交换环;含幺环：若环中乘法 存在单位元，则称 R是含幺环;无零因子环： 若 a,b6R ab=0a=0 W=0 ,则称R是无零因子环。整环：设R,+, ?是一个代数系统，若满足：R,+是阿贝尔群;R,?是可交换独异点，且无零因子，即对 a,b R, a 0,b 0则a? b 0；(3)运算？又t+是可分配的，则称R,+, ?是整环域：设R,+, ?是一个代数系统，若满足：R,+是阿贝尔群;(2) R-0, ?是阿贝尔群;(3)运算？又t+

54、是可分配的，则称R,+, ?是域。【定义10.12格：设S, ?是偏序集，如果 xv S, x,y都有最小上界和最大下界，则称S关于偏序？作成一个格【定义11.1】格的代数系统定义：设S ?, ? 是代数系统，？和？是二元运算，如果？和？满足交换律、结合律和 吸收律，则S, ?,?构成格【定义11.3】对偶命题：设f是含有格中元素以及符号=,? ,? ,V和A的命题.令f*是将f中的？替换成？,？替换成？，潜换成A ,A替换成V所得到的命题.称f*为f的对偶命题 【定义11.2】格的对偶原理：设f是含有格中元素以及符号=,?,?, V和A等的命题.若f对一切格为真，则f的对偶命题f*也对一切格为真.格的性质：设L, ?是格，则运算V和A适合交换律、结合律、募等律和吸收律，即(1) a,b6L 有 aVb = b V a, a Ab = b A a(2) a,b,c 6 L 有(a V b) V c = a V (b V c), (aA b) A c = a A (b A c)(3) a6L 有 aVa = a, a A a = a(4) a,b 6 L 有 a V (a A b) = a, a A (a V