离散数学单元1

1、1离数数学主讲者:吝维军、赵俊2绪言一、离散数学研究离散量的结构和相互间的关系整数: .,-3,-2,-1,0,1,2,3,.序群现实问题能否从河的两岸或两个小岛中的任何一处出发,经过每座桥一次且仅仅一次,再返回到出发点?从任一点出发,经过每条边一次且仅次,回到起点?二、离散数学是现代数学的一个分支（形成于70年代）数理逻辑、集合论、代数系统、图论三、离散数学与计算机科学的关系离散数学是计算机科学与技术的理论基础，是计算机科学与技术的核心骨干课程它给数据结构、编译系统、操作系统、数据库原理、人工智能提供必要的数学基础。形式化、符号化的方法，培养和提高了学生的抽象思维能力、逻辑推理能力。DACB

2、3绪言四、离散数学学习要点描述问题的方式：公式(符号)和图公式：用符号描述对象或对象间的关联或概念特点：严密、抽象、一般图：用点和线描述对象或对象间的关联或概念特点：直观、具体重要性有趣性五、参考书目离散数学，王遇科，北京理工大学离散数学，李盘林等，高等教育出版社离散数学及其在计算机中的应用，徐洁磐，人民邮电出版社4第一篇 数理逻辑一、逻辑学研究人的思维形式和规律的科学形式逻辑_代表人：Hilbert辩证逻辑_代表人物：罗素数理逻辑二、数理逻辑形成于17世纪中叶代表人物：莱布尼兹、布尔、哥德尔、德.摩根研究推理：用数学方法（形式化、公理化）研究前提和结论之间的形式关系。特别是数学中的推理的科学

