离散数学 命题逻辑推理

1、1主要内容主要内容推理的形式结构推理的形式结构l 推理的正确与错误推理的正确与错误l 推理的形式结构推理的形式结构l 判断推理正确的方法判断推理正确的方法l 推理定律推理定律自然推理系统自然推理系统Pl 形式系统的定义与分类形式系统的定义与分类l 自然推理系统自然推理系统Pl 在在P中构造证明中构造证明:直接证明法、附加前提证明法、归谬法直接证明法、附加前提证明法、归谬法第三章第三章 命题逻辑的推理理论命题逻辑的推理理论23.1 推理的形式结构推理的形式结构推理推理：从前提出发推导出结论思维过程，：从前提出发推导出结论思维过程，前提前提 是已知的命题公式集合，是已知的命题公式集合，结论结论 是

2、从前提出发应用推理规则推出的命题公式。是从前提出发应用推理规则推出的命题公式。什么样的推理是正确的有效的？什么样的推理是正确的有效的？定义定义3.1 设设A1, A2, , Ak, B为命题公式为命题公式. 若对于每组赋值，若对于每组赋值，A1 A2 Ak 为假为假，或或当当A1 A2 Ak为真为真时时B也为真，也为真，则则称由称由前提前提A1, A2, , Ak推出推出结论结论B的的推理推理是是有效的有效的或或正确正确的的, 并称并称B是是有效结论有效结论.定理定理3.1 由命题公式由命题公式A1, A2, , Ak 推出推出B的的推理正确推理正确当且仅当当且仅当A1 A2 AkB为重言式为

3、重言式注意注意: 推理正确不能保证结论一定正确推理正确不能保证结论一定正确注：注：1 1）由前提集合）由前提集合A1A1，A2A2，A3A3，Am Am 推出推出B B的推理是否是有的推理是否是有效的与前提集合各命题公式的效的与前提集合各命题公式的次序无关次序无关。 2 2）由推理）由推理形式形式A A1 1AA2 2AAm m B B 取得取得真值的几种情况真值的几种情况： a a) ) A A1 1AA2 2AAm m 真值为真值为F F ， B B为为F F b)b) A A1 1AA2 2AAm m 真值为真值为F F ， B B为为T T c) c) A A1 1AA2 2AAm m

4、 真值为真值为T T ， B B为为F F d) d) A A1 1AA2 2AAm m 真值为真值为T T ， B B为为T T 当取得当取得a)a)、b)b)、d) d) 三种情况均称为三种情况均称为有效推理有效推理 3 3）由推理有效的定义可得出：）由推理有效的定义可得出： 推理有效推理有效（推理正确）并（推理正确）并不不能保证结论能保证结论B B一定为真一定为真 推理推理有效（推理正确）是指推理有效（推理正确）是指推理过程是合乎逻辑过程是合乎逻辑的的 （即：只要前提集合是真的，那么结论一定是真的）（即：只要前提集合是真的，那么结论一定是真的）4推理的形式结构推理的形式结构2. A1 A

5、2 AkB 若推理正确若推理正确, 记为记为A1 A2 Ak B3. 前提：前提： A1, A2, , Ak 结论：结论： B判断推理是否正确的方法判断推理是否正确的方法: 真值表真值表法：法： 没有前提真而结论假的情况没有前提真而结论假的情况 等值演算等值演算法：重言式法：重言式 主析取范式主析取范式法：含所有极小项法：含所有极小项推理的推理的形式结构形式结构1. A1, A2, , Ak B 若推理正确若推理正确, 记为记为A1,A2,An B例：前提公式：例：前提公式： A1A1：，A2A2 ， 结论结论 B B 真值表为真值表为 P Q PQ P A1 A2 BP Q PQ P A1

6、A2 B 0 0 0 0 1 11 1 1 1 0 0 0 1 0 1 1 11 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 1 可知可知 B B不是不是A1,A2A1,A2的有效的有效结论结论例：前提公式例：前提公式 A1A1：，A2A2， 结论结论 B B 真值表为真值表为 P Q PQ P A1 A2 BP Q PQ P A1 A2 B 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 1 11 1 1 1 1

7、1 可知可知 B B 是是A1,A2A1,A2的有效结论的有效结论6推理实例推理实例例例1 判断下面推理是否正确判断下面推理是否正确(1) 若今天是若今天是1号，则明天是号，则明天是5号号. 今天是今天是1号号. 所以所以, 明天是明天是5号号. (2) 若今天是若今天是1号，则明天是号，则明天是5号号. 明天是明天是5号号. 所以所以, 今天是今天是1号号. 解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号. (1) 推理的形式结构推理的形式结构: (pq) pq用等值演算法用等值演算法 (pq) pq ( p q) p) q pq q 1 由定理由定理3.1可知推理正确可知

