离散数学考研习题讲解

离散数学考研复习2/3/20231复习时注意准确掌握每个概念灵活应用所学定理注意解题思路清晰证明问题时,先用反向思维(从结论入手)分析问题,再按正向思维写出证明过程.2/3/20232全书知识网络：图论篇同构同构<{1,0},,,,,><p(E),~,∩,∪,－,>格与布尔代数半群,独异点,群,环,域<P(A×A),~,∩,∪,－,,,c,r,s,t><YX,~,∩,∪,－,,,-1>代数系统篇n元运算命题逻辑谓词逻辑集合初步二元关系函数集合论篇数理逻辑篇2/3/20233总复习复习重点第一章命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.重言式的证明.4.等价公式的证明,记住并能熟练应用常用公式.5.会写命题公式的范式,能应用范式解决问题.6.熟练掌握命题逻辑三种推理方法.2/3/20234第二章谓词逻辑1.准确掌握有关概念.2.会命题符号化.(如2.3题)3.掌握常用的等价公式和重言蕴涵式.包括:

带量词的公式在个体域内展开式,量词否定,量词辖域扩充,量词分配公式.4.会用等价公式求谓词公式的真值.(如2.13)5.会写前束范式6.熟练掌握谓词逻辑推理.第三章集合论初步1.集合的表示,幂集,全集,空集.2.集合的三种关系(包含,相等,真包含)的定义.3.集合的五种运算及相关性质.4.应用包含排斥原理.2/3/20235第四章二元关系1.关系的概念,表示方法.2.二元关系的性质的定义,熟练掌握性质的判断及证明.3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质)4.掌握等价关系的判断,证明,求等价类和商集.5.偏序关系的判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.第五章函数1.函数的定义.2.函数的类型,会判断,会证明.3.会计算函数的复合(左复合),求逆函数.知道有关性质.4.了解集合的特征函数.2/3/20236第六章代数系统1.掌握运算的定义.2.熟练掌握二元运算的性质的判断及证明.3.掌握代数系统的同构定义,会证明.了解同构性质的保持.4.了解半群,独异点,*环和*域的概念.5.熟练掌握群,子群,交换群(会证明),了解循环群.*6,子群的陪集,Lagrange定理及其推论,(会应用).*第七章格与布尔代数*

1.掌握格的定义,了解格的性质.*2.会判断格,分配格,有补格和布尔格,*3.重点掌握两个元素的布尔代数的性质(10个).*4.会写两个元素的布尔表达式的范式.(实质是第一章的主析取和主合取范式).2/3/20237第八章图论1.掌握图的基本概念.(特别注意同构的概念)2.熟练掌握图中关于结点度数的定理.(会应用)3.无向图的连通性的判定,连通分支及连通分支数的概念.4.有向图的可达性,强连通,单侧连通和弱连通的判定.求强分图,单侧分图和弱分图.5.会求图的矩阵.有向图邻接矩阵的应用。6.会判定欧拉图和汉密尔顿图.*7.二部图与匹配.*8.会判定平面图,掌握欧拉公式，了解对偶图.9.掌握树的基本定义,v和e间的关系式.会画生成树,会求最小生成树.根树的概念,完全m叉树,会画最优树,*会设计前缀码.2/3/20238总复习复习重点第一章命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.重言式的证明.4.重言蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能熟练应用常用公式.6.会写命题公式的范式,*能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法.2/3/20239第一章命题逻辑1.联结词定义了六个逻辑联结词，分别是：

(1)否定“”

(2)合取“∧”

(3)析取“∨”

(4)异或“

”

(5)蕴涵“”

(6)等价“”要熟练掌握这六个联结词在自然语言中所表示的含义以及它们的真值表的定义。：否定表示“不”∧：合取表示“不但…,而且...”“并且”∨：析取表示“或者－可兼取的或”：异或表示“或者－不可兼取的或”：蕴涵表示“如果…,则...”

:等价表示“当且仅当”“充分且必要”可以将这六个联结词看成六种“运算”。2/3/202310联结词的定义(包括真值表和含义).特别要注意：“或者”的二义性,即要区分给定的“或”是“可兼取的或∨”还是“不可兼取的或”。“”的用法，它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件.

PQP∧QP∨QPQPQPQ

0000110

0101101

10010011111110

2/3/2023112.会命题符号化.

例如P:我有时间.Q:我上街.R:我在家.

表示P是Q的充分条件:如果p,则Q.只要P,就Q.PQ

表示P是Q的必要条件:仅当P,才Q.只有P,才Q.QP

如果P,则Q;否则R.(PQ)(PR)3.重言式的证明.

方法1.列真值表.(R(QR)(PQ))P

