离散数学第1章

1、离散数学朱平相关说明 教材:离散数学,李盘林 学时:64(48) 考试:期末笔试80%+平时20%(点名、作业) 主要内容：命题逻辑、谓词逻辑、集合、关系、函数 以及图论相关知识(64)第一讲命题逻辑 命题逻辑，也称命题演算，记为Ls。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入符号研究推理的学问。因此，数理逻辑又名为符号逻辑。 命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。 1.1 命题与联结词 1.2 命题变元和合式公式 1.3 公式分类与等价公式 1.4 对偶式与蕴涵式 1.5 联结词的扩充与功能完全组 1.6 公式标准型

2、范式 1.7 公式的主范式 1.8 命题逻辑的推理理论1.1 命题与联结词. 命题的概念 所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。1.1 命题与联结词命题命题: 判断结果惟一的陈述句判断结果惟一的陈述句命题的真值命题的真值: 判断的结果判断的结果真值的取值真值的取值: 真与假真与假真命题真命题: 真值为真的命题真值为真的命题假命题假命题: 真值为假的命题真值为假

3、的命题注意注意: 感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不陈述句中的悖论以及判断结果不惟一确定的也不是命题是命题 例例 下列句子中那些是命题？下列句子中那些是命题？ (1) 是无理数是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？你有铅笔吗？ (5) 这只兔子跑得真快呀！这只兔子跑得真快呀！ (6) 请不要讲话！请不要讲话！ (7) 我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题2 如果一陈述句

4、再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。 命题分为两类，第一类是原子命题，原子命题用大写英文字母P，Q，R及其带下标的Pi，Qi，Ri，表示。 第二类是复合命题，它由原子命题、命题联结词和圆括号组成。简单命题符号化简单命题符号化 2用英文字母用英文字母 p, q, r, , ,pi, ,qi, ,ri (i1）表示）表示简单命题简单命题用用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p： 是有理数，则是有理数，则 p 的真值为的真值为 0 q：2 + 5 = 7，则，则 q 的真值为的真值为 1 . 命题联结词 定义1.1.1设

5、P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否定式复合命题， lP读“非P”。称l为否定联结词。lP是真，当且仅当P为假；lP是假，当且仅当P为真。否定联结词“l”的定义可由表1.1.1表示之。表 1 .1 .1 的 定 义P P1001由于“否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。定义1.1.2设P和Q为两个命题，由命题联结词将P和Q连接成PQ，称PQ为命题P和Q的合取式复合命题，PQ读做“P与Q”，或“P且Q”。称为合取联结词。当且仅当P和Q的真值同为真，命题PQ的真值才为真；否则，PQ的真值为假。合取联结词的定义由表1.1.2表示之。表 1 .1 .

6、2 的 定 义P QP Q0 00 11 01 10001 例例 将下列命题符号化将下列命题符号化. (1) 王晓既用功又聪明王晓既用功又聪明. (2) 王晓不仅聪明，而且用功王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生张辉与王丽都是三好生. (5) 张辉与王丽是同学张辉与王丽是同学. 解解 令令 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1) pq (2) pq (3) p q. 例例 (续续) 令令 r : 张辉是三好学生，张辉是三好学生，s :王丽是三好学生王丽是三好学生 (4) rs. (5) 令令 t