8、推理正确7推理实例推理实例(2) 推理的形式结构推理的形式结构:(pq) qp 用主析取范式法用主析取范式法 (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 结果不含结果不含m1, 故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确8推理定律推理定律重言蕴涵式重言蕴涵式用定义构造推理过程，需要一些有用的推理定律用定义构造推理过程，需要一些有用的推理定律1. A (A B) 附加律附加律 2. (A B) A 化简律化简律3. (AB) A B 假言推理假言推理4. (AB)B A 拒取式拒取式 5. (

9、A B)B A 析取三段论析取三段论6. (AB) (BC) (AC) 假言三段论假言三段论7. (AB) (BC) (AC) 等价三段论等价三段论8. (AB) (CD) (A C) (B D) 构造性二难构造性二难 (AB) ( AB) B 构造性二难构造性二难(特殊形式特殊形式)9. (AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如, 由由AA可产生可产生 AA 和和 AA93.2 自然推理系统自然推理系统P定义定义3.2 一个一个形式系统形式系统 I 由下面四个部分组成：由下面四个部分组成： (1) 非空的字母

10、表，记作非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作推理规则集，记作 R(I). 记记I=, 其中其中是是 I 的的形式语言形式语言系统系统, 是是 I 的的形式演算系统形式演算系统.自然推理自然推理系统：系统：无无公理公理, 即即AX(I)=公理推理公理推理系统：系统：推出推出的结论是系统中的重言式的结论是系统中的重言式, 称作称作定理定理103.2 自然推理系统自然推理系统 P定义定义3.3

11、 自然推理系统自然推理系统 P 定义定义如下如下:1. 字母表字母表 (1) 命题变项符号：命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：联结词符号： , , , , (3) 括号与逗号：括号与逗号：(, ), ，2. 合式公式（同定义合式公式（同定义1.6）3. 推理规则推理规则 (1) 前提引入前提引入规则规则 P：在证明的任何步骤都可以引入前提：在证明的任何步骤都可以引入前提 (2) 结论引入结论引入规则规则 T：在证明中得到的结论可以作为后继证：在证明中得到的结论可以作为后继证明的前提明的前提 (3) 置换置换规则规则 T ：可以使用等值的公式置换，得

12、到新的公：可以使用等值的公式置换，得到新的公式式11推理规则推理规则(4) 假言推理规则假言推理规则 (6) 化简规则化简规则 (8) 假言三段论规则假言三段论规则 AB AB AA B A B A(5) 附加规则附加规则 (7) 拒取式规则拒取式规则 (9) 析取三段论规则析取三段论规则 AB B A AB BCACA B BA12推理规则推理规则(10) 构造性二难推理规则构造性二难推理规则 (11) 破坏性二难推理规则破坏性二难推理规则 (12) 合取引入规则合取引入规则 AB CD A C B D AB CD BD A C A BA C13在自然推理系统在自然推理系统P中构造证明中构造

13、证明设前提设前提A1, A2, Ak,结论结论B 及及公式序列公式序列C1, C2, Cl. 如果每一个Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理规则得到, 并且Cl =B, 则则称这个称这个公式序列是公式序列是由由A1, A2, Ak推出推出B的的证明。证明。形式推理形式推理证明的格式：证明的格式： 建立命题公式序列的过程中为三个部分：建立命题公式序列的过程中为三个部分：序号序号（进入序列的公式序号）（进入序列的公式序号） 命题公式命题公式 公式出现的公式出现的理由理由理由可以理由可以是：推理规则（是：推理规则（P P或或T T）被被引用的相应的公式序号引用的相应的公式序号

14、等值等值式式 推理推理过程中过程中不要出现解释性文字不要出现解释性文字例例2 构造下面推理的证明：构造下面推理的证明： 若明天是星期一或星期三，我明天就有课若明天是星期一或星期三，我明天就有课. 若我明天有若我明天有 课，课，今天必备课今天必备课. 我今天没备课我今天没备课. 所以，明天不是星期一、也不是所以，明天不是星期一、也不是星期三星期三. 解解 (1) 设命题并符号化设命题并符号化 设设 p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三， r：我明天有课，：我明天有课，s：我今天备课：我今天备课(2) 写出证明的形式结构写出证明的形式结构 前提：前提：(p q)r,

15、rs, s 结论：结论： pq1415直接证明法直接证明法(2) 写出证明的形式结构写出证明的形式结构 前提：前提：(p q)r, rs, s 结论：结论： pq(3) 证明证明 序号序号 命题命题公式公式 理由理由 rs P 前提引入前提引入 s P 前提引入前提引入 r T 拒取式拒取式 (p q)r P 前提引入前提引入 (p q) T 拒取式拒取式 pq T 置换置换16附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为适用于结论为蕴涵式蕴涵式欲证欲证 前提：前提：A1, A2, , Ak 结论：结论：CB等价地证明等价地证明 前提：前提：A1, A2, , Ak,

16、 C 结论：结论：B理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B17附加前提证明法实例附加前提证明法实例例例3 构造下面推理的证明构造下面推理的证明 2是素数或合数是素数或合数. 若若2是素数，则是素数，则 是无理数是无理数. 若若 是无理是无理数，则数，则4不是素数不是素数. 所以，如果所以，如果4是素数，则是素数，则2是合数是合数. 解解 用附加前提证明法构造证明用附加前提证明法构造证明 (1) 设设 p：2是素数，是素数，q：2是合数，是合数， r： 是无理数，是无理数，s：4是素数是素数 (

17、2) 推理的形式结构推理的形式结构 前提：前提：p q, pr, rs 结论：结论：sq 22218附加前提证明法实例附加前提证明法实例 (2) 推理的形式结构推理的形式结构 前提：前提：p q, pr, rs 结论：结论：sq (3) 证明证明 s P 附加附加前提引入前提引入 pr P r s P p s T 假言三段论假言三段论 p T 拒取式拒取式 p q P q T 析取三段论析取三段论当结论为当结论为 ABAB 形式形式时，也可用此方法，时，也可用此方法，将将A A作为附加前提作为附加前提即可即可A A B ABB19归谬法（反证法）归谬法（反证法）归谬法归谬法 (反证法反证法)欲

18、证欲证 前提：前提：A1, A2, , Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB) (A1 A2 AkB) 0 A1 A2 AkB020归谬法实例归谬法实例例例4 前提：前提： (p q) r, rs, s, p 结论：结论： q证明证明 用归缪法用归缪法 q P 结论结论否定引入否定引入 rs P s P r T 拒取式拒取式 (p q) r P (p q) T 析取三段论析取三段论 pq T 置换置换 p T 析取三段论析取三段论 p P p p T 合取合取21第三章第三章

19、 总结总结主要内容主要内容l 推理的形式结构推理的形式结构l 判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系统自然推理系统Pl 构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)22基本要求基本要求l 理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 结论：结论：Bl 熟练掌握判断推理是否正确的不同方法（如真值表法、等熟练掌握判断推理是否

