离散数学-2005`2006(2)-试卷b

《离散数学-2005`2006(2)-试卷b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、基础知识（40分）1．判断下列句子是否是命题，若是命题将其符号化。（4分）①.李平不是不聪明，而是不用功。②.如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。2．在一阶逻辑中将下列命题符号化。（4分）①.整数都是有理数，并不是每个有理数一定是整数，有些有理数不是整数。②.某些汽车比所有的火车慢。3．求下列集合的幂集。（4分）①.A={Æ,{Æ},{{Æ}}}②.B={{a,b},{c}}4．设A={1,2,3}，求A上所有的等价关系。（6分）5．设集合A={1,2,3,4}，关系R={<1,2>,<2,1>,<2,3>,<3,4>

2、}，分别求r(R)，s(R)，t(R)。（6分）6．一棵树有两个顶点度数为2，一个顶点度数为3，三个顶点度数为4，问它有几个度数为1的顶点。（4分）7．设有无向图G如下所示，判断图G是是否是欧拉图和哈密顿图。若是，分别求出一条欧拉回路和哈密顿回路．（4分）8．设有代数系统(Z,*)，运算*的定义为：任意x,y∈Z，x*y＝x+y-2，试证(Z,*)是群。（8分）二、理解运用（30分）9．判断命题公式的类型。（6分）10.求下列命题公式的主析取范式和所有成假赋值。（6分）11.求谓词公式的前束范式。（6分）12.画出集合A={1,2,3,4,

3、6,8,12,24}关于整除关系的哈斯图。并求(1)集合A的最大元、最小元、极大元和极小元；(2)集合B＝{4,6}的上界、下界、最小上界、最大下界。（6分）13.求下面带权图的最小生成树及权（6分）三、综合能力（30分）11.请用一阶逻辑推理理论证明以下推理：每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家。(10分)12.某班学生50人，会FORTRAN语言的有40人，回ALGOL语言的35人，会C语言的10人，以上三门语言都会的5人，都不会的没有，问只会两门语言的有几人？(10分)13.有向图G=

4、如下图所示，分别求:(1)G中v1到v4的长度为3、长度为4的通路条数。(2)G中长度不超过4的通路总数。（10分）答案及评分参考（B卷）1.①是命题(1分)。用p表示“李平聪明”，q表示“李平用功”，则符号化为﹁(﹁p)∧﹁q。(1分)②是命题(1分)。可表示为(q→p)→┐q，其中p：我懂得希腊文，q：我了解柏拉图(1分)2.①设I(x)：x是整数，Q(x)：x是有理数。则原句可符号化为：(2分)②令：是火车。：是汽车。：比快。则有或者；(2分)3.①(2分)②ρ(B)={φ,{{a,b}},{{c}},{{a,b},{c}}}(2分)

5、4.先求A的所有划分：只有1个划分块的划分，具有两个划分块的划分，和，具有3个划分块的划分，如下图。(2分)设对应于划分的等价关系为，则有；(1分)；(1分)；(1分)；(1分)。(1分)5.r(R)={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,4>}(2分)s(R)={<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}(2分)t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<1,1>,<2,2>,<1,3>,<2,4>,<1,4>}(2分)6.设有x个度数为

6、1的结点，结点数v＝2+1+3+x＝6+x，边数e＝v-1=5+x。而2e＝∑deg(vi)，(2分)故2(5+x)=2·2+1·3+3·4+x·1，x＝9。(2分)7.图G不是欧拉图，是哈密尔顿图(2分)。哈密顿回路为。(2分)（答案不唯一）8.证明：任意x,y,z∈Z，有(x*y)*z＝(x+y-2)*z＝x+y+z-4x*(y*x)＝x*(y+z-2)＝x+y+z-4∴*满足结合律。(2分)任意x∈Z，有x*2＝x+2-2＝a,2*x＝x，∴单位元是2。(3分)任意x∈Z，有(4-x)*x＝(4-x)+x-2＝2，∴a的逆元是4-x。

7、(3分)综上，根据群的定义可知，代数系统(Z,*)是群。9.解：(1分)(1分)(1分)(1分)(1分)所以，该命题公式为永真式。(1分)(注：此题判断方法不唯一，用其他方法也可)10．解：(3分)A的所有成假赋值为000，001,010,100，101，110,111。(3分)11.(3分)(3分)12.哈斯图如下：(2分)(1)集合A的极小元、最小元是1，极大元、最大元是24。(2分)(2)集合B的上界是12,24，下界是2,1，最小上界是12，最大下界是2。(2分)13.所求最小生成树如下图所示(3分)W(T)=40(3分)14.解：

8、首先将命题符号化，个体域为全总个体域。：是学术会成员。：是专家。：是工人。：是青年人。(2分)前提：，。结论：。(2分)下面进行证明：(6分)①前提引入②①EI③前提引入④③UI