第1章离散数学命题逻辑

1、数理逻辑概述数理逻辑概述v逻辑：逻辑是人的一种抽象思维，是人通过概念、判逻辑：逻辑是人的一种抽象思维，是人通过概念、判断、推理、论证来理解和区分客观世界的思维过程。断、推理、论证来理解和区分客观世界的思维过程。v数理逻辑：是用数学方法研究逻辑学科。其研究对象数理逻辑：是用数学方法研究逻辑学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形是对证明和计算这两个直观概念进行符号化以后的形式系统。式系统。v数理逻辑的发展：数理逻辑的发展：莱布尼兹的设想：能不能创造一种莱布尼兹的设想：能不能创造一种“通用的科学语通用的科学语言言”，可以把推理过程象数学一样利用公式来进行计，可以把推理过程象数

2、学一样利用公式来进行计算，从而得出正确的结论。算，从而得出正确的结论。布尔、弗雷格的符号化布尔、弗雷格的符号化 v数理逻辑的基本内容：命题演算和谓词演算数理逻辑的基本内容：命题演算和谓词演算 推论 ：每个X都是Y，一些Z是X，因此一些Z是Y填入内容：每个传记作者都是作家，有些政治家是传记作者，因此，有些政治家是作家在上述推理中，论证的合理性与内容无关，而是由一般形式的逻辑正确性来保证的推论中的X，Y和Z表明了插入语句的位置，在数理逻辑中称为“逻辑变量”第第1章章 命题逻辑命题逻辑命题逻辑：也称命题演算，它与一阶逻辑命题逻辑：也称命题演算，它与一阶逻辑构成数理逻辑的基础，而命题逻辑又是一构成数理

3、逻辑的基础，而命题逻辑又是一阶逻辑的基础。数理逻辑是用数学方法即阶逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。，数理逻辑又名为符号逻辑。命题逻辑是研究由命题为基本单位构成的命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。前提和结论之间的可推导关系。学习要求学习要求 深刻理解命题、逻辑连接词以及复合命题的概念深刻理解命题、逻辑连接词以及复合命题的概念。深刻理解公式及其解释的概念。深刻理解公式及其解释的概念。深刻理解原子、公式的永真性、永假性、可满足深刻理解原子、公式的永真性、永假性、可满足性。

4、性。 掌握用基本等价公式对公式进行等价变换的方掌握用基本等价公式对公式进行等价变换的方法。法。 深刻理解公式范式的概念。深刻理解公式范式的概念。 熟练掌握用主析取范式判断任意两个公式是否等熟练掌握用主析取范式判断任意两个公式是否等价的方法。价的方法。掌握命题逻辑的判定方法。掌握命题逻辑的判定方法。掌握形式演绎的方法。掌握形式演绎的方法。 1.1 命题符号化与联结词命题符号化与联结词一一 命题的概念：（描述）命题的概念：（描述）所谓命题，是指具有非真必假的陈述句。而疑问所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故句、祈使句和感叹句等因都不能判断其真假，故都

5、不是命题。命题仅有两种可能的真值都不是命题。命题仅有两种可能的真值-真和真和假，且二者只能居其一。真用假，且二者只能居其一。真用1 1或或T T表示，假用表示，假用0 0或或F F表示。由于命题只有两种真值，所以称这种逻辑表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定不是由人的主观决定 问题：如何判断句子是命题？（问题：如何判断句子是命题？（P1） 如何判断命题的真值？如何判断命题的真值？ 例：例： P1例例1.1二 命题的种类：命题的种类：简单命题（原子命题）：如果一陈述句再也不简单命题（原子命

6、题）：如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。本原子命题。原子命题是命题逻辑的基本单位。本书中用小写英文字母表示简单命题书中用小写英文字母表示简单命题复合命题：它由原子命题、命题联结词和圆括复合命题：它由原子命题、命题联结词和圆括号组成。例：号组成。例： P2例例1.2命题常项（命题常元）；命题变项（命题变元命题常项（命题常元）；命题变项（命题变元）三三 、联结词与复合命题符号化、联结词与复合命题符号化 1.联结词联结词否定联结词：否定联结词： P2定义定义1.1合取联结词：合取联结词： P2

