离散数学期末考试题

《离散数学》期末考试题(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套）答案文档)。

一．判断题（共10小题，每题1分，共10分）在各题末尾的括号内画 表示正确，画 表示错误：1．设p、q为任意命题公式，则(p∧q)∨p ⇔ p ( )2．∀x(F(y)→G(x)) ⇔ F(y)→∃xG(x)。

( )3．初级回路一定是简单回路。

( )4．自然映射是双射。

( )5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。

( )6．群的运算是可交换的。

( )7．自然数集关于数的加法和乘法<N，+， >构成环。

( )8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。

( )9．设A={a,b,c},则A上的关系R={<a,b>,<a,c>}是传递的。

( )10．设A、B、C为任意集合，则A⨯(B⨯C)=(A⨯B)⨯C。

( )二、填空题（共10题，每题3分，共30分）11．设p：天气热。

q：他去游泳。

则命题“只有天气热，他才去游泳”可符号化为。

12．设M(x)：x是人。

S(x)：x到过月球。

则命题“有人到过月球”可符号化为。

13．p↔q的主合取范式是。

14．完全二部图K r,s（r < s）的边连通度等于。

15．设A={a,b}，,则A上共有个不同的偏序关系。

16．模6加群<Z6，⊕>中，4是阶元。

17．设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，则R的传递闭包t(R) = 。

.18．已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的入度列为。

19．n阶无向简单连通图G的生成树有条边。

20．7阶圈的点色数是。

三、运算题（共5小题，每小题8分，共40分）21．求∃xF(x)→∃yG(x,y)的前束范式。

22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。

一．填空题（每小题2分，共10分）1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。

