离散数学期末试卷A卷

离散数学考试试题（A 卷及答案）一、（10分）求(P ↓Q )→(P ∧⌝(Q ∨⌝R ))的主析取范式解：(P ↓Q )→(P ∧⌝(Q ∨⌝R ))⇔⌝(⌝( P ∨Q ))∨(P ∧⌝Q ∧R ))⇔(P ∨Q )∨(P ∧⌝Q ∧R ))⇔(P ∨Q ∨P )∧(P ∨Q ∨⌝Q )∧(P ∨Q ∨R )⇔(P ∨Q )∧(P ∨Q ∨R )⇔(P ∨Q ∨(R ∧⌝R ))∧(P ∨Q ∨R )⇔(P ∨Q ∨R )∧(P ∨Q ∨⌝R )∧(P ∨Q ∨R )⇔0M ∧1M⇔2m ∨3m ∨4m ∨5m ∨6m ∨7m二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。

乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。

试判断王教授是哪里人？解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。

则根据题意应有： 甲：⌝P ∧Q乙：⌝Q ∧P丙：⌝Q ∧⌝R王教授只可能是其中一个城市的人或者3个城市都不是。

所以，丙至少说对了一半。

因此，可得甲或乙必有一人全错了。

又因为，若甲全错了，则有⌝Q ∧P ，因此，乙全对。

同理，乙全错则甲全对。

所以丙必是一对一错。

故王教授的话符号化为：((⌝P ∧Q )∧((Q ∧⌝R )∨(⌝Q ∧R )))∨((⌝Q ∧P )∧(⌝Q ∧R ))⇔(⌝P ∧Q ∧Q ∧⌝R )∨(⌝P ∧Q ∧⌝Q ∧R )∨(⌝Q ∧P ∧⌝Q ∧R )⇔(⌝P ∧Q ∧⌝R )∨(P ∧⌝Q ∧R )⇔⌝P ∧Q ∧⌝R⇔T因此，王教授是上海人。

三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。

证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。

