离散数学(第39讲总复习一)

1、冯伟森冯伟森Email：2022年年5月月10日星期二日星期二2022-5-102022-5-10计算机学院计算机学院2 22022-5-102022-5-10计算机学院计算机学院3 3第一章第一章一、基本概念一、基本概念 命题、命题常元、命题变元、命题的解释或命题、命题常元、命题变元、命题的解释或赋值、赋值、原子命题原子命题( (简单命题简单命题) )、复合命题、否定、复合命题、否定联结词、合取、析取、可兼或、不可兼或、条联结词、合取、析取、可兼或、不可兼或、条件、双条件件、双条件、常值命题、命题变量、命题公式、常值命题、命题变量、命题公式、命题公式的解释、真值表、永真公式命题公式的解释、真

2、值表、永真公式( (重言式重言式) )、永假公式永假公式( (矛盾式，不可满足公式矛盾式，不可满足公式) )、可满足公、可满足公式、公式的等价、对偶（公）式、对偶原理、式、公式的等价、对偶（公）式、对偶原理、子句、短语、子句、短语、析取范式、合取范式、主析取析取范式、合取范式、主析取（主合取）范式、极小项、极大项（主合取）范式、极小项、极大项2022-5-102022-5-10计算机学院计算机学院4 4二、基本要求二、基本要求1 1、深刻理解五种常用联结词的涵义，并能准确、深刻理解五种常用联结词的涵义，并能准确地应用它们地应用它们将基本命题及复合命题符号化将基本命题及复合命题符号化。2 2、熟

3、练地写出给定命题公式的真值表熟练地写出给定命题公式的真值表3 3、牢记基本等价式的名称及它们的内容；、牢记基本等价式的名称及它们的内容；4 4、熟练地应用基本等价式及置换规则进行等价、熟练地应用基本等价式及置换规则进行等价 演算演算5 5、熟练掌握求主析取（主合取）范式的方法熟练掌握求主析取（主合取）范式的方法2022-5-102022-5-10计算机学院计算机学院5 56 6、理解并牢记、理解并牢记9 9类基本蕴涵关系式和蕴涵的基本类基本蕴涵关系式和蕴涵的基本性质性质7 7、牢记各条推理规则的内容及名称、牢记各条推理规则的内容及名称8 8、熟练掌握推理的各种方法（直接法、利用熟练掌握推理的各