方法2.用公式的等值变换,化简成1.例如证明(R(QR)(PQ))P是重言式.证:上式(R(QR)(PQ))P(PQPQ)(R(QR)(PQ))P(公式的否定公式)((R(QR))((PQ)P)(结合律)((RQ)(RR))((PP)(QP)(分配律)(RQ)(QP)RQQP1(互补,同一律)2/3/2023124.重言蕴涵式的证明,

记住常用的公式.

重言蕴涵式:AB是重言式,则称A重言蕴涵B.(AB)

方法1.列真值表.

方法2.假设前件真,推出后件真.(即直接推理)

方法3.假设后件假,推出前件假.(即反证法)例证明(P(QR))((PQ)(PR))是重言蕴涵式.证:假设后件(PQ)(PR)假,则PQ为1,PR为0,于是P为1,R为0,进而又得Q为1.所以QR为0,所以前件P(QR)为0.所以(P(QR))((PQ)(PR))为重言式.

对于给定一个题,究竟是用哪种方法,原则上哪种都可以.但是哪个方法简单,要根据具体题而定.ABA

B0010111001112/3/2023135.等值公式的证明,记住常用的公式.

方法1.列真值表.

方法2.用公式的等值变换.

例如:证明P(QR)(P∧Q)RP(QR)P(QR)(PQ)R

(PQ)∨R(P∧Q)R注意:不论是证明重言蕴涵式,还是证明等值公式以及后边的求公式的范式,命题逻辑推理,都应用9，23页的公式。必须记忆一些常用的公式2/3/2023146.命题公式的范式1)析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)是合取式.

2)合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)是析取式.3)析取范式与合取范式的求法.4)极小项及其性质.

m3m2m1

m0PQP∧QP∧QP∧QP∧Q000000010101001010100100111110002/3/2023156)极大项及其性质.M0M1M2M3PQP∨QP∨QP∨QP∨Q0000

011101011

011101011011111111

07)主析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)极小项.

8)主合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)极大项.2/3/2023169).会求主析取范式和主合取范式.求下面命题公式的范式:A(P,Q,R)

(P∨Q)R方法1.列真值表.主析取范式A(P,Q,R)

(P∨Q)R(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式A(P,Q,R)

(P∨Q)R

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)PQR(P∨Q)R000100110100011110001011110011112/3/202317方法2.用公式的等值变换.主析取范式;A(P,Q,R)

