离散数学第二章命题演算的推理理论-假设推理系统.ppt

《离散数学第二章命题演算的推理理论-假设推理系统.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章命题演算的推理理论2.1命题演算的公理系统2.2命题演算的假设推理系统2.2.1假设推理系统的组成2.2.2假设推理系统的推理过程2.3命题演算的归结推理法2．2命题演算的假设推理系统假设推理系统：由于它的推理形式类似于日常生活中的推理形式，也称为自然推理系统。2.2.1假设推理系统的组成一、扩充的推理规则二、假设推理过程三、推理定理四、假设推理证明定理的方法一、扩充的推理规则分离规则的推广A1，A2，…，An├A(2)肯定前提律A1，A2，A3，…，An├Ai分离规则的推广设有如下的推理规则R：若A1，A2，…，An，可以推出A，即R：A1

2、，A2，…，An├A，则称A是由A1，A2，…，An实施规则R而得。设Γ=A1，A2，…，An，则上述规则R可以记为Γ├A其中Γ为形式前提，A为形式结论。肯定前提律A1，A2，A3，…，An├Ai(i=1，2，…，n)，即前提中的任何命题均可作为结论。二、假设推理过程定义:如果能够作出一系列合式公式序列A1，A2,A3,…，An，它们(诸Ai)满足下列性质：(1)或为公理之一；(2)或为公式1,2,…,k之一，每个i称为假设；(3)或由前面的若干个Ag、Ah利用分离规则而得；(4)An=B。称这个公式序列A1，A2,…，An为由公式1，

3、2，…，k证明B的证明过程.1，2，…，k├B三、推理定理(附加前提证明法)如果Γ，A├B，则Γ├AB要证Γ├(AB)，即要证Γ，A├B附加前提证明法如果A1，A2，…，An-1，An，A├B，则A1，A2，…，An-1，An├AB进而，有下面定理：A1，A2…，An-1├An(AB)A1，A2，…，An-2├An-1(An(AB))依次类推可得定理：├A1(A2(…(An(AB))…))(2)归谬法如果Γ，A├B且Γ，A├B，则Γ├A。此定理称为反证律。这里B是一个公式。其它公理、规则同前节。四、假设推理证

4、明定理的方法(1)把待证公式的前件一一列出，作为假设(或把待证公式的后件的否定作为假设)，并在式子后注明为假设。(2)按上述介绍的推理方法进行推理，但此时不能对假设实施代入规则（因为假设不是永真公式）。(3)当推导出待证公式的后件时(或推导出矛盾时)就说证明了该定理。第二章命题演算的推理理论2.1命题演算的公理系统2.2命题演算的假设推理系统2.2.1假设推理系统的组成2.2.2假设推理系统的推理过程2.3命题演算的归结推理法例1：求证(P(QR))((PQ)R)证明:(1)P(QR)假设(2)PQ假设(3)(PQ)P公理8(4

5、)(PQ)Q公理9(5)P(3)(2)分离(6)Q(4)(2)分离(7)QR(1)(5)分离(8)R(6)(7)分离由假设推理过程的定义知：P(QR)，PQ├R由推理定理得：(P(QR))((PQ)R)(6)R在(5)中用R代入P有错吗?不能对(5)实施代入规则!!!例2(p21)求证：(PP)P证明：(1)PP假设(2)P假设，结论的否定(3)P(1)(2)分离显然，(2)与(3)表明推出矛盾(PP),P├P(PP),P├P由反证法得：(PP)├P由推理定理得：(PP)P例((SQ)

6、(PQ)S)P解:(1)S→Q假设(2)P→Q假设(3)S假设(4)P假设,结论的否定(5)Q(1)(3)分离(6)Q(1)(3)分离显然，(5)与(6)表明推出矛盾:SQ,PQ,S,P├QSQ,PQ,S,P├Q由反证法推理定理得：((SQ)(PQ)S)P例(P(QR))((PQ)(PR)))解:(1)P假设(2)P→Q假设(3)P→(Q→R)假设(4)Q(1)(2)分离(5)Q→R(1)(3)分离(7)R(4)(5)分离即证得P→(Q→R),P→Q,P┣R亦即证得命题：(P(QR))((P

7、Q)(PR))例((PQ)R)(P(QR))解:(1)P∧Q→R假设(2)P假设(3)Q假设(4)P→(Q→(P∧Q))公理10(5)Q→(P∧Q)(2)(4)分离(6)P∧Q(3)(5)分离(7)R(1)(6)分离即证得(P∧Q)→R,P,Q┣R亦即证得((PQ)R)(P(QR))例((PQ)((PR)(QS)))(SR)解:(1)(P∧Q)∧((PR)∧(QS))假设(2)P∧Q→P公理8(3)P∧Q→Q公理9(4)(P∧Q)∧((PR)∧(QS))→(P∧Q)代入(2)(5)(P∧Q)∧((P

8、R)∧(QS))→(PR)∧(QS)代入(3)(6)P∧Q(1)(4)分离(7)(PR)∧(QS)(1)(5)分