《离散数学》期末考试题(A)一、填空题(每小题3分，共15分)1.设}}{},,{{c b a A =，}}{},,{},{{c c b a B =，则)(=⋃B A ，)(=⋂B A ，)()(=A P .2.集合},,{c b a A =，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.3.命题公式1)(↑∧q p 的对偶式为( ).4.所有6的因数组成的集合为( ).5.不同构的5阶根树有( )棵.二、单选题(每小题3分，共15分)1.设A , B 是集合，若A B A =-，则(A)B = ∅ (B) A = ∅ (C)=⋂B A ∅ (D)A B A =⋂2.谓词公式)())()((x R y yQ x P x ∧∃→∀中量词x ∀的辖域为(A))())()((x R y yQ x P x ∧∃→∀ (B))()(y yQ x P ∃→(C))())()((x R y yQ x P ∧∃→ (D))()(y yQ x P ∃→和)(x R3.任意6阶群的子群的阶一定不为(A)4 (B)6 (C)2 (D)34.设n 是正整数，则有限布尔代数的元素个数为(A)2n (B)4n (C)n 2 (D)2n5.对于下列序列，可构成简单无向图的度数序列为(A)3, 3, 4, 4, 5 (B)0, 1, 3, 3, 3 (C)1, 1, 2, 2, 3 (D)1, 1, 2, 2, 2三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1. 设N N N :⨯→f ，)1,()(+=x x x f ，则f 是满射. () 2. 5男5女圆桌交替就座的方式有2880种. () 3. 设),(≤L 是格，对于L z y x ∈,,，若z x y x ⋅=⋅且z x y x +=+，则z y =. () 4. 任何树都至少2片树叶. ()5. 无向图G 有生成树的充要条件是G 为连通图. ( )四、(10分)设C B A ,,和D 是集合，证明)()()()(D B C A D C B A ⨯-⨯⊆-⨯-，并举例说明上式中不能将⊆改为 = .五、(15分)设N 是自然数集合，定义N 上的关系R 如下：y x R y x +⇔∈),(是偶数，1.证明R 是N 上的等价关系.2.求出N 关于等价关系R 的所有等价类.3.试求出一个N 到N 的函数f ，使得)}()(,N ,|),{(y f x f y x y x R =∈=.六、(10分)在实数集合R 中证明下列推理的有效性:因为R 中存在自然数，而所有自然数是整数，所以R 中存在整数.七、(10分)设R 是实数集合，令}0,R ,|),{(≠∈=a b a b a G ，定义G 上的运算如下: 对于任意G d c b a ∈),(),,(，),(),(),(b ad ac d c b a +=⋅，证明),(⋅G 是非Abel 群.八、(10分)若简单平面图G 的节点数7=n 且边数15=m ，则G 是连通图，试证明之.《离散数学》期末考试题(B)一、填空题(每小题3分，共15分)1.设,,},,{{b a b a A =∅}，则-A ∅ = ( )，-A {∅} = ( )，)(A P 中的元素个数=|)(|A P ( ).2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数.3.谓词公式))()(())()((y P y Q y x Q x P x ⌝∧∃∧→∀中量词x ∀的辖域为( ), 量词y ∃的辖域为( ).4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元.5.当n ( )时，n 阶完全无向图n K 是平面图，当n 为( )时，n K 是欧拉图.二、单选题(每小题3分，共15分)1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1-⋃R R 是A 上的(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立2.由2个命题变元p 和q 组成的不等值的命题公式的个数有(A)2 (B)4 (C)8 (D)163.设p 是素数且n 是正整数，则任意有限域的元素个数为(A)n p + (B)pn (C)n p (D)pn4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是(A)有界格 (B)分配格 (C)有补格 (D)布尔格5.3阶完全无向图3K 的不同构的生成子图有(A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( )2.命题联结词→不满足结合律. ( )3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“⋅8”的逆元为4. ( )4.整环不一定是域. ( )5.任何),(m n 平面图的面数2+-=n m r . ( )四、(10分)设B A f →:且C B g →:，若g f 是单射，证明f 是单射，并举例说明g 不一定是单射.五、(15分)设},,,{d c b a A =,A 上的关系)},(),,(),,(),,(),,(),,(),,(),,(),,{(c d b d a d c c b c a c c a b a a a R =,1.画出R 的关系图R G .2.判断R 所具有的性质.3.求出R 的关系矩阵R M .六、(10分)利用真值表求命题公式))(())((p q r r q p A →→↔→→=的主析取范式和主合取范式.七、(10分) 边数30<m 的简单平面图G ，必存在节点v 使得4)deg(≤v .八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.《离散数学》期末考试题(C)一、填空题(每小题3分，共15分)1. 若n B m A ==||,||，则=⨯||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个.2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3,1)}，则( )是单射，( )是满射，( )是双射.3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号).(1)q q p p →→∧)(；(2))(q p p ∨→；(3))(q p p ∧→；(4)q q p p →∨∧⌝)(；(5)q q p →→)(.4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).二、单选题(每小题3分，共15分)1. 设A , B , C 是集合，则下述论断正确的是( ).(A)若A ⊆ B ， B ∈ C ，则A ∈ C . (B)若A ⊆ B ， B ∈ C ，则A ⊆ C .(C)若A ∈ B ， B ⊆ C ，则A ∈ C . (D)若A ∈ B ， B ⊆ C ，则A ⊆ C .2. 设R ⊆ A ⨯ A ，S ⊆ A ⨯ A ，则下述结论正确的是( ).(A)若R 和S 是自反的，则R ⋂ S 是自反的.(B)若R 和S 是对称的，则S R 是对称的.(C)若R 和S 是反对称的，则S R 是反对称的.(D)若R 和S 是传递的，则R ⋃ S 是传递的.3.在谓词逻辑中，下列各式中不正确的是( ).(A))()())()((x xB x xA x B x A x ∀∨∀=∨∀(B))()())()((x xB x xA x B x A x ∀∧∀=∧∀(C))()())()((x xB x xA x B x A x ∃∨∃=∨∃(D)),(),(y x xA y y x yA x ∀∃=∃∀4. 域与整环的关系为( ).(A)整环是域 (B)域是整环 (C)整环不是域 (D) 域不是整环5.设G 是(n , m )图，且G 中每个节点的度数不是k 就是k + 1，则G 中度数为k 的节点个数为( ). (A)2n . (B)n (n + 1). (C)nk . (D)m k n 2)1(-+. 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1.设f : Z → Z ，x x x f 2||)(-=，则f 是单射. ( )2.设ϕ是群G 1到群G 2的同态映射，若G 1是Abel 群，则G 2是Abel 群. ( )3.设),(≤L 是格，对于L z y x ∈,,，若z x y x ⋅=⋅且z x y x +=+，则z y =. ( )4.元素个数相同的有限布尔代数都是同构的. ( )5.设G 是n (n ≥ 11)阶简单图，则G 或G 是非平面图. ( )四、(15分)设A 和B 是集合，使下列各式(1)A B A =⋂； (2)A B B A -=-；(3)A A B B A =-⋃-)()(成立的充要条件是什么，并给出理由.五、(10分) 设S 是实数集合R 上的关系，其定义如下∈=y x y x S ,|),{(R 且是3y x -是整数}， 证明: S 是R 上的等价关系. 六、(10分) 求谓词公式)))()(()(()(x xD y yC y B x xA ∀→∃⌝→→∃的前束范式.七、(10分) 若n 个人，每个人恰有3个朋友，则n 必为偶数，试证明之.八、(10分) 利用生成函数求解递归关系⎩⎨⎧=-+=-2)1(211a n a a n n .《离散数学》期末考试题(D)一、填空题(每小题3分，共15分)1. 设|A | = 5, |B | = 2, 则可定义A 到B 的函数( )个，其中有( )单射，( )个满射.2. 令G (x ): x 是金子，F (x ): x 是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ).3. 设X 是非空集合，则X 的幂集P (X )关于集合的⋃运算的单位元是( )，零元是( )，P (X )关于集合的⋂运算的单位元是( ).4. 不同构的5阶无向树有( )棵.5. 对于n 阶完全无向图K n , 当n 为( )时是Euler 图，当n ≥ ( )时是Hamilton 图，当n ( )时是平面图.二、单选题(每小题3分，共15分)1. 幂集P (P (P (∅))) 为( )(A){{∅}, {∅, {∅}}}. (B){∅, {∅, {∅}}, {∅}}.(C){ ∅, {∅, {∅}}, {{∅}}, {∅}} (D){ ∅, {∅, {∅}}}.2. 设R 是集合A 上的偏序关系，则1-⋃R R 是( ).(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对3. 下列( )组命题公式是不等值的.(A))(B A →⌝与B A ⌝∧. (B) )(B A ↔⌝与)()(B A B A ∧⌝∨⌝∧.(C))(C B A ∨→与C B A →⌝∧)(. (D))(C B A ∨→与)(C B A ∨∧⌝.4.下列代数结构(G , *)中，( )是群.(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法.(C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法.5.4阶完全无向图4K 中含3条边的不同构的生成子图有(A)3 (B)4 (C)5 (D)2三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1.函数的复合运算“ ”满足结合律. ( )2. {→⌝,}是最小功能完备联结词集合. ( )3. 实数集R 关于数的乘法运算“⋅”阿贝尔群. ( )4. 任意有限域的元素个数为2n . ( )5. 设G 是n (n 为奇数)简单图，则G 与G 中度数为奇数的节点个数相同. ( )四、(10分)设A 和B 是集合，使B B A =-成立的充要条件是什么，并给出理由.五、(10分) 设R 和S 是集合A 上的对称关系，证明S R 对称的充要条件是R S S R =.六、(15分)分别利用(1)等值演算法和(2)真值表求命题公式))(())((r q p p q r A ∨→→→∨⌝=的主析取范式和主合取范式.七、(10分) 设G 是(n , m )无向图，若n m ≥，证明G 中必存在圈.八、(10分) 在初始条件f (1) = c 下，求解递归关系bn n f n f +⎪⎭⎫ ⎝⎛=22)(，其中b ，c 为常数且kn 2=，k 为正整数.《离散数学》期末考试题(E)一、填空题(每小题3分，共15分)1.设A = {2, {3}, 4, a }, B = {1, 3, 4, {a }}, 则{3}( )A ，{a }( )B ，{{a }}( )B .2. 设A = {1, 2, 3, 4, 5}上的关系R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则=S R { }, =R S { }, =R R { }.3. gcd(36, 48) = ( )，lcm(36, 48) = ( ).4.任意有限布尔代数)1,0,,,,(⋅+B 均与集合代数( )同构，其元素个数为( ).5. 不同构的5阶无向树有( )棵，不同构的5阶根树有( )棵.二、单选题(每小题3分，共15分)1. 在有理数集合Q 上定义运算“*”如下：对于任意x , y ∈ Q ，y x * = x + y – xy ，则Q 关于*的单位元是( ).(A)x . (B)y . (C)1. (D)0.2. 设A = {1, 2, 3}, 下图分别给出了A 上的两个关系R 和S ，则S R 是( )关系.(A)自反. (B)对称. (C)传递. (D)等价.3.令T (x ): x 是火车，B (x ): x 是汽车，F (x , y ): x 比y 快，则“某些汽车比所有的火车慢”符号化为( ).(A)()()),()()(y x H x T x y B y →∀∧∃.(B)()()),()()(y x H x T x y B y ∧∀→∃.(C)()()),()()(y x H x T y B y x ∧→∃∀.(D)()()),()()(y x H x T x y B y →∀→∃.4. 整数集合Z 关于数的加法“+”和数的乘法“⋅”构成的代数结构(Z, +, ⋅)是( ). 1 1 22 3 3G S G R(A)域(B)域和整环(C)整环(D) 有零因子环G≅，则称G为自补图. 5阶不同构的自补图5.设G是简单图，G是G的补图，若G个数为( ).(A)0. (B)1. (C)2. (D)3.三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1. { ∅, {∅}} ∉P(P({∅})). ( )2. 非空1元及2元联结词集合的个数为29-1. ( )3. 群可分为Abel群和非Abel群. ( )4. 元素个数相同的有限域都是同构的. ( )5. 设G是简单图，则G或G是连通图. ( )四、(15分)设C,:, 若gf 是单射，证明f是单射，并举例说明g→:f→gBBA不一定是单射.五、(10分)设A = {a, b, c, d}上的关系R = {(a, b), (b, d), (c, c), (a, c)}, 画出R的关系图，并求出R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R).六、(10分)用CP规则证明下列推理.⌝∨→∨(.⇒),(⌝),→pqssrqrqp→七、(10分)求谓词公式))xyByAxA∀→∨∀∧⌝∃的前束范式.zC((x()))(z(()八、(10分)任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.《离散数学》期末考试题(F)一、填空题(每小题3分，共15分)1. 设A = {1, 2, 3, {1, 2}, {3}}, B = {2, {2,3}, {1}} , 则A–B = { }, B–A = { }, A⊕B = { }.2. 实数集合R关于加法运算“+”的单位元为( ), 关于乘法运算“⋅”的单位元为( ), 关于乘法运算“⋅”的零元为( ).3. 令Z(x): x是整数，O(x): x是奇数，则“不是所有整数都是奇数”符号化为( ).4. 有限域的元素个数为( ), 其中( )且( ).5. 设G 是(7, 15)简单平面图，则G 一定 ( )连通图，其每个面恰由( )条边围成，G 的面数为( ).二、单选题(每小题3分，共15分)1. 函数的复合运算“ ”满足( )(A)交换律. (B)结合律. (C)幂等律. (D)消去律.2. 设集合A 中有4个元素，则A 上的等价关系共有( )个.(A)13 (B)14 (C)15 (D)163.下列代数结构(G , *)中，( )是群.(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法.(C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法.4. 下列偏序集，( )是格.5. 不同构的(5, 3)简单无向图有( )个.(A)4 (B)5 (C)3 (D)2三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1. 设A ，B ，C 是集合，若C A B A ⊕=⊕, 则B = C . ( )2. 逻辑联结词“→”满足结合律. ( )3. 设 (L , ≤)是偏序集，若L 的任意非空子集均存在上确界和下确界，则(L , ≤)是格.( )4. 在同构意义下，有限布尔代数只有,,,),((⋂⋃X P ∅, X ). ( )5. 设G 是简单图，则G 与G 中度数为奇数的节点个数相同. ( )四、(15分) 设C B g B A f →→:,:, 若g f 是满射，证明g 是满射，并举例说明f 不一定是满射.五、(10分) 在整数集合Z 上定义关系R 如下：对于任意∈y x , Z ，y y x x R y x +=+⇔∈22),(.判断R 是否具有自反性、反自反性、对称性、反对称性及传递性.六、(10分)利用真值表求命题公式)())(q p q p A ⌝→↔→⌝=的主析取范式和主合取范式.七、(10分)证明：在至少两个人的人群中，必有两个人有相同个数的朋友.八、(10分)将6阶完全无向图K 6的边随意地涂上红色或蓝色，证明：无论如何涂法，总存在红色的K 3或蓝色的K 3.(ps ：答案见离散数学期末复习题（6套）答案文档)。

2020-2021《离散数学》期末课程考试试卷A一、填空题（每空3分，共15分）1．命题公式)(r q p p ∨∨→的类型是 。

2．设p ：我将去镇上。

q ：我有时间。

则命题“我将去镇上，仅当我有时间。

”的符号化形式为 。

3．化简下面集合表达式：)())((C B A C A B -= 。

4．已知一有向图的D 的度序列为（2,3,2,3），出度序列为（1,2,1,1），则D 的入度序列为 。

5．5个顶点的非同构的无向树共有 棵。

二、选择题（单项选择题，每题3分，共30分）1．设命题公式)(p q p ⌝→∧，记作A ，则使A 的真值指派为1的p ，q 的取值是（ ）。

A 、00B 、 01C 、10D 、112．设p ：你努力。

q ：你将失败。

则命题“除非你努力，否则你将失败。

”符号化为（ ）。

A 、p →q B 、q →p C 、┐p →q D 、┐q →p 3．下列公式中不与)(q p ↔⌝等值的是（ ）。

A 、)()(q p q p ∨⌝∧⌝∨B 、)()(q p q p ∧⌝∨⌝∧C 、q p ↔⌝D 、q p ⌝↔4．下面公式正确的是（ ）。

A 、)()())()((x xB x xA x B x A x ∀∨∀⇔∨∀ B 、)()())()((x xB x xA x B x A x ∃∨∃⇔∨∃C 、)())((x xB A x B A x ∃→⇔→∀D 、)()(x A x x xA ⌝∃⇔⌝∃5．下列命题错误的是（ ）。

A 、}},,{,,,{},{c b a c b a b a ⊆ B 、}},{,,,{},{b a c b a b a ∈ C 、}}},{{,,{},{b a b a b a ⊆D 、}}},{{,,{},{b a b a b a ∈6．设R={<x,y>|x,y ∈R ，x-y+2>0且x-y-2<0}，则R 具有的性质是（ ）。

--北京工商大学离散数学试卷(A)答案及评分标准题号 一 二三 四 五 六 七总分得分一、（30分）设A ={1,2,3,4}，给定A 上二元关系R 如下：R ={<1,1>, <1,2>, <2,3>, <3,3>, <4,4>}请回答以下各问题：1.写出R 的关系矩阵. （3分）2.画出R 的关系图. （3分）3.求包含R 的最小的等价关系，并写出由其确定的划分. （6分）4.分别用关系矩阵表示出R 的自反闭包r (R )、对称闭包s (R ). （6分）5.求传递闭包t (R ).（写出计算步骤）（6分）6.求R 2的关系矩阵. （3分）7.集合A 上最多可以确定多少个不同的二元关系？说明理由。

（3分）[解] (1)⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000010001000011R M 。

……（3分）（2） ……（3分）(3)法一：直接由等价关系与划分之间的一一对应可知，包含R 的最小等价关系为: {<1, 2>, <1, 3>, <2, 1>,<2, 3>, <3, 1> <3, 2>}∪I A , ……（3分） 对应的划分为{{1, 2, 3},{4}}. ……（6分） 法二：包含R 的最小的等价关系就是tsr (R ), 计算过程如下：⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=100001000110001110000100001000011000010001000011)(E M M R R r,100001100111001110000110001100011000010001100011][)()()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+=T R r R r R sr M M M ,3,10001110111011110000110011100111000011001110011)]([)()()]([2≥=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛⨯⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⨯=k M M M M k R sr R sr R sr R sr 从而,10000111011101111000011101110111100001110111011110000111011101111000011001110011432)]([)]([)]([)()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+++=R sr R sr R sr R sr R tsr M M M M M即}2,3,1,3,3,2,1,2,3,1,2,1{)(><><><><><><⋃=A I R tsr =包含R 的最小的等价关系， ……（3分） 故其对应的划分为{{1, 2, 3},{4}}. ……（6分） 法三：由于4=A ，包含R 的最小的等价关系就是4131211)()()()()()(----⋃⋃⋃⋃⋃⋃⋃⋃==R R R R R R R R I R rts R tsr A ,计算过程如下：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃100001100101001110000110000100011000010001000011][1TR R R R M M M ⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃10000111011101111000011001010011)][(22)(21T R R R R M M M412131)()(33)(10000111011101111000011001010011)][(---⋃⋃⋃==⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=R R R R T R R R R M M M M M 考试纪律承诺本人自愿遵守学校考试纪律，保证以诚信认真的态度作答试卷。

………密………封………线………以………内………答………题………无………效……电子科技大学英才学院2022 -2022学年第 1学期期 末 考试 A 卷离散数学 课程考试题 A 卷 〔 120分钟〕 考试形式：闭卷 考试日期 2022 年 月 日课程成绩构成：平时 分， 期中 分， 实验 分， 期末 100 分I.Multiple Choice (15%, 1.5 points each)〔A 〕 1. (p ∧q)→(p ∨q) is logically equivalent toa) T b) p ∨q c) F d) p ∧q〔A 〕 2. If P(A) is the power set of A, and A = ∅, what is |P(P(P(A)))|?a) 4 b) 24 c) 28 d) 216〔C 〕 3. Which of these statements is NOT a proposition?a) Today is Monday. ` b) 1+1=2.c) Am I right? d) Go and play with me.〔C 〕 4. Which of these propositions is not logically equivalent to the other three?a) (p → q) ∧ (r → q) b) (p ∨ r) → qc) (p ∧r) → q d) The contrapositive of ¬q → (¬p ^ ¬r)〔B 〕 5. Suppose | A | = 3 and | B | = 8. The number of 1-1 functions f : A → B isa) 24 b) P (8,3). c) 38 d) 83〔B 〕 6. Let R be a relation on the positive integers where xRy if x is a factor of y . Whichof the following lists of properties best describes the relation R ? a) symmetric, transitiveb) antisymmetric, transitive, reflexive c) antisymmetric, symmetric, reflexive d) symmetric, transitive, reflexive〔C 〕 7. Which of the following are partitions of },,,,,,,{h g f e d c b a U =?a)},,,,,{},,,{},{h g f e d c c b a a . b) },,,,,{},,{},{h g f e d c c b a c) }{},,{},,{},,,{h f e c b g d a . d) },,,,{},,{},,{h g f e d c b b a〔C 〕 8. The function f(x)=x 2log(x 3+78) is big-O of which of the following functions?a) x 2 b) x(logx)3 c) x 2logx d) xlogx〔A 〕 9.If 1010110111101101R ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦M , then R is: a) reflexive b) symmetric c) antisymmetric d) transitive.〔B 〕 10. Which of the followings is a function from Z to R ?………密………封………线………以………内………答………题………无………效……a) )1()(-±=n n f . ` b) 1)(2+=x x f . c) x x f =)( d) 21)(2-=n n fII. True or False (10%, 1 point each) 〔T 〕 1. If 1 < 0, then 5 = 6. 〔F 〕 2. (p ∧ q) ∨ r ≡ p ∧ (q ∨ r)〔F 〕 3. If A , B , and C are sets, then (A -C )-(B -C )=A -B . 〔T 〕 4. Suppose A = {a ,b ,c }, then {{a }} ⊆ P (A ).〔F 〕 5.()h x =is defined as a function with domain R and codomain R.〔T 〕 6. Suppose g : A → B and f : B → C , where f g is 1-1 and f is 1-1. g must be 1-1? 〔T 〕 7. If p and q are primes (> 2), then p + q is composite .〔F 〕 8.If the relation R is defined on the set Z where aRb means that ab > 0, then R is an equivalence relation on Z .〔T 〕 9. (A - B ) ⋃ (A - C ) = A - (B ⋂ C ).〔T 〕 10. The set{∅,{a },{∅},{a ,∅}} is the power set of some set III. Fill in the Blanks (20%, 2 points each)1. Let p and q be the propositions “I am a criminal 〞 and “I rob banks 〞. Express in simpleEnglish the proposition “if p then q 〞: If I am a criminal them I rob banks. 2. P (x ,y ) means “x + 2y = xy 〞, where x and y are integers. The truth value of ∃x ∀yP (x ,y )is False .3. T he negation of the statement “No tests are easy.〞 is some tests are easy.4. If 11{|}i A x x R x i i =∈∧-≤≤ then 1i i A +∞=is ∅.5. Suppose A = {x , y }. Then ()P A is {∅, {x}, {y},{x,y}}.6. Suppose g : A →A and f :A →A where A ={1,2,3,4},g = {(1, 4), (2,1), (3,1), (4,2)} andf ={(1,3),(2,2),(3,4),(4,2)}.Then fg ={(1,2),(2,3),(3,3),(4,2)}.7. The sum of 2 + 4 + 8 + 16 + 32 + ... + 210 is 211 - 2 .8. The expression of gcd(45, 12) as a linear combination of 12 and 45 is 12 ⋅ 4 + 45 ⋅ (1). 9.There are 5! permutations of the seven letters A,B ,C ,D ,E ,F have A immediately to the left of E .10. The two's complement of -13 is 1 0011 . IV. Answer the Questions (32%, 4points each)：1. Determine whether the following argument is valid:………密………封………线………以………内………答………题………无………效……p→rq→rq∨⌝r________∴⌝pAns: Not valid: p true, q true, r true2.Suppose you wish to prove a theor em of the form “if p then q〞.(a) If you give a direct proof, what do you assume and what do you prove?(b) If you give an indirect proof, what do you assume and what do you prove?(c) If you give a proof by contradiction, what do you assume and what do you prove? Ans: (a) Assume p, prove q.(b) Assume ⌝q, prove ⌝p.(c) Assume p∧⌝q, show that this leads to a contradiction.3.Prove that A B A B⋂=⋃by giving a proof using logical equivalence.Ans:()()()() A B x x A Bx x A Bx x A Bx x A x Bx x A x Bx x A x Bx x A x Bx x A B A B ⋂={|∈⋂}={|∉⋂}={|⌝∈⋂}={|⌝∈∧∈}={|⌝∈∨⌝∈}={|∉∨∉}={|∈∨∈}={|∈⋃}=⋃4.Suppose f:R→R where f(x) =⎣x/2⎦.(a) If S={x| 1 ≤x≤ 6}, find f(S).(b) If T={3,4,5}, find f-1(T). Ans: (a) {0,1,2,3}(b) [6,12).e the definition of big-oh to prove that5264473n nn+--is O(n3).………密………封………线………以………内………答………题………无………效……Ans: 5555322226446410573763n n n n n n n n n n +-+≤==--, if n ≥ 2. 6. Solve the linear congruence 5x ≡ 3 (mod 11).Ans: 5 + 11k .7. Use the Principle of Mathematical Induction to prove that 1311392732n n+-++++...+= for alln ≥ 0.Ans: P (0):13112-= , which is true since 1 = 1. P (k ) → P (k + 1):111211313123311333222k k k k k k ++++++--+⋅-++...+=+==.8．Encrypt the message NEED HELP by translating the letters into numbers, applying the encryption function f(p ) = (3p + 7) mod 26, and then translating the numbers back into letters.Ans: Encrypted form: UTTQ CTOA.V. (6%) Without using the truth table, show that the following are tautologiesa) [⌝p ∧(p ∨q)]→q b) [p ∧(p →q)]→qAns:a) ⌝p ∧(p ∨q)≡(⌝p ∧p)∨(⌝p ∧ q)≡flase[⌝p ∧(p ∨q)]→q ≡ false →q ≡⌝false ∨q ≡true ∨q ≡true (3points)b)[p ∧(p →q)]→q ≡(⌝[p ∧(⌝p ∨q)])∨q ≡(⌝p ∨(p ∧⌝q))∨q ≡((⌝p ∨p)∧(⌝p ∨⌝q))∨q ≡⌝p ∨⌝q ∨q ≡true (3points)VI. (6%) Devise an algorithm which will find the minimum of n integers. What is the worst case time………密………封………线………以………内………答………题………无………效……complexity of this algorithm?a) procedure min(a1, a2, …, an: integers)(4points)v := a1 {largest element so far}for i := 2 to n {go thru rest of elems}if ai < v then v := ai {found smaller?}{at this poi nt v’s value is the same as the smallest integer in the list}return vb) the worst case time complexity of this algorithm is O(n). (2points)VII.(5%) Give the definition of a transitive relation, and Prove or disprove that the union of two transitive relations is transitive.Ans: A relation R on a set A is called transitive if only if (a,b)∈R and (b,c)∈R ,then (a,c) ∈R ,for a,b,c ∈A. (2points)The union of two transitive relations may be not transitive. A counter-example:A={1,2,3}, R1= {<1,1>, <2,3>}, R2={<1,2><3,3> }R1∪R2={<1.1>, <2,3><1,2><3,3>}, which is not transitive. (3points)VIII.(6%) Give an argument using rules of inference to show that the conclusion follows from the hypotheses. List all the steps in your argument.Hypotheses: All computer scientists like Star Trek. Sarah does not like Star Trek. Therefore, Sarah is not a computer scientist.Solution:Hypotheses: ∀x(ComputerScientist(x) →Likes(x, StarTrek))¬Likes(Sarah, StarTrek)Conclusion: ¬ComputerScientist(Sarah)Step 1: ∀x(ComputerScientist(x) →Likes(x, StarTrek)) (Hypothesis)Step 2: ComputerScientist(Sarah) →Likes(Sarah, StarTrek) (Univ. Inst. Step 1)Step 3: ¬Likes(Sarah, StarTrek) (Hypothesis)Step 4: ¬ComputerScientist(Sarah) (Modus Toll. St. 2+3)The argument is sound.Grading rubric: -3 points for making wrong assumptions.-2 points for not being able to complete the proof.-1 to -3 points for illegal usage of inference rules.。

桂林电子科技大学试卷A学年第 学期 课号课程名称 离散数学（闭卷） 适用班级分钟 班级 学号 姓名考试时间 120一．单项选择题：（每小题2分，共12分）1．以下4个命题公式中，哪个是永真式？ （ ）A．p→(p→q)； B．(p→q)∨┓q→┓p；C．(p→q)∧┓q→┓p； D．┓(p↔┓p∨q)。

2．设P(x)表示“x在桂林上学”，Q(x)表示“x是桂林人”，则“在桂林上学的人未必是桂林人”可以表示为： （ ）A． x┓(P(x)→Q(x))； B．┓ x(P(x)→Q(x))；C． x(P(x)→┓Q(x))； D．┓ x(P(x)→┓Q(x))。

3．某个集合的元素个数为10，这个集合有多少个不同的子集？（ ）。

A．10； B．20； C．102； D．210。

4．设R为实数集，映射σ：R→R定义为σ(x)=2x－1，则σ是：（ ）A．单射而非满射； B．满射而非单射；C．双射； D．既不是单射，也不是满射。

5． 设R是实数集，C是复数集合，试问下列各个代数系统哪一个是交换群？（ ）A．<M（n×n；R），·>，其中M（n×n；R）是所有元素为实数的n×n 矩阵集，·是矩阵的普通乘法；B．<A，*>，其中A＝｛1，2，3，4，6，12｝，a*b为a与b的最大公约数，a，b∈A；C．<M（m×n；R），+>，其中M（m×n；R）是所有元素为实数的m×n矩阵集，+是矩阵的加法；D．<Z，+>，其中Z＝｛z|z∈C且z的实部为非负数｝，+是复数的加法。

6．给定有向图见下图，则其邻接矩阵是： （ ）V V 34A ．B ．C ．D ． 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 0二．填空题：（每个空2分，共16分）1．在谓词公式 x (∃w (P (x,w )∧P (x,y ))→(Q (x,y,z )∨Q (x,z,y )))中，约束变元为 ___________，自由变元为 __________。

浙江师范大学《离散数学》考试卷（2010—2011学年第 1 学期）考试形式闭卷使用学生软件工程、网络工程09考试时间120分钟出卷时间2010 年12 月26 日说明：考生应将全部答案都写在答题纸上，否则作无效处理。

一．选择题（每题2分，共20分）：1. 设P：我平时认真学习，Q：我通过离散数学考试，则如下哪种说法能符号化为P→Q：（）A．除非我平时认真学习，否则我不能通过离散数学考试。

B. 若我平时认真学习，则我通过离散数学考试。

C. 因为我平时不认真学习，所以我没有通过离散数学考试。

D. 我通过离散数学考试仅当我平时认真学习。

2．命题公式P→(P∨Q∨R) 为（）。

A．重言式B．可满足式C．矛盾式D．等值式3．设集合A={c, {c}}，下列命题错误的是（）。

A. {c}∈P(A)B. {c}⊆P(A)C. {{c}}∈P(A)D. {{c}}⊆P(A)4. 设f: N N, f(x)=(x) mod 5, 即x除以5的余数，则函数f （）.A. 仅单射B. 仅满射C. 双射D. 既不单设也不满射5．下列命题中正确的结论是：（）A．集合上A的关系如果不是自反的，就一定是反自反的；B．集合上A的关系如果不是对称的，就一定是反对称的；C．在任意关系R上，若<a, b>、<b, c>∈R，则必有<a, c>∈R；D．非空集合A上的恒等关系既是等价关系又是偏序关系6. 设集合A={a, b, c}，A上的关系R={<a, b>, <a, c>}，则下列结论错误的是：（）A．R-1 = {<b, a>, <c, a>}； B. r(R) = R；C．s(R) = {<a, b>, <a, c>, <b, a>, <c, a>}； D. t(R) = R7．设集合A 和二元运算*，可交换的代数运算是（ ）。

2 离散数学（A 卷） 王军东（答案写在答题纸上，写在试题纸上无效）一、单项选择题（每小题3分，共30分）1．设A , B 是集合，若A B A =-，则(A) B = ∅ (B) A = ∅ (C) =⋂B A ∅ (D) A B A =⋂2．在有理数集合Q 上定义运算“*”如下：对于任意x , y ∈ Q ，y x * = x + y – xy ，则Q 关于*的单位元是( ).(A)x . (B)y . (C)1. (D)0.3．谓词公式)())()((x R y yQ x P x ∧∃→∀中量词x ∀的辖域为(A))())()((x R y yQ x P x ∧∃→∀ (B))()(y yQ x P ∃→(C))())()((x R y yQ x P ∧∃→ (D))()(y yQ x P ∃→和)(x R4．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( )(A) ⌝ p ∧⌝ q (B) ⌝ p ∨⌝ q (C) ⌝ (p ↔ q ) (D) ⌝ (⌝ p ∨⌝ q ).5．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ）A ．仅是单射B ．仅是满射C ．是双射D ．不是函数6. 设集合A = {1, 2, 3, 4, 5}上的关系R = {(x , y )|x , y ∈ A 且x + y = 6}，则R 的性质是( ).(A) 自反的. (B) 对称的. (C) 对称的、传递的. (D) 反自反的、传递的.7. 下列联结词中，不满足交换律的是( ).(A)∧. (B)∨. (C)⊕. (D) →.8．.设G 是n 阶简单无向图，则其最大度)(G ∆( ).(A) > n (B) ≤ n . (C) < n . (D) ≥ n .9. 下列所示的哈斯图所对应的偏序集中能构成格的是（ ）A ．B ．C ．D ．课程考试试题学期 学年 拟题人:校对人:拟题学院（系）: 适 用 专 业:10. 设G 是(n , m )图，且G 中每个节点的度数不是k 就是k + 1，则G 中度数为k 的节点个数为( ). (A)2n . (B)n (n + 1). (C)nk . (D)m k n 2)1(-+. 二、填空题(每空3分，共30分)1．设A={1，2}，B={2，3}，则A-B=_______， A ⊕B=________，2．设A={2,3 }，R ⊆A ×A ，R={(2,3)， (2,2)}，则R 的自反闭包r(R)=__________,对称闭包s(R)=__________。

学年第二学期期末考试《离散数学》试卷（ A ）使用班级：命题教师：主任签字：一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( )A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )A.10B.12C.16D.143.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( )A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( )A.〈Z，+，/〉B.〈Z，/〉C.〈Z，-，/〉D.〈P(A)，∩〉6.下列各代数系统中不含有零元素的是( )A.〈Q，*〉Q是全体有理数集，*是数的乘法运算B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,∀x,y∈ZD.〈Z，+〉，Z是整数集，+是数的加法运算7.设A={1,2,3}，A上二元关系R的关系图如下：R具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )A.R∪I AB.RC.R∪{〈c,a〉}D.R∩I A9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}10.下列式子正确的是( )A. ∅∈∅B.∅⊆∅C.{∅}⊆∅D.{∅}∈∅11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R下为真的是( )A.( ∀x)( ∀y)( ∀z)(A(x,y))→A(f(x,z),f(y,z))B.( ∀x)A(f(a,x),a)C.(∀x)(∀y)（A(f(x,y),x))D.(∀x)(∀y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(∀x)(A(x)→B)等价于( )A.(∃x)A(x)→BB.(∀x)A(x)→BC.A(x)→BD.(∀x)A(x)→(∀x)B13.谓词公式(∀x)(P(x,y))→(∃z)Q(x,z)∧(∀y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q15.以下命题公式中，为永假式的是( )A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。

离散数学考试试题(A 卷及答案)一、 (10 分)判断下列公式的类型(永真式、永假式、可满足式)？1)((P Q)∧Q)一 ((Q∨R)∧Q) 2)((Q P)∨P)∧ (P∨R)3)((P∨Q)R)((P∧Q)∨R)解： 1)永真式； 2) 永假式； 3)可满足式。

