第二章 命题逻辑（下） 主讲人：耿国华.

Presentation on theme: "第二章 命题逻辑（下） 主讲人：耿国华."— Presentation transcript:

1 第二章 命题逻辑（下） 主讲人：耿国华

2 第三节 命题逻辑的自然演绎系统NP 命题逻辑的推理可以分成自然演绎推理和公理系统推理两大类型。在自然演绎推理中，可以从任意给定的前提出发，用给定的推理规则依照一定的步骤进行推理或演算 自然演绎系统与公理系统不同，它没有公理，只有一系列推理规则。它引入特定前提为假设，根据推理规则推演出结论而建构起来的演算系统。由于这个系统描述的推演关系比较直接而自然地反映了人们的思维过程，因而被称作自然演绎系统。我们将以自然演绎系统为基础讨论有效推理的证明。

3 命题的自然演绎推理系统NP 命题逻辑的推理可以分成自然演绎推理和公理系统推理两大类型。在自然演绎推理中，可以从任意给定的前提出发，用给定的推理规则依照一定的步骤进行推理或演算 自然演绎系统与公理系统不同，它没有公理，只有一系列推理规则。它引入特定前提为假设，根据推理规则推演出结论而建构起来的演算系统。由于这个系统描述的推演关系比较直接而自然地反映了人们的思维过程，因而被称作自然演绎系统。我们将以自然演绎系统为基础讨论有效推理的证明。

4 一、形式语言 命题公式——复合命题的逻辑形式。有意义的符号式又称为命题公式或合式公式，简称为公式。
形式语言——人为创造出来的一种特殊的语言符号作为命题公式的表达式。这样的语言叫做形式语言。 人们创造这些符号是为了表达复合命题的逻辑形式以满足逻辑研究的需要。对于这些语言符号构造的表达式，我们只重视它们在形式结构上的区分。因此，我们把这样的语言叫做形式语言。

5 1、初始符号 命题逻辑中命题的构建方法主要包括两部分内容。一是初始符号，二是形成规则。
1、初始符号——形式语言也有其构造表达式的基本符号，称之为初始符号。如同自然语言有基本构词要素，如英文有26个字母。 构造命题公式的初始符号如下： 初始符号 ①命题变元：p，q，r，…；p1 ,q1 ,r1 , … ②命题联结词：∧，∨，→，，┓ ③辅助符号： （， ）

6 2、形成规则 ①所有命题变元是命题公式（合式公式）； ②如果A是命题公式，那么A是命题公式；
③如果A和B是命题公式，那么A，A∨B，A∧B，A→B，A←→ B 都是命题公式。 ④只有符合以上3条的才是命题公式。

7 原子公式——结构最简单的命题公式，因此被称作原子公式。
命题公式的子公式作为一个命题公式构成部分的公式。

8 二、推导规则 推导规则——也叫变形规则，具体地规定从某种形式的一个或一些公式可推出具有某种形式的另一个公式。即从一个或一些符号串，变形为另一个符号串。 自然演绎系统形式证明是建立在推理规则基础之上的。这些规则大约可分为四部分： （一）基本推导规则， (二)等值替换规则， (三)条件证明规则， (四)间接证明规则。

9 （一）NP系统的基本推导规则 （ 1）引入假设前提规则。简称“规则P”。这一规则是说，在推理或演算过程中，可以在任一步骤上引入一个公式或真值形式作为前提。若引入多个假设前提，可用符号P1 ，P2 ， … ， Pn 表示。 （ 2）引入重言式蕴涵式规则。简称“规则T”。这一规则是说，在推理或演算过程中，如果有一个或一些先行出现的公式或真值形式的合取重言蕴涵A，则可以在这个推理或演算中引入A。 设：前提为B，结论为A，则有：B→A 。B重言蕴涵A就是指B→A是一重言式。

10 重言蕴涵式可以作为规则引入到命题自然推理系统中。 下面将一部分常用重言蕴涵式以推理规则的方式列出。
①T-合取引入，也叫组合规则（记为∧ + ）：从公式 A和B推出A∧B。 ②T-合取消去，也叫简化规则（记为∧ - ）：从公式A∧B推出A；从公式A∧B推出B。 ③T-析取消去（记为∨ - ）：从公式A∨B和┐A推出B；从公式A∨B和┐B推出A。 ④T-析取引入，也叫附加规则（记为∨ + ）：从公式 A推出A∨B；从公式B推出A∨B。