7、 : 张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题 .说明说明: (1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性. (5) 中中“与与”联结的是句子的主语成分，因而联结的是句子的主语成分，因而(5)中句子是简单命题中句子是简单命题.定义1.1.3设P和Q为两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的析取式复合命题，PQ读做“P或Q”。称为析取联结词。当且仅当P和Q的真值同为假，PQ的真值为假；否则，PQ的真值为真。析取联结词的定义由表1.1.3表示之。表表 1 .1 .3 的的 定定 义义P Q P Q0 00 11 01 10111

8、例例 将下列命题符号化将下列命题符号化 (1) 2或或4是素数是素数. (2) 2或或3是素数是素数. (3) 4或或6是素数是素数. (4) 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨. (5) 王晓红生于王晓红生于1975年或年或1976年年. 解解 令令 p:2是素数是素数, q:3是素数是素数, r:4是素数是素数, s:6是素是素数数, 则则 (1), (2), (3) 均为相容或均为相容或. 分别符号化为分别符号化为: pr , pq, rs, 它们的真值分别为它们的真值分别为 1, 1, 0. n (4) 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.n

9、 (5) 王晓红生于王晓红生于1975年或年或1976年年. 而而 (4), (5) 为排斥或为排斥或. 令令 t :小元元拿一个苹果，小元元拿一个苹果，u:小元元拿一个梨，小元元拿一个梨， 则则 (4) 符号化为符号化为 (t u) ( tu). 令令v :王晓红生于王晓红生于1975年年, ,w: :王晓红生于王晓红生于1976年年, ,则则 (5) 既可符号化为既可符号化为 (v w)( vw), 又可又可符号化为符号化为 vw , 为什么为什么? 由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别的联结词定义之。 与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系

10、。定义1.1.4设P和Q为两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的条件式复合命题，简称条件命题/蕴涵式。PQ读做“P条件Q”或者“若P则Q”。称为条件联结词/蕴涵联结词。P为前件，Q为后件。当P的真值为真而Q的真值为假时，命题PQ的真值为假；否则，PQ的真值为真。条件联结词的定义由表1.1.4表示之。表表 1 .1 .4 的的 定定 义义P QP Q0 00 11 01 11101 在条件命题PQ中，命题P称为PQ的前件或前提，命题Q称为PQ的后件或结论。条件命题PQ有多种方式陈述： “如果P，那么Q”；“P仅当Q”；“Q每当P”；“P是Q的充分条件”；“Q是P的必要条件

11、”等。 例例 设设 p p: :天冷，天冷，q q: :小王穿羽绒服，小王穿羽绒服， 将下列命题符号化将下列命题符号化 (1) 只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候小

12、王穿羽绒服仅当天冷的时候.注意：注意： pq 与与 qp 等值（真值相同）等值（真值相同） pqpq qppqqp qp pqqp pq 的逻辑关系的逻辑关系: q为为p的必要条件的必要条件“如果如果p,则则q” 的多种表述方式：的多种表述方式： 若若p,就就q 只要只要p,就就q p仅当仅当q 只有只有q 才才p 除非除非q, 才才p 除非除非q, 否则非否则非p当当p为假时，为假时，pq为真为真(不管不管q为真为真, 还是为假还是为假)在日常生活中，用条件式表示前提和结论之间的因果或实质关系，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式

13、称为实质条件命题。采用实质条件式作定义，不单是出于“善意推断”，主要是因为前提与结论间有无因果和实质关系难以区分，而且实质条件式已包含了形式条件式，更便于应用。定义1.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.1.5表示之。表表 1 .1 .5 的的 定定 义义P QP Q0 00 11 01 11001例例 求下列复合命题的真值求下列复合命题的真值

14、(1) 2 + 2 4 当且仅当当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数. (3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起. (4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲. (5) 函数函数 f (x) 在在x0 可导的充要条件是它在可导的充要条件是它在 x0连续连续. 它们的真值分别为它们的真值分别为 1，0，1，0，0.以上给出了以上给出了5个联结词：个联结词： , , , , ，组成，组成一个联结词集合一个联结词集合 , , , , ， 联结词的优先顺序为：联结词的优先顺序为： , , , , ;

15、 如果出如果出现的联结词同级，又无括号时，则按从左到右现的联结词同级，又无括号时，则按从左到右的顺序运算的顺序运算; 若遇有括号时，应该先进行括号若遇有括号时，应该先进行括号中的运算中的运算. 在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请同学认真去领会。1.2 合式公式 . 命题变元 在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这

16、时也说对该命题变元指派真值。 命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下： 定义1.2.1以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。 2.合式公式 通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。 定义1.2.2单个命题变元和命题常元称为原子命题公式，简称原子公式。 定义定义1.2.3合式公式是由下列规则生成的合式

17、公式是由下列规则生成的公式：公式： 单个原子公式是合式公式。单个原子公式是合式公式。 若若A是一个合式公式，则是一个合式公式，则(l lA)也是一个合式也是一个合式公式。公式。 若若A、B是合式公式，则是合式公式，则(AB)、(AB)、(AB)和和(A B)都是合式公式。都是合式公式。 只有有限次使用、和生成的公式才是只有有限次使用、和生成的公式才是合式公式。合式公式。例如例如 0, p, p q, (p q) ( p r), p qr, (pq)r当合式公式比较复杂时，常常使用很多圆括当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定号，为了减少圆括号的使用量，可

18、作以下约定（见教材（见教材P6中间）：中间）：规定联结词的优先级由高到低的次序为：规定联结词的优先级由高到低的次序为：l l、 相同的联结词按从左至右次序计算时，圆相同的联结词按从左至右次序计算时，圆括号可省略。括号可省略。最外层的圆括号可以省略。最外层的圆括号可以省略。为了方便计，合式公式也简称公式。为了方便计，合式公式也简称公式。. 公式真值表公式真值表定义定义1.2.4对于公式中所有命题变元的每一对于公式中所有命题变元的每一种可能的真值指派，也叫公式的一个赋值或解释。种可能的真值指派，也叫公式的一个赋值或解释。将公式在所有赋值之下取值的情况列成表，称为将公式在所有赋值之下取值的情况列成表

19、，称为该公式的真值表。该公式的真值表。含含n个命题变元的公式，共有多少组赋值？个命题变元的公式，共有多少组赋值？定义定义1.2.5如果如果B是公式是公式A中的一部分，且中的一部分，且B为公式，则称为公式，则称B是公式是公式A的子公式。的子公式。用归纳法不难证明，对于含有用归纳法不难证明，对于含有n个命题变元个命题变元的公式，有的公式，有2n个真值指派，即在该公式的真值表个真值指派，即在该公式的真值表中有中有2n行。行。为方便构造真值表，为方便构造真值表，特约定如下：特约定如下： 命题变元按字典序排列。命题变元按字典序排列。 对每个指派，以二进制数从小到大或从对每个指派，以二进制数从小到大或从大

20、到小顺序列出。大到小顺序列出。 若公式较复杂，可先列出各子公式的真若公式较复杂，可先列出各子公式的真值值(若有括号，则应从里层向外层展开若有括号，则应从里层向外层展开)，最后列，最后列出所求公式的真值。出所求公式的真值。真值表真值表 真值表真值表: 公式公式A在所有赋值下的取值情况列成的表在所有赋值下的取值情况列成的表 例例 给出公式的真值表给出公式的真值表 A= (qp) qp 的的真值表真值表 p q qp (qp) q (qp) qp 0 00 11 01 1 1011 0001 1111例例 B = ( p q) q 的的真值表真值表 p q p p q ( p q) ( p q) q

21、0 00 11 01 1 1100110100100000实例实例例例 C= (p q) r 的的真值表真值表 p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 111010104. 公式分类公式分类 定义定义1.2.6设设 A 为任意公式，则为任意公式，则 对应每一个指派，公式对应每一个指派，公式 A 均相应确定真均相应确定真值为真，称值为真，称 A 为重言式，或永真式。为重言式，或永真式。 对应每一个指派，公式对应每一个指派，公式 A 均相应确定真均相应确定真值为假，称值为假，称

22、 A 为矛盾式，或永假式。为矛盾式，或永假式。 至少存在一个指派，公式至少存在一个指派，公式 A 相应确定真相应确定真值为真，称值为真，称 A 为可满足式。为可满足式。A为重言式，为重言式，B为矛盾式，为矛盾式，C为可满足式为可满足式 A= (qp) qpB = ( p q) qC= (p q)r 由定义可知，重言式必是可满足式，反之一般由定义可知，重言式必是可满足式，反之一般不真。不真。 重点将研究重言式，它最有用，因为它有以下重点将研究重言式，它最有用，因为它有以下特点：特点： 重言式的否定是矛盾式，矛盾式的否定是重重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。言式，

23、这样只研究其一就可以了。 两重言式的合取式、析取式、条件式和双条两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。可构造出复杂的重言式。 由重言式使用公认的规则可以产生许多有用由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。等价式和蕴涵式。 判定给定公式是否为永真式、永假式或可满足判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。式的问题，称为给定公式的判定问题。 在在Ls中，由于任何一个命题公式的指派数目总中，由于任何一个命题公式的指派数目总是有限的，所以是有限的，所以Ls

24、的判定问题是可解的。其判的判定问题是可解的。其判定方法有真值表法和公式推演法。定方法有真值表法和公式推演法。1.3 等价式与等价演算等价式与等价演算 定义定义1.3.1设设A和和B是两个命题公式，如果是两个命题公式，如果A、B在其任意指派下，其真值都是相同的，则称在其任意指派下，其真值都是相同的，则称A和和B是等值的，或逻辑相等，记作是等值的，或逻辑相等，记作AB，读作，读作A等等值值B，称，称AB为等值为等值/等价式。等价式。 显然，若公式显然，若公式A和和B的真值表是相同的，则的真值表是相同的，则A和和B等值。因此，验证两公式是否等值，只需做出它等值。因此，验证两公式是否等值，只需做出它们

25、的真值表即可。们的真值表即可。真值表法真值表法例例1 判断判断 (p q) 与与 p q 是否等值是否等值解解结论结论: (p q) ( p q) p q p q p q (p q) p q (p q)( p q) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1真值表法真值表法(续续)例例2 判断下述判断下述3个公式之间的等值关系个公式之间的等值关系: p(qr), (pq)r, (p q)r解解 p q r p(qr) (pq)r (p q)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0

26、1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)与与(p q)r等值等值, 但与但与(pq)r不等值不等值在这里，请读者注意在这里，请读者注意和和的区别与联系。的区别与联系。区别：区别：是逻辑联结词，它出现在命题公式是逻辑联结词，它出现在命题公式中；中；不是逻辑联结词，表示两个命题公式的一不是逻辑联结词，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的种关系，不属于这两个公式的任何一个公式中的符号。符号。联系：可用下面定理表明之。联系：可用下面定理表明之。定理定理1.3.1A B当且仅当当且仅当

27、AB是永真式。是永真式。 等值式有下列性质：等值式有下列性质： 自反性，即对任意公式自反性，即对任意公式A，有，有A A。 对称性，即对任意公式对称性，即对任意公式A和和B，若，若A B，则则B A。 传递性，即对任意公式传递性，即对任意公式A、B和和C，若，若A B、B C，则，则A C。2.2.基本等值式基本等值式命题定律命题定律在判定公式间是否等值在判定公式间是否等值/ /等价，有一些简单等价，有一些简单而又经常使用的等值式，称为基本等值式或称命而又经常使用的等值式，称为基本等值式或称命题定律。牢固地记住它并能熟练运用，是学好数题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，

28、同学们应该注意到这一点。理逻辑的关键之一，同学们应该注意到这一点。现将这些命题定律列出如下（见教材现将这些命题定律列出如下（见教材P9P9）：）：(1)(1)双否定：双否定： A AA A。(2)(2)交换律：交换律：A AB BB BA A，A AB BB BA A，A AB BB BA A。 (3) (3) 结合律：结合律：( (A AB B)C CA A(B BC C) )，( (A AB B)C CA A(B BC C) )，( (A AB B) )C CA A( (B BC C) )。 (4) (4) 分配律：分配律：A A(B BC C) )( (A AB B)()(A AC C)

29、 )，A A(B BC C) )( (A AB B)()(A AC C) )。 (5) (5) 德德摩根律：摩根律： ( (A AB B) )A A B B， ( (A AB B) )A A B B。 (6) (6) 等幂律：等幂律：A AA AA A，A AA AA A。(7) (7) 同一律：同一律：A A11A A，A A00A A。(8) (8) 零零 律：律：A A000 0，A A111 1。(9) (9) 吸收律：吸收律：A A(A AB B) )A A，A A(A AB B) )A A。(10)(10)矛盾律：矛盾律：A A A A0 0。( (互补律互补律) )(11)(11

30、)排中律：排中律：A A A A1 1。(12) (12) 蕴涵等值式：蕴涵等值式：A AB BA AB B。（条件式。（条件式转化律）转化律）(13) (13) 假言易位：假言易位：A AB BB B A A。(14) (14) 等价等值式：等价等值式：A AB B( (A AB B)()(B BA A) )( (A AB B)()( A A B B) )， A AB B( (A AB B) )。（双条件式转化律）。（双条件式转化律）(15)(15)等价否定等值式：等价否定等值式： A AB B A AB B(16) (16) 输出律：输出律：( (A AB B)C CA A(B BC C)

31、 )。(17) (17) 归谬论：归谬论：( (A AB B)()(A A B B) )A A。上面这些定律，即是通常所说的布尔代数或上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。值表是不难给出证明的。应用举例应用举例证明两个公式等值证明两个公式等值 例例1 证明证明 p(qr) (p q)r证证 p(qr) p ( q r) （蕴涵等值式）（蕴涵等值式） ( pq) r （结合律）（结合律） (p q) r （德摩根律）（德摩根律） (p q) r （蕴涵等值式）（蕴涵等值式） 说明说明: :也

