第3章_命题逻辑

1、123项目： 1. 校科研项目，直觉模糊满意度模型与应用 (编号：12SKY009)已结题。 2. 校科研项目，基于直觉模糊聚类分析的电子作业抄袭检测研究(编号：13SKY009)已结题。 3. 校教改项目，地方院校离散数学课计算机基础性及应用性研究(编号：14SJYX013)，在研。 教学：主要承担C语言、计算机基础、数据结构、离散数学等课程教学。4章节章节主要内容主要内容各教学环节学时分配各教学环节学时分配备注备注讲授讲授实验实验讨论讨论习题习题课外课外其它其它小计小计1命题逻辑命题逻辑6282一阶逻辑一阶逻辑6283集合的基本概念和运算集合的基本概念和运算4264二元关系和函数二元关系和

2、函数6285图的基本概念图的基本概念606合计合计28836l离散数学离散数学(又称计算机数学计算机数学)是现代数学的重要分支，是计算机专业核心基础课程之一。l离散数学是数据结构、数据库原理、数字逻辑、编译原理、人工智能、信息安全等课程的前续课程，同时以计算机导论和程序设计基础作为离散数学的先导课程。5l离散数学是计算机应用的必不可少的工具。例如数理逻辑在数据模型、计算机语义、人工智能等方面的应用，集合论在数据库技术中的应用，代数系统在信息安全中的密码学方面的应用，图论在信息检索、网络布线、指令系统优化等方面的应用。67定义、定理多。 本课内容定义定义定理定理例题例题为了学好这门课，要求： (

3、1) 弄懂定义、定理，弄懂例题，加深对定义、定理的理解； (2) 在课后复习基础上，做好作业。同学之间可以讨论，但要弄懂弄通。 (3)做好课堂笔记。8离散数学离散数学授课教师：鱼先锋命题符号化及联结词命题符号化及联结词命题公式及分类命题公式及分类等值演算等值演算联结词全功能集联结词全功能集对偶与范式对偶与范式推理理论推理理论10逻辑学：逻辑学： 研究推理的一门学科研究推理的一门学科数理逻辑：数理逻辑： 用数学方法研究推理的一门数学学科用数学方法研究推理的一门数学学科一套符号体系一套符号体系+一组规则一组规则11数理逻辑的内容：数理逻辑的内容： 古典数理逻辑：古典数理逻辑： 命题逻辑、谓词逻辑命

4、题逻辑、谓词逻辑 现代数理逻辑：现代数理逻辑： 逻辑演算、公理化集合论、递逻辑演算、公理化集合论、递归论、模型论、证明论归论、模型论、证明论12命题命题(Proposition)： 一个有确定真或假意义的陈述句。一个有确定真或假意义的陈述句。命题符号化及联结词命题符号化及联结词13EXAMPLE 1 下列句子都是命题：下列句子都是命题： 1. 华盛顿是美国的首都。华盛顿是美国的首都。 2. 多伦多是加拿大的首都。多伦多是加拿大的首都。 3. 1+1=2。 4. 2+2=3。 命题命题1和和3是真命题，是真命题，2和和4是假命题。是假命题。14EXAMPLE 2 考虑如下句子：考虑如下句子： 1

5、. 现在几点了？现在几点了？ 2. 认真阅读一下。认真阅读一下。 3. x+1=2. 4. x+y=z. 句子句子1和和2不是命题，因为它们都不是陈述句。不是命题，因为它们都不是陈述句。句子句子3和和4不是命题，由于不是命题，由于x，y和和z的值不确定，的值不确定，使得它们的真值都不唯一。使得它们的真值都不唯一。15命题的语句形式：命题的语句形式： 陈述句陈述句非命题语句：非命题语句： 疑问句、命令句、感叹句、疑问句、命令句、感叹句、 非命题陈述句：悖论语句（真值不唯一）非命题陈述句：悖论语句（真值不唯一）庄子庄子天下篇天下篇中提到：中提到：“一尺之棰，日取其半，一尺之棰，日取其半，万世不竭。

