本科离散数学复习题(20120629)

一、填空题

1、对于所有的真值指派，命题公式_______________，这种命题叫做重言式。

对于所有的真值指派，命题公式_______________，这种命题叫做矛盾式。 2、具有_______________________的______________________是命题。

3、一个命题标识符如表示确定的命题，就称为_____________，如果命题标识符只表示任意命题的位置标志，就称为______________。 4、设有命题“如果天不下雨，我就去游泳”。

则其逆换式为__________________________；

反换式为______________________________； 逆反式为______________________________。 5、已知原命题为：“如果天不下雨，我就去。”则该命题的

反换式是___________________________________________，

逆换式是___________________________________________， 逆反式是___________________________________________。 其中意义相同的命题是___________________________________。 6、已知原命题为：“如果风不大，我就去打羽毛球。”则该命题的

反换式是___________________________________________， 逆换式是___________________________________________， 逆反式是___________________________________________。 7、班长组织同学们星期日旅游，征求大家意见。意见如下：

①刘同学说：“如果天不下雨，我就去”；②曲同学说：“如果天下雨，我就不去”； ③于同学说：“如果我去，天就没下雨”；④张同学说：“如果我不去，天就下雨了”； ⑤李同学说：“星期日或者天下雨，或者我去公园”。 班长总结共有2种意见，其中_______________的意见相同，而_______________的意见一致。 8、命题公式?P?Q的主析取范式是____________________________ 9、命题公式?P?Q的主合取范式是____________________________ 10、命题公式 ((P∧Q)∨R)↑0 的对偶式是________________________ 11、命题公式 (P∨Q)→R 的对偶式为____________________________

12、对于前提S??Q，S?R，?R，?P?Q，其有效结论是________________ 13、对于前提 (p?Q)?R，?R?S，?S，其有效结论是_____________________ 14、用谓词表达命题，必须包括__________和__________两个部分。

15、设G(x) : x是金子，F(x) : x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”可以符号化为________________________________________

16、设C(x) : x是计算机，P(x,y) : x能做y，I(x) : x是智能工作，则命题“并非所有智能工作都能由计算机来做”可以符号化为________________________________________

17、设C(x) : x是计算机，P(x,y) : x能做y，I(x) : x是智能工作，则命题“并非所有智能工作都能由计算机来做”可以符号化为________________________________________

18、一个谓词公式，如果量词均在全式的开头，而且它们的作用域延伸到整个公式的末尾，则该公式叫做____________________。

19、谓词公式?xP(x)??xQ(x)??yR(y)的前束范式为_______________________ 20、谓词公式?x(P(x)?Q(x,y)??zR(y,z))?S(x)的前束范式为______________ 21、谓词公式(?x)P(x)?(?x)Q(x)的前束范式为______________________ 22、谓词公式(?x)P(x)?(?x)Q(x)的前束范式为_______________________

23、通常，一元谓词表达了客体的__________多元谓词表达了客体之间的__________。 24、设集合A?{x|x?3,x?Z},B?{x|x?2k,k?Z},C?{1,2,3,4,5}。

则A?C?_______________________，(A?B)?C?_______________________ 25、设集合A?{x|x?3,x?Z},B?{x|x?2k,k?Z},C?{1,2,3,4,5}。

则B?B?_______________________，A?(C?B)?______________________ 26、设A = {x | 100＜x＜200, x = 7n＋3, n?N, x?N}，则 |A| = ___________________ 27、若集合A的基数是10，则其幂集的基数是________________________________ 28. 设A={1,2,3,4,5}

S1={{1},{3,5},{2,4}}， S2={{1,2},{3},{3,4,5}} S3={{1},{3},{5},{2,4}} S4={{1,2},{3},{3,4,5}}

A上的覆盖集合是_________________，A上的划分集合是_________________。 29. 序偶=当且仅当_______________

30．A={1,2,3,4}上的二元关系R={<1,2>,<2,1>,<2,4>,<1,4>}具有_______________性质。 31．设集合A={1,2,3,4}上的等价关系

