第二章 命题逻辑的等值和推理演算
??
?? ??
??
推理形式和推理演算是数理逻辑研究的基本内 容 推理形式是由前提和结论经蕴涵词联结而成的 推理过程是从前提出发，根据所规定的规则来 推导出结论的过程 重言式是重要的逻辑规律，正确的推理形式、 等值式都是重言式
??
??
本章对命题等值和推理演算进行讨论，是以语 义的观点进行的非形式的描述，不仅直观且容 易理 也便于实际问题的逻辑描述和推理。 严格的形式化的讨论见第三章所建立的公理系 统。
等值演算(考察逻辑关系符??(=))
?? ??
?? ??
等值定理、公式 联结词的完备集(由个别联结词表示所有联结 词的问题) 对偶式(命题公式的对偶性) 范式(命题公式的统一标准) 由真值表写命题公式(由T写、由F写)
推理演算(考察逻辑关系符??)
?? ?? ??
??
推理形式( '推理形式的表示) 基本推理公式(各种三段论及五种证明方法) 推理演算(证明推理公式的第六种方法，使用 推理规则) 归结推理法(证明推理公式的第七种方法，常 用反证法)
2.1 等值定理
??
若把初等数学里的＋、－、×、÷等运算符看作是数 与数之间的联结词，那么由这些联结词所表达的代数 式之间，可建立许多等值式如下： x2－y2 = (x＋y)(x－y) (x＋y)2 = x2＋2xy＋y2 sin2x＋cos2x = 1 ……
在命题逻辑里也同样可建立一些重要的 等值式
2.1.1 等值的定义
??
给定两个命题公式A和B, 而P1…Pn是出现于A和B中的 所有命题变项, 公式A和B共有2n个解释, 若对其 中的任一 , 公式A和B的真值都相等, 就称A和B是 等值的(或等价的)。记作A = B或A??B 显然，可以根据真值表来判明任何两个公式是否是等 值的
??
例1: 证明(P∧??P)∨Q = Q
证明: 画出(P∧??P)∨Q与Q的真值表可看出等式 是成立的。
例2: 证明P∨??P = Q∨??Q
??
证明: 画出P∨??P, Q∨??Q的真值表, 可看出它 们是等值的, 而且它们都是重言式。
说明
??
从例1、2还可说明, 两个公式等值并不一定要 求它们一定含有相同的命题变项
??
?? ??
若仅在等式一端的公式里有变项P出现, 等式 两端的公式其真值均与P无关。 例1中公式(P∧??P)∨Q与Q的真值都同P无关 例2中P∨??P, Q∨??Q都是重言式, 它们的真值也 都与P、Q无关。
2.1.2 等值定理
定理 对公式A和B, A=B的充分必要条件是A??B 是重言式。 ?? A、B不一定都是简单命题, 可能是由简单命题 P1, …, Pn构成的. 对A, B的一个解释, 指的是对 P1, …, Pn的一组具体的真值设定. ?? 若A??B为重言式, 则在任一 下A和B都只 能有相同的真值, 这就是定理的意思。
证明
若A ?? B是重言式, 即在任一 下, A ?? B的 真值都为T
依A ?? B的定义只有在A、B有相同的值时, 才有A ?? B = T。于是在任一 下, A和B都有相同的真 值, 从而有A=B。 ?? 反过来，若有A = B, 即在任一 下A和B都有相 同的真值, 依A ?? B的定义, A ?? B只有为真, 从而 A ?? B是重言式。 注：根据该等值定理，证明两个公式等值，只要证 明由这两个公式构成的双条件式是重言式即可
??

下一页