妯辫姳鑽�
2009离散数学复习题
一、填空题
二、选择题
1．下列语句中不是命题的只有( ) ．．A．鸡毛也能飞上天？ C．不经一事，不长一智。 2．下列是真命题的有（ ）
A． {a}?{{a}}；
B．{{?}}?{?,{?}}；
B．或重于泰山，或轻于鸿毛。 D．牙好，胃口就好。
C． ??{{?},?}； D． {?}?{{?}}。 3．下列集合中相等的有（ ）
A．{4，3}??；B．{?，3，4}；C．{4，?，3，3}；D． {3，4}。
S
4．设S?{?,{1},{1,2}}，则 2 有（ ）个元素。
A．3； B．6； C．7； D．8 。
5．令p：张三做这件事，q：李四做这件事，则命题“这件事由张三和李四中的一人去做”可符号化为( ) ．．．．．A．p ∨ q
B．(p∧?q)∨(?p∧q)
C．(p∨?q)∧(?p∨q) D．(p∧?q)∧(?p∧q)
6．从真值角度看，命题公式的全部类型是( ) ．．．．．．．．．．A．永真式 C．永真式，永假式
B．永假式
D．永真式，永假式，可满足式
7．下述命题公式中，是重言式的为（ ）。
A、(p?q)?(p?q) ； B、(p?q)?((p?q))?(q?p)) ； C、?(p?q)?q ； D、(p??p)?q 。
8．设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”可符号化为( ) ．．．．A．(?x)(A(x)?B(x))
B．?(?x)(A(x)??B(x))
C．?(?x)(A(x)?B(x)) D．?(?x)(A(x)??B(x))
9．关于谓词公式(x)(y)(P(x, y)∧Q(y, z))∧(x)p(x, y),下面的描述中错误的是．．( )
A．(x)的辖域是(y)(P(x, y)∧Q(y, z)) B．z是该谓词公式的约束变元 C．(x)的辖域是P(x, y)
D．x是该谓词公式的约束变元
10．A，B是集合，P(A)，P(B)为其幂集，且A∩B=?，则P(A)∩P(B)为( ) A．? B．{?} C．{{?}} D．{?，{?}} 11．设S?{?,{1},{1,2}}，则有（ ）?S。
A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。
12．设A={a, b, c}， A上二元关系R={
B．反对称的 D．不可传递的
13．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}， S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1?R-1的运算结果是( ) A．{〈4，1〉，〈2，3〉，〈4，2〉} C．{〈4，1〉，〈2，3〉，〈2，4〉}
B．{〈2，4〉，〈2，3〉，〈4，2〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}
14．下面关于关系R的传递闭包t(R)的描述最确切的是( ) ．．．A．t(R)是包含R的二元关系 C．t(R)是包含R的一个传递关系
B．t(R)是包含R的最小传递关系 D．t(R)是任何包含R的传递关系
15．设S?{ 1, 2, 3 }，S上关系R的关系图为
则R具有（ ）性质。
A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性
?1?016．关系R的关系矩阵为MR???0??0( )
010010100?1??，则关系R所具有的性质是
．．0??1?A.自反、对称、传递 B.自反、反对称、传递 C.反自反、对称、传递 D.自反、反对称 17．设S={1，2，3}，R为S上的关系，其关系图为
则R具有（ ）的性质。
A、自反、对称、传递； B、什么性质也没有；
C、反自反、反对称、传递； D、自反、对称、反对称、传递。
18．设集合X为人的全体，在X上定义关系R、S为R={
R
和
S是
P
B． R?S-1 D． R-1?S
上的关系，P
是所有人的集合，
R?{?x,y?|x,y?P?x是y的父亲}，S?{?x,y?|x,y?P?x是y的母亲} 则
S?1?R表示关系 （ ）。
}； A、{?x,y?|x,y?P?x是y的丈夫}； B、{?x,y?|x,y?P?x是y的孙子或孙女C、 ?；
}。 D、{?x,y?|x,y?P?x是y的祖父或祖母20．设A={?，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（ ）
21. 函数的复合运算满足( ) ．．
A．交换律 B．分配律 C．结合律 D．等幂律
22．设简单图G所有结点的度数之和为12，则G一定有( ) ．．．A．3条边 B．4条边 C．5条边 23．下列各有向图是强连通图的是( )
D．6条边
24．设无向图G的边数为m，结点数为n，则G是树等价于( ) ．．．A．G连通且m=n+1 C．G连通且m=2n
B．G连通且n=m+1
D．每对结点之间至少有一条通路
25．设G为简单图，若图中存在一条经过每边一次且仅一次的回路，则此图为：( )
A、欧拉图 B、哈密顿图 C、平面图 D、树
26．下列语句中不是命题的只有( ) ．．A．这个语句是假的。 C．飞碟来自地球外的星球。
B．1+1=2.0
D．凡石头都可练成金。
27．下列语句是命题的有（ ）。
A、明年中秋节的晚上是晴天； B、x?y?0； C、xy?0当且仅当x和y都大于0； D、我正在说谎。
28．设p：天下大雨，q：他在室内运动，命题“除非天下大雨，否则他不在室．内运动”可符合化为( ) A. ┐p∧q C. ┐p→┐q
B. ┐p→q D. p→┐q