7、定义定义1.2析取联结词：析取联结词： P3定义定义1.3蕴涵联结词：蕴涵联结词： P3定义定义1.4等价联结词等价联结词 ： P4定义定义1.5定义定义1.1设设p表示一个命题，由命题联表示一个命题，由命题联 结词结词和命题和命题p连接成连接成 p p，称，称 p为为p的否的否定式复合命题，定式复合命题， p读读“非非p”。称。称 为否为否定联结词。定联结词。 p是真，当是真，当 且仅当且仅当p为假；为假； p是假，当且仅当是假，当且仅当p为真。否定联结词为真。否定联结词“”的定义可由的定义可由表表1.1表示之。表示之。定义定义1.2 设设p和和q为两个命题，由命题联结为两个命题，由命题联结

8、词词将将p和和q连接成连接成pq，称，称pq为命题为命题p和和q的合取式复合命题，的合取式复合命题，pq读做读做“p与与q”，或，或“p且且q”。称。称为合取联结词为合取联结词。当且仅当。当且仅当p和和q的真值同为真，命题的真值同为真，命题pq的真值才为真；否则，的真值才为真；否则，pPq的真的真值为假。合取联结词值为假。合取联结词的定义由表的定义由表1.2表示之。表示之。p与与q的合取表达的逻辑关系是：的合取表达的逻辑关系是：p与与q两两个命题同时成立。因而自然语言中个命题同时成立。因而自然语言中“既既又又”，“不仅不仅而且而且”，“虽然虽然但是但是 ”等，都可以符号等，都可以符号化为化为（

9、1）李平既聪明又用功）李平既聪明又用功（2）李平虽然聪明，但不用功）李平虽然聪明，但不用功（3）李平不但聪明而且用功）李平不但聪明而且用功注意：句中的注意：句中的“和和”、“与与”例：王兰和陈芳是好朋友例：王兰和陈芳是好朋友（4）李平不是不聪明而是不用功）李平不是不聪明而是不用功定义定义1.3 设设p和和q为两个命题，由命题联为两个命题，由命题联结词结词把把p和和q连接成连接成pq，称，称pq为为命题命题p和和q的析取式复合命题，的析取式复合命题，pq读做读做“p或或q”。称。称为析取联结词。为析取联结词。当且仅当当且仅当p和和q的真值同为假，的真值同为假，pq的的真值为假；否则，真值为假；否

10、则，pq的真值为真。的真值为真。析取联结词析取联结词的定义由表的定义由表1.3表示之表示之。析取式析取式p q表示的是一种相容或，即允表示的是一种相容或，即允许许p与与q同时为真同时为真自然语言中的或具有二义性，即有时表现自然语言中的或具有二义性，即有时表现为相容或，有时表现为排斥或为相容或，有时表现为排斥或 例例王燕学过英语或法语王燕学过英语或法语派小王或小李中的一人去开会派小王或小李中的一人去开会p q(p q) ( p q)定义定义1.4设设p和和q为两个命题，由命题联结为两个命题，由命题联结词词把把p和和q连接成连接成pq，称，称pq为命题为命题p和和q的蕴涵式复合命题，简称条件命题。

11、的蕴涵式复合命题，简称条件命题。pq读做读做“p蕴涵蕴涵q”或者或者“如果如果p则则q”。称。称为为蕴涵联结词。蕴涵联结词。当当p的真值为真而的真值为真而q的真值为假时，命题的真值为假时，命题pq的真值为假；否则，的真值为假；否则，pq的真值为真的真值为真。条件联结词。条件联结词的定义由表的定义由表1.4表示之。表示之。在蕴涵命题在蕴涵命题 pq 中，命题中，命题p称为称为 pq 的前的前件或前提，命题件或前提，命题q称为称为pq的后件或结论。的后件或结论。pq 表示的基本逻辑关系是：表示的基本逻辑关系是：“p是是q的充的充分条件分条件”或或“q是是p的必要条件的必要条件”。条件命题条件命题p

