交大数理逻辑课件2-3 命题逻辑的等值和推理演算.ppt

《交大数理逻辑课件2-3 命题逻辑的等值和推理演算.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件2-3 命题逻辑的等值和推理演算.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 命题逻辑的等值和推理演算 2.1 等值定理2.2 等值公式2.3 命题公式与真值表的关系2.4 联结词的完备集2.5 对偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 归结推理法讨论讨论等值演算等值演算讨论讨论推理演算推理演算2.7 推理形式n推理引例:(1)正项级数收敛当且仅当部分和有上界正项级数收敛当且仅当部分和有上界.(2)若若A C B D，则，则A B且且C D.n数理逻辑的主要任务是用逻辑的方法研究数学中的推理。n推理从从前前提提出出发发，应应用用推推理理规规则则推推出出结结论论的的思维过程思维过程n上面上面(1)是正确的推理，而是正确的推理

2、，而(2)是错误的推理是错误的推理.n推理的组成n前提前提推理所根据的已知命题推理所根据的已知命题n结论结论从前提出发通过推理而得到的新命题从前提出发通过推理而得到的新命题n证明描述推理正确或错误的过程描述推理正确或错误的过程.推理形式n例：如果我有时间，那么我就去上街；如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；如果我上街，那么我就去书店买书；但我没有去书店买书，但我没有去书店买书，所以我没有时间。所以我没有时间。n 解：令 P：我有时间。Q：我去上街。R：我去书店买书。根据题意，前提为：PQ，QR，R 结论为：P 推理的形式为：(PQ)(QR)R P 反映了一类推理关系反

3、映了一类推理关系重言蕴涵n定义定义n若（若（A1 A2 Ak）B为重言式，则称为重言式，则称n由由A1,A2,Ak推出结论推出结论B的的推理正确（有效结论）推理正确（有效结论）n否则否则推理不正确（错误）推理不正确（错误）.n“A1,A2,Ak 推出B”的推理正确 当且仅当 A1 A2 AkB为重言式.n推理的形式结构推理的形式结构nA1 A2 AkB 或或n前提：前提：A1,A2,Ak结论结论：Bn若推理正确，则记作：若推理正确，则记作：A1 A2 Ak B例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。解题方法将命题符号化将命题符号化写出前提、结论和推

4、理的形式结构写出前提、结论和推理的形式结构进行判断进行判断解：设 P：天气凉快，Q：小王去游泳.前提：P Q，P 结论：Q 推理的形式结构为：(PQ)P)Q 判断上式是否为重言式 例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断 (PQ)P)Q 是否为重言式 方法1：真值表法PQP Q(P Q)P(P Q)P)QFFTFTFTTFTTFTTTTTFFT(PQ)P)Q例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断(PQ)P)Q 是否为重言式 方法2：等值演算法(PQ)P)Q=(PQ)P)Q=(P Q)PQ =(

5、P Q)(P Q)=T(PQ)P)Q例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断(PQ)P)Q是否为重言式 方法3：主析取范式法(PQ)P)Q=(PQ)P)Q=(P Q)PQ=m11 m0 x mx0=m11 m00 m01 m00 m10 =(0,1,2,3)=T(PQ)P)Q例：判断下面推理是否正确（2）若我上街，我一定去新华书店。我没上街，所以我没去新华书店。解：设 P：我上街，Q：我去新华书店.前提：PQ，P 结论：Q 推理的形式结构为：(PQ)P)Q 判断上式是否为重言式 (PQ)P)Q=(P Q)P)Q=(P Q)P Q=m10 m1x

6、 mx0=m10 m10 m11 m00 m10 =(0,2,3)不是重言式！不是重言式！所以推理不正确所以推理不正确重言蕴涵的几个结果n如果A B，A为重言式，则B也是重言式n如果A B，B A同时成立，必有A=Bn反之，如果反之，如果A=B，必有，必有A B，B An如果A B，B C，则A Cn如果A B，A C，则A B Cn如果A C，B C，则ABB C2.8 基本的推理公式n判断推理是否正确的方法n真值表法、等值演算法、主析取范式法真值表法、等值演算法、主析取范式法n推理演算法推理演算法一个描述推理过程的命题公式序列一个描述推理过程的命题公式序列n其中的每个命题公式是已知的前提、

7、或是由某些前其中的每个命题公式是已知的前提、或是由某些前提依据提依据等值公式等值公式或或蕴涵关系式蕴涵关系式、应用、应用推理规则推理规则得到得到的结论的结论 n说明：说明：n当命题变项比较少时，用前当命题变项比较少时，用前3 3个方法比较方便个方法比较方便,此时采此时采用用形式结构形式结构“A1 A2 AkB”.n而在推理演算时，而在推理演算时，采用下面形式：采用下面形式：前提前提:A1,A2,Ak,结论结论:B基本的推理公式1.P QP化简律化简律2.2.(PQ)P3.3.(PQ)Q4.P P Q附加律附加律5.5.PPQ6.QPQ7.P(P Q)Q 析取三段论析取三段论8.P (PQ)Q假

8、言推理假言推理9.9.Q(PQ)P拒取式拒取式基本的推理公式10.(PQ)(QR)PR假言三段论假言三段论11.(PQ)(QR)P R等价三段论等价三段论12.(PR)(QR)(P Q)R13.13.(PQ)(RS)(P R)Q S构造性二难构造性二难14.(PQ)(RS)(QS)(PR)破坏性二难破坏性二难15.(QR)(P Q)(P R)16.(QR)(PQ)(PR)证明推理公式的方法n定理2.8.1 ABB成立的充分必要条件是成立的充分必要条件是AB 是重言式。是重言式。n定理2.8.2 ABB成立的充分必要条件是成立的充分必要条件是A B 是矛盾式是矛盾式。n(AB)=(A B)=A

