离散数学复习 1

1、复习,廖波,一、命题 可以确定其值的陈述语句。非陈述、悖论不可 二、联结词：能给出真值表 否定、合取、析取、条件、双条件 的等价式、异或、不可兼或、可兼或 三、合式公式的定义 (1)命题变元、常量是合法 (2)若A是合式公式，则 A合式 (3)若A、B合则AB、AB、AB、AB合式 (4)有限次使用(2)(3)得到的式子都是合法的。 学会判断一个公式是否合法。,四、真值表 先确定公式中命题变元即自由变元清单 可以分步给出每部分的公式的真值 也可以直接将各部分的值写在运算符的下方 证明两个公式等值、求主析取范式、主合取范式、设计电路、重言式或永真式、矛盾式或永假式、可满足式 五、习题一 命题符号

2、化第6题、14题、16、17、18、19、20、21、22、23、,六、等值式 1、定义：对于命题变元的每组值真值完全相同 2、pq(1个)、 pq(3个) 3、分配律(正用/逆用)、德摩、原=逆否 4、双否、幂等、交换、结合、A0 、A1、 A0、A1、AA、 AA 5、局部等值变换后，整体仍等值。 例题某次研讨会及习题，写出表达式再等值变换 七、主析取范式与主合取范式 1、先给出真值表 2、公式=主析取=小项的析取=大项的合取 3、小项对应真值表中取值为1之行 mo1=pq 大项0之行 M01= pq 4、先给出真值表再给出公式，设计题,八、析取范式与合取范式 1、定义：主范式是每一项中每

3、个变元均出现，范式则不一定。 九、习题二 1、掌握用真值表证明公式等值 2、学会用真值表求主析取、主合取范式 3、掌握设计题第27题 4、某科研所派人出国、29、30题 变元不多时，可给出真值表主析取式范式 并且将明显不成立的取值组去掉 变元多时先等值变换再求析取范式 也可用归结法Robinson方法“对对碰”。,十、推理的定义 1、定义：若A1，A2，为真时公式B为真，则称A1, A2, , An可推出B，记为A1,A2,B。 2、证明方法： (1)真值表法：A1A2AnB为永真。 (2)利用范式：将转换为，将进行到底，顺、逆用分配律，得到公式的范式，判断是否为永真。 (3)自然推理：从A1

4、,A2,An 为真出发，推理判断B是否为1。 (4)附加条件法： A1A2An (CD)等价于A1A2An C D (5)反证法或归谬法 假设A1,A2,为1时， B不为1即为0，也即B为1，则可以推出矛盾的结论。,3、常用的等值式 pq(pq) q p pq pq 逆用 pq (pq)(qp) (pq) (p q) (pq) (pq) 主析取范式 (pq) pq 顺、逆用 (pq) pq 顺、逆用 p(qr) (pq) (p r) 顺、逆用 p(qr) (pq)(p r) 顺、逆用 p(pq) p p(pq) p 吸收律 多吃少 0BB，1B 1 0B0，1B B,4、推理定律 1)AAB

5、因为A为1时， AB 为1 2)ABA 因为AB为1时，A为1且B为。 3)(AB)AB 左=1时右=1，假言推理或分离原则 4)(AB)(BC)(AC) 附加条件再(3) 传递律 可以不记，但要会推 5)(AB)(CD)(AC)(BD) 到附加再(3) (AB)(AB)B 归谬法或反证法 B为1 6)(AB)(CD)(BD)(AC)附加逆反再 7)(AB)BA 逆否再(3)。 拒取式 8)(AB)BA 到转换再(3). 析取三段论,5、Robinson证明法：机器证明法，归结法 若pq，pr为真，则qr为真。 用反证法证明，即假设qr为假。 (1) qr为0 (假设) (2) q为0，r为0

6、 (析取的定义) (3) pq为1 (已知) (4) p0为1 (2)代入(3) (5) p为1 (由(4)及的定义) (6) pr为1 (已知) (7) p0为1 (2)代入(6) (8) p为1 (由(7)及的定义) (9) p p为1 (由(5)与(8)可知),这是矛盾！ 故“假设qr为假”错！，只能为真。证毕,(1)对对碰！ (2)P必须变元 q,r可为公式 (3)前提为析取式的合取 (4)可用于反证法与顺证法。,十一、习题三 1、游泳题、看电影给出真值表主析取式范式 2、如果小赵去小李也去等问题：推理方式 3、自然推理：分离原则、逆否、条件式来回用,十二、谓词的符号即一阶逻辑命题的符

7、号化 1、个体常项 独立存在的个体，如“杨圣洪” 2、个体变元 表示某个范围(个体域)任意对象。 3、谓词 大写字母表示F，G，H 刻画一个对象的性质或多个对象之间的关系。 4、量词 All “所有的”、 “全部”、 “一切”、 F(x)表示x男人是坏蛋 , xF(x) x值域为男人集 L(x,y)表示x人与y人是同事, xyL(x,y) x,y值域为“计通院的老师集”。 5、量词 Exist “存在有”、 “某些”、 “一部分”、 F(x)表示x男人是坏蛋 , xF(x) x值域为男人集 L(x,y)表示x人与y人是同事, x yL(x,y) x,y值域为“湖南大学的职工集”。 6、掌握对简