2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____，=A _____，=B A __ _____3. 设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__ __________，=-)()(A B ρρ_____ ______。

二．选择题（每小题2分，共10分）1. 与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=,A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 三．计算题（共43分）1. 求命题公式r q p ∨∧的主合取范式与主析取范式。

（6分）2. 设集合{}d c b a A ,,,=上的二元关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000000011010001R M ,求)(),(),(R t R s R r 的关系矩阵，并画出R ，)(),(),(R t R s R r 的关系图。

（10分）5. 试判断),(≤z 是否为格？说明理由。

（5分）（注：什么是格？Z 是整数，格：任两个元素，有最小上界和最大下界的偏序）四．证明题（共37分）1. 用推理规则证明D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(,。

（10分）2. 设R 是实数集，b a b a f R R R f +=→⨯),(,:，ab b a g R R R g =→⨯),(,:。

求证：gf 和都是满射，但不是单射。

（10分）一，1, _∃x∃y¬P(x)∨Q(y)2, {2} {4,5} {1,3,4,5}3, {{c},{a,c},{b,c},{a,b,c}} Φ_二，B D三，解：主合取方式：p∧q∨r⇔(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r⇔(p∧q∧r) ∨(p∧q∧¬r)∨(¬p∧q∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q ∧r)=∑1.3.5.6.7四，1，证明：编号公式依据（1）（¬B∨C）∧¬C前提（2）¬B∨C，¬C（1）（3）¬B（2）（4）A→B （3）（5）¬A（3）（4）（6）¬（¬A∧D）前提（7）A∨¬D（6）（8）¬D（5）（6）2，证明：要证f是满射，即∀y∈R,都存在（x1，x2）∈R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；再证g是满射，即∀y∈R，,都存在（x1，x2）∈R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g（x1，x2）=g（x2，x1），取x1≠x2，即证得。

一、单项选择题（每小题3分，共30分）1．下列为两个命题变元ｐ，ｑ的最小项的是（ ） A ．ｐ∧ｑ∧⎤ ｐB ．⎤ ｐ∨ｑC ．⎤ ｐ∧ｑD ．⎤ ｐ∨ｐ∨ｑ 2．下列句子不是命题的是（ ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的D ．太好了！3．对于公式(∀x ) (∃y )(P (x )∧Q (y ))→(∃x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元C ．(∃x )的辖域是R(x , y )D ．(∀x )的辖域是(∃y )(P (x )∧Q (y ))→(∃x )R (x ,y )4．7．集合A={1，2，…，10}上的关系R={（x ，y ）|x +y =10，x ∈A ，y ∈A}，则R 的性质是（ ）A ．自反的B ．对称的C ．传递的、对称的D ．反自反的、传递的 5．设论域为{l ，2}，与公式)(x xA ∃等价的是( ) A.A (1)∨A (2)B. A (1)→A (2)C.A (1)D. A (2)→A (1)6. 下列关系矩阵所对应的关系具有反自反性的是（ ） A ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001110101B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101100001 C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100100D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0010101017. 下列运算不满足．．．交换律的是（ ） A ．a *b =a+2bB ．a *b =min(a ,b )C ．a *b =|a -b |D ．a *b =2ab8．.设A 是奇数集合，下列构成独异点的是( ) A.<A ，+> B.<A ，-> C.<A ，×> D.<A ，÷> 9. 右图的最大入度是( ) A ．0 B ．1 C ．2D ．3第9题图拟题学院（系）： 高密校区 适用专业： 学年 2学期 离散数学 （Ｂ卷） 试题标准答案10. 设有向图D 的节点数大于1，D=（V ,E ）是强连通图，当且仅当（ ） A. D 中至少有一条通路 B. D 中至少有一条回路C. D 中有通过每个结点至少一次的通路D. D 中有通过每个结点至少一次的回路 二、填空题(每空3分，共30分)1．设A ={1，2，3，4}，B ={2，4，6}，则A -B =________，A ⊕B =________。

离散数学复习注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。

2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。

把大纲中指定的例题及书后习题认真做一做。

检验一下主要内容的掌握情况。

3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。

离散数学综合练习题一、选择题1．下列句子中，（）是命题。

A．2是常数。

B．这朵花多好看呀！C．请把门关上！D．下午有会吗？2．令p: 今天下雪了，q:路滑，r:他迟到了。

则命题“下雪路滑，他迟到了”可符号化为（）。

A. p q r∨→∧→ B. p q rC. p q r∨↔∧∧ D. p q r3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。

A.p q∧∧⌝ B.p qC.p q→⌝∨⌝ D. p q4．设()Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。

P x:x是鸟，()A. ()(()())Q x⌝∀∧())x P x Q x⌝∀→ B. ()(()x P xC. ()(()())Q x⌝∃∧())x P x Q x⌝∃→ D. ()(()x P x5.设()L x y：x大于等于y；命题“所有整数f x:x的绝对值，(,)P x:x是整数，()的绝对值大于等于0”可符号化为（）。

A. (()((),0))∀→x P x L f x∀∧B. (()((),0))x P x L f xC. ()((),0)∀→xP x L f x∀∧ D. ()((),0)xP x L f x6.设()F x:x是人，()G x:x犯错误，命题“没有不犯错误的人”符号化为（）。

A．(()())⌝∃→⌝x F x G x∀∧B．(()())x F x G xC．(()())⌝∃∧⌝x F x G x⌝∃∧D．(()())x F x G x7.下列命题公式不是永真式的是（）。

一、填空2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 (B ⊕C)-A4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为 )()(R S P R S P ∨⌝∨⌝∧∨∨⌝ 。

5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为 1 。

6．设A={1，2，3，4}，A 上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。

//备注：⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000100001010010R⎪⎪⎪⎪⎪⎭⎫⎝⎛=00000000101001012R7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图如下，则R= {(a,b),(a,c), (a,d), (b,d), (c,d)} U {(a,a),(b,b)(c,c)(d,d)} 。

//备注：偏序满足自反性，反对称性，传递性8．图的补图为 。

//补图:给定一个图G ,又G 中所有结点和所有能使G 成为完全图的添加边组成的图,成为补图. 自补图:一个图如果同构于它的补图,则是自补图 9．设A={a ，b ，c ，d} ，A 上二元运算如下：* a b c d a b c da b c d b c d a c d a b d a b c那么代数系统<A ，*>的幺元是 a ，有逆元的元素为 a,b,c,d ，它们的逆元分别为 a,b,c,d 。

//备注：二元运算为x*y=max{x,y}，x,y ∈A 。

10．下图所示的偏序集中，是格的为 c 。

//（注：什么是格？即任意两个元素有最小上界 和最大下界的偏序）二、选择题1、下列是真命题的有（ C 、D ）A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ．}},{{ΦΦ∈Φ； D ．}}{{}{Φ∈Φ。

2、下列集合中相等的有（ B 、C ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。

一、选择题（每题2分，共20分）1. 下列命题中，正确的是（）A. 逻辑真命题一定是逻辑假命题B. 逻辑假命题一定是逻辑真命题C. 逻辑真命题和逻辑假命题都是存在的D. 逻辑真命题和逻辑假命题都不存在2. 设A和B是两个集合，则下列命题中正确的是（）A. A∩B = A∪BB. A∩B = A-BC. A∪B = A∩BD. A-B = A∩B3. 设A和B是两个集合，则下列命题中正确的是（）A. A⊆B当且仅当A∩B = AB. A⊆B当且仅当A∩B = BC. A⊆B当且仅当A-B = ∅D. A⊆B当且仅当A∪B = B4. 下列命题中，不是逻辑等价命题的是（）A. A→B与¬A∨BB. A∧B与A→BC. A∨B与B→AD. A→B与¬B∨A5. 设R是一个关系，下列命题中正确的是（）A. R是等价关系当且仅当R是自反的、对称的和传递的B. R是等价关系当且仅当R是自反的、非对称的和传递的C. R是等价关系当且仅当R是非自反的、对称的和传递的D. R是等价关系当且仅当R是非自反的、非对称的和传递的6. 设P和Q是两个命题，则下列命题中正确的是（）A. P∧Q的否定是P∨QB. P∧Q的否定是P∧QC. P∨Q的否定是P∧QD. P∨Q的否定是P∧Q7. 设R是一个偏序关系，下列命题中正确的是（）A. R是自反的、反对称的和传递的B. R是自反的、对称的和传递的C. R是自反的、非对称的和传递的D. R是非自反的、对称的和传递的8. 设R是一个全序关系，下列命题中正确的是（）A. R是自反的、反对称的和传递的B. R是自反的、对称的和传递的C. R是自反的、非对称的和传递的D. R是非自反的、对称的和传递的9. 设R是一个函数，下列命题中正确的是（）A. R是单射当且仅当R是满射B. R是单射当且仅当R是自反的C. R是满射当且仅当R是自反的D. R是单射当且仅当R是反对称的10. 设R是一个关系，下列命题中正确的是（）A. R是等价关系当且仅当R是自反的、对称的和传递的B. R是等价关系当且仅当R是自反的、非对称的和传递的C. R是等价关系当且仅当R是非自反的、对称的和传递的D. R是等价关系当且仅当R是非自反的、非对称的和传递的二、填空题（每题2分，共20分）1. 在集合A={1, 2, 3}中，A的子集个数是______。

数理逻辑一、选择题。

1、下列选项中是原子命题的是（)A、霍金去世了。

B、霍金是物理学家，也是科普作家。

B、霍金的《时间简史》你看过吗？D、我看过《时间简史》，但没有看懂。

2、下列命题中，（）不是真命题。

A、海水是咸的当且仅当雪是白色的B、如果1+1=2，那么7+8＞16C、若太阳从西边落下，则2是奇数D、夏天冷当且仅当冬天热3、下列句子不是命题的是（）A.雪是黑色的。

B.江西师大是一座工厂。

C.好大的雪啊！D.若7+8＞16，则三角形有4条边。

4、下列句子是命题的是（）A.我正在说谎。

B.X < 0。

C.好大的雪啊！D.如果x大于3，则x2大于9。

5、下列句子是命题的是（）A.我正在说谎。

B.X < 0。

C.好大的雪啊！D.如果x大于3，则x2大于9。

6、下列联结词中不是完备的是（）A、{,,⌝∨∧} B、{,⌝∨} C、{,∨∧} D、{,⌝∧}7、下列选项中哪一个是复合命题？（)x>。

A、我不去看电影。

B、如果3x>，那么29C、我正在说谎。

D、把大象放进冰箱需要多少步？8、公式()P Q RP Q R=（）→⌝∨的成假解释是(,,)B、(,,)T F FT F T D、(,,) T T T B、(,,)T T F C、(,,)9、下列选项中是合式公式的是（)A 、3a b c ++=B 、P Q R <+C 、R Q P ∧⌝D 、R Q P ∧∨⌝10、下列公式不是永真公式的是（ ）C 、P P → B 、P P ↔ C 、 P P ∨⌝D 、P P ∧⌝ 11、下列公式 ( )为重言式．A ．⌝P ∧⌝Q ↔P ∨QB ．(Q →(P ∨Q)) ↔(⌝Q ∧(P ∨Q))C ．(P →(⌝Q →P))↔(⌝P →(P →Q))D ．(⌝P ∨(P ∧Q)) ↔Q12、 设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))13、下列是真命题的有（ ）A 、；B 、；C 、；D 、。