(P∨Q)R(P∨Q)∨R(P∧Q)∨R(P∧Q∧(R∨R))∨((P∨P)∧(Q∨Q)∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式:A(P,Q,R)

(P∨Q)R(P∨Q)∨R(P∧Q)∨R(P∨R)∧(Q∨R)(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)2/3/202318已知A(P,Q,R)的主析取范式中含有如下极小项:

m0,m3,m4,m5,m7求它的主合取范式.解:A(P,Q,R)的主合取范式中含有极大项:M1,M2,M6A(P,Q,R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)*范式的应用如习题:安排工作(排课表),携带工具箱,判断矿样种类，判断输出信号

…2/3/2023197.会用三种推理方法,进行逻辑推理.

会用三个推理规则:前提引入，结论引入，附加前提引入例如:证明((A∧B)C)∧D∧(C∨D)A∨B1.直接推理:⑴D

前提引入⑵C∨D前提引入⑶C⑴⑵析取三段论Q,(P∨Q)P⑷(A∧B)C前提引入⑸(A∧B)⑶⑷拒取式Q,PQP⑹A∨B⑸德摩根

(P∧Q)P∨Q2/3/202320((A∧B)C)∧D∧(C∨D)A∨B2.附加前提论证:适用于结论是蕴涵式.A∨BAB⑴A附加前提引入⑵(A∧B)C前提引入(3)(A∨B)∨C蕴涵等值式⑷A∨(

B∨C)结合律⑸A(BC)⑷蕴涵等值式⑹BC⑴⑸

假言推理⑺D前提引入⑻C∨D前提引入⑼C⑺⑻

析取三段论(10)B⑹⑼拒取式(11)AB附加前提论证2/3/202321((A∧B)C)∧D∧(C∨D)A∨B3.归谬法:⑴(A∨B)假设前提错误⑵A∧B⑴德摩根⑶(A∧B)C前提引入⑷C

⑵

⑶假言推理⑸D前提引入⑹C∨D前提引入⑺C⑸⑹析取三段论⑻C∧C⑷⑺合取引入由⑻得出矛盾，根据归谬法说明推理正确。2/3/202322考研题分析：例1：将下列句子翻译成命题公式：（1）仅当我有时间且天不下雨，我才去镇上。（2）张刚总是在图书馆看书，除非图书馆不开门或张刚生病。[分析]“仅当”是指“仅当”后面的事件是结论成立的必要条件；“除非”是指只要不出现“除非”后面的事件，则结论一定成立。[解答]（1）设P：我有时间。Q：天下雨。R：我去镇上则原命题翻译成：R(P∧Q)(2)设P:张刚在图书馆看书。Q:图书馆开门.R:张刚生病则原命题翻译成:(Q∧R)P2/3/202323例2：甲乙丙丁4人有且仅有2人参加围棋优胜比赛。关于谁参加比赛，下列4种判断是正确的。（1）甲和乙只有一人参加。（2）丙参加，丁必参加。（3）乙或丁至多参加一人。（4）丁不参加，甲也不会参加。请推出哪两个人参加了比赛。[分析]本题考察两个知识点：命题公式的翻译和范式。[解答]首先将命题符号化：设A:甲参加了比赛；B:乙参加了比赛；C:丙参加了比赛；D:丁参加了比赛。依题意有：2/3/202324（1）AB(A∧B)∨(A∧B)（2）CD(C∨D)（3）(B∧D)B∨D（4）DAD∨A所以，原命题为：((A∧B)∨(A∧B))∧(C∨D)∧(B∨D)∧(D∨A)((A∧B∧C)∨(A∧B∧D)∨(A∧B∧C)∨(A∧B∧D))∧((B∧D)∨(B∧A)∨(D∧D)∨(D∧A)(A∧B∧C∧D)∨(A∧B∧C∧D)∨(A∧B∧D)1根据题意有且仅有2人参加比赛，故(A∧B∧C∧D)真值为0，所以只有(A∧B∧C∧D)为真，甲和丁参加了比赛。2/3/202325中科院计算机技术研究所1999年离散数学考研试题和答案

一.(8分)求与公式(x2ornotx1)->x3

逻辑等值的主合取范式和主析取范式.2/3/202326一.(8分)求与公式(x2ornotx1)->x3

逻辑等值的主合取范式和主析取范式.解：(x2ornotx1)->x3

符号化为(x2

∨x1)->x3

(x2

∨x1)∨x3(x2

∧x1)∨x3

(x2∨x3)∧(x1∨x3)(x2∨x3∨(x1∧x1))∧(x1∨x3∨(x2∧x2))(x1∨x2∨x3)

∧(x1∨x2∨x3)

∧(x1∨x2∨x3)主合取范式2/3/202327(x2ornotx1)->x3

符号化为(x2

∨x1)->x3

(x2

∨x1)∨x3(x2

∧x1)∨x3

(x2∧x1∧(x3∨x3))∨(x3∧(x2∨x2)∧(x1∨x1))(x1∧x2∧x3)∨(x1∧x2∧x3)∨(x1∧x2∧x3)∨(x1∧x2∧x3)∨(x1∧x2∧x3)主析取范式2/3/202328主合取范式:(notx1ornotx2orx3)and(x1ornotx2orx3)and(x1orx2orx3)

主析取范式:(x1andnotx2andnotx3)or(x1andx2andx3)or(x1andnotx2and

x3)or(notx1andx2andx3)or(notx1andnotx2andx3)

2/3/202329二.(8分)判断下列各公式是:1.永真式2.永假式3.其它

(1)(p->(q->r))->(q->(p->r))

(2)(notporq)<->(pand(pandq))

(3)(notporq)andnot(qornotr)andnot(rornotpornotq)

(4)(qandp)->(porq)2/3/202330二.(8分)判断下列各公式是:1.永真式2.永假式3.其它

(1)(p->(q->r))->(q->(p->r))

解:用公式的等值演算和真值表法都较麻烦,下面先分析一下.公式具有蕴涵式的结构,蕴涵式真值为0当且仅当蕴涵式的前件为1后件为0.假设后件为0,则可以得出q为1,p为1,r为0;这时前件也为0,所以(1)式不存在真值为0的情况,因此(1)为1永真式.2/3/202331二.(8分)判断下列各公式是:1.永真式2.永假式3.其它

(2)(notporq)<->(pand(pandq))解:先符号化为(p∨q)(p∧(p∧q))(pq)(p∧q)

pqpqp∧q(pq)(p∧q)0010001100100

0111111

所以(2)为3.其它2/3/202332二.(8分)判断下列各公式是:1.永真式2.永假式3.其它

(3)(notporq)andnot(qornotr)andnot(rornotpornotq)

符号化为:(p∨q)∧(q∨r)∧(r∨p∨q)解:先分析是否有可能真值为1.若真值为1,则p∨q真值为1;(q∨r)真值为1,q为0,r为1;(r∨p∨q)真值为1,则r∨p∨q真值为0,r为0,p为1,q为1,矛盾.所以(3)式不存在真值为1的情况,即是一个永假式.2/3/202333二.(8分)判断下列各公式是:1.永真式2.永假式3.其它

解:(4)(qandp)->(porq)符号化为

(p∧q)(p∨q)(p∧q)∨(p∨q)p∨q∨p∨q1所以(4)式为1永真式.2/3/202334一、在命题逻辑中将下列命题符号化1.电灯不亮当且仅当灯泡或开关发生故障。

解：设p：电灯亮，q:灯泡发生故障，r：开关发生故障

2.仅当你去，我才留下。2/3/202335例：三个人估计比赛结果，甲说“A第一，B第二”，乙说“C第二,D第四”,丙说：“A第二，D第四”。结果，3人估计的都不全对，但都对了一个，问A,B,C,D的名次。[解答]设P：A是第一；Q：B是第二；R：C是第二；S：D是第四。E：A是第二。则根据题意有：(PQ)∧(RS)∧(ES)((P∧Q)∨(P∧Q))∧((R∧S)∨(R∧S))∧((E∧S)∨(E∧S))利用分配律展开(P∧Q∧R∧S∧E)∨(P∧Q∧R∧E∧S)因R与E矛盾，故只有P∧Q∧R∧E∧S为真，即C第一，B第二，A第三，D第四。2/3/202336

第二章谓词逻辑1.准确掌握有关概念.2.会命题符号化.3.掌握常用的等值公式和重言蕴涵式.包括:

带量词的公式在个体域内展开式,量词否定,量词辖域扩充,量词分配公式.4.会用等值公式求谓词公式的真值.5.会写前束范式6.熟练掌握谓词逻辑推理.2/3/2023372.会命题符号化.

命题的符号表达式与个体域有关。当个体域扩大时，需要添加用来表示个体特性的谓词，称此谓词为特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。如“所有自然数...”、“有些大学生...”。如何添加特性谓词，这是个十分重要的问题，这与前边的量词有关。

如果前边是全称量词，特性谓词后边是蕴含联结词“→”；

如果前边是存在量词，特性谓词后边是合取联结词“∧”。另外有些命题里有的个体词在句中没有明确的量词,而在写它的符号表达式时,必须把隐含的量词明确的写出来.2/3/202338例如1、金子闪光,但闪光的不一定都是金子.设:G(x):x是金子.F(x):x闪光.x(G(x)F(x))x(F(x)G(x))x(G(x)F(x))x(F(x)G(x))2、有些液体可以溶解所有固体.F(x):x是液体.S(x):x是固体.D(x,y):x可溶解y.x(F(x)y(S(y)D(x,y)))3、每个大学生都爱好一些体育活动。S(x):x是大学生,L(x,y):x爱好y,P(x):x是体育活动.x(S(x)y((P(y))L(x,y)))

2/3/2023393.掌握常用的等值公式和重言蕴涵式.包括:

带量词的公式在个体域内展开式,量词否定,量词辖域扩充,量词分配公式.

设个体域为{a1,a2,....,an}，则

1).xA(x)A(a1)∧A(a2)∧......∧A(an)2).xB(x)B(a1)∨B(a2)∨......∨B(an)1).xA(x)xA(x)2).xA(x)xA(x)1).xA(x)∨Bx(A(x)∨B)2).xA(x)∧Bx(A(x)∧B)3).xA(x)∨Bx(A(x)∨B)4).xA(x)∧Bx(Ａ(x)∧B)5).B→xA(x)x(B→A(x))2/3/2023406).B→xA(x)x(B→A(x))7).xA(x)→Bx(A(x)→B)8).xA(x)→Bx(A(x)→B)1).x(A(x)∨B(x))xA(x)∨xB(x)2).x(A(x)∧B(x))xA(x)∧xB(x)3).x(A(x)∧B(x))xA(x)∧xB(x)4).xA(x)∨xB(x)x(A(x)∨B(x))4.会用等值公式求谓词公式的真值.例设个体域为{1,2},A(x,y):x+y=xy,求xyA(x,y)的真值.xyA(x,y)xyA(x,y)yA(1,y)yA(2,y)(A(1,1)A(1,2))(A(2,1)A(2,2))(11)(10)12/3/2023415.将下面谓词公式写成前束范式(xF(x,y)yG(y))xH(x,y)(xF(x,y)yG(y)xH(x,y)(去)xF(x,y)yG(y)xH(x,y)(德.摩根)xF(x,y)yG(y)xH(x,y)(量词否定)xF(x,z)yG(y)tH(t,z)(变元换名)xyt((F(x,z)G(y)H(t,z))(辖域扩充)2/3/2023426.熟练掌握谓词逻辑推理.1).注意使用EI、UI、EG、UG的限制条件,特别是EI,UG2).对于同一个个体变元，既有带也有带的前提，去量词时，应先去后去，这样才可以特指同一个个体c.3).去量词时，该量词必须是公式的最左边的量词，且此量词的前边无任何符号，它的辖域作用到公式末尾。下面的作法是错误的：正确作法:⑴xP(x)→xQ(x)前提引入

