离散数学公式.pdf

《离散数学公式.pdf》由会员分享，可在线阅读，更多相关《离散数学公式.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基本等值式 1、双重否定律A 2。幂等律 AA,A A 3。交换律AB BA,AB BA 4、结合律 (AB)C A(BC)(A)C A(BC)5、分配律 (C)(AB)(AC)(对得分配律)(BC)(AB)(C)(对得分配律)6、德摩根律 ()AB (AB)AB 7、吸收律 A(A)A,A()A 8。零律 1 1,0 9、同一律 A A,A1 A 0、排中律 A 11、矛盾律 A 0 12。蕴涵等值式 AB AB、等价等值式 AB (AB)(BA)14、假言易位 AB BA 5。等价否定等值式 A B 16、归谬论 (AB)(AB)A 求给定公式范式得步骤 (1)消去联结词、(若存在)。()

2、否定号得消去(利用双重否定律)或内移(利用德摩根律)、(3)利用分配律:利用对得分配律求析取范式,对得分配律求合取范式。推理定律-重言蕴含式(1)(A)附加律(2)(A)A 化简律(3)(AB)A B 假言推理(4)(A)B A 拒取式(5)(AB)B 析取三段论 (6)(AB)(C)(AC)假言三段论(7)(A)(BC)(A C)等价三段论(8)(B)(CD)(C)(BD)构造性二难(AB)(AB)(AA)B 构造性二难(特殊形式)()(AB)(C)(BD)(C)破坏性二难 设个体域为有限集 Da,a2,an,则有(1)A(x)(a1)A(2)(an)(2)xA()A(a)A(2)A(an)

