第二章命题逻辑的等值和推理演算

1、第二章 命题逻辑的等值和推理演算 n推理形式和推理演算是数理逻辑研究的基本内容 n推理过程是从前提出发，根据所规定的规则来推导出结论的过程 n重言式是重要的逻辑规律，正确的推理形式，等值式都是重言式。 n本章对命题等值和推理演算进行讨论，是以语义的观点进行的非形式的描述，不仅直观且容易理解，也便于实际问题的逻辑描述和推理。n严格的形式化的讨论见第三章所建立的公理系统。 2.1 等值定理 n若把初等数学里的、等运算符看作是数与数之间的联结词，那么由这些联结词所表达的代数式之间，可建立许多等值式如下：x2y2 = (xy)(xy)(xy)2 = x22xyy2 sin2xcos2x = 1在命题逻

2、辑里也同样可建立一些重要的等值式。 2.1.1 等值的定义 n给定两个命题公式A和B, 而P1Pn是出现于A和B中的所有命题变项, 那么公式A和B共有2n个解释, 若对其中的任一解释, 公式A和B的真值都相等, 就称A和B是等值的(或等价的)。记作A = B或A B。 n显然，可以根据真值表来判明任何两个公式是否是等值的。例1: 证明(PP)Q = Q证明: 画出(PP)Q与Q的真值表可看出等式是成立的。例2: 证明PP = QQn证明: 画出PP, QQ的真值表, 可看出它们是等值的, 而且它们都是重言式。n从例1、2还可说明, 两个公式等值并不要求它们一定含有相同的命题变项。若仅在等式一端

3、的公式里有变项P出现, 那么等式两端的公式其真值均与P无关。例1中公式(PP) Q与Q的真值都同P无关, 例2中PP, QQ都是重言式, 它们的真值也都与P、Q无关。 2.1.2 等值定理 n定理 对公式A和B, A = B的充分必要条件是A B是重言式。n若A B为重言式(A、B不一定都是简单命题, 可能是由简单命题P1, , Pn构成的对A, B的一个解释, 指的是对P1, , Pn的一组具体的真值设定), 则在任一解释下A和B都只能有相同的真值, 这就是定理的意思。 证明n若A B是重言式, 即在任一解释下, A B的真值都为T。依A B的定义只有在A、B有相同的值时, 才有A B =

4、T。于是在任一解释下, A和B都有相同的真值, 从而有A=B。反过来，若有A = B, 即在任一解释下A和B都有相同的真值, 依A B的定义, A B只有为真, 从而A B是重言式。 n有了这个等值定理，证明两个公式等值，只要证明由这两个公式构成的双条件式是重言式即可。 不要将“”视作联结词，在合式公式定义里没有“”出现。A = B是表示公式A与B的一种关系。这种关系具有三个性质: 1. 自反性 A = A。2. 对称性 若A = B则B = A。3. 传递性 若A = B, B = C则A = C。这三条性质体现了“”的实质含义。 2.2 等值公式2.2.1 基本的等值公式(命题定律)1.

5、双重否定律P = P2. 结合律(PQ) R = P(QR)(PQ) R = P(QR)(P Q) R = P (Q R)3. 交换律PQ = QPPQ = QPP Q = Q P4. 分配律P(QR) = (PQ)(PR)P(QR) = (PQ)(PR)P(QR) = (PQ)(PR)5. 等幂律(恒等律)PP = PPP = PPP = TPP = T6. 吸收律P(PQ) = PP(PQ) = P7. 摩根律(PQ) = PQ(PQ) = PQ对蕴涵词、双条件词作否定有(PQ) = PQ(PQ) = PQ = PQ= (PQ)(PQ)n8. 同一律nPF = PnPT = PnTP =

6、PnTP = Pn还有nPF = PnFP = P 9. 零律PT = TPF = F还有PT = TFP = T10. 补余律PP = TPP = F还有PP = PPP = PPP = F n所有这些公式，都可使用直值表加以验证。 Venn图n若使用Venn图也容易理解这些等值式, 这种图是将P、Q理解为某总体论域上的子集合, 而规定PQ为两集合的公共部分(交集合), PQ为两集合的全部(并集合), P为总体论域(如矩形域)中P的余集。 从Venn 图因PQ较P来得“小”, PQ较P来得“大”，从而有P(PQ) = PP(PQ) = P对这些等式使用自然用语加以说明，将有助于理解。如P表示

