2002年国防科技大学软件基础试题(离散数学部分)试题

国防科技大学研究生院2002年硕士生入学考试428-离散数学试题题单号：40628（可不抄题）考生注意：1、答案必须写在统一配发的答题纸上；2、统考生做第一、二、三、四、五、六、七、八、九题；3、单独考生做第一、二、三、四、五、六、七、十、十一题。一、（每小题6分，共12分）设集合A={1，2，3，4}上的二元关系R₁和R₂定义如下：i)试分别指出R₁和R₂所具有的性质（即是否具有自反性，反自反性，对称性，反对称性和传递性这五种性质）。ii)).()(,2121RtsrRtRR和二、（8分）求合式公式))(())((RQPRQP的主合取范式和主析取范式。三、（10分）设二元关系RA2是自反的。证明R为等价关系的充要条件是：若〈a,b〉，〈a,c〉R,则b,cR.2四、（每小题5分，共15分）在1到2000这2000个正整数中，试求出：I）能被3、5或7整除的正整数的个数；II）仅能被3、5或7这三数中的两者整除的正整数的个数；III）能被3整除，但不能被5整除，也不能被7整除的正整数的个数。五、（10分）设A，B为非空集合且AB=.证明：存在函数h:AAB和k:BAB，使得对任意集合D及任意函数f:AD和g:BD，都存在唯一的函数:ABD使.kghf且六、（10分）证明：若n阶简单无向图G的任意两个结点的度数之和大于等于n-1，则G是连通的。七、（10分）设A为非空集合，Π={|为A的划分}。若令R={,且对每个u皆有v使uv}试证明R为II上的半序。八、（10分）任给52个整数，证明其中必有两数之和能被100整除或两数之差能被100整除。[提示：考虑一个整数被100除所得的余数。]九、（15分）用自然推理系统证明：I）┡A∨B（8分）II）├(∀x)(y)(P(x)P(y))（7分）十、（10分）试求P（A）P(B)=PAB)的充要条件，并加以证明。其中，P（A）表示A的幂集。十一、（15分）用自然推理系统证明：I）（8分）├II）（7分）x)xx))├x)A(x)x)B(x)