11 重言蕴涵式可以作为规则引入到命题自然推理系统中。 下面将一部分常用重言蕴涵式以推理规则的方式列出。
重言蕴涵式可以作为规则引入到命题自然推理系统中。 下面将一部分常用重言蕴涵式以推理规则的方式列出。 ⑤T-蕴涵消去，也叫分离规则（MP）（记为 →- ）：从公式 A→B和公式A推出公式B。 ⑥T-蕴涵引入，也叫逆分离规则（MT）还叫条件证明或演绎推理。（记为 →+ ）：如果从一前提公式集合Γ和 A推出B，则从Γ推出公式A→B。 ⑦T-假言三段论（HS） A→B，B→C 可推出A→C ⑧T-二难推理（CD）：A→C，B→D，A∨B 可推出C∨D

12 (二)等值替换规则 基本推导规则 ①交换律（COM） (p∧q)  (q∧p) (p∨q)  (q∨p) ②结合律（Ass）
((p∧q)∧r)  (p∧(q∧r)) ③德摩根律 （DeM）  (p∧q)  (p∨q)  (p∨q)  (p∧q) ④分配律（Dist） (p∧(q∨r))  ((p∧q)∨(p∧r)) (p∨(q∧r))  ((p∨q)∧(p∨r))

13 (二)等值替换规则 ⑤实质蕴涵（Impl） (p→q)  (p∨q) ⑥假言易位（Tran） (p→q)  (q →p)
⑦移出律 （Esp） ((p∧q)→r)  (p→(q→r)) ⑧实质等值（Equi） (pq)  ((p→q) ∧ (q→p)) ⑨双否律 （DN） p  p ⑩重言律 （Taut） p  (p∧p) p  (p∨p)

14 实例： 例3 如果他主张减轻农民的税负，他将赢得农民的支持。如果他主张政府增加对社会福利的投入，他将赢得工人的支持。如果他既赢得农民的支持又赢得工人的支持，他就肯定能当选。但是他没有当选。所以，或者他不主张减轻农民的税负，或者不主张政府增加对社会福利的投入。

15 实例： 解：设“他主张减轻农民的税负”为A，“他将赢得农民的支持”为B，“他主张政府增加对社会福利的投入”为C，“他将赢得工人的支持”为D，“他肯定能当选”为E。 将推理形式化并建立推理有效性的形式证明： ① A→B P ② C→D P ③ （B∧D）→ E P

16 实例： ④ E P \ ∴ A∨C ⑤ （B∧D） ③④MT ⑥ B∨D ⑤DeM ⑦ （A→B）∧（C→D） ①②∧+
⑧ （B→A）∧(D→C) ⑦Tran ⑨ A∨C ⑥⑧CD

17 运用等值替换规则和基本推导规则必须注意两类规则之间的区别。
等值替换规则是用逻辑等值的命题去代换原命题，无论怎样替换都不改变原命题公式逻辑值。 基本推导规则的运用是代入，代入必须处处进行，这就决定了基本推导规则只能对公式的整体起作用。

18 (三)条件证明规则C.P ①条件证明规则C.P p • q ∴p→q

19 (四)间接证明规则RAA 间接证明又叫做归谬证明或反证法。这是一种在数学中经常用到的证明方法。当我们要证明某一定理时，先引入该定理的否定为假设。然后由这一假设推导出矛盾。由于矛盾是不可能的，假设一定错误，即该定理的否定不成立。由此就间接地证明了该定理成立。 间接证明规则就是根据这一思路得到的。当我们为一有效推理建立形式证明时，不是直接去证明由前提推演出结论，而是将结论的否定作为一个补充前提引入形式证明。然后由扩充的前提集合推演出一个矛盾：即演出一个形式为“p∧p”的命题公式。由这个矛盾我们实际上推演出对这个补充前提的否定，即对结论的否定的否定，再根据双否律DN，就相当于推演出结论。

20 (四)间接证明规则RAA A→（B∧C） （B∨D）→E D∨A / ∴E 解 ⑴ A→（B∧C） P ⑵（B∨D）→E P
⑶ D∨A P / ∴ E

21 (四)间接证明规则RAA ⑷ E RAA ⑸ （B∨D） ⑵⑷ MT ⑹ B∧D ⑸DeM ⑺ D ⑹ COM，∧-
⑼ B∧C ⑴⑻ MP ⑽ B ⑼ ∧- ⑾ B ⑹ ∧- ⑿ B∧B ⑽⑾ ∧+