⑴xP(x)→xQ(x)前提引入

⑵P(c)→xQ(x)UI⑴⑵xP(x)∨xQ(x)⑴蕴涵或⑵xP(x)→Q(c)EI⑴⑶xP(x)∨xQ(x)⑵实际上x的辖域扩充后⑷x(P(x)∨Q(x))⑶量词改成为x⑸P(c)∨Q(c)⑷EI⑹P(c)→Q(c)⑸蕴涵等值式2/3/202343下面的作法是错误的：正确作法:⑴xP(x)前提引入⑴xP(x)前提引入⑵P(c)⑴UI⑵xP(x)⑴实际上⑴中量词不是⑶P(c)⑵EIx而是x

⑴xyP(x,y)前提引入⑴xyP(x,y)前提引入⑵xP(x,c)EI⑴⑵yP(c,y)UI⑴令P(x,y):y是x的生母，显然⑵是个假命题4).添加量词时，也要加在公式的最左边，(即新加的量词前也无任何符号！！)且其辖域作用到公式的末尾。 例如下面作法是错误的:⑴xP(x)→Q(c)前提引入

⑵

xP(x)→yQ(y)⑴EG2/3/202344例如.证明下面推理的有效性.证明:⑴x(A(x)∧D(x))

前提引入⑵A(a)∧D(a)