4、种方法（直接法、利用CPCP规则、反证法）规则、反证法）2022-5-102022-5-10计算机学院计算机学院6 6第二章第二章一、基本概念一、基本概念 全总个体域（全论域）、全称量词、存在量词、全总个体域（全论域）、全称量词、存在量词、特性谓词、指导（作用）变元、辖域（作用域）、约特性谓词、指导（作用）变元、辖域（作用域）、约束变元、自由变元、约束变元的改名规则、自由变元束变元、自由变元、约束变元的改名规则、自由变元的代入规则、常量符号、变量符号、函数符号、谓词的代入规则、常量符号、变量符号、函数符号、谓词符号、谓词公式、公式的解释、永真公式符号、谓词公式、公式的解释、永真公式( (重言式

5、重言式) ) 、永假公式永假公式( (矛盾式，不可满足公式）、可满足公式、矛盾式，不可满足公式）、可满足公式、前束范式、母式、前束合取前束范式、母式、前束合取( (或析取或析取) )范式、范式、SkolemSkolem范范式、式、US(US(全称指定规则全称指定规则) )、ES(ES(存在指定规则存在指定规则) )、UG(UG(全全称推广规则称推广规则) )、EG(EG(存在推广规则存在推广规则) )2022-5-102022-5-10计算机学院计算机学院7 7二、基本要求二、基本要求 能准确地将给定命题符号化能准确地将给定命题符号化 深刻理解全称量词、存在量词及量词的辖域、深刻理解全称量词、

6、存在量词及量词的辖域、全总个体域的概念全总个体域的概念 能准确理解约束变元能准确理解约束变元( (量量) )和自由变元的概念和自由变元的概念 掌握约束变元的改名规则和自由变元的代入掌握约束变元的改名规则和自由变元的代入规则规则 能熟练地运用能熟练地运用USUS、ESES、UGUG、EGEG规则进行推理规则进行推理2022-5-102022-5-10计算机学院计算机学院8 8第三、四、五章第三、四、五章一、基本概念一、基本概念 幂集、笛卡尔集、幂集、笛卡尔集、关系、关系、n n元关系、空关元关系、空关系、二元关系、全关系、关系矩阵；关系的交、系、二元关系、全关系、关系矩阵；关系的交、并、补、差、

7、复合、幂、逆；并、补、差、复合、幂、逆；自反闭包、对称自反闭包、对称闭包、传递闭包闭包、传递闭包；等价关系、以；等价关系、以m m为模的同余为模的同余关系、等价类、生成元、偏序关系、偏序集、关系、等价类、生成元、偏序关系、偏序集、偏序集的哈斯图、最大元偏序集的哈斯图、最大元 、最小元、最小元 、极大元、极大元、极小元、上界、下界、最小上界、最大下界、极小元、上界、下界、最小上界、最大下界、全序关系、良序关系、良序集全序关系、良序关系、良序集2022-5-102022-5-10计算机学院计算机学院9 9二、基本要求二、基本要求1 1、熟练掌握关系的性质和运算、熟练掌握关系的性质和运算2 2、熟练

8、运用、熟练运用WarshallWarshall算法计算关系的传递闭包算法计算关系的传递闭包3 3、熟练掌握偏序关系的哈斯图的画法以及由哈斯熟练掌握偏序关系的哈斯图的画法以及由哈斯图给出相应的偏序关系图给出相应的偏序关系4 4、熟练掌握求偏序集中子集的最大元熟练掌握求偏序集中子集的最大元 、最小元、最小元 、极大元、极小元、上界、下界、最小上界、最极大元、极小元、上界、下界、最小上界、最大下界的方法大下界的方法5 5、熟练掌握利用关系的性质和定义进行证明、熟练掌握利用关系的性质和定义进行证明2022-5-102022-5-10计算机学院计算机学院1010第六章第六章一、基本概念一、基本概念 复合

9、函数、复合函数、单射单射 、满射、双射、置、满射、双射、置 换、换、单位单位( (恒等恒等) )置换、循环、置换、循环、逆函数逆函数二、基本要求二、基本要求1 1、熟练掌握判断函数是否为单射、熟练掌握判断函数是否为单射 、满射、双射、满射、双射的方法的方法2 2、熟练掌握、熟练掌握置换的复合运算和置换表示成循环置换的复合运算和置换表示成循环的积的积的方法的方法2022-5-102022-5-10计算机学院计算机学院1111求求G G(PQ)R(PQ)R的主合取范式和主析取范式。的主合取范式和主析取范式。解解：（公式转换法）：（公式转换法）G G(PQ)R(PQ)R( (PQ)RPQ)R（蕴涵）

10、（蕴涵）( (PQ(RPQ(RR)R) (PP)(PP)(QQ)R)QQ)R)（添加（添加R R、P P、Q Q）( (PQR)(PQR)(PQPQR)R)( (PPQR)(QR)(PQR)PQR)(P(PQR)(PQR) QR)(PQR) （分配律）（分配律）(PQR)(P(PQR)(PQR)(QR)(PQR)PQR)( (PQPQR)(R)(PPQR)QR)（结合律）（结合律）主合取范式主合取范式例例1 12022-5-102022-5-10计算机学院计算机学院1212G G(PQ)R(PQ)R( (PQ)R PQ)R （蕴涵）（蕴涵）( (PR)(QR)PR)(QR)( (P(P(QQ)

11、R)QQ)R)(PP)QR)PP)QR)( (PPQR)(QR)(PQR)PQR)( (PQR)(PQR) PQR)(PQR) （分配律）（分配律）( (PPQR)(QR)(PQR)(PQR)PQR)(PQR)主析取范式主析取范式2022-5-102022-5-10计算机学院计算机学院1313真值表技术法真值表技术法 1)1)、求公式的主合取范式、求公式的主合取范式P Q RP Q R(PQ) R(PQ) R0 0 00 0 0 0 00 0 10 0 1 1 1 0 1 00 1 0 0 00 1 10 1 1 1 11 0 01 0 0 0 01 0 11 0 1 0 01 1 01 1

