离散数学-复习题.docVIP

离散数学试题1 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子为命题的是( ) A.走，看电影去 B.x+y0 C.空集是任意集合的真子集 D.你明天能来吗? 2.下列式子不是谓词合式公式的是( ) A.(x)(P(x)→((x)(Q(x) ∧A(x，y))) B.(x)∧((y)∨P(x，y) C.(x)P(x)→R(y) D.((x)P(x)∧Q(y，z) 3.下列式子为重言式的是( ) A.P→P∨Q B.(﹁P∧Q)∧(P∨﹁Q) C.﹁ (P Q) D.(P∨Q) (P→Q) 4.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为xy，下列公式真值为真的是( ) A.(x)(y)F(x，f(f(x，y)，y)) B.(x)(y)(﹁F(f(x，y)，x)) C.(x)(y)(z)(F(x，y)→F(f(x，z)，f(y，z))) D.(x)F(f(a，x)，a) 5.对于公式(x)(y)P(x，y)∨Q(x，z)∧((x)P(x，y)，下列说法正确的是( ) A.x是自由变元 B.x是约束变元 C.( x)的辖域是P(x，y)∨Q(x，z) D.(x)的辖域是P(x，y) 6.设论域为{1，2}，与公式(x)﹁A(X)等价的是( ) A. ﹁A(1) ∨﹁A(2) B. ﹁A(1)→﹁(A2) C. ﹁A(1) ∧﹁A(2) D. A(1) →A(2) 7.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f( ) A.仅是单射 B.仅是满射 C.是双射 D.不是函数 8.下列哪个关系矩阵所对应的关系具有自反性( ) A. B. C. D. 10.在整数集上，下面哪个运算不是二元运算( ) A.加法 B.减法 C.乘法 D.除法 二、填空题 请在每小题的空格中填上正确答案。错填、不填均无分。 11.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。 12.请用联结词﹁，∧表示联结词∨和联结词 ：________，________。 13.设A={l，2，3，4}，A上的二元关系R={1，2，3，4，4，3}，S={l，3，3，4，4，1}，则R～S=________，(RS)-1=________。 三、计算题 14.用等值演算求(P→Q)→R的主合取范式。 15.列出(P→(Q∨R)) (P→Q)的真值表。 16．设A={a,b,c,d}，R={a，b，a，d，b，c，c，a，d，a}，求R的传递闭包。 17.设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。 四、证明题 18.用推理方法证明：P∨Q，P→R，Q→S├R∨S。 19.设A={a，b|a，b∈Z+，Z+为整数集}，A上的关系R={a，b,c，d|ad=bc}，证明R是等价关系。 五、综合应用题 20．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。 离散数学试题2 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。 1.下列句子为命题的是( ) A.全体起立! B.x=0 C.我在说谎 D.张三生于1886年的春天 2.下列式子不是谓词合式公式的是( ) A. B. C. D. 3.下列式子为矛盾式的是( ) A. B. C. D. 4.设给定赋值N如下：个体域为自然数集；特定元素a=0；特定函数f(x,y)=x+y,g(x,y)=xy；特定谓词F(x,y)为x=y。在赋值N下，下列公式为真的是( ) A. B. C. D. 5.对于公式，下列说法正确的是( ) A.y是自由变元 B.x是约束变元 C. 的辖域是 D. 的辖域是P(x,y) 6.设论域为{l，2}，与公式等价的是( ) A.A(1)A(2) B. A(1)A(2) C.A(1) D. A(2)A(1) 7.设Z+是正整数集合，f:Z+→Z+，f(n)=2n-2,则f( ) A.仅是单射 B.仅是满射 C.是双射 D.不是函数 8.下列关系矩阵所对应的关系具有反自反性的是( ) A. B. C. D. 二、填空题 请在每小题的空格中填上正确答案。错填、不填均不得分。 9.请