8、单语句的符号化,7、合法的谓词公式 非逻辑符号:个体常元、函数符号、谓词符号 逻辑符号:个体变元、量词符号、联结词、逗号、括号。 项的定义：个体常元与变元及其函数式为项。 (1)个体常元和个体变元是项。 (2)若(x1,x2, xn)是n元函数,t1,t2,tn是n个项，则(t1,t2, tn)是项。 (3)有限次使用(2)得到的表达式是项。 原子公式： 设R(x1,x2,xn)是n元谓词，t1,t2,tn是项，则R(t1,t2, tn)是原子公式。,7、合法的谓词公式 项的定义：个体常元与变元及其函数式为项。 原子公式： 设R(x1,x2,xn)是n元谓词，t1,t2,tn是项，则R(t1,

9、t2, tn)是原子公式。 合式谓词公式： (1)原子公式是合式公式； (2)若A是合式公式，则(A)也是合式公式； (3)若A,B合式，则AB, AB, AB , AB 合式 (4)若A合式，则xA、 xA合式 (5)有限次使用(2)(4)得到的式子是合式。,7、合法的谓词公式 项的定义：个体常元与变元及其函数式为项。 原子公式： 设R(x1,x2,xn)是n元谓词，t1,t2,tn是项，则R(t1,t2, tn)是原子公式。 合式谓词公式： (A)、AB, AB, AB , AB 、xA、xA 量词指导变元：xA和xA中的x 量词辖域：xA和xA中的A为量词/辖域 变元的约束出现：在x和x

