离散数学A卷

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

离散数学试题（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 上的二元关系，则由定理4.19知，tsr (R )是包含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.。

离散数学AB卷离散数学黄金AB卷A卷一、选择题：（30分）1、取个体域为整数集，给定下列公式（1）∀x∃y（x*y=0）（2）∀x∃y（x*y=1）（3）∃y∃x（x*y=2）（4）∀x∀y ∃z（x – y = z）（5）x – y = - y + x（6）∀x∀y（x *y = y）（7）∀x（x*y = x）（8）∃x∀y（x + y = 2y）在上面的公式中，真命题的为 A ，假命题的为B 。

A：①（1）、（3）、（4）、（6）；②（3）、（4）、（5）；③（1）、（3）、（4）、（5）；④（3）、（4）、（6）、（7）B：①（2）、（3）、（6）；②（2）、（6）、（8）；③（1）、（2）、（6）、（7）；④（2）、（6）、（8）、（7）2、设S1=｛1，2，…，8，9｝，S2=｛2，4，6，8｝，S3=｛1，3，5，7，9｝，S4=｛3，4，5｝，S5=｛3，5｝。

确定在以下条件下X可能与S1,…,S5中哪个集合相等。

（1）若X∩S5 = φ，则A ；（2）若X⊆S4但X∩S2 = φ，则B ；（3）若X⊆S1但X⊄S3，则C ；（4）若X - S3= φ，则D ；（5）若X⊆S3但X⊄S1，则E ；A、B、C、D、E：①X=S2或者S3；②X= S4或者S5；③X=S1，S2或者S4；④X与其中任何集合都不等；⑤X=S2；⑥X=S5；⑦X=S3或者S5；⑧X=S2或者S4；3、（1）设S=｛1，2｝，R为S上的二元关系，且xRy。

如果R=Is，则A ；如果R是数的小于等于关系，则B ；如果R=Es，则C 。

（2）设有序对< x+2，4 > 与有序对<5，2x+y >相等，则x=D ，y=E 。

A、B、C：①x与y可任意选择1或2；②x=1，y=1；③x=1，y=1或2；x=y=2；④x=2，y=2；⑤x=y=1或x=y=2；⑥x=1，y=2；⑦x=2，y=1；D 、E ：⑧3；⑨9；⑩ -24、设S=<1，2，3，4>，R 为S 上的关系，其关系矩阵是⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0001100000011001，则（1）R 的关系表达式是A ；（2）domR=B ；ranR=C ；（3）R R 中有D 个有序对；（4）R-1的关系图中有E 个环。

