离散数学 第三章的课件

1、1主要内容主要内容推理的形式结构推理的形式结构l 推理的正确与错误推理的正确与错误l 推理的形式结构推理的形式结构l 判断推理正确的方法判断推理正确的方法l 推理定律推理定律自然推理系统自然推理系统Pl 形式系统的定义与分类形式系统的定义与分类l 自然推理系统自然推理系统Pl 在在P中构造证明中构造证明:直接证明法、附加前提证明法、归谬法直接证明法、附加前提证明法、归谬法第三章第三章 命题逻辑的推理理论命题逻辑的推理理论23.1 推理的形式结构推理的形式结构定义定义3.1 设设A1, A2, , Ak, B为命题公式为命题公式. 若对于每组赋值，若对于每组赋值，或者或者A1 A2 Ak 为假，

2、或者当为假，或者当A1 A2 Ak为真时，为真时，B也为也为真，则称由真，则称由前提前提A1, A2, , Ak推出推出结论结论B的的推理推理是是有效的有效的或或正确的正确的, 并称并称B是是有效结论有效结论.几点说明：几点说明：1由前提由前提A1,A2,Ak推结论推结论B的推理是否正确与诸前提的排列次序的推理是否正确与诸前提的排列次序无关。无关。 2设设A1,A2,Ak，B中共出现中共出现n个命题变项，对于任何一组赋值前个命题变项，对于任何一组赋值前提和结论的取值情况有以下四种：提和结论的取值情况有以下四种： (1) A1A2 Ak为为0，B为为0. (2) A1A2 Ak为为0，B为为1.

3、 (3) A1A2 Ak为为1，B为为0. (4) A1A2 Ak为为1，B为为1. 3推理正确，并不能保证结论推理正确，并不能保证结论B一定为真，这与通常的推理是不同一定为真，这与通常的推理是不同3例例3.1 判断下列推理是否正确：判断下列推理是否正确：(1)p,pq q(2)p,qp q解解 只要写出前提的合取式与结论的真值表，看是否出现前提合取式为真，只要写出前提的合取式与结论的真值表，看是否出现前提合取式为真，而推论为假的情况。而推论为假的情况。 (1)由上表可知，没有出现前提合取式为真，而结论为假的情况，因由上表可知，没有出现前提合取式为真，而结论为假的情况，因而而(1)中推理正确，

4、即中推理正确，即p,pqq. (2)由上表可知，在赋值为由上表可知，在赋值为10情况下，出现了前提合取式为真，而结情况下，出现了前提合取式为真，而结论为假的情况，因而论为假的情况，因而(2)推理不正确，即推理不正确，即p,qp q.4推理的形式结构推理的形式结构2. A1 A2 AkB 若推理正确若推理正确, 记为记为A1 A2 Ak B3. 前提：前提： A1, A2, , Ak 结论：结论： B判断推理是否正确的方法判断推理是否正确的方法: 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法推理的形式结构推理的形式结构1. A1, A2, , Ak B 若推理正确若推理正确,

5、 记为记为A1,A2,Ak B定理定理3.1 由命题公式由命题公式A1, A2, , Ak 推推B的推理正确当且仅当的推理正确当且仅当 A1 A2 AkB为重言式为重言式5推理实例推理实例例例3.2 判断下面推理是否正确判断下面推理是否正确(1)若若a能被能被4整除，则整除，则a能被能被2整除；整除； a能被能被4整除。所以整除。所以a能被能被2整除。整除。(2)若若a能被能被4整除，则整除，则a能被能被2整除；整除； a能被能被2整除。所以整除。所以a能被能被4整除。整除。 (3)下午马芳或去看电影或去游泳；她没有看电影。所以，她去游泳了。下午马芳或去看电影或去游泳；她没有看电影。所以，她去

