命题逻辑的推理理论.ppt

第1页，共35页，2022年，5月20日，8点45分，星期二
数理逻辑的主要任务是用数学的方法来研究数学中的推理。
推理是指从前提出发推出结论的思维过程。
前提是已知命题公式集合。
结论是从前提出发应用推理规则推出的命题公式。
证明是构造性二难
(9)(A→B)∧(C→D)∧(┐B∨┐D) (┐A∨┐C) 破坏性二难
推理定律--重言蕴含式
第10页，共35页，2022年，5月20日，8点45分，星期二
关于推理定律的几点说明
A,B,C为元语言符号，代表任意的命题公式。
若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。
。例如双重否定律A A产生两条推理定律A A和 AA。
由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则。
第11页，共35页，2022年，5月20日，8点45分，星期二
构造性证明方法
判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。
当推理中包含的命题变项较多时，上述三种方法演算量太大。
对于由前提A1,A2,…,Ak推B的正确推理应该给出严谨的证明。
证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。
第12页，共35页，2022年，5月20日，8点45分，星期二
常用的推理规则
（1）前提引入规则：在证明的任何步骤上， 都可以引入前提。
（2）结论引入规则：在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。
（3）置换规则：在证明的任何步骤上，命题公式中任何子命题公式都可以用与之等价的命题公式置换。
第13页，共35页，2022年，5月20日，8点45分，星期二
（4）假言推理规则 AB A  B
（5）附加规则 A  AB
（6）化简规则 AB A
（4）若今天下雪,则将去滑雪。今天下雪，所以去滑雪。
（5）现在气温在冰点以下。因此，要么现在气温在冰点以下，要么现在下雨。
（6）现在气温在冰点以下并且正在下雨。因此，现在气温在冰点以下。
第14页，共35页，2022年，5月20日，8点45分，星期二
（7）拒取式规则 AB B   A
（8） 假言三段论规则 AB BC   AC
（9）析取三段论规则 AB B  A
第15页，共35页，2022年，5月20日，8点45分，星期二
（10）构造性二难推理规则 AB CD AC  BD
（11）破坏性二难推理规则 AB CD BD  AC
（12） 合取引入规则 A B  AB
第16页，共35页，2022年，5月20日，8点45分，星期二
构造证明
构造证明就是由一组公式作为前提，利用自然推理系统中的规则，推出结论。
构造形式结构A1A2…Ak  B 的推理的书写方法：前提： A1,A2,…,Ak 结论： B
证明方法：
直接证明法
附加前提法
归谬法（或称反证法）
第17页，共35页，2022年，5月20日，8点45分，星期二
构造下面推理的证明：前提：┐p∨q, r∨┐q ,r→s 结论：p→s
① ┐p∨q     前提引入
② p→q       ①置换
③ r∨┐q     前提引入
④ q→r       ③置换
⑤ p→r       ②④假言三段论
⑥ r→s       前提引入
⑦ p→s       ⑤⑥假言三段论
第18页，共35页，2022年，5月20日，8点45分，星期二
例题
构造下面推理的证明：前提：p→（q→r）, p∧q 结论： ┐r→s
① p→（q→r）    前提引入
② p∧q       前提引入
③ p     ②化简
④ q       ②化简
⑤ q→r        ①③假言推理
⑥ r       ④⑤假言推理
⑦ r∨s      ⑥附加
⑧ ┐r→s ⑦置换
第19页，共35页，2022年，5月20日，8点45分，星期二
技巧一：附加前提证