7、张三是学生, Q表示李四是工人, 那么(PQ)就表示并非“张三是学生或者李四是工人”。这相当于说，“张三不是学生而且李四也不是工人”，即可由PQ表示, 从而有(PQ) = PQ。 2.2.2 若干常用的等值公式 n由于人们对、更为熟悉，常将含有和的公式化成仅含有、的公式。这也是证明和理解含有，的公式的一般方法。n公式11-18是等值演算中经常使用的,也该掌握它们, 特别是能直观地解释它们的成立。 11. PQ = P Qn通常对PQ进行运算时, 不如用PQ来得方便。而且以PQ表示PQ帮助我们理解如果P则Q的逻辑含义。问题是这种表示也有缺点，丢失了P、Q间的因果关系。 12. PQ = QPn如

8、将PQ视为正定理, 那么QP就是相应的逆否定理, 它们必然同时为真, 同时为假, 所以是等值的。 13. P(QR) = (PQ)RnP是(QR)的前提, Q是R的前提, 于是可将两个前提的合取PQ作为总的前提。 即如果P则如果Q则R, 等价于如果P与Q则R。 14. PQ = (PQ)(PQ)n这可解释为PQ为真, 有两种可能的情形, 即(PQ)为真或(PQ)为真。而PQ为真, 必是在P = Q = T的情况下出现, PQ为真, 必是在P = Q = F的情况下出现。从而可说, PQ为真, 是在P、Q同时为真或同时为假时成立。这就是从取真来描述这等式。 15. PQ = (PQ)(PQ)n这

9、可解释为PQ为假, 有两种可能的情形, 即(PQ)为假或(PQ)为假, 而PQ为假, 必是在P = F, Q = T的情况下出现, PQ为假, 必是在P = T, Q = F的情况下出现。从而可说PQ为假, 是在P真Q假或P假Q真 时成立。这就是从取假来描述这等式 16. PQ = (PQ)(QP)n这表明PQ成立, 等价于正定理PQ和逆定理QP都成立。 17. P(QR) = Q(PR)n前提条件P、Q可交换次序。 18. (PR) (QR)=(PQ)Rn左端说明的是由P而且由Q都有R成立。从而可以说由P或Q就有R成立, 这就是等式右端。2.2.3 置换规则 定理: 对公式A的子公式, 用与