R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<3,4>,<4,3>}，

对应A上的一个划分是_______________

32、关系R是反自反的，当且仅当在关系矩阵中__________________________ 33、关系R是反自反的，当且仅当在关系图中____________________________ 34、关系R是反对称的，当且仅当在关系矩阵中__________________________ 35、关系R是反对称的，当且仅当在关系图中____________________________ 36、设R={<2,2>,<3,1>,<1,2>,<2,3>}，S={<1,2>,<2,2>,<3,1>}

则s(R)=_______________________ t(R)= ______________________

37．设集合A={1,2,3}上的关系R={<1,2>,<2,1>,<3,3>}，S={<1,3>,<2,2>,<3,2>}

则R·S＝________________________ ，S·R＝________________________。 38、设R={<2,2>,<3,1>,<1,2>,<2,3>}，S={<1,2>,<2,2>,<3,1>}

则R?S=_______________________，Rc=_______________________。

39、设R是定义在集合A上的一个关系，若R是_________________________________的，则称R为等价关系。

40、设r是定义在集合A上的一个关系，若r是______________________________的，则称r为相容关系。 41、在偏序集合的一个子集中，如果______________________________，则称这个子集为链。

如果______________________________，则称这个子集为反链。

42、对于一个偏序集合，如果______________________________，则称其为良序集。

43、定义在集合A上的一个关系，若满足______________________________，则称其为偏序关系。

二、选择题

2、设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（ ）。A

A、P→Q B、Q→P C、P?Q D、﹁Q∨﹁P

4、设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（ ）。B A、﹁P∧﹁Q B、﹁P∨﹁Q C、﹁(P?Q) D、P??Q

5、设P：张三可以做这件事，Q：李四可以做这件事。命题“张三或李四可以做这件事”符号化为（ ）。A A、P∨Q B、P∨﹁Q C、P?Q D、﹁(﹁P∨﹁Q) 6、命题公式(P∧(P→Q))→Q是（ ）。C

A、矛盾式 B、蕴含式 C、重言式 D、等值式 7、P→Q的逆反式是（ ）。D

A、Q→﹁P B、P→﹁Q C、﹁Q→P D、﹁Q→﹁P 8、﹁P→Q的逆换式是（ ）。A

A、Q→﹁P B、P→﹁Q C、﹁Q→P D、﹁Q→﹁P

9、已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的（ ）。A

A、充分条件 B、必要条件 C、充要条件 D、A，B，C都不对 10、﹁P→Q的反换式是（ ）。D

A、Q→﹁P B、﹁P→﹁Q C、﹁Q→﹁P D、P→﹁Q 11、重言式的否定式是（ ）。B A、重言式 B、矛盾式 C、可满足式 D、蕴含式 12、命题公式P→Q∧R的对偶式为（ ）。D

A、P→(Q∨R) B、P∧(Q∨R) C、﹁P∨(Q∧R) D、﹁P∧(Q∨R) 13、命题公式P→(Q↓P)是（ ）。B A、重言式 B、可满足式 C、矛盾式 D、等值式 14、P?﹁Q?（ ）。D A、﹁P→(P→﹁Q) B、(﹁P∨Q)∧(﹁Q∨P )

C、(﹁P∨﹁Q)∧(﹁Q∨P) D、(﹁P∨﹁Q)∧(Q∨P )

18、谓词公式 (?x)(P(x)∨(?y)R(y))→Q(x) 中量词?x的作用域是（ ）。C A、(?x)(P(x)∨(?y)R(y)) B、P(x) C、P(x)∨(?y)R(y) D、P(x) ,Q(x) 19、谓词公式 (?x)(P(x)∨(?y)R(y))→Q(x) 中变元x是（ ）。 D

A、自由变量 B、约束变量

C、既不是自由变量也不是约束变量 D、既是自由变量也是约束变量

20、设谓词P(x):x是奇数，Q(x):x是偶数，谓词公式 (?x)(P(x)?Q(x)) 在下面哪个论域中