12、q有多种方式陈述：有多种方式陈述：“如果如果p，那么，那么q”；“只要只要p，就，就q”： “p仅当仅当q”；“只有只有q才才p”；等。；等。在日常生活中，用条件式表示前提和结论之在日常生活中，用条件式表示前提和结论之间的因果或实质关系，这种条件式称为形式条间的因果或实质关系，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称提并不要求与结论有任何关系，这种条件式称为实质条件命题。采用实质条件式作定义，不为实质条件命题。采用实质条件式作定义，不单是出于单是出于“善意推断善意推断”，主要是因为前提与结，主要

13、是因为前提与结论间有无因果和实质关系难以区分，而且实质论间有无因果和实质关系难以区分，而且实质条件式已包含了形式条件式，更便于应用。条件式已包含了形式条件式，更便于应用。因此在数理逻辑中，因此在数理逻辑中，p与与q不必一定有内在必不必一定有内在必然联系然联系只要天不下雨，我就骑自行车上班只要天不下雨，我就骑自行车上班只有天不下雨，我才骑自行车上班只有天不下雨，我才骑自行车上班若若2+2=4，则太阳从东方升起，则太阳从东方升起如果明天天气晴朗，我们就去郊游如果明天天气晴朗，我们就去郊游pqpqpq注意：在数理逻辑中，注意：在数理逻辑中，pq中中的的p与与q不一定有内在联系不一定有内在联系注意：在

14、数理逻辑中，当前件注意：在数理逻辑中，当前件p为假时，为假时，pq为真。这一点为真。这一点与日常逻辑不同与日常逻辑不同q p定义定义1.5令令p、q是两个命题，由命题联是两个命题，由命题联结词结词把把p和和q连接成连接成p q，称，称p q为为命题命题p和和q的等价式复合命题，简称等价的等价式复合命题，简称等价命题，命题，p q读做读做“p当且仅当当且仅当q”，或，或“p等价等价q”。称。称为等价联结词。当为等价联结词。当p和和q的的真值相同时，真值相同时，p q的真值为真；否则，的真值为真；否则，p q的真值为假。等价联结词的真值为假。等价联结词的定义的定义由表由表1.5表示之。表示之。2.

15、复合命题的符号化（重点内容）复合命题的符号化（重点内容） 步骤：步骤： (1) 分析出各简单命题，将它们符号化；分析出各简单命题，将它们符号化；（2）分析各简单命题之间的关系，选择使）分析各简单命题之间的关系，选择使用合适的联结词，把简单命题逐个联结起来，用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示；组成复合命题的符号化表示； 例：例： P4 例例1.6作业：作业：P32 1.4 1.51.2 命题公式及分类命题公式及分类 命题常元与命题变元的概念命题常元与命题变元的概念在命题逻辑中，命题有命题常元（常值命在命题逻辑中，命题有命题常元（常值命题）和命题变元（命题变项）之分。

16、一个有题）和命题变元（命题变项）之分。一个有确定的具体值的命题，称为命题常元；一个确定的具体值的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值时也说对该命题变元指派真值。命题常元和命题常元和命题变元均可用字母命题变元均可用字母p、q、r或或pi、qi、ri等等表示表示 命题公式和合式公式的概念：命题公式和合式公式的概念：命题公式：从形式上看，命题公式由命命题公式：从

17、形式上看，命题公式由命题常元（常值命题）、命题变元（命题常元（常值命题）、命题变元（命题变项）和括号经命题联结词构成的题变项）和括号经命题联结词构成的字符串，但这个字符串必须按一定的字符串，但这个字符串必须按一定的规则构成，即它是合式公式规则构成，即它是合式公式合式公式：经定义的，有规则可循的命合式公式：经定义的，有规则可循的命题公式。通常我们将合式公式称为命题公式。通常我们将合式公式称为命题公式题公式定义定义1.6 合式公式是由下列规则生成的合式公式是由下列规则生成的公式：公式：单个命题常元或变元是合式公式。单个命题常元或变元是合式公式。若若A是一个合式公式，则是一个合式公式，则(A)也是一

