《离散数学》课程教学课件（PPT讲稿）03 命题逻辑的推理理论

命题逻辑的推理理论

析取范式与合取范式 命题逻辑的推理理论

推理的形式结构定义3.1 设A1,A2,…,Ak,B为命题公式,若对于每一组赋值,AiA^..人Ak为假，或当AA人..A为真时，B也为真，则称由前提A1,A2,A,推出结论B的推理是有效的或正确的，并称B是有效结论。定理3.1由命题公式A1,A2,，Ak推出B的推理正确当且仅当A1A2^...ΛAk→B为重言式注意：推理正确不能保证结论一定正确，因为前提有可能不成立

1 推理的形式结构 定义3.1 设A1 , A2 , ., Ak , B为命题公式. 若对于每一组赋值， A1A2. Ak 为假，或当A1A2.Ak为真时，B也为真， 则称由前提A1 , A2 , ., Ak推出结论B的推理是有效的或正确 的, 并称B是有效结论. 定理3.1由命题公式A1 , A2 , ., Ak 推出B的推理正确当且仅当 A1A2.Ak→B为重言式 注意: 推理正确不能保证结论一定正确，因为前提有可能不 成立

推理的形式结构推理的形式结构1. [A, A2,., A}B若推理正确,记为[A1,A2….,A,}二B2. A1M2^...Ak→>B若推理正确,记为A^A,^.^A=B3.前提：A1,A2,,Ak结论：B对应蕴含式为重言式每个等值式可产生两个推理判断推理是否正确的方法：定律真值表法如，由A一一A可产生A二一一A和→→A=A等值演算法主析取范式法2

2 推理的形式结构 判断推理是否正确的方法: ◆ 真值表法 ◆ 等值演算法 ◆ 主析取范式法 推理的形式结构 1. {A1 , A2 , ., Ak } B 若推理正确, 记为{A1 ,A2 ,,An } B 2. A1A2.Ak→B 若推理正确, 记为A1  A2  .  Ak  B 3. 前提： A1 , A2 , . , Ak 结论： B • 对应蕴含式为重言式 • 每个等值式可产生两个推理 定律 如, 由AA可产生 AA 和 AA

推理实例例题判断下面推理是否正确若a能被4整除则a能被2整除，a能被4整除，所以a能被2整除，解设p：a能被4整除，q：a能被2整除推理的形式结构： (p→q)^p→q用等值演算法(p>q)p>q-((-pvg)ap)vg蕴含等值式←pv-qvq←1分配律、德摩根律推理正确3

3 推理实例 例题 判断下面推理是否正确 ① 若a能被4整除,则a能被2整除. a能被4整除. 所以a能被2整除. 解 设 p：a能被4整除，q：a能被2整除. 推理的形式结构: (p→q)p→q 用等值演算法 (p→q)p→q  ((pq)p)q  pqq  1 分配律、德摩根律 蕴含等值式 推理正确

推理实例例题判断下面推理是香正确若a能被4整除,则a能被2整除.a能被2整除，所以a能被4整除，解设p：a能被4整除，：a能被2整除.(p→>q)^q→p推理的形式结构：用主析取范式法(p→>q)^q→p (-pvq)^qp((-pvq)q)p←qvp吸收律AV（AΛB)AAΛ（AVB)台A←Mmvm2vm34推理不正确

4 推理实例 例题 判断下面推理是否正确 ② 若a能被4整除,则a能被2整除. a能被2整除. 所以a能被4整除. 解 设 p：a能被4整除，q：a能被2整除. 推理的形式结构: (p→q)q→p 用主析取范式法 (p→q)q→p  (pq)q→p   ((pq)q)p  qp M1  m0m2m3 推理不正确

形式系统定义3.2一个形式系统由下面四个部分组成：(1)）非空的字母表，记作A()(2) A(I) 中符号构造的合式公式集，记作E(I),(3)E(I)中一些特殊的公式组成的公理集，记作Ax(I)(4)推理规则集，记作R(U)记/=,其中是/ 的形式语言系统,是 / 的形式演算系统,自然推理系统：无公理集,即Ax(I)=の公理推理系统：有公理集，推出的结论是系统中的童式，称作定理5