⑴EI⑶A(a)⑵化简规则⑷D(a)

⑵化简规则⑸x(A(x)→(B(x)→C(x)))前提引入⑹A(a)→(B(a)→C(a))⑸UI⑺B(a)→C(a))⑶⑹假言推理⑻x(A(x)→(C(x)∨D(x)))前提引入⑼A(a)→(C(a)∨D(a)))⑻UI⑽C(a)∨D(a)⑶⑼假言推理⑾C(a)⑷⑽析取三段论⑿B(a)⑺⑾拒取式⒀A(a)∧B(a))⑶⑿合取引入⒁x(A(x)∧B(x))⒀EG2/3/202345

在谓词逻辑中符号化下列命题，并给出结论有效性的证明：如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过，有些人未曾失败过，所以有些人不怕困难。解：令H(x):x是人，D(x):x怕困难，S(x)：x获得成功，F(x):x失败过。则本题符号化为前提：结论：2/3/202346中科院99.(9分)问anyxexistyP(x,y)->existyanyxP(x,y)是否谓词演算的有效式?证明你的结论.解答：用谓词公式表示：判断xyP(x,y)→yxP(x,y)是否为重言蕴涵式。不是，取一特定的解释I如下：设P(x,y)：x<=y,个体域为自然数集合。则有：xyP(x,y)为真，而yxP(x,y)为假，故给定公式在解释I下为假，故不是谓词公式的有效式。2/3/202347

四.(9分)将下列推理符号化并给出形式证明:

鸟会飞,猴子不会飞;所以,猴子不是鸟.解：设P(x):x会飞；Q(x):x是鸟；R(x):x是猴子前提：x(Q(x)→P(x)),x(R(x)→P(x))结论：x(R(x)→Q(x))证明：⑴x(Q(x)→P(x))前提引入⑵x(R(x)→P(x))前提引入⑶Q(a)→P(a)

(1)UI⑷R(a)→P(a)

⑵UI⑸P(a)→Q(a)(3)假言易位⑹R(a)→Q(a)(4)⑸假言三段论⑺x(R(x)→Q(x))

⑹UG2/3/202348中科院98：(12分)将命题"并非E1中的每个数都小于或等于E2中的每个数"按以下要求的形式

表达出来:

(1)出现全称量词,不出现存在量词;