18、个也是一个合式公式。合式公式。若若A、B是合式公式，则是合式公式，则(AB)、(AB)、(AB)和和(A B)都是合式公都是合式公式。式。只有有限次使用、和生成的公只有有限次使用、和生成的公式才是合式公式。式才是合式公式。(P5)三三 命题公式的层次和真值表（重点内命题公式的层次和真值表（重点内容）容） 命题公式的层次定义命题公式的层次定义 见书见书P5 什么是真值表：将命题公式在所有赋真值表：将命题公式在所有赋值之下取值之下取 值的情况列成的表值的情况列成的表 构造真值表的步骤：见构造真值表的步骤：见P6 例：例：P6例例1.7作业：作业：P32 1.6（1），）， P33 1.7（1）,（

19、5）,（10）设设 A 为任意公式，则为任意公式，则 对应每一个赋值，公式对应每一个赋值，公式 A的真值均相的真值均相应确定为真，称应确定为真，称 A 为重言式，或永真为重言式，或永真式。式。 对应每一个赋值，公式对应每一个赋值，公式 A的真值均相的真值均相应确定为假，称应确定为假，称 A 为矛盾式，或永假为矛盾式，或永假式。式。 至少存在一个赋值，公式至少存在一个赋值，公式 A的的真值相真值相应确定为真，称应确定为真，称 A 为可满足式为可满足式。 四四 公式分类公式分类例：例：P7的表的表1-1,1-2,1-3由定义可知，重言式必是可满足式，反之由定义可知，重言式必是可满足式，反之一般不真

20、。一般不真。今后重点将研究重言式，因为它最有用，今后重点将研究重言式，因为它最有用，它有以下特点：它有以下特点：重言式的否定是矛盾式，矛盾式的否定重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。是重言式，这样只研究其一就可以了。两个重言式的合取式、析取式、蕴涵式两个重言式的合取式、析取式、蕴涵式和等价式等都仍是重言式。于是，由简和等价式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。单的重言式可构造出复杂的重言式。1.3 等值演算等值演算一一 等价公式等价公式定义：定义：设设A和和B是两个命题公式，如果是两个命题公式，如果A、B在其在其任意赋值下，其真值都是相同的

21、，则称任意赋值下，其真值都是相同的，则称A和和B是等价的，或逻辑相等，记作是等价的，或逻辑相等，记作AB，读作，读作A等价等价B，称，称AB为等价式。为等价式。显然，若公式显然，若公式A和和B的真值表是相同的，则的真值表是相同的，则A和和B等价。因此，验证两公式是否等价，只需做等价。因此，验证两公式是否等价，只需做出它们的真值表即可。出它们的真值表即可。 例：例：P8 例例1.8注意：注意：和和的区别的区别是逻辑联结词，它出现在命题公式中，是逻辑联结词，它出现在命题公式中，表示两个命题之间的一种逻辑关系。表示两个命题之间的一种逻辑关系。不是逻辑联结词，表示两个命题公式的不是逻辑联结词，表示两个

22、命题公式的一种关系，不属于这两个公式的任何一一种关系，不属于这两个公式的任何一个公式中的符号。个公式中的符号。等价式有下列性质：等价式有下列性质： 自反性，即对任意公式自反性，即对任意公式A，有，有A A 对称性，即对任意公式对称性，即对任意公式A和和B， 若若A B，则，则B A 传递性，即对任意公式传递性，即对任意公式A、B和和C， 若若A B、B C，则，则A C二二 基本等价式基本等价式命题定律命题定律给定给定n n（n n1）个命题变项，按合式公式的形个命题变项，按合式公式的形式规则可以形成无穷多个命题公式，但其中只式规则可以形成无穷多个命题公式，但其中只有有2 22 2n n个真值

