1、第二章命题逻辑的等值和推理演算,内容：推理形式和推理演算是数理逻辑研究的基本内容。推理演算要用正确的推理：推理形式由前提和结论经蕴涵词联接而成。我们关注正确的推理形式 。正确的推理形式可由逻辑关系符表达。非形式描述：本章对命题等值和推理演算进行的讨论，是以语义的观点进行的非形式的描述。,等值演算(考察逻辑关系符 )： 1)等值定理、公式 2)由真值表写命题公式(由T写、由F写) 3)联结词的完备集(由个别联结词表示所有联结词的问题) 4)对偶式(命题公式的对偶性) 5)范式(命题公式的统一标准),推理演算(考察逻辑关系符 ) ： 1)推理形式(正确推理形式的表示) 2)基本推理公式(各种三段论
2、及五种证明方法) 3)推理演算(证明推理公式的第六种方法，使用推理规则) 4)归结推理法(证明推理公式的第七种方法，常用反证法),2.1.1 等值的定义,等值的定义：给定两个命题公式A和B, 而P1Pn是出现于A和B中的所有命题变项, 那么公式A和B共有2n个解释, 若对其中的任一解释, 公式A和B的真值都相等, 就称A和B是等值的(或等价的)。记作A = B或A B。注意逻辑关系词,2.1 等值定理,例1: 证明(PP)Q = Q,证明: 画出(PP)Q与Q的真值表可看出等式是成立的。,例2: 证明PP = QQ,证明: 画出PP, QQ的真值表, 可看出它们是等值的, 而且它们都是重言式。
3、,等值定义补充说明：两个公式等值并不要求它们一定含有相同的命题变项。若仅在等式一端的公式里有变项P出现, 那么等式两端的公式其真值均与P无关。例1中公式(PP) Q与Q的真值都同P无关, 例2中PP, QQ都是重言式, 它们的真值也都与P、Q无关。,2.1.2 等值定理,定理2.1.1 对公式A和B, A = B的充分必要条件是A B是重言式。 即任意解释下，A和B都有相同的真值。证明：定理中的两部分都与上一行等同。,“”作为逻辑关系符是一种等价关系,A = B是表示公式A与B的一种关系。这种关系具有三个性质: 1. 自反性 A = A。2. 对称性 若A = B则B = A。3. 传递性 若
4、A = B, B = C则A = C。这三条性质体现了“”的实质含义。,2.2 等值公式(真值表验证，Venn图理解),2.2.1 基本的等值公式(特别注意蓝色字)1. 双重否定律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 = T,6. 吸收律P(PQ) = PP(PQ) = P7. 摩根律(PQ)
5、 = PQ(PQ) = PQ对蕴涵词、双条件词作否定有(PQ) = PQ(PQ) = PQ = PQ= (PQ)(PQ),8. 同一律PF = PPT = PTP = PTP = P还有PF = PFP = P,9. 零律PT = TPF = F还有PT = TFP = T10. 补余律PP = TPP = F还有PP = PPP = PPP = F,Venn图,这种图是将P、Q理解为某总体论域上的子集合, 而规定PQ为两集合的公共部分(交集合), PQ为两集合的全部(并集合), P为总体论域(如矩形域)中P的余集。,Venn图实例,1. P(PQ) = P2. P(PQ) = P,3. (P
6、Q) = PQ,Venn图可以用来理解集合间、命题逻辑中、部分信息量间的一些关系。,2.2.2 若干常用的等值公式,等值演算中，由于人们对、更为熟悉，常将含有和的公式化成仅含有、的公式。这也是证明和理解含有，的公式的一般方法。但后面的推理演算中，更希望见到和.,12. 逆否定理PQ=QP,11. PQ = P Q,13. 前提合并P(QR) = (PQ)R,17. 前提交换P(QR) = Q(PR),18. 另一种前提合并(PR) (QR)=(PQ)R,14. 从取真来描述双条件词PQ = (PQ)(PQ),15.从取假来描述双条件词PQ = (PQ)(PQ),16. 从蕴涵词描述双条件词PQ
7、 = (PQ)(QP),2.2.3 置换规则(注意与代入规则p8的区别),置换定义：对公式A的子公式, 用与之等值的公式来代换便称置换。置换规则：将公式A的子公式置换后，A化为公式B, 必有A = B。置换与代入是有区别的：代入规则要求操作重言式、对所有同一命题变元都作代换,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)
8、 (PQ)(PR) = T证明:左端=(PQ)(P(QR)(PQ)(PR)(摩根律)=(PQ)(PQ)(PR)(PQ)(PR) (分配律)=(PQ)(PR)(PQ)(PR)(等幂律)=T(置换规则),问题提出：由命题公式写真值表是容易的，那么如何由真值表写命题公式呢？,2.3 命题公式与真值表关系,2.3.1 从T来列写1.记忆方法：各项间用，每项内用2.每项内书写方法：例 真值表中P=F且Q=F等价于PQ=T3.简化方法：有时A的表达通过A来描述,2.3.2 从F来列写1.记忆方法：各项间用 ，每项内用2.每项内书写方法：例 真值表中P=T且Q=F等价于PQ=F3.简化方法：有时A的表达通过
9、A来描述4.任意值的问题(图2.3.1),2.4 联结词的完备集,问题的提出：对n 个命题变项P1Pn来说, 共可定义出多少个联结词? 在那么多联结词中有多少是相互独立的? 介绍3个新型联结词： 异或 : PQ =(PQ)(PQ)与非 : P Q = (PQ)或非 : P Q = (PQ),2.4.1 命题联结词的个数,要解决本节提出的第一个问题，首先要把n个命题变项构造出的无限多个合式公式分类。将等值的公式视为同一类，从中选一个作代表称之为真值函项。对一个真值函项，或者说对于该类合式公式，就可定义一个联结词与之对应。,例：一元联结词是联结一个命题变项(如P)的。P有真假2种值，因此P(自变量
10、)上可定义4种一元联结词(真值函项、函数)：真值表见图。f0 f1 f2 f3 或称f0(P) f1(P) f2(P) f3(P),由真值表写出真值函项的命题公式：f0(P) = Ff1(P) = Pf2(P) = Pf3(P) = T,例：二元联结词联结两个命题变项(如P、Q)，两个变项共有4种取值情形, 于是P、Q上可建立起16种不同的真值函项, 相应的可定义出16个不同的二元联结词g0, g1, , g15 图2.4.2给出了这些联结词gi或说真值函项gi(P, Q)的真值表定义。,根据真值表写出各真值函项的命题表达式:g0 (P,Q) = Fg1(P,Q) = PQg2(P,Q) =
11、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) = T,联结词个数统计：对n 个命题变元P1Pn, 每个Pi有两种取值, 从而对P1P
12、n来说共有2n种取值情形。 于是相应的直值函项就有22n个, 或说可定义22n个n元联结词。,2.4.2 联结词的完备集,关于本节提出的第二个问题，也就是说这些联结词是否能相互通过组合来表示呢?联结词的完备集定义: 设C是联结词的集合，如果对任一命题公式(能直接使用T和F)都有由C中的联结词表示出来的公式(不能直接使用T和F)与之等值，就说C是完备的联结词集合，或说C是联结词的完备集。,书上的8个完备集(提问)：1.显然全体联结词的无限集合是完备的。 2.定理: , , 是完备的联结词集合。 证明：从2.3节介绍的由真值表列写逻辑公式的过程可知, 任一公式都可由, , 表示出来, 从而, ,
13、是完备的。 8., , , , 是完备的, 因为它包含了2中的集合。另外，, 不是完备的，因为F不能仅由该集合的联结词表达出来。, 也不是完备的。,3. , , 4. , 都是联结词的完备集。证明：PQ = (PQ) PQ = (PQ)这说明, 可由, 表示, 可由, 表示, 故由定理2.4.1可证本结论。5. , 是完备集。证明： 6.是完备集。证明： 7.是完备集。证明：,特别注意,如果一个联结词的集合是不完备的，那么它的任何子集都是不完备的。因此，, 的任何子集都是不完备的。 , 的任何子集也是不完备的。由此可推知，集合3,4,5,6,7都是独立的完备集。事实上，6,7是仅有的两个只有一
14、个联结词的完备集(不证).,不是完备的(不证).,2.5 对偶式,新符号“对偶式”：将A中出现的、T、F分别以、F、T代换, 得到公式A*, 则称A*是A的对偶式, 或说A和A*互为对偶式。 若A = B必有A*=B*?,对仅含 、三个联结词的公式考察相似性,新符号“-”：若A=A(P1, , Pn)令 A= A(P1, , Pn)关于等值的三个定理 (这不是2.1节的等值定理)定理2.5.1 (A*) = (A)*, (A) = (A) 定理2.5.2 (A*)* = A, (A)=A定理2.5.3 摩根律 A = A*,可用数学归纳法, 施归纳于A中出现的联结词个数n来证明。,定理 2.5
15、.4 若A = B必有A*=B*证明: 因为A = B等价于AB 永真等价于AB永真。依定理2.5.3, A = A*, B = B* 于是 A* B* 永真必有 A* B*永真故 A* = B*,关于推理的三个定理,定理2.5.5 若AB永真, 必有B*A*永真定理2.5.6 A与A同永真, 同可满足 A与A*同永真, 同可满足注意： “A与B同永真, 同可满足”的意思是：A永真可推出B永真,反之亦然。,2.6 范式(命题的统一形式),n 个命题变项所能组成的具有不同真值表的命题公式仅有22n个, 然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个。这些等值的公式，能否都可以化为某
16、一个统一的标准形式?,2.6.1 范式,好多新概念文字、合取式、析取式、互补对、析取范式、合取范式范式定理：任一命题公式都存在与之等值的析取范式、合取范式。求范三步曲：1) 消去和2) 否定深入到变元3) 使用分配律的等值变换,范式功能：判断两公式是否等值(参主范式)；判断重言式：合取范式中所有析取式都有互补对；判断矛盾式：析取范式中所有合取式都有互补对；,2.6.2 主范式,主析取范式极小项定义与编码：主析取范式定义主析取范式唯一性定理由真值表写主析取范式(从T写)，例3由析取范式写主析取范式，例4,极小项性质所有极小项的个数极小项为真的唯一解极小项互不相同坐标系功能A与 A的主析取范式关系
17、,主合取范式极大项定义：主合取范式定义主合取范式唯一性定理由真值表写主合取范式(从F写)，例5由合取范式写主合取范式，例6,极大项性质所有极大项的个数极大项为假的唯一解极大项互不相同坐标系功能A与 A的主合取范式关系,主析取范式与主合取范式的转化参见板书！注意补集与数字补的不同含义。,2.7 推理形式,1.通过蕴涵词建立正确(即条件真时，结论必真)或不正确的推理形式例：(PQ)P)Q 是正确的推理形式 (PQ)Q)P是正确的推理形式 (PQ)P)Q是不正确的推理形式,2.正确推理形式的书写方法使用逻辑关系词：重言蕴涵AB表示命题A为真时命题B一定为真,3.重言蕴涵的进一步应用(与2.8.1推理
18、公式不同，是一些推理规则即证明推理公式的方法),如果AB, A为重言式，则B也是重言式。如果AB，BA同时成立，必有A=B。如果AB，BC，则AC。如果AB，AC，则ABC。如果AC，BC，则AB C。,2.8 基本的推理公式,2.8.11. (PQ) P 化简律2. (P Q) P 3. (P Q) Q4. P (PQ) 附加律 5. P P Q6. Q P Q7. (PQ)P Q 析取三段论8. (P Q)P Q 假言推理、分离规则注意2、3、5、6的关系,9. (PQ)Q P 拒取式10. (PQ)(QR) (PR) 假言三段论、三段论11. (PQ)(QR) (PR) 等价三段论12.
19、 (P R)(Q R)(PQ) R 构造性二难(特殊形式)13. (PQ)(RS)(PR) (QS) 构造性二难14. (PQ)(RS)(QS) (PR) 破坏性二难15. (QR) ( (P Q)(P R) )16. (QR) ( (PQ)(PR) ),2.8.2 证明推理公式的5种方法,定理2.8.1 AB成立的充分必要条件是AB为重言式。注意：1)比较定理2.1.1 2)证明AB为重言式的方法：等值演算、主析取范式、真值表,例1 用等值演算法证明(pq)pq为重言式 (pq)pq (pq)p)q (pq)p)q pqq T,例2 用主析取范式法证明(pq)qp不是重言式 (pq)qp (
20、pq)qp (pq)q)p qp (pq)(pq)(pq)(pq) m0 m2 m3 缺少m1即pq, 所以(pq)qp不是重言式，或者说推理形式(pq)qp不正确。,2. 定理2.8.2 AB成立的充分必要条件是AB为重言式即AB为矛盾式。3.逆否定理 AB成立的充分必要条件BA4. 解释法：参考书上p32页例子5. 真值表法：即通过真值表检验A为真时B一定为真。又见方法1中的第3个子方法。,注： 证明AB时不考虑A为假的情况。,2.9 推理演算(证明推理公式AB的新方法),从前提A1, , An出发(即A= A1A2 An)运用推理规则和基本推理公式，逐步推演出结论B，即证明AB 。2.9
21、.1 推理规则前提引入规则：推理中,随时引入前提A1, , An2）结论引用规则：推理中,中间结论作为后续推理前提,3) 代入规则(参考p8)： 推理中,对重言式的命题变项使用4) 置换规则(参考p18): 命题公式任何部分由与之等值的公式置换5) 分离规则（假言推理）: 已知命题公式A和AB为前提条件,则有命题公式B,6) 条件证明规则(附加前提): 利用A1A2B与A1A2 B等价，即结论方的条件移到了前提方。,例1特点：前提引入规则、分离规则例2特点：使用基本推理公式例3特点：置换规则例4特点：条件证明规则(附加前提引入)例5特点: 反证法、条件证明、结论引入,2.10 归结推理法(归结推理规则) (证明推理公式AB的新方法),一、思想1.证明AB等价于证明AB是重言式 等价于证明AB是重言式 等价于证明AB是矛盾式2.用反证法，假设AB在某种解释下为真3.将AB化为合取范式，每个析取式均作为一个前题(子句).这些子句的集合记作S.,4. 对S作归结,消互补对，即使用推理(PR)(PQ)RQ (注意R,Q变形T,F)其中(PR)和(PQ)都是S中的前题(子句).最后导出矛盾。二、具体步骤：见p36例1例21)合取范式2)子句集3)归结过程,
