离散数学公式17727(10页).doc

-离散数学公式17727-第 10 页基本等值式1.双重否定律A Û A2.幂等律A Û AA,A Û AA 3.交换律AB Û BA，AB Û BA4.结合律(AB)C Û A(BC) (AB)C Û A(BC)         A(BC) Û (AB)(AC) （对的分配律）A(BC) Û (AB)(AC) （对的分配律）·摩根律     (AB) Û AB (AB) Û AB         A(AB) Û A，A(AB) Û A 8.零律     A1 Û 1,A0 Û 0         A0 Û A，A1 Û A        AA Û 1   AA Û 0    AB Û AB   A«B Û (AB)(BA)     AB Û BA      A«B Û A«B      (AB)(AB) Û A 求给定公式范式的步骤 (1)消去联结词、«(若存在)。(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。(3)利用分配律：利用对的分配律求析取范式，对的分配律求合取范式。推理定律-重言蕴含式(1) A Þ (AB)                          附加律(2) (AB) Þ A                            化简律(3) (AB)A Þ B                            假言推理(4) (AB)B Þ A                         拒取式(5) (AB)B Þ A                           析取三段论 (6) (AB) (BC) Þ (AC)                  假言三段论(7) (A«B) (B«C) Þ (A « C) 等价三段论(8) (AB)(CD)(AC) Þ(BD)          构造性二难  (AB)(AB)(AA) Þ B       构造性二难(特殊形式)(9)(AB)(CD)(BD) Þ(AC) 破坏性二难 设个体域为有限集D=a1,a2,an,则有（1）"xA(x) Û A(a1)A(a2)A(an) （2）$xA(x) Û A(a1)A(a2)A(an)   设A(x)是任意的含自由出现个体变项x的公式，则（1）"xA(x) Û $xA(x)（2）$xA(x) Û "xA(x)设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则（1） "x(A(x)B) Û "xA(x)B"x(A(x)B) Û "xA(x)B"x(A(x)B) Û $xA(x)B"x(BA(x) Û B"xA(x)（2） $x(A(x)B) Û $xA(x)B$x(A(x)B) Û $xA(x)B$x(A(x)B) Û "xA(x)B$x(BA(x) Û B$xA(x)设A(x)，B(x)是任意的含自由出现个体变项x的公式，则（1）"x(A(x)B(x) Û "xA(x)"xB(x)（2）$x(A(x)B(x) Û $xA(x) $xB(x)全称量词“"”对“”无分配律。存在量词“$”对“”无分配律。UI规则。UG规则。EG规则。EI规则。ABx|xAxB 、ABx|xAxB ABx|xAxÏB 幂集 P(A)x | xÍA 对称差集 AÅB(AB)(BA) AÅB(AB)(AB) 绝对补集 Ax|x Ï A 广义并 Ax | $z(zAxz) 广义交 Ax | "z(zAxz)设 Aa,b,c,a,c,d,a,e,f Ba Ca,c,d则 Aa,b,c,d,e,f Ba Cac,d Aa Ba Cac,d集合恒等式 幂等律 AAA AAA 结合律 (AB)CA(BC) (AB)CA(BC) 交换律 ABBA ABBA 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 同一律 AÆA AEA 零律 AEE AÆÆ 排中律 AAE 矛盾律 AAÆ 吸收律 A(AB)A A(AB)A 德摩根律 A(BC)(AB)(AC) A(BC)(AB)(AC) (BC)BC (BC)BC ÆE EÆ 双重否定律 (A)A 集合运算性质的一些重要结果ABÍA，ABÍBAÍAB，BÍABABÍAABAB ABB Û AÍB Û ABA Û ABÆAÅBBÅA (AÅB)ÅCAÅ(BÅC) AÆÅA AÅAÆ AÅBAÅC Þ BC 对偶(dual)式：一个集合表达式，如果只含有、Æ、E、Í、Ê，那么同时把与互换，把Æ与E互换，把Í与Ê互换，得到式子称为原式的对偶式。有序对<x,y>具有以下性质： （1）当xy时，<x,y><y,x>。 （2）<x,y><u,v>的充分必要条件是xu且yv。 笛卡儿积的符号化表示为 A×B<x,y>|xAyB 如果|A|=m,|B|=n,则|A×B|=mn。笛卡儿积的运算性质 (1)对任意集合A，根据定义有A×ÆÆ, Æ×AÆ(2)一般的说，笛卡儿积运算不满足交换律，即A×BB×A (当 AÆ BÆ AB 时)(3)笛卡儿积运算不满足结合律，即(A×B)×CA×(B×C)(当 AÆ BÆ CÆ 时)(4)笛卡儿积运算对并和交运算满足分配律，即A×(BC)=(A×B)(A×C) (BC)×A=(B×A)(C×A)A×(BC)=(A×B)(A×C) (BC)×A=(B×A)(C×A)(5)AÍC BÍD Þ A×B Í C×D常用的关系对任意集合A，定义全域关系 EA=<x,y>|xAyA=A×A 恒等关系 IA=<x,x>|xA空关系 Æ小于或等于关系：LA=<x,y>|x,yAxy，其中 AÍR。整除关系：DB=<x,y>|x,yBx整除y，其中 AÍZ* ，Z*是非零整数集包含关系：RÍ<x,y>|x,yAxÍy，其中 A是集合族。 关系矩阵和关系图设 A=1,2,3,4，R=<1,1>,<1,2>,<2,3>,<2,4>,<4,2>，则R的关系矩阵和关系图分别是 定义域 dom R x | $y(<x,y>R )值域 ran Ry | $ x(<x,y>R)域 fld Rdom R ran R 例 求R=<1,2>,<1,3>,<2,4>,<4,3>的定义域、值域和域。 解答dom R1,2,4 ran R2,3,4 fld R1,2,3,4 逆 R-1<x,y>|<y,x>R右复合 F°G<x,y> | $t(<x,t>F<t,y>G)限制 RA=<x,y>|xRyxA 像 RA=ran(RA) 例 设R<1,2>，<1,3>，<2,2>，<2,4>，<3,2>R1<1,2>，<1,3> RÆ Æ R2,3<2,2>，<2,4>，<3,2> R12,3 RÆ Æ R32设F是任意的关系，则 (1)(F-1)-1F (2)dom F-1ran F，ran F-1dom F 设F，G，H是任意的关系，则(1)(F°G)°HF°(G°H)(2)(F°G)-1G-1 ° F-1设R为A上的关系，则R ° IAIA° RR设F，G，H是任意的关系，则(1) F°(GH)F°GF°H(2) (GH)°FG°FH°F(3) F°(GH)ÍF°GF°H(4) (GH)°FÍG°FH°F设F为关系，A,B为集合，则(1) F(AB)FAFB (2) FABFAFB (3) F(AB)FAFB (4) FABÍFAFB 关系的幂运算设R为A上的关系，n为自然数，则R的n次幂定义为：（1） R0<x,x>|xAIA（2） Rn+1Rn ° R幂运算的性质设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。设R是A上的关系，m,nN，则(1)Rm ° RnRm+n (2)(Rm)nRmn设R是A上的关系，若存在自然数s,t(s<t)使得Rs=Rt，则(1) 对任何kN有 Rs+k=Rt+k(2) 对任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s(3) 令S=R0，R1，Rt-1，则对于任意的qN有 RqS自反 "x(xA<x,x>R)，反自反 "x(xA<x,x>ÏR)，对称 "x"y(x,yA<x,y>R<y,x>R)反对称 "x"y(x,yA<x,y>R<y,x>Rx=y)，传递 "x"y"z(x,y,zA<x,y>R<y,z>R<x,z>R)关系性质的等价描述 设R为A上的关系，则（1）R在A上自反当且仅当 IA Í R（2）R在A上反自反当且仅当 RIAÆ（3）R在A上对称当且仅当 RR-1（4）R在A上反对称当且仅当 RR-1 Í IA（5）R在A上传递当且仅当 R°RÍR (1)若R1，R2是自反的和对称的，则R1R2也是自反的和对称的。(2)若R1和R2是传递的，则R1R2也是传递的。关系性质的特点 自反性反自反性对称性反对称性传递性集合表达式IA Í RRIAÆRR-1RR-1 Í IAR°RÍR关系矩阵主对角线元素全是1主对角线元素全是0 矩阵是对称矩阵 若rij1，且ij，则rji0 对M2中1所在位置，M中相应的位置都是1 关系图每个顶点都有环每个顶点都没有环 如果两个顶点之间有边，一定是一对方向相反的边(无单边) 如果两点之间有边，一定是一条有向边(无双向边) 如果顶点xi到xj有边，xj到xk有边，则从xi到xk也有边 关系的性质和运算之间的关系 自反性反自反性对称性反对称性传递性R1-1R1R2R1R2××R1R2××R1 ° R2××××闭包的构造方法设R为A上的关系，则有（1）自反闭包 r(R)RR0（2）对称闭包 s(R)RR-1（3）t(R)RR2R3 关系性质与闭包运算之间的联系设R是非空集合A上的关系，（1）若R是自反的，则s(R)与t(R)也是自反的。（2）若R是对称的，则r(R)与t(R)也是对称的。（3）若R是传递的，则r(R)是传递的。等价类的性质设R是非空集合A上的等价关系，则（1）"xA，x是A的非空子集。（2）"x,yA，如果xRy，则xy。（3）"x,yA，如果<x,y>ÏR，则x与y不交。（4）x|xAA。偏序集中的特殊元素设<A，>为偏序集，BÍA，yB。（1）若"x(xByx)成立，则称y为B的最小元。（2）若"x(xBxy)成立，则称y为B的最大元。（3）若"x(xBxyxy)成立，则称y为B的极小元。（4）若"x(xByxxy)成立，则称y为B的极大元B最大元最小元极大元极小元2,3,6,12,24,36 无无 24，36 2,3 6,12 126  12 62,3,6 6无 6 2,3 6 66 66 363242126B上界下界上确界下确界2,3,6,12,24,36 无 无 无无 6,12 12,24,362,3,6 12  62,3,6 6,12,24,36无 6 无 6 6,12,24,36,2,3,6,6 6 函数相等由定义可知，两个函数F和G相等, 一定满足下面两个条件：（1）dom Fdom G （2）"xdom Fdom G，都有 F(x)G(x) 所有从A到B的函数的集合记作BA，读作“B上A”，符号化表示为 BAf | f：AB 。例：设A1,2,3，Ba,b，求BA。 BA f0, f1, f2, f3, f4, f5, f6, f7 。其中 f 0<1,a>,<2,a>,<3,a> f 1<1,a>,<2,a>,<3,b> f 2<1,a>,<2,b>,<3,a> f 3<1,a>,<2,b>,<3,b> f 4<1,b>,<2,a>,<3,a> f 5<1,b>,<2,a>,<3,b> f 6<1,b>,<2,b>,<3,a> f 7<1,b>,<2,b>,<3,b>设f:AB，（1）若ran fB，则称f:AB是满射(surjection)的。（2）若"yran f 都存在唯一的xA使得f(x)y，则称 f:AB是单射(injection)的。（3）若f 既是满射又是单射的，则称f:AB是双射(bijection) abc1234 abc1234d abc1234d abc123d单射 双射 函数 满射例：判断下面函数是否为单射、满射、双射的，为什么?(1) f：RR，f(x)= -x2+2x-1 (2) f：Z+R，f(x)=ln x，Z+为正整数集(3) f：RZ，f(x)=ëxû (4) f：RR，f(x)=2x+1。解（1）f 在x=1取得极大值0。既不是单射也不是满射的。（2）f 是单调上升的，是单射的，但不满射。ran f=ln1, ln2, 。（3）f 是满射的， 但不是单射的，例如f(1.5)=f(1.2)=1。（4）f 是满射、单射、双射的，因为它是单调函数并且ran f=R。例：(1) 给定无向图G<V,E>，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 给定有向图D=<V,E>，其中 Va,b,c,d， E<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>。 画出G与D的图形。邻域：NG(v1) v2，v5 后继元集：+D(d ) c闭邻域：NG(v1) v1，v2，v5 先驱元集：-D(d ) a，c关联集：IG(v1) e1，e2，e3 邻域： ND(d ) a，c 闭邻域：ND(d ) a，c，dd(v1)4(注意，环提供2度)， 出度：d+(a)4，入度：d-(a)1 4，1， (环e1提供出度1，提供入度1)，v4是悬挂顶点，e7是悬挂边。 d(a)4+15。5，3， +4 (在a点达到)度数列为4,4,2,1,3。 +0(在b点达到) -3(在b点达到)-1(在a和c点达到) 按字母顺序，度数列：5,3,3,3 出度列：4,0,2,1 入度列：1,3,1,2设G<V,E>是n阶m条边的无向图，则下面各命题是等价的：（1）G是树。 （2）G中任意两个顶点之间存在唯一的路径。（3）G中无回路且mn-1。 （4）G是连通的且mn-1。（5）G是连通的且G中任何边均为桥。（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。例题 已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。 解答 设有x片树叶，于是结点总数n1+2+x3+x 由握手定理和树的性质mn-1可知，2m2(n-1)2×(2+x) 1×3+2×2+x解出x3，故T有3片树叶。故T的度数应为1、1、1、2、2、3。求最小生成树的算法（避圈法(Kruskal)）(1)设n阶无向连通带权图G<V,E,W>有m条边。不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大排序：e1,e2,em。(2)取e1在T中。(3)依次检查e2,em ，若ej(j2)与已在T中的边不构成回路，取ej也在T中，否则弃去ej。(4)算法停止时得到的T为G的最小生成树为止。例：求下图所示两个图中的最小生成树。 W(T1)6 W(T2)12 T是n(n2)阶有向树，(1) T为根树 T中有一个顶点入度为0，其余顶点的入度均为1(2) 树根入度为0的顶点(3) 树叶入度为1，出度为0的顶点(4) 内点入度为1，出度不为0的顶点(5) 分支点树根与内点的总称(6) 顶点v的层数从树根到v的通路长度(7) 树高T中层数最大顶点的层数根树的画法：树根放上方，省去所有有向边上的箭头。 树叶8片 内点 6个 分支点 7个 高度 5求带权为1、1、2、3、4、5的最优树。W(T)=38 中序行遍法：b a (f d g) c e 前序行遍法：a b (c (d f g) e) 后序行遍法：b (f g d) e c) a