6、万世不竭。”16命题的符号表示：命题的符号表示： 大小写英文字母：大小写英文字母：P、Q、R、 p 、q 、r命题真值命题真值(Truth Values)的表示：的表示： 真：真：T、1 假：假：F、017命题语句真值确定的几点说明：命题语句真值确定的几点说明： 1、时间性、时间性 2、区域性、区域性 3、标准性、标准性命题真值间的关系表示：命题真值间的关系表示： 真值表真值表(Truth Table) 18DEFINITION 1. 设设p为任一命题，复合命题为任一命题，复合命题“非非p”（或（或“p的否定的否定”）称为）称为p的的否定式否定式。记作。记作 p 。 为为否定联结词否定联结词。

7、真值表见。真值表见Table 1。(Let p be a proposition. The statement “It is not the case that p.” is another proposition, called the negation of p. The negation of p is denoted by p. The proposition p is read “not p.”)p的否定的否定19Table 1 20EXAMPLE 3 设设p表示表示“离散数学好学离散数学好学”，则则 p表示表示“离散数学难学离散数学难学”。显然，当显然，当p的真值为的真值为0时，时

8、， p的的真值为真值为1。21设设p，q为两命题，复合命题为两命题，复合命题“p并且并且q”（或（或“p和和q”）称作）称作p与与q的的合取式合取式。记作。记作pq。 为为合取联结词合取联结词。真值表见。真值表见Table 2。(Let p and q be propositions. The proposition p and q, denoted by pq, is the proposition that is true when both p and q are true and is false otherwise. The proposition pq is called the

9、conjunction of p and q. )p和和q的合取的合取DEFINITION 2. 22Table 2 23EXAMPLE 4 用用p表示命题表示命题“今天是星期五今天是星期五”，q表示命题表示命题“今天下雨今天下雨”， 则命题则命题p与与q的合取式是什么？的合取式是什么？解答：解答： p与与q的合取式的合取式 pq是是“今天是星期五，而今天是星期五，而且今天下雨。且今天下雨。”如果是星期五，又下雨，则该如果是星期五，又下雨，则该命题为真；如果是除星期五外的任意一天，或命题为真；如果是除星期五外的任意一天，或者虽是星期五但没下雨，则该命题为假。者虽是星期五但没下雨，则该命题为假。

10、24设设p，q为两命题，复合命题为两命题，复合命题“p或或q” 称作称作p与与q的的析取式析取式。记作。记作pq。为为析取联结词析取联结词。真值表见真值表见Table 3。 (Let p and q be propositions.The proposition p or q, denoted by pq,is the proposition that is false when p and q are both false and true otherwise. The proposition pq is called the disjunction of p and q.)p和和q的析取的

11、析取DEFINITION 3. 25Table 3 26还是以还是以Example 4 为例，命题为例，命题p与与q的析取式是什么？的析取式是什么？解答：解答： p与与q的析取式的析取式 pq是是“今天是星期五或今天今天是星期五或今天下雨。下雨。”只有今天既不是星期五，又没有下雨，只有今天既不是星期五，又没有下雨，则该命题为假；如果今天是星期五或者今天下雨则该命题为假；如果今天是星期五或者今天下雨了（包括下雨的星期五），则该命题就为真。了（包括下雨的星期五），则该命题就为真。EXAMPLE 5 27设设p，q为两命题，复合命题为两命题，复合命题“如果如果p，则，则q”称作称作p与与q的的蕴含式

12、蕴含式。 记作记作 pq。称。称p为蕴为蕴含式的含式的前件前件(hypothesis)，q为蕴含式的为蕴含式的后后件件(conclusion)。称作称作蕴含联结词蕴含联结词。真值。真值表见表见Table 4。(Let p and q be propositions.The implication pq is the proposition that is false when p is true and q is false and true otherwise. )如果如果p，则，则q单条件，单条件， 蕴涵蕴涵p：前提：前提 q：结论：结论DEFINITION 4. 28Table 4 29

