下载文档原格式
第5章 习题解答5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨分析 S 为n 元集,那么有个元素.S 上的一个二元运算就是函数S S ⨯2n .这样的函数有个.因此上的二元运算有个.S S S f →⨯:2n n },{b a 162=n n 下面说明通过运算表判别二元运算性质及求特导元素的方法.1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律.2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元,,,21n x x x 素的排列也为 则该运算满足幂等律.,,,21n x x x 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立.z y x ,,3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的.e ,,,21n x x x i x 行和列的元素排列顺序也是则为幺元.,,,21n x x x i x 4 ° 零元如果元素所在的行和列的元素都是,则是零元. .θi x i x i x 5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上,,,21n x x x 第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元.i },,2,1{n i x i ∈i x 6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并i x i x 且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两i j j i 个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一j x i x i x 定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没i x i x i x 有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零i x e e e =-1元不是可逆元素.θ以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的,321,,f f f而不是可交换的.再看幂等律.四个运算表表头元素排列都是,其中主对角4f b a ,线元素排列为的只有,所以, 遵从幂等律.下面考虑幺元.如果某元素所b a ,4f 4f 在的行和列元素的排列都是,该元素就是幺元.不难看出只有中的a 满足这b a ,2f 一要求,因此,a 是的幺元,其他三个运算都不存在幺元.最后考虑零元.如果a 2f 所在的行和列元素都是a,那么a 就是零元;同样的,若b 所在的行和列元素都是b,那么b 就是零元.检查这四个运算表,中的a 满足要求,是零元,其他运算都没1f 有零元.在的运算表中,尽管a 和b 的列都满足要求,但行不满足要求.因而4f 4f 中也没有零元.5.2 A:①; B:③; C:⑤; D:⑦; E:⑩分析 对于用解析表达式定义的二元运算 °和 *,差别它们是否满足交换律,结合律,幂等律,分配律和吸收律的方法总结如下:任取,根据 °运算的解析表达式验证等式是否成立.如果成y x ,x y y =x 立 °运算就满足交换律.2 ° °运算的地合律任取根据°运算的解析表达式验证等式是否成立. z y x ,,)y (z y)(z x x =如果成立, °运算就是可结合的.3 ° °运算的幂等律任取x,根据 °运算的解析表达式验证等式是否成立.如果成立, °x x x = 运算满足幂等律.4 ° °运算对*运算的分配律任取,根据 °和*运算的解析表达式验证等式z y x ,,和是否成立。
一、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ．2．设给定图G(如右由图所示)，则图G的点割集是{f，c} ．3．设G是一个图，结点集合为V，边集合为E，则G的结点度数等于边数的两倍．4．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数．5．设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于n-1 ，则在G中存在一条汉密尔顿路．6．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W≤|S|．7．设完全图Kn 有n个结点(n≥2)，m条边，当n为奇数时，Kn中存在欧拉回路．8．结点数v与边数e满足e=v-1 关系的无向连通图就是树．9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4 条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i = 4 ．二、判断说明题（判断下列各题，并说明理由．）1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．不正确，图G是无向图，当且仅当G是连通，且所有结点度数均为偶数，这里不能确定图G是否是连通的。
2．如下图所示的图G存在一条欧拉回路．错误．因为图G为中包含度数为奇数的结点．3．如下图所示的图G不是欧拉图而是汉密尔顿图．解：错，既不是欧拉图也不是汉密尔顿图，欧拉图要求所有结点度数均为偶数，这里结点bd各有三个节点；汉密尔顿图要求每一对结点度数之和大于等于总结点数，这里不满足。
4．设G是一个有7个结点16条边的连通图，则G为平面图．错，没有提到面5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．对，由欧拉定理得到：结点-边+面=2 ，即为连通平面图，这里6-11+7=2三、计算题1．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出其补图的图形．解：（1）G的图形如图十二（2）邻接矩阵：图十二⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡111111111111（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2（4）补图如图十三：2．图G=<V, E>，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．解：（1）G的图形表示如图十四：图十四（2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1111111111111111（3）粗线表示最小的生成树，如图十五如图十五最小的生成树的权为1+1+2+3=7：3．已知带权图G如右图所示．(1) 求图G的最小生成树；(2)计算该生成树的权值．4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．四、证明题1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k 条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数．又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图． 故最少要加2k 条边到图G 才能使其成为欧拉图．。
5.1 一阶逻辑等值式与置换规则定义5.1设A，B是一阶逻辑中任意两个公式，若A B是永真式，则称A与B 是等值的。
记做A B，称A B是等值式。
谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。
下面主要讨论关于量词的等值式。
一、基本等值式第一组代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。
例如：xF(x)┐┐xF(x)x y(F(x,y)→G(x,y))┐┐x y(F(x,y)→G(x,y))等都是(2.1)式的代换实例。
又如：F(x)→G(y)┐F(x)∨G(y)x(F(x)→G(y))→zH(z)┐x(F(x)→G(y))∨zH(z))等都是(2.1)式的代换实例。
第二组消去量词等值式设个体域为有限域D={a1,a2,…,a n}，则有(1)xA(x)A(a1)∧A(a2)∧…∧A(a n)(2)xA(x)A(a1)∨A(a2)∨…∨A(a n) (5.1)第三组量词否定等值式设A(x)是任意的含有自由出现个体变项x的公式，则(1)┐xA(x)x┐A(x)(2)┐xA(x)x┐A(x)(5.2)(5.2)式的直观解释是容易的。
对于(1)式，“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。
对于(2)式，“不存在有性质A的x”与“所有x都没有性质A”是一回事。
第四组量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则(1)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x) (5.3)(2)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x) (5.4)注意：这些等值式的条件。
第五组量词分配等值式设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) (5.5)二、基本规则1．置换规则设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若A B，则Φ(A)Φ(B).一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B 是一阶逻辑公式。
1.自变元与函数值(像源与映像) ：f:X→Y, 如果<x,y>∈f,称x是自变元(像源)，称y是x 的函数值(x的映像) 。
<x,y>∈f⇔ y=f(x) ⇔ f:x→y
2.定义域、值域和陪域(共域)
3.从X到Y函数的集合Y X：Y X={f| f:X→Y}
Y X ：它是由所有的从X到Y函数构成的集合
如果X和Y是有限集合，|X|=m,|Y|=n,因为X中的每个元素对应的函数值都有n种选择，于是可构成n m个不同的函数，因此|Y X|=|Y||X|=n m
4. 两个函数相等
设有两个函数f:A→B g:C→D, f=g 当且仅当A=C，B=D，且对任何x ∈A，有f(x)=g(x)。
即它们的定义域相等、陪域相等、对应规律相同。
5. 函数的类型
1.满射的：f:X→Y是函数，如果R f=Y,则称f 是满射的。
2.映内的：f:X→Y是函数，如果R f⊂Y 则称f 是映内的。
3.入射的：f:X→Y是函数，如果对于任何x1,x2∈X, 如果x1≠x2有f(x1)≠f(x2),(或者若f(x1)=f(x2),则x1=x2),则称f 是入射的，也称f 是单射的，也称f 是一对一的。
4.双射的：f:X→Y是函数，如果f 既是满射的，又是入射的，则称f 是双射的，也称f 是一一对应的。
6. 函数的复合
. 定义: f:X→Y, g:Y→Z是函数,则定义g f ={<x,z>|x∈X∧z∈Z∧∃y(y∈Y∧<x,y>∈f∧<y,z>∈g)}则称g f 为f与g的复合函数(左复合).
注意:这里把g写在f的左边了.所以叫左复合.
g f :X→Z,即g f 是X到Z的函数.这样写是为了照顾数学习惯: g
f(x)=g(f(x))—(函数代入时使用)
7. 函数复合的性质
定理5-2.1满足可结合性。
f:X→Y, g:Y→Z, h:Z→W 是函数,则(h g) f=h (g f)。
定理5-2.2 f:X→Y, g:Y→Z是两个函数, 则
⑴如果f和g是满射的，则g f 也是满射的；
⑵如果f和g是入射的，则g f 也是入射的；
⑶如果f和g是双射的，则g f 也是双射的。
8. ⑴如果g f 是满射的，则g是满射的；
⑵如果g f 是入射的，则f 是入射的；
⑶如果g f 是双射的，则f是入射的和g是满射的。
9.逆函数
定义：设f:X→Y是双射的函数，f C:Y→X 也是函数, 称之为f 的逆函数。
并用f-1代替f C。
f-1存在，也称f 可逆。
显然，f-1也是双射的函数。
10.令f:X→Y, g:Y→X是两个函数,如果g f= I X且f g = I Y ,则g= f-1。
证明：
⑴证f和g都可逆。
因为g f= I X ，I X是双射的，由关系复合性质3得，f是入射的和g是满射的。
同理由f g = I Y，得g是入射的和f 是满射的。
所以f和g都可逆。
⑵显然f-1和g具有相同的定义域和陪域。
⑶证明它们的对应规律相同。
任取y∈Y，f-1(y)= f-1 I Y (y)= f-1 (f g)(y)=(f-1 f) g(y)=(I X g)(y) =g(y)所以f-1 =g
11. 定理5-3.4,令f:X→Y, g:Y→X是两个双射函数,则(g f) -1 =f -1 g-1
12. 集合的特征函数。
