计算机离散数学练习题

一、填空题

1、量词辖域中出现的（ ）和指导变元交换为另一变元符

号，公式其余的部分不变，这种方法称为换名规则。

2、集合A={ ,{ }}的幂集P(A) = （ ）

3、Q：我将去上海，R：我有时间，公式(Q R) (R Q)的

自然语言为 （ ）

4、A B=（ ）

5、设F(x): x是人，G(x): x用右手写字，命题“有的人并不用右手写字”用谓词公式

表示为（ ）

6、设A是n个(n≥1)元集的集合，则A的幂集有（ ）个元素，有

（ ） 种不同的二元关系

7、命题公式 P Q P Q 可化简为（ ）

二、选择题

1、下列各命题中真值为真的命题有（ ）。

A．2+2=4当且仅当3是奇数；B.2+2=4当且仅当3不是奇数；

C.2+2≠4当且仅当3是奇数； D.2+2=4仅当3不是奇数；

2、下列等价式成立的有（ ）。

A.P Q Q P ；B.P (P R) R ；

C. P (P Q) Q； D.P (Q R) (P Q) R。

3、命题“尽管有人聪明，但未必一切人都聪明”的符号化

（P(x)：x是聪明的，M(x)：x是人） （ ）

A. x(M(x) P(x)) ( x(M(x) P(x)))

B. x(M(x) P(x)) ( x(M(x) P(x)))

C. x(M(x) P(x)) ( x(M(x) P(x)))

D. x(M(x) P(x)) ( x(M(x) P(x)))

4、下列语句中哪一个是真命题？（ ）

A、我正在说谎 B、严禁吸烟 C、如果1+2=3，则雪是黑的 D、如果1+2=5，则雪是黑的

5、若公式(P Q) ( P R)的主析取范式为m001 m011 m110 m111则它的主合取范

式为（ ）

A.m001 m011 m110 m111 ； B.M000 M010 M100 M101 ；

C.M001 M011 M110 M111； D.m000 m010 m100 m101 。

6、谓词公式 x yP(x,y)否定式为（ ）

A、 x y P(x,y) B、 x y P(x,y) C、 x y P(x,y) D、 x y P(x,y)

7、在集合运算中，（ ）对 可分配

A、 B、 C、— D、

8、A={1，2，3}，在下列A上的二元关系中（ ）是不可传递关系

A、{22} C、A×A D、IA 2} B、{三、解答题

1、将wff x( ( yP(x,y)) ( zQ(z) R(x)))化为与其等价的前束范式。

2、集合S={a，b，c，d，e}，找出S上的等价关系，

此关系能产生划分{{a}，{b,c}，{d，e}}，并画出关系图

3、设A {2，3，4，9}，B {2，4，7，10,12}，从A到B的关系

R { a,b a A,b B,且a整除b}，试给出R的关系图和关系矩阵，

4、A={a,b,c,d}，R={<a,b>,<b,c>,<b,d>,<c,b>}为A上的关系，求R的传递闭包，并画出t（R）的关系图。

5、设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24}，“ ”为S上整除关系，问：（1）偏序集 S　, 的Hass图如何？（2）偏序集{S　, }的极小元、最小元、极大元、最大元、上界、下界、上确界、下确界是什么?（3）子集{2,4,6}极小元、最小元、极大元、最大元、上界、下界、上确界、下确界是什么?

6、求命题公式 P Q R P Q R 的主合取范式和主析取范式

7、求谓词公式 x F(x) G(x,y) yH(y) zR(y,z)

8、设二元关系R={<a, b>, <{a}, b>,<{φ}, {φ}>, <{φ}, φ>}求：

（1）domR（2）ranR（3）R R（4）R -

9、（8分）设A={a, b, c, d, e, f}, R=IA∪{<a, b>, <b,a>,<c,e>,<e,c>}

（1）验证R是A上的等价关系，(2)求a的等价类 a R ，(3)求c的等价类[c]R，

(4)求一个划分A/R

10、设<A,R>为一个偏序集，其中，A={1，2，3，4，6，8，12，24}，R是A上的整除关系。（1）画出<A,R>的哈斯图；

（2）求R关于A的最大元、最小元、极大元、极小元；

（3）求B={4,6,8}的最小上界和最大下界

四、证明与应用题

1、前提：(P Q) R, R S, S

结论： P

2、问下列推理是否逻辑有效？证明你的结论

鸟会飞，猴子不会飞；所以，猴子不是鸟。

3、符号化并证明其结论：“所有有理数是实数，某些实数是整数，因此某些有理数是整数”（设R(x)：x是实数，Q(x)：x是有理数，I(x)：x是整数）

4、 A B B A B

5、设A、B为二集合，已知A B，

证明：P(A) P(B)。其中，P(B), P(B)分别为A与B的幂集。

本文来源：https://www.bwwdw.com/article/4lx4.html