432-离散数学 试题 题单号:40632
(可不抄题)
考生注意：答案必须写在统一配发的答题纸上!
一、(每小题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为连通的。
第一大题：R1 、R2，中的1、2实际是R的下标。IAU中，A是字母I的下标，U是并集符号。
第一大题 ii) 小题中，R12、R22、R1+、R2+中第一个数字是下标，第二个数字/+号是上标。
第三大题 ? n中，n是字母 ? 的上标;IA 中，A是字母 I 的下标。
第五大题中红色的A应为倒置，红色的E应为反向。
第六大题中红色的A、E 同第五大题 | 