6、游泳了。 (4)若下午气温超过若下午气温超过30，则王小燕必去游泳；若她去游泳，她就不去看，则王小燕必去游泳；若她去游泳，她就不去看电影了。所以王小燕没有去看电影，下午气温必超过了电影了。所以王小燕没有去看电影，下午气温必超过了30。 解解 (1)设设 p：a能被能被4整除。整除。 q ： a能被能被2整除。整除。 前提：前提：pq，p 结论：结论：q 推理的形式结构：推理的形式结构：(pq)pq 由例由例3.1可知，此推理正确，即可知，此推理正确，即(pq)pq。 （2）设）设p，q的含义同的含义同(1)。 前提：前提：pq，q 结论：结论：p 推理的形式结构：推理的形式结构：(pq)qp

7、在此推理中，容易看出在此推理中，容易看出01是以上形式结构的成假赋值，所以是以上形式结构的成假赋值，所以(2)推理不正确。推理不正确。 6推理实例推理实例例例3.2 判断下面推理是否正确判断下面推理是否正确(3)下午马芳或去看电影或去游泳；她没有看电影。所以，她去游泳了。下午马芳或去看电影或去游泳；她没有看电影。所以，她去游泳了。解：解： (3)设设 p：马芳下午看电影。：马芳下午看电影。 q：马芳下午去游泳。：马芳下午去游泳。 前提：前提：pq，p 结论：结论：q 推理形式结构：推理形式结构：(pq)p)q 用等值演算法来判断上式是否为重言式。用等值演算法来判断上式是否为重言式。 (pq)p

8、)q (pq)p)q (pq)p)q (pq)p)q (pp)(qp)q qpq 1 这说明上式为重言式，所以推理正确。这说明上式为重言式，所以推理正确。 7推理实例推理实例例例3.2 判断下面推理是否正确判断下面推理是否正确 (4)若下午气温超过若下午气温超过30，则王小燕必去游泳；若她去游泳，她就不去看电影，则王小燕必去游泳；若她去游泳，她就不去看电影了。所以王小燕没有去看电影，下午气温必超过了了。所以王小燕没有去看电影，下午气温必超过了30。 （4）解：）解： 设设 p：下午气温超过：下午气温超过30。 q：王小燕去游泳。：王小燕去游泳。 r： 王小燕去看电影。王小燕去看电影。 前提：前

9、提：pq，qr 结论：结论：rp 推理的形式结构：推理的形式结构： (pq)(qr)(rp) 用主析取范式法判断上式是否为重言式。用主析取范式法判断上式是否为重言式。 (pq)(qr)(rp) (pq)(qr)(rp) (pq)(qr)rp rp (用两次吸收律用两次吸收律) (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) (pqr)(pqr) m1m3m4m5m6m7 可见上式不是重言式（主析取范式中少两个极小项可见上式不是重言式（主析取范式中少两个极小项 m0，m2），所以），所以推理不正确。推理不正确。 8推理定律推理定律重言蕴涵式重言蕴涵式1. A (A B) 附加律附