3、。各门学科中都要进行推理，从具体的前提出发，得出具体的结论。例（1）函数f(x)在闭区间a,b上连续（2）f(a).f(b)0（3）存在c(a,b)使f(c)=0.又如：（1）a=0或a0（2）a不等于0（3）a0数理逻辑研究的推理的特点：不注重内容，注重形式关系 (1）A B（2）A（3）B5三、数理逻辑的内容集合论模型论递归论证明论共同的逻辑基础：逻辑演算（命题逻辑和谓词逻辑） 也是本课程学习的内容四、学习的要点掌握使用符号形式地刻划概念、推理和思维的基本思想和方法掌握形式的描绘和直观念义之间的关系形意相通6第一章 命题逻辑 1-1 命题及其表示数理逻辑研究的中心问题是推理推理的前题和结论

4、都是表达判断的陈述句。表达判断的陈述句构成了推理的基本单位称能判断真假的陈述句为命题 注：真值，命题的值判断为正确的命题的真值为真，用T表示判断为错误的命题的真值为假，用F表示7例1:判断下列句子哪些是命题？ 请止步! 你听懂了吗？ 我是学生 不是自然数 张校长的头发有一万根 我所说的是假的 如果天气好，那么我去散步 哥德巴赫猜想是正确的 不是命题 不是命题 是命题 是命题，假命题 是命题 不是命题，是悖论 是命题 是命题8几个概念 命题的种类原子命题（简单命题）、复合命题 命题的表示大写英文字母：A、B、C、P、Q、带下标的大写英文字母： P1、Q1、数字加方括号：1、2、 命题标识符：表示

5、命题的符号 命题常量：T、F 命题变元、原子变元91-2 联结词否定联结词 P读作:非P的真值为T当且仅当P为F合取联结词 PQ读作:与、P合取Q PQ为T当且仅当P和Q均为T析取联结词PQ读作: P或Q、要么P要么QPQ为F当且仅当P和Q均为F条件联结词（蕴涵联结词） PQ读作:如果P那么QPQ为F当且仅当P为T，Q为F双条件联结词（等值联结词） PQ读作: P当且仅当QPQ为T当且仅当P和Q的真值相同联结词是逻辑联结词或命题联结词的抽象是自然语言中连词的抽象10五种联结词的定义PPTFFTPQPQTTTFFTFFTFFFPQPQTTTFFTFFTTTFPQPQTTTFFTFFTFTTPQP

6、 QTTTFFTFFTFFT11注 析取联结词是“或”的抽象可兼或：a.b=0即a=0或b=0或a=b=0 (至少有一发生)排斥或：他的死或重于泰山或轻于鸿毛表示近似的或:去文昌楼需6分钟或8分钟 条件联结词PQ,P称为前件,Q称为后件当前件为F时,PQ为T 复合命题的真值只取决于构成它们的各原子命题的真值，而与其内容、含义无关 联结词有操作或运算的含义可看作一元运算符、二元运算符，12例2：将下列命题符号化(1)他既聪明又用功。(2)他虽聪明但不用功。(3)如果2+2=4,太阳将从东方升起(4)除非你努力，否则你将失败。(5)除非天气好，我才骑自行车上班。(6)张明正在睡觉或游泳。(7)A中

7、没元素，A就是空集。解：(1) P：他聪明。 Q：他用功。则(1)可表示为：PQ(2)可表示为：PQ(3) P： 2+2=4。 Q：太阳将从东方升起。(3)可表示为: PQ(4) P:你努力. Q:你将失败.则(4)可表示为：PQ(5) P:我骑自行车上班。Q:天气好。则(5)可表示为PQ或QP(6) P:张明在睡觉.Q:张明在游泳.则(6)可表示为(PQ)(PQ)(7) P: A中没元素.Q: A是空集.则(7)可表示为：PQ131-3命题公式与翻译 定义1-3.1命题演算的合式公式（wff）:(1)单个命题变元是合式公式.(2)如果A是合式公式,则(A)是合式公式.(3)如果A和B是合式公

8、式,则(AB),(AB),(AB),(AB)是合式公式.(4)有限次地使用(1),(2),(3)所得到的结果是合式公式. 注:(1) 定义是以递归形式给出的(2) 合式公式有无穷多个(3) 合式公式没有真值,只有对其命题变元指派真值后,方有真值.14 约定:(1) 公式最外层的括号可省略(2) 联结词运算的优先次序:, (3) 结合性 右结合 , 左结合15命题翻译 文字叙述的命题 由命题标识符,联结词,括号所组成的合式公式. 步骤:(1)分析出各原子命题,并用符号表示(2)使用合适的联结词,将原子命题联结起来,并加适当的括号,来组成复合命题的符号化表示.16例3: 将下列命题符号化(1)如果

9、我上街,我就去书店看看,除非我很累.P:我上街. Q: 我去书店. R:我很累.(1)可符号化为: R (PQ)(2)王一乐是数学系的学生,他生于1968年或1969年,他是三好学生.P:王一乐是数学系的学生.Q:他生于1968年.R:他生于1969年.S:他是三好学生.(2)可符号化为: P(QR)S171-4,5 真值表 等价公式 重言式 蕴涵公式 1.真值表 定义1-4.1 在命题公式中,对于分量指派真值的各种可能组合,就确定了这个命题公式的各种真值情况,把它汇成表,就是命题公式的真值表.18例4:给出下列公式的真值表 (1) (PQ)PPQPQTTTFFTFFTFFF(PQ)PFFFF

10、PQPQTTTFFTFFTFFFFFFTPQ (2)TFFT (2) (PQ)(PQ)解: (1)的真值表如下:解: (2)的真值表如下:19 (3) (PQ) (PQ)PQ(PQ)TTTFFTFFFTTTFTTTPQ (PQ) (PQ)TTTT注:10:有一类公式无论命题变元作何种指派,其真值为永真(永假)20:含n个命题变元的命题公式，其真值表有2n行202.重言式矛盾式 定义1-5.1 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为T,则称该命题公式为重言式或永真公式. 定义1-5.2 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为F,则称该命题公式为矛盾式或永假

11、公式. 定理1-5.1 任何两个重言式的合取或析取,仍是重言式.213. 等价公式 定义1-4.2 设A和B是两个命题公式,若AB是重言式,则称A和B是等价的或逻辑相等.记作AB. 例5 证明: (1) PQPQ(2) PQ (PQ)(QP) 注:AB 即对A和B的任一真值指派,有A和B的真值相同.在逻辑相等意义下,含n 个原子变元的公式的个数为与的区别是逻辑符号是语义符号基本特性AA若AB则BA若AB且BC则ACn2222对合律1幂等律2结合律 3交换律 4分配律5吸收律6德.摩根律7同一律8零律9否定律10P PPP P, PP P(PQ)R P(QR)(PQ)R P(QR) PQ QP,

12、 PQ QPP(QR) (PQ)(PR)P(QR) (PQ)(PR) P(PQ) PF PT PP T, PP F常用的命题定律)()(),()(QPQPQPQPP(PQ) PPPP PT F TPF 234.蕴涵公式(逻辑蕴涵) 定义1-5.3 设A,B是公式,若AB是重言式,则称A蕴涵B,记作AB. 定理 1-5.4 设A,B是命题公式.AB的充要条件是AB且BA. 证明:利用A B (AB)(BA)来证.24注: 与的区别. 几个类似的公式PQ, QP, PQ, QP称为 逆换式 反换式 逆反式有PQQP PQ的证明方法真值表假设前件真,推出后件真假设后件假,推出前件假 的特性若AB且A

13、为重言式,则B为重言式.AB,BC则ACAB,AC则ABCAB,CB则ACB251,234567891011121314PQP, PQQPPQPPQQPQ(PQ) P(PQ) QP(PQ) Q(PQ) P(PQ) (PQ)(QR) (PQ)(PR)(QR) (PQ)(RS) (PR)(QS)(P Q)(Q R) (P R)常用的蕴涵式QPQ (PR)R26例5 推证Q(PQ) P 证明:法一:设Q(PQ)为T,则Q为T从而Q为F由(PQ)为T及Q为F可知P为F故P为T.法二:设P为F,则P为T.若Q为F,则(PQ)为F 从而Q(PQ)为F.若Q为T,则Q为F, 从而Q(PQ)为F.综上有Q(P

14、Q) P法三:列真值表275.替换规则 代入规则 替换(置换)规则定义1-4.3 若X是合式公式A的一部分且为合式公式,则称X为A的子公式.定理1-4.1 设X是合式公式A的子公式,Y是一公式.若XY,如果将A中的X用Y来置换所得公式B,则A B. 注满足定理1-4.1的置换称为等价转换或等价代换.替换规则又提供了一种证明公式等价的方法.28例7 证明: Q(P(PQ) QP证明: 因为P(PQ) P, (吸收律)故有 Q(P(PQ) QP (替换规则)例8 证明: (PQ)(PQ) P证明: (PQ)(PQ) P(QQ) (分配律) PT (否定律,替换规则) P (同一律)29例9 证明

15、P(QR) Q(PR) R(QP)证明: P(QR)P(QR) P(QR) Q(PR) Q(PR) Q(PR) 核心: PQ PQR(QP) R(QP) R(QP) P(QR) P(QR)30例10 证明 (PQ) (P(QR)(PQ)(PR) T证明: (PQ) (P(QR)(PQ)(PR) (PQ)(P(QR)(PQ)(PR) (德.摩根律) (PQ)(PQ)(PR)(PQ)(PR) (分配律) (PQ)(PR)(PQ)(PR) (结合律, 幂等律) (PQ)(PR) (PQ) (PR) (德.摩根律)(PQ)(PR) (PQ)(PR) (德.摩根律) T (否定律)31代入规则 定理1-

16、5.2(代入规则) 一个重言式,对同一分量全部用同一合式公式代换所得结果为重言式. 注:全部代又提供了判定重言式的方法 例:已知PP为重言式,则有下列重言式:(PQ)(PQ)(PQR)(PQR)AA321-6 其它联结词 QP )(QPQP联结词 符号 复合命题 含义不可兼析取条件否定与非,合非或非,谢孚竖)(QPQPQP)(QPQPQP)(QPQPQP33与非的特性合非的特性PPPPP)(1)QPQPQPQP)()()(2)QPQPQPQQPP)()()(3)PPPPP)(1)QPQPQPQP)()()(2)QPQPQPQQPP)()()(3)(QPQP)(QPQP342.最小联结词组(联结

17、词的完全集)P QT T T F T T F F T F TF T FT F T FT F T F T F F T F T TF F TF T T FF T T F F T T F F T TF T FF T F TF F T F F F T T F T FT T FT F T FT F P Q P Q 问:在逻辑相等意义下,两个命题变元P和Q可构成的不同的命题公式有多少个?由T,F,P,Q及9个命题联结词可以表示16个命题公式. 但有几个就够了?35可由前5个表示 (1)()(PQQPQP(2)QPQP(3)(),(QPQPQPQP(4)结论: , ,是最小联结词组 ,也是最小联结词组(1)

18、 ,V均不是最小联结词组361-7对偶和范式 1.对偶 定义1-7.1 在给定的仅用联结词,和的命题公式A中,若把和互换,F和T互换,所得公式A*称为A的对偶式. 例1:写出下列公式的对偶式.(1) (PQ)R(2) (PQ)T(3) (PQ)(P (QS) 例2:求PQ,PQ的对偶式.PQ的对偶式为PQ PQ的对偶式为PQ37 定理1-7.1 若A和A*是对偶式,P1,P2,Pn是出现在A和A*中的原子变元, 则A(P1,P2,Pn) A*(P1, P2, Pn)A(P1, P2, Pn) A*(P1,P2,Pn) 注:德.摩根律的推广(P1P2Pn) P1P2Pn设A1,A2,An是任意命

19、题变元,则(A1A2An) A1A2An 例3. 设A*(S,W,R)是S(WR),验证: A*(S, W, R) A(S,W,R) 例4. 如果A(P,Q,R)是P(Q(RP),求它的对偶式A*(P,Q,R),分别求与A及A*等价,但仅包含联结词,和的公式.38 定理1-7.2 设P1,P2,Pn是出现在公式A和B中的所有原子变元,如果AB,则A*B*. 证明:由于AB,则A(P1,P2,Pn) B(P1,P2,Pn)是重言式,故A(P1, P2, Pn) B(P1, P2, Pn)是重言式.即A(P1, P2, Pn) B(P1, P2, Pn)由定理1-7.1A(P1, P2, Pn)

20、A*(P1,P2,Pn)B(P1, P2, Pn) B*(P1,P2,Pn)故A*B*392.范式-公式的标准型(1)析取范式,合取范式 定义 1-7.2 一个命题公式称为合取范式,当且仅当它具有型式: A1A2An (n1)其中A1，A2，An都是由命题变元或其否定所组成的析取式 定义 1-7.3 一个命题公式称为析取范式,当且仅当它具有型式: A1A2An (n1)其中A1，A2，An都是由命题变元或其否定所组成的合取式40例5. 求(P(QR)S的合取范式.解: (P(QR)S(P(QR)S(P(QR)SP (Q R)S(PS)(QR)(PSQ)(PSR)41例6.求(PQ) (PQ)的

21、析取范式.解: (PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) P)(PQ)Q)(PP)(QP)(PQ)(QQ)(QP)(PQ)42(2) 主析取范式 定义1-7.4n个命题变元的合取式,称作布尔合取式或小项,其中每个变元与它的否定出现且仅出现一个. 注:三个命题变元P,Q,R其小项:PQR, PQR, PQR, PQR,PQR, PQR, PQR, PQRn个命题变元的小项共有2n个一小项仅对应一组真值指派使其真值为真.任两个小项均不等价,且其合取为假.全体小项的析取永为真.43小项的编

22、码表示 命题变元P,Q,R的小项m000= PQR, m001= PQRm010 = PQR, m011 =PQR m100 = PQR, m101 = PQR m110 = PQR, m111 = PQR, 记真值T和F分别为1和0,小项的真值指派与编码相同时,真值为. 小项也可记为:m0, m1, m2, m3, m4, m5, m6, m7.44主析取范式 定义1-7.5对于给定的命题公式，如果有一个等价公式，它仅有小项的析取所组成，则该等价式称作原式的主析取范式 例6.求(PQ)的主析取范式.解:列出其真值表:(PQ)(PQ)(PQ) (PQ)P Q (PQ)T TFT FTF TTF

23、 FT 定理1-7.5 (主析取范式的求法) 在真值表中,公式的真值为T的指派所对应的小项的析取即为此公式的主析取范式.45例8. 求(PQ)(PR)(QR)的主析取范式.解:首先列出其真值表:P QRTTTTTFTFTTFFFTTFTFFFTFFF(PQ)(PR)(QR)TTFFTFTF真值为T所对应的小项为:PQRPQRPQRPQR故原公式的主析取范式为:(PQR)(PQR)(PQR)(PQR)46法二:(PQ)(PR)(QR)(PQ)(RR)(PR)(QQ)(QR)(PP)(PQR)(PQR)(PRQ) (PRQ)(QRP)(QRP)(PQR)(PQR)(PQR)(PQR)47(3) 主

24、合取范式 定义1-7.6 n个命题变元的析取式,称作布尔析取式或大项,其中每个变元与它的否定出现且仅出现一个. 注:n个命题变元的大项共有2n个三个命题变元P,Q,R其大项:M000=PQR, M001=PQR, M010=PQR, M011=PQR,M100=PQR, M101=PQR, M110=PQR, M111=PQR一大项仅对应一组真值指派使其真值为假.任两个大项均不等价,且其析取为真.全体大项的合取永为假.48主合取范式 定义1-7.7 对于给定的命题公式，如果有一个等价公式，它仅有大项的合取所组成，则该等价式称作原式的主合取范式 定理1-7.4 (主合取范式的求法)在真值表中,公

25、式的真值为F的指派所对应的大项的合取即为此公式的主合取范式.49例10. 求(PQ)(PR)的主合取范式与主析取范式.解:首先列出其真值表:PQRTTTTTFTFTTFFFTTFTFFFTFFF(PQ)(PR)TTFFTFTF真值为F所对应的大项为:PQRPQRPQRPQR故原公式的主合取范式为:(PQR)(PQR)(PQR)(PQR)同理,原公式的主析取范式为(PQR)(PQR)(PQR)(PQR)50例10:化(PQ)(PR)为主合取范式.解: (PQ)(PR)(PQ)P)(PQ)R)(PP)(QP)(PR)(QR)(QP)(PR)(QR)(QP)(R R)(PR)(Q Q) (QR)(P

26、 P)(QPR)(QPR)(PRQ) (PRQ)(QRP)(QRP)(QPR)(QPR)(PRQ)(PRQ)51(4)主析(合)取范式的简洁表达 表示小项的析取, i,j,k表示mimjmk 表示大项的合取, i,j,k表示ijk 例10可表示为(PQ)(PR) (PQR)(PQR)(PQR)(PQR) m111m110m011 m0011,3,6,7(PQ)(PR) (PQR)(PQR)(PQR)(PQR) M101M100M010 M000 0,2,4,5 命题公式A主析取范式为i1,i2,ik 命题公式A主合取范式为 1,2, i1-1, i1+1,i2-1, i2+1, ik-1, i

27、k+1,2n-1521-8 推理理论 定义1-8.1设A和C是两个命题公式,若AC,称C是A的有效结论.或称C可由A逻辑地推出.称C是一组前提H1,H2,Hn的有效结论,当且仅当H1H2HnC记作: H1,H2,Hn C 判别有效结论的过程就是论证过程 常用的论证方法：真值表法,真接证法, 间接证法. (1)真值表法53例1.一份统计表格的错误或者是由于材料不可靠,或者是由于计算有错误;这份统计表格的错误不是由于材料不可靠,所以这份统计表格是由于计算有错误.解: 设各命题变元为P:统计表格的错误是由于材料不可靠.Q:统计表格的错误是由于计算有错误.本例可译为:Q是前提PQ, P的有效结论,即P

28、(PQ) Q.为此列出真值表如下:PQPQ PTTTFTFTFFTTTFFFT由真值表可看到,仅在第三行,前提PQ, P均为真,而此时结论Q为T.故P(PQ) Q成立54例2. 如果张老师来了,这个问题可以得到解答,如果李老师来了,这个问题也可以得到解答,总之张老师或李老师来了,这个问题就可以得到解答.解: 若设 P:张老师来了.Q:李老师来了.R:这个问题可以得到解答.上述语句可译成下述命题关系式:(PR)(QR)(PQ) R通过真值表可验证上述关系式成立.55(2)直接证法 直接证法就是由一组前提,利用一些公认的推理规则,根据已知的等价或蕴涵重言式,推演得到有效的结论. 推理规则P规则(也

29、称前提引入规则)在推导过程中,前提可视需要引入使用T规则(也称结论引入规则)在推导过程中,前面导出的有效结论都可作为后继推导的前提引入CP规则(也称条件证明引入规则)若推出的有效结论为条件式RC,只需将前件R加入到前提中作为附加前提,再推出后件C即可.事实上,若H1H2HnRC则H1H2HnRC 常用的蕴涵式和等价式 P4356例1. 证明(PQ)(PR)(QS) SR 证明:(1) PQ P(2) PQ T(1) E(3) QS P(4) PS T(2)(3), I(5) PR P(6) SP T(4),E(7) SR T(6) (5) E(8) SR T(7) E 证明(二)(1) PR P(2) PQRQ T(1),I(3) QS P(4) QRSR T(3),I(5) PQSR T(2)(4),I (6) PQ P(7) SR T(5)(6), I57例2.WRV,VCS,SU,CUW证明:CU PC T(1),I U T(1),ISU PUS T(4), IS T(3)(5)