《离散数学(大作业)与答案》由会员分享,可在线阅读,更多相关《离散数学(大作业)与答案(4页珍藏版)》请在金锄头文库上搜索。
1、一、 请给出一个集合A,并给出A上既具有对称性,又具有反对称性的关系。(10分) 解:A=1,2 R=(1,1),(2,2)二、 请给出一个集合A,并给出A上既不具有对称性,又不具有反对称性的关系。(10分) 三、 设A=1,2,请给出A上的所有关系。(10分) 答:四、 设A=1,2,3,问A上一共有多少个不同的关系。(10分) 五、 证明: 命题公式G是恒真的当且仅当在等价于它的合取范式中,每个子句均至少包含一个原子及其否定。(10分)证明:设公式G的合取范式为:G=G1G2Gn 若公式G恒真,则G恒真,即子句Gi;i=1,2,n恒真为其充要条件。Gi恒真则其必然有一个原子和它的否定同时出
2、现在Gi中,也就是说无论一个解释I使这个原子为1或0 ,Gi都取1值。若不然,假设Gi恒真,但每个原子和其否定都不同时出现在Gi中。则可以给定一个解释I,使带否定号的原子为1,不带否定号的原子为0,那么Gi在解释I下的取值为0。这与Gi恒真矛盾。因此,公式G是恒真的当且仅当在等价于它的合取范式中,每个子句均至少包含一个原子及其否定。六、 若G=(P,L)是有限图,设P(G),L(G)的元数分别为m,n。证明:n ,其中 表示m中取2的组合数。(10分)证明:如果G=(P,L)为完全图,即对于任意的两点u、v(uv),都有一条边uv,则此时对于元数为m的P(G),L(G)的元数取值最大为。因此,
3、若G=(P,L)为一有限图,设P(G)的元数为m,则有L(G)的元数n ,其中 表示m中取2的组合数。七、 设G是有限图,P(G),L(G)的元数分别为m,n。d,D分别是G中点的最小度和最大度。证明:d2n/mD。(10分)证明:因为 mdmD 同时由定理1知=2n 则有 md2nmD 由m0有:d2n/mD八、设G=(P,L)是有限图,P(G),L(G)的元数分别为m,n。证明:如果n ,则G是连通的。(10分)证明:反证法,假设此时G不是连通的,则将G中的一个连通分支作为一个子图记为G1,剩余的部分记为G2。可设P(G1)的元数为m1,P(G2) 的元数为m2,其中1m1,m2矛盾,命题
4、得证。九、 设G为图(可能无限),无回路,但若任意外加一边于G后就形成一回路,试证G必为树。(10分)证明:从树的定义出发,1)由已知有G中无回路2)要证G连通,反证法,假设G不连通,则一定存在点u和v,满足在G中没有从u到v的路,现在连接u、v,即在G中添加一条边uv,由已知G中加一条边后形成一回路可知,G中u、v两点间有一回路,即若G中删除边uv后,点u、v仍然连通,矛盾。所以G连通。因此,G必为树十、 证明:一个有限连通图G是一条非回路的简单路,当且仅当G中有两个点的度为1,且其余点的度均为2。(10分)证明:必要性,设P(G)的元数为n,k=3时显然成立。假设k=n-1时,G中有两个点
5、的度为1,且其余点的度均为2。则当k=n时,设v1是路G的起点v2是与v1相邻的另一点,把点v1及边v1v2从G中删去得G。显然G仍是非回路的简单路且有n-1个节点,有归纳假设知G中有两个点的度为1,且其余点的度均为2。把点v1及边v1v2加入到G中得G,显然G中有两个点的度为1,且其余点的度均为2,归纳法完成。充分性,k=3时显然成立,假设k=n-1时,G是一条非回路的简单路。则当k=n时,设v1是路G中度为1的一点,v2是与v1相邻的另一点,把点v1及边v1v2从G中删去得G,此时v2的度必为1(若为0则与G是连通图矛盾;若为2则在G中v2的度为3,矛盾),有假设知G是一条非回路的简单路。把点v1及边v1v2加入到G中得G显然仍成立,归纳法完成。