9、B n说明：n可用可用AB 是重言式是重言式或或A B 是矛盾式是矛盾式来来证明推理公式证明推理公式ABB2.9 推理演算推理规则 (1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)假言推理假言推理(分离规分离规则则)PQ P Q(5)附加规则附加规则PP Q(6)化简规则化简规则 P Q P(7)拒取式规则拒取式规则 PQ QP(8)假言三段论规则假言三段论规则PQQRPR推理规则(续)(11)破破坏坏性性二二难难推推理理规则规则PQRS QSPR(12)合取引入规则合取引入规则PQP Q(9)析取三段论规则析取三段论规则P Q QP(10)构构造造性性

10、二二难难推推理理规规则则PQRSP RQ S使用推理规则的推理演算举例例1：证明：前提：前提：P Q,Q R,P 结论：结论：R 证：(1)P 前提引入前提引入 (2)P Q 前提引入前提引入(3)Q (1)(2)分离（假言推理）分离（假言推理）(4)Q R 前提引入前提引入(5)R (3)(4)分离（假言推理）分离（假言推理）推理演算直接证明法例2 证明：前提：前提：P Q，P R,Q S 结论：结论：S R证明：证明：(1)P Q 前提引入前提引入 (2)P Q (1)置换置换 (3)Q S 前提引入前提引入 (4)P S (2)(3)假言三段论假言三段论 (5)S P (4)置换置换 (

11、6)P R 前提引入前提引入 (7)S R (5)(6)假言三段论假言三段论 (8)S R (7)置换置换(PQ)()(RS)()(P R)Q S 构造性二难构造性二难 在大城市球赛中，在大城市球赛中，如果北京队第三，那么如果上海队第如果北京队第三，那么如果上海队第二，则天津队第四；沈阳队不是第一或北京队第三，上海队第二，则天津队第四；沈阳队不是第一或北京队第三，上海队第二。从而知：如果沈阳队第一，那么天津队第四。二。从而知：如果沈阳队第一，那么天津队第四。解：设 P：北京队第三：北京队第三 Q：上海队第二：上海队第二 R：天津队第四：天津队第四 S：沈阳队第一：沈阳队第一 前提：前提：P(Q

12、R)，SP,Q 结论：结论：S R写出对应下面推理的证明 (1)P(Q R)前提前提(2)Q(P R)(1)置换置换(3)Q 前提前提(4)P R (2)(3)假言推假言推理理(5)SP 前提前提(6)S P (5)置换置换(7)S R (6)(4)析取三段析取三段论论推理演算附加前提证明法 欲证明欲证明前提：前提：A1,A2,Ak结论：结论：CB等价地证明等价地证明前提：前提：A1,A2,Ak,C结论：结论：B理由：理由：(A1 A2 Ak)(CB)=(A1 A2 Ak)(C B)=(A1 A2 Ak)C)B=(A1 A2 Ak C)B=(A1 A2 Ak C)B例如：证明下列推理。前提：P

13、(QR)，SP,Q 结论：S R证明：证明：(1)S P 前提前提 (2)S 附加前提引入附加前提引入 (3)P (1)(2)析取三段析取三段论论 (4)P(Q R)前提前提 (5)Q R (3)(4)假言推理假言推理 (6)Q 前提前提 (7)R (5)(6)假言推理假言推理附加前提证明法 举例2.10 归结推理法（反证法）欲证明欲证明前提：前提：A1,A2,Ak结论：结论：B将将 B加入前提，若推出矛盾，则得证推理正确加入前提，若推出矛盾，则得证推理正确.理由理由:A1 A2 AkB=(A1 A2 Ak)B =(A1 A2 Ak)(B)=(A1 A2 AkB)括号内部为矛盾式当且仅当括号内

14、部为矛盾式当且仅当 (A A1 1 A A2 2 A Ak k B B )为为重言式重言式 证明AB是重言式的归结证明过程n建立子句集Sn将将AB化成合取范式，如化成合取范式，如 P (P R)(PQ)(P R)的形式，进而将所有句子构成子句集合：的形式，进而将所有句子构成子句集合：S=P，(P R)，(PR)，(P R)n对S作归结n对对S的子句消去的子句消去互补对互补对：子句：子句：P R，P Q 作归结，得作归结，得归结式：归结式：R Q 并将此归结式仍放入并将此归结式仍放入S中，重复此过程中，重复此过程n直至归结出矛盾式，证明结束归结推理法 举例例例构造下面推理的证明构造下面推理的证明

15、 前提：(P Q)R,RS,S,P结论结论：Q证明：证明：Q 结论否定引入RS前提引入前提引入 R S 置换置换 S前提引入前提引入 R归结归结 (P Q)R前提引入前提引入 (P Q)归结归结 PQ置换置换 P归结归结 P前提引入前提引入 归结归结作业4P38:7(1)(7)(15)P38:8(1)(6)P38:9(2)P39:12(1)有关命题逻辑的思考题n有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两今有两门，一为自由，一为死亡，你可任意开启门，一为自由，一为死亡，你可任意开启一门。为协助你脱逃，今派两名战士负责一门。为协助你脱逃，今派两名战士负责解答你所提出的任何问题。惟可虑者，此解答你所提出的任何问题。惟可虑者，此两战士中一名天性诚实，一名说慌成性，两战士中一名天性诚实，一名说慌成性，今后生死由你自己选择。今后生死由你自己选择。”逻辑学家深思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？