《命题逻辑(证明方法)》由会员分享，可在线阅读，更多相关《命题逻辑(证明方法)（30页珍藏版）》请在金锄头文库上搜索。
1、Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学第一部分 数理逻辑Mathematical LogicDiscrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学1.4命题逻辑的推理理论 内容： 命题公式的蕴涵式 基本蕴涵式直接证明法间接证明法反证法/归谬法 目标：熟记基本蕴涵式熟练利用上述各种证明法论证任意推理的 有效性 Discrete MathematicsHarbin Engineering University CST
2、哈尔滨工程大学校级精品课离散数学命题逻辑的蕴涵式例1.符号化下列命题并确定真值1.如果自然数N是偶数，那么N+1也是偶数。 2.如果2是偶数，那么3也是偶数。 3.如果4能够整除整数K，那么2也能整除K。Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学例题解（1）1.如果自然数N是偶数，那么N+1也是偶数。 解：设 p：自然数N是偶数。 q： N+1是偶 数。命题符号化为：p q 此命题的真值根据N的取值确定。pqpq011100Discrete MathematicsHarbin Engineering
3、 University CST哈尔滨工程大学校级精品课离散数学例题解（2）2.如果2是偶数，那么3也是偶数。 解：设p：2是偶数。 q：3是偶数。命题符号化为：p q 因为p为真命题，q为假命题，所以此命 题为永假命题 pqpq100Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学例题解（3）3.如果4能够整除整数K，那么2也能整除K。 解：设 p：4能够整除整数K。q： 2也能整除K。命题符号化为：p q 此命题为永真命题。即有 p q pqpq001011111Discrete Mathematics
4、Harbin Engineering University CST哈尔滨工程大学校级精品课离散数学命题公式的关系 逻辑等值（logically equivalent） AB设A、B是公式，如果在任意解释下 ，AB是重言式，则称公式A、B是等值 的。 逻辑蕴涵（logically imply） A B设A、B是公式，如果在任意解释下 ，A B是重言式，则称公式A逻辑蕴涵B 。 Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学基本蕴涵式(1)化简律：AB=A, AB = B (2)附加律：A = AB, B
5、= AB (3)假言推理： A ( AB) = B (4)拒取式：(AB)B = A (5)析取三段论：(AB) B = A (6)假言三段论：(AB) (BC) = AC (7)等价三段论： (AB) (B C) = AC (8)二难推理： (AC)(AB)(CB) = B (9)构造性二难： (AB)(CD)(AC) = BD (10)破坏性二难： (AB)(CD)(BD) = ACDiscrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学逻辑推理1.如果下雨，则菜价会上涨。菜价上涨了，因此下 了雨。 2.如果
6、丽莎今年工作表现好，她会得到奖金。如果 她得到奖金，她会去度假。如果她去度假，她会 去航海。丽莎没有去航海，因此她没有得到奖金 。 3.如果我的办公桌上有支票簿，则说明我已经付过 电话费。我在吃早饭时查看电话账单或在办公室 查看电话账单。如果在早餐时查看电话账单，则 支票簿在早餐桌上，说明我没有付电话费。如果 我在办公室查看电话账单，则支票簿在我的办公 桌上，支票簿到底在哪里？Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学推理的形式结构 有限命题序列A1,A2,Ak,B称为推理（或论证（ argumen
7、t）。A1,A2,Ak称为推理的前提（ premise），B称为推理的结论（conclusion）。 当且仅当A1A2Ak B为重言式时，称由 前提A1, A2, Ak推出B的推理是有效的（或正确 的），并称B是该前提的有效结论。 形式结构记为： A1 A2 Ak =B或为 A1 ,A2 , ,Ak|- B。Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学重言式的证明方法 真值表法 等值演算法 主析取范式法 形式演算系统 （1）自然推理系统-从任意给定的前提出 发，应用系统中的推理规则进行推理演算 ，得到
8、的公式是推理的结论。 （2）公理推理系统-只能从若干给定的公 理出发，应用系统中推理规则进行推理演 算，得到的结论是系统中的重言式，称为 定理。Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学推理证明1.如果下雨，则菜价会上涨。菜价上涨了， 因此下了雨。 证明：设 p: 下雨。q: 菜价上涨。推理形式化：pq, q p(pq)q) p(pq)q)p(pq) qp(p q) qpqp非重言式Discrete MathematicsHarbin Engineering University CST哈尔滨工程大
9、学校级精品课离散数学推理证明2.如果丽莎今年工作表现好，她会得到奖金 。如果她得到奖金，她会去度假。如果她 去度假，她会去航海。丽莎没有去航海， 因此她没有得到奖金。 证明：设 p:丽莎工作表现好。q：丽莎得到 了奖金。r：丽莎去度假。s：丽莎去航海 。 推理的形式化为：pq, qr, rs, s qDiscrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学自然推理系统定义3.2 一个形式系统 I 记为:由下面四个部分组成： (1)非空的字符表集，记作A(I)。 (2)A(I)中符号构造的合式公式集，记作E(I)
10、。 (3)E(I)中一些特殊的公式组成的公理集，记 作AX(I)。 (4)推理规则集，记作R(I)。Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学定义3.3 自然推理系统P定义 1字母表 （1） 命题变项符号：p，q，r，,pi，qi，ri， （2） 联结词符号：, （3） 括号和逗号：( , )， 2合式公式 同前面定义 3推理规则 （1）前提引入规则：在证明的任何步骤上都可以 引入前提。 （2）结论引入规则：在证明的任何步骤上所得到 的结论都可以作为后继证明的前提。 （3）置换规则：在证明的任何步骤
11、上，命题公式 中的子公式都可以用与之等值的公式置换，得到 公式序列中的又一个公式。Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学定义3.3 自然推理系统P定义（续）（4） 假言推理规则（或称分离规则）：若证明的 公式序列中已出现过AB和A，则由假言推理定 律(AB)A=B可知，B是AB和A的有效结论 。由结论引入规则可知，可将B引入到命题序列 中来。用图式表示为如下形式：Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散
12、数学定义3.3 自然推理系统P定义（续）（5） 附加规则： （6） 化简规则： Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学定义3.3 自然推理系统P定义（续）（7） 拒取式规则： （8） 假言三段论规则： Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学定义3.3 自然推理系统P定义（续）（9） 析取三段论规则： （10） 构造性二难推理： Discrete MathematicsHarbin Engineer
13、ing University CST哈尔滨工程大学校级精品课离散数学定义3.3 自然推理系统P定义（续）（11）合取引入规则： （12）破坏性二难推理规则： Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学自然推理系统例2 ：设 p:丽莎工作表现好。q：丽莎得到了 奖金。r：丽莎去度假。s：丽莎去航海。 推理的形式化为：pq, qr, rs, s q 证明： qr 前提引入 rs 前提引入 qs 假言三段论 s 前提引入 q 拒取式Discrete MathematicsHarbin Engineerin
14、g University CST哈尔滨工程大学校级精品课离散数学证明推理的有效性例4 ：如果丽莎有天赋且努力工作，在可以找到好 工作。如果她找到好工作，则她会幸福。因此， 如果她不幸福，那么她没有努力工作或她没有天 赋。 证明：设 p:丽莎有天赋。q：丽莎努力工作。r：丽 莎找到好工作。s：丽莎幸福。 则推理的形式化为：(pq) r, rs, s p q s 前提引入 rs 前提引入 r 拒取式 (pq) r 前提引入 (pq) 拒取式 p q 置换规则 Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学证明技术 直接证明法（direct proof） （A1A2Ak ) B 1 间接证明法（indirect proof） (A1A2Ak ) (A B) (A1A2Ak A ) B 1 反证法/归谬法（proof by contradiction） 1(A1A2Ak) B (A1A2Ak B) (A1A2Ak B) 0Discrete MathematicsHarbin Engineering University CST哈尔滨工程大学校级精品课离散数学间接证明法例：pq, rq ,rs = ps p 附加前提
