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

李老师

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