1、基本等值式基本等值式 1.双重否定律双重否定律 A A 2.幂等律幂等律AAA,AAA 3.交换律交换律AB BA， AB BA 4.结合律结合律(AB)C A(BC)(AB)C A(BC) 5.分配律分配律A(BC) (AB)(AC)（对对的分配律）的分配律） A(BC) (AB)(AC)（对对的分配律）的分配律） 6.德德摩根律摩根律(AB) AB(AB) AB 7.吸收律吸收律A(AB) A，A(AB) A 8.零律零律A1 1,A0 0 9.同一律同一律A0 A，A1 A 10.排中律排中律AA 1 11.矛盾律矛盾律AA 0 12.蕴涵等值式蕴涵等值式AB AB 13.等价等值式等价
2、等值式AB (AB)(BA) 14.假言易位假言易位AB BA 15.等价否定等值式等价否定等值式AB AB 16.归谬论归谬论(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) (
3、BC) (AC)假言三段论假言三段论 (7) (AB) (BC) (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
4、的公式，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) BxA(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) BxA(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 规则。规则。 A(c)
5、A(c) xA(x)xA(x) 或或 A(y)A(y) xA(x)xA(x) xA(x)xA(x) A(y)A(y) xA(x)xA(x) A(c)A(c) EI 规则。规则。 ABx|xAxB 、 ABx|xAxB ABx|xAxB 幂集P(A)x | xA 对称差集AB(AB)(BA) AB(AB)(AB) 绝对补集Ax|x A 广义并 Ax | z(zAxz)广义交 Ax | z(zAxz) 设 Aa,b,c,a,c,d,a,e,fBaCa,c,d 则Aa,b,c,d,e,f Ba Cac,d Aa Ba Cac,d 集合恒等式集合恒等式 幂等律幂等律AAAAAA 结合律结合律(AB)C
6、A(BC)(AB)CA(BC) 交换律交换律ABBAABBA A(c)A(c) xA(x)xA(x) 分配律分配律A(BC)(AB)(AC)A(BC)(AB)(AC) 同一律同一律AAAEA 零律零律AEEA 排中律排中律AAE 矛盾律矛盾律AA 吸收律吸收律A(AB)AA(AB)A 德摩根律德摩根律A(BC)(AB)(AC)A(BC)(AB)(AC) (BC)BC(BC)BC EE 双重否定律双重否定律(A)A 集合运算性质的一些重要结果集合运算性质的一些重要结果 AB A，AB B A AB，B AB AB A ABAB ABB A B ABAAB A BB A (A B) CA (B C
7、) A A A A A BA C BC 对偶对偶(dual)式式：一个集合表达式，如果只含有、E、，那么同时把 与互换，把与 E 互换，把与互换，得到式子称为原式的对偶式。 有序对有序对具有以下性质具有以下性质： （1）当 xy 时，。 （2）的充分必要条件是 xu 且 yv。 笛卡儿积的符号化表示为笛卡儿积的符号化表示为AB|xAyB 如果|A|=m,|B|=n,则|AB|=mn。 笛卡儿积的运算性质笛卡儿积的运算性质 (1)对任意集合 A，根据定义有 A, A (2)一般的说，笛卡儿积运算不满足交换律，即 ABBA(当 A B AB 时) (3)笛卡儿积运算不满足结合律，即 (AB)CA(
8、BC)(当 A B C 时) (4)笛卡儿积运算对并和交运算满足分配律，即 A(BC)=(AB)(AC)(BC)A=(BA)(CA) A(BC)=(AB)(AC)(BC)A=(BA)(CA) (5)AC BD AB CD 常用的关系常用的关系 对任意集合 A，定义 全域关系 EA=|xAyA=AA 恒等关系 IA=|xA 空关系 小于或等于关系：LA=|x,yAxy，其中 AR。 整除关系：DB=|x,yBx 整除 y，其中 AZ* ，Z*是非零整数集 包含关系：R|x,yAxy，其中 A 是集合族。 关系矩阵和关系图关系矩阵和关系图 设 A=1,2,3,4，R=,， 则 R 的关系矩阵和关系
9、图分别是 0 00 01 10 0 0 00 00 00 0 1 11 10 00 0 0 00 01 11 1 MMR R 定义域定义域 dom R x | y(R ) 值域值域ran Ry | x(R) 域域fld Rdom R ran R 例 求 R=,的定义域、值域和域。 解答dom R1,2,4ran R2,3,4fld R1,2,3,4 逆逆 R-1|R 右复合右复合 FG | t(FG) 限制限制 RA=|xRyxA 像像 RA=ran(RA) 例 设 R， R1，R R2,3， R12,3R R32 设 F 是任意的关系，则 (1)(F-1)-1F (2)dom F-1ran
10、F，ran F-1dom F 设 F，G，H 是任意的关系，则 (1)(FG)HF(GH) (2)(FG)-1G-1 F-1 设 R 为 A 上的关系，则 R IAIA RR 设 F，G，H 是任意的关系，则 (1) F(GH)FGFH (2) (GH)FGFHF (3) F(GH)FGFH (4) (GH)FGFHF 设 F 为关系，A,B 为集合，则 (1) F(AB)FAFB (2) FABFAFB (3) F(AB)FAFB (4) FABFAFB 关系的幂运算关系的幂运算 设 R 为 A 上的关系，n 为自然数，则 R 的 n 次幂定义为： （1） R0|xAIA （2） Rn+1R
11、n R 幂运算的性质幂运算的性质 设 A 为 n 元集，R 是 A 上的关系，则存在自然数 s 和 t,使得 Rs=Rt。 设 R 是 A 上的关系，m,nN，则 (1)Rm RnRm+n(2)(Rm)nRmn 设 R 是 A 上的关系，若存在自然数 s,t(st)使得 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(xAR)， 反自反反自反 x(xAR)， 对称对称 xy(x,yARR) 反对称反对称 xy(x,yARRx
12、=y)， 传递 xyz(x,y,zARRR) 关系性质的等价描述关系性质的等价描述 设 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 上传递当且仅当 RRR (1)若 R1，R2 是自反的和对称的，则 R1R2 也是自反的和对称的。 (2)若 R1 和 R2 是传递的，则 R1R2 也是传递的。 关系性质的特点关系性质的特点 自反性反自反性对称性反对称性传递性 集合表达式IA RRIARR-1RR-1 IARRR
13、关系矩阵主 对 角 线 元 素全是 1 主对角线元素 全是 0 矩阵是对称矩 阵 若 rij1，且 i j，则 rji0 对 M2 中 1 所 在位置，M 中 相应的位置都 是 1 关系图每 个 顶 点 都 有环 每个顶点都没 有环 如果两个顶点 之间有边，一 定是一对方向 相反的边(无 单边) 如果两点之间 有边，一定是 一条有向边(无 双向边) 如果顶点 xi 到 xj 有边，xj 到 xk 有边，则从 xi 到 xk 也有边 关系的性质和运算之间的关系关系的性质和运算之间的关系 自反性反自反性对称性反对称性传递性 R1-1 R1R2 R1R2 R1R2 R1 R2 闭包的构造方法闭包的构
14、造方法 设 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，如果R，则x与y不交。 （4）x|xAA。
15、 偏序集中的特殊元素偏序集中的特殊元素 设为偏序集，BA，yB。 （1）若x(xByx)成立，则称 y 为 B 的最小元。 （2）若x(xBxy)成立，则称 y 为 B 的最大元。 （3）若x(xBxyxy)成立，则称 y 为 B 的极小元。 （4）若x(xByxxy)成立，则称 y 为 B 的极大元 36 3 24 2 12 6 B上界下界上确界下确界 2,3,6,12,24,36 无无无无 6,1212,24,362,3,6126 2,3,66,12,24,36 无6无 66,12,24,36,2,3,6,66 函数相等函数相等 由定义可知，两个函数 F 和 G 相等, 一定满足下面两个条
16、件： （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,f 1, f 2,f 3, f 4,f 5, f 6,f 7, 设 f:AB， （1）若 ran fB，则称 f:AB 是满射(surjection)的。 （2）若yran f 都存在唯一的 xA 使得 f(x)y，则称 f:AB 是单射(injection)的。 （3）若 f 既是满射又是单
17、射的，则称 f:AB 是双射(bijection) a b c 1 2 3 4 a b c 1 2 3 4d a b c 1 2 3 4d a b c 1 2 3 d 单射双射函数满射 例：判断下面函数是否为单射、满射、双射的，为什么? B最大元 最小元 极大元 极小元 2,3,6,12,24,36 无无24，36 2,3 6,12126126 2,3,66无62,3 66666 (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。既不
18、是单射也不是满射的。 （2）f 是单调上升的，是单射的，但不满射。ran f=ln1, ln2, 。 （3）f 是满射的， 但不是单射的，例如 f(1.5)=f(1.2)=1。 （4）f 是满射、单射、双射的，因为它是单调函数并且 ran f=R。 例：(1) 给定无向图 G，其中 Vv1,v2,v3,v4,v5， E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 给定有向图 D=，其中 Va,b,c,d， E,。 画出 G 与 D 的图形。 邻域：NG(v1) v2，v5后继元集：+D(d ) c 闭邻域：NG(v1
19、) v1，v2，v5先驱元集：-D(d ) a，c 关联集：IG(v1) e1，e2，e3邻域：ND(d )a，c 闭邻域：ND(d )a，c，d d(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是 n 阶 m 条边的无向图，则下面
20、各命题是等价的： （1）G 是树。（2）G 中任意两个顶点之间存在唯一的路径。 （3）G 中无回路且 mn1。（4）G 是连通的且 mn1。 （5）G 是连通的且 G 中任何边均为桥。 （6）G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一 个含新边的圈。 例题 已知无向树 T 中，有 1 个 3 度顶点，2 个 2 度顶点，其余顶点全是树叶，试求树叶数， 并画出满足要求的非同构的无向树。 解答 设有 x 片树叶，于是结点总数 n1+2+x3+x 由握手定理和树的性质 mn1 可知， 2m2(n1)2(2+x) 13+22+x 解出 x3，故 T 有 3 片树叶。
21、故 T 的度数应为 1、1、1、2、2、3。 求最小生成树的算法（避圈法(Kruskal)） (1)设 n 阶无向连通带权图 G有 m 条边。不妨设 G 中没有环（否则，可以将所有 的环先删去） ，将 m 条边按权从小到大排序：e1,e2,em。 (2)取 e1 在 T 中。 (3)依次检查 e2,em ，若 ej(j2)与已在 T 中的边不构成回路，取 ej 也在 T 中，否则弃去 ej。 (4)算法停止时得到的 T 为 G 的最小生成树为止。 例：求下图所示两个图中的最小生成树。 W(T1)6W(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
