下载文档原格式
北京工业大学经管学院期末试卷
《离散数学》（A）
学号姓名：成绩
一、单项选择题（每题2分，共18分）
1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不．滑”可符号化为（D）A．P→Q B．P∨Q
C．P∧Q D．P∧Q
p→q，蕴涵式，表示假设、条件、“如果，就”。
“→”与此题无关
2. 关于命题变元P和Q的极大项M1表示( C )。书P1520，此题换作p、q更容易理解
A.┐P∧Q
B.┐P∨Q p∨┐q 01 1 M1
∨┐Q∧┐Q
3.设R（x）：x是实数；S（）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D）
4.在论域{}中与公式（x∃）A（x）等价的不含存在量词的公式是（B）
A.)b(
)a(
A∨
A
A
)a(
A∧ B. )b(
C. )b(
)b(
A→
A
A
)a(
A→ D. )a(
5．下列命题公式为重言式的是（C）
A．Q→（P∧Q）B．P→（P∧Q）
C．（P∧Q）→P D．（P∨Q）→Q
牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况
6. 设｛1，2，3｝，｛｝，下列二元关系R为A到B的函数的是( A )
A. ｛<1>,<2>,<3>｝
B. ｛<1>,<2>｝
C. ｛<1>,<1>,<2>,<3>｝
D. ｛<1>,<2>,<3>,<1>｝
7.偏序关系具有性质（D）背
A.自反、对称、传递
B.自反、反对称
C.反自反、对称、传递
D.自反、反对称、传递
8.设R 为实数集合，映射:,R R σ→2
()21,x x x σ=-+-则σ 是( D ).
(A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f ：A→B
（1）若，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】
（2）若对于任何的x 12∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即真正一一对应，甚至不存在一个y 对应多个x 。显然，本题为二次函数，不满足】
（3）若f 既是满射的，又是单射的，则称f 是双射的【本题中两个都不满足，既不是单射也不是满射】
二、填空题（每空2分，共22分）
１.设Q 为有理数集，笛卡尔集×Q ，*是S 上的二元运算，∀
则
２.在个体域D 中，公式)x (xG ∀的真值为假当且仅当某个G(x)的真值为假，公式)x (xG ∃的真值为假，当且仅当所有G(x)的真值都为假。
３.给定个体域为整数域，若F （x ）：表示x 是偶数，G （x ）：表示x 是奇数；那么，)x (G )x ()x (F )x (∃∧∃是一个 永真式 ；而))x (G )x (F )(x (∧∃是一个 永假式 。
４.设{}{}===)R (r ,c ,b ,b ,a R A ,c ,b ,a A 则上的二元关系
{<>,<>,<>,<>,<>,<>} ；
s(R)= {<>,<>,<>,<>} 。
书P89、P85.
自反闭包：r(R) = R U R 0
={<>,<>} U {<>,<>,<>,<>} ={<>,<>,<>,<>,<>,<>}
对称闭包：s(R) = R U R -1 = {<>,<>} U {<>,<>} = {<>,<>,<>,<>}
传递闭包：t(R) = 2 3U……
５. 设{1,2,3}{}，则从X 到Y 的不同的函数共有8个.
书P96，B 上A 的概念：
设Ａ、Ｂ为集合，所有从Ａ到Ｂ的函数构成集合ＢA ，读作“B 上A”
如果 = m ， = n ，m 、n 不全是0，则 =
即，若题中给出集合A 有m 个元素，B 有n 个元素，可直接用 计算出A 到B 的函数个数。本题中为23 = 8
６.设,,G 是群*∈，则（1）-1= a ，（*）-1= 1 * 1 。
书P139公式
7. 设{1，2，3}，f ：X→X ，g ：X→X ，{<1, 2>,<2,3>,<3,1>},
{<1,2>,<2,3>,<3,3>}，则ο{<1,3>,<2,1>,<3,1>}，ο{<1,3>,<2,3>,<3,2>}。
书P82-83
合成：ο = {<>∧}
需要说明的是，这里的合成ο是左复合，即G 先作用，然后将F 复合到G 上。之前的答案“有误”，因为采用了右复合。这两种合成定义所计算的合成结果是不相等的，但两个定义都是合理的，只要在体系内部采用同样的定义就可以了。总之，在咱们的离散里牢记左复合。
三、计算题（每题9分，共36分）
1. 设集合A ＝{1, 2, 3,4,5}，A 上的关系R ＝{<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3,
3>,<3,5>,<4,4>,<5,5>}
(1) 画出R 的关系图；
(2) 问R 具有关系的哪几种性质(自反、对称、传递、反对称).
自反性、传递性
书P87表格，根据关系图可直接判断性质……
(3) 给出R 的传递闭包。
{<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3, 3>,<3,5>,<4,4>,<5,5>}
R 2 = ο = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}
R 3 = R 2οR = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>} ……