二、 (8 分) 个体域为{1， 2}，求x3y (x+y=4)的真值。

解：x3y (x+y=4) 一 x ((x+1=4)∨(x+2=4))一((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+1=4))一(0∨0)∧(0∨1)一1∧1一0三、 (8 分) 已知集合 A 和 B 且|A|=n， |B|=m，求 A 到 B 的二元关系数是多少？ A 到 B 的函数数是多少？解：因为|P(A×B) |=2|A×B|=2|A| |B|=2mn，所以 A 到 B 的二元关系有 2mn 个。

因为|BA|= |B| |A|=mn，所以 A 到 B 的函数 mn 个。

四、 (10 分) 已知 A={1,2,3,4,5}和 R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求 r(R) 、s(R)和 t(R)。

解： r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>}t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}五、 (10 分) 75 个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20 人这三种东西都乘过，其中 55 人至少乘坐过其中的两种。

离散数学课程期末考试试卷（第 A 卷）考试专业班级信息09101、09102班考试形式闭卷考试时间 120 分钟考试学期 2010年下学期考试类型考试命题教师席金菊题号一二三四五六七八总分分值20 20 40 20 0 0 0 0 100一、选择题 (总共20 分,每小题2分)1.设G是n个结点、m条边和r 个面的连通平面图，则m等于（）。