32、可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍） 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 应用举例应用举例证明两个公式不等值证明两个公式不等值例例2 证明证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假. 方法一方法一 真值表法（自己证）真值表法（自己证） 方法二方法二 观察赋值法观察赋值法. 容易看出容易看出000, 010等使左边的等使左边的成真赋值，使右边的成假赋值成真

33、赋值，使右边的成假赋值. 方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.应用举例应用举例判断公式类型判断公式类型 例例3 3 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1) q(pq) 解解 q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式. 例例3 (续续)(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （

34、蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律） 1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？ 例例3 (续续)(3) (p q) (pq) r) 解解 (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的可这不是矛盾式，也不是重言式，而是非重言式的可满足式满足式. .如如101是它的成真赋值是它的成真赋值, ,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛

35、盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一, ,应尽量使演算短些应尽量使演算短些3.3.代入规则和替换规则代入规则和替换规则 在定义合成公式时，已看到了逻辑联结在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍逻辑联结词外，还要介绍“代入代入”和和“替换替换”，它们也有从已知公式得到新，它们也有从已知公式得到新的公式的作用，因此有人也将它们看成的公式的作用，因此有人也将它们看成运算，这不无道理，而且在

36、今后讨论中，运算，这不无道理，而且在今后讨论中，它的作用也是不容忽视的。它的作用也是不容忽视的。 (1)代入规则代入规则 定理定理1.3.2 在一个永真式在一个永真式A A中，任何一个原子中，任何一个原子命题变元命题变元R出现的每一处，出现的每一处， 用另一个公式代入，用另一个公式代入，所得公式所得公式B仍是永真式。本定理称为代入规则。仍是永真式。本定理称为代入规则。 (2)替换规则替换规则 定理定理1.3.3 设设A1是合式公式是合式公式A的子公式，若的子公式，若A1B1，并且将，并且将A中的中的A1用用B1 替换得到公式替换得到公式B，则则AB。称该定理为替换规则。称该定理为替换规则。 满

37、足定理满足定理1.3.3条件的替换，称为等价替换。条件的替换，称为等价替换。代入和替换有两点区别：代入和替换有两点区别： 代入是对原子命题变元而言的，而替换代入是对原子命题变元而言的，而替换可对命题公式实行。可对命题公式实行。 代入必须是处处代入，替换则可部分替代入必须是处处代入，替换则可部分替换，亦可全部替换。换，亦可全部替换。代入规则与替换规则用处：用于永真式运用代入规则与替换规则用处：用于永真式运用和等值演算和等值演算1.4 对偶式与蕴涵式对偶式与蕴涵式 .对偶式对偶式 在上节介绍的命题定律中，多数是成对出在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶性质现的，这些

38、成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的命题定的反映，即对偶式。利用对偶式的命题定律，可以扩大等价式的个数，也可减少证律，可以扩大等价式的个数，也可减少证明的次数。明的次数。 定义定义1.4.1 在给定的仅使用联结词在给定的仅使用联结词 、和和的命题公式的命题公式A中，若把中，若把和和互换，互换，0和和1互换而得到一个命题公式互换而得到一个命题公式A*，则称，则称A*为为A的对偶式。的对偶式。 显然，显然，A也是也是A*的对偶式。可见的对偶式。可见A与与A*互互为对偶式。为对偶式。 定理定理1.4.1(对偶定理对偶定理) 设设A和和A*互为对偶互为对偶式，式，P1，P2，Pn是

39、出现是出现A和和A* 中的中的原子命题变元，则原子命题变元，则 A(P1，P2，Pn)A*( P1， P2， Pn) A( P1， P2， Pn)A*(P1，P2，Pn) 表明，公式表明，公式A的否定等价于其命题变元的否定等价于其命题变元否定的对偶式；表明，命题变元否定否定的对偶式；表明，命题变元否定的公式等价于对偶式之否定。的公式等价于对偶式之否定。 定理定理1.4.2 设设A和和B为两个命题公式，若为两个命题公式，若AB则则A*B*。 有了等值式、代入规则、替换规则和对有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证偶定理，便可以得到更多的永真式，证明更多的等值式，使化

40、简命题公式更为明更多的等值式，使化简命题公式更为方便。方便。.蕴涵式蕴涵式定义定义1.4.2 设设A和和B是两个命题公式，若是两个命题公式，若AB是永真式，则称是永真式，则称A蕴涵蕴涵B，记作，记作AB，称，称AB为蕴涵式或永真条件式。为蕴涵式或永真条件式。符号符号和和的区别与联系类似于的区别与联系类似于和和的关的关系。区别：系。区别：是逻辑联结词，是公式中的符号；是逻辑联结词，是公式中的符号；而而不是联结词，表示两个公式之间的关系，不不是联结词，表示两个公式之间的关系，不是两公式中符号。联系：是两公式中符号。联系：AB成立，其充要条成立，其充要条件件AB是永真式。是永真式。 蕴涵式有下列性质

41、：蕴涵式有下列性质： 自反性，即对任意公式自反性，即对任意公式A，有，有AA。 传递性，即对任意公式传递性，即对任意公式A、B和和C，若，若AB，BC，则，则AC。 对任意公式对任意公式A、B和和C，若，若AB，AC，则，则A(BC)。 对任意公式对任意公式A、B和和C，若，若AC，BC，则，则ABC。 这些性质的正确性，请读者自己验证。这些性质的正确性，请读者自己验证。 下面给出等价式与蕴涵式之间的关系。下面给出等价式与蕴涵式之间的关系。 定理定理1.4.3 设设A和和B是两命题公式，是两命题公式，AB的充要条件是的充要条件是AB且且BA。 .蕴涵式证明方法蕴涵式证明方法 除真值表外，还有两

42、种方法：除真值表外，还有两种方法： 前件真导后件真方法前件真导后件真方法 设公式的前件为真，若能推导出后件也为真，设公式的前件为真，若能推导出后件也为真，则条件式是永真式，故蕴涵式成立。则条件式是永真式，故蕴涵式成立。 因为欲证因为欲证AB，即证，即证AB是永真式。对于是永真式。对于AB，除在，除在A取真和取真和B取假时，取假时，AB为假外，为假外，余下余下AB皆为真。所以，若皆为真。所以，若AB的前件的前件A为为真，由此可推出真，由此可推出B亦为真，则亦为真，则AB是永真式，是永真式，即即AB。 后件假导前件假方法后件假导前件假方法 设条件式后件为假，若能推导出前件也设条件式后件为假，若能推

43、导出前件也为假，则条件式是永真式，即蕴涵式成为假，则条件式是永真式，即蕴涵式成立。立。 因为若因为若AB的后件的后件B取假，由此可推出取假，由此可推出A取假，即推证了：取假，即推证了： BA。又因。又因ABB A，故，故AB成立。成立。1.5 联结词的扩充与功能完全组联结词的扩充与功能完全组 . 联结词的扩充联结词的扩充 定义定义1.5.1 设设P和和Q是任两个原子命题，是任两个原子命题， PQ，称它为，称它为P和和Q的合取非式复合命题，的合取非式复合命题，读作读作“P合取非合取非Q”。PQ的真值由命题的真值由命题P和和Q的真值确定：当且仅当的真值确定：当且仅当P和和 Q均为均为时，时，PQ为

44、为，否则，否则PQ为为。“合取非合取非”又又常称为常称为“与非与非”。PQ，称它为，称它为P和和Q的析取非式复合命题，的析取非式复合命题，读作读作“P析取非析取非Q”。PQ的真值由的真值由P和和Q的真值的真值确定：当且仅当确定：当且仅当P和和Q均为均为时，时，PQ为为，否，否则则PQ为为。“析取非析取非”又常称为又常称为“或非或非”。*P Q，称它为，称它为P和和Q的条件非式复合命题，的条件非式复合命题，读作读作“P条件非条件非Q”。P Q的真值由的真值由P和和Q的真值的真值确定：当且仅当确定：当且仅当P为为而而Q为为时，时，P Q为为；否则否则P Q为为。 P Q，称它为，称它为P和和Q的双

45、条件非式复合的双条件非式复合命题，读作命题，读作“P双条件非双条件非Q”。P Q的真的真值由值由P和和 Q的真值确定：当且仅当的真值确定：当且仅当P和和Q的真值不同时，的真值不同时，P Q为为，否则，否则P Q为为。“双条件非双条件非”又常称为又常称为“异或异或”，也常用符号也常用符号 表示之。表示之。 上面上面4个联结词构成的复合命题，其真值个联结词构成的复合命题，其真值表如下：表如下：P Q P Q P Q P Q P Q0 00 11 01 11 1 0 01 0 0 11 0 1 10 0 0 0 由表可知，由表可知，P Q(P Q) P Q(P Q) P Q(PQ) P Q(PQ).

46、与非、或非和异或的性质与非、或非和异或的性质与非、或非以及异或在计算机科学中是经常与非、或非以及异或在计算机科学中是经常使用的使用的3个联结词，因此，掌握它们的性质是十个联结词，因此，掌握它们的性质是十分必要的。令分必要的。令P、Q和和R是原子命题变元。是原子命题变元。 与非的性质与非的性质 （交换率，与（交换率，与 、 、 转换转换）(a)PQQP (b) PP P (c) (P Q) (P Q)PQ(d) (PP)(QQ)PQ 或非的性质或非的性质 (a) PQQP (b) PPP (c)(PQ)(PQ)PQ (d) (PP)(QQ)PQ 从上述的性质可知，联结词从上述的性质可知，联结词

47、、 和和 可分可分别用联结词别用联结词 或者或者 取代，读者可以自行取代，读者可以自行验证，验证， 和和 都不满足结合律。都不满足结合律。 异或的性质异或的性质 (a)P QQ P (b) P (Q R)(P Q) R (c) P(Q R)(PQ) (PR) (d) P P0 0，0 PP，1 PP 以上所有性质，用真值表或命题定律都是不以上所有性质，用真值表或命题定律都是不难证明的。难证明的。 至此，已有了至此，已有了9个联结词，是否还需要扩充呢？个联结词，是否还需要扩充呢？事实上，两上命题变无事实上，两上命题变无P和和Q，与，与9个联结词个联结词一共可构成一共可构成 类命题公式，如下表示之

48、：类命题公式，如下表示之：222P Q F T PQ P QP Q P Q P Q P Q0 00 11 01 10000111100110101110010100001111001111000所所 用用的的 联联结结 词词 序序 号号 1 2 3 4 5 678910续 表P Q P Q P Q P Q P Q Q P Q P0 00 11 01 1110100101001011010110100所所 用用的的 联联结结 词词 序序 号号1 11213141516 从列表可知，除命题常元从列表可知，除命题常元F，T及命题变及命题变元本身外，命题联结词一共有元本身外，命题联结词一共有9个就够了

49、。个就够了。为了方便，可规定其优先级，由高到低为了方便，可规定其优先级，由高到低次序为次序为 ， ， ，等。等。 .联结词功能完全组联结词功能完全组 已知有已知有9个联结词就够用了，能不能少呢？个联结词就够用了，能不能少呢？若能少，表明有些联结词的逻辑功能可若能少，表明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如由其他联结词替代。事实上，也确实如此，因为有下列等价式：此，因为有下列等价式： P Q(P Q) P Q(P Q) P Q(PQ) P Q(PQ) 可见，扩充的可见，扩充的4个联结词个联结词 ， ， 和和 能能由原有由原有5个联结词分别替代之。个联结词分别替代之。又由命题定

50、律：又由命题定律：PQ( P Q) ( Q P)PQP QP Q( PQ)P Q( PQ)可知，原有可知，原有5个联结词个联结词 ， ， ，和和又又能由联结词组能由联结词组 ， 或或 ， 取代。那么，究竟取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。这少的几个联结词就能替代所有联结词的功能。这便是所要定义的极小联结词全功能集。便是所要定义的极小联结词全功能集。定义定义1.5.2 称称G为极小联结词全功能集，如为极小联结

51、词全功能集，如果果G满足下列两条件：由满足下列两条件：由G中联结词能表示任中联结词能表示任意命题公式意命题公式全功能集；全功能集；G 中的任一联结词中的任一联结词不能用其余下联结词等价表示。不能用其余下联结词等价表示。可以证明，可以证明， ， ， ， ， ， ， ， 都是联结词功能完全组；而都是联结词功能完全组；而 ， ， ， ， ， ， 都不是极小联结词功能完全都不是极小联结词功能完全组，但为了表示方便，仍经常使用全功能联结词组，但为了表示方便，仍经常使用全功能联结词组组 ， ， 。1.6 公式标准型公式标准型范式范式.简单合取式与简单析取式简单合取式与简单析取式 定义定义1.6.1 在一公

52、式中，仅由命题变元及其在一公式中，仅由命题变元及其否定构成的合取式，否定构成的合取式， 称该公式为简单合取称该公式为简单合取式，其中每个命题变元或其否定，称为合式，其中每个命题变元或其否定，称为合取项。取项。 定义定义1.6.2 在一公式中，仅由命题变元及其在一公式中，仅由命题变元及其否定构成的析取式，否定构成的析取式， 称该公式为简单析取称该公式为简单析取式，其中每个命题变元或其否定，称为析式，其中每个命题变元或其否定，称为析取项。取项。 例如，公式例如，公式P， Q，P Q和和 P Q P等都等都是简单合取式，而是简单合取式，而P，Q和和 P为相应的简为相应的简单合取式的合取项；公式单合取

53、式的合取项；公式P， Q，P Q， P Q P等都是简单析取式，而等都是简单析取式，而P，Q和和 P为相应简单析取式的析取项。为相应简单析取式的析取项。 注意，一个命题变元或其否定既可以是注意，一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如简单合取式，也可是简单析取式，如P， Q等。等。 定理定理1.6.1 简单合取式为永假式的充要条件是：简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。它同时含有某个命题变元及其否定。 定理定理1.6.2 简单析取式为永真式的充要条件是：简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。它同时含有某个命题变元及其否定

54、。 .析取范式与合取范式析取范式与合取范式 定义定义1.6.3 一个命题公式一个命题公式A称为析取范式，称为析取范式，当且仅当当且仅当A可表为简单合取式的析取，即可表为简单合取式的析取，即AAi；其中；其中Ai为简单合取式，为简单合取式，i=1，2，n。 定义定义1.6.4 一个命题公式一个命题公式A称为合取范式，称为合取范式，当且仅当当且仅当A可表为简单析取式的合取，即可表为简单析取式的合取，即AAi；其中；其中Ai为简单析取式，为简单析取式，1in。 定理定理1.6.3 对于任何一命题公式，都存对于任何一命题公式，都存在与其等价的析取范式和合取范式。在与其等价的析取范式和合取范式。 求范式

55、算法：求范式算法： 使用命题定律，消去公使用命题定律，消去公式中除式中除 、 和和 以外公式中出现的所有联以外公式中出现的所有联结词；结词； 使用使用 ( P)P和德和德摩根律，将公式中摩根律，将公式中出现的联结词出现的联结词 都移到命题变元之前；都移到命题变元之前； 利用结合律、分配律等将公式化成析利用结合律、分配律等将公式化成析取范式或合取范式。取范式或合取范式。 .范式的应用范式的应用 利用析取范式和合取范式可对公式进行利用析取范式和合取范式可对公式进行判定。判定。 定理定理1.6.4 公式公式A为永假式的充要条件是为永假式的充要条件是A 的析取范式中每个简单合取式至少包的析取范式中每个

56、简单合取式至少包含一个命题变元及其否定。含一个命题变元及其否定。 定理定理1.6.5 公式公式A为永真式的充要条件是为永真式的充要条件是A 的合取范式中每个简单析取式至少包的合取范式中每个简单析取式至少包含一个命题变元及其否定。含一个命题变元及其否定。 .范式不唯一性范式不唯一性求公式的范式举例求公式的范式举例 例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1) A=(pq)r解解 (pq)r ( pq)r （消去（消去） pqr （结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（