23、不同的命题公式。见个真值不同的命题公式。见P8 P8 表表1-41-4在判定公式间是否等价，有一些简单而又经在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定常使用的等价式，称为基本等价式或称命题定律（律（2424个）。牢固地记住它并能熟练运用，是个）。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一。学好数理逻辑的关键之一。见书见书P9 P9 三三 等值演算（重点内容）等值演算（重点内容） 根据已知的等值式推演出另外一些等值式根据已知的等值式推演出另外一些等值式的过程。的过程。1.演算规则：演算规则：代入规则和替换规则代入规则和替换规则代入规则代入规则： 在一个

24、永真式在一个永真式A A中，任何一个原子中，任何一个原子 命题变元命题变元r r出现的每一处，出现的每一处， 用另一个公用另一个公式代入，所得公式式代入，所得公式B B仍是永真式。本定理称为仍是永真式。本定理称为代入规则。代入规则。置换规则置换规则： 设设A A1是合式公式是合式公式A A的子公式，若的子公式，若A A1B B1，并且将，并且将A A中的中的A A1用用B B1 替换得到公替换得到公式式B B，则，则A AB B。称该定理为置换规则。称该定理为置换规则。代入和置换有两点区别：代入和置换有两点区别： 代入是对原子命题变元而言的，代入是对原子命题变元而言的，而置换可对命题公式实行。

25、而置换可对命题公式实行。 代入必须是处处代入，置换则可代入必须是处处代入，置换则可部分替换，亦可全部替换。部分替换，亦可全部替换。2.演算举例演算举例 例例1 P10 例例1.9、1.10、1.11作业：作业： 试证语句：试证语句：“不会休息的人也不会休息的人也不会工作，没有丰富知识的人也不会工不会工作，没有丰富知识的人也不会工作作”，与语句：，与语句：“工作的好的人一定会工作的好的人一定会休息并且有丰富的知识休息并且有丰富的知识”逻辑一致逻辑一致1.4 范式（命题公式的标准式）范式（命题公式的标准式）1.简单合取式和简单析取式简单合取式和简单析取式 P12 定义定义1.122.析取范式和合取

26、范式（非标准式）析取范式和合取范式（非标准式） P12 定义定义1.133.主析取范式和主合取范式（标准式）主析取范式和主合取范式（标准式） P14定义定义1.15和和P14定理定理1.3例如例如:公式公式p， q，p q和和 p q p p等都等都是是 简单合取式，而简单合取式，而p，q和和 p为相应的简为相应的简单合取式的合取项；公式单合取式的合取项；公式p， q，p q， p q p等都是简单析取式，而等都是简单析取式，而p，q和和 p为相应简单析取式的析取项。为相应简单析取式的析取项。 注意注意:一个命题变元或其否定既可以是简单一个命题变元或其否定既可以是简单 合取式，也可以是简单析取

27、式，如例合取式，也可以是简单析取式，如例中中p， q等。等。定理定理: 简单合取式为永假式的充要条件是：简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。它同时含有某个命题变元及其否定。定理：定理：简单析取式为永真式的充要条件是：简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。它同时含有某个命题变元及其否定。范式存在定理：范式存在定理：对于任何一命题公式，都存在与其对于任何一命题公式，都存在与其等价的析取范式和合取范式。（等价的析取范式和合取范式。（P13）求范式算法：求范式算法： 使用命题定律，消去公式中除使用命题定律，消去公式中除 、 和和以外以外 公式公式中

28、出现的所有联结词；中出现的所有联结词； 使用使用 ( P)P和德和德摩根律，将公式中出现摩根律，将公式中出现 的联的联结词结词 都移到命题变元之前；都移到命题变元之前； 利用结合律、分配律等将公式化成析取范式利用结合律、分配律等将公式化成析取范式 或合或合取范式。取范式。举例：举例：P13 P13 例例1.121.12（析取范式与合取范式具有不唯一性）析取范式与合取范式具有不唯一性）.主析取范式主析取范式(1) 极小项的概念和性质极小项的概念和性质 定义：定义： 在含有在含有n个命题变元的简单合取式中，个命题变元的简单合取式中， 若每个命题变元与其否定不同时存在，而二若每个命题变元与其否定不同