10、加律 2. (A B) A 化简律化简律3. (AB) A B 假言推理假言推理4. (AB)B A 拒取式拒取式 5. (A B)B A 析取三段论析取三段论6. (AB) (BC) (AC) 假言三段论假言三段论7. (AB) (BC) (AC) 等价三段论等价三段论8. (AB) (CD) (A C) (B D) 构造性二难构造性二难 (AB) ( AB) B 构造性二难构造性二难(特殊形式特殊形式)9. (AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如, 由由AA可产生可产生 AA 和和 AA93.2 自然推理

11、系统自然推理系统P定义定义3.2 一个一个形式系统形式系统 I 由下面四个部分组成：由下面四个部分组成： (1) 非空的字母表，记作非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作推理规则集，记作 R(I). 记记I=, 其中其中是是 I 的的形式语言形式语言系统系统, 是是 I 的的形式演算系统形式演算系统.自然推理系统自然推理系统: 无公理无公理, 即即AX(I)=公理推理系统公理推理系统: 推

12、出的结论是系统中的重言式推出的结论是系统中的重言式, 称作称作定理定理10自然推理系统自然推理系统P定义定义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1. 字母表字母表 (1) 命题变项符号：命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：联结词符号： , , , , (3) 括号与逗号：括号与逗号：(, ), ，2. 合式公式（同定义合式公式（同定义1.6）3. 推理规则推理规则 (1) 前提引入规则前提引入规则 (2) 结论引入规则结论引入规则 (3) 置换规则置换规则11推理规则推理规则(4) 假言推理规则假言推理规则 (6) 化简规则化简规

13、则 (8) 假言三段论规则假言三段论规则 AB AB AA B A B A(5) 附加规则附加规则 (7) 拒取式规则拒取式规则 (9) 析取三段论规则析取三段论规则 AB B A AB BCACA B BA12推理规则推理规则(10) 构造性二难推理规则构造性二难推理规则 (11) 破坏性二难推理规则破坏性二难推理规则 (12) 合取引入规则合取引入规则 AB CD A C B D AB CD BD A C A BA B13在自然推理系统在自然推理系统P中构造证明中构造证明设前提设前提A1, A2, Ak,结论结论B及公式序列及公式序列C1, C2, Cl. 如果每如果每一个一个Ci(1 i

14、 l)是某个是某个Aj, 或者可由序列中前面的公式应用推理或者可由序列中前面的公式应用推理规则得到规则得到, 并且并且Cl =B, 则称这个公式序列是由则称这个公式序列是由A1, A2, Ak推推出出B的的证明证明直接证明法直接证明法附加前提证明法附加前提证明法归谬法（反证法）归谬法（反证法）14直接证明法直接证明法例例3.3 在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明： （1）前提：）前提：p q,q r,p s, s 结论：结论：r (p q) （2）前提：前提： p q,r q,r s 结论：结论：p s (1) 证明证明: ps 前提引入前提引入 s 前提

15、引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 q r 前提引入前提引入 r 假言推理假言推理 r (p q) 合取引入合取引入所以推理正确，所以推理正确， r (p q)是有效的结论是有效的结论直接证明法直接证明法例例3.3 在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明： （1）前提：）前提：p q,q r,p s, s 结论：结论：r (p q) （2）前提：前提： p q,r q,rs 结论：结论：ps(2) 证明证明: p q 前提引入前提引入 pq 置换置换 r q 前提引入前提引入 qr 置换置换 pr 假言三段论假言

16、三段论 rs 前提引入前提引入 ps 假言三段论假言三段论所以推理正确，所以推理正确， ps是有效结论得证是有效结论得证15直接证明法例题直接证明法例题例例3.4 在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明： 若数若数a是实数，则它不是有理数就是无理数；若是实数，则它不是有理数就是无理数；若a不能不能表示成分数，则它不是有理数；表示成分数，则它不是有理数；a是实数且它不能表示成是实数且它不能表示成分数。所以分数。所以a是无理数。是无理数。 解解 首先将简单命题符号化：首先将简单命题符号化： 设设 p：a是实数。是实数。 q：a是有理数。是有理数。 r：a是无理数。

17、是无理数。 s：a能表示成分数。能表示成分数。 前提：前提：p(qr), sq, ps 结论：结论：r 16直接证明法例题直接证明法例题 前提：前提：p(qr), sq, ps 结论：结论：r 证明：证明： ps 前提引入前提引入 p 化简化简 s 化简化简 p(qr) 前提引入前提引入 qr 假言推理假言推理 sq 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论 1718附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：A1, A2, , Ak 结论：结论：CB等价地证明等价地证明 前提：前提：A1, A2,

18、 , Ak, C 结论：结论：B理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B19附加前提证明法实例附加前提证明法实例例例3.5 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明 如果小张和小王去看电影，则小李也去看电影；小赵不如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影去看电影时，小李也去看电影.解解 用附加前提证明法构造证明用附加前提证明法构造证明

19、 (1)将简单命题符号化：将简单命题符号化： 设设 p:小张去看电影小张去看电影. q:小王去看电影小王去看电影. r:小李去看电影小李去看电影. s:小赵去看电影小赵去看电影. (2) 推理的形式结构推理的形式结构 前提：前提：(pq)r,sp,q 结论：结论：sr20附加前提证明法实例附加前提证明法实例 (2) 推理的形式结构推理的形式结构 前提：前提：(pq)r,sp,q 结论：结论：sr (3) 证明证明 s 附加前提引入附加前提引入 sp 前提引入前提引入 p 析取三段论析取三段论 (pq)r 前提引入前提引入 q 前提引入前提引入 pq 合取合取 r 假言推理假言推理21不用附不用

20、附加前加前提法证明提法证明 (2) 推理的形式结构推理的形式结构 前提：前提：(pq)r,sp,q 结论：结论：sr (3) 证明证明 sp 前提引入前提引入 s p 置换置换 (pq)r 前提引入前提引入 p q r 置换置换 q 前提引入前提引入 p r 析取三段论析取三段论 p r 置换置换 sr 假言假言三段论三段论归谬法（反证法）归谬法（反证法）归谬法归谬法 (反证法反证法)欲证欲证 前提：前提：A1, A2, , Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB) (A1 A

21、2 AkB) 0 A1 A2 AkB0若（若（A1 A2 AkB）为）为矛盾式，则说明矛盾式，则说明(A1 A2 Ak) B是重言是重言式，即：式，即： A1 A2 Ak B，故推理正确。，故推理正确。这种将结论的否定式作为附这种将结论的否定式作为附加前提引入并推出矛盾式的加前提引入并推出矛盾式的证明方法称为证明方法称为归谬法归谬法。23归谬法实例归谬法实例例例3.6 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明 如果小张守第一垒并且小李向如果小张守第一垒并且小李向B队投球，则队投球，则A队将取胜；队将取胜；或者或者A队未取胜，或者队未取胜，或者A队获得联赛第一名；队

