下载文档原格式
..一、填空2．A ，B ，C 表示三个会合，文图中暗影部分的会合表达式为 (B⊕C)-AA C4．公式(PR)(SR)P的主合取范式为(PSR) ( PS R)。
5．若解说I 的论域D 仅包括一个元素，则 xP(x) xP(x) 在I 下真值为 1 。
6．设A={1，2，3，4}，A 上关系图以下，则 R^2={(1,1),(1,3),(2,2),(2,4)}。
//备注： 0 1 0 01 0 1 0 0 1 0 1R 1 0 1 0 R 20 0 0 1 0 0 0 00 0 0 00 0 0 07．设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 da abcd b b c d a ccdabd 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}。
;....3、设A={1，2，3}，则A 上的二元关系有（ C ）个。
离散数学综合练习题一一、单项选择题（每题2分 ）16 %设P ：王强是南方人，Q ：他怕热．命题“王强不怕热是因为他是南方人”符号化为 ( ) (A)(B)()(D)P Q P Q C Q P Q P →→⌝→⌝→2 设F (x )：x 是熊猫，G (y )：y 是竹子，H (x ,y )：x 喜欢y. 那么命题“有些熊猫喜欢各种的竹子”符号化为 ( )(A) (()(()(,)))x F x y G y H x y ∃→∀∧ (B) (()(()(,)))x F x y G y H x y ∃→∀→ (C) (()(()(,)))x F x y G y H x y ∃∧∀→ (D) (()(()(,)))y x F x G y H x y ∀∃→∧3. 命题公式()p q p →∧⌝是 ( )(A) 重言式 (B) 矛盾式(C) 可满足式 (D) 以上3种都不是4. 设集合A ＝{a,b,{c,d,e}}则下列各式为真的是 ( )(A) ∈A (B) c ∈A (C) {c,d,e} A (D) {a,b}A5. 设函数 :f N N →且()3x f x =，则f 是 ( )(A) 单射，非满射 (B) 满射,非单射 (C) 双射 (D) 非单射，非满射6. 设E 为全集, A , B 为非空集，且BA ，则空集为（ ）(A) A B I (B) A B :I (C) A B I : (D) A B :I :7. 设A ={0,1,2,3}，A 上的关系R ={<0,1>,<0,2>,<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}，则R 是 ( )（A ）自反的 （B ）对称的 （C ）反对称的 （D ）可传递的8. 无向图K 3,3是（ ）（A ）哈密顿图 （B ）欧拉图 （C ）完全图 （D ）平面图二、填空题（每空2分）18 %1. 设():F x x 是火车，():G y y 是汽车，H (x,y )：x 比y 快，则命题“说所有火车比有的汽车快是不对的”符号化是 ，其另一种等值形式为 。
离散数学期末考试题及答案1.选择题（每题3分，共30分）1. 下列命题中，属于复合命题的是：A. 3是一个奇数，且2是一个偶数B. 如果2是一个素数，那么4也是一个素数C. 不是所有奇数都是素数D. 存在一个整数x，使得x>5且x是一个偶数答案：D2. 已知命题p：草地是绿的，命题q：天空是蓝的。
下列表述可以表示p ∧ ¬q 的是：A. 草地是绿的，天空是蓝的B. 草地不是绿的，天空是蓝的C. 草地是绿的，天空不是蓝的D. 草地不是绿的，天空不是蓝的答案：B3. 设命题p表示“这个数是偶数”，q表示“这个数大于10”。
那么“这个数既是偶数又大于10”可以表示为：A. p ∧ qB. p ∨ qC. ¬p ∧ qD. ¬p ∨ q答案：A4. 下列以下列集合的方式描述，其中哪个是空集∅：A. {x | 0 ≤ x ≤ 1}B. {x | x是一个自然数，x > 10}C. {x | x是一个正偶数，x < 2}D. {x | x是一个负整数，x < -1}答案：C5. 设A = {a, b, c}，B = {c, d, e}，C = {a, c, e}。
则(A ∪ B) ∩ C等于：A. {a, b, c, d, e}B. {a, c, e}C. {c}D. 空集∅答案：B6. 假设U是全集，A、B、C是U的子集。
则(A ∪ B) ∩ C 的补集是：A. A ∩ B ∩ C的补集B. (A ∪ B) ∩ C的补集C. A ∪ (B ∩ C)的补集D. (A ∩ C) ∩ (B ∩ C)的补集答案：D7. 若关系R为集合A到集合B的一种映射，且|A| = 7，|B| = 4，则R包含的有序对数目为：A. 4B. 7C. 11D. 28答案：D8. 设A={1,2,3}，B={4,5,6}，则从A到B的映射总数为：A. 3B. 9C. 6D. 18答案：C9. 设A={a,b,c,d,e}，则集合A的幂集的元素个数是：A. 2B. 5C. 10D. 32答案：D10. 若f：A→B为满射且g：B→C为单射，则(g ∘ f)：A→C为：A. 双射B. 满射C. 单射D. 非单射且非满射答案：A2.简答题（每题10分，共20分）1. 请简要解释什么是关系R的自反性、对称性和传递性。
离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，空集表示为：A. {0}B. {1}C. {}D. Ø答案：D2. 命题逻辑中，下列哪个是合取命题的真值表？A. P | Q | P ∧ QB. P | Q | P ∨ QC. P ∧ Q | P ∨ QD. P ∧ Q | ¬(P ∨ Q)答案：A3. 函数f: A → B是单射的，那么f的逆函数：A. 一定存在B. 一定不存在C. 可能存在D. 以上都不对答案：C4. 关系R是自反的，那么对于所有a∈A，以下哪个命题一定为真？A. (a, a) ∈ RB. (a, a) ∉ RC. (a, a) ∈ R或(a, a) ∉ RD. (a, a) ∈ R且(a, a) ∉ R答案：A5. 在图论中，下列哪个不是图的基本术语？A. 顶点B. 边C. 子集D. 路径答案：C6. 命题p: “如果x是偶数，则x能被4整除”的否定是：A. 如果x是偶数，则x不能被4整除B. 如果x不是偶数，则x不能被4整除C. 如果x不是偶数，则x能被4整除D. 如果x是偶数，则x不能被4整除或x不是偶数答案：A7. 有向图G中，如果存在从顶点u到顶点v的有向路径，则称v是u 的：A. 祖先B. 后代C. 邻居D. 连接点答案：B8. 在命题逻辑中，下列哪个命题是永真命题？A. (P ∧ ¬P) ∨ (P ∨ ¬P)B. (P ∧ ¬P) ∧ (P ∨ ¬P)C. (P ∨ ¬P) ∧ (¬P ∨ P)D. (P ∧ ¬P) ∧ (¬P ∧ P)答案：C9. 以下哪个选项是等价命题？A. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)B. P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)C. P ∨ ¬P ≡ ¬P ∧ PD. P ∧ ¬P ≡ ¬P ∨ P答案：A10. 树是无环连通图，以下哪个是树的属性？A. 至少有一个环B. 至少有两个顶点C. 至少有一个顶点D. 至少有一个边答案：B二、填空题（每空2分，共20分）11. 集合{1, 2, 3}的幂集含有__个元素。
离散数学期末考试试题(配答案)1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。
2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____；=A _____；=B A Y __ _____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 =→⨯),(,:。
求证：g f 和都是满射；但不是单射。
（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；即证得。
一、填空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}。
苏州大学2011—2012年上学期离散数学期末试卷
一、名词解释
1、等势：
2、阿贝尔群：
3、偏序关系：
4、命题：
5、平面图：
二、求(p∧r)∨(p←→q)的主析取和主合取范式。
三、符号化下面的命题并推证其结论。
任何人如果他喜欢音乐，他就不喜欢美术，每个人或者喜欢美术或者喜欢体育，有的人不喜欢体育。
所以存在有人不喜欢音乐。
四、证明：
1）A∩（A∪B）＝A
2）若关系R是对称和传递的，试证明R°R=R。
五、已知映射f和g，f和g都是双射，试证明f°g也为双射。
六、证明：[0,1]是不可数的。
七、设<A，《>是一个分配格，那么，对于任意的a，b，c∈A,如果有：
a∧b＝a∧c，a∨b＝a∨c 成立，则必有b＝c。
八、有关独异点的证明，证明某一代数系统是可交换的独异点。
九、简单无向图G，有N个结点，N+1条边，证明G中至少有一个结点的次数大于等于3。
十、简述欧拉定理，并证明该定理成立。
注：该份试题是参加完离散考试后整理出来的，除第八大题记不清具体题目外，其他都是原题。
希望对学弟学妹的离散数学期末复习有所帮助。
另外说明该份试卷是马小虎老师班上考的，徐汀荣老师班上不知道是不是和该份试卷一样。
离散数学考试题及答案一、选择题1. 关于图论的基本概念，以下哪个说法是正确的？A. 无向图中的边无方向性，有向图中的边有方向性。
B. 有向图中的边无方向性，无向图中的边有方向性。
C. 无向图和有向图都是由顶点和边组成的。
D. 无向图和有向图都只由边组成。
答案：A2. “若顶点集合为V，边集合为E，那么图G可以表示为G(V, E)”是关于图的哪个基本概念的描述？A. 图的顶点B. 图的边C. 图的邻接D. 图的表示方法答案：D3. 以下哪个命题是正确的？A. 若集合A和B互相包含，则A和B相等。
B. 若集合A和B相交为空集，则A和B相等。
C. 若集合A和B相等，则A和B互相包含。
D. 若集合A和B相等，则A和B相交为空集。
答案：C二、填空题1. 有一个集合A = {1, 2, 3, 4}，则集合A的幂集的元素个数为__________。
答案：162. 设A = {a, b, c}，B = {c, d, e}，则集合A和B的笛卡尔积为__________。
答案：{(a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, c), (c, d), (c, e)}3. 若p为真命题，q、r为假命题，则合取范式(p ∨ q ∨ r)的值为__________。
答案：真三、计算题1. 计算集合A = {1, 2, 3, 4}和集合B = {3, 4, 5, 6}的交集、并集和差集。
答案：交集：{3, 4}并集：{1, 2, 3, 4, 5, 6}差集：{1, 2}2. 计算下列命题的真值：(~p ∨ q) ∧ (p ∨ ~q)，其中p为真命题，q为假命题。
答案：真四、证明题证明：对于任意集合A和B，如果A和B互相包含，则A和B相等。
证明过程：假设A和B互相包含，即A包含于B且B包含于A。
设x为集合A中的任意元素，则x也必然存在于集合B中，即x属于B。
同理，对于集合B中的任意元素y，y也属于集合A。
离散数学期末考试试题及答案详解一、【单项选择题】(本大题共15小题，每题3分，共45分)在每题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。
1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。
[A] 3 [B] 8 [C]9 [D]272、设A1,2,3,5,8,B1,2,5,7,那么AB( )。
[A] 3,8 [B]3 [C]8 [D]3,83、假设X是Y的子集，那么一定有( )。
[A]X不属于Y [B]X∈Y[C]X真包含于 Y [D]X∩Y=X4、以下关系中是等价关系的是( )。
[A]不等关系 [B]空关系[C]全关系 [D]偏序关系5、对于一个从集合A到集合B的映射，以下表述中错误的选项是( )。
[A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象[C]对B的.每个元素都有原象 [D] 对B的元素可以有不止一个原象6、设p:小李努力学习，q:小李获得好成绩，命题“除非小李努力学习，否那么他不能获得好成绩”的符号化形式为( )。
[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、设A={a,b,c},那么A到A的双射共有( )。
[A]3个 [B]6个 [C]8个 [D]9个8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点( )。
[A] G没有奇数度结点 [B] G有1个奇数度结点[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元10、令p：今天下雪了，q：路滑，那么命题“虽然今天下雪了，但是路不滑”可符号化为( )[A] p→┐q [B] p∨┐q[C] p∧q [D] p∧┐q11、设G=的结点集为V={v1,v2,v3},边集为E={,}.那么G 的割(点)集是( )。
苏 州 大 学 试 卷2011 — 2012 学年第二学期期末考试《 离散数学 》（A 卷）班级 学号 姓名 总分 注：P={1,2,3,….}1.(6’)用题中所提供的变元将下面一段论述转化成命题公式，然后给出形式化证明。
如果天气干燥，那么我将去远足或游泳。
我去游泳当且仅当天气暖和。
所以，如果我没去远足，则天气是潮湿的或暖和的。
(d, h, s, w)2.(5’)判断下列两个谓词蕴含式的逻辑值。
如果逻辑值为F ，须举例予以说明【或者通过定义一个恰当的谓词说明，或者在一个小的论域上（如U={a,b}）通过给变元赋真值验证】。
(a)),(),(y x p y x y x p x y ∀∃⇒∃∀。
(b) ),(),(y x p x y y x p y x ∃∀⇒∀∃。
3.(6’)设A={1, 2, 3}，},{},{是奇数，是偶数n P n n C n P n n B ∈=∈=.(a) 求的值确定C B C B C B B A ⊕⋃⋂⋂,,,。
(b) 列出A 的所有子集。
(c) A C C A C A B A --⊕⊕,,,中哪些是无穷集合？4.(6’)从集合{1,2,3,…,1000}中随机取一个整数，该整数至少能被4,5或6中的一个整除的概率是多少。
5.(5’)整数集合Z 上的关系R 定义如下：(m ,n )∈R 当且仅当)5(mod 033≡-n m .判断R 是否满足自反，反自反，对称，反对称和传递属性。
R 是否为等价关系？6.(5’) 设R 1和R 2是集合S 到T 上的关系，R 3是集合T 到U 上的关系。
证明：3231321)(R R R R R R R ⋃=⋃7.(8 ’) 集合S ={1,2,3,4,5}上关系R 的关系矩阵是：--------------------------------------------------------------------------------------装订线------------------------------------------------------------------------------------000000010000000111010000=A ，写出下列闭包运算的布尔矩阵：(a)r(R)；(b)s(R)；(c)rs(R)；(d)sr(R)；(e)tsr(R)；(f)列出tsr(R)的等价类；(g)画出与关系R 对应的关系图，并计算该关系图的可达性矩阵。
简要说明有向图可达性矩阵和对应的传递闭包之间的关系。
8.(7’)下表给出格),(≤L 关于”∨”运算的部分结果，例如，b ∨d=d.(a) 将表中剩余部分填满。
(b) 找出L 的最大元素和最小元素。
(c) 证明e d c f ≤≤≤。
(d) 画出L 的哈斯图。
9.(6’)设f 和g 是Z 到Z 的映射，其中Z n n n f ∈-=,1)(，g 是集合},{是偶数n Z n n E ∈=的特征函数。
(a)计算),8)((),7)((),4)((),5)((g f g f f g f g (b)计算)12)((),11)((),12)((),11)((g g g g f f f f 。
(c)确定函数f f f g 和.(d)证明：)(,f g g f f g g g -==10.(5’)(a)证明若S 和T 是可数的，则S ×T 也是可数的；(b)证明若f 是S 到T 的满射并且S 是可数的，则T 也是可数的； (c)用(a)和(b)的结论证明有理数集合Q 是可数的。
11.(8’) 设ϕ是布尔代数B 1和B 2之间的一一对应，且已知ϕ保持或运算∨。
(a)证明1-ϕ也保持或运算∨；即，如果x,y ∈B 2和a,b ∈B 1且满足)(),(b y a x ϕϕ==，则)()()(1-1-1-b x b a y x ϕϕϕ∨=∨=∨(b)证明ϕ保持序关系≤；即，如果在B 1中c ≤d,则在B 2中有)()(d c ϕϕ≤。
(c)证明如果01和02分别是B 1和B 2的全下界，则210)0(=ϕ。
(c)证明如果11和12分别是B 1和B 2的全上界，则211)1(=ϕ。
12.(8’)设两个变元的布尔函数的集合用BOOL(2)表示，B={0,1}.(a)用列表形式写出布尔代数BOOL(2)的全部原子。
(b)将定义在B B g →2:上的函数x y x g =),(用BOOL(2)中的原子”∨”表示出来。
(c)写出布尔表达式y x ∨'的析取范式，并用BOOL(2)中的原子”∨”表示出来。
13.(5’) 设完全图K 6的顶点为v 1,v 2,…,v 6.(a) K 6中有多少个与K 4同构子图？(b)从v 1到v 2所有长度小于等于3的迹有几条？ (c) K 6中所有长度小于等于3的迹总共有几条？ 14.(5’) (a)画一个能构造3阶de Bruijn 序列的有向图。
(b)根据你所画出的有向图，写出两个3阶de Bruijn 序列。
15.(5’)(a)一棵树有n 2个节点度数是2，n 3个节点的度数是3，…，n k 个节点的度数是k ，问它有几个度数为1的节点。
16.(5’) (a)找出下图的最小生成树。
(b)最小生成树的总权重是多少？(c)此图中Hamilton 回路的最小权重是多少？(e)判断此图中有没有Euler 回路或Euler 路，如果有的话，计算相应的权重；如果没有的话，说明原因。
17(5’)假设要用字母C, E, L, S, U, Y 的二进制码字编写信息，它们的使用频率分别为7, 31, 20,24, 12, 6. (a) 画一颗使这些字母编码效率最高的树。
(b) 用(a)中确定的编码方法对信息CLUE 进行编码。
参考答案注：P={1,2,3,….}1.(6’)设：d:=天气干燥; h:=我去远足; s:=我去游泳; w:=天气暖和。
(d, h ,s, w) 条件：d →h ∨s, s ↔w. 结论：﹃h →﹃d ∨w 证明：① ﹃h附加前提 ② d →h ∨s P ③ ﹃d ∨h ∨sT ②E ④ ﹃d ∨s T ①③I ⑤ s ↔w P ⑥ s →wT ⑤I ⑦ ﹃s ∨wT ⑥E⑧ ﹃d ∨w T ④⑦I2.(5’)(a)真值F 。
例如，假设U={a,b},令p(x,y)表示命题“x=y ”,则逻辑蕴含不成立。
(b)真值T 。
3.(6’)(a) P ,P ,,{2}=⊕=⋃=⋂=⋂C B C B C B B A φ(b) {1,2,3}}{2,3}{1,3}{1,2}{3}{2}{1}{，，，，，，，φ (c) A C C A -⊕⊕,B A ，。
4.(6’)0.4665.(5’)满足自反，对称，传递。
是等价关系。
6.(5’) 32131211)(R R R R R R R R ⋃⊆∴⋃⊆，,同理可得，32132)(R R R R R ⋃⊆所以，3213231)(R R R R R R R ⋃⊆⋃反之，设321)(),(R R R u s ⋃∈，则321),(),(,R u t R R t s T t ∈⋃∈∈∃且使得。
若311),(),(R R u s R t s ∈∈，此时，若322),(),(R R u s R t s ∈∈，此时，总之， 3231),(R R R R u s ⋃∈，故3231321)(R R R R R R R ⋃⊆⋃。
证毕。
7.(8’) (a) 100000101000100111010001)(=A r ; (b) 0000100010000100111010000)(=A s ;(c) 100010101000110111010001)(=A rs ;(d) 1000101010001100111010001)(=A sr ; (e) 100010111001110111010001)(=A tsr ; (f)[1]={1,5}; [2]={2,3,4}. （g ）与关系R 对应的关系图如下和该关系图的可达性矩阵如下：000001110000000111010000)(=A t3一个有向图可达性矩阵就是其对应关系的传递闭包。
8.(7’)(a)(b)L 的最大元素和最小元素分别为：e,f(c)证明c f c c f ≤∴=∨, ,同理可证，e d d c ≤≤,，e d c f ≤≤≤∴(d)画出L 的哈斯图如下：9.(6’)(e) 1,0,-1,0 (f) 9,10,1,0(c)f g 是E 的特征函数，Z n n n f f ∈-=,2)((d)证明：fg g g E Z n En f g E Z n E n g g =∴⎩⎨⎧-∈∈=⎩⎨⎧-∈∈=,1,0,,1,0同理可证：)(f g g f -=10.(5’)(a) Tt t S T S ∈⨯=⨯}){(:，每个S ×{t}是可数的，所以S ×T 也是可数的。
(b)对每个t ∈T,设g(t)是S 的元素且f(g(t))=t,则g 是单射函数。
所以T 是S 的子集，已知S 是可数的，所以S 的子集T 也是可数的。
(c)由(a)可知，Z ×P 是可数的。
又因为从Z ×P 到Q 存在满射函数f,根据(b)的结论，Q 是可数的。
11.(8’)(a))()())(())()(()(1-1-1-1-1-b x b a b a b a y x ϕϕϕϕϕϕϕϕ∨=∨=∨=∨=∨，(b)若c ≤d ，则d=c ∨d,所以)()()()()()(d c d c d c d ϕϕϕϕϕϕ≤∨=∨=故，c(c)因为φ是B 2上的满射，所以在B 1中存在e ，使得φ(e)=02.故2112110)()0()()0(0)0()0(==∨=∨=∨=e e e ϕϕϕϕϕϕ(d ) 与(c)类似，设φ(e)=12.则22111111)1()()1()1()1(=∨=∨=∨=ϕϕϕϕϕe e12.(8’)(a)(b)根据(a)中的记号，g=c ∨d(c)根据(a)中的记号，y x ∨'= a ∨b ∨d13.(5’)(a)1546=C(b) 1+4+4×3=17(c) 6×5+6×5×4+6×5×4×4=63014.(5’)(a)(b)两个序列如下：15.(5’)是度数为1的节点数为x 个，则)1(2323232-++++=++++x n n n x kn n n k k所以，2)2(243+-+++=k n k n n x1111111116.(6’)(a)(b)18。