(2)出现存在量词,不出现全称量词.解：F(x):x属于E1;G(x):x属于E2;H(x,y):x小于或等于y。（1）x(F(x)→y(G(y)→H(x,y))(2)x(F(x∧y(G(y)∧H(x,y))

2/3/202349中科院2000：在谓词逻辑中是否可以从前提x(p(x)→q(x))，x(r(x)∧q(x))推出结论x(r(x)→p(x))证明：⑴x(r(x)∧q(x))前提引入⑵r(c)∧q(c)⑴EI⑶q(c)⑵化简规则⑷r(c)⑵化简规则⑸x(p(x)→q(x))前提引入⑹p(c)→q(c)⑸UI⑺p(c)(3)⑹拒取式(8)r(c)∧p(c)(4)(7)合取引入(9)x(r(x)∧p(x))(8)EG(10)

x(r(x)∨p(x))⑼德摩根（11）x(r(x)→p(x))（10）量词转换，蕴涵等值式2/3/202350重庆大学98年：用推理规则证明：x(P(x)∨Q(x))xP(x)→xQ(x)证明：⑴xP(x)附加前提引入⑵xP(x)⑴量词转换⑶P(c)⑵EI⑷x(P(x)∨Q(x))前提引入(5)P(c)∨Q(c)(4)UI(6)Q(c)(3)(5)析取三段论(7)xQ(x)(6)EG2/3/202351重庆大学98年：填空题（2分）若个体域是非负数集，A(x,y)表示x+y=y，则xyA(x,y)的真值是：

12/3/202352上海交大99年考研（6分）设A(x):x是人；B(x):x是错误；C(x,y):x犯了y；D(x,y):y能改正x。用上述谓词构成下列语句的谓词公式：(1)人都会犯错误。(2)并非所有人犯错误都能改。(3)有的错误任何人犯了都不能改。x(A(x)→y(B(y)∧C(x,y))xy(A(x)∧B(y)∧C(x,y)∧D(y,x))y(B(y)∧x((A(x)∧C(x,y))→D(y,x))2/3/202353第三章集合论初步1.集合的表示,幂集,全集,空集.2.集合的三种关系(包含,相等,真包含)的定义及证明.3.集合的五种运算交∩，并∪，相对补－，绝对补~，对称差及相关性质.4.应用包含排斥原理.2/3/202354第三章集合论初步基本概念:集合与元素,子集与真子集,空集,全集,幂集,并集,交集,相对补集(差集),绝对补集(补集)1.集合的表示,元素与集合的属于关系∈.

集合的三种表示方法:

枚举法:一一列出集合中的元素.

谓词描述法:用谓词描述集合中元素的性质.

文氏图:用一个平面区域表示.2.集合的三种关系(被包含,相等,被真包含)的定义及证明.ABx(x∈Ax∈B)A=BABBAx(x∈Ax∈B)ABABA≠Bx(x∈Ax∈B)x(x∈BxA)

2/3/2023553空集,全集,幂集空集φ:无元素的集合.x∈Φ是矛盾式.(空集是唯一的)

全集E:包含所讨论所有集合的集合.(全集不唯一)x∈E是重言式幂集:由A的所有子集构成的集合.

P(A)={X|XA}|P(A)|=2|A|

4.掌握集合的五种运算及相关性质.A∩B={x|x∈A∧x∈B}x∈A∩Bx∈A∧x∈BA∪B={x|x∈A∨x∈B}x∈A∪Bx∈A∨x∈BA-B={x|x∈A∧xB}x∈A-Bx∈A∧xB~A=E-A={x|x∈E∧xA}={x|xA}x∈~AxAA-B=A∩~BAB=(A-B)∪(B-A)={x|(x∈A∧xB)∨(x∈B∧xA)}AB=(A∪B)-(A∩B)2/3/202356例1.已知全集E={Φ,{Φ}},AE,计算:a)P({Φ})P({Φ})=()b)P(A)∩P(~A)=()c)P(E)-P(~{{Φ}})=()解:a)因为任何集合A,都有AA=Φ所以

P({Φ})P({Φ})=Φb)因为ΦAΦ~A,即Φ∈P(A)Φ∈P(~A)所以

P(A)∩P(~A)={Φ}c)P(E)={Φ,{Φ},{{Φ}},{Φ,{Φ}}}~{{Φ}}={Φ}P(~{{Φ}})=P({Φ})={Φ,{Φ}}P(E)-P(~{{Φ}}))={Φ,{Φ},{{Φ}},{Φ,{Φ}}}-{Φ,{Φ}}={{{Φ}},{Φ,{Φ}}}2/3/202357例2

证明各式彼此等值。PQ(P∨Q)∧(P∨Q)c)A∪B=B,A∩B=A,AB,~B~A.证明.A∪B=B

