第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基本内容 推理形式是由前提和结论经蕴涵词联结而成的

Presentation on theme: "第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基本内容 推理形式是由前提和结论经蕴涵词联结而成的"— Presentation transcript:

1 第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基本内容 推理形式是由前提和结论经蕴涵词联结而成的 推理过程是从前提出发，根据所规定的规则来推导出结论的过程 重言式是重要的逻辑规律，正确的推理形式、等值式都是重言式

2 本章对命题等值和推理演算进行讨论，是以语义的观点进行的非形式的描述，不仅直观且容易理解，也便于实际问题的逻辑描述和推理。
严格的形式化的讨论见第三章所建立的公理系统。

3 等值演算(考察逻辑关系符⇔(=)) 等值定理、公式 联结词的完备集(由个别联结词表示所有联结词的问题) 对偶式(命题公式的对偶性)
范式(命题公式的统一标准) 由真值表写命题公式(由T写、由F写)

4 推理演算(考察逻辑关系符⇒) 推理形式(正确推理形式的表示) 基本推理公式(各种三段论及五种证明方法)
推理演算(证明推理公式的第六种方法，使用推理规则) 归结推理法(证明推理公式的第七种方法，常用反证法)

5 2.1 等值定理 在命题逻辑里也同样可建立一些重要的等值式
2.1 等值定理 若把初等数学里的＋、－、×、÷等运算符看作是数与数之间的联结词，那么由这些联结词所表达的代数式之间，可建立许多等值式如下： x2－y2 = (x＋y)(x－y) (x＋y)2 = x2＋2xy＋y2 sin2x＋cos2x = 1 …… 在命题逻辑里也同样可建立一些重要的等值式

6 等值的定义 给定两个命题公式A和B, 而P1…Pn是出现于A和B中的所有命题变项, 那么公式A和B共有2n个解释, 若对其中的任一解释, 公式A和B的真值都相等, 就称A和B是等值的(或等价的)。记作A = B或AB 显然，可以根据真值表来判明任何两个公式是否是等值的

7 例1: 证明(P∧P)∨Q = Q 证明: 画出(P∧P)∨Q与Q的真值表可看出等式是成立的。

8 例2: 证明P∨P = Q∨Q 证明: 画出P∨P, Q∨Q的真值表, 可看出它们是等值的, 而且它们都是重言式。

9 说明 从例1、2还可说明, 两个公式等值并不一定要求它们一定含有相同的命题变项
若仅在等式一端的公式里有变项P出现, 那么等式两端的公式其真值均与P无关。 例1中公式(P∧P)∨Q与Q的真值都同P无关 例2中P∨P, Q∨Q都是重言式, 它们的真值也都与P、Q无关。

10 2.1.2 等值定理 定理 对公式A和B, A=B的充分必要条件是AB是重言式。
等值定理 定理 对公式A和B, A=B的充分必要条件是AB是重言式。 A、B不一定都是简单命题, 可能是由简单命题P1, …, Pn构成的. 对A, B的一个解释, 指的是对P1, …, Pn的一组具体的真值设定. 若AB为重言式, 则在任一解释下A和B都只能有相同的真值, 这就是定理的意思。

11 证明 若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是重言式。 注：根据该等值定理，证明两个公式等值，只要证明由这两个公式构成的双条件式是重言式即可

12 “＝”作为逻辑关系符是一种等价关系 不要将“＝”视作联结词，在合式公式定义里没有“＝”出现
A = B是表示公式A与B的一种关系。这种关系具有三个性质: 1. 自反性 A = A 2. 对称性 若A = B, 则B = A 3. 传递性 若A = B, B = C, 则A = C 这三条性质体现了“＝”的实质含义。

13 2.2 等值公式 2.2.1 基本的等值公式(命题定律, P和Q是任意的命题公式) 1. 双重否定律 P = P 2. 结合律
2.2 等值公式 基本的等值公式(命题定律, P和Q是任意的命题公式) 1. 双重否定律 P = P 2. 结合律 (P∨Q)∨R = P∨(Q∨R) (P∧Q)∧R = P∧(Q∧R) (P  Q)  R = P  (Q  R) 注: 所有这些公式，都可使用真值表加以验证