13、 用用p表示命题表示命题“天下雨天下雨”，用，用q表示命题表示命题“我骑自行车上班我骑自行车上班”，将下列命题符号化：，将下列命题符号化： （1）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。 （2）只有不下雨，我才骑自行车上班。）只有不下雨，我才骑自行车上班。解答：解答： （1）中，）中， p是是q的充分条件，因而符号化为的充分条件，因而符号化为 pq；（2）中，）中， p是是q的必要条件，因而符号化为的必要条件，因而符号化为q p。EXAMPLE 6 30设设p，q为两命题，复合命题为两命题，复合命题“p当且仅当当且仅当q”称称作作p与与q的的等价式等价式。记作。记作pq，

14、称作称作等价联结等价联结词词。真值表见。真值表见Table 5。(Let p and q be propositions, The biconditional pq is the proposition that is true when p and q have the same truth values and is false otherwise.)p当且仅当当且仅当q双条件，等价双条件，等价DEFINITION 5. 31Table 5 32将下一命题符号化：将下一命题符号化： “只有（仅当）只有（仅当）你是计算机科学系的学你是计算机科学系的学生或者你不是新生，你才可以通过校园网生或者

15、你不是新生，你才可以通过校园网上上Internet。”解答：解答： a (cf )EXAMPLE 7 cfa33 将下一命题符号化：将下一命题符号化：“如果你身高如果你身高小于小于4英尺英尺，你就不，你就不能乘能乘坐过山车坐过山车，除非你，除非你超过了超过了16岁岁。”解答：解答：(1) (r s) q.(2) s(r q).EXAMPLE 8 rqs如果你身高小于如果你身高小于4英尺，而英尺，而且你不超过且你不超过16岁，那么你就岁，那么你就不能乘坐过山车。不能乘坐过山车。如果你不超过如果你不超过16岁，那么岁，那么当你身高小于当你身高小于4英尺时，你英尺时，你就不能乘坐过山车。就不能乘坐过

16、山车。34“说离散数学是枯燥无味的或毫无价值说离散数学是枯燥无味的或毫无价值的，那是不对的。的，那是不对的。”p：离散数学是有味道的；：离散数学是有味道的；q：离散数学是有价值的；：离散数学是有价值的；EXAMPLE 9 符号化为：符号化为：( p q)35命题公式及分类命题公式及分类P、Q、R 称为称为原子命题原子命题(Atomic Proposition)。原子命题或加上逻辑联结词组成的表达式成为原子命题或加上逻辑联结词组成的表达式成为复合命题复合命题(Compositional Proposition)。从从命题常量命题常量 到到 命题变量命题变量(Propositional Varia

17、ble)命题公式：命题公式：1. 原子命题是命题公式；原子命题是命题公式；2. 设设P是命题公式，则是命题公式，则 P也是命题公式；也是命题公式；3. 设设P、Q是命题公式，则是命题公式，则(PQ)、(PQ)、(PQ)、(P Q)也是命题公式；也是命题公式；4. 有限次地使用有限次地使用1、2、3所得到的也是命题公式。所得到的也是命题公式。Proposition Formulas, Well-Formed Formulas(wff)36命题公式的运算规则：命题公式的运算规则： 逻辑联接词的优先级：逻辑联接词的优先级： 、 、 、 、 命题公式的表达式的运算规律：命题公式的表达式的运算规律： 同

