1、第1章 命题逻辑离离 散散 数数 学学本章说明本章说明q本章的主要内容本章的主要内容 命题、联结词命题、联结词 命题公式、命题公式的分类命题公式、命题公式的分类 等值演算等值演算 连接词全功能集连接词全功能集 对偶与范式对偶与范式 推理理论推理理论 题例分析题例分析1.1 命题符号化与联结词q数理逻辑研究的数理逻辑研究的中心问题中心问题是是推理推理。q推理的推理的前提前提和和结论结论都是都是表达判断表达判断的的陈述句陈述句。q表达判断的陈述句构成了推理的表达判断的陈述句构成了推理的基本单位基本单位。1.1 命题符号化与联结词q 称能判断真假的陈述句为称能判断真假的陈述句为命题命题（propos
2、ition）。q 作为命题的陈述句所表达得的判断结果称为命题的作为命题的陈述句所表达得的判断结果称为命题的真值真值。q 真值只取两个：真值只取两个：真与假真与假。q 真值为真的命题称为真值为真的命题称为真命题真命题。q 真值为假的命题称为真值为假的命题称为假命题假命题。q感叹句、疑问句、祈使句都不能称为命题。感叹句、疑问句、祈使句都不能称为命题。q判断结果不唯一确定的陈述句不是命题。判断结果不唯一确定的陈述句不是命题。q陈述句中的悖论不是命题陈述句中的悖论不是命题。说说明明(1)(1)2 2是素数。是素数。(2)(2)(3)(3)x x大于大于y y。(4)(4)充分大的偶数等于两个充分大的偶
3、数等于两个素数之和。素数之和。(5)(5)明年明年1010月月1 1日是晴天。日是晴天。(6)(6)(7)(7)请不要吸烟！请不要吸烟！(8)(8)这朵花真美丽啊！这朵花真美丽啊！(9)(9)我正在说假话。我正在说假话。例1.1 判断下列句子是否为命题。(1)(1)是，真命题是，真命题(2)(2)是，真命题是，真命题(3)(3)不是，无确定的真值不是，无确定的真值(4)(4)是，真值客观存在是，真值客观存在(5)(5)是，真值根据具体情况是，真值根据具体情况而定。而定。(6)(6)不是，疑问句不是，疑问句(7)(7)不是，祈使句不是，祈使句(8)(8)不是，感叹句不是，感叹句(9)(9)不是，
4、悖论不是，悖论是无理数5吗？大于2命题可分为命题可分为:原子命题和复合命题原子命题和复合命题q不能被分解成更简单的陈述句，称这不能被分解成更简单的陈述句，称这样的命题为样的命题为简单命题简单命题或或原子命题原子命题。q由简单陈述句通过联结词而成的陈述由简单陈述句通过联结词而成的陈述句，称这样的命题为句，称这样的命题为复合命题复合命题。简单命题和真值的符号化简单命题和真值的符号化q 简单命题简单命题用小写英文字母用小写英文字母p,q,r,pi,qi,ri 表示命题表示命题q 用用“1”表示真，用表示真，用“0”表示假表示假 q 简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以简单命题是真
5、值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为也称简单命题为命题常项命题常项或或命题常元命题常元。q 称真值可以变化的陈述句为称真值可以变化的陈述句为命题变项命题变项或或命题变元命题变元 。也用。也用p,q,rp,q,r,表示命题变项。表示命题变项。q 当当p,q,rp,q,r,表示命题变项时，它们就成了取值表示命题变项时，它们就成了取值0 0或或1 1的变项，因而的变项，因而命题变项已不是命题命题变项已不是命题。q 这样一来，这样一来，p,q,rp,q,r,既可以表示命题常项，也可以表示命题变项既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是
6、变项。在使用中，需要由上下文确定它们表示的是常项还是变项。q：x大于大于y。p：4 4是素数。是素数。P,q成了所表示命题的代表，其中成了所表示命题的代表，其中p的值是的值是0，q为命题变项。为命题变项。例例1.21.2将下面这段陈述中所出现的原子命题符号化，并指出它将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。们的真值，然后再写出这段陈述。是有理数是不对的；是有理数是不对的；2 2是偶素数；是偶素数；2 2或或4 4是素数；如果是素数；如果2 2是素数，则是素数，则3 3也是素数；也是素数；2 2是素数当且仅当是素数当且仅当3 3也是素数。也是素数。2p：是有
7、理数是有理数q：2 2是素数；是素数；r：2 2是偶数是偶数s s：3 3是素数；是素数；t：4 4是素数是素数20111 10非非p；q并且并且(与与)r；q或或t t；如果如果q，则则s；q当且仅当当且仅当s。例例1.21.2的讨论的讨论q半形式化形式半形式化形式q数理逻辑研究方法的主要特征是将论述或推数理逻辑研究方法的主要特征是将论述或推理中的理中的各种要素都符号化各种要素都符号化。即构造各种符号。即构造各种符号语言来代替自然语言语言来代替自然语言。q形式化语言形式化语言：完全由符号所构成的语言。完全由符号所构成的语言。q将联结词（将联结词（connective）符号化，消除其二义）符号
8、化，消除其二义性，对其进行严格定义。性，对其进行严格定义。q 主要的五个联结词：主要的五个联结词：1.1.否定联结词否定联结词2.2.合取联结词合取联结词 3.3.析取联结词析取联结词4.4.蕴涵联结词蕴涵联结词5.5.等价联结词等价联结词联结词联结词定义1.1 否定否定(negation)q设设p为命题，复合命题为命题，复合命题“非非p”(或或“p的否定的否定”)称为称为p的否定式的否定式,记作记作p，符号符号称作称作否定联结词否定联结词，并规定，并规定p为真当且仅当为真当且仅当p为假为假。例如例如：p：哈尔滨哈尔滨是一个大城市是一个大城市。p：哈尔滨是一个不大城市。哈尔滨是一个不大城市。p
9、：哈尔滨不是一个大城市。哈尔滨不是一个大城市。pp1001定义1.2 合取合取(conjunction)q设设p,qp,q为二命题，复合命题为二命题，复合命题“p p并且并且q q”(或或“p p与与q q”)称为称为p p与与q q的的合取式合取式，记作，记作pqpq，称作称作合取联结词合取联结词，并规定，并规定pqpq为真为真当且仅当当且仅当p p与与q q同时为真同时为真。使用合取联结词时要注意的两点：使用合取联结词时要注意的两点：1)1)描述合取式的灵活性与多样性。描述合取式的灵活性与多样性。自然语言中的自然语言中的“既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一面一面一
10、面一面”等联结词都等联结词都可以符号化为可以符号化为。2)2)分清简单命题与复合命题。分清简单命题与复合命题。不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词。pqpq1 11 11 11 10 00 00 01 10 00 000 0例1.3 将下列命题符号化将下列命题符号化(1)(1)吴颖既用功又聪明。吴颖既用功又聪明。(2)(2)吴颖不仅用功而且聪明。吴颖不仅用功而且聪明。(3)(3)吴颖虽然聪明，但不用功。吴颖虽然聪明，但不用功。(4)(4)张辉与王丽都是三好学生。张辉与王丽都是三好学生。(5)(5)张辉与王丽是同学。张辉与王丽是同学。p:p:吴颖用功。吴颖用功。q:q:吴
11、颖聪明。吴颖聪明。r:r:张辉是三好学生。张辉是三好学生。s:s:王丽是三好学生。王丽是三好学生。t:t:张辉与王丽是同学。张辉与王丽是同学。(1)pq(1)pq(2)pq(2)pq(3)qp(3)qp(4)rs(4)rs(5)t(5)t解题要点：解题要点：正确理解命题含义。正确理解命题含义。找出原子命题并符号化。找出原子命题并符号化。选择恰当的联结词。选择恰当的联结词。合取举例合取举例qp：我们去看电影。我们去看电影。q：房间里有十张桌子。房间里有十张桌子。pq：我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。在数理逻辑中，关心的只是复合命题与构成复合在数理逻辑中，关心的
12、只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容辑关系，并不关心各语句的具体内容。说说明明定义1.3 析取析取(disjunction)q设设p p，q q为二命题，复合命题为二命题，复合命题“p p或或q q”称作称作p p与与q q的的析取式析取式，记作，记作p pq q，称作称作析取联结词析取联结词，并，并规定规定p pq q为假当且仅当为假当且仅当p p与与q q同同时为假时为假。自然语言中的自然语言中的“或或”具有二义性，用它联结的命具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应
13、的联题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或结词分别称为相容或和排斥或排斥或(排异或排异或)。析取式析取式pq 表示的是一种相容或表示的是一种相容或说说明明pqpq1 11 11 11 10 01 10 01 11 10 000 0例例1.4 1.4 将下列命题符号化将下列命题符号化 (1)(1)张晓静爱唱歌或爱听音乐。张晓静爱唱歌或爱听音乐。(2)(2)张晓静只能挑选张晓静只能挑选202202或或203203房间。房间。(3)(3)张晓静是江西人或安徽人。张晓静是江西人或安徽人。(1)(1)设设 p p：张晓静爱唱歌，张晓静爱唱歌，q q：张晓静爱听音乐。张晓静爱听音乐。
14、相容或，符号化为相容或，符号化为 p pq q(2)(2)设设t t：张晓静挑选张晓静挑选202202房间，房间，u u：张晓静挑选张晓静挑选203203房间。房间。排斥或，符号化为：排斥或，符号化为：(t tu u)()(t tu u)(3)(3)设设r r：张晓静是江西人，张晓静是江西人，s s：张晓静是安徽人。张晓静是安徽人。排斥或，符号化为：排斥或，符号化为：r rs s。(排斥或排斥或联结的两个命题事实上不可能同时为真联结的两个命题事实上不可能同时为真)或符号化为：或符号化为：(rs)(rsrs)(rs)定义1.4 蕴涵蕴涵(implication)q 设设p p，q q为二命题，复
15、合命题为二命题，复合命题“如果如果p p，则则q q”称作称作p p与与q q的的蕴涵式蕴涵式，记作，记作p pq q，并称并称p p是蕴涵式的是蕴涵式的前件前件，q q为蕴涵式的为蕴涵式的后件后件，称作称作蕴涵联结词蕴涵联结词,并规定并规定p pq q为假当且仅当为假当且仅当p p为真为真q q为假为假。说说明明 pqpq的逻辑关系表示的逻辑关系表示q q是是p p的必要条件。的必要条件。q q是是p p的必要条件有许多不同的叙述方式。的必要条件有许多不同的叙述方式。只要只要p，就就q 因为因为p，所以所以q p仅当仅当q只有只有q才才p除非除非q才才p除非除非q，否则非否则非p 前件前件p
16、和后件和后件q可以没有任何可以没有任何 内在联系。内在联系。pqp q1 11 11 11 10 00 00 01 11 10 001 1例例1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 (1)(1)如果如果3+33+36 6，则雪是白的。，则雪是白的。(2)(2)如果如果3+363+36，则雪是白的。，则雪是白的。(3)(3)如果如果3+33+36 6，则雪不是白的。，则雪不是白的。(4)(4)如果如果3+363+36，则雪不是白的。，则雪不是白的。解：令解：令p p：3+33+36 6，p p的真值为的真值为1 1。q q：雪是白色的，雪是白色的，q q的真
17、值也为的真值也为1 1。(1)pq(2)(2)pq(3)pq(4)(4)pq1101例例1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 以下命题中出现的以下命题中出现的a a是一个给定的正整数：是一个给定的正整数：(5)(5)只要只要a a能被能被4 4整除，则整除，则a a一定能被一定能被2 2整除。整除。(6)(6)a a能被能被4 4整除，仅当整除，仅当a a能被能被2 2整除。整除。(7)(7)除非除非a a能被能被2 2整除，整除，a a才能被才能被4 4整除。整除。(8)(8)除非除非a a能被能被2 2整除，否则整除，否则a a不能被不能被4 4整除
18、。整除。(9)(9)只有只有a a能被能被2 2整除，整除，a a才能被才能被4 4整除。整除。(10)(10)只有只有a a能被能被4 4整除，整除，a a才能被才能被2 2整除。整除。解：解：令令r r：a a能被能被4 4整除整除 s s：a a能被能被2 2整除整除 (5)(5)至至(9)(9)五个命题均叙述的是五个命题均叙述的是a a能被能被2 2整除是整除是a a能被能被4 4整除的必要整除的必要条件条件，因而都符号化为，因而都符号化为r rs s。其真值为其真值为1 1在在(10)(10)中，中，将将a a能被能被4 4整除看成了整除看成了a a能被能被2 2整除的必要条件整除的
19、必要条件，因而，因而应符号化为应符号化为s sr r。a a值不定时，真值未知。值不定时，真值未知。关于蕴含的进一步说明关于蕴含的进一步说明q 作为一种规定，当作为一种规定，当p p为假时，无论为假时，无论q q是真是假，是真是假，p pq q均为真均为真。也就是说，只有。也就是说，只有p p为真为真q q为假这一种情况使得复合命题为假这一种情况使得复合命题p pq q为假。为假。q 例：如果例：如果x5x5，则则x2x2。(1)(1)x=6x=6如果如果6565，则，则6262。(2)(2)x=3x=3 如果如果3535，则，则3232。(3)(3)x=1 x=1 如果如果1515，则，则1
20、212。q 常出现的错误，没有分清充分条件与必要条件。常出现的错误，没有分清充分条件与必要条件。定义1.5 等价等价(two-way-implication)q设设p p，q q为二命题，复合命题为二命题，复合命题“p p当且仅当当且仅当q q”称作称作p p与与q q的的等价式等价式，记作，记作p pq q，称作称作等价联结词等价联结词，并规定，并规定p pq q为真当且仅当为真当且仅当p p与与q q同时为真或同时为假同时为真或同时为假。说说明明q“当且仅当当且仅当”（if and only if）q p pq q的逻辑关系为的逻辑关系为p p与与q q互为充分必要条件。互为充分必要条件。
21、q(pq)(qppq)(qp)与与p pq q的逻辑关系完全一致。的逻辑关系完全一致。pqp q1 11 11 11 10 00 00 01 10 00 001 1例例1.6 1.6 将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值 (1)(1)是无理数当且仅当加拿大位于亚洲。是无理数当且仅当加拿大位于亚洲。(2)(2)2+32+35 5的充要条件是的充要条件是 是无理数。是无理数。(3)(3)若两圆若两圆A A，B B的面积相等，则它们的半径相等；反之亦然。的面积相等，则它们的半径相等；反之亦然。(4)(4)当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快当王
22、小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。(1)(1)设设 p p：是无理数，是无理数，q q：加拿大位于亚洲。加拿大位于亚洲。符号化为符号化为 p p q q，真值为真值为0 0。(2)(2)设设 p p：2+32+35 5，q q：是无理数。是无理数。符号化为符号化为 p p q q，真值为真值为1 1。(3)(3)设设 p p：两圆两圆A A，B B的面积相为的面积相为 p p q q，真值为真值为1 1。(4)(4)设设 p p：王小红心情愉快，王小红心情愉快，q q：王小红唱歌。王小红唱歌。符号化为符号化为 p p q q，真值由具体情况而定。真值由具体情况而定。33
23、关于关于真值（逻辑）真值（逻辑）联结词的说明联结词的说明q 基本基本联结词联结词的真值见下表：的真值见下表：关于关于真值真值联结词的说明联结词的说明q 在命题逻辑中，可用这些联结词将各种各样的复合命题符在命题逻辑中，可用这些联结词将各种各样的复合命题符 号化。基本步骤如下：号化。基本步骤如下：（1 1）分析出各简单命题，将它们符号化）分析出各简单命题，将它们符号化 （2 2）使用合适的联结词，将简单命题逐个联结起来，组）使用合适的联结词，将简单命题逐个联结起来，组 成复合命题的符号化表示。成复合命题的符号化表示。关于联结词的说明关于联结词的说明q 多次使用联结词集中的联结词，可以组成更为复杂的
24、复多次使用联结词集中的联结词，可以组成更为复杂的复合命题。合命题。q 求复杂复合命题的真值时，除依据上表外，还要规定联求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。结词的优先顺序，将括号也算在内。本书规定的联结词优先顺序为：本书规定的联结词优先顺序为：()()，对于同一优先级的联结词，先出现者先运算。，对于同一优先级的联结词，先出现者先运算。例例1.71.7令令 p p：北京比天津人口多。北京比天津人口多。q q：2+22+2 4.4.r r：乌鸦是白色的。乌鸦是白色的。求下列复合命题的真值：求下列复合命题的真值：(1)(1)(pq)(pq)rpq)(pq)r
25、 (2)(qr)(pr)(2)(qr)(pr)(3)(pr)(3)(pr)(prpr)解：解：p p、q q、r r的真值分别为的真值分别为1 1、1 1、0 0 (1)1(1)1(2)1(2)1(3)0(3)0我们关心的是复合命题中命题之间的真值关系，我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。而不关心命题的内容。说说明明1.2 1.2 命题公式及命题公式及分类分类定义定义1.6 1.6 合式公式合式公式(wff)命题公式的严格定义：命题公式的严格定义：(1)(1)单个命题单个命题或命题或命题变项变项p,q,r,pi,qi,ri，0，1是合式公是合式公式。式。(2)(2)若
26、若A A是合式公式，则是合式公式，则(A)A)也是合式公式。也是合式公式。(3)(3)若若A A，B B是合式公式，则是合式公式，则(AB)AB)，(AB)(AB)，(AB)(AB)，(A(AB)B)也是合式公式。也是合式公式。(4)(4)只有有限次地应用只有有限次地应用(1)(1)(3)(3)组成组成的符号串才是合式公的符号串才是合式公式。式。合式公式也称为合式公式也称为命题公式命题公式，简称为，简称为公式公式。将命题变项用联结词和圆括号按一定的逻辑关系联将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为结起来的符号串称为合式公式合式公式或或命题公式命题公式。关于合式公式的说明关
27、于合式公式的说明q 定义定义1.61.6给出的合式公式的定义方式称为给出的合式公式的定义方式称为归纳定义归纳定义或或递归定义递归定义方式。方式。q 定义中引进了定义中引进了A,BA,B等符号，用它们表示任意的合式公式，而不是某个具等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与体的公式，这与p,p,pqpq,(,(pq)rpq)r等具体的公式是有所不同的。等具体的公式是有所不同的。q(A)A)、(AB)(AB)等公式单独出现时，外层括号可以省去，写成等公式单独出现时，外层括号可以省去，写成A A、ABAB等。等。q 公式中不影响运算次序的括号可以省去，公式中不影响运算次序的括号可以
28、省去，如公式如公式(pq)(rpq)(r)可以写成可以写成pqrpqr。q 合式公式的例子：合式公式的例子：(pq)(qpq)(q r)r)(pq)rpq)rp(qrp(qr)q 不是合式公式的例子不是合式公式的例子pqrpqr(p(rqp(rq)定义定义1.7 1.7 公式层次公式层次(1)(1)若公式若公式A A是单个的命题是单个的命题（常项或（常项或变项变项），则称，则称A A为为0 0层合式层合式。(2)(2)称称A A是是n+1(n0)n+1(n0)层公式层公式是指下面情况之一：是指下面情况之一：(a)A(a)ABB，B B是是n n层公式；层公式；(b)A(b)ABCBC，其中其中
29、B,CB,C分别为分别为i i层和层和j j层公式，且层公式，且n=n=max(i,jmax(i,j)；(c)A(c)ABCBC，其中其中B,CB,C的层次及的层次及n n同同(b)b)；(d)A(d)ABCBC，其中其中B,CB,C的层次及的层次及n n同同(b)b)；(e)A(e)AB B C C，其中其中B,CB,C的层次及的层次及n n同同(b)b)。(3)(3)若公式若公式A A的层次为的层次为k k，则称则称A A是是k k层公式层公式。例如：例如：(pq)rpq)r，(pq)(rs(pq)(rs)p)p)分别为分别为3 3层和层和4 4层公式层公式 公式的解释公式的解释q 在命题
30、公式中，由于有命题符号的出现，因而真值是不确定在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之的。当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了。后，公式就成了真值确定的命题了。q(pq)rpq)r 若若p p：2 2是素数，是素数，q q：3 3是偶数，是偶数，r r：是无理数，则是无理数，则p p与与r r被解释被解释成真命题，成真命题，q q被解释成假命题，此时公式被解释成假命题，此时公式(pq)rpq)r被解释成被解释成：若：若2 2是素数或是素数或3 3是偶数，则是偶数，则 是无理数。（真命题）是
31、无理数。（真命题）若若p,qp,q 的解释的解释 不变，不变，r r被解释为：被解释为：是有理数，则是有理数，则(pq)rpq)r被解释成：若被解释成：若2 2是素数或是素数或3 3是偶数，则是偶数，则是有理数。（假命题是有理数。（假命题）q 将命题变项将命题变项p p解释成真命题，相当于指定解释成真命题，相当于指定p p的真值为的真值为1 1，解释，解释成假命题，相当于指定成假命题，相当于指定p p的真值为的真值为0 0。222定义定义1.8 1.8 赋值或解释赋值或解释q设设A A为一命题公式，为一命题公式，p p1 1,p,p2,2,p pn n是出现在公式是出现在公式A A中的全部中的
32、全部命题变项，给命题变项，给p p1 1,p,p2,2,p pn n各指定一个真值，称为对各指定一个真值，称为对A A的的一个一个赋值赋值或或解释解释。若指定的一组值使。若指定的一组值使A A的真值为的真值为1 1，则称，则称这组值为这组值为A A的的成真赋值成真赋值；若使；若使A A的真值为的真值为0 0，则称这组值，则称这组值为为A A的的成假赋值成假赋值。q对含对含n n个命题变项的公式个命题变项的公式A A的赋值情况做如下规定：的赋值情况做如下规定：(1)(1)若若A A中出现的命题符号为中出现的命题符号为p p1 1,p,p2,2,p pn n，给定给定A A的赋值的赋值1,1,2,
33、2,n n 是指是指p p1 11 1，p p2 22 2,，p pn nn n。(2)(2)若若A A中出现的命题符号为中出现的命题符号为p p，q q，r r.,.,给定给定A A的赋值的赋值1,1,2,2,n n是指是指p p1 1，q q2 2,，最后一个字母最后一个字母赋值赋值n n。上述上述i i取值为取值为0 0或或1 1，i i1,2,1,2,n,n。赋值举例赋值举例q 在公式在公式(p p1 1pp2 2pp3 3)(p)(p1 1pp2 2)中，中，000(000(p p1 10 0，p p2 20 0，p p3 30)0)，110(p110(p1 11 1，p p2 21
34、 1，p p3 30)0)都是成真赋值，都是成真赋值，001(001(p p1 10 0，p p2 20 0，p p3 31)1)，011(p011(p1 10 0，p p2 21 1，p p3 31)1)都是成假赋值。都是成假赋值。q 在在(pq)rpq)r中，中，011(011(p p1 10 0，p p2 21 1，p p3 31)1)为成真赋值，为成真赋值，100(100(p p1 11 1，p p2 20 0，p p3 30)0)为成假赋值。为成假赋值。q 重要结论：重要结论：含含n(n1)n(n1)个命题变项的公式共有个命题变项的公式共有2 2n n个不同的赋值。个不同的赋值。定义
35、定义1.9 1.9 真值表真值表q 将命题公式将命题公式A A在所有赋值下取值情况列成表，称作在所有赋值下取值情况列成表，称作A A的的真值真值表表。q 构造真值表的具体步骤如下：构造真值表的具体步骤如下：(1)(1)找出公式中所含的全体命题变项找出公式中所含的全体命题变项p p1 1,p,p2 2,p pn n(若无下角标就若无下角标就按字典顺序排列按字典顺序排列)，列出，列出2 2n n个赋值。本书规定，赋值从个赋值。本书规定，赋值从00000 0开始，然后按二进制加法依次写出各赋值，直到开始，然后按二进制加法依次写出各赋值，直到11111 1为止。为止。(2)(2)按从低到高的顺序写出公
36、式的各个层次。按从低到高的顺序写出公式的各个层次。(3)(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。真值。公式公式A A与与B B具有相同的或不同的真值表，是指真值表的最具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。后一列是否相同，而不考虑构造真值表的中间过程。说说明明例例1.1.7 7 求下列公式的真值表，并求成真赋值和成假赋值。求下列公式的真值表，并求成真赋值和成假赋值。(1)(1)(pq)rpq)r (2)(2)(pppp)(qqqq)(3)(3)(pq)qrpq)qr （1）
37、（2）（3）定义定义1.10 1.10 重言式、永真式、可满足式重言式、永真式、可满足式设设A A为任一命题公式为任一命题公式 (1)(1)若若A A在它的各种赋值下取值均为真在它的各种赋值下取值均为真,则称则称A A是是重言式重言式或或永永真式真式。(2)(2)若若A A在它的各种赋值下取值均为假在它的各种赋值下取值均为假,则称则称A A是是矛盾式矛盾式或或永永假式假式。(3)(3)若若A A不是矛盾式不是矛盾式,则称则称A A是是可满足式（可满足式（satisfactable。定义定义1.101.10的进一步说明的进一步说明q A A是可满足式的等价定义是：是可满足式的等价定义是：A A至
38、少存在一个成真赋值。至少存在一个成真赋值。q 重言式一定是可满足式，但反之不真。因而，若公式重言式一定是可满足式，但反之不真。因而，若公式A A是可是可满足式，且它至少存在一个成假赋值，则称满足式，且它至少存在一个成假赋值，则称A A为非重言式的为非重言式的可满足式。可满足式。q 真值表可用来判断公式的类型真值表可用来判断公式的类型:若真值表最后一列全为若真值表最后一列全为1 1，则公式为重言式。，则公式为重言式。若真值表最后一列全为若真值表最后一列全为0 0，则公式为矛盾式。，则公式为矛盾式。若真值表最后一列中至少有一个若真值表最后一列中至少有一个1 1，则公式为可满足式。，则公式为可满足式
39、。说说明明qn n个命题变项共产生个命题变项共产生2 2n n个不同赋值个不同赋值q含含n n个命题变项的公式的真值表只有个命题变项的公式的真值表只有 种不同情况种不同情况 n22例题例题例题例题1.91.9 下列各公式均含两个命题变项下列各公式均含两个命题变项p p与与q q，它们中它们中哪些具有相同的真值表哪些具有相同的真值表?(1)(1)pqpq(4)(4)(pq)(qppq)(qp)(2)(2)p pq q(5)(5)qpqp(3)(3)(pqpq)例题例题 例例1.101.10 下列公式中下列公式中,哪些具有相同的真值表哪些具有相同的真值表?(1)pq(1)pq(2)(2)qrqr
40、(3)(3)(pq)(pr)ppq)(pr)p)(4)(4)(qr)(ppqr)(pp)本章主本章主要内容要内容q命题与真值（或真假值）。命题与真值（或真假值）。q简单命题与复合命题。简单命题与复合命题。q联结词：联结词：，。q命题公式（简称公式）。命题公式（简称公式）。q命题公式的层次和公式的赋值。命题公式的层次和公式的赋值。q真值表。真值表。q公式的类型：重言式（永真式），矛盾式（永假式）公式的类型：重言式（永真式），矛盾式（永假式），可满足式。，可满足式。本章学习要求本章学习要求q 在在5 5种联结词中，要特别注意蕴涵联结的应用，要弄种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题：
41、清三个问题：pqpq 的逻辑关系的逻辑关系 pqpq 的真值的真值 pqpq 的灵活的叙述方法的灵活的叙述方法q 写真值表要特别仔细认真，否则会出错误。写真值表要特别仔细认真，否则会出错误。q 深刻理解各联结词的逻辑含义。深刻理解各联结词的逻辑含义。q 熟练地将复合命题符号化。熟练地将复合命题符号化。q 会用真值表求公式的成真赋值和成假赋值。会用真值表求公式的成真赋值和成假赋值。本章典型习题本章典型习题q命题符号化命题符号化q求复合命题的真值与命题公式的赋值求复合命题的真值与命题公式的赋值q判断公式的类型判断公式的类型例题：命题符号化例题：命题符号化(1)(1)我和他既是兄弟又是同学我和他既是
42、兄弟又是同学 p p：我和他是兄弟，我和他是兄弟，q q：我和他是同学。我和他是同学。故命题可符号化为：故命题可符号化为：pqpq。(2)(2)张三或李四都可以做这件事。张三或李四都可以做这件事。p p：张三可以做这件事。张三可以做这件事。q q：李四可以做这件事。李四可以做这件事。故命题可符号化为：故命题可符号化为：pqpq。(3)(3)仅当我有时间且天不下雨，我将去镇上。仅当我有时间且天不下雨，我将去镇上。对于对于“仅当仅当”，实质上是，实质上是“当当”的逆命题。的逆命题。“当当A A则则B B”是是ABAB，而而“仅当仅当A A则则B B”是是BABA。p p：我有时间。我有时间。q q
43、：天不下雨。天不下雨。r r：我将去镇上。我将去镇上。故命题可符号化为：故命题可符号化为：r(pqr(pq)。例题：命题符号化例题：命题符号化(4)(4)张刚总是在图书馆看书，除非图书馆不开门或张刚生病。张刚总是在图书馆看书，除非图书馆不开门或张刚生病。对于对于“除非除非”，只要记住，只要记住，“除非除非”是条件。是条件。p p：张刚在图书馆看书，张刚在图书馆看书，q q：图书馆不开门，图书馆不开门，r r：张刚生病。张刚生病。故命题可符号化为：故命题可符号化为：(qr)pqr)p。(5)(5)风雨无阻，我去上学。风雨无阻，我去上学。可理解为可理解为“不管是否刮风、是否下雨，我都去上学不管是否
44、刮风、是否下雨，我都去上学”。p p：天刮风，天刮风，q q：天下雨，天下雨，r r：我去上学。我去上学。故命题可符号化为：故命题可符号化为：(pqr)(pqr)(pqr)(pqrpqr)(pqr)(pqr)(pqr)或或(pqr)(pqr)(pqr)(pqrpqr)(pqr)(pqr)(pqr)理解为理解为“四种情况必居其一四种情况必居其一,而每种情况下我都去上学而每种情况下我都去上学”命题符号化的要点命题符号化的要点q要准确确定原子命题，并将其形式化要准确确定原子命题，并将其形式化。q要选用恰当的联结词，尤其要善于识别自然语言要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略）中的联结词（有时它们被省略）。q否定词的位置要放准确。否定词的位置要放准确。q需要的括号不能省略，而可以省略的括号，在需需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略要提高公式可读性时亦可不省略。q要注意的是要注意的是,语句的形式化未必是唯一的。语句的形式化未必是唯一的。例题：求公式例题：求公式(p(qr)p(qr)的真值表。的真值表。pqr000001010011100101110111qr00010001p(qr)11110001(p(qr)00001110
