离散数学：第3章 命题逻辑的推理理论

1第第3 3章章 命题逻辑的推理理论命题逻辑的推理理论 离散数学离散数学 2本章说明本章说明q本章的主要内容本章的主要内容推理的形式结构推理的形式结构自然推理系统自然推理系统P Pq本章与后续各章的关系本章与后续各章的关系本章是第五章的特殊情况和先行准备本章是第五章的特殊情况和先行准备 3q3.1 3.1 推理的形式结构推理的形式结构q3.2 3.2 自然推理系统自然推理系统P Pq 本章小结本章小结q 习题习题q 作业作业 43.1 推理的形式结构推理的形式结构q数理逻辑的主要任务是数理逻辑的主要任务是用数学的方法来研究数学中的用数学的方法来研究数学中的推理推理。q推理推理是指从前提出发推出结论的思维过程。是指从前提出发推出结论的思维过程。q前提前提是已知命题公式集合。是已知命题公式集合。q结论结论是从前提出发应用推理规则推出的命题公式。是从前提出发应用推理规则推出的命题公式。q证明证明是描述推理正确或错误的过程。是描述推理正确或错误的过程。q要研究推理，首先应该明确什么样的推理是有效的或要研究推理，首先应该明确什么样的推理是有效的或正确的。正确的。5定义定义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 AAk k为假为假;（2 2）或者当）或者当A A1 1AA2 2 AAk k为真时，为真时，B B也为真也为真;则称由前提则称由前提A A1 1,A,A2 2,A,Ak k推出推出B B的的推理是有效的或正确推理是有效的或正确的的，并称，并称B B是是有效结论有效结论。有效推理的定义有效推理的定义 6关于有效推理的说明关于有效推理的说明q A1，A2，Ak由由 推推B的推理记为的推理记为B若推理是正确的，记为若推理是正确的，记为 B若推理是不正确的，记为若推理是不正确的，记为 Bq由前提由前提A1，A2，Ak推结论推结论B的推理是否正确的推理是否正确与诸前提的排列次序无关。与诸前提的排列次序无关。7关于有效推理的说明关于有效推理的说明q设设A A1 1，A A2 2，A Ak k，B B中共出现中共出现n n个命题变项，对于任何个命题变项，对于任何一组赋值一组赋值1 12 2n n(i i=0=0或者或者1 1，i=1,2,i=1,2,n),n)，前提前提和结论的取值情况有以下四种：和结论的取值情况有以下四种：(1)(1)A A1 1AA2 2 AAk k为为0 0，B B为为0 0。(2)(2)A A1 1AA2 2 AAk k为为0 0，B B为为1 1。(3)(3)A A1 1AA2 2 AAk k为为1 1，B B为为0 0。(4)(4)A A1 1AA2 2 AAk k为为1 1，B B为为1 1。q只要不出现只要不出现(3)(3)中的情况，推理就是正确的，因而判断中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现推理是否正确，就是判断是否会出现(3)(3)中的情况。中的情况。q推理正确，并不能保证结论推理正确，并不能保证结论B B一定为真一定为真。8(1)(1)p,pq qp,pq q(2)p,qp q(2)p,qp q 例例3.13.1 判断下列推理是否正确。（真值表法）判断下列推理是否正确。（真值表法）pqp(pq)qp(qp)q000000010101100010111111例题例题正确正确不正确不正确 9定理定理3.13.1 命题公式命题公式A A1 1,A,A2 2,A,Ak k推推B B的推理正确当且仅当的推理正确当且仅当 (A A1 1AA2 2AAk k)B )B 为重言式。为重言式。q该定理是判断推理是否正确的另一种方法。该定理是判断推理是否正确的另一种方法。说说明明有效推理的等价定理有效推理的等价定理 10定理定理3.13.1的证明的证明(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均为真，故它均为真，故它为重言式。为重言式。(2)(2)证明充分性。若蕴涵式证明充分性。若蕴涵式(A A1 1AA2 2AAk k)B)B为重言式，为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，为假的情况，即在任何赋值下，或者即在任何赋值下，或者A A1 1AA2 2AAk k为假，为假，或者或者A A1 1AA2 2AAk k和和B B同时为真，这正符合推理正确的定义。同时为真，这正符合推理正确的定义。11当推理正确时，当推理正确时，q形式（形式（1）记为）记为 B。q形式（形式（2）记为）记为A1 A2 AkB。表示蕴涵式为重言式。表示蕴涵式为重言式。(1)设设=A1,A2,Ak，记为记为 B。(2)A1 A2 AkB(3)前提：前提：A1,A2,Ak 结论：结论：B说说明明推理的形式结构推理的形式结构 12q 真值表法真值表法 q 等值演算法等值演算法 q 主析取范式法主析取范式法判断推理是否正确的方法判断推理是否正确的方法q是否有其他的证明方法？是否有其他的证明方法？思思考考q当命题变项较少时当命题变项较少时,这三种方法比较方便这三种方法比较方便。说说明明 13（1 1）下午马芳或去看电影或去游泳。她没去看电影，所以，她下午马芳或去看电影或去游泳。她没去看电影，所以，她 去游泳了。去游泳了。例例3.23.2 判断下列推理是否正确。（等值演算法）判断下列推理是否正确。（等值演算法）解：设解：设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 q (p pq)q)pp)q q (pppp)(q qp)p)q q (q qp)p)q q 1 1由定理由定理 3.1 3.1可知，可知，推理正确。推理正确。例题例题 14（2 2）若今天是若今天是1 1号，则明天是号，则明天是5 5号。明天是号。明天是5 5号，所以今天是号，所以今天是1 1号。号。例例3.23.2 判断下列推理是否正确。（主析取范式法判断下列推理是否正确。（主析取范式法 ）(pq)qp(p q)qp (p q)q)p q p(pq)(pq)(pq)(p q)m0 m2 m3 主析取范式不含主析取范式不含m m1 1，故故不是重言式（不是重言式（0101是成是成假赋值），所以推理假赋值），所以推理不正确。不正确。解：设解：设p p：今天是今天是1 1号，号，q q：明天是明天是5 5号。号。前提：前提：pq，q 结论：结论：p 推理的形式结构：推理的形式结构：(pq)qp 例题例题 15(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)假言三段论假言三段论(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)破坏性二难破坏性二难 推理定律推理定律-重言蕴含式重言蕴含式 16小节结束小节结束关于推理定律的几点说明关于推理定律的几点说明qA,B,CA,B,C为元语言符号，代表任意的命题公式。为元语言符号，代表任意的命题公式。q若一个推理的形式结构与某条推理定律对应的蕴涵若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。式一致，则不用证明就可断定这个推理是正确的。q2.12.1节给出的节给出的2424个等值式中的每一个都派生出两条推个等值式中的每一个都派生出两条推理定律。例如双重否定律理定律。例如双重否定律A A A A产生两条推理定产生两条推理定律律A A A A和和 A AA A。q由九条推理定律可以产生九条推理规则由九条推理定律可以产生九条推理规则,它们构成了它们构成了推理系统中的推理规则推理系统中的推理规则。173.2 3.2 自然推理系统自然推理系统P Pq判断推理是否正确的三种方法：真值表法、等值演判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。算法和主析取范式法。q当推理中包含的命题变项较多时，上述三种方法演当推理中包含的命题变项较多时，上述三种方法演算量太大。算量太大。q对于由前提对于由前提A A1 1,A,A2 2,A,Ak k推推B B的正确推理应该给出严谨的正确推理应该给出严谨的证明的证明。q证明是一个描述推理过程的命题公式序列，其中的证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。规则得到的结论（中间结论或推理中的结论）。q要构造出严谨的证明就必须在形式系统中进行。要构造出严谨的证明就必须在形式系统中进行。18形式系统的定义形式系统的定义定义定义3.23.2 一个一个形式系统形式系统I由下面四个部分组成：由下面四个部分组成：（1 1）非空的字母表，记作）非空的字母表，记作A(I)。（2 2）A(I)中符号构造的合式公式集，记作中符号构造的合式公式集，记作E(I)。（3 3）E(I)中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作AX(I)。（4 4）推理规则集，记作推理规则集，记作R(I)。可以将可以将I记为记为4 4元组元组 是是I的的形式语言系统形式语言系统 是是I的的形式演算系统形式演算系统 19形式系统的分类形式系统的分类（1 1）自然推理系统自然推理系统从任意给定的前提出发，应用系统中的推理规则进从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论）。（有时称为有效的结论）。（2 2）公理系统公理系统从若干给定的公理出发，应用系统中推理规则进行从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的定理。推理演算，得到的结论是系统中的定理。q本书只介绍自然推理系统本书只介绍自然推理系统P P。说说明明 20自然推理系统的定义自然推理系统的定义定义定义3.33.3 自然推理系统自然推理系统P P的定义的定义1.1.字母表字母表（1 1）命题变项符号：命题变项符号：p，q，r，pi，qi，ri，（2 2）联结词符号：联结词符号：，（3 3）括号与逗号：括号与逗号：()，2.2.合式公式（同定义合式公式（同定义1.61.6）21自然推理系统的定义自然推理系统的定义3.3.推理规则推理规则（1 1）前提引入规则）前提引入规则 在证明的任何步骤上都可以引入前提。在证明的任何步骤上都可以引入前提。（2 2）结论引入规则）结论引入规则 在证明的任何步骤上所得到的结论都可以作为在证明的任何步骤上所得到的结论都可以作为后继证明的前提。后继证明的前提。（3 3）置换规则）置换规则 在证明的任何步骤上，命题公式中的子公式都在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又可以用与之等值的公式置换，得到公式序列中的又一个公式。一个公式。22自然推理系统的定义自然推理系统的定义（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 6）现在气温在冰点以下并）现在气温在冰点以下并且正在下雨。因此，现在且正在下雨。因此，现在气温在冰点以下。气温在冰点以下。23自然推理系统的定义自然推理系统的定义（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 24自然推理系统的定义自然推理系统的定义（1010）构造性二难推理规则）构造性二难推理规则 A AB B C CD D A A C C B B D D （1111）破坏性二难推理规则）破坏性二难推理规则 A AB B C CD D B BD D A AC C（1212）合取引入规则合取引入规则 A A B B A A B B 25在自然推理系统在自然推理系统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证明方法：证明方法：直接证明法直接证明法 附加前提法附加前提法归谬法（或称反证法）归谬法（或称反证法）26例题例题例例3.33.3 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：前提：前提：pq,rq,rs pq,rq,rs 结论：结论：ps ps pqpq 前提引入前提引入 pq pq 置换置换 rqrq 前提引入前提引入 qr qr 置换置换 pr pr 假言三段论假言三段论 rs rs 前提引入前提引入 ps ps 假言三段论假言三段论 27例题例题例例3.33.3 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：前提：前提：pp（qrqr）,p,pq q 结论：结论：rs rs pp（qrqr）前提引入前提引入 p pq q 前提引入前提引入 p p 化简化简 q q 化简化简 qrqr 假言推理假言推理 r r 假言推理假言推理 rsrs 附加附加 rsrs置换置换 28例题例题例例3.43.4 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：若数若数a a是实数，则它不是有理数就是无理数；若是实数，则它不是有理数就是无理数；若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 29 ps ps 前提引入前提引入 p p 化简化简 s s 化简化简 p(qr)p(qr)前提引入前提引入 qr qr 假言推理假言推理 sqsq 前提引入前提引入 q q 假言推理假言推理 r r 析取三段论析取三段论 例题例题 30附加前提法附加前提法q有时推理的形式结构具有如下形式有时推理的形式结构具有如下形式 ：前提：前提：A1,A2,Ak 结论：结论：CBq可将结论中的前件也作为推理的前提，使结论只为可将结论中的前件也作为推理的前提，使结论只为B B。前提：前提：A1,A2,Ak,C 结论：结论：Bq理由：理由：(A A1 1 A A2 2 A Ak k)(C CB B)(A A1 1 A A2 2 A Ak k)(C C B B)(A A1 1 A A2 2 A Ak k C C)B B (A A1 1 A A2 2 A Ak k C C)B B 31例题例题例例3.53.5 在自然推理系统在自然推理系统P P中构造下面推理的证明。中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。看电影时，小李也去看电影。构造证明：构造证明：（1 1）将简单命题符号化：）将简单命题符号化：设设 p:p:小张去看电影。小张去看电影。q:q:小王去看电影。小王去看电影。r:r:小李去看电影。小李去看电影。s:s:小赵去看电影。小赵去看电影。32例题例题（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 假言推理假言推理 33归谬法（反证法）归谬法（反证法）q 有时推理的形式结构具有如下形式：有时推理的形式结构具有如下形式：前提：前提：A A1 1,A A2 2,A Ak k 结论：结论：B Bq 如果将如果将B B作为前提能推出矛盾来，则说明推理正确。作为前提能推出矛盾来，则说明推理正确。前提：前提：A A1 1,A A2 2,A Ak k,B B 结论：矛盾结论：矛盾q 理由：理由：A A1 1 A A2 2 A Ak kB B (A A1 1 A A2 2 A Ak k)B B (A A1 1 A A2 2 A Ak kB B)q若若A A1 1 A A2 2 A Ak kB B为矛盾式，则说明为矛盾式，则说明(A A1 1 A A2 2 A Ak kB B)为重言式。为重言式。34例题例题例例3.63.6 在自然推理系统在自然推理系统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队获得联赛第一名。队获得联赛第一名。（2 2）形式结构：）形式结构：前提：前提：(pq)r,rs,s,p pq)r,rs,s,p 结论：结论：q q 35例题例题（3 3）证明：用归谬法）证明：用归谬法 q q 结论的否定引入结论的否定引入 rs rs 前提引入前提引入 s s 前提引入前提引入 r r 析取三段论析取三段论 (pq)r pq)r 前提引人前提引人 (pq)pq)拒取式拒取式 pq pq 置换置换 p p 前提引入前提引入 q q 析取三段论析取三段论 qqqq 合取合取 由于最后一步为矛盾式，所以推理正确。由于最后一步为矛盾式，所以推理正确。小节结束小节结束 36本章主要内容本章主要内容q 推理的形式结构：推理的形式结构：推理的前提推理的前提推理的结论推理的结论推理正确推理正确q 判断推理是否正确的方法：判断推理是否正确的方法：真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法 q 对于正确的推理，在自然推理系统对于正确的推理，在自然推理系统P P中构造证明中构造证明:自然推理系统自然推理系统P P的定义的定义自然推理系统自然推理系统P P的推理规则：的推理规则：附加前提证明法附加前提证明法归谬法归谬法 37本章学习要求本章学习要求q 理解并记住推理的形式结构的三种等价形式，即理解并记住推理的形式结构的三种等价形式，即A1,A2,AkBA1A2AkB前提：前提：A1,A2,Ak 结论：结论：B在判断推理是否正确时，用；在在判断推理是否正确时，用；在P系统中构造证明时用。系统中构造证明时用。q 熟练掌握判断推理是否正确的三种方法（真值表法，等值演算熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。法，主析取范式法）。q 牢记牢记P系统中的各条推理规则。系统中的各条推理规则。q 对于给定的正确推理，要求在对于给定的正确推理，要求在P系统中给出严谨的证明序列。系统中给出严谨的证明序列。q 会用附加前提证明法和归谬法。会用附加前提证明法和归谬法。小节结束小节结束 38习题习题1、用不同的方法验证下面推理是否正确。对于正确的推理还、用不同的方法验证下面推理是否正确。对于正确的推理还要在要在P系统中给出证明。系统中给出证明。（1）前提：前提：pq,q 结论：结论：p（2）前提：前提：qr,pr 结论：结论：qp 39（1）不正确。）不正确。验证答案，只需证明验证答案，只需证明(pq)qp不是重言式。不是重言式。方法一方法一 等值演算等值演算 (pq)qp (p q)q)p(pq)qp(p q)(q q)p p q易知易知10是成假赋值，故是成假赋值，故(pq)qp不是重言式，所以不是重言式，所以推理不正确。推理不正确。40方法二方法二 主析取范式法主析取范式法经过演算后可知经过演算后可知(pq)qp m0 m1 m3 未含未含m2,故故(pq)qp不是重言式。不是重言式。方法三方法三 直接观察出直接观察出10是成假赋值。是成假赋值。41方法四方法四 真值表法真值表法(pq)qp的真值表为的真值表为pq(pq)qp001101010111结论（不正确）是对的。结论（不正确）是对的。42（2）推理正确）推理正确方法一方法一 真值表法（自己做）真值表法（自己做）方法二方法二 等值演算法（自己做）等值演算法（自己做）方法三方法三 主析取范式法（自己做）主析取范式法（自己做）方法四方法四 P系统中构造证明系统中构造证明证明：证明：（直接证明法）（直接证明法）pr （前提引入）前提引入）rp （置换）置换）qr （前提引入）前提引入）qp （假言三段论）假言三段论）432、在、在P系统中构造下面推理的证明：系统中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩。如果今天是周六，我们就到颐和园或圆明园玩。如如果颐和园游人太多，就不去颐和园。果颐和园游人太多，就不去颐和园。今天是周六，并且今天是周六，并且颐和园游人太多。颐和园游人太多。所以我们去圆明园或动物园玩。所以我们去圆明园或动物园玩。构造证明：构造证明：（1）设设p：今天是周六。今天是周六。q：到颐和园玩。到颐和园玩。r：到圆明园玩。到圆明园玩。s：颐和园游人太多。颐和园游人太多。t：到动物园玩。到动物园玩。（2）前提：）前提：p(q r),sq,p,s 结论：结论：r t 44（3）证明：证明：p(q r)前提引入前提引入 p 前提引入前提引入 q r 假言推理假言推理 sq 前提引入前提引入 s 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论 r t 附加附加小节结束小节结束 45homeworkhomeworkq习题三：习题三：6(1,2,3)、14(1,2)、15(1)、16(1)、17)