20、正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l 牢记牢记 P 系统中各条推理规则系统中各条推理规则l 熟练掌握构造证明的直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l 会解决实际中的简单推理问题会解决实际中的简单推理问题作业：作业：P52，习题三，习题三：9 (推理三种方法推理三种方法)构造证明：构造证明：10 ， 12，14(1)(3)， 15(1)， 16(2)， 17 2324练习练习1：判断推理是否正确：判断推理是否正确1. 判断下面推理是否正确判断下面推理是否正确: (1) 前提：前提： pq, q 结

21、论：结论： p 解解 推理的形式结构推理的形式结构: ( pq)qp 方法一：等值演算法方法一：等值演算法 ( pq)qp (p q)q)p ( pq) qp ( p q) ( q q)p p q易知易知10是成假赋值，不是重言式，所以推理不正确是成假赋值，不是重言式，所以推理不正确.25练习练习1解答解答方法二：主析取范式法，方法二：主析取范式法， ( pq)qp (p q)q)p p q M2 m0 m1 m3未含未含m2, 不是重言式不是重言式, 推理不正确推理不正确.26练习练习1解答解答方法三方法三 真值表法真值表法 不是重言式不是重言式, 推理不正确推理不正确11100111010

22、0( pq)qpqp pq 0 1 1 1( pq)q 0 0 1 0方法四方法四 直接观察出直接观察出10是成假赋值是成假赋值27练习练习1解答解答用等值演算法用等值演算法 (qr) (pr)(qp) ( q r) ( pr)( qp) (qr) (p r)( qp) (q p) (q r) ( r p)( qp) (q p) (q r) ( r p) ( qp)1推理正确推理正确(2) 前提：前提：qr, pr 结论：结论：qp 解解 推理的形式结构：推理的形式结构： (qr) (pr)(qp) 28练习练习2：构造证明：构造证明2. 在系统在系统P中构造下面推理的证明：中构造下面推理的证

