逻辑学课件：第四章 命题逻辑-5

1、第五节 命题逻辑的自然推理系统NP三、推理规则及形式证明（三）等值置换规则 等值置换规则（记为R.P.）：在形式证明中，具互推关系的公式，可以相互置换。常用的互推关系有：1. A A A A2.德摩根律（记为DeM）: （AB）AB ； （AB）AB 。3.蕴析律：ABAB；第五节 命题逻辑的自然推理系统NP常用的互推关系:4. 对的否定：（AB）AB；5对的否定：（AB）AB； 6假言易位律：AB BA ；7输入输出律：ABCA（BC）8条件交换律： A（BC）B（AC）等值置换规则使用示例(AB)C， AB C(1) (AB)C A1(2) AB A2(3) (AB)C (1), R.P.

2、(蕴析律) (4) C (2),(3), _ 第五节 命题逻辑的自然推理系统NP三、推理规则及形式证明（四）关于联结词的一些逻辑规律 1.(AB) A，(AB) B； 2.A (AB)，B (AB)； 3.AB，AC，BC C (二难推理,记为D.C.)； 4.AB，AC，BCA ( 二难推理)； 5.ABCACB ( 反三段论)； 6.ABC A(BC) (条件输出)； 7.A(BC) ABC (条件输入)；第五节 命题逻辑的自然推理系统NP （四）关于联结词的一些逻辑规律 8.A(BC)(AB)(AC) (蕴涵分配) ； 9.A(BC)B(AC) (条件互易)； 10.AC，BC ABC

3、(前件合取)； 11.AB，AC ABC (后件合取)； 12.ABC(AC)(BC)；13.ABC(AC)(BC)； 以元语言变元表达的NP系统的语法推出关系，每一种都代表了对象语言中无穷多的语法推出关系。(AB) A，就代表了以下无穷多的语法推出关系： (pq) p, (pq) p, (pqr) (pq), (pr)(pq) (pr), 第五节 命题逻辑的自然推理系统NP三、推理规则及形式证明（五）形式证明的应用（1）证明公式集的不一致 如果从一个公式（命题）集合中可以推出逻辑矛盾，那么，这个公式（命题）集合是不一致（不相容、不协调）的。 例如， AB ，A，B 就是不一致的。 证明下列公

4、式集不一致1.ABC，CD，A D(1) ABC A1(2) CD A2(3) A D A3(4)A (3)，_(5) D (3)， _ (6) AB (4)，+(7) C (1)，(6)， _(8) D (2)，(7)，_(9) D D (5)，(8)，+三、推理规则及形式证明（五）形式证明的应用（2）构造日常推理的形式证明例：如果不换8号（p）或12号上场(q)，甲队的形势不会好转(r)。 教练没有换8号上场，也没有换12号上场。 所以，甲队的形势不会好转。 将前提和结论形式化： A A1 1： (pq)(pq) r r A A2 2： pp q q B B： r r(1) (pq) r

5、A1(2) pq A2(3)(pq) (2),R.P.(DeM)(4) r (1)，(3) ,_ 构造日常推理的形式证明 有以下几个条件成立： (1)如果甲是作家(p)，那么乙不是律师(q)； (2)或者丙是作家(r)，或者甲是作家； (3)如果乙不是律师，那么丁不是演员； (4)或者丁是演员(s) ，或者戊不是医生。 (5)戊是医生(t)。求证：丙是作家。 形式化： 前提：p q; r p; qs; s t; t 结论：r(1) p q A1(2) r p A2(3) qs A3(4) s t A4(5) t A5(6) t (5), +(7) s (4),(6), -(8) p s (1)

6、,(3),H.S.(9) s (7), +(10) p (8),(9),M.T.(11)r (2),(10), -第五节 命题逻辑的自然推理系统NP四、命题逻辑的形式语言的语义解释回顾：命题逻辑的形式语言（一）初始符号1.可数无穷多的变元符号：p1, p2, p3，；2.联结词符号：，；3.左括号和右括号：(，)。回顾：命题逻辑的形式语言（二）公式的形成规则1.p，q，r，是公式；2.如果A是公式，那么（A）是公式；3.如果A和B是公式，那么（AB）、（AB）、（AB）都是公式。4.只有13形成的符号串是公式。第五节 命题逻辑的自然推理系统NP 四、命题逻辑的形式语言的语义解释 直观：把原子公