A、n+r-2 ；B、n-r+2 ；C、n-r-2 ； D 、n+r+2 。

2.设L(x)：x是演员，J(x)：x是老师，A(x , y)：x 钦佩y，命题“所有演员都钦佩某些老师”符号化为（）。

A 、； B、；C、；D、3.设K = {e , a , b , c}，是Klein四元群，则元素a的逆元为（）。

A、e ；B、a ；C、b ；D、c。

4.设，下列各式中（）是正确的。

domS B ； B 、domS A； C、ranS A； D、domS ranS = S 。

5.下面是前缀编码的是（）A. 00,10,110,011B. 10, 000, 101, 01C.111,000,110,11D.010,110,01,1016.设<A ，+ ，·>是一代数系统，+、·为普通加法和乘法运算，当A为（）时，<A ，+ ，·>是域。

A、；B、；C、；D、。

7.下列问题成立的有（）。

A、若，则； B、若，则；C、若，则；D、若，则。

8.设集合A，B是有穷集合，且，则从A到B有（）个不同的双射函数。

A、；B、；C、；D、。

9.设<A, >是一个格，由格诱导的代数系统为，则（）成立。

A、；B、；C、；D、。

10.下列表达式正确的有（）A、；B、；C、；D、。

二、填空题 (总共20 分,每空2分)1.设p：我生病，q：我去上课，命题“我虽然生病但我还是去上课”符号化为：（）。

