2015-2016学年第二学期期末考试《离散数学》大作业.doc

《2015-2016学年第二学期期末考试《离散数学》大作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）三、设A={1，2}，请给出A上的所有关系。（10分）四、设A={1，2，3}，问A上一共有多少个不同的关系。（10分）五、证明：命题公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分）六、若G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n£，其中表示m中取2的组合数。（10分）七、设G是有限图，P(G)，L(G)的元数分别为m，n。d，D分别是

2、G中点的最小度和最大度。证明：d£2n/m£D。（10分）八、设G=(P，L)是有限图，P(G)，L(G)的元数分别为m，n。证明：如果n>，则G是连通的。（10分）九、设G为图（可能无限），无回路，但若任意外加一边于G后就形成一回路，试证G必为树。（10分）十、证明：一个有限连通图G是一条非回路的简单路，当且仅当G中有两个点的度为1，且其余点的度均为2。（10分）