资源描述：
《离散数学 ( 第3次 ).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3次作业一、填空题（本大题共20分，共10小题，每小题2分）1.是否可以画出一个简单的无向图，使得各点度数与一下序列一致。（T or F）（1）2，2，2，2，2，2； （）（2）2，2，3，4，5，6； （） (3) 1，2，3，4，4，5； （）2.在根树中，若从Vi到Vj可达，则称Vi是Vj的____________，Vj是Vi的__________3.设A={a,b},B={1,2,3}，判断下列集合是否是A到B的函数。F_1={〈a,1〉,〈b,2〉}, F_2={〈a,1〉,〈b,1〉}， F_3={〈a,1〉,〈a,2〉}, F_4={〈a,3〉}4.用列元
2、法表示下列集合A={x
3、x∈N且x^2≤9}，则可表示为（ ）。5.设X={a,b,c,d},Y={1,2,3,4,5}，且有f={,,,}，则domf为（ ）、R_f为 和f(x)为（ ）。6.判断下列命题正确与否：(1)正整数集N上的小于等于关系“≤”是良序关系。（ ）（2）In={1,2,…,n}上的小于等于关系“≤”是良序关系。（ ） (3)整数集Z和实数集R上的小于等于关系“≤”是良序关系。（ ）7.在由n个元素组成的集合上，可以有（ ）种不同的二元关系？若集合A,B的元数分别为
4、A
5、=m,
6、B
7、=n,试问从A
8、到B有( )种不同的二元关系？8.设R_1和R_2是集合A上的二元关系，试判断下列命题是否正确？( )( )( )9.设R_1和R_2是非空集合A上的等价关系，下列各式哪些是A上的等价关系？哪些不是A上的等价关系？举例说明：⑴A×A-R_1；( ) ⑵R_1-R_2；( )⑶R_1^2； ( ) ⑷r(R_1-R_2)； ( )⑸R_1∙R_2 ( )10.对下述论断判断正确与否，在相应括号中键入“Y”或“N”。设A={2,3,6,12,24,36}，A上的整除关系是一偏序关系，用“≤”表示。 (a）该偏序关系的哈斯图是（ ）（b)“≤”={〈2,2〉,〈2,6〉
9、,〈3,3〉,〈3,6〉,〈6,6〉,〈6,12〉,〈12,12〉,〈12,24〉,〈24,24〉,〈36,36〉} （ ） 二、计算题（本大题共40分，共4小题，每小题10分）1.试将公式化成等价的前束范式：∀xF(x)→∃xQ(x)；2.z)R(x，y，z))"z)Q(x，z)∨(∀"x)((∀$∀x)P(x)→(∃"求等价于下面wff的前束合取范式与前束析取范式：(3. 试将公式P∧（P→Q）化为析取范式和合取范式：4. 设f：R→R，f（x）=x^2-2；g：R→R，g（x）=x+4。 (1)求g°f，f°g (2)问g°f和f°g是否为单射、满射、双射？ （3）求出
10、f、g、g°f和f°g中的可逆函数的逆函数。三、简答题（本大题共20分，共4小题，每小题5分）1.设G是有两个奇度点的连通图,设计一个构造G的欧拉道路的算法。2.设X={2,3,4,5}，求集合上的关系“<”、dom<及ran<。3.设A={1,2,3,4,5},R={<1,2>,<1,5>,<2,2>,<3,2>,<3,1>,<4,3>}，画出R的关系图。4.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>}，S={<4,2>,<2,5>,<3,1>,<1,3>，求R°S和S°R的矩阵。四、证明题（本大题共20分，共2小题，每
11、小题10分）1.证明:∀x∀y(P(x)→Q(y))=∃xP(x)→∀yQ(y)2.设是一个代数系统，*是R上的一个二元运算，使得对于R中的任意元素a,b都有a*b=a+b+a∙b,试证明：0是幺元且是独异点。答案：一、填空题（20分，共10题，每小题2分）1.参考答案：（1）T （2）F （3）F解题方案：评分标准：2.参考答案：祖先；后代解题方案：评分标准：3.参考答案：F_1,F_2是函数，F_3,F_4不是函数。解题方案：若不强调是A到B的函数，则F_4是函数，其定义域为{a}。评分标准：4.参考答案：{1,2,3}解题方案：评分标准：5.参考答案：{
12、a,b,c,d} {1,3,4} f(a)=1,f(b)=3,f(c)=4,f(d)=4解题方案：评分标准：6.参考答案：正确 正确 错误解题方案：整数集Z和实数集R上的小于等于关系“≤”不是良序关系(因为Z或R本身无最小元)。评分标准：7.参考答案：2^(n^2) 2^(m×n) 解题方案：评分标准：8.参考答案：（1）命题正确（2）命题正确（3）命题不正确解题方案：评分标准：9.参考答案：（1）不是 （2）不是（3）是（4）不是 （5） 是解题方案：评分标准：10.参考