5 形式系统 定义3.2 一个形式系统I 由下面四个部分组成： (1) 非空的字母表，记作A(I). (2) A(I) 中符号构造的合式公式集，记作E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作AX (I). (4) 推理规则集，记作R(I). 记I=, 其中是I 的形式语言 系统, 是 I 的形式演算系统. 自然推理系统: 无公理集, 即AX (I)= 公理推理系统: 有公理集, 推出的结论是系统中的重言式, 称 作定理

自然推理系统定义3.3自然推理系统P定义如下：1.字母表(1)命题变项符号：p,q, r,, Pi,qi, r,….(2) 1联结词符号：一,^,V,一→,←(3)括号与退号：（),，2.合式公式（同定义1.6）3.推理规则例如以下基本推理规则(1) 前提引入规则：在证明的任何步骤可以引入前提(2) 结论引入规则：在证明的任何步骤得到的结论可作为后继证明的前提(3) 置换规则：在证明的任何步骤，命题公式中的子公式可用等值的公式替换6

6 自然推理系统 定义3.3 自然推理系统P 定义如下: 1. 字母表 (1) 命题变项符号：p, q, r, ., pi , qi , ri , . (2) 联结词符号：, , , →,  (3) 括号与逗号：(, ), ， 2. 合式公式（同定义1.6） 3. 推理规则 例如以下基本推理规则 (1) 前提引入规则：在证明的任何步骤可以引入前提 (2) 结论引入规则：在证明的任何步骤得到的结论可作为后 继证明的前提 (3) 置换规则：在证明的任何步骤,命题公式中的子公式可用 等值的公式替换

在自然推理系统P中构造证明设前提A1,A2,Ak结论B及公式序列C1,C2………,C如果每一个C(1<i<)是某个A，或者可由序列中前面的公式应用推理规则得到,并且C,=B,则称这个公式序列是由A1A2.，A推出B的证明7

7 在自然推理系统P中构造证明 设前提A1 ,A2 ,, Ak ,结论B及公式序列C1 ,C2 ,, Cl . 如果每一个Ci (1il)是某个Aj , 或者可由序列中前面的公式应 用推理规则得到,并且Cl =B, 则称这个公式序列是由A1 ,A2 ,, Ak推出B的证明

直接证明法例题构造下面推理的证明：若明天是星期一或星期三，我明天就有课，一若我明天有课，今天必备课，一我今天没备课一所以，明天不是星期一，也不是星期三解 (1)设命题并符号化(3) 证明设明天是星期一p:E①r→s前提引入明天是星期三q:@-s前提引入我明天有课，r: E③-r(A->B)Λ-B=AS：我今天备课 (pvq)-→>r前提引入(2）写出证明的形式结构③④拒取式(pvq)前提：(pvg)→r,r→s,-s③置换@p-q结论：p-q8

8 例题 构造下面推理的证明： – 若明天是星期一或星期三, 我明天就有课. – 若我明天有课,今天必备课. – 我今天没备课. – 所以, 明天不是星期一, 也不是星期三. 直接证明法 解 (1) 设命题并符号化 设 p：明天是星期一， q：明天是星期三， r：我明天有课， s：我今天备课 (2) 写出证明的形式结构 前提：(pq)→r, r→s, s 结论：pq (3) 证明 ① r→s 前提引入 ② s 前提引入 ③ r ①②拒取式 ④ (pq)→r 前提引入 ⑤ (pq) ③④拒取式 ⑥ pq ⑤置换

附加前提证明法适用于结论为蕴涵式附加前提证明法欲证前提：AA2Ak结论：C→B等价地证明前提：A,A2,Ak,C结论：B理由:(A1NA2^...NAk)→(C->B)( -(Ar^A2^...^Ak)V(CVB)结合律、德摩根律-(A1NA...NA^C)B (A1A^...Ak^C)>B9

9 附加前提证明法 附加前提证明法 适用于结论为蕴涵式 欲证 前提：A1 , A2 , ., Ak 结论：C→B 等价地证明 前提：A1 , A2 , ., Ak , C 结论：B 理由： (A1A2.Ak )→(C→B)  ( A1A2.Ak )(CB)  ( A1A2.AkC)B  (A1A2.AkC)→B 结合律、德摩根律