离散数学期末复习题第一章集合论一、判断题（1）空集是任何集合的真子集． （ 错 ）（2）{}φ是空集． （ 错 ） （3）{}{}a a a },{∈ （ 对 ） （4）设集合{}{}{}{}AA 22,1,2,1,2,1⊆=则. ( 对 ） （5）如果B A a ⋃∉，则A a ∉或B a ∉． （ 错 ）解 B A a ⋃∉则B A B A a ⋂=⋃∈，即A a ∈且B a ∈，所以A a ∉且B a ∉（6）如果A ∪.,B A B B ⊆=则 （ 对 ）（7）设集合},,{321a a a A =，},,{321b b b B =，则},,,,,{332211><><><=⨯b a b a b a B A （ 错 ）（8）设集合}1,0{=A ，则}1},0{,0},0{,1,,0,{><><><><=φφρ是A2到A 的关系． （ 对 ）解 A 2}},1{},0{,{A φ=， =⨯A A 2}1,,0,,1},1{,0},1{,1},0{,0},0{,1,,0,{><><><><><><><><A A φφ（9）关系的复合运算满足交换律． （ 错 ）（10）.条件具有传递性的充分必要上的关系是集合ρρρρA = （ 错 ）（11）设.~,上的传递关系也是则上的传递关系是集合A A ρρ ( 对 ) （12）集合A 上的对称关系必不是反对称的. （ 错 ）（13）设21,ρρ为集合A 上的等价关系, 则21ρρ⋂也是集合A 上的等价关系( 对 )（14）设ρ是集合A 上的等价关系, 则当ρ>∈<b a ,时， ρρ][][b a = ( 对 )（15）设21,ρρ为集合 A 上的等价关系, 则 ( 错 )二、单项选择题（1）设R 为实数集合，下列集合中哪一个不是空集 （ A ）A. {}R x x x ∈=-且,01|2 B ．{}R x x x ∈=+且,09|2C. {}R x x x x ∈+=且,1|D. {}R x x x ∈-=且,1|2（2）设B A ,为集合，若φ=B A \，则一定有 （ C ）A. φ=B B ．φ≠B C. B A ⊆ D. B A ⊇（3）下列各式中不正确的是 （ C ）A. φφ⊆ B ．{}φφ∈ C. φφ⊂ D. {}}{,φφφ∈ （4）设{}}{,a a A =，则下列各式中错误的是 （ B ）A. {}A a 2∈ B ．{}A a 2⊆ C. {}A a 2}{∈ D. {}Aa 2}{⊆ （5）设{}2,1=A ，{}c b a B ,,=，{}d c C ,=，则)(C B A ⨯为 （ B ） A. {}><><c c ,2,1, B ．{}><><c c ,2,,1C. {}><><2,,,1c cD. {}><><2,,1,c c（6）设{}b A ,0=，{}3,,1b B =，则B A 的恒等关系为 （ A ） A. {}><><><><3,3,,,1,1,0,0b b B ．{}><><><3,3,1,1,0,0C. {}><><><3,3,,,0,0b bD. {}><><><><0,3,3,,,1,1,0b b（7）设{}c b a A ,,=上的二元关系如下，则具有传递性的为 （ D ）A. {}><><><><=a b b a a c c a ,,,,,,,1ρB ． {}><><=a c c a ,,,2ρC. {}><><><><=c b a b c c b a ,,,,,,,3ρD. {}><=a a ,4ρ（8）设ρ为集合A 上的等价关系，对任意A a ∈，其等价类[]ρa 为 （ B ）A. 空集； B ．非空集； C. 是否为空集不能确定； D. }|{A x x ∈.（9）映射的复合运算满足 （ B ）A. 交换律 B ．结合律 C. 幂等律 D. 分配律（10）设A ，B 是集合，则下列说法中（ C ）是正确的.A ．A 到B 的关系都是A 到B 的映射B ．A 到B 的映射都是可逆的C ．A 到B 的双射都是可逆的D ．B A ⊂时必不存在A 到B 的双射（11）设A 是集合，则（ B ）成立.A ．A A #22#=B ．A X X A⊆↔∈2 C ．{}A2∈φ D ．{}AA 2∈ （12）设A 是有限集（n A =#），则A 上既是≤又是～的关系共有（B ）.A ．0个B ．1个C ．2个D ．n 个三、填空题1. 设}}2,1{,2,1{=A ，则=A2____________.填}}},2,1{,2{}},2,1{,1{},2,1{}},2,1{{},2{},1{,{2A A φ=2.设}}{,{φφ=A ，则A 2= . 填}}},{{},{,{2A A φφφ=3.设集合B A ,中元素的个数分别为5#=A ，7#=B ，且9)(#=⋃B A ，则集合B A ⋂中元素的个数=⋂)(#B A .34.设集合}4,1001|{Z x x x x A ∈≤≤=的倍数，是，}5,1001|{Z x x x x B ∈≤≤=的倍数，是，则B A 中元素的个数为 .405.设 },{b a A =, ρ 是 A2 上的包含于关系，,则有ρ= .},,},{,}{},{,},{,}{},{,,,}{,,}{,,,{><><><><><><><><><A A A b b b A a a a A b a φφφφφ6.设21,ρρ为集合 A 上的二元关系, 则=21ρρ .~1~2ρρ7.集合A 上的二元关系ρ为传递的充分必要条件是 ．ρρρ⊆8. 设集合{}{}><><==0,2,2,02,1,01ρ上的关系A 及集合A 到集合{}4,2,0=B 的关系=2ρ｛><b a ,|><b a ,A b a B A ∈⨯∈,且∩}=21,ρρ 则B ___________________. 填 }2,2,0,2,2,0,0,0{><><><><四、解答题1. 设 A d c b a A },,,,{=上的关系 },,,,,,,,,,,,,,,{><><><><><><><><=c d d c a b b a d d c c b b a a ρ（1）写出ρ的关系矩阵；（2）验证ρ是A 上的等价关系；（3）求出A 的各元素的等价类。

大学《离散数学》期末考试试卷及答案(1)一、选择题1. 离散数学的主要研究对象是（）。

A. 连续的数学结构B. 有限的数学结构C. 数学的综合应用D. 数学的哲学思考2. 命题逻辑是离散数学的一个重要组成部分，它主要研究（）。

A. 命题之间的真假关系B. 变量之间的关系C. 函数之间的关系D. 集合之间的关系3. 集合的基本运算包括（）。

A. 并、交、差、补B. 加、减、乘、除C. 包含、相等、不等、自反D. 大于、小于、等于、不等于二、填空题1. 若集合A={m|2m-1>3}，则A中的元素为______。

2. 有一个集合A={1，2，3}，则集合A的幂集为______。

3. 若命题p为真，命题q为假，则复合命题“p∧q”的真值为______。

三、解答题1. 请写出离散数学中常用的数学符号及其含义。

2. 请解释命题逻辑中的充分必要条件及其符号表示，并给出一个例子。

3. 请定义集合的笛卡尔积，并给出两个集合进行笛卡尔积运算的例子。

四、问答题1. 离散数学在计算机科学中有着重要的应用，请列举三个与计算机科学相关的离散数学应用领域并简要介绍。

2. 请简要解释归纳法在离散数学中的作用，并给出一个使用归纳法证明的例子。

3. 什么是有向图？请给出一个有向图的例子，并解释该图中的关系。

参考答案：一、选择题1. B2. A3. A二、填空题1. A={m|2m-1>3}2. {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}3. 假三、解答题1. 常用数学符号及含义：- ∪：并，表示集合的合并操作。

- ∩：交，表示集合的交集操作。

- ∖：差，表示减去一个集合中的元素。

- ⊆：包含，表示一个集合包含于另一个集合。

- =：相等，表示两个集合具有相同的元素。

2. 充分必要条件是指一个命题的成立与另一个命题的成立互为必要条件，若A是B的充分必要条件，那么当A成立时B一定成立，且当A不成立时B也一定不成立。

一、填空2．A ，B,C 表示三个集合,文图中阴影部分的集合表达式为 （B ⊕C ）—A4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为 )()(R S P R S P ∨⌝∨⌝∧∨∨⌝ 。

5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为 1 . 6．设A=｛1，2,3,4｝,A 上关系图如下，则 R^2= {（1,1），(1，3),（2,2）,(2,4）} 。

//备注:⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000100001010010R⎪⎪⎪⎪⎪⎭⎫⎝⎛=00000000101001012R7．设A=｛a,b ，c ，d}，其上偏序关系R 的哈斯图如下,则R= {（a ，b)，(a ，c ）, (a ，d), （b,d ）， (c,d ）} U ｛(a ，a),（b,b)(c,c ）(d ，d ）} .//备注:偏序满足自反性,反对称性，传递性8．图的补图为 。

//补图：给定一个图G ,又G 中所有结点和所有能使G 成为完全图的添加边组成的图,成为补图。

自补图：一个图如果同构于它的补图,则是自补图 9．设A=｛a ，b ，c ，d ｝ ，A 上二元运算如下：* a b c d a b c da b c d b c d a c d a b d a b c那么代数系统〈A,＊〉的幺元是 a ，有逆元的元素为 a ，b,c,d ，它们的逆元分别为 a ，b ，c,d 。

//备注：二元运算为x*y=max{x,y ｝,x ，y ∈A 。

10．下图所示的偏序集中，是格的为 c 。

//（注：什么是格？即任意两个元素有最小上界 和最大下界的偏序)二、选择题1、下列是真命题的有（ C 、D ）A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ．}},{{ΦΦ∈Φ; D ．}}{{}{Φ∈Φ.2、下列集合中相等的有( B 、C ）A CA ．{4,3}Φ⋃;B ．{Φ，3，4}；C ．｛4，Φ，3，3｝；D ． {3，4｝。

国家开放大学电大本科《离散数学》2024-2025期末试题及答案(试卷号：1009)一、单项选择题(每小题3分，本题共16分)若集合A = {1,2,3,4},则下列表述不正确的是( ).A.{2,3)€AB.AU{1,2,3,4}C. <1,2,3,4)QAD. 16A2.若无向图G的结点度数之和为20,则G的边数为( ).A.10B. 20C. 30D. 53.无向图G是棵树，结点数为10,则G的边数为( ).A. 5B. 10C.9D. 114.设A(x)：x是人,B(x)：x是学生，则命题“有的人是学生”可符号化为( )•A.Vx)(A(x)-*B(x»B.(3x)(A(x)AB(x))C.(Vx)(A(x)AB(x»D.-«(3x)(A(x)A -B(x»5.下面的推理正确的是( ).A.(l)(Vx)F(x)->G(x) 前提引入(2)F(>-)-*G(y) US(1).B.(1)( 3 x)F(x)-*G(x) 前提引入(2)F(y)-*G(y) US(1),C.(l)(3x)(F(x)->G(x»前提引入(2)F(y)-*G(x) ES(1).D.(l)(3x)(F(x)-*G(x)) 前提引入(2)F(y)-*G(y) ESQ).二、填空题(每小题3分，本题共15分)6.设A = {1,2),H = {1,2,3},则A到B上不同的函数个数为________________ .7.有&个结点的无向完全图的边数为 ____________ .8.若无向图G中存在欧拉路但不存在欧拉回路，则G的奇数度数的结点有________ 个.9.设G是有10个结点的无向连通图，结点的度数之和为30,则从G中删去条边后使之变成树.10.设个体域£> = {1,2,3,4},则谓词公式(*)人(了)消去量词后的等值式为三、逻辑公式翻译(每小题6分，本息共12分)11.将语句“昨天下甬“翻译成命题公式.12.将语句“小王今天上午或者去看电彩或者去打球”翻译成命JS公式.四、判断说明题(判断各题正误，并说明理由.每小题7分，本黑共14分)13.存在集合A与B,使得A6B与AUB同时成立.14.完全图K<是平面图.五、计算题(每小题12分，本题共36分)15.设偏序集VA,R>的哈斯图如下,B为A的子集，其中B = 试(1)写出R的关系表达式；(2)画出关系R的关系图；(3)求出B的最大元、极大元、上界.16.设图G — <V,E>,V={vj f v it v t,Vi»v s)»(v2, v3)»(v3»vs)}»试(1)画出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的图形，17.求P TQ代R)的合取范式与主合取范式.六、证明题(本题共8分)18.设A.B是任意集合，试证明：若AXA=BXB,^ A = B.M答杖松标准(仅辩者)一、单项选择题(每小题3分，本题共15分)1. A2. A3. C4.B5. D二、填空题(每小题3分，本题共］5分)6.97.”3 — 1)/2(或庆)8.210. A(l) VA(2) V A(3) V A(4)三、 逻辑公式翻译（每小题6分，本题共】2分）H,设P ：昨天下雨. 则命题公式为:P ，12. 设P ：小王今天上午去看电影 Q ：小王今天上午去打球 则命题公式为：r （PiQ ）. 或者（rPAQ ）V 〈PA rQ ）四、 判断说明题（每小题7分，本题共14分）13. 正确.例：设 A = {a} t H — {a,{a}） 则有且ACI3.说明：举出符合条件的例均给分. 14. 正确.完全图K 〈是平面图， 如K,可以如下图示嵌入平面.（7分）五、计算题（每小题12分，本题共36分）15. （l ）R = {Va ，a>,Vb,Q>,Vc,c>,Vd,d>・Va0>・Va ・c>，V&，d>，VQ,d >}. （4 分）（2）关系图(8分)（3）集合B 无最大元，极大元为6与c.无上界. 16, 解: （1）关系图（2分） （6分）（2分）（6分）（3分） （517. P TQAR) 5PV(QAR) 0(rPVQ 〉A(rPVR)合取范式<=>(-PVQ)V(K A rR)A(rPVR) 0("VQ)V(& A rR)A(" VR)V(QA -Q)D(rPVQVR)A(rPVQVA("VR VQ) A(-、PVR V -Q) c=>(-PVQV7?)A(-'PVQV-R)A(-PV-QVR) 主合取范式 六、证明题（本意共8分）18. 证明：V2（2）邻接矩阵bioir 101001001 1 00 0（6分）(3) deg(vi)=,3deg(v t )—2 <ieg(v 3)~2 deg顷)=1 deg(v s )=2 (4) 补图（9分）（】2分）（2分） （5分）（7分〉设x€A,则Vx,x>€AXA,（1 分）因AXA = BXB,故V X,X>€BXB,则有xGB, （3 分）因此AGB. （5分）设xQB,则Vx,x>€BXB,（6 分）因AXA-BXB,故Vx,x>eAXA,则有因此BWA. （7 分）故得A=B. （8分）。

课程名称:《离散数学》一、单项选择题1、 (D)。

下列句子是命题的为 。

A 、这朵花多好看呀！B 、明天下午有会吗？C 、5y x >+D 、地球外的星球上也有人。

2、 (A)。

李平不是不聪明，而是不用功。

p:李平聪明q:李平用功。

符号化为 。

A 、 q )p (⌝⌝⌝∧ B 、 q p ⌝⌝∧ C 、 q )p (∧⌝⌝ D 、q )p (⌝⌝⌝∨ 3、 (A)。

与)q p (∨⌝命题公式等值的是 。

A 、q p ⌝⌝∧ B 、q p ⌝⌝∨ C 、q p ∧ D 、q)(p ∧⌝4、 (D)。

含有3个命题变项的简单和取式中一定可形成 种不同的极小项。

A 、2 B 、4 C 、6 D 、85、 (C)。

q )q p (∧→⌝此公式的类型为 。

A 、重言式B 、永真式C 、矛盾式D 、可满足式 6、 (C)。

q )q )q p ((→∧→此公式的类型为 。

A 、矛盾式B 、可满足式C 、重言式D 、永假式7、 (A)。

设A 是含有3个命题变项的公式,若它的主析取范式中含有8个极小项,则它是 。

A 、重言式B 、矛盾式C 、可满足式D 、永假式8、 (B)。

只有天下大雨,他才乘公共汽车上班.p:天下大雨q:他乘车上班,符号化为 。

A 、q p → B 、p q → C 、q p →⌝D 、p q →⌝9、 (B)。

不经一事,不长一智p:经一事q:长一智,符号化为 。

A 、p q →B 、q p ⌝⌝→C 、p q ⌝⌝→ D 、q p → 10、 (B)。

R Q P →∧⌝)(成真赋值为 。

A 、 000,001,110B 、 001,011,101,110,111C 、全体赋值D 、无11、 (B)。

公式Q P →的主析取范式为)3,1,0(∑，则公式的主合取范式为 。

A 、)2(TB 、)2(∏C 、)3,1,0(∏D 、)3,2,1,0(∏12、 (A)。

R Q P →∧⌝成假赋值为 。

离散数学试题(B卷答案1）一、证明题（10分）1)(⌝P∧(⌝Q∧R))∨(Q∧R)∨(P∧R)⇔R证明: 左端⇔(⌝P∧⌝Q∧R)∨((Q∨P)∧R)⇔((⌝P∧⌝Q)∧R))∨((Q∨P)∧R)⇔(⌝(P∨Q)∧R)∨((Q∨P)∧R)⇔(⌝(P∨Q)∨(Q∨P))∧R⇔(⌝(P∨Q)∨(P∨Q))∧R⇔T∧R(置换)⇔R2) ∃x (A(x)→B(x))⇔∀xA(x)→∃xB(x)证明：∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(x)∨∃xB(x)⇔⌝∀xA(x)∨∃xB(x)⇔∀xA(x)→∃xB(x)二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。

证明：(P∨(Q∧R))→(P∧Q∧R)⇔⌝(P∨(Q∧R))∨(P∧Q∧R))⇔（⌝P∧(⌝Q∨⌝R)）∨(P∧Q∧R)⇔(⌝P∧⌝Q)∨(⌝P∧⌝R))∨(P∧Q∧R)⇔(⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R)∨(⌝P∧Q∧⌝R))∨(⌝P∧⌝Q∧⌝R))∨(P∧Q∧R)⇔m0∨m1∨m2∨m7⇔M3∨M4∨M5∨M6三、推理证明题（10分）1）C∨D， (C∨D)→⌝E，⌝E→(A∧⌝B)， (A∧⌝B)→(R∨S)⇒R∨S 证明：(1) (C∨D)→⌝E P(2) ⌝E→(A∧⌝B) P(3) (C∨D)→(A∧⌝B) T(1)(2)，I(4) (A∧⌝B)→(R∨S) P(5) (C∨D)→(R∨S) T(3)(4)， I(6) C∨D P(7) R∨S T(5)，I2) ∀x(P(x)→Q(y)∧R(x))，∃xP(x)⇒Q(y)∧∃x(P(x)∧R(x))证明(1)∃xP(x) P(2)P(a) T(1)，ES(3)∀x(P(x)→Q(y)∧R(x)) P(4)P(a)→Q(y)∧R(a) T(3)，US(5)Q(y)∧R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)∧R(a) T(2)(7)，I(9)∃x(P(x)∧R(x)) T(8)，EG(10)Q(y)∧∃x(P(x)∧R(x)) T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。

