资源描述：
《命题逻辑的推理结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算机科学MOOC课程群离散数学基础•推理的形式结构−例：»前提1:如果今天是周五，那么我们有数理逻辑课。»前提2:今天是周五。»结论:今天我们有数理逻辑课。»形式化：P：今天是周五。Q：今天我们有数理逻辑课。»前提1：P→Q»前提2：P»结论：Q•定义：条件式推理结构−将例子中的两个前提记为(P→Q)∧P，结论记为Q，上述推理过程可表述为：(P→Q)∧P
2、→Q或(P→Q)∧P├Q称为条件式推理结构。−记号”├”读成”推出”−(P→Q)∧P├Q经常写成(P→Q),P├Q•定义：推理结构的有效性−设命题公式H、C，若当H为真时，C必为真，则称推理结构H├C是有效的（或是正确的）推理形式
3、。否则，称推理结构H├C不是有效的（或是无效的）推理形式。»H├C有效，即在H上的任何令H的真值为T的解释下，C的真值均为T。»H├C无效，即至少存在一个令H的真值为T而C的真值为F的解释。»推广到有n个前提H1,H2,…,Hn的情形，可令H=H1∧H2∧…∧Hn将推理的形式结构写成H├C；如果定义Γ={H1,H2,…,Hn}，可写成Γ├C。−例：P,(P→Q)├Q是有效的推理结构。»由下面的真值表可见，穷尽所有的解释，只有第4行令P∧(P→Q)=T。而对应此解释，Q=T。PQP→QP∧(P→Q)FFTFFTTFTFFFTTTT−例：¬Q,(P→Q)├¬P是有效的推理结构。»由真值表
4、可见，只有第1行解释令¬Q∧(P→Q)=T。而对应此解释，¬P=T。PQ¬QP→Q¬Q∧(P→Q)¬PFFTTTTFTFTFTTFTFFFTTFTFF−例：¬P,(P→Q)├¬Q不是有效的推理结构。»由其真值表可见，存在第2行解释令¬P∧(P→Q)=T。而对应此解释，¬Q=F。PQ¬QP→Q¬Q∧(P→Q)¬PFFTTTTFTFTFTTFTFFFTTFTFF•定义：逻辑推出/重言蕴涵−当H├C有效时，可写成H⇒C，称H逻辑推出C，或说C是H的逻辑推论（有效结论），或H重言蕴涵C。−注意到H⇒C描述了公式H和C之间的一种真值联系，但”⇒”不是连接词，”H⇒C”也不是合式公式。•重言蕴涵
5、的若干性质：−若A⇒B，且A为重言式，则B也为重言式。−若A⇒B，且B⇒A，则A⇔B。−若A⇒B，且B⇒C，则A⇒C。−若A⇒B，且A⇒C，则A⇒B∧C。−若A⇒C，且B⇒C，则A∨B⇒C。−性质的证明：从重言蕴涵的定义可以直接对上述性质进行验证。•定理：演绎定理−设有命题公式H1,H2,…,Hn,C，则推理形式H1,H2,…,Hn├C是有效的当且仅当命题形式H1∧H2∧…∧Hn→C是重言式。−演绎定理的证明：⇒对于那些令H1∧H2∧…∧Hn=1的解释，由于H1,H2,…,Hn├C是有效的，必须C=1，此时H1∧H2∧…∧Hn→C=1；对于那些令H1∧H2∧…∧Hn=0的解释，H1∧
6、H2∧…∧Hn→C=1。故H1∧H2∧…∧Hn→C是重言式。⇐对于那些令H1∧H2∧…∧Hn=1的解释，由于H1∧H2∧…∧Hn→C是重言式，必须C=1，所以H1,H2,…,Hn├C是有效的。•定理：演绎定理−推论：上述H1,H2,…,Hn├C有效当且仅当H1∧H2∧…∧Hn∧¬C为矛盾式。−推论的证明：只需证明命题形式H1∧H2∧…∧Hn→C是重言式当且仅当H1∧H2∧…∧Hn∧¬C为矛盾式。⇒若H1∧H2∧…∧Hn→C是重言式：对于那些令H1∧H2∧…∧Hn=1的解释，C=1，即¬C=0，此时H1∧H2∧…∧Hn∧¬C=0；对于那些令H1∧H2∧…∧Hn=0的解释，H1∧H2∧…
7、∧Hn∧¬C=0。故H1∧H2∧…∧Hn∧¬C为矛盾式。⇐若H1∧H2∧…∧Hn∧¬C为矛盾式：对于那些令H1∧H2∧…∧Hn=1的解释，必须¬C=0，即C=1，此时H1∧H2∧…∧Hn→C=1；对于那些令H1∧H2∧…∧Hn=0的解释，H1∧H2∧…∧Hn→C=1。故H1∧H2∧…∧Hn→C是重言式。•常用的推理公式/推理定律−下面是常用的14条有效的推理结构，也称推理定律或推理公式。其正确性可以利用真值表加以验证。(1)P∧Q⇒P化简(2)¬(P→Q)⇒P(3)¬(P→Q)⇒¬Q(4)P⇒P∨Q附加(5)¬P⇒P→Q(6)Q⇒P→Q(7)¬P∧(P∨Q)⇒Q析取三段论(8)P∧(
8、P→Q)⇒Q假言推理/分离规则(9)¬Q∧(P→Q)⇒¬P拒取式(10)(P→Q)∧(Q→R)⇒(P→R)假言三段论(11)(P↔Q)∧(Q↔R)⇒(P↔R)等价三段论(12)(P→R)∧(Q→R)⇒((P∨Q)→R)二难推论(13)(P→Q)∧(R→S)∧(P∨R)⇒(Q∨S)构造性二难推论(14)(P→Q)∧(R→S)∧(¬Q∨¬S)⇒¬P∨¬R破坏性二难推论•证明A⇒B的方法−真值表法：列出真值表，证明A→B是重言式，再利用演绎定理得证；−解释法：设
