《离散数学高教版第一部分第三章ppt课件》由会员分享，可在线阅读，更多相关《离散数学高教版第一部分第三章ppt课件（8页珍藏版）》请在金锄头文库上搜索。
1、离散数学数理逻辑,第三章 命题逻辑的推理理论,3.1推理的形式结构,定义3。1 设 A1，A2Ak, B 都是命题公式，若对于A1,A2.Ak,B中出现的命题变项的任意一组赋值，或者A1A2 .Ak 为假，或者A1A2 .Ak 为真时，B为真，则称为由前提A1，A2 ， .Ak 推出B的推理是有效的，或者正确，并称B是有效的结论。,关于定义3.1还需做以下几点说明：,1.由前提A1,A2.Ak推结论B的推理是否正确与诸前提的排列次序无关。因而前提中的公式不一定是序列，而是一个有限公式集合，若将这个集合记为 , 可将由推B的推理记作 B 。若推理正确的，记为 B ，否则记作 B 这里可以称为 B
2、 。 2.设A1，A2.Ak,B中出现n个命题变项，对于任一组赋值，前提和结论的取值情况有四种： （1） A1A2 .Ak 为0，B为0； （2）A1A2 .Ak 为0, B为1； （3） A1A2 .Ak 为1, B为0； （4） A1A2 .Ak 为1，B为1.,定理3.1 命题公式A1,A2.Ak推B的正确推理正确，当且仅当（A1A2 .Ak) B为重言式。,例： （1）若a能被4整除，则a能被2整除。a能被4整除，所以a能被2整除。 （2）下午马芳或去看电影或去游泳，她没有去看电影，所以她去游泳了。,（1）解：设p：a能被4整除q:a能被2 整除.前提:p q,p 结论:q推理的形式结
3、构: (pq) p q,(2)设 P:马芳下午去看电影. Q:马芳下午去游泳. 前提:pq, p 结论:q 推理的形式结构（pq ）q）q,3.2 自然推理系统P,定义3.2 一个形式系统I由下面四个部分成： （1）非空的字母表，记作A(I)。 （2）A（I）中符号构造的合式集，记作 E（I） （3） E（I）中一些特殊的公式组成的公理集，记作Ax（I）。 （4）推理规则集，记作R（x）。,3.2自然推理系统P,1. 字母表 (1)命题变项符号：p，q，r. (2)连接词符号：，等 (3)括号与逗号：（），2.合式公式3.推理规则（1）前提引入规则：在证明的任何步骤都可以引入前提。（2）结论引
4、入规则：在证明的任何步骤上的所得结论都可以作为定义3.3 自然推理系统P定义如下后继证明的前提。（3）置换规则：在证明的任何规则步骤上，命题公式中的子公式都可以用于之等值的公式置换，得到公式序列中有一个公式。假言推理规则（或称分离规则），附加规则，化简规则，拒取式规则，假言三段论规则，析取三段论规则，构造性二难推理规则，破坏性二难推理规则合取引入规则,例：如果小王是理科学生，则他的数学成绩一定很好。如果小王不是文科生，他一定是理科生。小王的数学成绩不好，所以小王是文科生。,解：设p：小王是理科学生，q：小王数学成绩好，r：小王是文科学生。 前提： 结论： 证明 1. pq 前提引入 2.非q 前提引入 3.非p 1，2拒绝式 4.非r q 前提引入 5.r3，4拒绝式,