29、时存在，而二者之一出现一次且仅出现一次，则称该简单者之一出现一次且仅出现一次，则称该简单合取式为极小项，或称布尔积。合取式为极小项，或称布尔积。例如：两个命题变元例如：两个命题变元p和和q，其构成的极小项有，其构成的极小项有p q，p q， p q和和 p q； 而三个命题变元而三个命题变元p、q和和r，其构成的极小项，其构成的极小项有有p q r ，p q r，p q r，p q r， p q r， p q r， p q r， p q r。可以证明：可以证明：n个命题变元共形成个命题变元共形成2n个极小项个极小项。如果将命题变元按字典序排列，并且把命题变元如果将命题变元按字典序排列，并且把命

30、题变元与与1对应，命题变元的否定与对应，命题变元的否定与0对应，则可对对应，则可对2n个极小项依二进制数编码，记为个极小项依二进制数编码，记为mi，其下标，其下标i是是由二进制数转化的十进制数。用这种编码所求由二进制数转化的十进制数。用这种编码所求得得2n个极小项的真值表，可明显地反映出极小个极小项的真值表，可明显地反映出极小项的性质。项的性质。 表表1.5.1和表和表1.5.2分别给出了分别给出了2个命题变元个命题变元p和和q、3个命题变元个命题变元p、q和和r的极小项真值表。的极小项真值表。 续续 表表m(二二 )m1 0 0m1 0 1m1 1 0m1 1 1P Q R P Q R P

31、Q R P Q R P Q R0 0 000000 0 100000 1 000000 1 100001 0 010001 0 101001 1 000101 1 10001m(+ )m4m5m6m7(2) 主析取范式定义与存在定理主析取范式定义与存在定理定义定义 在给定命题公式的析取范式中，若其简单在给定命题公式的析取范式中，若其简单合取式都是极小项，合取式都是极小项， 则称该范式为主析取范则称该范式为主析取范式。式。定理定理 任意含任意含n个命题变元的非永假命题公式个命题变元的非永假命题公式A 都存在与其等价的主析取范式。都存在与其等价的主析取范式。从表从表1.5.1、1.5.2可看出，极

32、小项有如下性质：可看出，极小项有如下性质：(a)没有两个极小项是等价的，即是说各极小项没有两个极小项是等价的，即是说各极小项的真值表都是不同的；的真值表都是不同的；(b)任意两个不同的极小项的合取式是永假的：任意两个不同的极小项的合取式是永假的：mi mj ，i j(c)所有极小项之析取为永真：所有极小项之析取为永真： mi(d)每个极小项只有一个解释为真，且其真值每个极小项只有一个解释为真，且其真值1位位于主对角线上。于主对角线上。ni 1.主合取范式主合取范式(1) 极大项的概念和性质极大项的概念和性质定义定义 在在n个命题变元的简单析取式中，若每个个命题变元的简单析取式中，若每个命题变元

33、与其否定不同时存在，而二者之一命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取必出现一次且仅出现一次，则称该简单析取式为极大项，或称布尔和。式为极大项，或称布尔和。例如：由两个命题变元例如：由两个命题变元p和和q，构成极大项有，构成极大项有p q q，p q， p q q， p q； 三个命题变元三个命题变元p，q和和r，构成，构成p q q r r，p q q r，p q r r，p q r， p q r r， p q q r， p q r， p q r。能够证明：能够证明：n个命题变元共有个命题变元共有2n个极大项。个极大项。如果将如果将n个命题变元排序，并且把