22、获得联赛第一名；A队没有获得队没有获得联赛的第一名；小张守第一垒。因此，小李没有向联赛的第一名；小张守第一垒。因此，小李没有向B队投队投球。球。 解解 先将简单命题符号化先将简单命题符号化: 设设 p:小张守第一垒。小张守第一垒。 q:小李向小李向B队投球。队投球。 r:A队取胜。队取胜。 s:A队获得联赛第一名。队获得联赛第一名。 前提：前提：(pq)r,rs,s ,p 结论：结论：q 证明：用归谬法证明：用归谬法归谬法证明实例归谬法证明实例 前提：前提：(pq)r,rs,s ,p 结论：结论：q 证明：用归谬法证明：用归谬法 q 结论的否定引入结论的否定引入 rs 前提引入前提引入 s 前

23、提引入前提引入 r 析取三段论析取三段论 (pq)r 前提引人前提引人 (pq) 拒取式拒取式 pq 置换置换 p 前提引入前提引入 q 析取三段论析取三段论 qq 合取合取 由于最后一步由于最后一步qq 0，即，即(pq)r)(rs)sp)q 0，所以推理正确。，所以推理正确。 24不用归谬法证明不用归谬法证明 前提：前提：(pq)r,rs,s ,p 结论：结论：q 证明：证明： (pq)r 前提引入前提引入 p q r 置换置换 p 前提引入前提引入 q r 析取三段论析取三段论 rs 前提引人前提引人 s 前提引人前提引人 r 析取三段论析取三段论 q 析取三段论析取三段论25作业作业

24、书本第书本第54页的第页的第15题第（题第（1）小题）小题 书本第书本第54页的第页的第16题第（题第（1）小题）小题 书本第书本第54页的第页的第17题题 请大家把答案写在科作业纸上，注意写明题号。下次上课请大家把答案写在科作业纸上，注意写明题号。下次上课之前交给我。之前交给我。27第三章第三章 习题课习题课主要内容主要内容l 推理的形式结构推理的形式结构l 判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系统自然推理系统Pl 构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明