是可满足的？（ ） D

A、自然数集 B、整数集 C、实数集 D、以上均不成立

21、设C(x):x是运动员，G(x):x是强壮的。命题“没有一个运动员不是强壮的”可符号化为（ ）。C

A、﹁(?x)( C(x)?﹁G(x) ) B、﹁(?x)( C(x)→﹁G(x) )

C、﹁(?x)( C(x)?﹁G(x) ) D、﹁(?x)( C(x)→﹁G(x) )

22、设A(x):x是人，B(x):x犯错误，命题“没有不犯错误的人”符号化为（ ）。 D A、(?x)( A(x)?B(x) ) B、﹁(?x)( A(x)→﹁B(x) ) C、﹁(?x)( A(x)?B(x) ) D、﹁(?x)( A(x)?﹁B(x) )

23、设Z(x):x是整数，N(x):x是负数，S(x,y):y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式：（ ）。 A

A、(?x) (?y) ( Z(x)?S(x,y)→﹁N(y )) B、(?x) (?y) ( Z(x)?S(x,y)→﹁N(y )) C、(?x) (?y) ( Z(x)→S(x,y)?﹁N(y )) D、(?x) ( Z(x)?S(x,y)→﹁N(y ))

24、令F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。则语句“某些汽车比所有的火车慢”可表示为：（ ）。 B

A、(?y) (G(y)→(?x) (F(x)?H(x,y ))) B、(?y) (G(y)?(?x) (F(x)→H(x,y ))) C、(?x) (?y) (G(y)→(F(x)?H(x,y ))) D、(?y) (G(y)→(?x) (F(x)→H(x,y ))) 25、设个体域A={a,b}，公式 (?x)P(x)?(?x)S(x) 在A中消去量词后应为（ ）。 B A、P(x)?S(x) B、P(a)?P(b)?(S(a)?S(b))

C、P(a)?S(b) D、P(a)?P(b)?S(a)?S(b)

26、在谓词演算中：P(a)是(?x)P(x)的有效结论，其理论根据是（ ）。 A A、全称规定规则（US） B、全称推广规则（UG） C、存在规定规则（ES） D、存在推广规则（EG） 27、设A-B=Φ，则有（ ）。 C

A、B=Φ B、B≠Φ C、A?B D、A?B

28、设A={x|x3-x=0}, B={x|x2-4<0,x?Z}, C={x|y=2x-1}, D={x|x+y=5,xy=6}，则有（ ）。 A A、A=B B、A=C C、C=D D、C=A

29、在0________Φ之间填上正确的符号。 D A、= B、? C、? D、?