18、代数表达式同代数表达式命题公式的运算方法：命题公式的运算方法： 所有公式中的命题变量用指定命题（真值）代所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。入（或指派），得到一个公式对应的真值。如果一个命题公式有如果一个命题公式有n个互异的命题变量，个互异的命题变量，则命题公式对应的真值有则命题公式对应的真值有2n种可能分布。种可能分布。37EXAMPLE 10 求下列命题公式的真值表：求下列命题公式的真值表：（1）p (q r ) .38EXAMPLE 10 求下列命题公式的真值表：求下列命题公式的真值表：（2）( p ( pq ) q .39EXAMPLE 10

19、求下列命题公式的真值表：求下列命题公式的真值表：（3） ( pq ) q .40永真式永真式(Tautology)：公式中的命题变量无论怎样公式中的命题变量无论怎样代入，公式对应的真值恒为代入，公式对应的真值恒为1。 永假式永假式(Contradiction)：公式中的命题变量无论公式中的命题变量无论怎样代入，公式对应的真值恒为怎样代入，公式对应的真值恒为0。 可满足式可满足式(Satisfaction)：公式中的命题变量无论公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为怎样代入，公式对应的真值总有一种情况为1。41 （1）设）设P是永真命题公式，则是永真命题公式，则P的否定的否定

20、公式是永假命题公式；公式是永假命题公式； （2）设）设P是永假命题公式，则是永假命题公式，则P的否定的否定公式是永真命题公式；公式是永真命题公式； （3）设）设P、Q是永真命题公式，则是永真命题公式，则 (PQ)、(PQ)、(PQ)、(P Q)也是也是永真命题公式永真命题公式 。 42小小 结结1. 命题的概念：定义、逻辑值、命题的概念：定义、逻辑值、 符号化表示符号化表示2. 从简单命题到复合命题：从简单命题到复合命题： 逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级3. 从命题常量到命题变量，从命题常量到命题变量， 从复合命题到命题公式：从复合命题到命题公式： 命题公式的

21、真值描述：真值表命题公式的真值描述：真值表4. 命题公式的分类：命题公式的分类： 永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式 、一般公式、一般公式 43Propositional Equivalences设设A，B为两命题公式，若等价式为两命题公式，若等价式AB是重是重言式，则称言式，则称A与与B是是等值等值的。记作的。记作AB。(The propositions A and B are called logically equivalent if AB is a tautology. The notation AB denotes that A and B are logi

22、cally equivalent.)逻辑等值，或逻辑等价逻辑等值，或逻辑等价DEFINITION 6. 等值演算等值演算44证明证明( pq )与与pq 是等值的。是等值的。（这个等值关系是德（这个等值关系是德摩根摩根(De Morgan)定律之定律之一。德一。德摩根是十九世纪中叶的英国数学家。）摩根是十九世纪中叶的英国数学家。）解答：真值表见解答：真值表见Table 9。因为对于。因为对于p和和q 所所有可能的组合，有可能的组合， (pq)和和pq的真的真值都相同，所以这两个命题是等值的。值都相同，所以这两个命题是等值的。EXAMPLE 11 45Table 9 46证明证明pq与与pq是等

23、值的。是等值的。解答：真值表见解答：真值表见Table 10。因为对于。因为对于p和和q 所有可能的组合，所有可能的组合， pq 和和pq的真值的真值都相同，所以这两个命题是等值的。都相同，所以这两个命题是等值的。EXAMPLE 12 47Table 10 48证明证明p(qr)与与 (pq)(pr) 是等是等值的。值的。（分配律）（分配律）解答：真值表见解答：真值表见Table 11。因为对于。因为对于p、q和和r所有可能的组合，所有可能的组合， p(qr) 和和(pq)(pr) 的真值都相同，所以这两个命题是等值的。的真值都相同，所以这两个命题是等值的。EXAMPLE 13 49Table

24、 11 50 下面给出下面给出24个重要的等值式个重要的等值式（祥见（祥见P40）：）：双重否定律、等幂律、交换律、结合律、分配律、双重否定律、等幂律、交换律、结合律、分配律、德德摩根律、吸收律、零律、同一律、排中律、矛摩根律、吸收律、零律、同一律、排中律、矛盾式、蕴含等值式、等价等值式、假言易位、等盾式、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。价否定等值式、归谬论。根据已知的等值式，推演出另外一些等值式根据已知的等值式，推演出另外一些等值式的过程称为的过程称为等值演算等值演算。在进行等值演算时，往往。在进行等值演算时，往往用到用到置换规则置换规则。51证明证明(p(pq)与

25、与pq是等值的。是等值的。EXAMPLE 14 0052证明证明(pq) (pq)是重言式。是重言式。EXAMPLE 15 11153判断命题公式逻辑等价的方法：判断命题公式逻辑等价的方法： 1. 真值表真值表 2. 命题公式的演算命题公式的演算 基本等值定理；基本等值定理； 公式的代入不变性（置换规则）；公式的代入不变性（置换规则）； 等值关系的传递性。等值关系的传递性。54命题公式逻辑等价关系的应用：命题公式逻辑等价关系的应用： 1、判定是否逻辑等价（等值）；、判定是否逻辑等价（等值）； 2、判断是否为永真公式或永假公式；、判断是否为永真公式或永假公式； 3、命题公式的化简。、命题公式的化

26、简。55设设p,q为两命题，复合命题为两命题，复合命题“p,q之中恰有一个成立之中恰有一个成立”称为称为p与与q的的排斥或排斥或或或异或异或。记作。记作p q， 称作称作排斥排斥或或或或异或联结词异或联结词。真值表见真值表见Table 12。(Let p and q be propositions.The exclusive or of p and q, denoted by p q,is the proposition that is true when exactly one of p and q is true and is false otherwise.)p和和q的异或的异或DEFI

27、NITION 7. 联结词全功能集联结词全功能集56Table 12 p q (p q)(pq)57设设p,q为两命题，复合命题为两命题，复合命题“p与与q的否定的否定”称为称为p与与q的的与非式与非式。记作。记作p q， 称作称作与与非联结词非联结词。真值表见真值表见Table 13。(Let p and q be propositions.The and not of p and q, denoted by p q, is the proposition that is false when p and q are both true and true otherwise. )p和和q的与

28、非的与非DEFINITION 8. 58Table 13 p q ( pq )59设设p,q为两命题，复合命题为两命题，复合命题“p或或q的否定的否定”称为称为p与与q的的或非式或非式。记作。记作p q， 称作称作或或非联结词非联结词。真值表见真值表见Table 14。(Let p and q be propositions.The or not of p and q, denoted by p q, is the proposition that is true when p and q are both false and false otherwise. )p和和q的或非的或非DEFIN

29、ITION 9. 60Table 14 p q ( pq )61逻辑联结词集是逻辑联结词集是功能完备集功能完备集(Functionally Complete Set)： 任一个命题公式都能够等价于仅包含这些任一个命题公式都能够等价于仅包含这些逻辑联结词联结起来的公式。逻辑联结词联结起来的公式。逻辑联结词集是逻辑联结词集是极小功能完备集极小功能完备集： 是功能完备集并且没有冗余联结词。是功能完备集并且没有冗余联结词。62例例1： 、 、 、 、是功能完备的，但不是是功能完备的，但不是极小功能完备的极小功能完备的。例例2： 、 、 是是极小功能完备的极小功能完备的。例例3： 、 、 是是极小功能完

30、备的极小功能完备的。63DEFINITION 10. 命题公式命题公式P的的对偶公式对偶公式(Dual)：将：将P中的中的 析取联结词换成合取联结词，析取联结词换成合取联结词， 合取联结词换成析取联结词，合取联结词换成析取联结词， 1换成换成0，0换成换成1（如果存在的话）。（如果存在的话）。记为记为P*.对偶与范式对偶与范式64对偶原理对偶原理(Duality Principle)： 设设P，Q是两命题公式，如果是两命题公式，如果 P Q， 则则 P* Q*。例：例：A： (P Q) Q B： P Q这里，这里， A B，分，分析是否析是否A* B*。65命题公式的标准化命题公式的标准化范式

31、范式小项小项(small item)/合取式合取式(conjunctive form): 若干个原子命题或其否定的合取。若干个原子命题或其否定的合取。大项大项(large item)/析取式析取式(disjunctive form): 若干个原子命题或其否定的析取。若干个原子命题或其否定的析取。析取范式析取范式(disjunctive normal form)： 若干个小项的析取。若干个小项的析取。合取范式合取范式(conjunctive normal form)： 若干个大项的合取。若干个大项的合取。66定理的证明思路：定理的证明思路： 1、消去对、消去对 、 来说冗余的联结词；来说冗余的联

32、结词； 2、将否定联结词移到命题变量的前面；、将否定联结词移到命题变量的前面； 3、消除多余的否定联结词；、消除多余的否定联结词； 4、利用分配律化成合取范式和析取范式。、利用分配律化成合取范式和析取范式。定理定理1：任意一个命题公式都存在与之等价的：任意一个命题公式都存在与之等价的 合取范式和析取范式。合取范式和析取范式。范式存在定理范式存在定理例：求（）（）的析取范式： 68令令A(a1、a2、an)是包含有是包含有n个变量的公式，个变量的公式，极小项极小项(extremal ):小项中恰包含小项中恰包含n个变量或其否定。个变量或其否定。极大项极大项(extremal ):大项中恰包含大项

33、中恰包含n个变量或其否定。个变量或其否定。主析取范式主析取范式(Unique disjunctive normal form): 若干个若干个极小项极小项的析取。的析取。主合取范式主合取范式(Unique conjunctive normal form): 若干个若干个极大项极大项的合取。的合取。69 以三个命题变项以三个命题变项p,q,r为例，可形成为例，可形成23=8个个极小项极小项，每个每个极小项极小项对应一个二进制数，也对应一个十进制数，对应一个二进制数，也对应一个十进制数，二进制数是该极小项的二进制数是该极小项的成真赋值成真赋值，十进制数可做该极，十进制数可做该极小项抽象表示法的角码

34、。对应情况如下：小项抽象表示法的角码。对应情况如下： pqr 0000，记作，记作m0； pqr 0011，记作，记作m1； pqr 0102，记作，记作m2； pqr 0113，记作，记作m3； pqr 1004，记作，记作m4； pqr 1015，记作，记作m5； pqr 1106，记作，记作m6； pqr 1117，记作，记作m7。主析取范式主析取范式：如：如m1m2m5可用可用 ( 1,2,5 )表示。表示。70 以三个命题变项以三个命题变项p,q,r为例，可形成为例，可形成23=8个个极大项极大项，每个每个极大项极大项对应一个二进制数，也对应一个十进制数，对应一个二进制数，也对应一个

35、十进制数，二进制数是该极大项的二进制数是该极大项的成假赋值成假赋值，十进制数可做该极，十进制数可做该极大项抽象表示法的角码。对应情况如下：大项抽象表示法的角码。对应情况如下： pqr 0000，记作，记作M0； pqr 0011，记作，记作M1； pqr 0102，记作，记作M2； pqr 0113，记作，记作M3； pqr 1004，记作，记作M4； pqr 1015，记作，记作M5； pqr 1106，记作，记作M6； pqr 1117，记作，记作M7。主合取范式主合取范式：如：如M0 M3 M6可用可用( 0,3,6 )表示。表示。（1）只要命题公式不是永假式，则一定可以根据该命题公式的

36、真值表直接写出其主析取范式，其方法是找出该公式为“”的行，对应写出极小项的析取式，且一定是唯一的。（2）若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2n个极小项。（3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。（4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“”的个数。讨论（5）与命题公式等价的主合范式中极大项的个数等于其真值表中真值为“”的个数。由真值表找极大项的方法为：将表中值为“”的对应真值指派中，把变元写成否定，把变元的否定写成变元。（6）只要命题公式不是永真式，则一定可以写出对应与其等价的唯一的主合取范式。（7）若命题公式为含有

37、个变元的永假式，则主合取范式包含了2n个极大项的合取式。（8）可用主合取范式判定二个命题公式是否等价。（9）已知一个命题公式的主析取范式，则一定可以直接写出与其等价的主合取范式来。反之也行。例： （ ）（）（） 主析取范式 （ ） 主合取范式74EXAMPLE 16 求求pqr的主析取范式和主合取范式：的主析取范式和主合取范式：解：解：( pq )r (p q) ( r r) (r (p p) (p q r) (p q r) (p r) ( p r) (p q r) (p qr) (p r) (qq) ( p r) (qq)(p q r) (p qr) (p q r) (pq r) ( p q

38、 r) ( pq r)(p q r) (p qr) (pq r) ( p q r) ( pq r)m7 m6 m5 m3 m1 ( 1,3,5,6,7 )（主析取范式）（主析取范式）M0 M2 M4 ( 0,2,4) （主合取范式）（主合取范式）75小小 结结1、命题公式的等价演算、命题公式的等价演算2、命题公式的标准化描述、命题公式的标准化描述 表达、分类、判定、应用表达、分类、判定、应用76数理逻辑的主要任务是借助于数学的数理逻辑的主要任务是借助于数学的方法来研究方法来研究推理推理的逻辑。的逻辑。推理推理是从前题推出结论的思维过程，是从前题推出结论的思维过程，前提前提是已知的命题公式，是已

39、知的命题公式，结论结论是从前题出是从前题出发应用推理规则推出的命题公式。发应用推理规则推出的命题公式。推理理论推理理论77DEFINITION 11. 若若A1A2AkB为重言式，则称从为重言式，则称从A1, A2, , Ak推出结论推出结论B的的推理正确推理正确，记作，记作A1A2AkB。B是是A1, A2, , Ak的的逻逻辑结论辑结论或或有效结论有效结论。称称A1A2AkB为推理的为推理的形式结构形式结构。78判断推理是否正确的方法有以下几种：判断推理是否正确的方法有以下几种： （1）真值表法；）真值表法； （2）等值演算法；）等值演算法； （3）主析取范式法。）主析取范式法。（即判断（

40、即判断A1A2AkB是否为重言式）是否为重言式）79EXAMPLE 17 判断下列推理是否正确：判断下列推理是否正确：如果天气凉快，小王如果天气凉快，小王就不去游泳，天气凉快，所以小王没去游泳。就不去游泳，天气凉快，所以小王没去游泳。 解这类推理问题，应先将命题符号化，然后写出解这类推理问题，应先将命题符号化，然后写出前提、结论和推理的形式结构，最后进行判断。前提、结论和推理的形式结构，最后进行判断。 在这里，设在这里，设p：天气凉快；：天气凉快；q：小王去游泳。：小王去游泳。前提：前提：pq, p。结论：。结论：q。推理的形式结构：推理的形式结构： (pq )p)q 。下面分别用三种方法来判

41、断该蕴含式是否为重言式。下面分别用三种方法来判断该蕴含式是否为重言式。80Table 15 （1）真值表法）真值表法 真值表的最后一列全为真值表的最后一列全为1，因而（，因而（*）是重言式，）是重言式，所以推理正确。所以推理正确。81（2）等值演算法）等值演算法 (pq)p)q(pq)p)q(p q)p)q(p q)pq(pq)(pq) 1该蕴含式是重言式，所以推理正确。该蕴含式是重言式，所以推理正确。82(pq)p)q (pq)p)q(pq)p)q(pq)pq(pq)(p(qq)(q(pp)(pq)(pq)(pq)(qp) (qp)(pq)(pq)(pq)(pq)m3m1m0m2 ( 0,1

42、,2,3 )（3）主析取范式法）主析取范式法 该蕴含式的主析取范式中含有该蕴含式的主析取范式中含有4个极小项，因而是重言式。个极小项，因而是重言式。83 为了更好地判断推理的正确性，引入为了更好地判断推理的正确性，引入构造证构造证明明的方法。的方法。 在数理逻辑中，在数理逻辑中，证明证明是一个描述推理过程的是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知命题公式序列，其中的每个命题公式或者是已知的前提，或者是由某些前提应用的前提，或者是由某些前提应用推理规则推理规则得到的得到的结论。其中有些规则建立在结论。其中有些规则建立在推理定律推理定律（重言蕴含（重言蕴含式）的基础之上。式）的基础之上。 重要的重要的8条条推理定律推理定律：附加、化简、假言推理、附加、化简、假言推理、拒取式、析取三段论、假言三段论、等价三段论、拒取式、析取三段论、假言三段论、等价三段论、构造性二难。构造性二难。 除