离散数学 ( 第3次 )

第三项任务一、填空(共20分，共10项，每项2分)1.是否可以画一个简单的无向图，使每个点的度数与下面的顺序一致。(T或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是_ _ _ _ _ _ _ _ _ _ _ _3.设A=a，b，B=1，2，3，判断下列集合是否为A到B的函数f1=a，1 uu, b，2 uu,F2= a，1 u, b，1 u,F3= a，1 u, a，2 u,f _ 4= a，3 uu4.下列集合A=x|xN且x 2 9可表示为()。5.如果X=a，b，c，d，Y=1，2，3，4，5，f=，则dom f为()，R_f为()，f(x)为()。6.判断下列命题是否正确：(1)正整数集合上小于或等于“”的关系是一种有序关系。()(2)in= 1，2，n是一个有序的关系。()(3)整数集Z与实数集R之间的小于或等于关系“”是一种有序关系。()7.在一组n个元素上，可以有()种不同的二元关系？如果集合a和b中的元素数分别是| a |=m和| b |=n，那么a和b之间怎么会有()种不同的二元关系呢？8.设R1和R2是集合A上的二元关系，并试着判断下列命题是否正确。() ()9.设R1和R2在非空集A上是等价关系，下列哪一个是A上的等价关系？在A上哪些是不等价的关系？例如：AA-R1；R1-R2；()r_12；R(R1-R2)；()R1R2()10.要判断下列陈述是否正确，请在相应的括号中键入“y”或“n”。设A=2，3，6，12，24，36，A上的可分关系是偏序关系，用“”表示。偏序关系的哈斯图是()(b)= 2，2 u, 2，6 u, 3，3 u, 3，6 u, 6，6 u, 6，12,12，12,12，24,24，二、计算题(此大题共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(PQ)转化为析取范式和合取范式；4.设f:RR r，f(x)=x2-2；g:RR，g(x)=x 4 .(1)查找gf，fg(2)询问gf和fg是否为单发、全发、双发？(3)求F，G，gf和fg中可逆函数的反函数。3.简短回答问题(这个主要问题20分，4个项目，每个项目5分)1.设G是一个有两个奇数度点的连通图，并设计了一个构造G的欧拉路的算法2.让X=2，3，4，5，并找到关系 dom并在集合上运行。3.让A=1，2，3，4，5，R=1，2，1，5，2，2，3，2，3，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，求RS和Sr的矩阵4.证明(本主题20分，2项，每项10分)1.证明3336xy (p (x) q (y)=xp (x) yq (y)2.假设*是一个代数系统和一个关于R的二元运算，所以对于R中的任何元素A和B，都有A *回答：一、填空(20分，共10道题，每题2分)1.参考答案：(1)T (2)F (3) F解决方案计划：评分标准：2.参考答案：祖先；产物解决方案计划：评分标准：3.参考答案：f1，F2是函数，F3，F4不是函数。解决方案计划：如果不强调从a到b的函数，那么F4就是一个函数，它的定义域是a。评分标准：4.参考答案：1，2，3解决方案计划：评分标准：5.参考答案：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(n2 ) 2(mn)解决方案计划：评分标准：8.参考答案：(1)命题是正确的(2)命题是正确的(3)命题不正确解决方案计划：评分标准：9.参考答案：(1)不(2)不(3)是(4)不是(5)是解决方案计划：评分标准：10.参考答案：Y N解决方案计划：评分标准：二、计算题(40分，共4题，每题10分)1.参考答案：xf(x)xq(x)=xf(x)xq(x)=xf(x)xq(x)=x(f(x)q(x)解决方案计划：评分标准：2.参考答案：z)r(x,y,z)z)q(x,z)(x)($x)p(x)(z)r(x,y,z)z)q(x,z)(x)($x)p(x)(u)r(x,y,u)z)q(x,z)(x)($x)p(x)($(u)r(x,y,u)z)q(x,z)(x)(p(x)($(u)(p(x)q(x，z)r(x，y，u) z) (x) ($(趾合取范式u)(p(x)q(x，z)r(x,y,u)(p(x)q(x，z)r(x,y,u)(p(x)q(x,z)r(x,y,u)(p(x)q(x,z)r(x,y,u)(p(x)q(x，z)r(x，y，u)(p(x)q(x，z)r(x，y，u)p(x)q(x，z)r(x，y，u)z ( x )($(toe析取范式)解决方案计划：评分标准：3.参考答案：(PQ)(PQ)=(pq )(pq)(pq )(pq)(等价定律)=(pq)(pq)(pq)(pq)(pq)(蕴涵定律)=(pq)(pq)(分布律)合取范式=(pp)(pq)(qp)(qp)(qq )(分布律)析取范式解决方案计划：评分标准：4.参考答案：(1)fg=x,x2 8x 14| xr gf=x,x2 2| xr (2)gf和fg都是非单一的和非完全的功能。(3)因为g是双射的，它是可逆的，它的反函数是：g (-1) (x)=x-4。解决方案计划：评分标准：三、简答题(20分，共4道题，每题5分)1.参考答案：步骤1:添加连接两个奇数点的边步骤2:调用通用欧拉路径算法步骤3:删除循环中添加的边解决方案计划：评分标准：2.参考答案：=2，3，2，4，2，5，3，4，3，5，4，5dom2，3，4ran3，4，5解决方案计划：评分标准：3.参考答案：解决方案计划：评分标准：4.参考答案：图3.6.1-2服务请求矩阵图3.6.1-3服务请求矩阵解决方案计划：因为关系可以用图形表示，所以复合关系也可以用图形表示。评分标准：四、证明(20分，共2题，每题10分)1.参考答案：xy(p(x)q(y)=xy(p(x)q(y)=xp(x)yq(y)=xp(x)yq(y)=xp(x)yq(y)解决方案计划：评分标准：2.参考答案：对于任何a r，都有0*a=0 a 0a=aa*0=a 0 a0=a因此，0是人民币。对于任何a，b r，都有a*b=a b abR所以*是关闭的。对于任何a，b，c