2.设|A|=3，则A上有（）个二元关系。

2020-2021《离散数学》期末课程考试试卷A2专业: 考试日期： 所需时间：120分钟 总分：100分 闭卷 一、选择题（每小题3分，总共30分）1、设P ：我们划船，Q ：我们跑步。

命题“我们不能既划船又跑步”符号化为（ ）A 、Q P ⌝∧⌝B 、Q P ⌝∨⌝C 、)(Q P ↔⌝D 、)(Q P ⌝↔ 2、下列语句中哪个是真命题？（ ）A 、我正在说谎。

B 、严禁吸烟C 、如果1+2=3，那么雪是黑的。

D 、如果1+2=5，那么雪是黑的。

3、命题公式Q Q P P →→∧))((是（ ）A 、矛盾式B 、蕴含式C 、重言式D 、等值式4、谓词公式)())()((x Q y yR x P x →∃∨∀中变元x 是（ ） A 、自由变量 B 、约束变量 C 、既不是自由变量也不是约束变量 D 、既是自由变量也是约束变量5、若个体域为整数域，下列公式中哪个值为真？（ ）A 、)0(=+∃∀y x y xB 、)0(=+∀∃y x x yC 、)0(=+∀∀y x y xD 、)0(=+∃⌝∃y x y x6、设个体域A={a,b},公式)()(x xS x xP ∃∧∀在A 中消去量词应为（ ） A 、)()(x S x P ∧ B 、))()(()()(b S a S b P a P ∨∧∧ C 、)()(b S a P ∧ D 、)()()()(b S a S b P a P ∨∧∧8、设A={{1，2，3}，{4，5}，{6，7，8}}，下列正确的是（ ） A 、1∈A B 、{1，2，3}⊆A C 、{{4，5}}⊂A D 、Φ∈A 9、幂集P （P （P （Φ）））为（ ）A 、{{Φ}，{Φ，{Φ}}}B 、{Φ，{Φ}，{Φ，{Φ}}}C 、{Φ，{Φ}，{Φ，{Φ}}，{{Φ}}}D 、{Φ，{Φ，{Φ}}}10、任意一个具有多个等幂元的半群，它（ ）A 、不能构成群B 、不一定能构成群C 、能构成群D 、不能构成交换群 二、填空题（每小题2分，总共16分）1、对于前提：S Q ⌝→，S ∨R ，R ⌝，Q P ↔⌝，其有效结论为2、谓词公式)()()(y yR x xQ x xP ∃∨∀→∀的前束范式为3、设集合A={x|x <3,x ∈Z},B={x|x=2k,k ∈Z} C={1,2,3,4,5},则 A ⊕（C-B ）=4、某校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，其中只有3人同时参加3种球队，则仅仅参加两种球队的队员为 人 。

离散数学期末试卷《离散数学》期末考试试卷（a卷）---------------------------------------------------------------------------------------------------------------------------------------------------03.a？{？，{a}，{B}，{a，B}上的包含关系是？，那么C子集呢？{a}，{B}的最大元素是＿＿＿＿，极小元为＿＿＿＿，上界为＿＿＿＿，下界为＿＿＿＿，最大元为＿＿＿，最小元为＿＿＿（若没有填无）。

04．设a?{a,b}，则a上共有＿＿＿个不同的等价关系。

有一个函数f:x吗？y、要使F有一个反函数，F必须是。

三、演算题（每小题10分，总30分）年级专业名称学生人数座位号大登一、单选题（从备选答案中选择正确答案，并将其数字填入题干后的括号中。

每个问题得3分，共18分）01。

在下面的句子中，真正的命题是（）a、我正在说谎；b、若1?2?3，则雪是黑的；c、这句话是错的；d、若1?2?5，则太阳绕地球转。

02．下列哪个公式是永真式（）a、（p？q）？（q？p）；b、（p？q）？p、c、（（p？q））？（？（？p？？q））；d、？（p？q）03．对任意集合a，b，c，下列结论正确的是（）a、如果是？b、 b？c、然后是a？c、 b.如果a？b、 b？c、然后是a？c、 c.如果a？b、 b？c、然后是a？c、 d.如果a？b、 b？c、然后是a？c、 04.a？{1,2,3}上的关系r？{?1,1?,?1,2?,?1,3?,?3,3?}，然后r有（a）、及物性和反对称性；b、及物性和对称性；c、自反性和对称性；d、反自反性和对称性。

05.在以下四个集合中，属于拟序集合的是（）a和？？（{a}）B（n） C（n） D(?),??。

06.在下列集合中，等于C的基数是（）a，{0,1,2，…，n？1}；b、 n；c、n？n、 d、[2,4]二、填空题（以下每个下划线为一空，请按要求填入合适的内容。

2006-2007《离散数学》期末试题A单项选择题：（每⼩题2分，共30分）1．下列语句是命题的有（）。

[A] 明年中秋节的晚上是晴天； [B] 0x y +>；[C] 0xy >当且仅当x 和y 都⼤于0；[D] 我正在说谎。

2．下列命题真值为真者（）[A] 若3+3=6则雪是⿊的 [B]2是⽆理数当且仅当印度位于⾮洲[C]“2或4是素数，这是不对的”是不对的[D] 只有2能被4整除，2才能被2整除3．设A={1 ,2 ,3 }，则A 上有（）个⼆元关系。

A 、23 ；B 、32 ；C 、322；D 、232。

4．在下述公式中是重⾔式为（）A ．)()(Q P Q P ∨→∧；B ．))()(()(P Q Q P Q P →∧→??；C ．Q Q P ∧→?)(；D ．)(Q P P ∨→。

5．命题公式 )()(P Q Q P ∨?→→? 中成真赋值的个数为（）。

A ．0；B ．1；C ．2；D ．3 。

6．下列等价关系正确的是（）。

A 、(()())()()x P x Q x xP x xQ x ?∨??∨?；B 、(()())()()x P x Q x xP x xQ x ?∨??∨?；C 、(())()x P x Q xP x Q ?→??→；D 、(())()x P x Q xP x Q ?→??→。

7．令x x F :)(是飞机，y y G :)(是⽕车，x y x H :),(⽐y 跑得快，则公式：))),()(()((y x H y G y x F x →?∧?的含义是（）[A]并不是所有的⽕车都⽐汽车跑得快[B]有的⽕车⽐所有的汽车跑得快 [C]不存在跑得⼀样快的⽕车与汽车[D]⽕车⽐汽车跑得快 8．公式),,(),,(z y x yG z y x xF ?→?中既呈约束出现⼜呈⾃由出现的变元是（）[A]z x , [B]z y , [C]z [D]y x , 9．全体⼩项合取式为（）。