25、法附加前提证明法 归谬法归谬法(反证法反证法)作作业业 书本第书本第52页的第页的第11题（要求要抄写题目，即证明的主体）题（要求要抄写题目，即证明的主体） 书本第书本第53页的第页的第12题（要求要抄写题目，即证明的主体题（要求要抄写题目，即证明的主体） 书本第书本第53页的第页的第14题第（题第（1）小题）小题 书本第书本第53页的第页的第14题第（题第（5）小题小题 书本第书本第54页的第页的第16题第（题第（1）小题）小题 书本第书本第54页的第页的第17题题 请大家把作业作在科作业纸上，下次上课之前交。请大家把作业作在科作业纸上，下次上课之前交。29基本要求基本要求l 理解并记住推理

26、形式结构的两种形式：理解并记住推理形式结构的两种形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 结论：结论：Bl 熟练掌握判断推理是否正确的不同方法（如真值表法、等熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l 牢记牢记 P 系统中各条推理规则系统中各条推理规则l 熟练掌握构造证明的直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l 会解决实际中的简单推理问题会解决实际中的简单推理问题土耳其商人和帽子的故事土耳其商人和帽子的故事 这是著名物理学家爱因斯坦出过的一道

27、题这是著名物理学家爱因斯坦出过的一道题. 一个土耳其商人，想找一个十分聪明的助手协助他经商，一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘有两个人前来应聘.这个商人为了试一试哪一个聪明些，就把这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后说：两个人带进一间漆黑的屋子里，他打开电灯后说：“这张桌这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的子上有五顶帽子，两顶是红色的，三顶是黑色的.现在，我把现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快

28、地说出自己头一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的上戴的帽子是什么颜色的.”说完之后，商人将电灯关掉，然后说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开藏了起来，接着把电灯打开.这时，那两个应试者看到这时，那两个应试者看到商人头商人头上戴的是一顶红帽子上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：，过了一会儿，其中一个人便喊到：“我戴的是黑帽子我戴的是黑帽子.” 请问这个人猜得对吗请问这个人猜得对吗?是怎么推导出来的是怎么推导出来的?解解:设设

29、 p1:猜对的人戴红帽子猜对的人戴红帽子. p2:猜对的人戴黑帽子猜对的人戴黑帽子. q1:另一个人戴红帽子另一个人戴红帽子. q2:另一个人戴黑帽子另一个人戴黑帽子. r:商人戴红帽子商人戴红帽子. 商人头上戴的是红帽子，即商人头上戴的是红帽子，即r为真，另一个人没有作出断定，故为真，另一个人没有作出断定，故q1，q2真真假未定。有如下几种可能：假未定。有如下几种可能：（1）如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子，）如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子，因为红帽子只有两顶。因为红帽子只有两顶。 （2）如果商人和另一个戴的都是红帽子，那么猜对的人戴的就

30、是黑帽子）如果商人和另一个戴的都是红帽子，那么猜对的人戴的就是黑帽子（3）如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子）如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子 （4）如果另一个人戴的不是红帽子，那么他戴的就是黑帽子。）如果另一个人戴的不是红帽子，那么他戴的就是黑帽子。根据题设，上面四种可能情况符化号为：根据题设，上面四种可能情况符化号为：（1） r p1 q2 （2） r q1 p2 （3） p1 p2 （4） q1 q2假设假设p1为真为真 p1 前提引入前提引入 r 前提引入前提引入 p1 r 合取引入合取引入 r p1 q2 前提引入前提引入 q2 假言推理假言推理 这就是说，这就是说， q2:另一个人戴黑帽子，这个判定是必然可以作出的，另一个人戴黑帽子，这个判定是必然可以作出的，但是这与题设条件（即但是这与题设条件（即“另一个没有作出判定另一个没有作出判定”）相矛盾，因此，）相矛盾，因此，p1为假，即为假，即 p1为真，为真， p1 前提引入前提引入 p1 p2 前提引入前提引入 p2 假言推理假言推理 即即p2是有效的结论，这就是说，是有效的结论，这就是说，“猜对的人戴着黑帽子猜对的人戴着黑帽子”是真的是真的，所以猜对的人肯定的说：，所以猜对的人肯定的说：“我戴的是黑帽子我戴的是黑帽子”。33练习练习1：判断推理是否正确：判断推理是否