10、的辖域A中，x的所有出现都称为约束出现。 变元的自由出现：不是约束出现的变元。,8、合法的谓词公式的解释 例4.7：x(F(x)G(x) 其中x的取值范围是什么？ F(x)的含义是什么？G(x)的含义是什么？ 将这些问题确定后，表达式x(F(x)G(x)的真值就确定了，这就是公式的解释。 dom(x)=D1=全总个体域 F(x)表示x是人，G(x)表示x是黄种人。 x(F(x)G(x)：所有的人都是黄种人，值为F. dom(x)=D2=实数集R F(x)表示x是自然数，G(x)表示x是整数。 x(F(x)G(x)：所有的自然数都是整数，值为T.,9、谓词公式的类型 永真式(逻辑有效式):在任何

11、解释下均为真。 永假式(矛盾式):在任何解释下均为假。 可满足式:至少存在一种解释下为真。 10、代换实例： 设A0是含命题变元p1,p2,.,pn的命题公式，A1,A2,.,An是n个谓词公式(其中个体常元/变元/函数/谓词公式都未确定含义)，用Ai处处代替A0中pi的出现，所得公式A称为A0的代换实例。 定理：命题重言式的代换实例都是永真式， 矛盾式的代换实例都是矛盾式。,十三、习题四 1、符号化 2、确定谓词公式的值：常量、取值范围、谓词 3、自然推理：分离原则、逆否、条件式来回用 十四、一阶逻辑等值 1、定义： 二个谓词公式等值是指对于谓词的每种解释下真值相同。 即AB在每种解释下都是

12、永真式！,2、消去量词等值式 设个体域为有限集D=a1,a2,.,an,则有 xA(x) A(a1)A(a2) A(an) xA(x) A(a1)A(a2) A(an) 3、量词否定等值式-对于量词的德摩律 设公式A(x)含自由出现的个体变项x,则 (1) xA(x) xA(x) 不是所有的个体有某性=有些个体没有该特性 (2) xA(x) xA(x) 没有x有某些特性=所有的没有这个特性 4、无关项自由进去辖域 设公式A(x)含自由出现的个体变项x，B不含x xA(x)?B x(A(x)?B) xA(x)?B x(A(x)?B),5、量词分配: 对, 对 设公式A(x),B(x)含自由出现的

13、个体变项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) (*) 10 x(A(x)B(x) xA(x) xB(x) (*) 01 6、置换规则 若A1B1，则将某公式(A1,A2,.,An)中的A全部换成B后得到(B1,A2,.,An)，仍然等值即 (A1,A2,.,An)= (B1,A2,.,An) 局部等值变换后整体仍然相等。x(A(x)B(x)G(x)(xA(x)xB(x)G(x),7、换名规则：指导变元与约束变元同换 将某量词的指导变元与辖域中同名约束变元，换成不在

14、公式中出现的变元，则与原公式等值。 8、代替规则：某个公式中自由变元全换掉则仍与公式等值。,十五、一阶逻辑的推理理论 1、定义 若在各种解释下A1A2A3AnB只能为真,则称为前提A1,A2,An可推出结论B。 2、常见的谓词推理式 (1)命题逻辑的推理式，代换得到的谓词推理式 如pqp, xF(x)yF(y)xF(x) pq,pq, xF(x) yF(y), xF(x) yF(y) (2)特有的谓词推理式 xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x) (3)四条铁律： 全称量词的指定 xA(x)A(x0) x0是任意个体 全称量词的推广 A(x0) xA

15、(x) x0前面某全称指定 存在量词的指定 xA(x)A(c) c为某个特定的个体 存在量词的推广 A(c) xA(x) c为某个特定的个体,例题 x(F(x)G(x),xF(x)xG(x) 证明: (1)xF(x)为真 (前提) (2) F(c)为真 (存在指定,至少存在c使F(c)为真) (3) x(F(x)G(x)为真 (前提) (4) F(c)G(c)为真 (全称指定,尤其x=c时为真) (5) G(c)为真 ( (2),(4)分离) (6) xG(x)为真 (5)存在推广) 通过指定将量词去掉,通过代换实例使用命题逻辑的方法. 通过推广加上量词,对于存在只有一个实例,对推广全称,一定

16、要注意x是全称指定的.,3、一阶逻辑前束范式 定义：形如Q1x1Q2x2QkxkB的公式为前束范式，其中Qi为或，B中不含有数量词。 如 xy(F(x)G(y)H(x,y) 是前束范式 x(F(x)y(G(y)H(x,y)不是！因B有量词 定理1：任何逻辑公式可转换为前束范式。 命逻代换 约变/自变换名 扩张 例：xF(x)xG(x) xF(x)xG(x) x(F(x)G(x) 量词在前,B中无量 xF(x)xG(x) xF(x)yG(y) xF(x)yG(y)xy(F(x)G(y),十六、习题五 1、确定谓词公式的值：常量、取值范围、谓词 2、符号化 3、自然推理： 四铁律 分离原则、逆否、

17、条件式来回用 十七、集合论 1、定义 枚举法: 教学楼=复临,中楼,东楼,北楼,前进楼 描述法:偶数集=除以2余为0的所有整数 2、子集AB:A中的每个元素都是B的元素 幂集P(A)=A的所有子集的集合=2A. 如A=1,2,3 A000=,A001=3,A010=2,A011=2,3, A100=1,A101=1,3,A110=1,2,A111=1,2,3 其有23个 ,即2|A|个,3、有穷集的计数 1)、|A|=集合A的元素数 2)、例题：会英=13、日=5、德=10、法=9，同时会英日有2人，会德、法、英中任意二种有4人，会日语的既不懂法也不懂德，只会1种和3种人？,令同时会三种语言为

18、x人， 只会英为y1,只会法为y2, 只会德语y3 y1+2+4-x+x+4-x=12 y2+4-x+4-x+x=9 y3+2(4-x)+x=10 y1+y2+y3+3+2+3(4-x)+x=24,4、包含排斥原理 4.1 |A1A2|=|A1|+|A2|-|A1A2| 因为公共部分算了两次！ 例1：A1=蓝球队=10，A2=足球队=13，双重身球员3人，请问这二个球队总共多少人？ 解：|A1A2|=|A1|+|A2|-|A1A2|=10+13-3=20人 4.2 |A1A2 |=|Ai|-|AiAj| +|AiAjAk|-|AiAjAkAL| . +(-1)n-1| A1A2 An| 加奇数

19、个集合相交-偶数集合相交,A1,A2,十八、习题六 1、60人看杂志、25个学生、1300整数、120的素数(不是2、3、5、7、11的倍数、不是1)、 2、符号化 3、自然推理： 四铁律 分离原则、逆否、条件式来回用 十九、关系 1、有序对 ： 有秩序的二个元素排在一块称为有序对,形如 2、笛卡尔积/直积AB 形如AB=|aA，bB,3、关系 ： 将笛卡尔积中前后两个元素之间存在某种关系的序偶检出来,便得到一个关系. AB=1,2,3a,b,c=, , R1=前后两个元素的序号一样 =,三、关系 AB=1,2,3a,b,c=, , R1=前后两个元素的序号一样 =, 用如下形式的关系矩阵表示

20、,A=1,2,3, FAxA,GAxA A上的关系 F=, G=,五、关系的分类 ：图、关系矩阵、序偶 自反关系:若xA,都有R 反自反关系:若xA有R 对称关系:若R有R 反对称关系:若R,Rx=y 若R且xyR则反对称 定义等价 如:A=1,2,3 R1=, 对称 R2=, 反对称 R3=, 因R1不对称,因与成对出现,而不是反对称,五、关系的性质与分类 传递关系:若R,RR 表示从结点x出发,连续2跳后达到结点的z所成序偶仍在R中。 而连续2跳所达关系即为RR, 仍在R中即要求RRR。 如A=1,2,3 R1=, 可传递的，OK R1R1=R1R1故为可传递！,六、关系的闭包：加点序偶使

21、之成某种类型 1、R自反闭包r(R)的定义： (1)r(R)自反; (2)Rr(R); (3)RR,R自反r(R)R 最小性 恰好增加到变成自反为止。 2、R对称闭包s(R)的定义： (1)s(R)对称; (2)Rs(R); (3)RR,R对称s(R)R 最小性 3、R传递闭包t(R)的定义： (1)t(R)传递; (2)Rt(R); (3)RR,R传递t(R)R 最小性,t(R)=RR2 R3. Rn-1.任何两点最多n-1步达 =M+M2+M3+.+Mn-1. 例A=a,b,c,d, R=, t(R)=RR2R3, R2=, R3=, , =, t(R)=, , , , , , , , ,

22、 , , , ,七、等价关系与划分 自反、对称、可传递的关系称为等价关系。 例 A=1,2,3,4,5,6,7,8 R=, 等价类1,4,7,2,5,8,3,6彼此不相交，并集=A，称为A的划分。,七、等价关系与划分 R= 1,4,7x1,4,72,5,8x2,5,8 3,6x3,6 得到划分 1,4,7, 2,5,8,3,6. 若有A的划分，倒用以上工作会得到一个划分！如A1=1,2,3,A2=4,5,6,A3=7,8，则： R=A1A1A2A2 A3A3 =, , , , , , , 可验证R是对称、自反、可传递的等价关系。,八、偏序关系 1)自反、反对称、可传递的关系。广义的“小于等于”

23、关系，记为。 2)当时，写成xy，主要为了直观。 3)当但xy时，记成x或。 5)全序(线序): x,yA ，x与y都可比。如 A=1,2,3,4,5,6 R=:xy 狭义 B=1,2,A=,1,2 R=:xy,xA,yA,即x与y是B的子集。全序 B=1,2,A=,1,2,1,2 R=:xy,xA,yA,即x与y是B的子集。 偏序,八、偏序关系 2)当时，写成xy，主要为了直观。 4)x,yA x与y可比是指或。 6)偏序集：集合A与定义其上偏序关系。 7)盖住:xA,yA,x:xy,xA,yA, 1盖住, 2盖住,但1,2并不盖住.,八、偏序关系 7)盖住:xA,yA,x:xy,xA,yA