10、之等值的公式来代换便称置换。置换规则 公式A的子公式置换后A化为公式B, 必有A = B。当A是重言式时, 置换后的公式B必也是重言式。n置换与代入是有区别的。置换只要求A的某一子公式作代换, 不必对所有同一的子公式都作代换。 2.2.4 等值演算举例 例1: 证明(P(QR)(QR)(PR) = R证明: 左端= (P(QR) (QP)R)(分配律)=(PQ)R)(QP)R)(结合律)=(PQ)R)(QP)R)(摩根律)=(PQ)(QP)R(分配律)=(PQ)(PQ)R(交换律)=TR(置 换)=R(同一律) 例2: 试证 (PQ)(P(QR) (PQ)(PR) = T证明:左端=(PQ)(

11、P(QR)(PQ)(PR)(摩根律)=(PQ)(PQ)(PR)(PQ)(PR) (分配律)=(PQ)(PR)(PQ)(PR)(等幂律)=T2.6 范式nn 个命题变项所能组成的具有不同真值的命题公式仅有22n个, 然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个。这样，首先就要问凡与命题公式A等值的公式，能否都可以化为某一个统一的标准形式。希望这种标准形能为我们的讨论带来些方便，如借助于标准形对任意两个形式上不同的公式，可判断它们的是否等值。借助于标准形容易判断任一公式是否为重言式或矛盾式。求解公式的成真指派和成假指派 n一个公式，其中含有命题变元P1, ,Pn, 表示为 P1,

12、,Pn，（P1, ,Pn）称为变元组，公式的变元组（P1, ,Pn）的任意一组确定的值，称为对该公式的关于该变元组（P1, ,Pn）的一个完全指派。如果仅对变元组中的部分变元确定值，其余变元没有赋以确定的值，则称这样的一组值为该公式的关于变元组的一个部分指派。完全指派与部分指派例如公式 ： p(qr)。 变元组为（p，q，r），一个完全指派为（T，F，F），在此指派下，公式取真值。即 = T。可这样来表示：（p，q，r）=（T，F，F） = T或者有时记为： （p，q，r）=（T，F，F） = T 一个部分指派为（T，T，）这时候 的值不能确定，当r = T时， = T，当r = F时，= F

13、。这一点通常都能理解，因为一个公式的值取决于公式中所含变元的值，当其中某些变元未确定时，公式最终的值也不能定。但是这一点也未必绝对，例如，赋（p，q，r）以（F，X，X）时，公式肯定是取假值，即= F。这时候可看出对q，r 的指派已经无关紧要了。成真指派与成假指派n定义：对于任一公式，凡是使得 取真值 = T 的指派，不管是完全指派还是部分指派，都称为 的成真指派。凡是使 取假值 = F 的指派，不管是完全指派还是部分指派，都称为 的成假指派。 例子：P 的成真指派 P=F, 成假指派P=T。：PQ 的成真指派（P，Q）=（T，T） 成假指派（P，Q）=（F，F），（F，T），（T，F）：PQ

14、 的成真指派（P，Q）=（T，T），（T，F），（F，T） 成假指派（P，Q）=（F，F）永真式、永假式、可满足式有的公式没有成真指派，如：PP, 称为永假式（反驳式）；有的公式没有成假指派，如：PP, 称为永真式（重言式）。永假式，又称为矛盾式，不可满足。如果一个公式，有成真指派，则称为公式 可满足。与它相对的，如果没有成真指派，就是不可满足的。如果一个公式，有成假指派，则称该公式为非永真公式。部分指派公式 的变元组（P1, ,Pn），一个部分指派 ：（V1, Vi-1, X, Vi+1, Vn），其中Vi为具体真假值。它为公式 的成真指派，当且仅当：（V1, Vi-1, T, Vi+1,

15、Vn）及（V1, Vi-1, F, Vi+1, Vn）均为成真指派。成假指派情况是相似的。求解成真指派和成假指派的方法n一个直截了当的办法是将公式 的所有完全指派全都列举出来，逐个验算该指派下 取的真假值，从而确定每个完全指派是成真指派还是成假指派。但是，含n个变元的公式，共有2n个完全指派，当n为5、6、时，指数的总数就会相当可观，按指数级数增长，难以全部枚举。因此应当选择更为简单、可行的办法部分指派。求部分指派的前提是将原来的公式 化简，使得原来含有n个变元的公式化为可能含变元数更少的公式，于是便大大地削减了运算的数量。部分指派的步骤n第一步，否定深入。将外层的否定深入到内层，一直深入到变

16、元为止。n第二步，部分指派。选定一个变元对其作真和假两种指派，得到两个不含该变元但较原式简单的公式。如果这两个公式直接得到真假值，则得部分指派，否则n第三步，化简。得到的两公式虽然较原公式简单，但仍含有变元，于是重复第二步，逐个减少变元，直到确定真假值为止。n第二步中如何选定一个变元，希望化简效果最好，因此选择在公式中出现次数最多的变元作指派。还有一种情况就是对该变元赋以一个指派后，立即使整个公式有确定的真假值。试求给定公式的成真成假指派n：(p r) ( (p q) ( p (q r) ) )n第一步 否定深入：n (p r) ( (p q) (p (q r) ) )n第二步 部分指派：选择

17、出现最多的命题，指派以T, F。（分别情况）。n 上式中，P出现最多，故 分为 p = T n p = F两种情况。 p = T ：(T r ) （T q ）（T (q r)） 化简(q (q r)也可最终化简为r， p = F ：(F r ) （F q ）（F (q r)） 化简得 r（T F）最终化简得r组合起来，的成真指派（p, q, r）= ( T, X, F ), (F, X, T ), 成假指派（p, q, r）= ( T, X, T ), (F, X, F )。不完全成真指派 (p, q, r): (T, X, F)可以生成相应的完全成真指派 (T, T, F ) 和 (T, F

18、, F )。 (p, q, r): (F, X, T) (F, T, T ) 和 (F, F, T )。因此，写完整的话，的完全成真指派：(T, T, F )，(T, F, F )，(F, T, T )，(F, F, T )。相仿地，的完全成假指派：(T, X, T ) (T, T, T) ，(T, F, T )，(F, X, F ) (F, T, F )，(F, F, F )完全成假指派：(T, T, T) ，(T, F, T )，(F, T, F )，(F, F, F )。 析取范式如果一个完全指派能使一个合取式取真值，那么这个完全指派和合取式之间是对应的。例如： (T, T, F )，(

19、T, F, F )， (F, T, T )， (F, F, T )p q r p q r p q r p q r 将上述四个合取式再析取，即得析取范式：（p q r）（p q r）（p q r）（p q r）合取范式相仿地：对应于成假指派对应的析取式为：(T, T, T) ，(T, F, T )，(F, T, F )，(F, F, F )pqrpqrpqrp q r将四个析取式再合取，即得合取范式：（pqr）（pqr）（pqr）（pqr）求范式等值变换法n消去和n否定深入到变元n等值变换主范式n主析取范式n主合取范式2.4 联结词的完备集 除了所详述过的五个联结词外, 还可定义更多的联结词。像

20、计算机的硬件电路设计分析就常使用异或(半加) : PQ = (PQ)(PQ)与非: P Q = (PQ)或非: P Q = (PQ)等联结词。问题是对n 个命题变项P1Pn 来说, 共可定义出多少个联结词? 还可以问, 在那么多联结词中有多少是独立的? 2.4.1 命题联结词的个数n按照合式公式的定义，由命题变项和命题联结词可以构造出无限多个合式公式。可把所有的合式公式加以分类 ，将等值的公式视为同一类，从中选一个作代表称之为真值函项。对一个真值函项就有一个联结词与之对应。 n一元联结词是联结一个命题变项的，如P。它取值只有真假两种情形，于是联结词作用于P , 可建立四种不同的真值函项, 相应

21、的可定义出四个不同的一元联结词f0f1f2f3。图6.2.4.1给出这些联结词fi或说真值函数fi(P)的定义。 写出真值函项：f0(P) = Ff1(P) = Pf2(P) = Pf3(P) = T其中f0(P)是永假式, f3(P)是永真式, 均与P无关, 而f1(P)就是变项P本身, 从而新的公式只有f2(P), 这就是由否定词所建立的真值函项。 n二元联结词联结两个命题变项，两个变项PQ共有四种取值情形, 于是联结词作用于PQ可建立起16种不同的真值函项, 相应的可定义出16个不同的二元联结词g0, g1, , g15 。图2.4.2给出了这些联结词gI或说真值函项gi(P, Q)的定

22、义。 写出各真值函项:g0 (P,Q) = Fg1(P,Q) = PQg2(P,Q) = PQg3(P,Q) = (PQ)(PQ) = P(QQ) = Pg4(P,Q) = PQg5(P,Q) = (PQ)(PQ) = (PP)Q = Qg6(P,Q) = PQg7(P,Q) = PQg8(P,Q) = PQ = P Qg9(P,Q) = P Qg10(P,Q) = (PQ)(PQ) = (PP)Q = Qg11(P,Q) = PQ = QPg12(P,Q) = (P Q)(PQ) = P(QQ) = Pg13(P,Q) = PQ = P Qg14(P,Q) = PQ = P Qg15(P,Q

23、) = Tn一般地说，对n 个命题变元P1Pn, 每个Pi有两种取值, 从而对P1Pn来说共有2n种取值情形。于是相应的直值函项就有22n个, 或说可定义22n个n元联结词。2.4.2 联结词的完备集 n由于可定义的联结词的数量是极大的, 需要考虑它们是否都是独立的? 也就是说这些联结词是否能相互表示呢?n定义: 设C是联结词的集合，如果对任一命题公式都有由C中的联结词表示出来的公式与之等值，就说C是完备的联结词集合，或说C是联结词的完备集。 n显然全体联结词的无限集合是完备的, 而, , 就不是完备的。n定理 , , 是完备的联结词集合n从节2.3介绍的由真值表列写逻辑公式的过程可知, 任一

24、公式都可由, , 表示出来, 从而, , 是完备的, 一般情形下, 这定理的证明可使用数学归纳法, 施归纳于联结词的个数来论证。 又由于PQ = (PQ)PQ = (PQ)这说明, 可由, 表示, 可由, 表示, 故, , , 都是联结词的完备集。还可证明, , , 也都是联结词的完备集。但, , , 不是完备的。尽管, , 是完备的, 但使用起来并不够方便, 我们愿意采取折衷方案, 不是仅用两个也不是使用过多的联结词, 还是选用详细讨论过的五个联结词集, , , , , 当然是完备的, 只是相互并不独立。 最小的联结词的完备集基底 n基底：完备的联结词集合的联结词是独立的， 也就是说这些联结

25、词不能相互表示基底 n只含一个联结词的: NK;NAn含两个联结词的:N,C; N,K; N,A; N,NC; F,C; T,NC; C,NE; E,NC; C,NC;n含三个联结词的:F,K,E; F,A,E; T,K,NE; T,A,NE; K,E,NE; A,E,NE;A- K- E- C- N- 基底 n任取四个一元或二元联结词，它们必组不成基底。加法器 Ai 0 0 0 0 1 1 1 1Bi 0 0 1 1 0 0 1 1Ei 0 1 0 1 0 1 0 1_Ci 0 1 1 0 1 0 0 1Ei+1 0 0 0 1 0 1 1 1Ci=(AiBiEi)(AiBiEi)(AiBiEi)(AiBiEi)Ei+1=(AiBiEi)(AiBiEi)(Ai BiEi)(AiBiEi)E1=0Cn+1=En+12.5 对偶式 n假定公式A仅出现 、这三个联结词n定义 将A中出现的、分别以、代换, 得到公式A*, 则称A*是A的对偶式, 或说A和A*互为对偶式。 (PQ)R的对偶式为(PQ)R不难知道, 若(PQ)R = (PR)(QR)成立, 相应的对偶式 (PQ)R = (PR)(QR)也成立。为方便, 若A=A(P1, , Pn)令 A= A(