7
NUIST
3 主析取范式法
((P→¬ ((P→¬Q)∧P)→ ¬Q ((¬P∨¬ ⇔((¬P∨¬Q)∧P)→ ¬Q ⇔(P∧Q)∨ ¬P∨ ¬Q (P∧Q)∨(¬P∧(Q∨ (Q∨¬ (P∨¬P)∧ ⇔(P∧Q)∨(¬P∧(Q∨¬Q) )∨( (P∨¬P)∧¬Q) (P∧Q)∨(¬P∧Q)∨(¬P∧¬Q)∨(P∧¬Q)∨(¬P∧¬ ⇔ (P∧Q)∨(¬P∧Q)∨(¬P∧¬Q)∨(P∧¬Q)∨(¬P∧¬Q) ⇔ (¬P∧¬Q)∨(¬P∧Q)∨(P∧¬Q)∨(P∧Q) P∧¬Q)∨(¬P∧Q)∨(P∧¬ ⇔ ∑(0,1,2,3 ) 因而 (*) 是永真式，推理正确。 ，
12
NUIST
1. 直接证明法
例1-5-3 检验下列推理的有效性。 如果马会飞或羊吃草，则母鸡就会是飞鸟； 如果母鸡是飞鸟，那么煮熟的鸭子还会跑； 煮熟的鸭子不会跑，所以羊不吃草。 解：设P：马会飞。 Q：羊吃草。 R：母鸡是飞鸟。S：煮熟的鸭子会跑 则前提为：(P∨Q)→R ， R→S ，¬S 结论为：¬Q 推理的形式结构为： ((P∨Q)→R)∧(R→S)∧(¬S)→ ¬Q
17
NUIST
课内练习 1-5-1 证明推理：P→(Q→R)，Q→(R→S)⇒ P→(Q→S) P→(Q→R)， P→(Q→R) Q→(R→S)⇒ 分析：由CP规则 P→(Q→R)，Q→(R→S)⇒ P→(Q→R)，Q→(R→S)⇒ P→(Q→S) 等价于 P→(Q→R)，Q→(R→S)， P→(Q→R)，Q→(R→S)，P ⇒ Q→S 再由CP规则，等价于 P→(Q→R)，Q→(R→S)，P，Q ⇒ S P→(Q→R)，Q→(R→S)，
18
NUIST
证明： 证明： (1) P (2) P→(Q→R) (3) Q→R (4) Q (5) R (6) Q→(R→S) (7) R→S (8) S (9) P→(Q→S) 规则， 由CP 规则，有： P→(Q→R)，Q→(R→S)⇒ P→(Q→R)，Q→(R→S)⇒
规则P(附加前提) 规则P(附加前提) P(附加前提 规则P 规则P (1),(2)假言推理 规则T 假言推理， (1),(2)假言推理，规则T 规则P(附加前提) P(附加前提 规则P(附加前提) (3),(4)假言推理 规则T 假言推理， (3),(4)假言推理，规则T 规则P 规则P (4) (6）假言推理，规则T (6）假言推理，规则T (5),(7)假言推理 规则T 假言推理， (5),(7)假言推理，规则T CP规则 CP规则 P→(Q→S)
10
NUIST
常用的推理规则
推理过程中使用的构造公式序列的规则： 规则P（前提引入规则）：在推导的任何步骤上，都可以 引入前提。 规则T（结论引入规则）：在推导过程中，如果前面有一 个或多个命题公式永真蕴含命题公式 S，那么就可以把 公式 S 引进推导过程中。 代入规则：在推导的任何步骤上，永真式中的任一命题 变元都可以用任一命题公式代入，代入后得到的仍是永 真式。 置换规则：在推导的任何步骤上，命题公式中的任何子 公式都可以用与之等值的命题公式置换。 常用的推理公式： 在表1.2-2中列出的永真蕴含式。 在表1.2-1中列出的逻辑等价式。
8
NUIST
4 指派分析法 (永真蕴含式) 即要判断(P→¬Q)∧P ⇒ ¬Q 证明：假设前件(P→¬Q)∧P 为真， 则P为真，且(P→¬Q)为真，所以¬Q 为真。 故(P→¬Q)∧P ⇒ ¬Q成立， 推理正确。
基于定义进行推理的不足： 1 如果命题公式的变元较多，以上四种方法都不方便 。 (n个变元， 2n种指派) 2 与自然生活和传统数学中的推理形式无相同之处。 3 过于机械，对培养推理能力和推理技巧毫无帮助。
11
NUIST
证明方法 推理：H1∧H2∧ … ∧Hm ⇒C
1．直接证明法 直接证明法 由已知的前提H1,H2,…, Hm出发，利用一些公 认的推理规则，根据已知的逻辑等价式和永真蕴 含式，推导出有效结论C。
2．间接证明法 间接证明法 将已知的前提和结论进行适当的改造， 转化为对新的前提和结论进行推理证明。 常用的技巧有：附加前提证明法和反证法。 。
20
NUIST
(2)反证法(归谬法) 将结论C的否定¬C 做为假设前提推出矛盾 的证明方法称为反证法或归谬法。 即：H1∧H2∧ … ∧Hm ⇒ C 的充要条件是 H1∧H2∧ H1∧H2∧ … ∧Hm∧ ¬C ⇒ F。 证明： 要证 H1∧H2∧ … ∧Hm ⇒ C 即证(H1∧H2∧ … ∧Hm)→C ⇔ T 同样，要证 H1∧H2∧ … ∧Hm∧¬C⇒ F ¬ 即证(H1∧H2∧ … ∧Hm∧¬C)→F ⇔ T ¬ 而(H1∧H2∧ … ∧Hm)→C ⇔ ¬ (H1∧H2∧ … ∧Hm)∨C ⇔ ¬ (H1∧H2∧ … ∧Hm∧¬C) 上式左边是永真式， 21 当且仅当H1∧H2∧ … ∧Hm∧¬C是永假式。
2
NUIST
推理的符号化实例 例1-5-1 1 如果天下雨，小王就不去跑步。 今天天下雨，所以小王没去跑步。 解： 设 P：天下雨。 Q：小王去跑步。 前提：P→¬Q， P 结论： ¬Q 推理的形式结构为：(P→¬Q)∧P→ ¬Q 2 如果我上街，我一定去新华书店。 我没上街，所以我没去新华书店。 解： 设P：我上街。 Q：我去新华书店。 前提：P→Q， ¬P 结论： ¬Q 推理的形式结构为： (P→Q)∧¬P→ ¬Q
16
NUIST
例1-5-5 证明：¬R→¬P是前提P→Q，Q→R的有效结论。 分析：要证明：(P→Q)∧(Q→R) ⇒ ¬R→¬P 采用附加前提证明法，转化为证明： (P→Q)∧(Q→R)∧¬R ⇒ ¬P 证明： (1) ¬ R 规则P(附加前提) (2) Q→R 规则P (3) ¬ Q (1),(2)拒取式，规则T (4) P→Q 规则P (5) ¬ P (3),(4)拒取式，规则T (6) ¬R→¬P CP规则 由CP 规则，得： (P→Q)∧(Q→R) ⇒ ¬R→¬P
14
NUIST
例1-5-4 证明 R∨S是前提C∨D，C→R，D→S的 有效结论，即证明： (C∨D)∧(C→R)∧(D→S)⇒(R∨S)。 证明: (1) (2) (3) (4) (5) (6) (7) (8) C∨D ¬C→D ¬ D→S ¬C→S C→R ¬R→¬C ¬R→S R∨S 规则P (1)蕴含等价式，规则T 规则P (2)(3)前提三段论，规则T 规则P (5) 逆反律，规则T (4)(6)前提三段论，规则T (7)蕴含等价式，规则T
第一列是步骤列, 将各次操作按先后排序; 列是步骤列 将各次操作按先后排序; 步骤 列是断言列或命题公式列, 断言列或命题公式列 第二列是断言列或命题公式列, 内容可以是 前提, 中间结论或最终结论; 前提, 中间结论或最终结论; 列是注释列或根据 根据列 第三列是注释列或根据列,表明所引用的推 理规则及与之有关的行的编号. 理规则及与之有关的行的编号.
1
NUIST
一、推理的基本概念
设H1,H2,…,Hm(ｍ≥１)和Ｃ都是命题公式。 若( H1∧H2∧ … ∧Hm ) →Ｃ为永真式， 即 H1∧H2∧ … ∧Hm ⇒Ｃ， 称由前提H1,H2,… ,Hm推出结论C的推理正确(有效)。 Ｃ称为前提H1,H2,… ,Hm的有效结论或逻辑结果。 H1∧H2∧ … ∧Hm →Ｃ称为 由前提H1,H2,… ,Hm推出结论C的推理的形式结构。
NUIST
1.5
推理规则与证明方法
推理是由一个或几个判断得出另一个新的判断的思维 形式(思维过程)。其中已知的判断——前提 新的判断——结论 列出前提H1,H2,… ,Hm与结论C——论证 逻辑的主要功能是提供推理的规则或论证的原理。从一 组给定的前提出发，根据推理规则得到的结论称为有效 结论，论证才是有效的。 建立逻辑学的主要目的在于探索出这一套完整的规则， 按照这些规则，就可以确定任何特定论证是否有效。
3
NUIST
二、基于 基于定义的推理 基于 的推理
根据定义：由前提H1,H2,… ,Hm推结论C的推理正确(有效)即： ( H1∧H2∧ … ∧Hm ) →Ｃ为永真式， 即 H1∧H2∧ … ∧Hm ⇒Ｃ 可知，判断推理是否正确的方法就是判断永真式 或永真蕴含式的方法。 基本方法有： 1 真值表法 2 等值演算法 3 主析取范式法 4 指派分析法(永真蕴含式 永真蕴含式) 永真蕴含式
19
NUIST
CP规则的适用范围： 待证的有效结论是P→Q 或 P∨Q 型的命题。
例1-5-6
采用附加前提法证明例1-5-4 ： (C∨D)∧(C→R)∧(D→S)⇒(R∨S)。 分析：由P→Q ⇔ ¬P∨Q， 得 R∨S ⇔ ¬R→S 由CP规则，等价于要证明 C∨D，C→R，D→S，¬R⇒ S 证明: (1) ¬R 规则P(附加前提) (2) C→R 规则P (3) ¬ C (1),(2)拒取式，规则T (4) C∨D 规则P (5) D (3),(4)析取三段论，规则T (6) D→S 规则P (7) S (5)，(6)前提三段论，规则T (8) ¬R→S CP规则 (9) R∨S (8)蕴含等价式，规则T
先将命题符号化 然后写出前提、结论和推理的形式结构 最后进行判断
5
NUIST
1 真值表法
P Q 0 0 0 1 1 0 1 1 ¬Q 1 0 1 0 Ｐ→¬Q 1 1 1 0 (Ｐ→¬Q)∧P Ｐ ∧ 0 0 1 0 (*) 1 1 1 1
真值表的最后一列全为1，因而(*)是永真式。 所以推理正确。 真值表技术：给定一个前提集合和一个结论，用构成真值表 的方法，在有限步骤内判定给定前提是否能推 导出该结论的这种方法，称为真值表技术 。
13
NUIST
证明： 第三列是形式推理的特点与优点. 第三列是形式推理的特点与优点. (1) ¬ S 规则P (2) R→S 规则P (3) ¬R (1)(2) 拒取式，规则T (4) (P∨Q)→R 规则P (5) ¬(P∨Q) (3)(4) 拒取式，规则T (6) ¬P∧¬Q (5) 德摩根律，替换规则，规则T (7) ¬Q (6) 简化式，规则T 所以推理正确 ¬ Q：羊不吃草——有效结论，但不是正确的结论。 ¬ P：马不会飞——有效结论，而且是正确的结论。 有效是指结论的推出是合乎推理规则的，并不在于 结论是否真实。