24、, 1盖住, 2盖住,但1,2并不盖住. 去掉自反线可传递线得到覆盖关系 哈斯图,八、偏序关系 7)盖住:xA,yA,x,剔可传递生、自反,八、偏序关系-最大元/最小元 8)最大元:设是偏序集，BA, y0B, 若xB,均有R，则y0是B的最大元。 y0与B每个元素x有关系R即可比，且比其大。,B=a,b,c,d,e,f,g,h 最大最小无,B=18 有最小,B=1,2,4,8 有最大与最小,B=b,c,d,e,f 最大有,八、偏序关系-极大元/极小元 8)最大元:设是偏序集，BA, y0B, 若xB,均有R，则y0是B的最大元。 y0与B每个元素x有关系R即可比，且比其大。 9)极大元: 不

25、存在x,使之与y0可比且R，,极大元 a,f,h,极小 元 a,b,c,g,极大元 8,6,9,7,极小元 1,二运算的定义 xP(A), yP(A) x+y =xy, xy=xy xBoolean, yBoolean x+y =xy, xy=xy x+y =(x(i,j)+y(i,j), x-y =(x(i,j)-y(i,j), xy=(x(i,j) y(i,j), 很幸运！这些运算都可利用，它们所在领域的运算符来定义，还有很多运算，只能给出其运算的结果，如xy=(xy) mod 5 x,y0,1,2,3,4,三、运算的性质 1、交换律 设是集合S上的二元运算，若x,yS都有xy=y x，

26、则称在S上是可交换的， 或者说运算在S上满足交换律。 若运算表是对称的，则满足交换律。xy=(xy) mod 5 x,y0,1,2,3,4,三、运算的性质 2、结合律 设是集合S上的二元运算，若x,y,zS都有(xy)z=x(yz)， 则称在S上是可结合的,或者说运算在S上满足结合律。 如：x,y,zP(A) (x+y)+z=(xy)z=x(yz)=x+(y+z) (xy)z=(xy)z=x(yz)=x(yz) 当运算满足结合律时，常将决定运算次序的园括号去掉，如(x+y)+z=x+y+z。 普通的加、乘、集合的并、交、逻辑的与、逻辑或、矩阵的加、乘满足结合律。,三、运算的性质 3、幂等律 设

27、是集合S上的二元运算，若xS都有xx=x， 则称在S上是幂等的,或者说运算在S上满足幂等律。 如：xP(A) x+x=(xx)=x , xx=(xx)=x 逻辑的与、逻辑或满足结合律。 有些运算不满足幂等律，但是集合S中的某些元素满足！ 如普通加法不满足幂等，但0满足0+0=0, 普通乘法不满足幂等，但1满足11=1。 普通矩阵的乘法不幂等，但单位矩阵满足！,三、运算的性质 4、分配律 设与*是集合S上的二种运算，若x,y,zS都有 x*(yz)=(x*y)(x*z)， (yz)*x=(y*x)(z*x) 则称*对是可分配的。 如： x,y,zP(A), 对可分配， x(yz)=(xy)(xz

28、) 对也可分配， x (yz)=(xy)(x z) 逻辑的与、逻辑或满足结合律。 有些运算不满足幂等律，但是集合S中的某些元素满足！ 如普通加法不满足幂等，但0满足0+0=0, 普通乘法不满足幂等，但1满足11=1。 普通矩阵的乘法不幂等，但单位矩阵满足！,三、运算的性质 5、吸收律 设与*是集合S上的二种可交换的二元运算，若x,yS都有 x*(xy)=x ， x(x*y)=x则称*与是满足吸收律。 如： x,y,zP(A), x(xy)=x， x (xy)=x 又如： x,y,z命题变元 x (xy)=x， x (x y)=x 小结： 交换律、结合律、幂等律、分配律、吸收律是普通的加与乘、集

29、合的并与交、命题变元的与或等运算的规律的总结、推广！,四、集合S中满足某运算的特殊元素 1、单位元 设是集合S上的二元运算，如果集合S中的某元素eL，对xS都有 eLx=x 则称之为左单位元。 设是集合S上的二元运算，如果集合S中的某元素eR，对xS都有 xeR=x 则称之为右单位元。 如果S中某个元素既是左单位元，又是右单位元，则为单位元。 如：A= A=A 0+x=x+0=x 1*x=x*1=x,四、集合S中满足某运算的特殊元素 1、单位元 对xS都有 eLx=x 则称之为左单位元。 对xS都有 xeR=x 则称之为右单位元。 定理:设是S上的二元运算,若存在左单位元eL与右单位元eR,则

30、eL=eR=e且唯一 证明： xS都有eLx=x eLeR=eR xS都有 xeR=x eLeR=eL 由以上二式可知eR=eL，即两个单位元的值相等，不妨将其值记为e ，则e既是左单位元，又是右单位元，故由单位元定义可知,e是单位元。 如： A= A=A 0+x=x+0=x 1*x=x*1=x,四、集合S中满足某运算的特殊元素 1、单位元 对xS都有 eLx=x 则称之为左单位元。 对xS都有 xeR=x 则称之为右单位元。 2、零元 对xS都有 Lx= L 则称之为左零元。 对xS都有 x R = R 则称之为右零元。 定理：设是S上的二元运算,若存在零元与单位元e,且集合S中至少有2个元

31、素，则e 。 证明：假设=e ， 由单位元定义可知，xS都有xe=x， 由假设可知=e ， 故x=x . (1) 。 由零元的定义可知，xS都有x=.(2) 由(1)(2)可知x=，又由假设可知=e ，故x= =e 故S中只有1个元素！矛盾！假设错！,四、集合S中满足某运算的特殊元素 3、逆元 并不是所有元素有逆元！ 某xS若有yLS,使得yLx=e，左逆元。 某xS若有yRS,使得xyR=e，右逆元。 则y既是x的左逆元又是右逆元，则为x的逆元。 定理：设运算满足结合律且存在单位元，某元素x，若存在左逆元yL与右逆元yR,则yL=yR并且唯一。 证明：yL=yLe=yL(xyR)=(yLx)

32、yR=eyR=yR。 唯一性：若x有两个逆元y1、y2。 y1=y1e=y1(xy2)=(y1x)y2=ey2=y2.,六、代数系统同构与同态 如果判断类似呢？同构或同态检测！ 定义1：设有两个代数系统,，若能在集合A与B之间构造映射f，满足如下要求： (1)yB均xA，使得y=f(x) (1)满射(2)1-1 (2)当x1,x2A, x1x2有f(x1),f(x2)B, f(x1)f(x2) (3) x1,x2A有f(x1x2)=f(x1) *f(x2),一、群的定义 (0)设V=是封闭代数系统，称为广群。 (1)设V=是封闭、可结合,则为半群。 (2)设V=是封闭、可结合、有单位元e，则V

33、为幺群，也叫独异点。 (3)V=是封闭、可结合、有单位元e、每aS，有逆元a-1S则称为群G。Group 例题1： 正整数集上的加法 x+y+z=(x+y)+z=x+(y+z) 可结合 x+0=x+0=x 单位元为0 x+(-x)=0 x的逆元为相反数。 故是群。,二、群的性质 有限群：指群的元素集G有限，|G|有限。 如：,无穷群， 有限群， Klein四元群是有限群 平凡群：只有单位元e的代数系统。 如： , 交换群：若群中的运算可交换，Abel群。 如： ,无穷群， 有限群， Klein四元群是有限群,二、群的性质 n次幂：,理解:an表示a进行n次运算,是群,aG 如：在中13表示1进

34、行3次+运算=1+1+1=3 如: 在中13表示1进行3次运算=11 1=1 如：,其中Z3=0,1,2, 0n=0n个3k型数加仍是3k型(3k1+3k2.+3kp)%3=0 1n=n个3k+1型数加(3k1+1+3k2+1+.+3kp+1)%3=n%3 2n=n个3k+2型数加(3k1+2+3k2+2.+3kp+2)%3=2n%3 1+2=(3k+1+3m+2)%3=3%3=0 互逆 (1-4)=(1-1)4=24=2n%3=2,定理1：设G为群，则G的幂运算满足： aG,(a-1)-1=a 验证a是a-1的逆元,(a-1)-1为a-1的逆元 a,bG,(ab)-1=b-1a-1 验证b-

35、1a-1是ab的逆元 aG,(an)am=an+m,n,mz 由幂的定义 aG,(an)m=anm,n,mz an进行m次运算 证明： (1) a-1是a的逆元，而逆元是相互的，故a也是a-1的逆元，同时a-1的逆元记为(a-1)-1，故a=(a-1)-1。 (2) (ab)-1是ab的逆元， 而ab(b-1a-1)=abb-1a-1=aea-1=aa-1=e， (b-1a-1)ab=b-1a-1ab=b-1eb=b-1b=e 根据逆元的定义，b-1a-1也是ab的逆元 而逆元唯一，故两个逆元相等，即(ab)-1=b-1a-1 (3) anam=an-1aam=an-1am+1=an-2aam

36、+1=.a0am+n=am+n (4) (an)m=anananan.an=anm 指数相加和为(n+n)=nm,定理2：设G为群且|G|1，则G中没有零元。 证明： 假设有零元, 由刚才定理可知e 由零元的定义可知，xG有x=x= 所以x=xe， 故零元不可能有单位元，这与群中每个元素有逆元矛盾！ 所以“假设有零元”是错的，即群中没有零元。,定理3：设为群，对于a, bG， 必存在唯一的 xG，使得a x = b。群中方程有解！ 证明：设 a 的逆元是a1 ，可验证 x = a1 b是其解！ 则 a x = a (a1 b) = (a a1) b = e b = b 若另有一解 x1，满足

37、a x1= b 则a1 (a x1)= a1 b 即 x1 = a1 b 故x1=x，即解唯一！,定理4：设G为群，则G的满足消去律： a,b,cG,若ab=ac，则b=c a,b,cG,若ba=ca,则b=c， 证明： (1) b=eb=a-1ab=a-1ac=ec=c (2) b=be=baa-1=caa-1=ce=c 定理5：设为群，aG,|a|=r，设k整数 (1) ak=er|k ar=e (2) |a-1|=|a|, 证明: (1) e=akr|k。用r去除k得余数i,则0ir,即k=mr+i e=ak=amr+i=amr.ai=(ar)mai=emai=ai 由于r是使得at=e

38、的最小整数，若0ir则矛盾，故i=0 故k=mr即r|k r|ke=ak， r|kk=mr ak=amr=(ar)m=em=e,三、子群：G是群的元素集，HG,若代数系统是群，则称为的子群，也简称H是G的子群，记为HG. 若HG则称H是G的真子群，记为H是的子群！ 是的子群 是的子群 是的子群，n是自然数 又如： 对于任何群其本身是其子群，因为GG 是的子群。因为是群,e G 平凡子群!,(1)子群判断定理一：设G为群, HG, H是G的子群 (i)a,bH,有abH(封闭) (ii) aH,有a-1H(逆元) (2)子群判断定理二:G为群, HG, H是G的子群 a,bH,有ab-1H (3

39、)子群判断定理三:G为群, HG, |H|有限,H是子群a,bH,有abH(只要封闭即可) 证明:左右显然! 右左:由Th1只需要证逆元存在即可. bH (i)若b=eH, 而母群G中ee=e可知e-1=e,而eH故e-1H. (ii)若be,由封闭性b2=bbH即b2H,故b3=b2bH S=b,b2,b3,bk,H |S|H|,而|H|有限S有限,bi肯定与bj相等!否则无穷了! bi=bj(ij)bjbi-j=bje,根据G中消去律bi-j=e,而 be i-j1bi-j-1b=bbi-j-1=e bi-j-1是b的逆元，即b-1=bi-j-1, 而bi-j-1SH，故bi-j-1H，即

40、b-1H,四、Abel群即交换群 定义：设是群,其运算是可交换的,则称为交换群. 例题:是交换群。 解： 封闭性：x,y0,1,2,3,则z=x+4y=(x+y)mod 4肯定在03之间，故z0,1,2,3。 可结合：x,y,z0,1,2,3 ,x+4y+4z=(x+y+z)mod 4， 由于(x+y+z) mod 4可结合，故+4是可结合的。 单位元：x+4e=e+4x=x,故e=0. 逆元：0+40 =0,1+43=0,2+42=0， 故0-1=0,1-1=3,3-1=1,2-1=2 交换：x+4y=(x+y)mod 4 y+4x=(y+x)mod 4 故x+4y= y+4x 故:是交换群

41、！,五、循环群 定义：设是群,若G存在一个元素a，使得G中任意元素都由a的幂组成，则称该群为循环群。 定理9：任何一个循环群,*必是Abel群。 定理10：设是生成元为a的循环群且|G|=n则an=e 故G=a,a2,a3,.,an-1,an 定理11：设是循环群，则 (1)若是无限循环群，由G只有a与a-1两个生成元。 (2)若|G|=n，则1n-1中与n互质的整数都是生成元。 如:无限循环群，其生成为1与1-1(即-1)两个生成元。 是4阶循环群，则13之间与4互质的整数有1,3，它俩都是生成元。 1,12=1+41=2,13=1+41+41=3,14=1+41+41+41=0 3,32=

42、3+43=2,33=3+43+43=1,34=3+43+43+43=0,五、循环群 定义：设是群,若G存在一个元素a，使得G中任意元素都由a的幂组成，则称该群为循环群。 定理12: (1)G=是循环群，则G的子群仍是循环群。 (2)G=无限循环群，则G的子群除e外都是无限循环 (3)G=n阶循环群,则G有d阶子群(d0,d|n) 如即模4加群，有限群！ 4的正因子为1,2,4 是的1阶子群， 是它自已的4阶子群 =,+4它的2阶子群。,六、陪集 H是G的子群，aG,H的右陪集Ha=x|x=ha,hH，其中a称为Ha的代表元或特征元。 例题：设G=e,a,b,c是Klein四元群，H=e,a是G

43、的子群，其实是即a的生成子群，H的所有陪集是： He=he|hH=ee,ae=e,a=H Ha=ha|hH=ea,aa=a,e=H 定理13：设H是G的子群，则 (1) He=H (2) aG，有aHa 证明： (1)He=he|hH=h|hH=H (2)Ha=ha|hH=ea, h1a, hka =a, h1a, hka 故Ha=a, h1a, hka, 显然aHa， 由e不一定在Ha中，故Ha不一定为子群。,六、陪集 H是G的子群，aG,H的右陪集Ha=x|x=ha,hH，其中a称为Ha的代表元或特征元。 定理13：设H是G的子群，则 (1) He=H (2) aG，有aHa(陪集至少有代

44、表元) 定理14：设H是G的子群，则a,bG aHbab-1HHa=Hb 如：G=e,a,b,c是Klein四元群，H=e,a是G的子群： He=he|hH=ee,ae=e,a=H Ha=ha|hH=ea,aa=a,e=H Hb=hb|hH=eb,ab=b,c cHb,cb-1=cb=aH Hc=hc|hH=ec,ac=c,b bHc,bc-1=bc=aH,六、陪集Ha=x|x=ha,hH 定理13H是子群则(1) He=H (2) aG，有aHa 定理14H是子群则a,bG aHbab-1HHa=Hb 定理15HG,R=|ab-1HR是等价关系,aR=Ha (1)证明R是自反的。 xH xx

45、-1=e，而H是群故eH xx-1H R (2)证明R是对称的。 R xy-1H，因为H是群，故(xy-1)-1H即yx-1H yx-1H R,六、陪集Ha=x|x=ha,hH 定理16(Lagrange)：G有限群,HG|G|=|H|G:H| 即群G的元素数=子群的元素数不同陪集的个数。 推论 G是n阶群,则aG,|a|是n的因子，且an=e 例题 6阶群中必有3阶元。即 a,a3=e 解:由Lagrange定理，6阶群的子群，只能是1,2, 3, 6. 若G中有6阶元，即a6=e,故(a2)3=e即a2是3阶元。 若G中没有6阶元则必有3阶元。 反证法，假设在没有6阶元时也没有3阶元，则只

46、有1阶元与2阶元，1阶元为e，其余均为2阶元,ae时，a2=e, 由于G有6个元素，除a,e外，还可找到b,H=e,a,b,ab是子群。 |H|=4,不是|G|=6的因子，与定理10矛盾！假设错！ H封闭！可结合！有单位元e, 逆元(a-1=a,(ab)2=b2a2=e 故(ab)-1=ab),八、置换群 定义:设S=1,2,.,n，双射:SS称为S上的n元置换 乘积或复合 =先进行变换，接着进行变换 如122, 故12，如231, 故21 如344, 故34，如413, 故43 定理17 是群！(S)是SS所有置换的集合。 证明: 封闭性: 1, 2 (S),则12=先进行1变换，接着进行2

47、变换，变换后仍SS双射，故12 (S)。 可结合性: 1, 2, 3 (S),求证(12)3=1(23) 不妨设x1y2z3w. (x1y2z) 3w(x12z)3wx123w x1(y2z3w) x1 (y23w) x123w,八、置换群 定义:设S=1,2,.,n，双射:SS称为S上的n元置换 乘积或复合 =先进行变换，接着进行变换 如122, 故12，如231, 故21 定理17 是群！(S)是SS所有置换的集合。 证明: 封闭性、 可结合性：已证 单位元: e( S) , (S),求证e=e= 映射e定义为：xex即为不变映射！ 则xyey xey e= (xexy) xey e= 故

48、e=e= 逆元：e( S) , (S),求证=e 不妨设映射：xy，则取映射：yx 则xy x xx, yxy yy 故xx, yy保持不变，即为不变映射！故互为逆元,S3=(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2) 的运算表,八、置换群 定义:设S=1,2,.,n，双射:SS称为S上的n元置换 乘积或复合 =先进行变换，接着进行变换 如122, 故12，如231, 故21 定理17 是群！n元对称群！也记为 定理18 是群，则其运算表的每一行/每一列均为G的元素置换。如Klein群！,九、环 设是代数系统, 与*是二元运算,如果 (1) 是交换群; (2) 是

49、半群(封闭与可结合); (3) 半群运算符*对群运算符可分配。 则是环！ 如 是环！ xy=(x+y)%n xy=(xy)%n 除n余均0n-1 封闭、可结、0,和为n、交换 封闭、可结合 x(y z)=x y y z (y z)=(x+y)%n x(y z)=(x*(y+z)%n)%n=(x*y+x*z)%n=xyyz,九、环整环 设环 (1) 半群即乘法运算*可交换则为交换环; (2) 半群即乘法运算*有单位元则含幺环； (3)a,bR,a*b=0a=0或b=0则称G无零因子。 (4)环是交换环、含幺环、无零因子则称为整环 半群运算有单位(独异点)、可交换、无0因子。 (5)若G是整环，G

50、中至少有2个元素0,a， 若aG-0,a在乘法运算下有逆元则为域！ 是群，是群！*可交与无0因子！ 与群*对+分、*可交、无0实数域,度,某结点关联边的条数，称为该点的度数： D(A)=5,d入(A) =1,d出(A) =4, 有向图 d入(A) +d出(A) =d(A)=5 “入”进入某结点的边，也称为“负边”，负度 “出”离开某结点的边，也称为“正边”，正度,各点度数和=边数的2倍,deg(v)=2|E|=2m (为偶数) 证明： 先去掉所有的边，每个点、整个图的度数为0 增加一条边e=(u,v)，使结点u与v的度数的各增加1 。 每增加一条边使整个图的度数增加2。 deg(v)=2|E|

51、 =2m(为偶数),由邻接矩阵A计算可达性矩阵P方法：1、B=A+A2+A3+An 2、将B中不为零的元素均改换为1，为 零的元素不变，即为可达性矩阵P。,A=,B=,注意：在计算P时，在每个AL中,对于两个结点间具有路的数目不感兴趣，只要有一条路即可，表明两结点间是否有路即可。 因此我们可将矩阵A，A2，An分别改为布尔矩阵A(1),A(2),A(n),于是计算P可简化为： P=A(1) A(2) A(n) 其中A(i)表示布尔运算意义下的A的i次方。,WarShall算法： For I=1 TO N /从第1列到第N列 For J=1 To N /每列从1行到第N行 If AJ,I=1 T

52、hen 第J行=第J行第I行 Endif EndFor /行号J值加1 EndFor / 列号I值加1,邻接矩阵,对于有向图，如果从结点vi到结点vj之间有一条边，则a(i,j)=1，否则为0。 由于结点vi到vj有一条边，反过来vj到vi之间不一定有一条，故不一定对称。 对于无向图，如果结点vi到Vj有一条边，则a(i,j)=1，否则为0。 由于Vi到Vj有一条边时，反过来Vj到Vi肯定也有一条边。故它是对称的。,可表示自环，不能表示重边,关联矩阵,关联矩阵表示结点与边之间的关联关系。 对于有向图： 如果Vi是ej的起点，则b(i,j)=1。 如果Vi是ej的终点，则b(i,j)=-1。 如

53、果以上两种情况不存在，则b(i,j)=0。 对于无向图： 如果Vi到ej某个端点，则b(i,j)=1。 否则 b(i,j)=0。 该矩阵的行对应为“点”，列对应“边”， nm.,ej,Vi,ej,Vi,ej,Vi,ej,Vi,重边可表示，自环不可能表示,A,B,C,D,e1,e2,e3,e4,e5,e6,e7,a,b,c,d,e1,e2,e3,e4,e5,e6,欧拉在1736年的论文中提出了一条简单原则，确定了哥尼斯堡七桥问题是不能解的。 定义对于无孤立结点图G，若存在一条路，经过图每边一次且仅一次，该条路称为欧拉路； 若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路。 过每点一次

54、称为Hamilton回路 具有欧拉回路的图称为欧拉图。,定理无向图G存在一条欧拉路G是连通的，且有0个或2个奇数度结点。首尾相接的边构成路 证明：左右必要性 设G具有欧拉路V0e1V1e2eiViei+1ekvk，此路包括图中所有边,则此路包括所有结点，所有点都在这条路上, 任何两点之间都存在一条路，即任何两点都是连通的，故G是连通的。 对任意一个中间结点Vi，在欧拉路中，Vi每出现现一次必关联2条边，故Vi虽可重复出现，但deg(Vi)必是偶数。 当端点V0=Vk，它是欧拉回路，该点也是中间点，故Deg(Vi)也为偶数。 当端点V0Vk时，则在端点处各自只关联一条边，故其度数为奇数。,Ham

55、ilton找到一条回路，使它包含图中每个结点一次且只一次，最后回到起点？环球旅游的问题。 经过每结点恰 一次为H路，回起点为H回路。有H回路的图为H图,Hamilton,Euler回路：经过每条边一次，也仅仅一次的回路。 Hamilton路：经过每个结点一次，也仅仅一次的回路。 旅行商路：寻找最短的H回路。,1)d0= ，权系数从小到大排队，编号小前 边 a35 a15 a24 a14 a12 a13 a34 a23 a45 a25 权 3 4 4 9 10 10 11 13 16 20,Dijkstra算法,1)D(1)=0,D(i)=W1i,若i与1有边相连则1到i的路长=权重,否则. S=2,3,n 2)在未用点集S中，寻找路长D(i)最小点j,同时从S去掉该点，直到S为空,找最小结点。 3) 调整后继点的路长:在S中寻找j的后继结点结点i，若经过j到i的路长d(j)+w(j,i)d(i)原值，则将d(i)修改为d(j)+w(j,i),回到第2步。,j,i,1,D1=0 D2=7 D3=1 d4=d5=d6= S=2,3,4,5,6 最小值为1 (D3) S=2,4,5,6,修改V3后继点的路长,为: d2=6, d5=3 ，d6=8.,D1=0,d2=