34、命题变元与个命题变元排序，并且把命题变元与对应，命题变元的否定与对应，则可对对应，命题变元的否定与对应，则可对2n个个极大项按二进制数编码，记为极大项按二进制数编码，记为Mi，其下标，其下标i是是由二进制数化成的十进制数。用这种编码所求由二进制数化成的十进制数。用这种编码所求的的2n个极大项的真值表，能直接反映出极大项个极大项的真值表，能直接反映出极大项的性质。的性质。 表表1.5.3给出了给出了2个命题变元个命题变元p和和q构成所有极大项构成所有极大项的真值表。的真值表。从表从表1.5.3可看出极大项的性质：可看出极大项的性质：(a)没有两个极大项是等价的。没有两个极大项是等价的。(b)任何

35、两个不同极大项之析取是永真的，即任何两个不同极大项之析取是永真的，即Mi M j，i j。(c) 所有极大项之合取为永假，即所有极大项之合取为永假，即Mi。(d) 每个极大项只有一个解释为假，且其真值每个极大项只有一个解释为假，且其真值0位于主对角线上。位于主对角线上。 类似可给出个命题变元类似可给出个命题变元p、q和和r的所有极大的所有极大项的真值表，留给同学们完成。项的真值表，留给同学们完成。.主范式的应用主范式的应用 利用主范式可以求解判定问题或者证明等价式成立。利用主范式可以求解判定问题或者证明等价式成立。（1）判定问题）判定问题 根据主范式的定义和定理，也可以判定含根据主范式的定义和

36、定理，也可以判定含n个命题变个命题变元的公式类型，其关键是先求出给定公式的主范式元的公式类型，其关键是先求出给定公式的主范式；其次按下列条件判定之：；其次按下列条件判定之：(a)若若A，或，或A可化为与其等价的、含可化为与其等价的、含2n个极小项的个极小项的主析取范式，则主析取范式，则A为永真式。为永真式。b)若若A，或，或A可化为与其等价的、含可化为与其等价的、含2n个极大项的主个极大项的主合取范式，则合取范式，则A为永假式。为永假式。(c)若若A不与不与或者或者等价，且又不含等价，且又不含2n个极小项或者极个极小项或者极大项，则大项，则A为可满足的。为可满足的。（2）证明等价式成立）证明等

37、价式成立由于任一命题公式的主范式是唯一的由于任一命题公式的主范式是唯一的，所以将给定的公式求出其主范式，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价若主范式相同，则给定两公式是等价的。的。问题：求给定命题公式的主析取范式？问题：求给定命题公式的主析取范式？ （ 重点内容重点内容）若求出命题公式的主析取范式，则可以若求出命题公式的主析取范式，则可以直接写出其真值表；若已知命题公式的直接写出其真值表；若已知命题公式的真值表，则可以立即写出其主析取范式真值表，则可以立即写出其主析取范式 例：例：P14 例例1.13 P14 例例1.14 作业作业: P33 1.12 (1)、(3)

38、1.5 联结词全功能集联结词全功能集一一 其他联结词其他联结词 排斥或（异或）排斥或（异或）与非与非或非或非真值表请真值表请同学们自同学们自己列己列二二 联结词全功能集联结词全功能集问题：问题： 八个命题联结词能否构造所有的八个命题联结词能否构造所有的命题公式呢？最少需命题公式呢？最少需 要多少个联结词才要多少个联结词才能表达所有的联结词呢？能表达所有的联结词呢？首先看含有首先看含有2个变元的命题公式个变元的命题公式A（p， q）有多少种？有多少种？p q123456780 0000000000 1000011111 0001100111 101010101A(p q)0pqp q9101112131415160 0111111110 1000011111 0001100111 101010101A(p q)p q q pp q1p qp q( p q)q pp q (q p)p qp q定义：一个由联结词作为其元素的集合，定义：一个由联结词作为其元素的集合， 如果用如果用该集合中联结词所构成的命题公式足以把一切真该集合中联结词所构成的命题公式足以把一切真值函数值函数(真值表真值表)逻辑等值逻辑等值(同真假同真假)地表达出来，地表达出来， 则这