大连理工大学软件学院离散数学第一章命题逻辑-4th

《大连理工大学软件学院离散数学第一章命题逻辑-4th》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学第一章命题逻辑2/38回顾对偶原理定义，三条原理：非运算与对偶，等价，永真蕴含析取范式和合取范式基本积，基本和基本和的积，基本积的和主析取范式和主合取范式极小项（积），极大项（和），基—二进制数—十进制数—描述符极小项的和，极大项的积，两者的关系。3/38求范式步骤：(2)否定消去或内移。(3)利用分配律。(1)消去联结词回顾4/381.7命题演算的推理理论数理逻辑的一个主要任务就是提供一套推理规则，给定一些前提，利用所提供的推理规则，推导出一些结论来，这个过程称为演绎或证明。生活中：倘若认定前提是真的，从前提推导出结论的论证是遵守了逻辑推理规则，则认为

2、此结论是真的，并且认为这个论证过程是合法的。数理逻辑中：不关心前提的真实真值，把注意力集中于推理规则的研究，依据这些推理规则推导出的任何结论，称为有效结论，而这种论证则被称为有效论证。5/38有效结论定义:设A和B是两个命题公式，当且仅当AB是个永真式，即AB，则说B是A的有效结论，或B由A可逻辑的推出。可把该定义推广到有n个前提的情况。6/38有效结论定义：例：H1：今天周一或者今天下雨。H2：今天不是周一。C：今天下雨。7/38证明有效结论的方法1，真值表法思路:“证明使前提集合取值为真的那些组真值指派，也一定使结论取值为真”。例:考察结论C是否是下列前

3、提H1，H2,H3的结论。(1)H1：P→Q，H2：P，C：QPQH1H2CH1ΛH2→C0010010110111001011111118/38真值表法(2)真值表构造如下：000001010011100101110111111100111101110110101010111100009/38真值表法(3)0001101111000111000110/38真值表法例：一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。解：设P:一份统计表格的错误是由于材料不可靠。Q:一份统计表格

4、的错误是由于计算有错误。于是问题可符号化为：(PQ)PQ11/38真值表法PQ(PQ)PQ000001111000110112/38证明有效结论的方法2，直接证法在命题变元较多的情况下，真值表法显得不方便，我们采用直接证明法，为此先给出如下的定义定义：设S是一个命题公式的集合，从S推出命题公式C的推理过程是命题公式的一个有限序列：C1，C2，…，Cn。其中，Ci或者属于S，或者是某些Cj(j

5、助大家记忆，我们把常用的等价式和永真蕴涵式再次列出来。13/38常用永真蕴含式I1：PQP,I2:PPQ,I3:PPQI4:QPQ,I5:(PQ)P,I6:(PQ)QI7：P,QPQ,I8：P,PQQ,I9：P,PQQI10：Q,PQP,I11：PQ,QRPRI12：PQ,PR,QRR公式中“,”代表“”,公式不必死记硬背，其证明均可从“”的定义出发。例如对I11前件为真时保证PQ和QR都必为真，PQ为真，则保证P为真时Q一定为真，而Q为真和QR为真则保证了R必为真，P为真，R为真

6、自然保证了PR为真，问题得证。14/38常用等价式E1:PP,E2:PQQP,E3:PQQPE4:(PQ)RP(QR)E5:(PQ)RP(QR)E6:(PQ)R(PR)(QR)E7:(PQ)R(PR)(QR)E8:(PQ)PQE9:(PQ)PQE10:PPPE11:PPP15/38常用等价式E12:R(PP)RE13:R(PP)RE14:R(PP)TE15:R(PP)FE16:PQPQE17:(PQ)PQE18:PQ

7、QPE19:P(QR)(PQ)RE20:(PQ)PQE21:PQ(PQ)(QP)E22:PQ(PQ)(PQ)16/38常用等价公式17/38直接证法直接证明法：使用推理规则和给定的等价式及永真蕴涵式进行推导证明。推理规则：规则P：在推导过程中，任何时候都可以引入前提。引入一个前提称为使用一次P规则。规则T：在推导中，如果前面有一个或多个公式永真蕴含公式S，则可以把公式S引进推导过程中。换句话说，引进前面推导过程中的推理结果称为使用T规则。18/38直接证法解:{1}(1)¬(P∧¬Q)P规则{1}(2)¬P∨Q

8、T规则(1)和E11{1