离散数学选择题

单项选择题

第一章 命题逻辑

1．下列语句，哪一个是真命题：（ B ）

A．我正在说谎 B．如果1+1=0，那么雪是黑的 C．9+5＞18 D．存在最大的质数 2．下面哪一个命题是假命题（ A ）

A．如果2是偶数，那么一个公式的析取范式唯一 B．如果2是偶数，那么一个公式的析取范式不唯一 C．如果2是奇数，那么一个公式的析取范式唯一 D．如果2是奇数，那么一个公式的析取范式不唯一 3．下面哪个联结词运算不可交换（ B ） A． ?； B．? C．? D．?

4．设P：天下大雨，Q：他乘公共汽车上班。命题“只有天下大雨，他才乘公共汽车上班”

符号化为（ B ）

A．P?Q B．Q?P C．P?Q D． ?P?Q

5．设P：天下钉子，Q：我去B城 。命题“除非天下钉子，否则我去B城”符号化为：（ C ）

A．P? Q B．Q? P C．?P? Q D．Q? ┐P

6．设P：我们划船，Q：我们跳舞，命题“我们不能既划船又跳舞”符号化为（ B ） A．PVQ 2）┐（P∧Q） C．┐P∧┐Q D．┐P∧Q

7．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）

A．P?┐Q B．P∨┐Q C．P∧Q D．P∧┐Q

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

A．P? Q B、Q? P C、P?Q D、┐P∨┐Q 9．下面哪一个命题公式是重言式（ D ）

A．（P∨R）∧（P? Q） B．P?（Q∨R）

C．（P∨Q）?（Q∨R） D．（P?（Q? R））?（P? Q）?（P?R） 10．下面哪一组命题公式不是等价的（ C ）

A．（P?Q）?（Q?P），P?Q B． ?（P?Q），（P∧┐Q）∨（┐P∧Q） C．P?（Q∨R），┐P∧（Q∨R） D． P?（Q∨R），（P∧┐Q）? R 11．下面哪个命题公式是重言式（ B ）

A．（P? Q）?（Q?P） B．（P?Q）?P C．（┐P∨Q）∧┐（┐P∧Q） D．（P?Q）?P 12．下列公式哪一个是两个命题变元P，Q的小项（ C ）

A．P∧┐P∧Q B．┐P∨Q C．┐P∧Q D．┐P∨P∨Q 13．一个公式在等价意义下，下面哪个写法是唯一的。（ C ）

A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不对 14．命题公式?(P?Q)的主析取范式编码为 ( D )

A．m00?m01?m11 B．m00∨m11 C．m01 D．m10

15.命题公式(P?Q)的主合取范为 ( a )

A．M01?M10 B.M00?M11 C.M00?M01 D.M10?M11 16.命题公式的任意两个不同极小项的合取式一定为( b )

A.永真式 B.永假式 C.可满足式 D.不可确定

17．下面联结词集中，哪一个不是联结词的极小全功能集（ d ）

A．{?，?} B．{↓} C．{?} D．{?，?，?}

第二章 一阶逻辑

1．设S(x): x是三好学生, a:张三, b: 李四, 命题“张三是三好学生而李四不是”符号化为（ ） D

A．S（a）， ?S（b） B．S（a）∨?S（b） C．S（a）∨?S（b） D．S（a）∧?S（b）

2.令F(x):x是有理数，G(x):x是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为 （ ） B A.?x(F(x)∧G(x))∧?x(G(x)??F(x)) B.?x(F(x)?G(x))∧?x(G(x)∧?F(x)) C.?x(F(x)∧G(x))∧?x(G(x)∧?F(x)) D.?x(F(x)?G(x))∧?x(G(x)??F(x))

3．设F(x)：x是火车，G(x)：x是汽车，H(x,y)：x比y快。“每列火车都比某些汽车快”符号化为（ ） C

A．(?x)(?y)(F(x)?G(y)?H(x,y))； B．(?x)(?y)(F(x)?G(y)?H(x,y))； C．(?x)(F(x)?(?y)(G(y)?H(x,y)))； D．(?x)F(x)?H(x,y)

4．设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))；

5．设个体域A={a、b}，公式(?x)P(x)??xS(x)在A上消去量词应为（ ） D

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)) 6．一阶公式

?x(P(x)∨

?yR(y))→Q(x)中量词

?x的辖域是 ( ) A

?yR(y))→Q(x)

A. (P(x)∨

?yR(y)) B. P(x) ?yR(y)) D. (P(x)∨

C. ?x(P(x)∨

7、设论域为整数集，下列公式中哪个值为真（ ） A

A．?x?y(x?y?0) B.?y?x(x?y?0) C. ?x?y(x?y?0) D．??x?y(x?y?0) 8．下面给出的一阶逻辑等价式中，哪一个是错的。（ ） B

A．A??xB（x）??x（A?B（x））

B．?x（A（x）?B（x））??xA（x）??xB（x）

C．?x（A（x）?B（x））??xA（x）??xB（x） D．??xA（x）??x（?A（x））

9．在谓词演算中，下列各式中，哪式是正确的（ ）。B

A．?x?yA(x,y)??y?xA(x,y) B．?x?yA(x,y)??y?xA(x,y) C．?x?yA(x,y)??x?yA(x,y) D．?x?yA(x,y)??y?xB(x,y) 10．设论域为整数集，下列公式中哪个值为假 （ ） D A．???y(x?y?0) B．?y?x(x?y?2) C．?x?y?z(x?y?z) D．?x?y((x?y)?1) 11．设I是如下一个解释：D＝{a,b},

P(a,a) P(a,b) P(b,a) P(b,b)

1 0 1 0则在解释I下取真值为1的公式是( ).D

A ?x?yP(x,y) B ?x?yP(x,y) C ?xP(x,x) D ?x?yP(x,y).

12．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)?(?x)(?y)R(x,y,z))中量词?x的辖域是（ ）A