14 3. 交换律 P∨Q = Q∨P P∧Q = Q∧P P  Q = Q  P 4. 分配律 P∨(Q∧R) = (P∨Q)∧(P∨R) P∧(Q∨R) = (P∧Q)∨(P∧R) P(QR) = (PQ)(PR) 5. 等幂律(恒等律) P∨P = P P∧P = P PP = T PP = T

15 6. 吸收律 P∨(P∧Q) = P P∧(P∨Q) = P 7. 摩根律 (P∨Q) = P∧Q (P∧Q) = P∨Q 对蕴涵词、双条件词作否定有 (PQ) = P∧Q (PQ) = PQ = PQ = (P∧Q)∨(P∧Q)

16 8. 同一律 P∨F = P P∧T = P TP = P TP = P 还有 PF = P FP = P

17 9. 零律 P∨T = T P∧F = F 还有 PT = T FP = T 10. 补余律 P∨P = T P∧P = F PP = P PP = P PP = F

18 Venn图(理解等式) 将P、Q理解为某总体论域上的子集合，并规定： P∧Q为两集合的公共部分(交集合) P∨Q为两集合的全部(并集合)
P为总体论域(如矩形域)中P的余集

19 Venn图(理解等式) 从Venn 图，因P∧Q较P来得“小”, P∨Q较P来得“大”，从而有
P∨(P∧Q) = P P∧(P∨Q) = P

20 理解等式: Venn图，自然语言 (P∨Q) = P∧Q Venn图(理解集合间、命题逻辑中、部分信息量间的一些关系)
对这些等式使用自然用语加以说明，将有助于理解 如P表示张三是学生, Q表示李四是工人, 那么(P∨Q)就表示并非“张三是学生或者李四是工人”。这相当于说，“张三不是学生而且李四也不是工人”，即可由P∧Q表示, 从而有(P∨Q) = P∧Q

21 常用的等值公式 由于人们对、∨、∧更为熟悉，常将含有和的公式化成仅含有、∨、∧的公式。这也是证明和理解含有，的公式的一般方法 公式11-18是等值演算中经常使用的, 也该掌握它们, 特别是能直观地解释它们的成立

22 11. PQ = P ∨Q 通常对PQ进行运算时, 不如用P∨Q来得方便。而且以P∨Q表示PQ帮助我们理解如果P则Q的逻辑含义

23 12. PQ = QP 逆否定理，假言易位 如将PQ视为正定理, 那么QP就是相应的逆否定理, 它们必然同时为真, 同时为假, 所以是等值的

24 13. P(QR) = (P∧Q)R 前提合并 P是(QR)的前提, Q是R的前提, 于是可将两个前提的合取P∧Q作为总的前提。 即如果P则如果Q则R, 等价于如果P与Q则R

25 14. PQ = (P∧Q)∨(P∧Q) 从取真来描述双条件
这可解释为PQ为真, 有两种可能的情形, 即(P∧Q)为真或(P∧Q)为真。而P∧Q为真, 必是在P = Q = T的情况下出现; P∧Q为真, 必是在P = Q = F的情况下出现。从而可说, PQ为真, 是在P、Q同时为真或同时为假时成立。这就是从取真来描述这等式

26 15. PQ = (P∨Q)∧(P∨Q) 从取假来描述双条件
这可解释为PQ为假, 有两种可能的情形, 即(P∨Q)为假或(P∨Q)为假, 而P∨Q为假, 必是在P = F, Q = T的情况下出现; P∨Q为假, 必是在P = T, Q = F的情况下出现。从而可说PQ为假, 是在P真Q假或P假Q真时成立。这就是从取假来描述这等式

27 16. PQ = (PQ)∧(QP) 从蕴含词来描述双条件 这表明PQ成立, 等价于正定理PQ和逆定理QP都成立

28 17. P(QR) = Q(PR) 前提交换 前提条件P、Q可交换次序

29 18. (PR)∧(QR)=(P∨Q)R 左端说明的是由P而且由Q都有R成立。从而可以说由P或Q就有R成立, 这就是等式右端

30 补充 等价否定等值式 PQ = PQ 归谬论 (PQ)(PQ) = P

31 2.2.3 置换规则 置换定义 对公式A的子公式, 用与之等值的公式来代换便称置换 置换规则
置换规则 置换定义 对公式A的子公式, 用与之等值的公式来代换便称置换 置换规则 公式A的子公式置换后A化为公式B, 必有A = B 当A是重言式时, 置换后的公式B必也是重言式 置换与代入是有区别的。置换只要求A的某一子公式作代换, 不必对所有同一的子公式都作代换

