国防科技大学2003年离散数学考研试题

　　国防科技大学2003年离散数学考研试题

　　国防科技大学2003年离散数学考研试题

　　考生注意：答案必须写在统一配发的答题纸上!

　　一、(每小题10分，共20分)

　　设 A = {a, b, c, d}，A 上的二元关系 R1和 R2定义如下：

　　R1 = {, , , }

　　R2= IA∪{,,,}

　　i) 试分别指出R1和R2所具有的性质(即 是否具有自反性，反自反性，对称性，反对称性和传递性这五种性质)。

　　ii) 试求出R12，R22，R1•R2， R1+ 和 R2+。

　　二、(15分)

　　设函数ƒ : X→Y 且 g : X→Y ，若令

　　A = {a∈X | g (ƒ(a))=a} 且 B = {b∈Y |ƒ(g (b))=b}

　　则 ƒ[A]= B。

　　三、(20分)

　　设 A 为有限集且ƒ:A→A , 证明：

　　a) 若有自然数 n≥1 使 ƒ n =IA ，则ƒ为双射;

　　b) 若ƒ为双射，则有自然数 n≥1 使 ƒ n =IA 。

　　四、(15分)

　　求合式公式(P∨Q)∧(P→R)∧(Q→R)<==>R 的主合取范式和主析取范式。

　　五、(15分)

　　试判断下列合式公式是否为永真式，并证明你的结论：

　　(Ax)(P(x)∨Q(x))→(Ax)P(x)∨(Ey)Q(y)，其中P和Q均为一元谓词。

　　六、(每小题10分，共30分)

　　用自然推理系统证明：

　　i) ﹁A∧﹁B ┣ ﹁(﹁A→B )

　　ii) ﹁(﹁A→B ) ┣ ﹁A∧﹁B

　　iii) (Ex)(﹁A(x)) ┣ ﹁(Ax)A(x)

　　七、(15分)

　　试求叶的权分别为 2，3，3，4，5，6，8 的最优叶加权二叉树及其叶加权路径长度。

　　八、(20分)

　　设n阶简单无向图G的边数 m >(1/2) (n-1)(n-2)，则G为连通的。