A．（Q(x,z)?(?x)(?y)R(x,y,z)） B．Q(x,z)，R(x,y,z) C．Q(x,z)?(?y)R(x,y,z) D．Q(x,z) 13.谓词公式?x(p(x)??yR(y)?Q(x)中变元χ是 ( ) D A．自由变元 B．既不是自由变元也不是约束变元 C．约束变元 D．既是自由变元又是约束变元 14.一阶逻辑公式?x(F(x,y)∧G(y,z))→?zF(z,y)是 （ ） C A.前束范式 B.封闭公式 C.永真式 D.永假式 15．一阶逻辑公式?xP(x)??xP(x)是( ) A

A.永真的 B.永假的 C.可满足的 D.前束范式. 16.一阶逻辑公式?xP(x)??yQ(y)的前束范式是（ d ） A.?x?y(P(x)?Q(y)) B.??xP(x)∨?yQ(y) C.?x?y?P(x)∨Q(y) D.?x?y(P(x)?Q(y))

第三章 集合的基本概念和运算

1．下列式子中正确的是（ ）． D

A．?＝0； B．???；C．?＝{?}； D．??｛?｝ 2．下列各式中哪个是错的（ B ）

A、? ? ? ； B、???； C、? ?｛?｝； D、??{?} 。 3．下列命题正确的是（ ）。 A

A．??{?}=? B．??{?}=? C．{a}?{a，b，c} D．??{a，b，c} 4．下列各命题哪一个是假命题（ ） B

A．{a,b}?{a,b,c,{a,b,c}} B．{a,b}?{a,b,c,{a,b,c}} C．{a,b}?{a,b,{a,b}} D．{a,b}?{{a,b}}

5．设A={{1,2,3}, {4,5}, {6,7,8}}，下列哪个式子为真（ ） C

A．1∈A B．{1,2,3}?A C．{{4,5}}?A D．??A

6．设A＝{?}，B=P（P（A）），下式中错的是（ ） D

A．??B； B．{?}?B； C．{{?}}?B； D．{?，{?}}?P（A）。 7．设A=?，B={?, {?}}，则B－A是（ ） C

A．{{?}}； B．{?}； C．{?, {?}}； D．? 8．集合{0}的所有子集是（ ） B

A．?； B．?, {0}； C．{?}； D．{?, {0}} 9．设A＝{a,b}，则A的幂集P（A）为（ ） D

A．{a,b} B．{?,{a},{b}} C．{?,{a,}} D．{?,{a},{b},{a,b}}

10．设X，Y，Z是集合，“一”是集合相对补运算，下列等式不正确的是（ ）Ａ

A．(X－Y)－Z＝X－(Y∩Z) B．(X－Y)－Z＝(X－Z)－Y C．(X－Y)－Z＝(X－Z)－(Y－Z) D．(X－Y)－Z＝X－(Y∪Z)

11.设集合A={2,{a},3,4}，B={1,{a},3,4}，E为全集，则下列命题正确的是( ) C

A {2}?A B {a}? A C ??{{a}}? B D {{a},1,3,4}? B. 12.设A,B为集合,A∩B=A∪B成立的充分必要条件是( D )

A. A=B=? B. A=? C. B=? D. A=B

第四章 二元关系与函数

1．设A＝{1，2}，B＝{a,b,c}，C＝{c,d}，则A×（B∩C）为（ B ）

A．??c,1?,?2,c?? B．??1,c?,?2,c?? C．??c,1?,?c,2?? D．??1,c?,?c,2?? 2．设集合A={1，2，3}，A上的关系R={<1，1>，<1，2>，<2，2>，<3，3>，<3，2>}，则R

不具备( ) B

A．传递性 B．对称性 C．自反性 D．反对称性 3．设R是集合A={a,b,c,d}上的二元关系，

R={,,,,,,}，则R具有关系的哪些性质（ ） D A.自反性、反对称性 B.反自反性、传递性 C.自反性、对称性 D.反对称性、传递性

4．设集合A＝{1,2,3,4}，A上的关系R＝{<1,1>,<2,2>,<1,3>}，则R具有关系的哪些性质（ ）．A

A．传递性；B．自反性；C．对称性；D．以上答案都不对 5．设A={0, b}，B={1, b, 3}，则A∪B的恒等关系为（ ）A

A．{<0, 0>, <1, 1>, ,<3, 3>}； B．{<0, 0>, <1, 1>, <3, 3>}； C．{<1, 1>, , <3, 3>}； D．{<0, 1>, <1, b>, , <3, 0>}

6．设A＝{1，2，4，6，8},集合A上的二元关系R??a,b?a?b2，则domR和ranR分别

为（ ）B

1,4? B．?1,4?和?1,2? C．??1,4??和?2,1? D．??1,1?,?4,2??和?2,1? A．??1,2??和???7．若集合A上的关系R为等价关系，则R的必要条件是（ ）D