57、由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）求公式的范式举例求公式的范式举例( (续续) )(2) B=(pq)r解解 (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续： (p q) r (p r) (q r) （ 对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成） 1.7 公式的主范式公式的主范式 范式基本解决了

58、公式的判定问题。但由于范式基本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等价带范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中的主析取问题。下面将分别讨论主范式中的主析取范式和主合取范式。范式和主合取范式。 .主析取范式主析取范式 (1) 小项的概念和性质小项的概念和性质 定义定义1.7.1 在含有在含有n个命题变元的简单合个命题变元的简单合取式中，取式中， 若每个命题变元与其否定不同若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现时存在，而二者之一出现一次且仅出现一次，则称该简

59、单合取式为小项，或布一次，则称该简单合取式为小项，或布尔积。尔积。 例如，两个命题变元例如，两个命题变元P和和Q，其构成的小项，其构成的小项有有P Q，PQ， P Q和和 PQ；而三个；而三个命题变元命题变元P、Q和和R，其构成的小项有，其构成的小项有P Q R，P QR，PQ R，PQR， P Q R ， P QR， PQ R， PQR。 可以证明，可以证明，n个命题变元共形成个命题变元共形成2n个小项。个小项。 如果将命题变元按字典序排列，并且把命题变如果将命题变元按字典序排列，并且把命题变元与元与1对应，命题变元的否定与对应，命题变元的否定与0对应，则可对对应，则可对2n个小项依二进制数

60、编码，记为个小项依二进制数编码，记为mi，其下标，其下标i是由二进制数转化的十进制数。用这种编码所是由二进制数转化的十进制数。用这种编码所求得求得2n个小项的真值表，可明显地反映出小项个小项的真值表，可明显地反映出小项的性质。的性质。 表表1.7.1和表和表1.7.2分别给出了分别给出了2个命题变元个命题变元P和和Q、3个命题变元个命题变元P、Q和和R的小项真值表。的小项真值表。 表表 1 .7 .1 两两 个个 命命 题题 变变 元元 的的 小小 项项 真真 值值 表表m( 二二 ) m0 0 m0 1 m1 0 m1 1P Q P Q P Q P Q P Q0 0 1 0 0 00 1 0