23、明： 如果今天是周六，我们就到颐和园或圆明园玩如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和如果颐和 园游人太多，就不去颐和园园游人太多，就不去颐和园. 今天是周六，并且颐和园游今天是周六，并且颐和园游 人太多人太多. 所以所以, 我们去圆明园或动物园玩我们去圆明园或动物园玩. 证明证明： (1) 设设 p：今天是周六，：今天是周六，q：到颐和园玩，：到颐和园玩， r：到圆明园玩，：到圆明园玩，s：颐和园游人太多：颐和园游人太多 t：到动物园玩：到动物园玩 (2) 前提：前提：p(q r), sq, p, s 结论：结论：r t29练习练习2解答解答(3) 证明：证明： p(q r) 前

24、提引入前提引入 p 前提引入前提引入 q r 假言推理假言推理 sq 前提引入前提引入 s 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论 r t 附加附加例：例： (1)(1)前提公式：前提公式：pq pq ， q rq r， p s p s ， s s 结论结论B B： r(pq)r(pq)证明：证明： 序号序号 公式序列公式序列 理由理由 1 s P1 s P 2 p s P 2 p s P 3 p T 1,2 3 p T 1,2 拒取式拒取式 4 pq P4 pq P 5 q T 3,4 5 q T 3,4析取三段析取三段 6 q r P6 q r P 7 r T 5

25、,6 7 r T 5,6假言推理假言推理 8 8 r(pq)r(pq) T 4,7 T 4,7合取规则合取规则 所以结论所以结论B B是前提集合的有效结论是前提集合的有效结论例：例：(2)(2)前提：前提：pq pq ，rq rq ， rs rs 结论结论: p s : p s 证明：证明： 序号序号 公式序列公式序列 理由理由 1 pq P1 pq P 2 p q T 1 2 p q T 1 等值等值 3 rq P3 rq P 4 q r T 3 4 q r T 3 等值等值 5 p r T 2,45 p r T 2,4假言三段假言三段 6 rs P6 rs P 7 7 p sp s T 5

26、,6 T 5,6假言三段假言三段返回返回例（例（3 3）: : 前提为：前提为：prpr， pq pq ，q s q s 结论为结论为 srsr证明：证明： 序号序号 公式序列公式序列 理由理由 1 pq P 2 p q T 1 等值等值 3 q s P 4 p s T 2,3假言三段假言三段 5 s p T 4等值等值 6 pr P 7 s p T 5,6假言三段假言三段 8 sr T 7等值等值返回返回例：前提为例：前提为 （pqpq）r r， sp sp ， q q 结论为结论为 s r s r （ 用附加前提法）用附加前提法）证明：证明： 序号序号 公式序列公式序列 理由理由 1 s

27、P 1 s P 附加附加 2 sp P2 sp P 3 p T 1,2 3 p T 1,2析取三段析取三段 4 q P4 q P 5 p q T 3,4 5 p q T 3,4合取合取 6 6 （pqpq）r Pr P 7 r T 5,6 7 r T 5,6假言推理假言推理 8 8 s rs r T 1,7 T 1,7附加前提附加前提注：若结论为注：若结论为 s r s r 也可以利用此方法也可以利用此方法 该题不用此方法也可（用直接证明方法）该题不用此方法也可（用直接证明方法）返回返回l例：前提为例：前提为 （pqpq）r r， rs , s ,p rs , s ,p l 结论为结论为 q

28、q证明：证明： 序号序号 公式序列公式序列 理由理由 1 q P 1 q P 附加附加 2 q T 12 q T 1等值等值 3 p P3 p P 4 p q T 2 4 p q T 2，3 3 合取合取 5 5 （pqpq）r Pr P 6 r T 4 6 r T 4，5 5 假言推理假言推理 7 rs P7 rs P 8 s T 6,7 8 s T 6,7析取三段论析取三段论 9 s P9 s P 10 s s T 8 10 s s T 8，9 9 合取合取 所以结论是前提集合的有效结论。所以结论是前提集合的有效结论。l例：前提为（例：前提为（pqrpqr） ， (q (q r) (s t

29、) r) (s t) l 结论为结论为 s t s t l证明：证明： 序号序号 公式序列公式序列 理由理由 1 1 （ s t s t ） P P 附加附加 2 (q 2 (q r) (s t) P r) (s t) P 3 (q 3 (q r) T 1r) T 1，2 2 拒取拒取 4 4 （(qr)(qr)(qr)(qr)） T 3 T 3 等值等值 5 (qr) (qr) T 4 5 (qr) (qr) T 4 等值等值 6 (qr) T 5 6 (qr) T 5 化简化简 7 7 （pqrpqr） P P 8 qr T 7 8 qr T 7 化简化简 9 (qr) (qr) T 79 (qr) (qr) T 7，8 8 合取合取 所以结论是前提集合的有效结论。所以结论是前提集合的有效结论。例例: : 前提为：前提为：prpr， pq pq ，q s q s 结论为结论为 srsr 1 1）