回答学生问题(离散数学)

《回答学生问题(离散数学)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、问题回答一、回答“学习求助”(wzzlhlf)教材第42页练习2.1(A)：1(1)求的真值。其中P：3>2；Q(x)：x£3；R(x)：x>5，e：6，个体域D＝{－2,3,6}。解P为“3>2”，显然为真，即PÛ1，e=6，R(e)为“6>5”，此命题真值为1，故R(e)Û1。二、回答“答张喜荣(wwwedu)”1．任意集合A，B，证明P(A)ÈP(B)ÍP(AÈB)证明"xÎ(P(A)ÈP(B))ÛxÎP(A)ÚxÎP(B)ÛxÍAÚxÍBÞxÍ(AÈB)ÛP(AÈB)说明：集合有性质AÍAÈB，BÍAÈB。xÍAÍAÈB，xÍBÍAÈB，所以xÍ(AÈB)Ç(AÈB)=AÈB。而

2、AÇBÍA，AÇBÍB证明中的“xÍAÚxÍBÞxÍ(AÈB)”，只能是单方向Þ，而不是双方向Û。2.教材第154页23题。解"x，xÎf－1(AÇB)Ûf(x)ÎAÇBÛf(x)ÎAÙf(x)ÎBÛ说明：本题需要分清楚：f：X®Y，即X＝Dom(f)，Ran(f)ÍY。Y的子集合A，B都是值域的部分，那么f－1(A)或f－1(B)都是定义域中的元素。3.自反性与反自反性的区分，自反性就是所有(第一元素与第二元素相等的有序对)都在二元关系R中，当然x应是集合A的元素；而反自反性就是所有(第一元素与第二元素相等的有序对)都不在二元关系R中。如A{a,b,c},那么只要含

3、有,,有序对的二元关系，就都具有自反性，而,,有序对都没有的二元关系，就都具有反自反性的。而有一个或两个这种对的二元关系既不是自反的也不是反自反的。三、回答Email：heavy_rain_tien的问题原问题1.证明“集合A上的二元关系是传递关系的充分必要条件是R·RÍR”是否要用归纳法？解答：不用归纳法，证明如下。证明先证必要性Þ．即已知R是传递关系，要证R·RÍR．因为，若ÎR·RÛ$bÎA(ÎRÙÎR)，由R是传递的定义，得到ÎÎR·R，都有Î<

4、R．故R·RÍR．再证充分性，Ü，即已知R·RÍR，要证R是传递的．由复合关系定义，若",,若ÎRÙÎRÞÎR·RÍR,即ÎR,所以R是传递的．原问题2.要画出完全图的子图很容易漏掉，请问对于Kn的子图数目有什么规律性？解答：作Kn的子图，尤其是非同构的子图，没有好的规律可用．一般地，对边数归纳逐一做．先做0条边的，结点逐一增至n；再做1条边的，结点逐一增至n；…………原问题3.第6章定理4,5,9,12都省略了证明，老师是否可以提供一下？解答：下面给出几个定理的证明。(1)第6章定理4的证明定理4：设G＝为无向简单图

5、且½V½³3，如果G中每对结点度数之和大于或等于½V½，则在G中存在一条哈密顿回路．为了证明定理4，首先证明引理．引理1：设G是有n个结点的无向简单图，如果G中每对结点度数之和大于或等于n－1，则G中存在哈密顿通路．证明首先证明G是连通的．否则，G中至少存在两个连通分支G1和G2．设G1有n1个结点，G2有n2个结点．由于G是简单图，故G1和G2均为简单图．因而于是与题设条件矛盾．所以G是连通图．下面证明存在哈密顿通路．设L＝v1v2…vl为G中一条长度为l－1的初级通路l£n，不妨设此通路的端点不再与L外的结点相邻了，否则可将相邻的结点扩充到该通路中来．（1）若l=n，则L是G中哈密顿

6、通路．（2）若l

7、得初级通路．这条新的通路比原来的通路多一条边，对新的通路重复(1)，(2)，(3)．重复上述过程，直到全部结点扩展到初级通路中来．得G的一条哈密顿通路为止．v1v2vi－1vl图1v1v2vi－1vl图2v1v1vk－1vkvi－1vlvx图3下面证明定理4．证明定理4设G有n个结点．由引理，G中存在哈密顿通路．不妨设v1v2…vn为G中一条哈密顿通路．(1)若v1与vn相邻，则v1v2…vn为G中一条哈密顿回路．(2)若v1与vn