x(x∈A∪Bx∈B)x((xA∪Bx∈B)(x∈A∪BxB))x(((xAxB)x∈B)((x∈Ax∈B)xB))x((xAxB)x∈B)x((xAx∈B)(xBx∈B))x((xAx∈B)x(x∈Ax∈B)ABx(x∈Ax∈B)x(xBxA)x(x∈~Bx∈~A)~B~A

由A∪B=B得A(A∪B)=AB又A(A∪B)=A，所以

A=AB类似由A∩B=A,可以推出A∪B=B

所以A∪B=BA∩B=A从而证得A∪B=B,A∩B=A,AB,~B~A彼此等值。12/3/202358例3

令全集E为信息学院的学生的集合,C表示计算机专业学生的集合,M表示学习了离散数学的学生的集合,D表示学习了数据结构课学生的集合,F表示一年级的学生的集合.用集合的关系式表达下面句子.“学习了离散数学和数据结构课的学生,一定是计算机专业的非一年级的学生”.

解.(M∩D)(C∩~F)2/3/202359上海交大99年考研（6分）某年级共有200名学生，喜欢打篮球的有134人，喜欢打排球的有101人，喜欢打乒乓球的有90人，篮球、乒乓球都不喜欢的23人，篮球、排球都喜欢的54人，喜欢排球但不喜欢乒乓球的有48人，三样都喜欢的有12人。求：1。三样运动都不喜欢的有多少人？2。只喜欢一项运动的人有多少？2/3/202360解：设某年级学生集合为全集E，喜欢打篮球的学生集合为A，喜欢打排球的学生集合为B，喜欢打乒乓球的学生集合为C。则有：|E|=200|A|=134|B|=101|C|=90|A∩B|=54|~A∩~C|23|B∩~C|=48|A∩B∩C|=12|A∩C|=-|A∪C|+|A|+|C|=|A|+|C|-(|E|-|~(A∪C)|)=134+90-(200-23)=47|B∩C|=|B|-|B∩~C|=101-48=53所以，1.|~(A∪B∪C)|=|E|-(|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+|A∩B∩C|)=200-(134+101+90-54-53-47+12)=172/3/2023612只喜欢一种运动的人数分别为：|A∩~B∩~C|，|~A∩B∩~C|，|~A∩~B∩C||A∩~B∩~C|=|(A-A∩B)∩~C|=|(A-A∩B)|-|(A-A∩B)∩C|=80-(|(A∩C|-|B∩C|)=80-(47-53)=88|~A∩B∩~C|=|(B-A∩B)∩~C|=|(B-A∩B)|-|(B-A∩B)∩C|=47-(|(B∩C|-|A∩C|)=47-(53-47)=39|~A∩~B∩C|=|(C-C∩B)∩~A|=|(C-C∩B)|-|(C-C∩B)∩A|=37-(|(C∩A|-|B∩A|)=80-(47-54)=87所以，2.只喜欢篮球的有88人，只喜欢排球的有39人，只喜欢乒乓球的有87人。2/3/202362

六、（5分）证明：P(A)∪P(B)P(A∪B)并说明等号成立的条件。证明：因为P(A)表示由A的所有子集构成的集合.

P(A)={X|XA}

，P(B)={X|XB}

P(A)∪P(B)={X|XA}P(A∪B)={X|XA∪B}X∈P(A)∪P(B)

X∈P(A)∨X∈P(B)XA∨XB任取x∈X，则有x∈A∨x∈B，所以x∈A∪B，所以有XA∪B，即X∈P(A∪B)，因此P(A)∪P(B)P(A∪B)。但是，不一定有P(A∪B)P(A)∪P(B)（因为XA∪B不一定有XA∨XB）2/3/202363如：A={1,2}B={2,3}A∪B={1,2,3}P(A)={Φ,{1},{2},{1,2}}P(B)={Φ,{2},{3},{3,2}}P(A∪B)={Φ,{1},{2},{3},{1,2},{2,3}{3,1},{1,2,3}}{1,2,3}∈P(A∪B),但是{1,2,3}不是P(A)∪P(B)中的元素。当XA∪BXA∨XB时，等号成立。即A∪B=A，或

A∪B=B。2/3/202364有14位学生参加考试,9位同学数学得了优;5位同学物理得了优;4位同学化学得了优;其中物理和数学都得优的同学有4人;数学和化学都得优的同学有3人;物理和化学都得优的同学有3人;三门都得优的同学有2人;问没有得到优的有多少人?恰有两门得优的同学有多少人?解.令A、B、C分别表示数学、物理、化学得优同学集合.全集为E.于是有|E|=14|A|=9|B|=5|C|=4|A∩B|=4|A∩C|=3|B∩C|=3|A∩B∩C|=2|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+|A∩B∩C|=9+5+4-4-3-3+2=10于是得到优的人数是10人.∴没有得到优的人数是:14-10=4人恰有两门得优的人数:(|A∩B|-|A∩B∩C|)+(|A∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=4-2+3-2+3-2=42/3/202365中山大学2004五、设A、B、C、D为集合，证明下列各式。（20分）1.A-B=A-A∩B2.A((B∪C)∩D)=((AB)∪(AC))∩(AD)证明：1.因为A-B=A∩~BA-A∩B=A∩~(A∩B)=A∩(~A∪~B)=(A∩~A)∪(A∩~B)=A∩~B所以A-B=A-A∩B。2.任取<x,y>A((B∪C)∩D)

xAy((B∪C)∩D

xA(yB∪C)yDxA(yB∨yC)yD(xAyB)∨(xAyC)(xAyD)<x,y>((AB)∪(AC))∩(AD)所以A((B∪C)∩D)=((AB)∪(AC))∩(AD)2/3/202366考研题分析：1、若A-B=B,问A和B是什么集合？说明理由。解答：A和B必为空集。这是因为：A-B=A∩~B~B,而已知A-B=B，故有B~B，B中一定不包含任何元素。否则若存在x∈B，x∈~B同时成立，这是不可能的。由B是空集可知A也是空集。2/3/202367求证：若(A-B)∪(B-A)=C,则A(B-C)∪(C-B)的充要条件是A∩B∩C=Φ.证明：(充分性)：即已知A∩B∩C=Φ，证明A(B-C)∪(C-B)。B∪C=B∪(A-B)∪(B-A)=B∪(A∩~B)∪(~

A∩B)=B∪A∪(~

A∩B)=B∪A。故AB∪C。而A∩B∩C=Φ，因此对于任意的x∈A，有x∈B∪C∧xB∩C，即x∈(B∪C)-(B∩C).又(B-C)∪(C-B)=(B∩~C)∪(~B∩C)=(B∪C)-(B∩C),所以x∈(B-C)∪(C-B)，即A(B-C)∪(C-B)2/3/202368(必要性)：即已知A(B-C)∪(C-B)，证明A∩B∩C=Φ。因为A(B-C)∪(C-B)，所以A(B∪C)-(B∩C)，所以对于任意的x∈A，有x∈B∪C∧xB∩C，因此A∩B∩C=Φ。证毕。2/3/202369

第四章二元关系1.关系的概念,表示方法.2.二元关系的性质的定义,熟练掌握性质的判断及证明.3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质)4.掌握等价关系的判断,证明,求等价类和商集.5.掌握相容关系的概念

6.偏序关系的判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.

注意本章证明题的证明过程的思路2/3/202370一.关系的概念,表示方法,三个特殊关系.1.集合的笛卡尔积

A×B={<x,y>|x∈A∧y∈B}|A|=m,|B|=n|A×B|=mn

设A={0,1}，B={a,b}，求AB。

AB={<0,a>,<0,b>,<1,a>,<1,b>}2.二元关系的概念定义1:设A、Ｂ是集合,如果ＲA×B,则称R是一个从A到

B的二元关系。如果RA×A,则称R是A上的二元关系.

如果|A|=m|B|=n则可以确定2mn个从A到B的不同关系.定义2:任何序偶的集合，都称之为一个二元关系。2/3/2023713.关系的表示方法1).枚举法:

即将关系中所有序偶一一列举出，写在大括号内.

如:R={<1,2>,<3,4>,<4,2>}2).(描述法)谓词公式法：即用谓词公式描述序偶中元素的关系。例如

R={<x,y>|x<y}3).有向图法：1。2。

3。

4。。。。ABabcR1:1。。4。。23R2:2/3/2023724).矩阵表示法：(实际上就是图论中的邻接矩阵)

设A={a1,a2,,am}，B={b1,b2,,bn}是个有限集，

RA×B，定义R的m×n阶矩阵

MR=(rij)m×n，其中4.三个特殊关系1).空关系Φ：