30、设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（ ）。 B A、M∩N B、M∪N C、M?N D、M－N 31、幂集(P(P(P(Φ)))为（ ）。 C

A、{{Φ},{Φ,{Φ}}} B、{Φ,{Φ,{Φ}},{Φ}} C、{Φ,{Φ,{Φ}},{{Φ}},{Φ}} D、{Φ,{Φ,{Φ}}} 32、空集Φ的幂集P（Φ）的基数是（ ）。 B A、0 B、1 C、3 D、4

33、集合A={1,2,?,10}上的关系R={ | x+y=10, x?A, y?A}，则R的性质为 （ ）。 B A、自反的 B、对称的 C、传递的，对称的 D、反自反的，传递的

34、设S={1,2,3}，下图给出了S上的两个关系R1，R2，则复合关系R1?R2是（ ）。C

A、自反的 B、传递的 C、对称的 D、等价的

~的性质是（ ）35、设A={1,2,3,4,5}，ρ={| i

A、对称的 B、自反的 C、反对称的 D、反自反、反对称、传递的

36、设集合A={a,b,c}，R是A上的二元关系，R={,,,}，那么R是（ ）。D

A、反自反的 B、反对称的 C、可传递的 D、不可传递的 37、设R和S是集合A上的等价关系，则R∪S的对称性（ ）。 A A、一定成立 B、一定不成立 C、不一定成立 D、不可能成立 38、设R和S是非空集合A上的等价关系，下述各式是等价关系的为（ ）。 B A、(A×A)-R B、R C、R-S D、r(R-S)

39、集合A上的关系R是相容关系的必要条件是（ ）。 D

A、自反、反对称的 B、反自反、对称的 C、传递、自反的 D、自反、对称的 40、设R是集合A上的偏序关系，则R∪Rc是（ ）。 B A、偏序关系 B、等价关系 C、相容关系 D、都不是

2

三、判断题

1、“王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（ ）错 2、凡陈述句都是命题。（ ）错

4、命题“两个角相等当且仅当它们是对顶角”的值为1。（ ）错

6、命题“十减四等于五”是一个原子命题。（ ） 对 7、命题“如果1+2=3，那么雪是黑的”是真命题。（ ） 错

8、(P∨→(Q∧R))是一个命题演算的命题公式，其中P、Q、R是命题变元。（ ） 错 9、(P→(Q∧R→﹁Q)是一个命题公式，其中P、Q、R是命题变元。（ ） 错 10、若A：张明和李红都是三好学生，则﹁A：张和李红都不是三好学生。（ ） 错 11、若A：张明和李红都运动员，则﹁A：张明和李红不都是运动员。（ ） 对 12、若P：每一个自然数都是偶数，则﹁P：每一个自然数都不是偶数。（ ） 错 13、若P：每个自然数都是偶数，则﹁P：每个自然数不都是偶数。（ ） 对 14、如果A?B，则A∧C?B∧C，A∨C?B∨C。（ ） 对 15、如果A∧C?B∧C，则A?B。（ ） 错 16、联结词“↓”是可结合的。（ ） 错 17、联结词“↑”是可结合的。（ ） 错 18、联结词“↓”是可交换的。（ ） 对 19、联结词“↑”是可交换的。（ ） 对 20、联结词“→”满足交换律。（ ） 错

21、“学习有如逆水行舟，不进则退”。设P：学习如逆水行舟，Q：学习进步，R：学习退步。则命题符号化为P∧(﹁Q→R)。（ ）错

22、P、Q、R定义同上题，则“学习有如逆水行舟，不进则退”形式化为：P→(﹁Q→R)。（ ） 对

23、设P、Q是两个命题，当且仅当P、Q的真值均为1时，P?Q的值为1。（ ） 错 24、命题公式(P∧(P→Q))→Q是矛盾式。（ ） 错 25、命题公式(P∧(P→Q))→Q是重言式。（ ） 对 26、联结词∧与∨不是相互可分配的。（ ） 错

27、在命题的演算中，每个最小联结词组至少有两个联结词。（ ） 错 28、命题联结词集{﹁,?}是最小联结词集。（ ） 错 29、命题联结词集{﹁,∧,∨}是最小联结词集。（ ） 错 30、命题联结词集{∧,→}是最小联结词集。（ ） 错 31、命题联结词集{↑}和{↓}都是最小联结词集。（ ） 对 32、A是命题公式，A与(A*)*互为对偶式。（ ） 错 33、A是命题公式，A?(A*)*。（ ） 对

34、P是命题变元，P与P互为对偶式。（ ） 对

35、任一命题公式的主析取范式和它的主合取范式互为对偶式。（ ） 错 36、任一命题公式都可以表示成与其等值的若干极小项的析取式。（ ） 对 37、在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（ > 错 38、公式 (?x)(P(x)→Q(x) )?R(y) 中量词?x的作用域为P(x)。（ ） 错 39、同一谓词公式，指定不同的论域，其真值不一定相同。（ ） 对 40、谓词公式(?x)P(x)?(?y)﹁P(y)是矛盾式。 （ ）对

41、(?x)(P(x)→Q(x) )→((?x)P(x)→(?x)Q(x) )为真。（ ）对

42、对公式(?z)(P(z)∧Q(x,z)∧M(z,y))∨R(z)中自由变量进行代入后，有(?z)(P(z)∧Q(a,z)∧M(z,b))∨R(z)。 （ ）错

43、(?x) (?y) (P(x)→Q(y) )?(?x)P(x)→(?y)Q(y)。 （ ）对

44、P(x)、Q(x)表示谓词，P表示命题，有(?x) (P(x)→P)?(?x)P(x)→P。 （ ）对 45、(?x) (A(x)∧B(x) )?(?x)A(x)∧(?x)B(x)。（ ）对 46、(?x) (A(x)→B(x) )?(?x)A(x)∧(?x)B(x)。（ ）错

47、任意一个谓词公式都与一个前束范式等价。（ ）对

48、公式(?x)P(x)→(?y)Q(x,y)的前束范式为(?x) (?y) (P(x)→Q(x,y) )。（ ）错 49、公式(?x)(﹁(?y)P(x,y)→((?z)Q(z)→R(x)))的前束范式为(?x) (?y) (?z) (P(x,y)∨﹁Q(z) ∨R(x))。（ ）错 50、下面的推理：

条件：(?x)(P(x)∨Q(x) )，根据全称规定（US）有：P(a)∨Q(b)

是正确的。（ ）错

51、对公式(?z)(P(z)∧Q(x,z)∧M(z,y))∨R(z)中约束变量z改名后，得到的等价公式为：(?t)(P(t)∧Q(x,t)∧M(t,y))∨R(t)。（ ）错 52、若P∪Q=Q，P∩Q=Φ，则P=Φ。 对 53、{Φ}?{Φ,{Φ}}且{Φ}?{Φ,{Φ}}。 对

54、设A={Φ}，B=P(P(A))，则有{Φ}?B，且{Φ}?B。 对 55、设A、B是集合，则命题A?B 和A?B可能同时成立。对 56、设A、B是任意集合，则P(A-B)=P(A)-P(B)。 错 57、若A-B?B，则B?A。 错 58、对每个集合A，有{A}?P(A)。 对

59、设A、B是任意集合，若{A∩B,B-A}是A∪B的一个划分，则有A-B=Φ。对

60、设A、B是两个非空集合，若{A-B,B-A}是A∪B的一个划分，则有A∩B=Φ。对 61、设A、B是任意集合，若{A∩B, A-B,B-A}是A∪B的一个划分，则有A∩B=Φ，A-B=Φ，B-A =Φ。 错

62、设A、B是任意集合，若{A∩B }是A∪B的一个划分，则有A-B=B-A =Φ。 对

+B=A○+C，则B=C。63、若A○（ ）。 对

64、集合A={1,2,3}的任何关系R都不可能既是对称的，又是反对称的。（ ） 错

65、集合A={a,b,c}上的关系R={,}是不可传递的。（ ） 错 66、若R和S67、若R和S68、若R和S69、若R和S

是集合A上的任意两个自反关系，则R?S也是自反的。（ ） 对 是集合A上的任意两个反自反关系，则R?S也是反自反的。（ ） 错 是集合A上的任意两个对称关系，则R?S也对称的。（ ） 错 是集合A上的任意两个传递关系，则R?S也是传递的。（ ）错

70、若R为是集合A上的反对称关系，则t(R)一定是反对称的。（ ） 错

71、若R是集合A上的传递关系，则R2也是集合A上的传递关系。（ ） 对 72、设R和S是集合A上的等价关系，则R∪S一定是等价的。（ ） 错 73、设R和S是集合A上的两个相容关系，则R?S与R∩S都是相容关系。（ ） 错 74、平面上直线间的平行关系是等价关系。（ ） 对

75、设人的集合A上的朋友关系为R，则R是A上的相容关系。（ ） 76、若集合A上的关系R是对称的，则Rc

也是对称的。（ ） 对 77、一个不是自反的关系，一定是反自反的。（ ） 错

四、各章习题

对

本文来源：https://www.bwwdw.com/article/5qp2.html