3、设 A(x)就是任意得含自由出现个体变项 x 得公式,则(1)x(x)A(x)()xA(x)xA(x)设 A()就是任意得含自由出现个体变项得公式,B 中不含得出现,则(1)x(A()B)xA(x)B x(A(x)B)xA(x)x(A(x)B)xA(x)B x(BA(x)BxA(x)(2)x(A()x(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)xA(x)设(x),()就是任意得含自由出现个体变项得公式,则()x(x)B(x)x()()(2)(x)B(x)(x)xB()全称量词“”对“”无分配律。存在量词“”对“”无分配律。UI 规则。UG 规则、E规则。

4、EI 规则。ABxxAB 、ABx|xAB A-xxAxB 幂集 P()|A 对称差集 A(-B)(B)A=(AB)(AB)绝对补集 x|x A 广义并 A=x z(zAxz)广义交 Ax z(A)设 A=a,b,a,c,e,a C,d 则 A=a,c,d,f Ba C=ac,a B=a Cac,d 集合恒等式 幂等律 AAA AA 结合律 (AB)A(C)(A)C=(BC)交换律 ABA AB=B 分配律 A(C)(AB)()(BC)=(AB)(C)同一律 AEA 零律 AEE 排中律 AA=E 矛盾律 AA 吸收律 A(A)=A A(AB)=A 德摩根律 (BC)(A-B)(AC)A-(B

5、C)=(-B)(A)(BC)BC (B)BC =E 双重否定律(A)A 集合运算性质得一些重要结果 BA,ABB AAB,AB ABA AB=AB AB AB A-B BBA (AB)C=A(BC)A=A AA AAC C 对偶(dual)式:一个集合表达式,如果只含有、E、=、,那么同时把与互换,把与 E 互换,把与互换,得到式子称为原式得对偶式、有序对x,y具有以下性质:(1)当 x时,x,yy,、(2)xAB 如果|m,|B|=,则AB|=n。笛卡儿积得运算性质 (1)对任意集合 A,根据定义有 A,A=(2)一般得说,笛卡儿积运算不满足交换律,即 ABBA (当 B AB 时)(3)笛

6、卡儿积运算不满足结合律,即 (AB)CA(B)(当 B C 时)(4)笛卡儿积运算对并与交运算满足分配律,即 A(B)=(B)(AC)(BC)=(BA)(C)A(B)=(AB)(AC)(C)=(A)()(5)B B D 常用得关系 对任意集合 A,定义 全域关系 EA=x,y|xA=AA 恒等关系 IA=|xA 空关系 小于或等于关系:LA=,yx,yAy,其中 AR。整除关系:B=x,y,yBx 整除 y,其中 AZ,Z就是非零整数集 包含关系:R=x,yAx,其中 就是集合族。关系矩阵与关系图 设 1,2,3,=1,1,1,2,2,2,4,则 R 得关系矩阵与关系图分别就是 定义域 om

7、R x y(,yR)值域 ran R=y x(,1,2,4,得定义域、值域与域。解答dom R=1,2,4 r,3,4 fl=1,2,3,4 逆 R-1x,yy,xR 右复合 FG=x,t(x,tt,G)限制 R=|xA 像 RA=ran(RA)例 设 R,1,3,2,2,4,2 1=1,2,1,3 2,3=,2,4,2 1=2,3 R=R3=2 设 F 就是任意得关系,则 ()(F1)=F (2)do F1=r F,rn 1=om F 设 F,G,H 就是任意得关系,则(1)(G)=(H)(2)(FG)1G1 F-1 设 R 为 A 上得关系,则 R IA=I R=R 设 F,G,H 就是任

8、意得关系,则(1)F(GH)FF(2)(GH)F=GFHF()F(G)FGFH4()GH)FGFHF 设 F 为关系,A,B 为集合,则(1)F(AB)=FFB (2)AB=AFB (3)F(AB)=A (4)FABFAF 关系得幂运算 设 R 为上得关系,n 为自然数,则得 n 次幂定义为:(1)R0=x,xAIA )2(Rn+n R 幂运算得性质 设 A 为元集,R 就是 A 上得关系,则存在自然数与 t,使得 Rs=Rt。设 R 就是 A 上得关系,m,nN,则(1)R Rn=Rm+n (2)(Rm)mn 设 R 就是 A 上得关系,若存在自然数 s,t(st)使得 R=R,则(1)对任

9、何 kN 有 s+k=k(2)对任何 k,N 有 Rs+k+i=+,其中=s(3)令,R1,t1,则对于任意得 qN 有 RqS 自反(xAx,),反自反(xAx,x),对称 xy(,x,yRy,xR)反对称 y(,yARy,xx=y),传递 xyz(,y,zAx,yy,R)关系性质得等价描述 设 R 为 A 上得关系,则(1)在 A 上自反当且仅当 I R(2)R 在上反自反当且仅当 IA=(3)R 在上对称当且仅当 R=1(4)R 在上反对称当且仅当 RR1 IA()R 在 A 上传递当且仅当 RR (1)若 R1,R2 就是自反得与对称得,则1R也就是自反得与对称得。(2)若 R1 与

10、R就是传递得,则 R12 也就是传递得。关系性质得特点 自反性 反自反性 对称性 反对称性 传递性 集合表达式 I R RA=1 RR1 A RRR 关系矩阵 主对角线元素全就是 1 主对角线元素全就是 0 矩阵就是对称矩阵 若 rij=1,且 i,则 ri0 对 M中所在位置,M 中相应得位置都就是 1 关系图 每个顶点都有环 每个顶点都没有环 如果两个顶点之间有边,一定就是一对方向 相 反 得 边(无单边)如果两点之间有边,一定就是一条有向边(无双向边)如果顶点 xi 到x有边,j 到k 有边,则从xi 到 x也有边 关系得性质与运算之间得关系 自反性 反自反性 对称性 反对称性 传递性

11、R1 R1R2 R1R2 R1R2 R1 R2 闭包得构造方法 设 R 为 A 上得关系,则有)1(自反闭包 r(R)RR0 ()对称闭包(R)RR-1 (3)t(R)RR2R3 关系性质与闭包运算之间得联系 设 R 就是非空集合 A 上得关系,()若 R 就是自反得,则()与 t(R)也就是自反得。()若 R 就是对称得,则 r(R)与()也就是对称得。)3(若 R 就是传递得,则 r(R)就是传递得。等价类得性质 设就是非空集合上得等价关系,则(1)xA,x就是 A 得非空子集。()x,yA,如果 xy,则xy。(3)x,y,如果,则x与不交。()A=A、偏序集中得特殊元素 设为偏序集,A

12、,yB。()若x(xByx)成立,则称 y 为 B 得最小元。(2)若(xBxy)成立,则称 y 为得最大元。(3)若(xx=y)成立,则称为 B 得极小元、(4)若x(yx=)成立,则称 y 为 B 得极大元 B 上界 下界 上确界 下确界 ,3,6,12,4,36 无 无 无 无 6,12 2,24,2,2,6 6,2,24,36 无 6 无 6 6,12,24,6,2,6,6 6 函数相等 由定义可知,两个函数与相等,一定满足下面两个条件:(1)dom F=dom G ()xdom F=dom,都有(x)=G()所有从 A 到 B 得函数得集合记作 BA,读作“B 上”,符号化表示为 B

13、A=f f:AB。例:设 A,2,3,Ba,b,求 BA。A 0,f1,f3,f,f5,f,f、其中 f 1,a,2,a,a =,2,a,f 2=,2,b,3,a f 3,a,2,b,3,f 1,b,2,a,5=1,b,2,a,f 6=1,2,3,a f 7=1,设 f:AB,()若 ra f=B,则称 f:AB 就是满射(surjecion)得、(2)若yran f 都存在唯一得 xA 使得 f(x)y,则称 f:AB 就是单射(inection)得、(3)若 既就是满射又就是单射得,则称 f:就是双射(bijecton)B 最大元 最小元 极大元 极小元 2,12,24,36 无 无 24

14、,36 2,3 6,12 12 6 1 6 2,3,6 6 无 6 ,3 6 6 6 6 36 3 24 2 12 6 单射 双射 函数 满射 例:判断下面函数就是否为单射、满射、双射得,为什么？(1)f:R,f(x)=x+2x1 (2)f:Z+R,f()ln,Z+为正整数集(3)f:R,f()=x (4)f:RR,f(x)=2x1。解(1)f 在=取得极大值 0。既不就是单射也不就是满射得。(2)f 就是单调上升得,就是单射得,但不满射。n f=,ln2,。()f 就是满射得,但不就是单射得,例如 f(。)=f(1、2)=1、()f 就是满射、单射、双射得,因为它就是单调函数并且 rn f=

15、R。例:()给定无向图 G=V,E,其中 V=v1,v2,v3,v,5,=(1,1),(v1,v2),(v,3),(,v3),(v,v5),(v,v5),(v,v5)。(2)给定有向图=V,E,其中 V=a,b,c,d,b,a,d,c,d,c,b。画出 G 与 D 得图形、邻域:G(v)=v2,v 后继元集:+D()=c 闭邻域:G(v1)v1,v2,v5 先驱元集:D(d),c 关联集:I(1)=,2,邻域:N(d)=,c 闭邻域:D()=a,c,(v1)4(注意,环提供度),出度:d+(a)=4,入度:d(a)=1,4=1,(环 e1 提供出度 1,提供入度 1),v4 就是悬挂顶点,e7

16、 就是悬挂边、d(a)=4+=5、5,3,(在点达到)度数列为 4,4,1,。+0(在 b 点达到)3(在点达到)1(在 a 与 c 点达到)按字母顺序,度数列:5,3,3 出度列:4,0,2,1 入度列:1,3,1,2 设 G就是 n 阶 m 条边得无向图,则下面各命题就是等价得:a b c 1 2 3 d a b c 1 2 3 4 a b c 1 2 3 4 d a b c 1 2 3 4 d(1)G 就是树。(2)G 中任意两个顶点之间存在唯一得路径。(3)中无回路且 m1、(4)G 就是连通得且 m1、(5)G 就是连通得且 G 中任何边均为桥、(6)G中没有回路,但在任何两个不同得

17、顶点之间加一条新边,在所得图中得到唯一得一个含新边得圈、例题 已知无向树 T 中,有 1 个 3 度顶点,2 个 2 度顶点,其余顶点全就是树叶,试求树叶数,并画出满足要求得非同构得无向树、解答 设有 x 片树叶,于就是结点总数=12+x+x 由握手定理与树得性质 mn可知,2m(n)2(+x)+2+1=x 解出 x=3,故 T 有 3 片树叶。故 T 得度数应为 1、1、2、3。求最小生成树得算法(避圈法(Krusl)()设 n 阶无向连通带权图 G,W有 m 条边。不妨设 G 中没有环(否则,可以将所有得环先删去),将 m 条边按权从小到大排序:e1,e2,em。(2)取 e1 在 T 中

18、。(3)依次检查 e2,em,若 ej(j2)与已在 T 中得边不构成回路,取 ej 也在中,否则弃去 ej。(4)算法停止时得到得 T 为 G 得最小生成树为止。例:求下图所示两个图中得最小生成树、(T1)=6 W()=12 T 就是 n(2)阶有向树,()T 为根树-T 中有一个顶点入度为,其余顶点得入度均为 1(2)树根-入度为 0 得顶点(3)树叶入度为 1,出度为 0 得顶点(4)内点-入度为 1,出度不为 0 得顶点(5)分支点树根与内点得总称(6)顶点 v 得层数从树根到得通路长度(7)树高T 中层数最大顶点得层数 根树得画法:树根放上方,省去所有有向边上得箭头。树叶片 内点-个 分支点-7 个 高度-求带权为 1、1、3、4、5 得最优树。()=38 中序行遍法:b a(f d g)e 前序行遍法:b(d f g)e)后序行遍法:b(f g d)e c)