22 三、NP系统的推演和证明 （语法推出关系） 形式证明的定义 一个形式证明是一个命题公式序列A1，A2，…，An。其中的任一Ai（1≤i≤n）或者是前提，或者是由前面的公式根据推理规则得到的。序列的最后一个公式An恰好是结论。

23 三、NP系统的推演和证明 注意： 按上述规则，最后一步使用的合成式的联结词，成为主联结词，即辖域最大的联结词，它决定这个多重复合命题的性质。
在公式结构中进行运算时，像数学运算一样，先乘除后加减。 联结词的结合力和括号的使用： ①联结词的结合力由强到弱依次递减的顺序： ┐，∧，∨，→，←→ ②每个复合命题外应加括号，不能省略的不得省略。公式最外层的括号可以省略。

24 NP系统的推演和证明 T1 ：p→p T1是 T-同一规则：从公式A推出A。 证： （ 1）p P （ 2）p （1）,T-同一
T2 ：(p∧q)→p T3 : (p∧q)→q T4 :（（p∨q）∧┐p）→q T5 :（（p∨q）∧┐q）→p

25 NP系统的推演和证明 T6 :（（p→q）∧p）→q 证： （1）p→q P （2）p P
（3）q 　　（1），（2），T-（→-） T7 :（（p→q）∧（q→p））→（ pq） T8 :（pq）→（ p→q） T9 :（pq）→（ q→p）

26 NP系统的推演和证明 T10 ：┐┐p→p T11 ：p →┐┐ p
T8 和T9 都是T-等值消去规则（记为- ）：从公式 AB推出A→B；从公式AB推出B→A。 T7 是T-等值引入规则（记为+ ）：从公式 A→B和B→A推出AB。 T10 、T11是T-双重否定规则（记为┐┐）：从公式┐┐A推出A；从公式A推出┐┐A。

27 NP系统的推演和证明 T12 ：((p→q)∧(q→r))→(p→r) 证： (1)p→q P1 (2)q→r P2 (3)p PP1
(4)q 　　(1),(3),T-(→- ) (5)r 　　(2),(4),T-(→ - ) (6)p→r 　(3),(5),T-(→+ ),( 消去PP1 ) T12 叫作“假言三段论”，它可以作导出规则：从公式A→B和B→C推出A→C。该规则也可记为H.S.。

28 NP系统的推演和证明 T13 :((p→q)∧(p→┐ q))→ ┐ p 证： （ 1）p→q P （ 2）p→┐q P
（ 3）┐┐p 　PP1 （ 4）p 　　　(3),T-(┐┐) （ 5）q 　　　(1),(4),T-( →- ) （ 6）┐q 　　(2),(4),T-( →- ) （ 7）q∧┐q 　(5),(6),T-(∧ + ) （ 8）┐p 　　(3),(7),(RAA) T13 :叫作“归谬法”，它是导出规则：从公式A→B和A →┐B推出┐A。

29 NP系统的推演和证明 T14 ：（p→q）→（┐q→┐p） 证： ⑴ p→q P ⑵ ┐q PP1 ⑶ ┐┐p PP2
⑸ q 　　　(1),(4),T-(→- ) ⑹ q∧┐q 　(5),(2),T-(∧ + ) ⑺ ┐p 　　　(3),(6),(RAA)(消去PP2 ) ⑻ ┐q→┐p 　(2),(7),T-(→+ )( 消去PP1 ) T15 ：（┐q→┐p）→（ p→q） T14 和T15 都是假言易位法。我们可以看出，从T14 推出T15 ，而且从T15 推出T14 。这种可互相推出的关系叫作“可证等价关系”。

30 NP系统的推演和证明 T16 :(( p→q)∧┐q)→┐ p 叫“否定后件式”，它是导出规则，记为M.T.:从公式A→B和┐B推出┐A。
证： ⑴ p→q 　　P1 ⑵ ┐q 　　P2 ⑶ ┐q →┐p 　(1),T13 和T14 ,R.P. ⑷ ┐p 　　　(2),(3), T-(→- )

31 NP系统的推演和证明 T17 ：((p→r)∧(q→r)∧(p∨q)) →r 证： ⑴ p→r P1 ⑵ q→r P2 ⑶ p∨q P3
⑸ ┐q 　　(2),(4),M.T. ⑹ p 　　　(3),(5),T-(∨ - ) ⑺ r 　　　(2),(6), T-(→- ) ⑻ r∧┐r 　(4),(7), T-(∧ + ) ⑼ r 　　　(4),(8),(RAA)(消去PP1 ) T17 :叫“二难式”，它是一种重要的导出规则：从公式A→B、B→C和A∨B推出C。也有把T16 叫作“析取消去规则”，记作D.E.。