12、0 0 01 1 11 1 1 1 1极大项极大项极大项极大项极大项极大项极大项极大项P PPP极大项极大项P2022-5-102022-5-10计算机学院计算机学院1414 将极大项全部进行合取后，可得到相应的主将极大项全部进行合取后，可得到相应的主合取范式：合取范式： G=G=（）=(PQR)(P=(PQR)(PQR)(QR)(PQR)PQR)( (PQPQR)(R)(PPQR)QR)2022-5-102022-5-10计算机学院计算机学院1515 2)2)、求公式的主析取范式、求公式的主析取范式P Q RP Q R(PQ(PQ）R R0 0 00 0 0 0 00 0 10 0 1 1

13、1 0 1 00 1 0 0 00 1 10 1 1 1 11 0 01 0 0 0 01 0 11 0 1 0 01 1 01 1 0 0 01 1 11 1 1 1 1P 极小项极小项极小项极小项极小项极小项PP2022-5-102022-5-10计算机学院计算机学院1616 将极小项全部进行析取后，可得到相应的主析将极小项全部进行析取后，可得到相应的主析取范式：取范式： G=G=（） = =（PP）（PP）（）2022-5-102022-5-10计算机学院计算机学院1717例例2 2 求证求证SRSR是前提是前提PQPQ，PRPR，QSQS的有效结论。的有效结论。( (构构造性二难推论造

14、性二难推论) ) 证：步骤证：步骤 公式公式 依据（注释）依据（注释） PQ PPQ P PQ TPQ T，E E1212 QS P QS P PS T, PS T, , , ,I,I6 6 SP TSP T，E E1414，E E1 1 PR P PR P SR TSR T，I I6 6 SR T SR T，E E1212，E E1 1 故故 PQPQ，PRPR，QS QS SRSR2022-5-102022-5-10计算机学院计算机学院1818例例3(CP3(CP规则规则) ) 证明证明RSRS可以从前提可以从前提 PP（QSQS），），RPRP，QQ推出推出 证：证： R PR P（附加

15、前提）（附加前提） RP PRP P P T P T，I I5 5 P P（QSQS） P P QS T QS T，I I3 3 Q P Q P S T S T，I I3 3 RS CP RS CP，2022-5-102022-5-10计算机学院计算机学院1919 证明：证明：RRQ Q，RSRS，SSQ Q，PQPQP P 证：证： （ P P） P P（假设前提）（假设前提） P TP T，E E1919 PQ P PQ P Q Q T, T, , , ,I,I3 3 S SQ PQ P S TS T，I I4 4 RS P RS P R T R T，I I5 5 R RQ PQ P Q

16、Q T T，I I3 3 Q QQ FQ F， 10 R RQ Q，RSRS，SSQ Q，PQPQP P例例4(4(反证法反证法) )2022-5-102022-5-10计算机学院计算机学院2020 若若n n是偶数，并且是偶数，并且n n大于大于5 5，则，则m m是奇数。是奇数。只有只有n n是偶数，是偶数，m m才大于才大于6 6。n n是大于是大于5 5，所以，所以，若若m m大于大于6 6，则，则m m是奇数。是奇数。解：设解：设p p：n n是偶数，是偶数，q: nq: n大于大于5,5, r: m r: m是奇数是奇数, s: m, s: m大于大于6.6.前提前提: (p: (

17、pq) q) r,sr,sp,qp,q结论：结论：s sr r证明证明: q P q P s sq q 扩充法则扩充法则 （关键）（关键）例例5 52022-5-102022-5-10计算机学院计算机学院2121 sqsq 蕴涵式蕴涵式 spsp P P ( (spsp)()(sqsq) ) 合取合取 s(ps(pq q) ) 蕴涵式蕴涵式 (p(pq q)r P)r P sr sr 假言三段论假言三段论2022-5-102022-5-10计算机学院计算机学院2222例例6 6 所有的有理数都是实数；所有的无理数也是实数；虚所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既

18、不是有理数也不是无理数。数不是实数。因此，虚数既不是有理数也不是无理数。解：设解：设Q(x)Q(x)：x x是有理数；是有理数；R(x)R(x)：x x是实数；是实数； N(x)N(x)：x x是无是无理数；理数； C(x)C(x)：x x是虚数；是虚数； )()()()5()3()()()4()()()()3()1()()()2()()()()1()()()()()()()(),()()(),()()(xRxCxUS xRxNxRxNxUS xRxQxRxQxxNxQxCxxRxCxxRxNxxRxQx 2022-5-102022-5-10计算机学院计算机学院2323(11) )( (12)

19、(10)I (11)(8)(9) ) ()( (10) (9) 1088UGxNxQxCxTxNxQxCTxCxNxCxQITxCxNITxCxQETxCxRUSxRxC)()()()()()()()()()()7)(4()()()7)(2()()()8()6()()()7()5()()()6(33 2022-5-102022-5-10计算机学院计算机学院2424例例7 7 设设R R是集合是集合A A上的一个传递关系和自反关系，上的一个传递关系和自反关系，S S是是A A上的一个关系，使得对任意上的一个关系，使得对任意a,bAa,bA，SS当且仅当当且仅当RR且且RR，试证，试证明明S S是

20、是A A上的一个等价关系。上的一个等价关系。证明：证明：1 1）对任意对任意aAaA，因，因R R是自反的，所以是自反的，所以RR。由由RR并且并且RR，有，有SS，即，即S S是是自反的。自反的。2 2）对任意对任意a,bAa,bA，若，若SS，则由已知条件有，则由已知条件有RR并且并且RR，即有，即有RR并且并且RR，所以，所以，SS，即，即S S是对称的。是对称的。2022-5-102022-5-10计算机学院计算机学院25253 3）对任意对任意a,b,cAa,b,cA，若，若SS，SS，则由已知条件有：则由已知条件有：RR并且并且RR和和RR并且并且RR。所以，由。所以，由RR并并且

21、且RR，有，有RR；由；由RR并且并且RR，有，有RR；由：；由：RR并且并且RR，有，有SS，即，即S S是传递的。是传递的。 由由1),2),3)1),2),3)知，知，S S是是A A上的一个等价关系。上的一个等价关系。2022-5-102022-5-10计算机学院计算机学院2626例例8 8证明：证明：“” 若若R R是等价关系。是等价关系。1 1）显然显然R R是自反的。是自反的。2 2）对任意对任意a,b,cAa,b,cA，若，若R,RR,R，则由，则由R R是对称的，有是对称的，有RR并且并且RR，由，由R R是传递是传递的，所以，的，所以，RR。即。即R R是循环的关系。是循环

