《离散数学课件03命题逻辑的推理理论》由会员分享，可在线阅读，更多相关《离散数学课件03命题逻辑的推理理论（57页珍藏版）》请在金锄头文库上搜索。
1、第第3 3章章 命题逻辑的推理理论命题逻辑的推理理论离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容推理的形式结构推理的形式结构自然推理系统自然推理系统P Pq本章与后续各章的关系本章与后续各章的关系本章是第五章的特殊情况和先行准备本章是第五章的特殊情况和先行准备q3.1 3.1 推理的形式结构推理的形式结构q3.2 3.2 自然推理系统自然推理系统P Pq 本章小结本章小结q 习题习题q 作业作业3.1 3.1 推理的形式结构推理的形式结构推理的形式结构推理的形式结构q数理逻辑的主要任务是数理逻辑的主要任务是用数
2、学的方法来研究数学中的用数学的方法来研究数学中的推理推理。q推理推理是指从前提出发推出结论的思维过程。是指从前提出发推出结论的思维过程。q前提前提是已知命题公式集合。是已知命题公式集合。q结论结论是从前提出发应用推理规则推出的命题公式。是从前提出发应用推理规则推出的命题公式。q证明证明是描述推理正确或错误的过程。是描述推理正确或错误的过程。q要研究推理，首先应该明确什么样的推理是有效的或要研究推理，首先应该明确什么样的推理是有效的或正确的。正确的。命题逻辑的推理理论命题逻辑的推理理论概念概念描述问题描述问题的句子的句子判断判断对概念的肯对概念的肯定与否定的定与否定的判断判断推理推理从一个或多从
3、一个或多个前提推出个前提推出结论的思维结论的思维过程过程认识世界的渐进过程认识世界的渐进过程定义定义3.1 3.1 设设A A1 1,A,A2 2,A,Ak k和和B B都是命题公式，若对于都是命题公式，若对于A A1 1,A,A2 2,A,Ak k和和B B中出现的命题变项的任意一组赋值，中出现的命题变项的任意一组赋值，（1 1）或者）或者A A1 1AA2 2 A Ak k为假为假; ;（2 2）或者当）或者当A A1 1AA2 2 A Ak k为真时，为真时，B B也为真也为真; ;则称由前提则称由前提A A1 1,A,A2 2,A,Ak k推出推出B B的的推理是有效的或正确推理是有效
4、的或正确的的，并称，并称B B是是有效结论有效结论。有效推理的定义有效推理的定义有效推理的定义有效推理的定义关于有效推理的说明关于有效推理的说明q A1，A2，Ak由由 推推B的推理记为的推理记为B若推理是正确的，记为若推理是正确的，记为 B若推理是不正确的，记为若推理是不正确的，记为 Bq由前提由前提A1，A2，Ak推结论推结论B的推理是否正确的推理是否正确与诸前提的排列次序无关。与诸前提的排列次序无关。关于有效推理的说明关于有效推理的说明q设设A A1 1，A A2 2，A Ak k，B B中共出现中共出现n n个命题变项，对于任何个命题变项，对于任何一组赋值一组赋值1 12 2n n(i
5、 i=0=0或者或者1 1，i=1,2,n)i=1,2,n)，前提前提和结论的取值情况有以下四种：和结论的取值情况有以下四种： (1) (1) A A1 1AA2 2 A Ak k为为0 0，B B为为0 0。(2) (2) A A1 1AA2 2 A Ak k为为0 0，B B为为1 1。(3) (3) A A1 1AA2 2 A Ak k为为1 1，B B为为0 0。(4) (4) A A1 1AA2 2 A Ak k为为1 1，B B为为1 1。q只要不出现只要不出现(3)(3)中的情况，推理就是正确的，因而判断中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现推理是否正
6、确，就是判断是否会出现(3)(3)中的情况。中的情况。q推理正确，并不能保证结论推理正确，并不能保证结论B B一定为真一定为真。 (1) (1) p,pq qp,pq q(2) p,qp q (2) p,qp q 判断下列推理是否正确。（真值表法）判断下列推理是否正确。（真值表法） pqp (pq)qp (qp)q000000010101100010111111例题例题例题例题正确正确不正确不正确 命题公式命题公式A A1 1,A,A2 2,A,Ak k推推B B的推理正确当且仅当的推理正确当且仅当 ( (A A1 1AA2 2AAk k )B )B 为重言式。为重言式。q该定理是判断推理是否
7、正确的另一种方法。该定理是判断推理是否正确的另一种方法。 说明说明有效推理的等价定理有效推理的等价定理有效推理的等价定理有效推理的等价定理(1)(1)证明必要性。若证明必要性。若A A1 1,A,A2 2,A,Ak k推推B B的推理正确，的推理正确，则对于则对于A A1 1,A,A2 2,A,Ak k,B,B中所含命题变项的任意一组赋值，不会出中所含命题变项的任意一组赋值，不会出现现A A1 1AA2 2AAk k为真，而为真，而B B为假的情况，为假的情况，因而在任何赋值下，蕴涵式因而在任何赋值下，蕴涵式( (A A1 1AA2 2AAk k )B )B均为真，故它均为真，故它为重言式。为
8、重言式。 (2)(2)证明充分性。若蕴涵式证明充分性。若蕴涵式( (A A1 1AA2 2AAk k)B)B为重言式，为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，为假的情况，即在任何赋值下，或者即在任何赋值下，或者A A1 1AA2 2AAk k为假，为假，或者或者A A1 1AA2 2AAk k和和B B同时为真，这正符合推理正确的定义。同时为真，这正符合推理正确的定义。 当推理正确时，当推理正确时，q形式（形式（1）记为）记为 B。q形式（形式（2）记为）记为A1 A2 AkB。表示蕴涵式为重言式。表示蕴
9、涵式为重言式。(1)设设 =A1,A2,Ak，记为记为 B。(2)A1 A2 AkB(3)前提：前提：A1,A2,Ak结论：结论：B说明说明推理的形式结构推理的形式结构推理的形式结构推理的形式结构判断有效结论的常用方法判断有效结论的常用方法 要求要求=G G1 1, G, G2 2, ,G, ,Gn n H H也就是也就是G G1 1GG2 2GGn n为永真公式为永真公式因而因而真值表技术、演绎法和真值表技术、演绎法和间接证明方法间接证明方法q 真值表法真值表法 q 等值演算法等值演算法 q 主析取范式法主析取范式法判断推理是否正确的方法判断推理是否正确的方法q是否有其他的证明方法？是否有其
10、他的证明方法？思考思考q当命题变项较少时当命题变项较少时,这三种方法比较方便这三种方法比较方便。说明说明（1 1） 下午马芳或去看电影或去游泳。她没去看电影，所以，她下午马芳或去看电影或去游泳。她没去看电影，所以，她 去游泳了。去游泳了。 判断下列推理是否正确。（等值演算法）判断下列推理是否正确。（等值演算法） 解：设解：设p:p:马芳下午去看电影，马芳下午去看电影，q:q:马芳下午去游泳。马芳下午去游泳。 前提：前提： p pq q，p p 结论：结论： q q 推理的形式结构：推理的形式结构： (p(pq)q)p)p)q q (p (pq)q)p)p)q q (p(pq)q)p) p) q
11、 q (p pq)q)p p) ) q q (p pp p ) )(q qp) p) q q ( (q qp) p) q q 1 1由定理由定理 3.1 3.1可知，可知，推理正确。推理正确。例题例题例题例题(1) A (1) A (AB)(AB) 附加律附加律(2) (2) (AB) AB) A A 化简律化简律(3)(3)( (AB)A AB)A B B 假言推理假言推理(4) (4) (AB)B AB)B A A 拒取拒取式式(5) (5) (AB)B AB)B A A 析取三段论析取三段论 (6)(6)( (AB) (BC) AB) (BC) (AC) (AC) 假言三段论假言三段论(
12、7)(7)( (A AB) (BB) (BC) C) (A (A C) C) 等价三段论等价三段论(8)(8)( (AB)(CD)(AC) AB)(CD)(AC) (BD)(BD) 构造构造性二难性二难 ( (AB)(AB)(AA) AB)(AB)(AA) B B 构造性二难构造性二难 ( (特殊形式特殊形式) )(9)(9)(AB)(CD)(BD) AB)(CD)(BD) (AC) (AC) 破坏性二难破坏性二难推理定律推理定律推理定律推理定律-重言蕴含式重言蕴含式重言蕴含式重言蕴含式小节结束小节结束关于推理定律的几点说明关于推理定律的几点说明关于推理定律的几点说明关于推理定律的几点说明qA
13、,B,CA,B,C为元语言符号，代表任意的命题公式。为元语言符号，代表任意的命题公式。q若一个推理的形式结构与某条推理定律对应的蕴涵若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。式一致，则不用证明就可断定这个推理是正确的。q2.12.1节给出的节给出的2424个等值式中的每一个都派生出两条推个等值式中的每一个都派生出两条推理定律。例如双重否定律理定律。例如双重否定律A A A A产生两条推理定产生两条推理定律律A A A A和和 A AA A。q由九条推理定律可以产生九条推理规则由九条推理定律可以产生九条推理规则, ,它们构成了它们构成了推理系统中的推
14、理规则推理系统中的推理规则。3.2 3.2 自然推理系统自然推理系统P Pq判断推理是否正确的三种方法：真值表法、等值演判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。算法和主析取范式法。q当推理中包含的命题变项较多时，上述三种方法演当推理中包含的命题变项较多时，上述三种方法演算量太大。算量太大。q对于由前提对于由前提A A1 1,A,A2 2,A,Ak k推推B B的正确推理应该给出严谨的正确推理应该给出严谨的证明的证明。q证明是一个描述推理过程的命题公式序列，其中的证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理每个公式或者是前提，或
15、者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。规则得到的结论（中间结论或推理中的结论）。q要构造出严谨的证明就必须在形式系统中进行。要构造出严谨的证明就必须在形式系统中进行。自然推理系统自然推理系统P P自然推理系统自然推理系统P P由下述由下述3 3部分组成部分组成: :1. 1. 字母表字母表(1) (1) 命题变项符号命题变项符号: : p,q,r,p,q,r, p, pi i,q,qi i,r,ri i, ,(2) (2) 联结词联结词: : , , , , , , , , (3) (3) 括号与逗号括号与逗号: ( ), ,: ( ), ,2. 2. 合式公式合式公
16、式3. 3. 推理规则推理规则(1) (1) 前提引入规则前提引入规则(2) (2) 结论引入规则结论引入规则(3) (3) 置换规则置换规则自然推理系统的定义自然推理系统的定义（4 4）假言推理规则）假言推理规则 A AB B A A B B（5 5）附加规则）附加规则 A A A A B B（6 6）化简规则）化简规则 A A B B A A（4 4）若今天下雪）若今天下雪, ,则将去滑则将去滑雪。今天下雪，所以去滑雪。雪。今天下雪，所以去滑雪。（5 5）现在气温在冰点以下。）现在气温在冰点以下。因此，要么现在气温在冰点因此，要么现在气温在冰点以下，要么现在下雨。以下，要么现在下雨。（6
17、6）现在气温在冰点以下并）现在气温在冰点以下并且正在下雨。因此，现在气且正在下雨。因此，现在气温在冰点以下。温在冰点以下。自然推理系统的定义自然推理系统的定义（7 7）拒取式规则）拒取式规则 A AB B B B A A（8 8）假言三段论规则假言三段论规则 A AB B B BC C A AC C（9 9）析取三段论规则）析取三段论规则 A A B B B B A A自然推理系统的定义自然推理系统的定义（1010）构造性二难推理规则）构造性二难推理规则 A AB B C CD D A A C C B B D D （1111）破坏性二难推理规则）破坏性二难推理规则 A AB B C CD D
18、B BD D A AC C（1212） 合取引入规则合取引入规则 A A B B A A B B在自然推理系统在自然推理系统在自然推理系统在自然推理系统P P P P中构造证明中构造证明中构造证明中构造证明qP P中构造证明就是由一组中构造证明就是由一组P P中公式作为前提，利用中公式作为前提，利用P P中的规则，推出结论。中的规则，推出结论。q构造形式结构构造形式结构A A1 1 A A2 2 A Ak k B B 的推理的的推理的书写方书写方法：法：前提：前提： A A1 1,A,A2 2,A,Ak k 结论：结论： B Bq证明方法：证明方法：直接证明法直接证明法 附加前提法附加前提法归
19、谬法（或称反证法）归谬法（或称反证法）命题逻辑推理的难点命题逻辑推理的难点 1.1.弄清楚弄清楚蕴涵式蕴涵式PQPQ的逻辑关系及其真值，这里的逻辑关系及其真值，这里Q Q是是P P的必的必要条件。无论蕴涵关系如何表述，都要仔细地区分出蕴要条件。无论蕴涵关系如何表述，都要仔细地区分出蕴涵式的前件和后件。涵式的前件和后件。2.2.推理过程中推理过程中推理规则、基本等值式和逻辑蕴涵式的引用推理规则、基本等值式和逻辑蕴涵式的引用要适当，逻辑思维要清晰。要适当，逻辑思维要清晰。3.3.弄清楚几种推理方法的区别与联系，对于命题逻辑推理弄清楚几种推理方法的区别与联系，对于命题逻辑推理而言，任何一个问题的推理
20、，都可以采取而言，任何一个问题的推理，都可以采取三种推理方法三种推理方法中的任何一种来证明，中的任何一种来证明，针对不同的问题选用不同的推理针对不同的问题选用不同的推理方法方法。一般而言，对于结论是蕴涵式或析取式的，大多。一般而言，对于结论是蕴涵式或析取式的，大多可以采取带附加前提的直接证明方法。可以采取带附加前提的直接证明方法。 例题例题 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：前提：前提：pq, rq ,rs pq, rq ,rs 结论：结论：ps ps pqpq 前提引入前提引入 pq pq 置换置换 rqrq 前提引入前提引入 qr qr 置换置换
21、 pr pr 假言三段论假言三段论 rs rs 前提引入前提引入 ps ps 假言三段论假言三段论 例题例题例题例题 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：前提：前提：pp（qrqr）, p, pq q 结论：结论： rs rs pp（qrqr） 前提引入前提引入 p pq q 前提引入前提引入 p p 化简化简 q q 化简化简 qrqr 假言推理假言推理 r r 假言推理假言推理 rsrs 附加附加 rsrs置换置换例题例题 在在 自自 然然 推推 理理 系系 统统 P P中中 构构 造造 下下 面面 推推 理理 的的 证证 明明 ： 若若数数a a
22、是是实实数数，则则它它不不是是有有理理数数就就是是无无理理数数；若若a a不不能能表表示示成成分分数数，则则它它不不是是有有理理数数；a a是是实实数数且且它它不不能能表表示示成成分分数数。所以所以a a是无理数。是无理数。 构造证明：构造证明：（1 1）将简单命题符号化：）将简单命题符号化： 设设 p p：a a是实数。是实数。 q q：a a是有理数。是有理数。 r r：a a是无理数。是无理数。 s s：a a能表示成分数。能表示成分数。（2 2）形式结构：）形式结构： 前提：前提：p(qr), sq, psp(qr), sq, ps 结论：结论：r r ps ps 前提引入前提引入 p
23、 p 化简化简 s s 化简化简 p(qr) p(qr) 前提引入前提引入 qr qr 假言推理假言推理 sqsq 前提引入前提引入 q q 假言推理假言推理 r r 析取三段论析取三段论 例题例题例题例题例题例题 在自然推理系统在自然推理系统P P中构造下面推理的证明。中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。看电影时，小李也去看电影。构造证明：构造证明：（1 1）将简单命题符号化：）将简
24、单命题符号化： 设设 p:p:小张去看电影。小张去看电影。 q:q:小王去看电影。小王去看电影。 r:r:小李去看电影。小李去看电影。 s:s:小赵去看电影。小赵去看电影。 例题例题（2 2） 形式结构：形式结构：前提：前提：( (pq)r,sp,q pq)r,sp,q 结论：结论：sr sr （3 3）证明：用附加前提证明法）证明：用附加前提证明法 s s 附加前提引入附加前提引入 spsp 前提引入前提引入 p p 析取三段论析取三段论 ( (pq)r pq)r 前提引入前提引入 q q 前提引入前提引入 pqpq 合取合取 r r 假言推理假言推理 例题例题 在自然推理系统在自然推理系统
25、P P中构造下面推理的证明。中构造下面推理的证明。如果小张守第一垒并且小李向如果小张守第一垒并且小李向B B队投球，则队投球，则A A队将取胜；或者队将取胜；或者A A队队未取胜，或者未取胜，或者A A队获得联赛第一名；队获得联赛第一名；A A队没有获得联赛的第一名；队没有获得联赛的第一名；小张守第一垒。因此，小李没有向小张守第一垒。因此，小李没有向B B队投球。队投球。 构造证明：构造证明：（1 1）将简单命题符号化：）将简单命题符号化： 设设 p:p:小张守第一垒。小张守第一垒。 q:q:小李向小李向B B队投球。队投球。 r:Ar:A队取胜。队取胜。 s:As:A队获得联赛第一名。队获得
26、联赛第一名。（2 2）形式结构：）形式结构： 前提：前提：( (pq)r,rs,s ,p pq)r,rs,s ,p 结论：结论：q q 例题例题（3 3）证明：用归谬法）证明：用归谬法 q q 结论的否定引入结论的否定引入 rs rs 前提引入前提引入 s s 前提引入前提引入 r r 析取三段论析取三段论 ( (pq)r pq)r 前提引人前提引人 ( (pq)pq) 拒取式拒取式 pq pq 置换置换 p p 前提引入前提引入 q q 析取三段论析取三段论 qqqq 合取合取 由于最后一步为矛盾式，所以推理正确。由于最后一步为矛盾式，所以推理正确。 小节结束小节结束本章主要内容本章主要内容
27、q推理的形式结构：推理的形式结构：推理的前提推理的前提推理的结论推理的结论 推理正确推理正确q判断推理是否正确的方法：判断推理是否正确的方法：真值表法真值表法等值演算法等值演算法 主析取范式法主析取范式法 q对于正确的推理，在自然推理系统对于正确的推理，在自然推理系统P P中构造证明中构造证明: : 自然推理系统自然推理系统P P的定义的定义自然推理系统自然推理系统P P的推理规则：的推理规则： 附加前提证明法附加前提证明法归谬法归谬法本章学习要求本章学习要求q理解并记住推理的形式结构的三种等价形式，即理解并记住推理的形式结构的三种等价形式，即A1,A2,AkBA1A2AkB前提：前提：A1,
28、A2,Ak结论：结论：B在判断推理是否正确时，用在判断推理是否正确时，用；在；在P系统中构造证明时用系统中构造证明时用。q熟练掌握判断推理是否正确的三种方法（真值表法，等值演算熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。法，主析取范式法）。q牢记牢记P系统中的各条推理规则。系统中的各条推理规则。q对于给定的正确推理，要求在对于给定的正确推理，要求在P系统中给出严谨的证明序列。系统中给出严谨的证明序列。q会用附加前提证明法和归谬法。会用附加前提证明法和归谬法。小节结束小节结束习题习题1、用用不不同同的的方方法法验验证证下下面面推推理理是是否否正正确确。对对于于正正确
29、确的的推推理理还还要在要在P系统中给出证明。系统中给出证明。（1）前提：前提： pq, q结论：结论： p（2）前提：前提：qr,pr结论：结论：qp（1）不正确。）不正确。验证答案，只需证明验证答案，只需证明( pq)qp不是重言式。不是重言式。方法一方法一等值演算等值演算( pq)qp (p q)q)p( pq) qp( p q) ( q q)p p q易易知知10是是成成假假赋赋值值，故故( pq)qp不不是是重重言言式式，所所以以推理不正确。推理不正确。方法二方法二主析取范式法主析取范式法经过演算后可知经过演算后可知( pq)qpm0 m1 m3未含未含m2,故故( pq)qp不是重言
30、式。不是重言式。方法三方法三直接观察出直接观察出10是成假赋值。是成假赋值。方法四方法四真值表法真值表法( pq)qp的真值表为的真值表为pq( pq)qp001101010111结论（不正确）是对的。结论（不正确）是对的。（2）推理正确）推理正确方法一方法一真值表法（自己做）真值表法（自己做）方法二方法二等值演算法（自己做）等值演算法（自己做）方法三方法三主析取范式法（自己做）主析取范式法（自己做）方法四方法四P系统中构造证明系统中构造证明证明：证明：（直接证明法）（直接证明法）pr（前提引入）前提引入）rp（置换）置换）qr（前提引入）前提引入）qp（假言三段论）假言三段论）2、在、在P系
31、统中构造下面推理的证明：系统中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩。如果今天是周六，我们就到颐和园或圆明园玩。如如果颐和园游人太多，就不去颐和园。果颐和园游人太多，就不去颐和园。今天是周六，并且今天是周六，并且颐和园游人太多。颐和园游人太多。所以我们去圆明园或动物园玩。所以我们去圆明园或动物园玩。构造证明：构造证明：（1）设设p：今天是周六。今天是周六。q：到颐和园玩。到颐和园玩。r：到圆明园玩。到圆明园玩。s：颐和园游人太多。颐和园游人太多。t：到动物园玩。到动物园玩。（2）前提：）前提：p(q r),sq,p,s结论：结论：r t（3）证明：证明：p(q r)前提引
32、入前提引入p前提引入前提引入q r假言推理假言推理sq前提引入前提引入s前提引入前提引入 q假言推理假言推理r析取三段论析取三段论r t附加附加小节结束小节结束例子例子( (续续1)1)3 3、某女子在某日晚归家途中被杀害，据多方调查确证，凶手、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提：班，没有外出，根据上述案情可得前提：。PQPQ2.2.如果王某是凶手，则他在作案当晚必外出如果王某是凶手，则他在作案当晚必外出PRPR3.3.王某案发之晚并未外出。王某
33、案发之晚并未外出。 RR结论：陈某是凶手。结论：陈某是凶手。Q Q则则可描述为可描述为：PRPR，RRPP( (否定后件式否定后件式) )PQPQ，PPQ Q( (选言三段论选言三段论) )例例4 4一个公安人员审查一件盗窃案，已知的事实如下：一个公安人员审查一件盗窃案，已知的事实如下： A A或或B B盗窃了盗窃了x x；若；若A A盗窃了盗窃了x x，则作案时间不能发生在午，则作案时间不能发生在午夜前；若夜前；若B B证词正确，则在午夜时屋里灯光未灭；若证词正确，则在午夜时屋里灯光未灭；若B B证证词不正确，则作案时间发生在午夜前；午夜时屋里灯光词不正确，则作案时间发生在午夜前；午夜时屋里
34、灯光灭了。灭了。B B盗窃了盗窃了x x。 设设 P P：A A盗窃了盗窃了x x；Q Q：B B盗窃了盗窃了x x； R R：作案时间发生在午夜前；：作案时间发生在午夜前；S S：B B证词正确；证词正确； T T：在午夜时屋里灯光未灭。：在午夜时屋里灯光未灭。 则上述命题可符号化为：则上述命题可符号化为：PQPQ，PP R R，STST， SRSR， T T Q Q 例例4 4（续）（续）证明证明1 1 采用采用直接证明直接证明方法（反证法请学生完成）方法（反证法请学生完成）（1 1） T T前提引入前提引入（2 2） STST前提引入前提引入（3 3） S S(1)(1)，(2)(2)拒
35、取式拒取式（4 4） SRSR前提引入前提引入（5 5） R R(3),(4)(3),(4)假言推理假言推理（6 6） PR PR前提引入前提引入（7 7） P P(5),(6)(5),(6)拒取式拒取式（8 8） PQ PQ前提引入前提引入（9 9） Q Q(7),(8)(7),(8)析取三段论析取三段论 分析分析：令：令P P：马会飞；：马会飞；Q Q：羊吃草；：羊吃草； R R：母鸡是飞鸟；：母鸡是飞鸟； S S：烤熟的鸭子还会跑。：烤熟的鸭子还会跑。符号化上述语句为：符号化上述语句为：=PQR=PQR，RSRS，SS，G=QG=Q。证明证明G G。如果马会飞或羊吃草，则母鸡就会是飞鸟；
36、如果如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。子不会跑。所以羊不吃草。例例5 5 例例5 5 证证明明S S 前提引入前提引入RSRS 前提引入前提引入R R ,拒取式拒取式PQRPQR 前提引入前提引入(PQ)(PQ) , ,拒取式拒取式PQPQ 置换置换Q Q 化简化简思考题：考试佯谬思考题：考试佯谬q逻辑课老师在周末放学时对学生说：逻辑课老师在周末放学时对学生说： 条件一：下周要进行一次考试；条件一：下周要进行一次考试； 条条件件二二：到到底底哪哪天天考考试试，你你们们在在考考试试
37、之之前前的的任任何何一一天天都不能确知。都不能确知。 注注：每每周周上上课课5 5天天（周周一一至至周周五五），每每天天都都上上一一节节逻逻辑辑课课; ;只有在逻辑课时才可能考试。只有在逻辑课时才可能考试。 一个聪明的学生运用逻辑知识做出了以下推理：一个聪明的学生运用逻辑知识做出了以下推理： 推推论论一一：周周五五不不可可能能考考试试，考考试试时时间间一一定定是是周周一一至至周周四四的的某某一一天天。因因为为如如果果周周一一至至周周四四都都不不考考，那那么么周周四四下下课课时时我我们们就就事事先先知知道道了了明明天天一一定定考考试试，这这不不符符合合条条件件二二。但但根根据据条条件件一一，下下
38、周周肯肯定定考考试试，因因此此考考试试时时间间只能是周一至周四的某一天，周五可以排除。只能是周一至周四的某一天，周五可以排除。思考题：考试佯谬思考题：考试佯谬q推论二：周四也不可能考试，考试时间一定是周一至推论二：周四也不可能考试，考试时间一定是周一至周三的某一天。因为如果周一至周三都不考，那么周周三的某一天。因为如果周一至周三都不考，那么周三放学时我们就事先知道了明天考试，这不符合条件三放学时我们就事先知道了明天考试，这不符合条件二。但根据条件一，下周肯定考试，因此考试时间只二。但根据条件一，下周肯定考试，因此考试时间只能是周一至周三的某一天，周四可以排除。能是周一至周三的某一天，周四可以排
39、除。q 推论三：周三也不可能考试，推理过程同上。推论三：周三也不可能考试，推理过程同上。q 推论四：周二也不可能考试，推理过程同上。推论四：周二也不可能考试，推理过程同上。q 推论五：周一也不可能考试，推理过程同上。推论五：周一也不可能考试，推理过程同上。q 结论：下周就不可能考试结论：下周就不可能考试思考题：考试佯谬思考题：考试佯谬q但是老师确实在下周的某一天考试了，这个聪明同学但是老师确实在下周的某一天考试了，这个聪明同学感到非常意外。问题究竟出在哪里呢？感到非常意外。问题究竟出在哪里呢？q提示：将推理过程形式化提示：将推理过程形式化q不失一般性，考虑简化问题的版本：每周只有两次逻不失一般
40、性，考虑简化问题的版本：每周只有两次逻辑课，分别在周一和周四。教师在本周四下课时宣布辑课，分别在周一和周四。教师在本周四下课时宣布下周将有一次逻辑考试。下周将有一次逻辑考试。思考题：考试佯谬思考题：考试佯谬q考试佯谬的一个形式表述考试佯谬的一个形式表述q命题常元命题常元 ExamB: ExamB: 考试在下周一的逻辑课上进行考试在下周一的逻辑课上进行 ExamD: ExamD: 考试在下周四的逻辑课上进行考试在下周四的逻辑课上进行 KnowKnow： 学生在考试所在的那天之前知道考试的时间学生在考试所在的那天之前知道考试的时间系统公理：系统公理：A1A1： （ExamBExamB ExamDE
41、xamD） （ExamBExamB ExamDExamD） A2A2： KnowKnow A3 A3： ExamBKnowExamBKnow A4 A4： ExamDKnowExamDKnow 思考题：考试佯谬思考题：考试佯谬q论证过程：用间接证法论证过程：用间接证法1 1证明证明A1-A4A1-A4和和ExamDExamD矛盾，推出矛盾，推出ExamDExamD；再用间接证法；再用间接证法1 1证明证明A1-A4A1-A4和和ExamBExamB矛盾，推出矛盾，推出ExamBExamB （1 1）1 ExamD 1 ExamD 附加前提附加前提 2 2（ExamBExamB ExamDExa
42、mD） （ExamBExamB ExamDExamD）P P 3 3（ExamBExamB ExamDExamD） （ExamBExamB ExamDExamD）T T （2)2) 4 ExamB 4 ExamB ExamD T (3) ExamD T (3) 5 ExamB T (1)(4) 5 ExamB T (1)(4) 6 ExamBKnow P 6 ExamBKnow P 7 Know T (5)(6) 7 Know T (5)(6) 8 Know P 8 Know P 所以，有所以，有ExamDExamD思考题：考试佯谬思考题：考试佯谬(2) 1 ExamB (2) 1 ExamB
43、 附加前提附加前提 2 2（ExamBExamB ExamDExamD） （ExamBExamB ExamDExamD） P P 3 3（ExamBExamB ExamDExamD） （ExamBExamB ExamDExamD） T (2)T (2) 4 ExamB 4 ExamB ExamD T (3) ExamD T (3) 5 ExamD T (1)(4) 5 ExamD T (1)(4) 6 ExamDKnow P 6 ExamDKnow P 7 Know T (5)(6) 7 Know T (5)(6) 8 Know P 8 Know P 所有，有所有，有 ExamBExamB综合
44、（综合（1 1）和（）和（2 2），有），有ExamBExamB ExamDExamD思考题：考试佯谬思考题：考试佯谬两个结论：两个结论：1 1 学生推理的没有错误学生推理的没有错误 2 2 教师的两个条件符合事实，故应视为真命题教师的两个条件符合事实，故应视为真命题问题：似乎正确的前提和正确的推理导致了错误的结论问题：似乎正确的前提和正确的推理导致了错误的结论（即与教师宣称的真命题矛盾的结论），为什么？（即与教师宣称的真命题矛盾的结论），为什么？回答：佯谬之所以出现，是因为试图将一个广义哥德尔回答：佯谬之所以出现，是因为试图将一个广义哥德尔型命题（可粗略地理解为涉及系统元知识的命题）显型命题
45、（可粗略地理解为涉及系统元知识的命题）显式地作为系统公理，来建构系统的完备性。不幸的是，式地作为系统公理，来建构系统的完备性。不幸的是，一旦这个原本是直觉真的广义哥德尔型命题在系统中一旦这个原本是直觉真的广义哥德尔型命题在系统中被作为公理显式地表达出来，系统在一致性方面就产被作为公理显式地表达出来，系统在一致性方面就产生了新的问题。生了新的问题。“There are truths of silence, when spoken, no There are truths of silence, when spoken, no longer true anymore.” Ludwig Wittge
46、nsteinlonger true anymore.” Ludwig Wittgenstein形式化命题逻辑系统形式化命题逻辑系统q考试佯谬这类逻辑悖论促使人们深入省思逻辑系统的考试佯谬这类逻辑悖论促使人们深入省思逻辑系统的本质，它的能力和局限。对形式化的逻辑系统的研究本质，它的能力和局限。对形式化的逻辑系统的研究有助于实现这个目的。在理论方面：形式化逻辑系统有助于实现这个目的。在理论方面：形式化逻辑系统帮助人们澄清逻辑系统的帮助人们澄清逻辑系统的元性质元性质( (一致性、完全性）一致性、完全性）、澄清基本的数学哲学问题（例如，数学是否可以形式澄清基本的数学哲学问题（例如，数学是否可以形式化希
47、尔伯特方案）；在应用方面：形式化逻辑系统化希尔伯特方案）；在应用方面：形式化逻辑系统在理论计算机科学、计算机科学、人工智能、软件工在理论计算机科学、计算机科学、人工智能、软件工程等领域有着深刻的应用。程等领域有着深刻的应用。形式化命题逻辑系统形式化命题逻辑系统q进一步的思考：更重要和实际的形式数学系统，如形式化数论进一步的思考：更重要和实际的形式数学系统，如形式化数论系统，是否也具有系统系统，是否也具有系统L L的良好性质？如果回答是肯定的，上述的良好性质？如果回答是肯定的，上述数学系统的全部内涵即可由形式系统囊括，至少在理论上，我数学系统的全部内涵即可由形式系统囊括，至少在理论上，我们可以编
48、写一个计算机程序，利用简单地穷尽搜索，逐步获得们可以编写一个计算机程序，利用简单地穷尽搜索，逐步获得一个又一个定理，数学发现的过程可以还原为计算机程序操作一个又一个定理，数学发现的过程可以还原为计算机程序操作q回答：这样的前景从来不会发生。回答：这样的前景从来不会发生。绝大多数绝大多数实际数学系统的形实际数学系统的形式化是不完备的（哥德尔第一不完备性定理），甚至其一致性式化是不完备的（哥德尔第一不完备性定理），甚至其一致性也无法在系统之内得到证明（哥德尔第二不完备性定理）。也无法在系统之内得到证明（哥德尔第二不完备性定理）。数数学真理不可能由包括程序在内的任何机械过程所穷尽，而必然学真理不可能
49、由包括程序在内的任何机械过程所穷尽，而必然包含直觉和洞察的成份包含直觉和洞察的成份。存在着对于人的直觉来说明显为真，。存在着对于人的直觉来说明显为真，但无法形式证明的良定义数学命题（哥德尔）；存在无限多不但无法形式证明的良定义数学命题（哥德尔）；存在无限多不可由可由“机械过程机械过程”计算的函数（图灵）；存在着具有重要实际计算的函数（图灵）；存在着具有重要实际意义，但无法被机械过程解决的判定问题（停机问题图灵）。意义，但无法被机械过程解决的判定问题（停机问题图灵）。形式化命题逻辑系统形式化命题逻辑系统q注：机械过程注：机械过程现代数字计算机程序现代数字计算机程序算法算法图灵机图灵机 所谓的所谓
50、的“机械过程机械过程”，应广义理解，指可实现的物理过程。，应广义理解，指可实现的物理过程。 “ “机械过程机械过程”涉及到数学之外的物理的内涵。量子计算的某些最新涉及到数学之外的物理的内涵。量子计算的某些最新理论研究结果似乎暗示，某种理论上的量子计算模型似乎可以实理论研究结果似乎暗示，某种理论上的量子计算模型似乎可以实现某些经典机械过程无法实现的计算任务（如等价于停机问题的现某些经典机械过程无法实现的计算任务（如等价于停机问题的丢番图方程解的存在性判定问题），但是上述结果尚未形成定论。丢番图方程解的存在性判定问题），但是上述结果尚未形成定论。q思考题：思考题：某些人认为，形式数学系统的不完备性
51、意味着人工智能某些人认为，形式数学系统的不完备性意味着人工智能的不可能性，存在着直觉上为真但形式系统内无法证明的真理，的不可能性，存在着直觉上为真但形式系统内无法证明的真理，说明人心比机器和程序更优越，程序不可能充分模拟人类智能。说明人心比机器和程序更优越，程序不可能充分模拟人类智能。谈谈你对该问题的看法。谈谈你对该问题的看法。q进一步的参考书目：进一步的参考书目： 皇帝新脑皇帝新脑，彭罗斯，胡南科技出版社，彭罗斯，胡南科技出版社 哥德尔、埃舍尔、巴赫哥德尔、埃舍尔、巴赫，D. HofstadterD. Hofstadter， 商务印书馆商务印书馆 作业作业习题三习题三：6、14、15、16、18结束结束
