计算机数学基础（1）07秋综合练习（三）_计算机_期末大练兵__电大在线

1、计算机数学基础（1）07秋综合练习（三） 三、化简计算题 1作命题公式的真值表，并判断该公式的类型解：命题公式的真值表PQP®Q001000011000100011111111 原式为可满足式. 2判断命题公式的类型(重言式、矛盾式或可满足式)解： 所以是矛盾式(永假式) 3设谓词公式，试写出量词的辖域，并指出该公式的自由变元和约束变元解：$x的辖域是：P(x,y)®"zQ(y,x,z)；"z的辖域是：Q(y,x,z)； "y的辖域是：R(y,x) 公式的自由变元是：y,z；约束变元是：x,y,z 4 化简集合表达式：(AÈB

2、0;C)Ç(AÈB)(BÈ(BC)A) 解： (AÈBÈC)Ç(AÈB)(BÈ(BC)A)(AÈB)(BA) (3分) =(AÈB)Ç(BÈA) (5分) =AÈ(BÇB)=AÈÆ=A 5设集合Aa,b,c,d，在A上定义二元关系R<a,a>,<a,d>,<b,b>,<b,c>,<c,b>,<c,c>,<d,a>,<d,d>R是否为等价关系，

3、说明理由. 解： R含有<a,a>,<b,b>,<c,c>,<d,d>, 是自反的； R含有<a,a>,<b,b>,<c,c>,<d,d>,<a,d>,<d,a>,<b,c>,<c,b>, 是对称的；可以验证，对，是传递的. 故R是A上的等价关系. ab c f d e<A,R>的哈斯图 6：偏序集<A, R>的哈斯图如下图所示： 试写出A和R的集合表达式并求A的极大元和最大元解：A=a,b,c,d,e,f(2分) R=<

4、b,a>,<d,b>,<d,a>,<d,c>,<c,a>, <e,c>,<e,a>ÈIA (5分) A的极大元：a,f；最大元：无v5 d v4v1v2 v3图Ge f n ca h g b7图G(如下图)能否一笔画出？说明理由. 若能画出，请写出一条通路或回路. 解：因为图中 (v1)=2, (v2)=(v3)=(v4)=(v5)=4,无奇数度结点，图G是欧拉图，故能一笔画出. 一条欧拉回路为：v5e v1a v2hv4c v3g v5f v2b v3n v4d v5 (不惟一) 8指出有向图D中各图是强

5、连通，单侧连通还是弱连通？(1)(2)(3)(4)(5)图D解：强连通图为：图(1),(4),(5)；单侧连通图为：图(2),(4),(5)，或图(2)；弱连通图为：图(3),(2),(4),(5)，或图(3) 9给定三个图如下图所示，试判断它们是否为欧拉图、哈密顿图、或平面图？并说明理由 a b c d e f g 图G1 图G2 图G3 解： 图G1是欧拉图，因为每个结点度数均为偶数 图G2是哈密顿图，存在哈密顿回路，如cdgfebac(不惟一) 图G3是平面图可以改画成可平面图，如下图 平面图 10(1)在1棵有2个2度结点，4个3度结点，其余为树叶的无向图中，应该有几片树叶？(2) 画

6、出两棵不同构的满足条件(1)的结点度数的无向树T1，T2解：(1)设有k片树叶，则该树有k+2+4个结点，根据树的等价定义，有k+5条边由握手定理，2×(k+5)=k+2×2+4×3k+16,故k=6即有6片树叶 (2) 非同构的树如下图 T1 T2 两个非同构树图 11设代数系统(Z，+，×)，已知(Z，×)是半群，验证(Z，+，×)是环解：只需验证(Z，+)是交换群易验证整数具有结合律，交换律0是加法的单位元"kÎZ，$(k)ÎZ，有k+(k)=(k)+k=0Z中每个元素有逆元故(Z,+)是交换群所以

7、(Z,+,×)是环 12化简布尔表达式. 解： 13求命题公式的主合取范式. 解： 14求命题公式的真值表. 解：作真值表P Q PÙQØPØQØPÚØQ(PÙQ)Ù(ØPÚØQ)00 0 1 1 1 001 0 1 0 1 010 0 0 1 1 011 1 0 0 0 0 15求谓词公式的真值其中P：4>3，Q（x）：x>1，R（x）：x£2f（-3）=1，f（1）=5，f（5）= -3a：5个体域D=（-3，1，5）解：= = 16求谓词公式的前束

8、范式解： (2分) (4分) (6分) (8分) (或) 17设，求：(AÇB)ÈC，P(A)P(B)，AÅB解：(AÇB)ÈC=1È AÅB =(AÈB)（AÇB）= 18设集合Xa,b,c,d,X上的二元关系R的关系图如下图所示ah hdbh hcR的关系图试写出R的表达式和关系矩阵 解：R<a,a>,<a,c>,<b,c>,<d,d> 19设偏序集<A,R>的哈斯图如下：4 62 35 1 <A,R>哈斯图求偏序关系R的集合表达

9、式和A的子集合B=2,3,6的极大元、极小元、最大元和最小元解：R=IAÈ<1,2>,<2,4>,<1,4>,<2,6>,<1,6>,<1,3>,<3,6>B的极大元和最大元：为6；极小元为2,3；最小元：无v4 h h v3v1 h h v2 图D 20已知有向图D(如下图)的邻接矩阵为 A(D)=求从v2到v4长度为2和从v3到v3长度为2的通路条数，并将它们具体写出.解答：. A2(D)= 从矩阵A2(D)中a24=2,a33=2可知， 从v2到v4长度为2的通路有2条. 它们是：v2v3v4,

10、和v2v1v4, 从v3到v3长度为2的通路有2条. 它们是：v3v4v3,和v3v2v3, 21设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3求G中有多少个结点试作一个满足该条件的简单无向图解：设图G有x个结点，有握手定理 2´1+2´2+3´4+3´（x-2-2-3）12´2 x9图G有9个结点 简单无向图作图如下图 22设无向图G如下图，说明图G是哈密顿图，并求一条哈密顿回路 e f无向图Gc dab解：这是6阶图，每个结点的度数为3，任意不相邻结点度数之和大于或等6，故图G是哈密顿图一条哈密顿回路为：acebfda 23已知带权图G，如下图所示试求图G的最小生成树，并计算该生成树的权 · 1 9 2· 8 · 7 · 4 · 3 · 图G5 610解：做法如下：选边1； 选边2；选边3； 选边5； 选边7 · 1 9 2· 8 ·