32 NP系统的推演和证明 T18 :┐(p∨q) → ┐p 证：（略） T19 : ┐(p∨q) →┐q T 20 ：p∨q q∨p
⑵ p 　　　　PP1 ⑶ q∨p 　　（2），T-（∨ + ） ⑷ p→q∨p 　(2),(3),T-(→+ )( 消去PP1 )

33 NP系统的推演和证明 ⑸ q PP2 ⑹ q∨p (5), T-（∨ + ）
⑺ q→q∨p 　　(5),(6),T-(→+ )( 消去PP2 ) ⑻ q∨p 　　　(1),(4),(7),D.E. ⑼ p∨q →q∨p 　(1),(8), T-(→+ ) 再证： q∨p→p∨q

34 NP系统的推演和证明 证明方法与先证的（ 1）-（9）相似，只是变项p和q的先后顺序有所变化，而且第⑼步得到的公式为： q∨p→p∨q
最后根据规则 T-（+ ），该等值式得证明。 这个等值式叫析取交换律。 T21 ：p∧qq∧p 这个等值式叫合取交换律。（证明略） T22 ：p∨（q∨r） (p∨q)∨r

35 NP系统的推演和证明 这个等值式叫析取结合律。（证明略） T23 : p∧(q∧r)  (p∧q)∧r 这个等值式叫合取结合律。（证明略）
T24 : p∧（q∨r） (p∧q)∨(p∧r) T25 : p∨(q∧r)  (p∨q)∧(p∨r） T24 和T25 叫分配律。（证明略） T26 ：┐(p∧q)  ┐p∨┐q 先证：┐ (p∧q)→┐p∨┐q ⑴ ┐(p∧q)　　 　　　P1 ⑵ ┐（┐p∨┐q） 　pp1 ⑶ ┐p 　　　　　　pp2 ⑷ ┐p∨┐q 　　　(3), T-（∨ + ） ⑸（┐p∨┐q）∧┐（┐p∨┐q） (2),(4),T-(∧ + ) ⑹ p 　　　　　(3),(5),(RAA)

36 NP系统的推演和证明 ⑺ ┐q PP3 ⑻ ┐p∨┐q (7), T-（∨ + ）
⑼（┐p∨┐q）∧┐（┐p∨┐q） 　(2),(8),T-(∧ + ) ⑽ q 　　　　　(7),(9),(RAA) ⑾ p∧q 　　　　(6),(10),T-(∧ + ) ⑿ (p∧q)∧┐(p∧q) 　　(1),(11),T-(∧ + ) ⒀ ┐p∨┐q 　　　(2),(12),(RAA)

37 NP系统的推演和证明 ⒁ ┐(p∧q)→ ┐p∨┐q (1),(13),T-(→+ ) 再证：┐ p∨┐q →┐(p∧q)
⑵ ┐┐(p∧q) 　　pp1 ⑶ p∧q 　　　　　(2), T-(┐┐) ⑷ p 　　　　　　(3), T-(∧ - ） ⑸ q 　　　　　　(3), T-(∧ - ）

38 NP系统的推演和证明 ⑹ ┐┐p (4), T-(┐┐) ⑺ ┐q (1),(6),T-(∨ - )
⑻ q∧┐q 　　　(5),(7),T-(∧ + ) ⑼ ┐(p∧q) 　　(2),(8),(RAA) ⑽ ┐p∨┐q → ┐(p∧q) 　　(1),(9),T-( →+ ) 通过对 T26 的先后两次证明，证明了等值符号两边的公式相互蕴涵。因此该等值式成立。这个等值式是著名的德·摩根定律，也有叫作“反演律”的。 T27 ：┐（p∨q）┐p∧┐q 这个等值式也是著名的德·摩根定律。（证明略） T28 :┐(p→q) p∧┐q 证：（略） T29 : (p→q)  ┐(p∧┐q) T30 : (p∧q→r)  (p→(q→r))

39 自然演绎推理的实例： 例1：如果货币供应总量保持现状 (p)，而货币需求量增加(q)，则银行利率就会上升(r)。如果货币需求量增加(q)导致银行利率上升(r)，则在银行存款更被看好(s)。主管部门已经宣布货币供应总量保持不变(p)。因此，在银行存款更被看好(s)。 整个推理可形式化为： ((p∧q→r)∧((q→r)→s)∧p )→s

40 自然演绎推理的实例： 证：（方法一） ⑴ p∧q→r P1 ⑵ (q→r)→s P2 ⑶ p P3 ⑷ q PP1
⑸ p∧q 　　　　(3),(4), T-(∧ + ) ⑹ r 　　　　　　(1),(5), T-(→- ) ⑺ q→r 　　　(4),(6), T-(→+ ) ⑻ s 　　　　　(2),(7),T-(→- )

41 自然演绎推理的实例： 证：（方法二） ⑴ p∧q→r P1 ⑵ (q→r)→s P2 ⑶ p P3 ⑷ ┐s PP1
⑸ ┐(q→r) 　　(2),(4),M.T. ⑹ q∧┐r 　　　(5),R.P. ⑺ ┐r 　　　　(6), T-(∧ - ) ⑻ ┐(p∧q) 　　(1),(7),M.T. ⑼ ┐p∨┐q 　　(8),R.P.

42 自然演绎推理的实例： ⑽ q(6), T-(∧ - ) ⑾ ┐┐q (10),T-(┐┐) ⑿ ┐p (9),(11), T-(∨ - )
⒀ p∧┐p 　　(3),(12),T-(∧ + ) ⒁ s 　　　　　(4),(13),(RAA) 这两种方法都证明该推理是符合逻辑的。

43 自然演绎推理的实例： 例2：如果上市公司的业绩普遍下降 (p)，或者经济增长全面滑坡(q)，那么股票价格就会全面下降(r)。如果股票价格全面下降(r)，那么，或者股市无人问津(s)，或者投资者普遍受到损失(t)。如果投资者普遍受到损失(t)，则人们对股市就会失去信心(u)。事实上有越来越多的人问津股市(┐s)，而且人们对股市没有失去信心(┐u)。所以，经济增长没有全面滑坡(┐q)。 整个推理可形式化为：

44 自然演绎推理的实例： ((p∨q)→r)∧(r→(s∨t))∧(t→u)∧(┐s∧┐u)→┐ q 证： ⑴ (p∨q)→r P1
⑵ r→(s∨t) 　　　P2 ⑶ t→u 　　　　　P3 ⑷ ┐s∧┐u 　　　P4 ⑸ ┐s 　　　　　(4), T-(∧ - )

45 自然演绎推理的实例： ⑹ ┐u (4), T-(∧ - ) ⑺ ┐t (3),(6), M.T.
⑻ ┐s∧┐t 　　(5),(6),T-(∧ + ) ⑼ ┐(s∨t) 　　(8), R.P. ⑽ ┐r 　　　　　(2),(9), M.T. ⑾ ┐(p∨q) 　　(1),(10), M.T. ⑿ ┐p∧┐q 　　(11), R.P. ⒀ ┐q 　　　　　(12), T-(∧ - ) 由该推理的前提集合推出的结论有效，证明该推理符合逻辑。

46 自然演绎推理的实例： 例3：公安人员侦破一起盗窃案。已知有这样几件事实：盗窃者或者是赵某或者是钱某 (p∨q)；如果是赵某，那么作案时间不会在午夜前发生(p→ ┐ r)；如果钱某的证词正确，那么，午夜时室内灯光没有熄灭(s→t)；如果钱某的证词不正确，那么作案时间在午夜前发生(┐s →r)；午夜之时室内灯光已经熄灭(┐t)。根据以上事实，能否推出盗窃者是谁。 将反映事实的命题作为前提集合形式化为： (p∨q) ∧(p→ ┐ r) ∧ (s→t) ∧ (┐s→r) ∧ (┐t)

47 自然演绎推理的实例： 推导过程如下： ⑴ p∨q P1 ⑵ p→┐r P2 ⑶ s→t P3 ⑷ ┐s→r P4 ⑸ ┐t P5
⑹ ┐s 　　　(3),(5), M.T. ⑺ r 　　　(4),(6), T-(→- ) ⑻ ┐p 　　(2),(7), M.T. ⑼ q 　　　(1),(8), T-(∨ - ) 这个推理的结论是：钱某是盗窃者。（“ q”= 钱某是盗窃者；“┐p”= 赵某不是盗窃者。）

48 如何运用规则建立形式证明： 例1 如果商品短缺日益严重，那么物价会上涨。如果存在生产过剩，那么物价不会上涨。如果存在通货膨胀威胁，那么财政控制将继续。如果政府改组，那么财政控制将取消。或者存在生产过剩，或者政府改组。因此，商品短缺不会日益严重，或者不再存在通货膨胀威胁。 解：设“商品短缺日益严重”为A，“物价会上涨”为B，“存在生产过剩”为C，“存在通货膨胀威胁”为D，“财政控制将继续”为E，“政府改组”为F。 首先将该推理形式化，在此基础上建立该推理有效性的形式证明。

49 如何运用规则建立形式证明： ① A → B P ② C → B P ③ D → E P ④ F →  E P
⑤ C ∨ F P / ∴ A∨D ⑥（C →B）∧（F →  E） ②④∧+ ⑦ B ∨ E ⑥⑤CD ⑧（A → B）∧（D → E） ②④∧+ ⑨ A∨D ⑦⑧CD

50 第四节 命题逻辑语义有效性的判定方法 一、真值函项和重言式 二、真值表法 三、简化真值表法（归缪赋值法）

51 一、真值函项和重言式 （一）真值函项 ⒈命题和命题联结词 复合命题是由命题和命题联结词构成的。最基本的命题联结词有五个：
否定（）、析取（∨）、合取（∧）、蕴涵（→）、等值（←→）。 按照习惯的用法，命题联结词的结合力依下面顺序递减：  、 ∧ 、 ∨ 、→、←→

52 ⒉命题变项 在命题逻辑中，通常用p、q、r、s……等符号表示命题。由于这些符号可以表示任何具体的命题，因此它们被称为命题变项（或“命题变元”）。 运用命题联结词将命题变项结合起来，可以构成各种各样的符号式。

53 ⒊命题公式 有意义的符号式又称为命题公式或合式公式，简称为公式。 只有符合下面要求的符号式才是有意义的： ①命题变项是公式。
②如果A和B是公式，那么A，A∨B，A∧B，A→B，A←→ B 都是公式。 ③只有按照以上两点组成的符号式才是公式。

54 ⒋真值形式、真值函项 由于命题所取的值是真值，所以，命题公式又称为真值形式。
真值形式的一个重要特征就是函项性。真值形式中的命题变项的真值决定着该真值形式的真假，两者构成一种函数关系。这种函数关系被称为真值函项。 每一个真值形式都是一个真值函项。

55 ⒌真值函项的数目 真值函项的数目是由公式中变项的真假组合决定的。
当有两个变项时，由于每个变项都可以取真假两值，因此，它的真假组合便有4(22)种： 当公式有三个 当有 n 个变项 变项时，其真 时，其真假组 假组合就变成 合有2 n 种。 了8(23)种。 p q T T T F F T F F

56 真值函项的数目 真值函项是对变项的各种真假组合作出判定，即对某一组合判定其为真或假。由于每一种组合都有可能判定为真或假，对于n个变项来说，其真值函项的数目为22n个。 （n个命题变项可能有的真假组合是2n，每一个真假组合又有两种断定：肯定和否定。对于2n 个组合，肯定和否定的组合是22n个）。

57 真值函项的数目 例：对于命题变项p来说，其真值函项为4个： p f1 (p) f2 (p) f3 (p) f4 (p) T F

58 真值函项 f1 (p)是指p无论取什么样的真值，其值总为真，可以用相应的公式p∨p表示。

59 常真或常假的真值函项 设：n=2，当有p 、q 两个变项时，真值函项数为222个，即16个真值函项（见下页表 ）：
f1表明，在这一函项的真值形式中无论其中p 和q取何值，公式的值都为真。因此，它是一个常真的真值函项，可以表示为p→q∨q，（p→q）∧p→q等等。 f16表明，在这一函项的真值形式中无论其中p 和q取何值，公式的值都为假。因此，它是一个常假的真值函项，可以表示为（p∨p） ∧ q，q∧p∧q等等。

60 常真或常假的真值函项 p q f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
T F

61 时真时假的真值函项 f2－f15是时真时假的，它们都可以用相应的公式表示，例如：
f2是p和q都取假值时才假的函项，相应的公式有：p→q，p∨q等； f8是p 和q都取真值时才真的函项，相应的公式有：（p→┐q），p∧q等。

62 真值函项和真值形式的种类 由前面可以看出，真值函项可以分为三类：永真的，时真时假的和永假的。与此相对应，表示真值函项的命题形式也可以分为三类。 第一类称为永真公式，也称重言式，逻辑 规律。 第二类称为可真公式（可满足式）。 第三类称为永假公式（矛盾式）。

63 （二）重言式 1、什么叫重言式： 重言式即永真公式，也称逻辑规律。即公式中所包含的变项 不论取真值或假值，该公式都为真。
例:p∨┓p 不论p被指派为什么真值，该公式都为真。 在上述三类公式中，永真公式也就是重言式，具有特别重要的意义，因为在命题逻辑中所有的规律都表示永真的真值函项。 命题逻辑主要的任务是考察重言式，研究重言式判定的方法，及构成能包罗所有重言式的形式推理系统。

64 2、重言式判定的方法 重言式判定的方法，实际上是指利用某种机械的程序，可以在有穷步骤内鉴别任一命题公式是否为重言式的方法。在命题逻辑中，
常用的判定方法： 真值表法、简化真值表法和真值树法（略）。

65 二、真值表法 任何一个正确的推理形式都可以视为永真式
二、真值表法 任何一个正确的推理形式都可以视为永真式 真值表：指能显示一个复合命题在它的支命题的各种组合下的真假情况的图表，是一种表格真值指派法。 真值表法：是一种表格真值指派法。它按照一定的次序，对一个公式的各个组成部分分别指派真值或赋值，求得该公式的真值。 作用： 可以在有穷步骤内计算出比较复杂的复合命题的真值； 例：((( p ∧q ) →r )∧(p ∧┓r) ) →┓q 判断各种复合命题是否等值。 例: ( p → q ) ←→(┓q → ┓ p)

66 运用真值表方法的步骤 列出各种真值组合：运用给定命题形式中的所有变项，列出这些命题的各种真值组合；
分解命题形式：根据命题形式的构成过程，由简而繁的将给定命题形式分解成各个组成部分（子公式）；被判定的公式（原公式）列在最后。 计算每个组成部分真值：根据已学过的联言命题、选言命题、假言命题、负命题七个真值表，计算出每个组成部分的真值，依次给出表中所有公式的真值。 最后得出该复合命题的真值。

67 真值表法① p q T F

68 真值表法② p q p q p→q (p→q)∧q (p→q)∧q→p T F

69 真值表法③、④ p q p q p→q (p→q)∧q (p→q)∧q→p T F

70 例1、判定（p∧q）→(p∨q)真值 例2、下列ABC三个命题不同真 ，可否断言小金是否当选班长，小赵是否当选学习委员？ A:小金不当选班长或者小赵当选学习委员 B:小赵当选学习委员 C:小金当选班长或者小赵当选学习委员 ①把ABC符号化为：A: (┓p∨q) B: q C :(p∨q) ②列真值表如下： ③由表第3、5行得知， ABC不同真 由此可断定 p 真或假，q假, (┓p∨q) 真假不定。 即：断定小赵没当选学习委员 不能断定小金是否当选班长 p q p  p∨ q P ∨ q T F

71 例3、甲、乙、丙三人争夺象棋比赛的前三名。 小林预测，“只有甲第一，丙才第二”。 小刘预测，“丙不是第二”。 事实证明两人中只有一人的预测为真，请回答甲、乙、丙三人的名次。
p q  q P ←q T F ①设：小林: (p← q) 小刘: ┓q ②列真值表如下： ③由真值表第2行得知，两命题不同真 p、q均真时，┓q 为假， (p← q)为真。 即：甲第一、丙第二、乙第三

72 例4：用真值表判定下列推理是否有效。 或者逻辑难学，或者没有多少学生喜欢它。如果数学容易学，那么逻辑不难学。因此，如果许多学生喜欢逻辑，那么学数学并不太容易。
答：设：p表示“逻辑难学” ，q表示“许多学生喜欢逻辑”，r表示“数学容易学”。则该推理的真值形式是： （（p∨┓q）∧（r→┓p））→（q→ ┓r ）

73 T F F T T T （（p∨┓q）∧（r→┓p））→（q→ ┓r ）的真值 p q r p q  r p∨  q r→ p

74 练习： 提示： 1、李的判断正确 2、⑴命题推理无效⑵命题有效，两命题不等值。 1、用真值表法，说明李的判断是否正确。
赵：小张在北京大学，小王不在南开大学。 钱: 要么小张在北京大学，小王不在南开大学。 孙: 只有小张不在北京大学，小王才不在南开大学。 李：赵、钱、孙三个命题不能同真。 2、用真值表法，说明下列两个命题是否有效、是否等值。 ⑴或者甲是罪犯，或者乙是罪犯。已查明甲是罪犯。所以，乙不是罪犯。 ⑵或者甲是罪犯，或者乙是罪犯。已查明甲不是罪犯。所以，乙是罪犯。 提示： 1、李的判断正确 2、⑴命题推理无效⑵命题有效，两命题不等值。

75 三、归谬赋值法(简化真值表法) 归谬赋值表——又称简化真值表法，即运用归谬推理的简化真值表的方法，用来判定一个蕴涵式是否为等值式，从从而断定一个推理是否有效的方法。 使用范围——仅适用于蕴涵式的推理，即复合推理；或者可以化为蕴涵式的推理（析取式和等值式）。 主要的思想——是使用反证法。先假定被判定的公式为假，假如能够从这一假定推导出形如p∧p的逻辑矛盾，即说明假定不成立，该公式不可能为假，由此可以断定该公式为重言式。假如从假定该公式假推不出矛盾，则表明该公式在某些赋值（真假组合情况）下为假，因此可以断定该公式不是重言式。

76 归谬赋值法的原理及方法 原理—— 方法→列出被判定的公式。 →推出变项应赋何值 →检验是否有逻辑矛盾 →确定是否为永真式
要说明一个蕴涵式为重言式（永真式），则须证明 不论蕴涵式的变项取什么值，公式都不会是假的。 否则，就会导致逻辑矛盾。 方法→列出被判定的公式。 →假定蕴涵式为假 →推出变项应赋何值 →检验是否有逻辑矛盾 →确定是否为永真式

77 例1 证： （p∨q∨r）∧┓r→（p∨q） 真 假 假 真 真 判定（p∨q∨r）∧┓r→（p∨q）是否为重言式 假 ①② ③ ④
①② ③ ④ 真 假 假 真 真 ⑴假定被断定的推理形式为假① ⑵由①得②， （p∨q∨r）∧┓r 为真 ，（p∨q）为假 ⑶ 由②得③， ┓r 为真，再得r为假 ⑷由③得④，p∨q为真 ⑵与⑷在逻辑上自相矛盾，因而，假设不成立。 所以，（p∨q∨r）∧┓r→（p∨q）为重言式

78 例2：如果地球绕太阳公转（p），但并不围绕自己的轴线自转（┓q）,那么地球上就没有白天和黑夜（ ┓r）
例2：如果地球绕太阳公转（p），但并不围绕自己的轴线自转（┓q）,那么地球上就没有白天和黑夜（ ┓r）.事实上地球上有白天和黑夜（ r ），所以，或者地球并不公转（ ┓ p），或者地球公转（p）又自转（q）。 证明：该命题的真值形式即归缪赋值如下 （（（p ∧  q） → r ）∧ r → T F F T T F T T T F （p ∨ （ p ∧ q）） FT F T F F 由上可见，命题变项q有赋值矛盾，故该真值形式是重言式。原推理有效。

79 归谬赋值法说明 如果其中有一个变项既取真值又取假值，即出现p∧p这种形式的逻辑矛盾，证明被判定的公式不可能为假，只能为真，即该公式为重言式；反之，如果没有出现矛盾，证明原假定成立，因此，该公式不是重言式。 简化真值表法只适用于蕴涵式，但是，非蕴涵式可以先变形为与它等值的蕴涵式，然后再用简化真值表法判定它们。

80 在公式赋值中出现了q取真值又取假值，也就是出现了q∧q的逻辑矛盾，因此，该公式不可能为假（假设不成立），是重言式。
练习: 根据归缪赋值法断定（p→ r）∧（q→ r）∧（p∨q）→ r 是否为永真式。 （p→ r）∧（q→ r）∧（p∨q）→ r ① F ② T T F ③ T T T F F F F F T ③④ 在公式赋值中出现了q取真值又取假值，也就是出现了q∧q的逻辑矛盾，因此，该公式不可能为假（假设不成立），是重言式。

81 1、甲、乙、丙三位领导发表了下列意见。请用真值表解答：是否有一种方案可同时满足甲、乙、丙的意见。
甲：如果小张去黄山，那么小刘也去黄山。 乙：只有小张去黄山，小刘才去黄山。 丙：或者小张去黄山，或者小刘去黄山。

82 答：小张与小刘都去黄山。