离散数学复习提纲
笫一章命题逻辑
1.(PvQ) T (-1QAR)的主合取范式和主析取范式。
2.试求下列公式的主析取范式：
(1)p^((?->(2)A^(-.gv-??))； (2)
(an: 1)解：原式=「八((「户\/0/\(0")) =「戶\/((「"0/\尸)\/(0人0/\卩))
=—iP V (2 A P) = (—1P V(2) A (—iP V P) = —1P V Q
2)解：P d (Q x/ (「0 T /?))) = Pv(Pv((2v(ev /?)))
=F 7 Q7 R = (—P A―Q A R) v (―P /\ Q /\ ―R) v (—P /\Q /\ R) v (P A―Q A R) V (P A -1(2 A -1/?) V (P A(2 A -1/?) V (P A 2 A /?))
3.用真值表判断下列公式是恒真？恒假？可满足?
(1)(P A-,P) O Q
(2) 1 (P T Q) A Q
(3)((P T Q) A (Q T R)) T (P T R)
(an:解：
(1)
因此公式(1)为可满足。
(2)真值表
（3）真值表
4.-I Q A (P-Q)蕴涵-I P
法1:真值表法2：若1 Q A (P—Q)为真，贝I」1 Q, P—Q为真, 所以Q为假，P为假，所以「P为真。
法3：若「P为假，则P为真，再分二种情况：
①若Q为真，贝'Ji QU (P-Q)为假
②若Q为假，则P-Q为假,则1 Q A(P-Q)为假根据①②，所以Q A (P—Q)蕴涵P。)
5.利用基本等价式证明下列命题公式为恒真公式。
((P T Q) A (Q T R)) T (P T R)
((PvQ) A-! (-.P A(I Q VI R))) V (I P A-H Q) V (-.P AI R)(an: 1、证明：
((P T Q) A (Q T R)) T (P T R)
=((「PvQ) A (->QvR)) -> (iPvR)
=-i ((「PvQ) A (-,QvR)) v (-,PvR)
=(P A-I Q ) v (Q A-I R ) v-iPvR
=((P A^Q)\Z->P ) v ((Q A^R) V R)
=(1A (「Q V-P )) v ((QvR) Al)
=—iQv—iPvQvR
=(-iQvQ) v-iP vR
=1 v—iP vR
=1
((PvQ) A-. (-I P A (「Q S R))) v (「P—Q) v (-.P A-I R)
=((PvQ) A (Pv (Q A R))) V (-,P A (-.Q V^R))
=(Pv (Q A Q A R)) V (-,P A (「QgR))
=(Pv (Q A R)) v-. (Pv (Q A R))
=1)
6.用形式演绎法证明：｝蕴涵P — S
（an:证明:
(1) rPyQ 规则P
(2) P — Q 规则Q (1)
(3) 「Qv R 规则P
(4) Q T R 规则Q (3)
(5) P t R 规则Q (2) (4)
(6) R T S 规则P
(7) P T S 规则Q (5) (6) )
7.用形式演绛法证明：(A\/3)T (C/\D),(D\/F)T ￡蕴涵A T E (an ：、证明:(改(A A B)为(A V B),(D A F)为(D V F))
⑵AVB 规则Q (1)
(3) (A V B)^(C A D) 规则P
(4) C A ￡> 规则 Q (2) (3)
(5) D 规则Q (4)
(6) DvF 规则Q (5)
(7) (D V F)T E 规则P
⑻E 规则 Q (6) (7)
(9) A^E 规则 Q (1) (8))
(PA-i Q), -i QVR, -i R 蕴涵 I P
(1)A 规则D
8. 1 (an: (1) -| QVR
(2) (3) (4) (5) (6) 1 9.某案涉及甲、 (1) (2) (3) (4)
R
Q
(PA-i Q)
PVQ
P)
乙、 丙、丁四个，根据已有线索，已知：
若甲、乙均未作案， 若丙、丁均未作案， 若甲与乙同时作案， 若乙少内?同时作案， 则丙、丁也均氷作案；
则甲、乙也均未作案；
则丙与丁冇一人R 只冇一人作案;
则甲与丁同吋作案或同未作案。
办案人员山此得出结论：甲是作案者。这个结论是否正确？为什么? (an:解：对问题中的四个简单命题用Pl, P2, P3, P4分别表示甲，乙，内, T ■作案，
则
办案人员的推理如下：
前提：
1)-nPlA-1P2^-.P3A-.P4
2)-.P3A->P4->-1P1A-.P2
3)P1 A P2-> (-,P3A P4) v (P3A-?P4)
4)P3A P4^ (^Pl A-,P2)v (Pl A P2)
结论：Pio
(^P1A^P2^P3A^P4) A (「P3人A (P1A P2^(^P3A P4) V (P3A^P4)) A (P3A P4-> (^Pl A-,P2) v (Pl A P2) ) -> Pl
不是永真式，比如：
Pl取假，P2取真，P3取假，P4取真时，上式为假
所以P1不是前提的有效结论，
所以甲是作案者的结论是错误的)
课丿口习题：
p8： 1, 5
pl9： 7
p23： 6, 7, 8
p39： 4
p47： 4, 5
第二章谓词逻辑
1.设个体域D={1, 2, 5), F (x)： xW2, G (x,y)： xNy,消去
(Vx) (F(X)T (3y) G(y,x))中的量词,并讨论其真值。
2.所有的主持人都很有风度。李明是个学生并且是个节口主持人。因此有些学生是很有风度。请用谓词逻辑中的推理理论证明上述推理。(个体域：所有人的集合)
3.设M(x):x是数，L(X9 y): x小于y,将“不存在最小的数。”符号化。
(an: 「(lc)(Vy)(M (x) /\ M (y) T L(x,)；))))
4.利用一阶逻辑的基木等价式，证明：
(Vx) (Vy) (F (x) ->G (y)) = (3x) F (x) t (Vy) G (y)
(an: VxVy (F (x) T G (y)) =Vx (F (x) —>Vy G (y))
=Vx (-iF (x) vVy G (y))
=Vx (「F (x)) vVy G (y)
=—i3xF (x) vVy G (y)
=3xF (x) —>VyG (y))
5.(Vx) (F(x) f-| A(x) ), (Vx) (A(x)VB(x), (3x) -] B(x)蕴涵(3x) -)F(x) (an: (1) 3x -] B(x)
(2)-i B(c)
(3)Vx (A(x)VB(x))
(4)A(c)VB(c)
(5)A(c)
(6)Vx (F(x) f-i A(x))
(7)F(c) 1 A(c)
(8)-i F(c)
(9)3x -| F(x))
6.符号化下列命题并推证其结论：
没有不守信用的人是可以信赖的，有些可以信赖的人是受过教育的人，因此，有些受过教育的人是可守信用的。(个体域：所有人的集合)
(an:
令M(x)： x是守信用的;J(x)： x是受过教冇的；D(x)： x是可以信赖的
前提：1 3x (-1 M(x)AD(x)), (3xD(x) AJ(x))有效结论:3x (J(x) A M(x))
证明：1) (3xD(x)AJ(x)) 前提
2) 3x D(x)AJ(y) 代替规则
3) 3x D(x) 合取
4) D(c) EI规则
5) J(y) 合取
6) VzJ(z) UG规则
7)J(c) UI规则
8) -| 3x (-| M(x) AD(x)) 前提规则
9) Vx-i (-1 M(x) AD(x)) 等价
10) Vx (M(x)v -| D(x)) 等价
11) M(c)v -i D(c) UI规则
12) M(c) 等价
13) M(c) A J(c) 合取
14) 3x (J(x) A M(x)) EG规则)
7?在一阶逻辑中，构造下面的证明：前提：撐3TGW),巴)结论：玉?)
(an: 1) Vx(F(x)—>G(x))
2)F(a)->G(a)
3)F(a)
4)G(a)
5)3G(x))
8.设解释I为：
(1)定义域D={-2, 3, 6}；
(2) F (x)： x<3；
G (x)： x>5o
在解释I下求公式(3x) (F (x) vG (x))的真值。
(an: ( 3x) (F (x) vG (x))
=(F (-2) vG (-2)) v (F (3) vG (3)) v (F (6) vG (6))
=(1 vO) 7 (1 vO) v (Ovl)
=1)
9.不存在能表示成分数的无理数。冇理数都能表示成分数。因此，冇理数都不是无理数。(an: F(x)： x为无理数，G(x)： x为有理数，H(x)： x能表示成分数)
10.设个体域为集合{a, b, c},试消去下列公式中的量词。
(1)(Vx) P(x) A (Vx) Q(x)
(2)(Vx) ( P(x) - Q(x))
课后习题：
p59： 1, 2
p62： 3, 6
p65： 2, 3
p72： 1, 4
p75： 1
p79： 2, 3
第三章集合论
1.设〈A, <)是偏序集，A={1, 2, 3, 4, 5, 6, 8}, S是整除关系，请画出 2.设A={1, 2, 3},求A上所有等价关系。 3.设全集E = N,有下列子集A= {1,2,8,10} B={nln2<509neN} C={ {/? I 汕J 以被3 整除，且料<2H],D = {n I 2,, i v 6,且i, n e N] 求1) ^u(CnD) 2) B-(4cC) 3)(? (an：Au(CnD) = {1,2,8,10}; B - (A n C) = B;(^4 n B) u D = {3,4,5,6,7,8,16,32}) 4.设集合A = {O,l},B = {a",c},试求： 1) AXB 2) A2X B 3) p(A)xA (an: AxB = {(O,d),(OQ,(O,c),(l,a),(l,b),(l,c)}; A2X B={ (0,0, a), (0,1, a), (1,0, Q), (1,1, a), (0,0, b), (0,1, b)9 (1,0, b), (1,1, b) (0,0,c),(0,1,c),(1,0,c),(1,1,c)} Q(A)X A={(0,O),({O},O),({1},O),({O,1},O),(0,1),({O},1),({1},1),({O,1},1)}) 5.一个年级170人■!?, 120名学生学英语，80名学牛学徳语，60名学生学H语，50名学生 既学英语又学徳语，25名学生既学英语又学日语，30名学生既学徳语又学tl 语，还有10 名学生同时学习三种语言。试问：有多少名学生这三种语言都没有学习？ (an:解： 设E 为全集，A 为学英语学生的集合，B 为学徳语学生的集合，C 为学日语学生的集合。 由公式， IAuBuCI=IAI+IBI+ICI-IAnBI-IBnCI-IAnCI+IAnBnCI 可得:IA U B L >CI=120+80+60-50-30-25+10 = 165 所以，这三种语言都没有学习的学生为170-165=5人。) 6. A={a, b, c, d}, R ), R2是 A 上的关系，其中 R|={ (a, a), (a, b), (b, a), (b, b), (c, c), (c, d), (d, c), (d, d) }, R 2={ (a, b), (b, a), (a, c), (c, a), (b, c), (c, b), (a, a), (b, b), (c, c) }。 (1) 写出R|和R2的关系矩阵，并画出Ri 和R2的关系图； (2) 判断它们是否为等价关系，是等价关系的求A 中各元素的等价类。 (an:) &为等价关系 等价类 Mi={a,b}, M 2={c,d} R2不为等价关系 r(/?), 5(/?),t(R),并分别画出它们的关系 图。 (an: 厂(/?) = {(Q,d),9,b),(c,c),(a,b),(b,d),(b,c)}; $(/?) = { (a, b),(仇 a), (b, c), (c,b)}; 『(/?) = {(a,a),(a,b),@,a),(a,c),(Z?,b),(b,c)}? 它们的关系图: 8.设集合A = {2,3,4, 6, 8,12, 24}, R 为A 上的整除关系，(1)画出偏序集(A, R)的 7 .集合 A = {a,b, c} R 是集合A 上的关系， R = {(a,b), (b, a), (b,c)} 哈斯图；(2)写出集合A屮的最大元、最小元、极大元、极小元：(3)写出A的子集 B = {2,3,6,12}的上界、下界、最小上界、最大下界。 (an: (1)半序集(A, R)的哈斯图如卜所示: (2)集合A中的最大元是24,无最小元，极大元是24,极小元是2与3。 (3)集合B的上界是12与24,无下界，最小上界是12,无最人下界。 9?设集合A = {a,b,c,d,e},R = {(a,b),(a,c),(a,d),(a,e),(b,e),(c,e),(d,e)}U/人，试画出偏序集(A,R)的哈斯图，并写出A的授大元，授小元，极大元和极小元。 (an: (A, <)的哈斯图为: a为A的极小元，也是最小元; e为A的极大元，也是最大元。 ) 11.设R是集合A上的二元关系，证叭R是传递的，当且仅当t (R) =R O (an:证明： 若R是传递的，又有R R,对于任何包含R的传递 关系，都冇，所以R满足传递闭包定义中 的全部条件，即t (R) =Ro 反Z,若t(R)=R,由传递闭包含定义中的条件1可得 R是传递的。 ) 12.设集合A = {0,123,4,5}, A 上的关系R = {(0,0), (1,1), (1,2), (1,3), (2,1),(2,2),(2,3),(3,1) (3,2), (3,3),(4,4), (4,5), (5,4), (5,5)},则R 在A 上构成的等价类是？ (an:) 13.设集合A= {1,2,3}，/?为A上的二元关系,R = {(1,2X3,1X23)}则心)是? (an: { (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) }) 14.设R是一个二元关系，设S={ (an: 1、证明: (1)???R是自反, ???若有xWA就有 ???s是自反的。 (2)因有Va, b>es 月?存在c,使Va, C>ER 且Vc, b>WR ???R是对称的 ???Vc, a>eR, ???Vb, a>es ?'?S是对称的 (3)设Va, b>, 则存在d, 0使<&, d>, ???R是传递的 ???Va, b>, A 即S是传递的 因此得证S是等价关系。 ) 课后习题： p85： 5, 6 p95： 3, 4 p99： 4, 5 p!04： 2, 4 pl09： 2, 5, 7 pll3： 4, 6 pll9： 1, 6, 8 pl27：2, 7 p130：1, 2, 4 pl35：2, 3, 4, p!39：3, 5 p!45 ： 1, 3, 6 笫四章函数 -i 1.设映射cr：z■: B T C Q,了都是双射，求证(nr) pl51： 1, 3, 4, 6 pl56： 2, 3, 4 pl64： 2 #include N=N/2; } while(!Empty(S)) { Pop(S,&e); printf("%d ",e); } } void main() { int n; printf("请输入待转换的值n：\n"); scanf ("%d",&n); conversion(n); }习题 1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？ (1)离散数学是计算机专业的一门必修课。 (2)李梅能歌善舞。 (3)这朵花真美丽！ (4)３＋２＞６。 (5)只要我有时间，我就来看你。 (6)x＝５。 (7)尽管他有病，但他仍坚持工作。 (8)太阳系外有宇宙人。 (9)小王和小张是同桌。 (10)不存在最大的素数。 解在上述10个句子中，(3)是感叹句，因此它不是命题。(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。其余语句都是可判断真假的陈述句，所以都是命题。其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。 2.判断下列各式是否是命题公式，为什么？ (1)(P→(P∨Q))。 (2)(?P→Q)→(Q→P)))。 (3)((?P→Q)→(Q→P))。 (4)(Q→R∧S)。 (5)(P∨QR)→S。 (6)((R→(Q→R)→(P→Q))。 解 (1)是命题公式。 (2)不是命题公式，因为括号不配对。 (3)是命题公式。 (4)是命题公式。 2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第（A）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下，放有本课程历年考试试卷的栏目名称是：（D ）． 选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标： 集合与关系《应用离散数学》 第3章 21世纪高等教育计算机规划教材 目录 3.1 集合及其运算 3.2 二元关系及其运算3.3 二元关系的性质与闭包3.4 等价关系与划分 3.5 偏序关系与拓扑排序3.6 函 数 3.7 集合的等势与基数3.8 多元关系及其应用 集合是现代数学中最重要的基本概念之一，数学概念的建立由于使用了集合而变得完善并且统一起来。集合论已成为现代各个数学分支的基础，同时还渗透到各个科学技术领域，成为不可缺少的数学工具和表达语言。对于计算机科学工作者来说，集合论也是必备的基础知识，它在开关理论、形式语言、编译原理等领域中有着广泛的应用。 本章首先介绍集合及其运算，然后介绍二元关系及其关系矩阵和关系图，二元关系的运算、二元关系的性质、二元关系的闭包，等价关系与划分、函数，最后介绍多元关系及其在数据库中的应用等。 3.1 集合及其运算 3.1.1 基本概念 集合是数学中最基本的概念之一，如同几何中的点、线、面等概念一样，是不能用其他概念精确定义的原始概念。集合是什么呢？直观地说，把一些东西汇集到一起组成一个整体就叫做集合，而这些东西就是这个集合的元素或叫成员。 例3.1 （1）一个班级里的全体学生构成一个集合。 （2）平面上的所有点构成一个集合。 （3）方程 的实数解构成一个集合。 （4）自然数的全体（包含0）构成一个集合，用N表示。 （5）整数的全体构成一个集合，用Z表示。 （6）有理数的全体构成一个集合，用Q表示。 （7）实数的全体构成一个集合，用R表示。 （8）复数的全体构成一个集合，用C表示。 （9）正整数集合Z+，正有理数集合Q+，正实数集合R+。（10）非零整数集合Z*，非零有理数集合Q*，非零实数集合R*。（11）所有n 阶(n≥2)实矩阵构成一个集合，用M n(R)表示，即 第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若 2+2=4,则 3+3=6. (2)若 2+2=4,则 3+3≠6. (3)若 2+2≠4,则 3+3=6. (4)若 2+2≠4,则 3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)0∨(0∧1) 0 （2）（p?r）∧(﹁q∨s) （0?1）∧(1∨1) 0∧10. （3）（p∧q∧r）?(p∧q∧﹁r) （1∧1∧1）? (0∧0∧0)0 (4)（r∧s）→(p∧q) （0∧1）→(1∧0) 0→0 1 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。” 答：p: 是无理数 1 q: 3是无理数0 r: 是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(q→p) （5）(p∧r) (p∧q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q q p q→p (p→q)→(q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) (p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1 所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)(p→(q∧r)) (4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q) 证明（2）(p→q)∧(p→r) (p∨q)∧(p∨r) p∨(q∧r)) p→(q∧r) （4）(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q) (p∨p)∧(p∨q)∧(q∨p) ∧(q∨q) 1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(p→q)→(q∨p) (2)(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (p→q)→(q p) (p q)(q p) (p q)(q p) (p q)(q p)(q p)(p q)(p q) (p q)(p q)(p q) ∑(0,2,3) 主合取范式： (p→q)→(q p) (p q)(q p) 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) P10 1对下面每个集合，判断2和{2}是否它的一个元素。 (1){x∈R | x是大于1的整数} (2){x∈R | x是某些整数的平方} (3){2, {2}} (4){{2},{{2}}} (5){{2}, {2,{2}}} (6){{{2}}} 解： {2}是(3)，(4)，(5)的元素。2是(1)，(3)的元素。 3 下列哪些命题成立？哪些不成立？为什么？ （1）φ∈{φ,{φ}} （2）φ?{φ,{φ}} （3）{φ}?{φ,{φ}} （4）{{φ}}?{φ,{φ}} 解： （1）成立 （2）成立 （3）成立 （4）成立 5 设A集合={a,b,{a,b},φ}。下列集合由哪些元素组成？ (1)A-{a,b}; (2){{a.b}}-A; (3){a,b}-A; (4)A--φ; (5)φ-A; (6)A-{φ}. 解： (1){{a,b},φ} (2)φ (3)φ (4) A (5)φ (6){a,b,{a,b}} 6 假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 解：A∩B 7 设A,B和C是任意集合，判断下列命题是否成立，并说明理由。 (1)若A?B,C?D，则A∪C?B∪D,A∩C?B∩D； (2)若ADB,CDD，则A∪CDB∪D,A∩CDB∩D； (3)若A∪B=A∪C，则B=C； (4)若A∩B=A∩C，则B=C； 解： (1)成立 (2)不一定成立 (3)不一定成立 (4)不一定成立 11（5）设A、B和C是集合，请给出(A-B)?(A-C)=φ成立的充要条件。解：错误！未找到引用源。A?B∪C 13试求： (1)P(φ); (2)P(P(φ)); (3)P({φ,a,{a}}) 解： (1){φ} (2){φ，{φ}} (3){φ，{φ}，{a}，{{a}}} 15 设A是集合，下列命题是否必定成立? （1）A∈P(A) （2）A?P(A) （3）{A}∈P(A) （4）{A}?P(A) 解： (1)成立 (2)不一定成立 (3)不一定成立 (4)成立 18设A＝{a,b}，B={b,c},下列集合由哪些元素组成？ (1)A×{a}×B; (2)P(A)×B; (3)(B×B) ×B; 解： (1){(a,a,b),(a,a,c),(b,a,b),(b,a,c)} (2){(φ,c),(φ,b),({a},c),({a},b),({b},c),({b},b),({a,b},c),({a,b},b)} (3){((b,b),c),((b,b),b),((b,c),c),((b,c),b),((c,b),c),((c,b),b),((c,c),c),((c,c),b)} 19 设A是任意集合，A3=(A×A)×A=A×(A×A)是否成立？为什么？ 解：不成立。 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R. 第七章作业 评分要求: 1、合计100分 2、给出每小题得分(注意: 写出扣分理由)、 3、总得分在采分点1处正确设置、 1 设R={ 习题1.1 1.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗? ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以 。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。 ⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：?p→?q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：p?q ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p?q。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：?p→q；该命题是真命题。 ⑶原命题符号化为：p→?q；该命题是假命题。 ⑷原命题符号化为：?p→?q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：p?q；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：p?q；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：p?q；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：p?q；该命题是真命题。 2015春课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1 设集合 A ={{2，3,4}，5，1}，下面命题为真是 A （选择题） [ A ] A．1 ∈A； B．2 ∈ A； C．3 ∈A； D．{3，2,1} ? A。 1-2 A,B,C 为任意集合，则他们的共同子集是 D （选择题） [ D ] A．C； B．A； C．B； D．?。 1-3 设 S = {N，Z，Q，R}，判断下列命题是否正确（是非题） （1） N ? Q，Q ∈S，则 N ? S，否［错］（2）-1 ∈Z，Z ∈S，则 -1 ∈S 。否［错］ 1-4 设集合 B = {4，3} ∩?， C = {4，3} ∩{ ? }，D ={ 3，4，? }， E = {x│x ∈R 并且 x2 - 7x + 12 = 0}， F = { 4，?，3，3}， 试问：集合 B 与那个集合之间可用等号表示 A （选择题） [A ] A. C; B. D; C. E; D. F. 1-5 用列元法表示下列集合：A = { x│x ∈N 且 3－x 〈 3 }（选择题） [D ] A. N; B. Z; C. Q; D. Z+ 1-6 为何说集合的确定具有任意性 ? (简答题) 按照所研究的问题来确定集合的元素。而我们所要研究的问题当然是随意的。所以，集合的定义（就是集合成分的确定）就带有任意性。 第二章二元关系 2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下： R = {〈x，y〉x，y ∈X 且 x > y } （综合题） 求：(1)domR =?; (2)ranR =?; (3)R 的性质。 所谓谓词表达法，即是将集合中所有元素的共同性质用一个谓词概括起来，如本题几例所示。有的书上称其为抽象原则。反过来，列元法则是遵照元素的性质和要求，逐一将他们列出来，以备下用,结果如下： R = {<1,1>,<2,2>,<3,3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={3,2,1}； (3)R 的性质:自反,对称,传递性质. 2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}， 试给出 dom（R 。R）。（选择题） [ B ] A. 3； B. {3}； C. 〈3，3〉； D.{〈3，3〉}。 2-3 判断下列映射 f 是否是 A 到 B 的函数；以及函数的性质。最后指出 f：A→B 中的双射函数。（选择题） [ B ] （1）A = {1，2，3}，B = {4，5}， f = {〈1，4〉〈2，4〉〈3，5〉}。 （2）A = {1，2，3} = B， f = {〈1，1〉〈2，2〉〈3，3〉}。 （3）A = B = R， f = x 。 第二章习题二 1、求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) ?x?y(P(x)→Q(y)) ??x?y(?P(x)∨Q(y)) 条件式的等值式 ??x(?P(x)∨?yQ(y)) 辖域的扩充与收缩规律 ??x?P(x)∨?yQ(y) 辖域的扩充与收缩规律 ???xP(x)∨?yQ(y) 量词的德摩律 ??xP(x)→?yQ(y) 条件式的等值式 2、把下列各式转换为前束范式 (1) ?x(?(?yP(x,y)→(?zQ(z)→R(x)))) ??x(?(?yP(x,y)→(??zQ(z)∨R(x)))) 条件式的等值式 ??x(?(??yP(x,y)∨(??zQ(z)∨R(x)))) 条件式的等值式 ??x((???yP(x,y)∧(???zQ(z)∧?R(x)))) 德摩律 ??x((?yP(x,y)∧(?zQ(z)∧?R(x)))) 否定的否定 ??x?y?z ((P(x,y)∧(Q(z)∧?R(x)))) 量词辖域的扩张与收缩 ??x?y?z (P(x,y)∧Q(z)∧?R(x)) 量词辖域的扩张与收缩 (2) ?x?y((?zP(x,y,z)∧?uQ(x,u))→?vQ(y,v)) ??x?y(? (?zP(x,y,z)∧?uQ(x,u)) ∨?vQ(y,v)) 条件式的等值式 ??x?y( (??zP(x,y,z) ∨??uQ(x,u)) ∨?vQ(y,v)) 德摩律 ??x?y( (?z?P(x,y,z) ∨?u?Q(x,u)) ∨?vQ(y,v)) 德摩律 ??x?y?z?u?v ( (?P(x,y,z) ∨?Q(x,u)) ∨Q(y,v)) 德摩律 ??x?y?z?u?v ( ?P(x,y,z) ∨?Q(x,u)∨Q(y,v)) 德摩律 (3) ?xF(x) →?yP(x,y) ??zF(z) →?yP(x,y) 约束变元与自由变元同名，故约束变元改名 ???zF(z)∨?yP(x,y) 条件式的等值式 ??z?F(z)∨?yP(x,y) 德摩律 ??z?y(?F(z)∨P(x,y)) 德摩律 (4) ?x(P(x,y)→?yQ(x,y,z)) ??x(P(x,y)→?sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名 ??x(?P(x,y) ∨?sQ(x,s,z)) 条件式的等值式 ??x?s(?P(x,y)∨Q(x,s,z)) 辖域的扩充与收缩 (5) ?x(P(x,y)??yQ(x,y,z)) ??x(P(x,y)??sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名 ??x((P(x,y)→?sQ(x,s,z)) ∧(?sQ(x,s,z)→P(x,y))) 双条件的等值式 ??x((P(x,y)→?sQ(x,s,z)) ∧(?tQ(x,t,z)→P(x,y))) 后面约束变元与前面同则后面换名??x((?P(x,y)∨?sQ(x,s,z))∧(??tQ(x,t,z)∨P(x,y))) 条件式的等值式 ??x((?P(x,y)∨?sQ(x,s,z))∧(?t?Q(x,t,z)∨P(x,y))) 德摩律 离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r 4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对 离散数学第二章 1. 有序二元组也称序偶,设 A , B 为任意集合，A 和 B 的笛卡尔积用 A × B 表示，定义为 A × B = {(a , b ) | a ∈ A , b ∈ B }。 2. 推广 n 个集合的笛卡儿积为A 1 × A 2 × … × A n = {(x 1, x 2, …, x n ) | x i ∈ A i , i = 1, 2, …, n }。 3. 笛卡尔乘与交并集符号之间满足分配率： A × (B ? C ) = (A × B ) ? (A × C ) 4. 笛卡尔积 A × B 的任意一个子集 ρ 称为由 A 到 B 的一个二元关系，当 A = B 时，称 ρ 是 A 上 的二元关系。 5. 几种特殊的关系：空关系，全关系（普遍关系）记为U A ，恒等关系I A = {(a , a ) | a ∈ A }。 6. 关系的表示方法：集合表示法，矩阵表示法，关系图表示法（结点，单边）自环 7. A,B 上的关系的交，并，补，运算结果都是A 到B 的关系。 8. ，称为关系p 的逆运算也记为p-1 9. 关系的复合运算：当且仅当存在元素 b ∈ B ，使得 a ρ1 b ，b ρ2 c 时，有 a (ρ1 ? ρ2) c 。 10. I A ? ρ = ρ ? I B =p ，关系的复合满足结合律：(ρ1 ? ρ2) ? ρ3 = ρ1 ? (ρ2 ? ρ3)。 11. 规定：ρ 0 = {(a , a ) | a ∈ A }，即 ρ 0 = I A 12. 复合关系的求法：定义，关系图，矩阵 13. 设 A 、B 均是有限集，ρ1、ρ2 都是由 A 到 B 的关系，它们的关系矩阵分别为和 ，则下列关系的关 系矩阵如何？ ρ1 ? ρ2，ρ1 ? ρ2，ρ1'，ρ1 - ρ2 ，ρ1-1。 14. 设 ρ1, ρ2 是集合 A 上的任意的关系，则 (ρ1 ? ρ2)-1 = ρ2-1 ? ρ1-1 15. 关系的性质：自反，非自反，反自反；对称，非对称，反对称；可传递，不可传递； 16. 反自反的关系一定是非自反的关系；若ρ是 A 上的反对称关系，则由定义知，在ρ中，(a , b ) 与 (b , a ) 至多有一个出现，其中 a ≠ b 。 17. {(1, 2), (3, 0), (3, 2)}这个关系可传递 18. 设 ρ 为 A 上的关系，（1） ρ 在 A 上自反当且仅当 I A ? ρ （2） ρ 在 A 上反自反当且仅当 ρ ∩I A = Φ （3） ρ 在 A 上对称当且仅当 ρ = ρ -1 （4） ρ 在 A 上反对称当且仅当 ρ ∩ ρ -1 ? I A （5） ρ 在 A 上传递当且仅当 ρ ? ρ ? ρ 。（自证，ppt 中有过程） 19.利用关系矩阵判断： }),(|),{(~ρρ ∈=b a a b 第1章 命题逻辑 一、单项选择题 1．下列语句中不是命题的有（ C ）. A 9+5≤12 ； B. 1+3=5； C. 我用的计算机CPU 主频是1G 吗？； D.我要努力学习。 2. 下列语句是真命题为( C )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗？ 3. 设命题公式G ：)(R Q P ∧→?,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( D ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式Q Q P →∨)(为 ( B ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 下列命题公式等值的是( C ) B B A A Q P Q Q P Q B A A B A A Q P Q P ),()D (),()C ()(),()B (,)A (∧∨?∨∨?∨→→→?→→∨?∧?6. 设P ：我将去市里，Q ：我有时间．命题“我将去市里，仅当我有时间时”符号化为( B ) Q P Q P Q P P Q ?∨??→→)D ()C ()B ()A (7．设P ：我听课，Q ：我看小说．命题 “我不能一边听课，一边看小说”的符号为（D ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 8. 命题公式)(Q P →?的主析取范式是( A )． (A) Q P ?∧ (B) Q P ∧? (C) Q P ∨? (D) Q P ?∨ 9. 前提为：P Q P ,?→；则有效结论是( A,D )． (A) P (B) ?P (C) Q (D)?Q 10．下列表达式正确的有（ A, C ）离散数学第1章习题答案
离散数学形考任务1-7试题及答案完整版
应用离散数学-集合与关系
离散数学(屈婉玲版)第一章部分习题分解
离散数学作业答案
离散数学第一章部分课后习题参考答案
离散数学规范标准答案屈婉玲版第二版高等教学教育出版社课后答案
华东师范大学离散数学章炯民课后习题第1章答案
离散数学答案第二章习题解答
离散数学课后习题答案第二章
离散数学第七章二元关系课后练习习题及答案
离散数学 第1章 习题解答
离散数学答案
离散数学 杨圣洪等著 第二章习题二解答
离散数学章练习题及答案
离散数学(屈婉玲版)第四章部分答案
离散数学第二章
《离散数学》全程练习册(2011)答案(讲解用)
相关主题
文本预览