哈尔滨理工大学斛监課裎 离影数 3:第3章命题逻辑的推理理论 计算机系
第3章 命题逻辑的推理理论 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章说可 口本章的主要内容 推理的形式结构 自然推理系统P 口本章与后续各章的关系 本章是第五章的特殊情况和先行准备
本章说明 ❑本章的主要内容 –推理的形式结构 –自然推理系统P ❑本章与后续各章的关系 –本章是第五章的特殊情况和先行准备
口3.1推理的形式结构 口3.2自然推理系统P 口本章小结 口习题 口作业
❑3.1 推理的形式结构 ❑3.2 自然推理系统P ❑ 本章小结 ❑ 习题 ❑ 作业
3.1推理的形式结构 口数理逻辑的主要任务是用数学的方法来研究数学中的 推理 口推理是指从前提出发推出结论的思维过程。 口前提是已知命题公式集合。 口结论是从前提出发应用推理规则推出的命题公式。 口证明是描述推理正确或错误的过程。 口要研究推理,首先应该明确什么样的推理是有效的或 正确的
3.1 推理的形式结构 ❑数理逻辑的主要任务是用数学的方法来研究数学中的 推理。 ❑推理是指从前提出发推出结论的思维过程。 ❑前提是已知命题公式集合。 ❑结论是从前提出发应用推理规则推出的命题公式。 ❑证明是描述推理正确或错误的过程。 ❑要研究推理，首先应该明确什么样的推理是有效的或 正确的
有效推理的定义 定义3.1设A1,A2…,A和B都是命题公式,若对于 A1,A2,…A和B中出现的命题变项的任意一组赋值, (1)或者A1∧A2∧…A为假; (2)或者当A1∧A2A…∧A为真时,B也为真; 则称由前提A1,A2,…,A推出B的推理是有效的或正确 的,并称B是有效结论
定义3.1 设A1 ,A2 ,…,Ak和B都是命题公式，若对于 A1 ,A2 ,…,Ak和B中出现的命题变项的任意一组赋值， （1）或者A1∧A2 ∧…∧Ak为假; （2）或者当A1∧A2 ∧…∧Ak为真时，B也为真; 则称由前提A1 ,A2 ,…,Ak推出B的推理是有效的或正确 的，并称B是有效结论。 有效推理的定义
关于有效推理的说明 口由前提A,A2,…,A推结论B的推理是否正确与 诸前提的排列次序无关 r={A1,A2,…,A 由r推B的推理记为B 若推理是正确的,记为rFB 若推理是不正确的,记为rHB
关于有效推理的说明 ❑＝{A1，A2，…，Ak } 由 推B的推理记为┣B 若推理是正确的，记为 ╞ B 若推理是不正确的，记为 B ❑由前提A1，A2，…，Ak推结论B的推理是否正确与 诸前提的排列次序无关
关于有效推理的说 口设A1,A2,…,Ak,B中共出现n个命题变项,对于任何 组赋值a1a2…an(a=0或者1,i=1,2,…,n),前提 和结论的取值情况有以下四种: (1)A1∧A2∧…∧A为0,B为0。 (2)A1∧A2∧…NA为0,B为1。 (3)A1∧A2∧…A为1,B为0 (4)A1∧A2∧…A为1,B为1 口只要不出现(3)中的情况,推理就是正确的,因而判断 推理是否正确,就是判断是否会出现(3)中的情况。 口推理正确,并不能保证结论B一定为真
关于有效推理的说明 ❑设A1，A2，…，Ak，B中共出现n个命题变项，对于任何 一组赋值α1α2…αn (αi =0或者1，i=1,2,…,n)，前提 和结论的取值情况有以下四种： (1) A1∧A2 ∧…∧Ak为0，B为0。 (2) A1∧A2 ∧…∧Ak为0，B为1。 (3) A1∧A2 ∧…∧Ak为1，B为0。 (4) A1∧A2 ∧…∧Ak为1，B为1。 ❑只要不出现(3)中的情况，推理就是正确的，因而判断 推理是否正确，就是判断是否会出现(3)中的情况。 ❑推理正确，并不能保证结论B一定为真
例题 例3.1判断下列推理是否正确。(真值表法 (1){p,p→q}q 正确 (2){p,q→p} 不正确 pA(P→q)q|p^(q→p) p-0-0—1—1 q-0-1-0—1 0 0001 0 00=11 q01=0=1 1
(1) {p,p→q}├ q (2) {p,q→p}├ q 例3.1 判断下列推理是否正确。（真值表法） p q p(p→q) q p(q→p) q 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 例题 正确 不正确
有效推理的等价定理 定理3.1命题公式A1,A2,…,A推B的推理正确当且仅当 (A1∧A2∧…Ak)→B为重言式。 说)口该定狸是判断推理是否正确的另一种方法
定理3.1 命题公式A1 ,A2 ,…,Ak推B的推理正确当且仅当 (A1∧A2∧…∧Ak )→B 为重言式。 ❑该定理是判断推理是否正确的另一种方法。 说 明 有效推理的等价定理
定理3,1的证明 (1)证明必要性。若A,A2,……,A推B的推理正确, 则对于A,A2,…,AB中所含命题变项的任意一组赋值,不会出 现A1∧A2A…A为真,而B为假的情况, 因而在任何赋值下,蕴涵式(A1A2…A)→B均为真,故它 为重言式。 (2)证明充分性。若蕴涵式(A1∧A2∧…A)→B为重言式, 则对于任何赋值此蕴涵式均为真,因而不会出现前件为真后件 为假的情况, 即在任何赋值下,或者A∧A2^…A为假, 或者A1∧A2∧….∧A和B同时为真,这正符合推理正确的定义
定理3.1的证明 (1)证明必要性。若A1 ,A2 ,…,Ak推B的推理正确， 则对于A1 ,A2 ,…,Ak ,B中所含命题变项的任意一组赋值，不会出 现A1∧A2∧…∧Ak为真，而B为假的情况， 因而在任何赋值下，蕴涵式(A1∧A2∧…∧Ak )→B均为真，故它 为重言式。 (2)证明充分性。若蕴涵式(A1∧A2∧…∧Ak )→B为重言式， 则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件 为假的情况， 即在任何赋值下，或者A1∧A2∧…∧Ak为假， 或者A1∧A2∧…∧Ak和B同时为真，这正符合推理正确的定义