ΦA×B，(或ΦA×A)，即无任何元素的关系.

它的关系图中只有结点,无任何边；它的矩阵中全是0。2).完全关系(全域关系)

：

A×B(或A×A)本身是一个从A到B(或A上)的完全关系.

即含有全部序偶的关系。它的矩阵中全是1。

1若<ai,bj>∈R

0若<ai,bj>∈R(1≤i≤m,1≤j≤n)rij=2/3/2023733).恒等关系IA：

IAA×A,且IA={<x,x>|x∈A}称之为A上的恒等关系。例如A={1,2,3},则IA={<1,1>,<2,2>,<3,3>}A上的Φ、完全关系A×A及IA的关系图及矩阵如下：MIA=1000100013×31。2。。31。2。。31111111113×31。。2。30000000003×3MΦ=MA×A=ΦA×AIA2/3/202374二.关系的性质:

熟练掌握性质的判断及证明.1.自反性定义:设R是集合A中的关系，如果对于任意x∈A都有

<x,x>∈R(xRx)，则称R是A中自反关系。即

R是A中自反的x(xAxRx)2.反自反性定义：设R是集合A中的关系，如果对于任意的x∈A都有

<x,x>R，则称R为A中的反自反关系。即

R是A中反自反的x(xA<x,x>R)3.对称性定义:R是集合A中关系,若对任何x,y∈A,如果有xRy,必有

yRx,则称R为A中的对称关系。

R是A上对称的xy((xAyAxRy)yRx)2/3/2023754.反对称性定义:设R为集合A中关系,若对任何x,y∈A,如果有xRy,和

yRx,就有x=y,则称R为A中反对称关系。R是A上反对称的xy((xAyAxRyyRx)

x=y)xy((xAyAxy<x,y>∈R)<y,x>R)5.传递性定义:R是A中关系，对任何x,y,z∈A,如果有xRy,和yRz,就

有xRz,则称R为A中传递关系。即R在A上传递xyz((xAyAzAxRyyRz)xRz)2/3/202376自反性反自反性对称性传递性反对称性每个结点都有环主对角线全是1每个结点都无环主对角线全是0不同结点间如果有边,则有方向相反的两条边.是以对角线为对称的矩阵不同结点间,最多有一条边.以主对角线为对称的位置不会同时为1如果有边<a,b>,<b,c>,则也有边<a,c>.或者使得前件为假.如果aij=1,且ajk=1,则aik=1从关系的矩阵从关系的有向图

性质判定:2/3/202377判断下面关系的性质：Y-有N-无1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4自反性反自反性对称性反对称性传递性R1YNNYYR2NYNYNR3YNYNYR4YNYYY2/3/202378R5NYNYYR6