7、式p，q，r，解释为或者为真或者为假的原子命题。 当原子命题的真值确定后，根据形成规则，根据真值条件可确定任何公式的真值。第五节 命题逻辑的自然推理系统NP 四、命题逻辑的形式语言的语义解释 1.A为真当且仅当A为假； 2.AB为真当且仅当A为真并且B为真； 3.AB为真当且仅A为真或者B为真； 4.AB为真当且仅当A为假或者B为真； 5.AB为真当且仅当A和B的真值相同。形式语言L的语义解释 真值指派和真值赋值 真值指派（简称指派）：给每个原子公式指定一个真值的过程，记为。 真值赋值（简称赋值）:给定一个真值指派以后，给每个公式确定一个唯一的真值的过程。这个过程称为由该真值指派导出的真值赋值

8、，记为。 公式A在赋值下的值，记为(A)。设为任一指派，是由导出的赋值。()对任何命题变元p，(p)=(p)，其中(p)已有定义。()(A)=T当且仅当(A)=F;()(AB)=T当且仅当(A)=T并且(B)=T;()(AB)=T当且仅当(A)=T或者(B)= T;()(AB)=T当且仅当(A)=F或者(B)=T。 真值语义学的直观解释 从直观上讲，真值指派实质上是给命题变元指定真值的过程。 (p)=T（(p)=F）就是把p解释为一个真（假）命题。 真值指派导出真值赋值，实质上可看成由命题变元的真值确定复合命题的真值的过程。公式真值的确定 给定一个真值指派: (p)=T, (q)=F, (r)

9、=T,。 根据基本语义解释，可以导出一个真值赋值,以确定由这些命题变元构成的任何公式在下的真值。 例如： (p)=F,(pr)=T,(pqr)=T,(prq)=F，。语义后承 设是一个公式集，B是一个公式，如果对任意赋值任意赋值都有： 如果如果()=T，则则(B B)=T， 则称B是的语义后承,记为：=B 。 ()=T即(A1)=T ,(A2)=T，(An)=T) （=B又称逻辑蕴涵B，能有效地推出B，与B具有语义推出关系）。1.+:A, BAB证明：对任何赋值， 如果（A）=T, （B）=T， 那么，根据基本语义解释()， （AB）=T， 因此：A，B=AB。 这就是说，+具有保真性保真性。

10、 2._2._：AB, AB ； AB, BA (1)假设存在赋值，使得(AB)=T，(A)=T,但是(B)=F； (2) 根据基本语义解释（），由(A)=T，得(A)=F; (3)由(A)=F和(B)=F,根据基本语义解释（），得(AB)=F；（4）（AB）=F，与假设(AB)=T矛盾；因此，假设不成立， 即没有赋值，使得： (AB)=T，(A)=T，但是(B)=F； 所以，AB，A=B。同理，AB,B=A。 可以验证，基本推导规则都具有保真性。重言蕴涵式 A1，A2，An=B当且仅当A1A2 An=B。 A1A2 An=B，即对任何赋值，如果(A1A2An）=T则(B)=T，也就是（A1A

11、2AnB）=T， A1A2AnB是只取真值T的永真蕴涵式或重言蕴涵式。把推理形式转化为重言蕴涵式只要用把诸前提联结为合取式:A1A2An，再把这个合取式用与B联结起来；判定A1A2AnB是否永真（重言）式，就可以判定A1，A2，An是否逻辑蕴涵B。(特例： A=B 和 重言式AB)用真值 表检验语义推出关系 用真值表方法验证用真值表方法验证(AB)， B = A 分析:要证(AB)， B = A，就是证(AB) B A是重言蕴涵式。A B A B(AB) B(AB) B ATTFFFTTFFTFTFTTFFTFFTTTT根据以上真值表，可判定(AB) B A是重言蕴涵式，所以有(AB)， B

12、= A。用真值 表检验语义推出关系（AB）， A = B证明 ABA 证：给定真值指派，满足(p)=F，(q)=T。 是由导出的赋值，有： (p)=F，(q)=T, 根据赋值定义，(pq)=T, 但(p)=F, 所以，pq p ,所以，ABA。证明没有语义推出关系第五节 命题逻辑的自然推理系统NP 五、命题逻辑的自然推理系统NP的性质 1可靠性。 命题逻辑的自然推理系统NP，包含着无穷多的关于联结词的推出关系，这些推出关系，都具有保真性，即，当前提真时，结论必然是真的，而不可能是假的，更不会推出逻辑矛盾。这种性质，称为可靠性。第五节 命题逻辑的自然推理系统NP五、命题逻辑的自然推理系统NP的性质2完全性。 关于联结词的从真前提推出真结论的推出关系，都包括在命题逻辑的自然推理系统NP中了。在NP系统外，再没有从真前提推出真结论的关于联结词推出关系了。总 结 有了可靠性定理和完全性定理之后，证明以下的方法：（1）具语法推出关系（2）不具有语法推出关系（3）具有语义推出关系（4）不具有语义推出关系 第五节 命题逻辑的自然推理系统NP一、形式语言初始符号、形成规则、定义二、有前提的形式推演定义三、推理规则及形式