22、的关系。由由1)1)，2)2)知知R R是自反的和循环的。是自反的和循环的。 设设R R是集合是集合A A上的一个关系，对上的一个关系，对 a,b,cAa,b,cA，若若RR并且并且RR，则有：，则有：RR，则，则R R称为称为A A上的上的循环关系循环关系。试证明。试证明R R是是A A上的一个等价上的一个等价关系的充要条件是关系的充要条件是R R是循环关系和自反关系。是循环关系和自反关系。2022-5-102022-5-10计算机学院计算机学院2727“” 若若R R是自反的和循环的。是自反的和循环的。1 1）显然显然R R是是自反性自反性的；的；2 2）对任意对任意a,bA,a,bA,若

23、若R,R,则由则由R R是自反的是自反的, ,有有RR，因，因R R是循环的，所以，是循环的，所以，RR且且R R RR，即即R R是对称的。是对称的。3 3）对任意对任意a,b,cAa,b,cA，若，若RR，RR，则由则由R R对称的，有对称的，有RR并且并且RR；由；由R R是循环的，所以是循环的，所以RR且且RRRR，即，即R R是传递的。是传递的。由由1),2),3)1),2),3)知，知，R R是是A A上的一个等价关系。上的一个等价关系。2022-5-102022-5-10计算机学院计算机学院2828例例9 9设设A A22，3 3，4 4，B B11，2 2，4 4。考虑。考虑从

24、从A A到到B B的的“大于等于大于等于”关系关系R R和和“小于等于小于等于”关关系系S S：R R,，S S,。求出求出R R S S、 R R S S、 R-S R-S、 R R S S、 、S S-1-1。解：解： R R S= ,S= ,R R S= ,S= ,R2022-5-102022-5-10计算机学院计算机学院2929 R-S= ,R-S= , R R S = ,S = , = = , ,S S-1-1= ,= ,R2022-5-102022-5-10计算机学院计算机学院3030例例1010解：解：最大元：无；最小元：最大元：无；最小元：x x5 5； 设设A Axx1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,A A上定义偏序集上定义偏序集的哈斯图如下，求的哈斯图如下，求B Bxx3 3,x,x4 4,x,x5 5 的最大的最大( (小小) )元、极大元、极大( (小小) )元、上元、上( (下下) )界、最小上界、最界、最小上界、最大下界。大下界。极大元