离散数学测试题1.docVIP

离散数学测试题1 　　　　　　　　　　　　　 选择题 1. 若集合A＝{ a，}，则下列表述正确的是( )． A．(A B．{}(A C．{a}(A D．((AA={1，2，3，4，5}，偏序关系(是A上的整除关系，则偏序集 A，( 上的元素5是集合A的（ ）． A．最大元 B．极大元 C．最小元 D．极小元 3.设图G的邻接矩阵为 则G的边数为( )． A．B．C．D． 4. 图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(a, d) ,(b, d)}是边割集 D．{(b, d)}是边割集 5. 在谓词公式(?x)(A(x)→B(x)?C(x，y))中，（ ）． A. x，y都是约束变元B. x是约束变元，y都是自由变元 ．x，y都是自由变元D. x是自由变元，y都是约束变元集合上的， 则R的有序对集合为= ． 设G＝〈V，E〉是有4个结点，8条边的无向连通图，则从G中删去 条边，可以确定图G的一棵生成树。 设集合A={1，2}上的关系R＝{1, 1,1, 2}，则在R中仅需加一个元素 ，就可使新得到的关系为对称的． ((x)(A(x)→B(x，z)∨C(y))中的变元(x)为“x大于1”，则谓词公式((x)P(x) 的真值为 ． 将下列语句翻译成谓词公式 自然数都是实数． 有人能做此事． 计算题 1. 1.设集合试计算 （1） （2） （3） 2.画一棵带权为1, 2, 2, 3, 4的． （1）试写出量词的辖域； （2）指出该公式的自由变元和约束变元． 五、证明题 1.试证明 2.证明：设A，B是任意集合，试证明：若，则 答案 选择题 1．A 2．B 3．C 4．A 5．B 二、填空题 1. {2, 2, 2, 3, 2, 4,3, 3,3, 4,4, 4}； 2. 5； 3. 2, 1 4. z，y ； 5.真（或T或1） 三、将下列语句翻译成谓词公式 1.设M（x）：x是自然数； N（x）：x是实数。 则谓词公式为 设：是人； ：能做此事。 则谓词公式为：。 四、计算题（每小题12分，共36分） 1. （1） （2） （3） 2.最优二叉树如图三所示 权为1(3+2(3+2(2+3(2+4(2=27 3.解 （1）量词的辖域为， 的辖域为，　　　　　　　　 的辖域为．　　　　　　　　 (2)自由变元为中的y，中的z． 约束变元为中的x，中的z，中的y． 　　 五、证明题（12分） 1.证明： （1） （2） （3） （4） （5） （6） （7） 2.证明： 设，则 由，故，则有 所以 设，则 由，故，则有 所以 ( ( ( ( ( ( ( ( ( 11 2 2 3 3 4 7 5 12