离散数学2012年4月考试真题(02324)

今有a，b，c，d，e，f，g共7人，已知下列事实：a会讲德语;b会讲法语和德语;c会讲俄语和英语;d会讲日语和汉语;e会讲德语和汉语;f会讲法语、日语和俄语;g会讲英语和汉语。

试问这7个人应如何排座位(圆桌)，才能使每个人和他身边的人交谈?

设G是有n个结点、n条边的简单连通图，且G中存在度数为3的结点。

证明：G中至少有一个度数为1的结点。

构造下列推理的证明。如果他是侦探，他必精通逻辑推理。如果他不是清洁工，他必是侦探。他逻辑推理能力差。所以他是清洁工。

求公式的主析取范式和主合取范式。

设A={l a，b为正整数}，在A上定义二元关系～如下：～

当且仅当a+b=c+d。

证明：～是一个等价关系。

在代数系统中，若存在a∈A，有a*a=a，则称a为A的幂等元。

证明：在群中，除幺元e外不可能有任何别的幂等元。

设R={<1，3>，<1，4>，<2，3>，<3，1>，<3，4>，<4，2>}是A={1，2，3，4}上的二元关系。

(1)画出R的关系图;

(2)写出R的关系矩阵;

(3)说明R是否具有自反、反自反、对称、反对称性质。

设={1，6，9，12，18，36}，≦为整除关系。

(1)画出的哈斯图;

(2)求子集B={6，12，18}的极大元、极小元、最大元、最小元。

K_n是n个结点的完全图，则K₆有_______条边，每个结点的度数为_______。

构造命题公式的真值表。