《离散数学》试卷（A 卷）一、 选择题（共5 小题，每题 3 分，共15 分）1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕⋃)(为(C )。

A 、{1,2}B 、{2,3}C 、{1,4,5}D 、{1,2,3}2、下列语句中哪个是真命题 ( A )A 、如果1+2=3，则4+5=9；B 、1+2=3当且仅当4+5≠9。

C 、如果1+2=3，则4+5≠9；D 、1+2=3仅当4+5≠9。

3、个体域为整数集合时，下列公式（ C ）不是命题。

A 、)*(y y x y x =∀∀B 、)4*(=∃∀y x y xC 、)*(x y x x =∃D 、)2*(=∃∃y x y x4、全域关系A E 不具有下列哪个性质（ B ）。

A 、自反性B 、反自反性C 、对称性D 、传递性5、函数612)(,:+-=→x x f R R f 是（ D ）。

A 、单射函数B 、满射函数C 、既不单射也不满射D 、双射函数二、填充题（共 5 小题，每题 3 分，共15 分）1、设|A|=4，|P(B)|=32，|P(A ⋃B)|=128，则|A ⋂B|=ˍˍ2ˍˍˍ.2、公式)(Q P Q ⌝∨∧的主合取式为 。

3、对于公式))()((x Q x P x ∨∃，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为ˍˍˍ1ˍˍˍ。

4、设A ＝{1,2,3,4}，则A 上共有ˍˍˍ15ˍˍˍˍ个等价关系。

5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。

三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分）1、“这个语句是真的”是真命题。

（ F ）2、“刚和小强是同桌。

”是复合命题。

（ F ）3、))(()(r q q p p ∧⌝∧→⌝∨是矛盾式。

（ T ）4、)(T S R T R S R ⋂⋅⊆⋅⋃⋅。

《 离散数学 》 试卷（A ） 一．单项选择题(每题2分，共30分)1．下列命题公式中不．是重言式的是（ ） A ．p →(q →r) B ．p →(q →p)C ．p →(p →p)D ．(p →(q→r))(q →(p →r))2．下列语句中为命题的是（ ） A ．这朵花是谁的？ B ．这朵花真美丽啊！ C ．这朵花是你的吗？ D ．这朵花是他的。

3．设个体域是整数集，则下列命题的真值为真的是（ ）A ．y x(x ·y=1)B．x y (x ·y ≠0) C ．x y (x ·y=y 2)D ．y x(x ·y=x 2)4．关于谓词公式（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 是该谓词公式的约束变元 5．设论域D={a,b}，与公式xA （x ）等价的命题公式是（ ）A ．A （a ）∧A （b ）B ．A （a ）→A （b ）C ．A （a ）∨A （b ）D ．A （b ）→A （a ）6．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（ ） A ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡100010101B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101010101C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101110011D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡1110110017．设A={Ø}，B=P （P （A ）），以下不．正确的式子是（ ） A ．{{Ø }，{{Ø }}，{Ø ，{Ø }}}包含于B B ．{{{Ø }}}包含于B C ．{{Ø ，{Ø }}}包含于B D ．{{Ø }，{{Ø ，{Ø }}}}包含于B8．设Z 是整数集，E={…，-4，-2，0，2，4，…}，f ：Z →E ，f （x ）=2x ，则f （ ） A ．仅是满射 B ．仅是入射 C ．是双射D ．无逆函数9．设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〉} B．{〈2，4〉，〈2，3〉，〈4，2〉}C．{〈4，1〉，〈2，3〉，〈2，4〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）A．矛盾式B．重言式C．可满足式D．公式p∧q11．在实数集合R上，下列定义的运算中不．可结合的是（）A．a*b=a+b+2ab B．a*b=a+bC．a*b=a+b+ab D．a*b=a-b12．下列集合关于所给定的运算成为群的是（）A．已给实数a的正整数次幂的全体，且a∉{0，1，-1}，关于数的乘法B．所有非负整数的集合，关于数的加法C．所有正有理数的集合，关于数的乘法D．实数集，关于数的除法13．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A．3 B．4C．5 D．614．设无向图G的边数为m，结点数为n，则G是树等价于（）A．G连通且m=n+1 B．G连通且n=m+1C．G连通且m=2n D．每对结点之间至少有一条通路15．设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立二、填空题（每题2分，共20分）1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。

《离散数学》试卷(A)适用专业： 考试日期：试卷类型：闭卷 考试时间：120分钟 试卷总分：100分一、单项选择题(本大题共8小题，每小题3分，共24分)1、下述哪一个不是命题？（ ） A 、离散数学是计算机系的一门必修课 B 、不存在最大偶数。

C 、若我有空，我就看书。

D 、请勿随地叶痰！2、设A={a,b,c}，B={1,2,3}，以下哪一个关系是从A 到B 的双射函数？（ ） A 、f={<a,2>,<b,2>,<c,1>} B 、f={<a,3>,<b,1>,<c,2>} C 、f={<a,1>,<b,2>,<c,3>,<a,3>} D 、f={<a,1>,<b,2>,<a,3>}3.设<G, 。

>是群，且|G|>1,则下列命题不成立的是（ ）A.G 中有幺元B. G 中有零元C.G 中任一元素有逆元D. G 中除幺元外无其它幂等元 4、设A={}c b a ,,,则下列是集合A 的划分的是（ ） A.{}{}{}c c b ,, B. {}{}{}c a b a ,,, C.{}{}c b a ,, D.{}{}{}c b a ,, 5.设集合A={a,{b}}，下面四个命题为真的是A.a 包含于AB.φ∈AC.{b}包含于AD.φ包含于A 6、下列是命题公式p ∧(q ∨⌝r)的成真指派的是（ ） A.110,111,100 B.110,101,011 C 所有指派 D.无 7、与一阶公式P(x)→VxQ(x)等值的公式是A.P(y)→VyQ(y)B.P(y)→VxQ(y)C.P(x)→VyQ(y)D.P(z)→VyQ(y)8、设A 和B 都是命题，则A →B 的真值为假当且仅当（ ） A 、A 为0 ，B 为1 B 、A 为0 ，B 为0 C 、A 为1 ，B 为1 D 、A 为1 ，B 为0二、填空题（本大题共7小题，每空3分，共21分）１．.设A={a,b,c}，F 是A 上的二元关系，F={<a,c>,<b,a>,<c,b>}，则其自反闭包为r(F)= 。

学年第二学期期末考试《离散数学》试卷（ 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分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。

则根据题意应有：A→C⊕D，⌝(B ∧C)，C→⌝D必须同时成立。

因此(A→C⊕D)∧⌝(B∧C)∧(C→⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧(⌝B∨⌝C)∧(⌝C∨⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧((⌝B∧⌝C)∨(⌝B∧⌝D)∨⌝C∨(⌝C∧⌝D))⇔(⌝A∧⌝B∧⌝C)∨(⌝A∧⌝B∧⌝D)∨(⌝A∧⌝C)∨(⌝A∧⌝C∧⌝D)∨(C∧⌝ D∧⌝B∧⌝C)∨(C∧⌝ D∧⌝B∧⌝D)∨(C∧⌝ D∧⌝C)∨(C∧⌝ D∧⌝C∧⌝D)∨(⌝C∧D∧⌝B∧⌝C)∨(⌝C∧D∧⌝B∧⌝D)∨(⌝C∧D∧⌝C)∨(⌝C∧D∧⌝C∧⌝D)⇔F∨F∨(⌝A∧⌝C)∨F∨F∨(C∧⌝ D∧⌝B)∨F∨F∨(⌝C∧D∧⌝B)∨F∨(⌝C∧D)∨F⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D∧⌝B)∨(⌝C∧D)⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D)⇔T故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。

S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：∀x(S(x)∧W(x))，∃x Y(x)∃x(S(x)∧Y(x))下面给出证明：(1)∃x Y(x) P(2)Y(c) T(1)，ES(3)∀x(S(x)∧W(x)) P(4)S( c)∧W( c) T(3)，US(5)S( c) T(4)，I(6)S( c)∧Y(c) T(2)(5)，I(7)∃x S((x)∧Y(x)) T(6) ，EG三、（10分）设A、B和C是三个集合，则A⊂B⇒⌝(B⊂A)。