离散数学期末复习题一、选择题1、永真式的否定是（2）(1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能2、设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，则下列真命题为(1)(1)R Q P ∧→ (2)S P R ∧→ (3)R Q S ∧→ (4) )()(S Q R P ∧∨∧。

3、设P ：我听课，Q ：我看小说，则命题R “我不能一边听课，一边看小说”的符号化为⑵ ⑴ P Q → ⑵Q P ⌝→(3) Q P →⌝ ⑷ P Q ⌝→⌝()P Q ⌝∧提示：()R P Q P Q ⇔⌝∧⇔→⌝4、下列表达式错误的有⑷⑴()P P Q P ∨∧⇔ ⑵()P P Q P ∧∨⇔⑶()P P Q P Q ∨⌝∧⇔∨ ⑷()P P Q P Q ∧⌝∨⇔∨5、下列表达式正确的有⑷⑴ P P Q ⇒∧ ⑵ P Q P ⇒∨ ⑶ ()Q P Q ⌝⇒⌝→⑷Q Q P ⌝⇒→⌝)(6、下列联接词运算不可交换的是(3)⑴∧ ⑵∨ (3)→ ⑷ ↔6、设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢y ，则命题“有的人喜欢所有的花”的逻辑符号化为⑷⑴(()(()(,))x M x y F y H x y ∀∧∃→ ⑵(()(()(,))x M x y F y H x y ∀∧∀→(3) (()(()(,))x M x y F y H x y ∃∧∃→ ⑷(()(()(,))x M x y F y H x y ∃∧∀→7、设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些老师”的逻辑符号化为⑵⑴)),()((y x A x L x →∀ ⑵))),()(()((y x A y J y x L x ∧∃→∀(3) )),()()((y x A y J x L y x ∧∧∃∀ ⑷)),()()((y x A y J x L y x →∧∃∀8、谓词公式)())()((x Q y yR x P x →∃∨∀中的 x 是⑶⑴自由变元 ⑵约束变元 ⑶既是自由变元又是约束变元 ⑷既不是自由变元又不是约束变元9、下列表达式错误的有⑴⑴(()())()()x A x B x xA x xB x ∀∨⇒∀∨∀ ⑵(()())()()x A x B x xA x xB x ∃∧⇒∃∧∃(3) (()())()()x A x B x xA x xB x ∀∧⇔∀∧∀ ⑷(()())()()x A x B x xA x xB x ∃∨⇔∃∨∃10、下列推导错在⑶①)(y x y x >∃∀ P②)(y z y >∃US ① ③)(z C z > ES ②④)(x x x >∀ UG ③⑴② ⑵③ ⑶④ ⑷无11、下列推理步骤错在⑶①(,)x yF x y ∀∃ P②),(y z yF ∃US ① ③),(c z FES ② ④),(c x xF ∀ UG ③⑤),(y x xF y ∀∃ EG ④⑴①→② ⑵②→③ ⑶③→④ ⑷④→⑤12、设个体域为{a,b}，则(),x yR x y ∀∃去掉量词后，可表示为⑷⑴()()()(),,,,R a a R a b R b a R b b ∧∧∧ ⑵()()()(),,,,R a a R a b R b a R b b ∨∨∨(3) ()()()()()()b b R a b R b a R a a R ,,,,∨∧∨ ⑷()()()()()()b b R a b R b a R a a R ,,,,∨∧∨ 提示：原式()()()()()()()(),,,,,,yR a y yR b y R a a R a b R b a R b b ⇔∃∧∃⇔∨∧∨二、填充题1、一个命题含有n 个原子命题，则对其所有可能赋值有2n 种。

离散数学复习注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。

2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。

把大纲中指定的例题及书后习题认真做一做。

检验一下主要内容的掌握情况。

3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。

离散数学综合练习题一、选择题1．下列句子中，（）是命题。

A．2是常数。

B．这朵花多好看呀！C．请把门关上！D．下午有会吗？2．令p: 今天下雪了，q:路滑，r:他迟到了。

则命题“下雪路滑，他迟到了”可符号化为（）。

A. p q r∨→∧→ B. p q rC. p q r∧∧ D. p q r∨↔3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。

A.p q∧∧⌝ B.p qC.p q∨⌝ D. p q→⌝4．设()Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。

P x:x是鸟，()A. ()(()())⌝∀∧())x P xQ xx P x Q x⌝∀→ B. ()(()C. ()(()())Q x⌝∃∧())x P x Q x⌝∃→ D. ()(()x P x5.设()L x y：x大于等于y；命题“所有整数f x:x的绝对值，(,)P x:x是整数，()的绝对值大于等于0”可符号化为（）。

A. (()((),0))∀→x P x L f x∀∧B. (()((),0))x P x L f xC. ()((),0)∀→xP x L f x∀∧ D. ()((),0)xP x L f x6.设()G x:x犯错误，命题“没有不犯错误的人”符号化为（）。

F x:x是人，()A．(()())⌝∃→⌝x F x G xx F x G x∀∧B．(()()) C．(()())x F x G x⌝∃∧⌝⌝∃∧D．(()())x F x G x7.下列命题公式不是永真式的是（）。