01命题逻辑04(证明方法)

《01命题逻辑04(证明方法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一部分数理逻辑MathematicalLogic1.4命题逻辑的推理理论内容：命题公式的蕴涵式基本蕴涵式直接证明法间接证明法反证法/归谬法目标：熟记基本蕴涵式熟练利用上述各种证明法论证任意推理的有效性命题逻辑的蕴涵式例1.符号化下列命题并确定真值1.如果自然数N是偶数，那么N+1也是偶数。2.如果2是偶数，那么3也是偶数。3.如果4能够整除整数K，那么2也能整除K。例题解（1）1.如果自然数N是偶数，那么N+1也是偶数。解：设p：自然数N是偶数。q：N+1是偶数。命题符号化为：p→q此命题的真值根据N的

2、取值确定。pqp→q011100例题解（2）2.如果2是偶数，那么3也是偶数。解：设p：2是偶数。q：3是偶数。命题符号化为：p→q因为p为真命题，q为假命题，所以此命题为永假命题pqp→q100例题解（3）3.如果4能够整除整数K，那么2也能整除K。解：设p：4能够整除整数K。q：2也能整除K。命题符号化为：p→q此命题为永真命题。即有p⇒qpqp→q001011111命题公式的关系逻辑等值（logicallyequivalent）AB设A、B是公式，如果在任意解释Ｉ下，AB是重言式，则称公式A、B

3、是等值的。逻辑蕴涵（logicallyimply）AB设A、B是公式，如果在任意解释Ｉ下，A→B是重言式，则称公式A逻辑蕴涵B。基本蕴涵式(1)化简律：AB=>A,AB=>B(2)附加律：A=>AB,B=>AB(3)假言推理：A(AB)=>B(4)拒取式：(AB)B=>A(5)析取三段论：(AB)B=>A(6)假言三段论：(AB)(BC)=>AC(7)等价三段论：(A↔B)(B↔C)=>A↔C(8)二难推理：(AC)(AB)(CB)=>B(9)构造性二难：(A

4、B)(CD)(AC)=>BD(10)破坏性二难：(AB)(CD)(BD)=>AC逻辑推理1.如果下雨，则菜价会上涨。菜价上涨了，因此下了雨。2.如果丽莎今年工作表现好，她会得到奖金。如果她得到奖金，她会去度假。如果她去度假，她会去航海。丽莎没有去航海，因此她没有得到奖金。3.如果我的办公桌上有支票簿，则说明我已经付过电话费。我在吃早饭时查看电话账单或在办公室查看电话账单。如果在早餐时查看电话账单，则支票簿在早餐桌上，说明我没有付电话费。如果我在办公室查看电话账单，则支票簿在

5、我的办公桌上，支票簿到底在哪里？推理的形式结构有限命题序列A1,A2,…Ak,B称为推理（或论证（argument））。A1,A2,…Ak称为推理的前提（premise），B称为推理的结论（conclusion）。当且仅当A1∧A2∧…∧Ak→B为重言式时，称由前提A1,A2,…Ak推出B的推理是有效的（或正确的），并称B是该前提的有效结论。形式结构记为：A1∧A2∧…∧Ak=>B或为{A1,A2,…,Ak}

6、-B。重言式的证明方法真值表法等值演算法主析取范式法形式演算系统（1）自然推理系统----从任意

7、给定的前提出发，应用系统中的推理规则进行推理演算，得到的公式是推理的结论。（2）公理推理系统----只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为定理。推理证明1.如果下雨，则菜价会上涨。菜价上涨了，因此下了雨。证明：设p:下雨。q:菜价上涨。推理形式化：p→q,q⇒p((p→q)∧q)→p⇔((p∨q)∧q)∨p⇔(p∨q)∨q∨p⇔(p∧q)∨q∨p⇔q∨p—非重言式推理证明2.如果丽莎今年工作表现好，她会得到奖金。如果她得到奖金，她会去度假

8、。如果她去度假，她会去航海。丽莎没有去航海，因此她没有得到奖金。证明：设p:丽莎工作表现好。q：丽莎得到了奖金。r：丽莎去度假。s：丽莎去航海。推理的形式化为：p→q,q→r,r→s,s⇒q自然推理系统定义3.2一个形式系统I记为:由下面四个部分组成：(1)非空的字符表集，记作A(I)。(2)A(I)中符号构造的合式公式集，记作E(I)。(3)E(I)中一些特殊的公式组成的公理集，记作AX(I)。(4)推理规则集，记作R(I)。定义3.3自然推理系统P定义1

9、．字母表（1）命题变项符号：p，q，r，…,pi，qi，ri，…（2）联结词符号：┐,∧,∨,→,（3）括号和逗号：(,)，，2．合式公式同前面定义3．推理规则（1）前提引入规则：在证明的任何步骤上都可以引入前提。（2）结论引入规则：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。（3）置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。定义3.3自然推理系统P定义