离散数学-复习题

离散题目

离散数学试题1

一、单项选择题

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.下列句子为命题的是( )

A.走，看电影去

C.空集是任意集合的真子集 B.x+y>0 D.你明天能来吗?

2.下列式子不是谓词合式公式的是( ) ．．

A.( x)(P(x)→( x)(Q(x) ∧A(x，y)))

C.( x)P(x)→R(y)

3.下列式子为重言式的是( )

A.P→P∨Q

C.﹁ Q) B.(﹁P∧Q)∧(P∨﹁Q) D.(P∨(P→Q) B.( x)∧( y)∨P(x，y) D.( x)P(x)∧Q(y，z)

4.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为x<y，下列公式真值为真的是

( )

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是自由变元

C.( x)的辖域是P(x，y)∨Q(x，z) B.x是约束变元 D.( x)的辖域是P(x，y)

6.设论域为{1，2}，与公式( x)﹁A(X)等价的是( )

A. ﹁A(1) ∨﹁A(2)

C. ﹁A(1) ∧﹁A(2) B. ﹁A(1)→﹁(A2) D. A(1) →A(2)

7.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f( )

A.仅是单射

C.是双射 B.仅是满射 D.不是函数

8.下列哪个关系矩阵所对应的关系具有自反性( )

101 A. 111

100

001 C. 001

100 100 B. 011 101 101 D. 010 100

1

离散题目

10.在整数集上，下面哪个运算不是二元运算( ) ．．

A.加法

C.乘法

二、填空题

请在每小题的空格中填上正确答案。错填、不填均无分。

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=________，(R S)-1=________。

三、计算题

14.用等值演算求(P→Q)→R的主合取范式。

15.列出(P→(Q∨(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．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。

B.减法 D.除法

离散数学试题2

一、单项选择题

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。

1.下列句子为命题的是( )

A.全体起立!

C.我在说谎

2.下列式子不是谓词合式公式的是( ) ．．

A.( x)(P(x,y) Q(x,z)) ( z)R(x,z)

B. ( x)( y)P(x,y) Q(x,z) ( x)P(x,y)

B.x=0 D.张三生于1886年的春天 2

离散题目

C. ( x)P(x) Q(x)) ( x)( P(x) Q(x))

D. ( x)P(x) Q(y,z)

3.下列式子为矛盾式的是( )

A.P P

C.P P B.P (P Q) D. (P Q) P Q

4.设给定赋值N如下：个体域为自然数集；特定元素a=0；特定函数f(x,y)=x+y,g(x,y)=xy；特定谓词F(x,y)为x=y。在赋值N下，下列公式为真的是( )

A. ( x)F(g(x,a),x)

B. ( x)( y)(F(f(x,a),y) F(f(y,a),x))

C. ( x)( y)( z)F(f(x,y),z)

D. ( x)( y)F(f(x,y),g(x,y))

5.对于公式( x)(P(x,y) Q(x,z)) ( z)R(x,z)，下列说法正确的是( )

A.y是自由变元

B.x是约束变元

C. ( x)的辖域是(P(x,y) Q(x,z)) ( z)R(x,z)

D. ( x)的辖域是P(x,y)

6.设论域为{l，2}，与公式( x)A(x)等价的是( )

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.下列关系矩阵所对应的关系具有反自反性的是( )

101 100

A. 011 B.

011

100 101

001 101

C. 001 D.

010

100 100

二、填空题

请在每小题的空格中填上正确答案。错填、不填均不得分。

9.请写出表示分配律的两个命题公式等价定理________,________。

10.请用联结词 ， 表示联结词 和联结词 ：________，________。

11.设A={1，2，3，4}，B={2，4，6}，则A-B=________，A B=________。

12.给出A={l，2}上的一个等价关系________，并给出其对应的划分________。

3

离散题目

13.设A={l，2，3，4}，A上的二元关系R={<1，2>，<2，3>，<3，2>}，S={<l，3>，<2，3>，<4，3>}，则R∩S=________，(R—S)-1=________。

三、计算题

14.列出(Q P) ((P R) Q)的真值表。

15.用等值演算求P (Q R)的主析取范式。

16.设A={1,2,3,4}，给定A上的二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}，求R的传递闭包。

四、证明题

17.用推理方法证明 …… 此处隐藏：3670字，全部文档内容请下载后查看。喜欢就下载吧 ……