32 代入规则回顾 A是一个公式，对A使用代入规则得公式B，若A是重言式，则B也是重言式 为保证重言式经代入规则仍得到保持，要求
公式中被代换的只能是命题变元(原子命题), 而不能是复合命题 对公式中某命题变元施以代入，必须对该公式中出现的所有同一命题变元代换以同一公式

33 2.2.4 等值演算举例 例1: 证明(P∧(Q∧R))∨(Q∧R)∨(P∧R) = R 证明:
等值演算举例 例1: 证明(P∧(Q∧R))∨(Q∧R)∨(P∧R) = R 证明: 左端= (P∧(Q∧R)) ∨((Q∨P)∧R) (分配律) = ((P∧Q)∧R))∨((Q∨P)∧R) (结合律) = ((P∨Q)∧R)∨((Q∨P)∧R) (摩根律) = ((P∨Q)∨(Q∨P))∧R (分配律) = ((P∨Q)∨(P∨Q))∧R (交换律) = T∧R (置 换) = R (同一律)

34 举例 例2: 试证 ((P∨Q)∧(P∧(Q∨R))) ∨(P∧Q)∨(P∧R) = T 证明:
=((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (分配律) =((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (等幂律) =T

35 2.3 命题公式与真值表关系 问题提出： 由命题公式写真值表是容易的，那么如何由真值表写命题公式呢？

36 2.3.1 从T来列写 记忆方法：各项间用∨，每项内用∧ 每项内书写方法：例 真值表中P=T且Q=F等价于P∧Q=T
简化方法：有时A的表达通过A来描述

37 2.3.2 从F来列写 记忆方法：各项间用∧ ，每项内用∨ 每项内书写方法：例 真值表中P=T且Q=F等价于P∨Q=F
简化方法：有时A的表达通过A来描述

38 举例 从A的真值T 从B的真值F 当C可取任意值 P Q A ¬A B C F T X B = (¬P ∨ Q) ∧ (¬P ∨ ¬Q)
直接: A = (¬P ∧¬Q) ∨ (¬P ∧Q) ∨ (P ∧Q) 间接: A = ¬¬A = ¬(P ∧¬Q) = ¬P ∨ Q 从B的真值F B = (¬P ∨ Q) ∧ (¬P ∨ ¬Q) 当C可取任意值 C与{P, Q} = {T, T}无关, 可适当选取C的真值, 使其表达式简单 P Q A ¬A B C F T X

39 作业(1) (P37) 1(1, 3), 2

40 2.4 联结词的完备集 问题的提出 对n 个命题变项P1…Pn来说, 共可定义出多少个联结词? 在那么多联结词中有多少是相互独立的?
2.4 联结词的完备集 问题的提出 对n 个命题变项P1…Pn来说, 共可定义出多少个联结词? 在那么多联结词中有多少是相互独立的? 3个新联结词： 思考：考虑异或联结词与双条件联结词的关系(可利用真值表)

41 2.4.1 命题联结词的个数 第一个问题。可定义多少个联结词？ 由命题变项和命题联结词可以构成无限多个合式公式
命题联结词的个数 第一个问题。可定义多少个联结词？ 由命题变项和命题联结词可以构成无限多个合式公式 把所有的合式公式分类：将等值的公式视为同一类，从中选一个作代表称之为真值函项。对一个真值函项，或者说对于该类合式公式，就可定义一个联结词与之对应 例：等价类。自然数集合N被3除余数相同的自然数构成3个集合N0 , N1 , N2

42 一元联结词的个数 一元联结词是联结一个命题变项(如P)的
P有真假2种值，因此P(自变量)上可定义4种一元联结词fi 或说真值函项fi(P), i = 1, 2, 3, 4

43 一元联结词 由真值表写出真值函项的命题公式： f0(P) = F (永假式) f1(P) = P (P自身)
f3(P) = T (永真式) 新的公式只有f2(P), 与之对应的联结词是否定词

44 二元联结词的个数 二元联结词联结两个命题变项(如P、Q)
两个变项共有4种取值情形,于是P、Q上可建立起16种不同的真值函项,相应的可定义出16个不同的二元联结词g0, g1, …, g15 图2.4.2给出了这些联结词gi或说真值函项gi(P,Q)的真值表定义

45

46 根据真值表写出各真值函项的命题表达式: g0(P,Q) = F (永假式) g1(P,Q) = P∧Q (合取式) g2(P,Q) = P∧Q g3(P,Q) = (P∧Q)∨(P∧Q) = P∧(Q∨Q) = P g4(P,Q) = P∧Q g5(P,Q) = (P∧Q)∨(P∧Q) = (P∨P)∧Q = Q g6(P,Q) = P Q (异或式) g7(P,Q) = P∨Q (析取式) g8(P,Q) = P∧Q = P  Q (或非式) g9(P,Q) = P Q (双条件式) g10(P,Q) = (P∧Q)∨(P∧Q) = (P∨P)∧Q = Q g11(P,Q) = P∨Q = QP (蕴涵式) g12(P,Q) = (P∧ Q)∨(P∧Q) = P∧(Q∨Q) = P g13(P,Q) = P∨Q = PQ (蕴涵式) g14(P,Q) = P∨Q = P  Q (与非式) g15(P,Q) = T (永真式)

47 n元联结词的个数 n元联结词 对n个命题变元P1 , … , Pn , 每个Pi有两种取值, 从而对P1…Pn来说共有2n种取值情形

48 2.4.2 联结词的完备集 第二个问题。联结词是否都是独立的，或者说能否相互表示?
联结词的完备集 第二个问题。联结词是否都是独立的，或者说能否相互表示? 联结词的完备集定义: 设C是联结词的集合，如果对任一命题公式(能直接使用T和F)都有由C中的联结词表示出来的公式(不能直接使用T和F)与之等值，就说C是完备的联结词集合，或说C是联结词的完备集。

49 完备集 1. 全体联结词的无限集合是完备的 2. { , ∨, ∧}是完备的联结词集合
证明：从2.3节介绍的由真值表列写逻辑公式的过程可知, 任一公式都可由, ∨, ∧表示出来, 从而{, ∨, ∧}是完备的 3. {, ∨}是联结词的完备集(独立的完备集) 证明：P∧Q = (P∨Q)，因此∧可由{, ∨}表示 4. {, ∧}是联结词的完备集(独立的完备集) 证明：P∨Q = (P∧Q)，因此∨可由{, ∧}表示

50 完备集 5. {, }是完备集(独立的完备集) 6. {}是完备集(独立的完备集) 7. {}是完备集(独立的完备集)
因为：P∨Q = PQ 6. {}是完备集(独立的完备集) 7. {}是完备集(独立的完备集) 8. {, ∧, ∨, , }是完备的 因为它包含了2中的集合

51 不完备集 {∨,∧,, }不是完备的 因为F不能仅由该集合的联结词表达出 {, }不是完备的
{∨,∧,, }的任何子集都是不完备的 {, }的任何子集也是不完备的 (如果一个联结词的集合是不完备的，那么它的任何子集都是不完备的) {∨,∧}不是完备的

52 最小的联结词的完备集—基底 基底：完备的联结词集合的联结词是独立的，也就是说这些联结词不能相互表示
任取四个一元或二元联结词，它们必组不成基底

53 基底 只含一个联结词的: NK;NA 含两个联结词的:
N,C; N,K; N,A; N,NC; F,C; T,NC; C,NE; E,NC; C,NC 含三个联结词的: F,K,E; F,A,E; T,K,NE; T,A,NE; K,E,NE; A,E,NE 其中：A-- ∨ K-- ∧ E--  C--  N-- 

54 2.5 对偶式 研究目的 简化等值公式的讨论 希望一个公式成立，能够导出与其“相像”的公式成立 逻辑关系上看，是一种逻辑规律 对偶式定义：将A中出现的∨、∧、T、F分别以∧、∨、F、T代换, 得到公式A*, 则称A*是A的对偶式, 或说A和A*互为对偶式 注：这里假定A中仅出现 、∨、∧三个联结词 若A = B，必有A*=B*?

55 对偶式相关定理 新符号“-”: (代入规则、内否式) 若A=A(P1, …, Pn)，令A－= A(P1, …, Pn)
关于等值的三个定理 定理2.5.1 (A*) = (A)*, (A－) = (A)－ 定理 (A*)* = A, (A－)－=A 定理2.5.3 A = A*－ (摩根律的另一种形式) 更多：(A  B)* = A*  B*，(A  B)- = A-  B- (A  B)* = A*  B*，(A  B)- = A-  B-

56 性质举例 A= (P  (Q  R)) T A*= (P  (Q  R))  F

57 定理2.5.3 A = A*－ 证明: 可用数学归纳法, 施归纳于A中出现的 联结词个数n来证明 基始: 设n=0, A中无联结词, 便有
A=P, 从而 A = P 但 A*－ = P ∴ n=0时定理成立。

58 定理2.5.3 A = A*－ 归纳： 设n ≤k时定理成立，来证n = k+1时定理也成立
∵ n = k + 1 ≥1, A中至少有一个联结词，可分为三种情形 A = A1, A = A1∧A2, A = A1∨A2 其中A1, A2中联结词个数≤k。 依归纳法假设，A1 = A1*－, A2 = A2*－

59 定理2.5.3 A = A*－ 当 A = A1时 A = (A1) A = A1 = (A1*－) 归纳法假设

60 定理2.5.3 (摩根律) A = A*－ 当 A = A1∧A2时， A = (A1∧A2) = A1∨A2 摩根律
另一种情况同理，从而定理得证。

61 对偶式相关定理 定理2.5.6 (1) A与A－同永真, 同可满足 (2) A与A*同永真, 同可满足
注：“A和B”同永真表示：A永真当且仅当B永真 证明：设A是由命题变项P1,…,Pn构成的命题公式。 (1) 如果A永真，根据代入规则，则A-永真。 如果A-永真，则(A-)-永真，又根据定理2.5.2有 A=(A-)-, 所以A永真 (2) 根据定理2.5.3，A = A*－，所以根据(1)可得(2)成立

62 对偶式相关定理 定理 2.5.4 若A = B，必有A*=B* 证明: 因为A = B等价于AB 永真等价于AB永真。
依定理2.5.3, A = A*－, B = B*－ 于是A*－ B*－永真， 则(A*- B*-)-永真(根据代入规则，A永真，A-永真) 亦即 A*  B* 永真 故 A* = B*

63 对偶式相关定理 定理2.5.5 若AB永真, 必有B*A*永真 或者，AB和B*A*同永真 证明:
所以B*-A*-永真，则(B*-A*-)-永真(代入规则)， 即B*A*永真 (2) 如果B*A*永真，根据(1)有: (A*)*(B*)*永真 根据定理2.5.2，A=(A*)*, B=(B*)* 所以AB永真 ☐

64 作业(2) (P37) 3，4(2)

65 2.6 范式 n 个命题变项所能组成的具有不同真值的命题公式仅有22n个, 然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个
2.6 范式 n 个命题变项所能组成的具有不同真值的命题公式仅有22n个, 然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个 等值的公式，能否都可以化为某一个统一的标准形式？ 希望这种标准形能为我们的讨论带来些方便，如借助于标准形对任意两个形式上不同的公式，可判断它们的是否等值 借助于标准形容易判断任一公式是否为重言式或矛盾式

66 2.6.1 范式 若干术语 简单命题P及其否定式P统称为文字 一些文字的合取称为合取式 一些文字的析取称为析取式(也称子句)
范式 若干术语 简单命题P及其否定式P统称为文字 一些文字的合取称为合取式 一些文字的析取称为析取式(也称子句) P与P称为互补对 析取范式，形如：A1∨A2∨ … ∨An 其中Ai(i=1, …, n)为合取式 合取范式，形如： A1∧A2∧ … ∧An 其中Ai(i=1, …, n)为析取式

67 范式举例 p, q p1∨p2 , q1∧q2

68 范式定理 范式定理：任一命题公式都存在与之等值的析取范式、合取范式 求范式三步曲： 1) 消去和 2) 否定深入到命题变项
3) 使用分配律的等值变换

69 举例 求¬(P∨Q)(P∧Q)的析取范式 ¬(P∨Q)(P∧Q) =(¬(P∨Q)∧(P∧Q))∨(¬¬(P∨Q)∧¬(P∧Q))
=(¬P∧¬Q∧P∧Q)∨(P∧¬P)∨(P∧¬Q)∨(Q∧¬P)∨(Q∧¬Q) (析取范式) = (P∧¬Q)∨(Q∧¬P) (析取范式，简化) 注：范式的不唯一性

70 举例 求¬(P∨Q)(P∧Q)的合取范式 ¬(P∨Q)(P∧Q) =(P∧¬Q)∨(Q∧¬P) (析取范式，简化)
=(P∨Q)∧(P∨¬P)∧(¬Q∨Q)∧(¬Q∨¬P) (合取范式) =(P∨Q)∧(¬Q∨¬P) (合取范式，简化) 注：已知一种范式，可以使用分配律求另一种范式

71 范式功能 判断重言式 合取范式中所有析取式都有互补对 判断矛盾式 析取范式中所有合取式都有互补对 判断两公式是否等值
范式不唯一，引入唯一的主范式， 便于判别公式相等

72 2.6.2 主范式 主析取范式 极小项必须含有Q1, …, Qn全部n个文字 极小项定义与编码
Q1∧…∧Qn是由n个命题变项P1, …, Pn组成的公式, 其中Qi=Pi或者¬Pi, 我们称其为极小项, 一般用mj表示 例：P1, P2的极小项有四个 ¬P1∧ ¬P2 (m0), ¬P1∧ P2 (m1), P1∧ ¬P2 (m2), P1∧P2 (m3) 主析取范式定义 仅由极小项构成的析取范式 主析取范式唯一性定理 任一含有n个命题变项的公式，都有唯一一个与之等值的恰仅含这n个命题变项的主析取范式 极小项必须含有Q1, …, Qn全部n个文字

73 主析取范式 由真值表写主析取范式：从T写 P  Q=(¬P∧¬Q)∨(P∧Q)=m0∨m3= ∨0,3
F T m1 m2 m3 由真值表写主析取范式：从T写 P  Q=(¬P∧¬Q)∨(P∧Q)=m0∨m3= ∨0,3 由析取范式写主析取范式：填满命题变项法, 永真式 ¬P = ¬P∧(Q∨¬Q) = (¬P∧Q)∨(¬P∧¬Q) Q = Q∧(P∨¬P) = (Q∧P)∨(Q∧¬P) P→Q = ¬P∨Q = (¬P∧Q)∨(¬P∧¬Q) ∨ (Q∧P)∨(Q∧¬P) = (¬P∧¬Q)∨(¬P∧Q)∨(P∧Q) = m0∨m1∨m3 = ∨0,1,3

74 极小项性质 所有可能极小项的个数：2n 每个极小项只在一个解释下为真 对于每个解释只有一个极小项为真
极小项互不相等，且mi ∧ mj=F (i ≠ j) 任一含有n个变项的公式，都可由k个(k≤2n)极小项的析取来表示；或者说所有的极小项可建立一个“坐标系” 恰由2n个极小项的析取构成的公式，必为重言式 A与A的主析取范式关系 A由k个极小项的析取组成，那么其余的2n-k个极小项的析取必是A．例如P1, P2, P3构成的A= ∨0,2,4, A= ∨1,3,5,6,7

75 主合取范式 极大项定义与编码 Q1∨ … ∨Qn是由n个命题变项P1, …, Pn组成的公式, 其中Qi=Pi或者¬Pi(i = 1, …, n), 我们称其为极大项, 一般用Mj表示(0≤j≤2n-1) 例：P1, P2的极大项有四个 ¬P1∨¬P2 (M0), ¬P1∨P2 (M1), P1∨¬P2 (M2), P1∨P2 (M3) 主合取范式定义 仅由极大项构成的合取范式 主合取范式唯一性定理 任一含有n个命题变项的公式，都有唯一一个与之等值的恰仅含这n个命题变项的主合取范式 由真值表写主合取范式(从F写) 由合取范式写主合取范式(填满命题变项法, 矛盾式) 极大项必须含有Q1, …, Qn全部n个文字

76 极大项性质 所有可能极大项的个数：2n 每个极大项只在一个解释下为假 对于每个解释只有一个极大项为假
极大项互不相等，且Mi ∨ Mj=T (i ≠ j) 任一含有n个变项的公式，都可由k个(k≤2n)极大项的合取来表示；或者说所有的极大项可建立一个“坐标系” 恰由2n个极大项的合取构成的公式，必为矛盾式 A与A的主合取范式关系 A由k个极大项的合取组成，那么其余的2n-k个极大项的合取必是A．例如P1, P2, P3构成的A= ∧0,2,5, A= ∧1,3,4,6,7

77 主析取范式与主合取范式的转换 设A是由命题变项P1, P2, P3构成的公式 已知主析取范式 已知主合取范式
极小项编码 P1 P2 P3 A 极大项编码 m0 F T M７ m1 M６ m2 M５ m3 M４ m4 M３ m5 M２ m6 M１ m7 M０

78 主析取范式与主合取范式的转换 注意 从真值表列写公式的主析取范式和主合取范式时，除了分别从T和F列写外，在填写合取式和析取式时是取变项还是其否定是有区别的，这就是主合取范式、主析取范式转换过程要求补的原因 数字补不同于补集。这里的数字求补是对2n-1=23-1=7而言的，如2的补是5，因为2+5=7

79 主范式的用途——与真值表相同 (1) 求公式的成真赋值和成假赋值 例如： (PQ)R  m1m3m5 m6m7，
其成真指派为001, 011, 101, 110, 111， 其余的指派 000, 010, 100为成假指派. 类似地，由主合取范式也可立即求出成假指派和 成真指派

80 主范式的用途(续) (2) 判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为T
A为矛盾式 A的主析取范式为F  A的主合取范式含2n个极大项 A为非重言式的可满足式 A的主析取范式中至少含一个且不含全部极小项 A的主合取范式中至少含一个且不含全部极大项

81 主范式的用途(续) 判断两个公式是否等值 例 用主析取范式判断下述两个公式是否等值： ⑴ P(QR) 与 (PQ)R
解 P(QR) = m0m1m2m3m4m5m7 (PQ)R = m0m1m2m3m4m5m7 (PQ)R = m1m3 m4m5 m7 显见，⑴中的两公式等值，而⑵的不等值.

82 作业(3) (P37) 5(1，5，8)

83 2.7 推理形式 自然语言推理 推理形式 前提1：如果我今天病了，那么我没来上课 前提2：今天我病了 结论：所以今天我没来上课
引入符号, 形式化并用条件式表示出来 例：((PQ)∧P)Q 正确的推理形式 前提真，结论必真的推理形式 ((PQ)∧Q)P 正确的推理形式 ((PQ)∧P)Q 不正确的推理形式 PQ P Q

84 重言蕴涵 重言蕴涵 重言蕴涵与正确推理形式 用真值表法判断A  B
对于公式A, B, 如果当A取值为真时，B必取值为真，则称A重言(永真)蕴涵B，或称B是A的逻辑推论。记为： A  B(是真值关系，并非逻辑联结词) 重言蕴涵与正确推理形式 如果A  B，则AB是正确的推理形式 如果AB是正确的推理形式，可以用A  B来表示 用真值表法判断A  B 查看真值表，如果所有使A为真的解释，亦能使B为真，则A  B

85 重言蕴涵的结果 如果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

86 2.8 基本的推理公式 1. (P∧Q)  P 化简律 2. (PQ)  P 3. (PQ)  Q
6. Q  PQ 7. (P∨Q)∧P  Q 析取三段论 8. (PQ)∧P  Q 假言推理、分离规则

87 基本的推理公式 9. (PQ)∧Q  P 拒取式 10. (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) 破坏性二难 15. (QR)  ((P∨Q)(P∨R)) 16. (QR)  ((PQ)(PR)) 注：真值表证明，或者语义上直接说明

88 2.8.2 证明推理公式的方法(五种) A  B成立的充分必要条件是AB(或¬A∨B) 为重言式
证明推理公式的方法(五种) A  B成立的充分必要条件是AB(或¬A∨B) 为重言式 证明：如果A  B, 那么在任一解释下, A真B必真, 而不会出现A真B假的情况, 于是AB为重言式。 如果AB为重言式, 则在任一解释下, 若A为真, B只能为真不可能为假, 从而有A  B 证明AB为重言式的方法 真值表、等值演算、范式

89 举例 例1 用等值演算法证明(PQ)∧PQ为重言式 (PQ)∧PQ ¬((¬P∨Q)∧P)∨Q ((P∧¬Q)∨¬P)∨Q
 T

90 举例 例2 用主析取范式法证明(PQ)∧QP不是重言式 (PQ)∧QP ¬((¬P∨Q)∧Q)∨P
((¬Q∧P)∨(¬Q∧¬P))∨((P∧Q)∨(P∧¬Q))  (¬P∧¬Q)∨(P∧¬Q)∨(P∧Q)  m0∨m2∨m3 缺少m1即(¬P∧Q), 所以(PQ)∧QP不是重言式，或者说推理形式(PQ)∧QP不正确

91 证明推理公式的方法 2. AB成立的充分必要条件是AB为重言式, 即A∧¬B是矛盾式
3. (逆否定理) AB成立的充分必要条件¬B ¬A 4. 解释法 　例: (PQ)∧(QR)  (PR) 若(PQ)∧(QR)＝T, 则同时有PQ＝T, QR=T 若P=T, 则Q=T, 进而R=T. 故PR＝T 若P=F, 则Q可取任意值: (1) Q=T, 则R=T; (2) Q=F, 则R取何值 无论如何, PR=T 5. 真值表法, 即通过真值表检验A为真时B一定为真 注： 证明AB时不考虑A为假的情况

92 上述方法的特点 都是从真值的角度进行论证和解释 看不出由前提A到结论B的推演过程 难于扩展到谓词逻辑的推演过程

93 2.9 推理演算(证明推理公式AB的新方法) 基本思想：从前提A1, …, An出发(即A= A1A2 … An)运用推理规则和基本推理公式，逐步推演出结论B，即证明AB 推理规则 前提引入规则 推理过程中可以随时引入前提A1, …, An 结论引用规则 推理过程中得到的中间结论可作为后续推理的前提 代入规则(参考P8) 推理过程中对重言式的命题变项可使用该规则

94 推理规则 置换规则(参考P18) 推理过程中命题公式中任何部分公式都可由与之等值的公式置换 分离规则(假言推理)
已知命题公式AB和A, 则有命题公式B(B被分离出来) 条件证明规则(附加前提) A1  A2B与A1A2  B是等价的。即结论方的条件A2移到了前提方, 作为条件使用。

95 举例 例1 证明R是PQ, QR, P的逻辑推论 特点: 前提引入规则、分离规则
例2 证明R∨S可以由前提C∨D, (C∨D)¬E, ¬E(A∧¬B ), (A∧¬B)R∨S推演出来 特点: 基本推理公式(三段论) 例3 证明(P∨Q)∧(PR)∧(QS)  S∨R 特点: 置换规则 例4 证明(P(QS))∧(¬R∨P)∧Q  RS 特点: 条件证明规则(附加前提引入) 例5 证明 (¬(PQ)¬(R∨S))∧((QP)∨¬R)∧R  (PQ) 特点: 反证法、条件证明、结论引入

96 2.10 归结推理法(证明推理公式AB的新方法)
特点 定理机器证明方法 只有一条归结推理规则 易于机器实现 可推广到谓词逻辑推理 基本思想 证明AB等价于证明AB是矛盾式 用反证法, 即假设AB在某种解释下为真, 最后导出矛盾, 得以证明

97 归结证明过程 从AB出发建立子句集S 将AB化为合取范式, 每个析取式均作为一个子句, 构成这些子句的集合, 记为S 对S作归结
直至归结出矛盾, 结束 即出现P与P

98 归结推理规则 归结式定义 设R1=P∨Q1, R2=P∨Q2为两个子句 推理规则 R1R2  R(R1, R2) 有互补对P和P
则新子句R(R1, R2)= Q1∨Q2称为R1, R2的归结式 推理规则 R1R2  R(R1, R2) 设在任一解释下, R1R2=T, 则R1=T且R2=T 若P=T, 则P=F, Q2=T, R(R1, R2)= Q1∨Q2=T 若P=F, 则P=T, Q1=T, R(R1, R2)= Q1∨Q2=T 若Q1=T或者Q2=T, 都有R(R1, R2)= Q1∨Q2=T

99 举例 证明(PQ)∧(QR)  (PR) 1. 将(PQ)∧(QR) ∧ ¬(PR)化成合取范式
2. 建立子句集 S={¬P∨Q, ¬Q∨R, P, ¬R} 3. 归结过程 (1)¬P∨Q (2)¬Q∨R (3)P (4)¬R (5)¬P∨R (1)(2)归结，新子句 (6)R (3)(5)归结 (7) (4)(6)归结

100 作业(4) (P37) 7(10,11), 9(1), 12(1)