《离散数学(大作业)与答案》由会员分享，可在线阅读，更多相关《离散数学(大作业)与答案（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显然仍成立，归纳法完成。
