离散数学 第1章 命题逻辑.ppt

1、第1章 命题逻辑 1.1 命题及联结词 1.2 命题公式与翻译 1.3 真值表和等价公式 1.4 重言式 1.5 范式 1.6 全功能联结词集 1.7 对偶式与蕴含式 1.8 命题逻辑的推理理论,返回总目录,1.1命题及联结词 1.1.1 命题的基本概念 命题的定义 在数理逻辑中把能判断真假的陈述句称为命题。 命题的表示 一般用小写英文字母或带下标的小写英文字母表示。 Remark： 只有陈述句才有可能成为命题 能判断真假的陈述句 虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。,命题的真值： 一个命题表达的判断结果称为命题的真值。任何命题的真值是惟一的。 真值为“真

2、” True T 1(真) 真命题 真值为“假” False F 0(假) 假命题,【例1.1】判断以下语句是否为命题。若是命题，确定其真值。 上海是个小村庄。 存在外星人。 禁止吸烟！ 北京是中国的首都。 4是素数或6是素数。 今天你吃了吗？ 11+1=100 我正在说谎。 解：命题(F)，命题(待定)，不是命题(祈使句)， 命题(T)，命题(F)，不是命题(疑问句), 命题(由上下文确定), 不是命题(悖论)。,命题常量与命题变元 表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。 如果命题标识符表示一个具体、确定的命题，称为命题常元。 如果命题标识符表示任意一个命题，称为命题

3、变元。 ？命题变元是命题吗？ 不是 命题变元代表任意的命题，其真值是不确定的。因而不是命题。,原子命题与复合命题（将命题完整分类） 原子命题: 如果一个命题不能再分解成更简单的命题 复合命题: 如果一个命题不是原子命题 原子变元： 顾名思义，原子变元表示的是任意一个原子命题。,思考： 原子命题和复合命题之间有什么样的关系呢？ 在自然语言中，可以通过“如果，那么”，“不但，而且”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。,1.1.2 命题联结词 常用的逻辑联结词有五种： 否定、合取、析取、条件和双条件。,1. 否定联结词（否）

4、 设p为命题，则p的否定是一个复合命题. 记作：p， 读作“非p”或“p的否定”。 定义为：若p为T，则p为F；若p为F，则p的真值为T。,【例1.2】否定下列命题。 p：中国的每一个城市都是沿海城市。 p：? 中国的每一个城市都不是沿海城市。 中国的每一个城市不都是沿海城市。,2. 合取联结词 （与） 设p和q均为命题，则p和q的合取是一个复合命题 记作pq，读作“p与q”或“p合取q”。 定义：当且仅当p和q均为T时，pq的才为T。 联结词“” 是二元逻辑运算。,【例1.3】 设 p：2008年在北京举办奥运会。 q：中国是世界四大文明古国之一。 则pq：2008年在北京举办奥运会并且中国

5、是世界四大文明古国之一。 补充说明： 在自然语言中：p和q若没有内在的联系， pq 所表示的命题没有实际意义 在命题逻辑中：只要p和q的真值能确定，则pq 就可以成为一个新命题，不管这新命题在自然语言中是否有意义。,3. 析取联结词（或者） 设p和q均为命题，则p和q的析取是一个复合命题， 记作pq，读作“p或q”或者“p析取q”。 定义为：当且仅当p和q均为F时，pq才为F。 联结词“” 是二元逻辑运算。,“”与汉语中的“或”相似，但又不相同。 【例1.4】下列两个命题中的“或”，哪个是可兼或？哪个是不可兼或？ 在电视上看这场杂技或在剧场里看这场杂技。(不可兼) 灯泡有故障或开关有故障。(可

6、兼, “”是可兼或),4. 条件联结词（如果那么） 设p和q均为命题，其条件命题是个复合命题。 记为：pq。读作“如果p，那么q”或“若p，则q”。 定义为：当且仅当p为T，q为F时，pq才为F。,p称为条件命题pq的前件， q称为条件命题pq的后件。 联结词“”是二元逻辑运算。,【例1.5】 p：小王努力学习。q：小王学习成绩优秀。 pq：如果小王努力学习，那么他的学习成绩就优秀。 联结词“”与汉语中的“如果，那么”或“若，则”相似，但又是不相同的。(区别有2条),5. 双条件联结词(当且仅当) 设p和q均为命题，其复合命题pq称为双条件命题。 读作：“p双条件q”或者“p当且仅当q”。 定

7、义为：当且仅当p和q的真值相同时，pq为T。 联结词“” 是二元逻辑运算。,双条件联结词表示的是一个充分必要关系，可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。,本节学习目标： （1）理解并掌握命题的概念，学会判断一个语句是否为命题并确定其真值。 （2）牢固掌握五类联结词的定义与其真值表。,1.2 命题公式与翻译 把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。 定义1.2.1按下列规则构成的符号串称为命题演算的合式公式。 （基础）单个命题变元和常元是合式公式。 （归纳）如果A是合式公式，那么A是合式公式。 （归纳）如果A和B是合

8、式公式，那么(AB)、 (AB)、(AB)和(AB)是合式公式。 （界限）当且仅当有限次地应用了、所得 到的符号串是合式公式。,命题公式一般的用大写的英文字母A，B，C，表示。,为方便起见，对命题公式约定如下： 最外层括号可以省略。 规定联结词的优先级由高到低依次为 ，。 按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。 ？命题公式是命题吗？ 一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。,用命题公式表示复合命题，常将这个过程称为命题的符号化。（翻译） 命题的符号化可按如下步骤进行： 找出原子命题。 用小写的英文字母或带下标的小写的英文字母表示原子命

9、题。 用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。,从例1.7中可以看出： （1）具有否定意义的命题一定不是原子命题 （2）对于不可兼或的表示，可用 (pq),本小节学习目标： （1）了解命题公式的概念，掌握五类连接词的优先级 （2）掌握如何将一个复合命题符号化？,1.3真值表和等价公式 1.3.1命题公式的真值表 定义1.3.1 设pl，p2，pn是出现在公式A中的全部命题变元，给pl，p2，pn各指定一个真值，称为对公式A的一个赋值或解释。 若赋值使A的真值为T，则称这个赋值为A的成真赋值， 若赋值使A的真值为F，则称这个赋值为A的成假赋值。,定义1.3.2 在命题公

10、式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。 构造真值表的几点注意： 1先找出公式中所含的所有命题变元 2第1行：命题变元；排列：由小到大；字典顺序 3前n列：赋值；排列：从000到111递增,如果公式A有n个命题变元，那么A的真值表应该有多少行？,【例1.8】构造命题公式pq的真值表，并求成真赋值和成假赋值。 解：,【例1.9】构造命题公式(pq)(pq)的真值表，并求成真赋值和成假赋值。 解：,命题公式(pq)(pq)的真值表如表1.7所示。00， 11是成真赋值，01，10是成假赋值。,Remark： 1.如果公式A有n个命题变元，那么A的

11、真值表应该有多少行？ 2.什么叫做两个真值表相等？ 取决于真值表的最后一列是否相同。,1.3.2命题公式的等价 定义1.3.3 设A和B是两个命题公式，对A和B的任一赋值，A和B的真值都相同，则称A和B等价的或逻辑相等的，记为AB 命题公式等价有下面的三条性质： 自反性，AA 对称性，若AB，则BA 传递性，若AB，BC，则AC,所谓两个命题公式等价即为两个公式的真值表相同，所以我们可以用真值表来验证两个命题公式是否等价.,【例1.12】根据等价的定义，用真值表证明 p(qp)p(pq) 证明：构造p(qp)和p(pq)的真值表,证明等价的另外一种方法叫做等价演算法，其基本思想是：先用真值表证

12、明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律。,下面是常用的命题定律。 1.双重否定律 AA 2.交换律 ABBA， ABBA 3.结合律 (AB)CA(BC) (AB)CA(BC) 4.分配律 A(BC)(AB)(AC) A(BC)(AB)(AC),5.德摩根律 (AB)AB (AB)AB 6.幂等律 AAA，AAA 7.吸收律 A(AB)A， A(AB)A 8.零律 A11，A00 9.同一律 A0A， A1A,10.排中律 AA1 11.矛盾律 AA0 12.条件等价式 ABAB 13.双条件等价式AB(AB)(BA) 14.假言易位式 ABBA 15.双条件

13、否定等价式 ABAB,定义1.3.4（子公式） 如果X是合式公式A的一部分且X本身也是合式公式，则称X为公式A的子公式。 例如，Aq(p(pq)，Xpq，则X是A的子公式。 定理1.3.1（等价置换） 设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式记为B，则B与A等价，即AB,返回章目录,本小节学习目标： 1.能够写出任一命题公式的真值表。 2.能熟练地应用命题定律来证明两个命题公式的等价。,1.4重言式 定义1.4.1 设A是任一命题公式。 若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式。 若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式

14、。 若A不是矛盾式，则称命题公式A为可满足的。 Remark： 1.任何重言式都是可满足的。 2.重言式的真值表的最后一列全为1， 矛盾式的真值表的最后一列全为0， 可满足的公式真值表的最后一列至少有一个1。 3.亦可以用等价演算法判断公式的类型。,定理1.4.1 任何两个重言式的合取或析取都是重言式。 任何两个矛盾式的合取或析取都是矛盾式。 定理1.4.2 一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。 一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。 【例1.19】 由排中律知pp为重言式， 以(pq)r)去置换其中的p，得公式(pq)

15、r)(pq)r)，这是重言式。,定理1.4.3 设A、B为两个命题公式，AB当且仅当AB是重言式。 证明： 设AB，下证AB是重言式。 因为AB，所以A，B具有相同的真值，由双条件联结词的定义知AB为真，所以AB为重言式。 设AB为重言式，下证AB 给A，B的任何赋值，因为AB为重言式，故A，B的真值相同，由命题公式等价的定义知AB,1.5范式 1.5.1析取范式与合取范式 定义1.5.1(基本和) 由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。 定义1.5.2(基本积) 由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或

16、其否定是基本积。,定义1.5.3(合取范式) 由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。 定义1.5.4(析取范式) 由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。,任何命题公式都可以化成与其等价的析取范式或合取范式。步骤如下： 消去联结词“”和“” 消去“”(双重否定律) 内移“” (德摩根律) 利用分配律，结合律将公式归约为合取范式和析取范式。,【例1.21】求命题公式(pq)p的合取范式和析取范式。 解：求合取范式 (pq)p (pq)p)(p(pq) (消去) (pq)p)(p(pq) (消去) (pq)p)(p(pq) (内移) (pp)(qp

17、)(ppq) (分配律，合取范式) 1(qp)(1q) (排中律) 1(qp)1 (零律，合取范式) (qp) (同一律，合取范式),求析取范式 (pq)p (pq)p)(pq)p) (消去) (pq)p)(pq)p) (内移) p(pqp) (吸收律，析取范式) p(ppq) (交换律) p(pq) (幂等律，析取范式) 命题公式的公式的合取范式并不唯一, 析取范式也不惟一。,1.5.2主析取范式 定义1.5.5(极小项) 在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。 两个命题变元的极小项有: pq，pq，pq，pq n个

18、命题变元共有几个极小项 ? 2n,极小项有下列的性质： 每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码; (极小项与其成真赋值的对应关系为： 变元对应1，而变元的否定对应0。 ) (2)任意两个不同的极小项的合取为永假式; (3)所有极小项的析取为永真式;,定义1.5.6 (主析取范式) 对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取组成，称该公式为原公式的主析取范式. 任何命题公式都存在着与之等价的主析取范式。可由以下两种方法求得： 等价演算法 真值表法,用等价演算法求主析取范式的步骤如下： 化归

19、为析取范式。 除去析取范式中所有永假的基本积。 在基本积中，将重复出现的合取项和相同变元合并。 在基本积中补入没有出现的命题变元，即添加(pp)，再用分配律展开，最后合并相同的极小项。,用真值表求主析取范式的步骤如下： 构造命题公式的真值表。 找出公式的成真赋值对应的极小项。 这些极小项的析取就是此公式的主析取范式。,【例1.24】用等价演算法和真值表法，求(pq)r的主析取范式。 解：,公式的成真赋值对应 的极小项为： pqr(成真赋值为001) pqr (成真赋值为011) pqr (成真赋值为100) pqr (成真赋值为101) pqr (成真赋值为111) (pq)r 的主析取范式为

20、： (pqr)(pqr)(pqr) (pqr) (pqr) m111m101m100m011m001 m7m5m4m3m1 1，3，4，5，7,Remark: (1)矛盾式无成真赋值，因而主析取范式为0。 (2)重言式无成假赋值，因而主析取范式含2n (n为公式中命题变元的个数)个极小项。,1.5.3主合取范式 定义1.5.7(极大项) 在基本和中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本和叫作布尔析取，也叫大项或极大项。 两个变元p，q构成的极大项为： pq，pq，pq，pq n个变元共有2n个极大项。,极大项有下列三个性质： 每个极大项只有一个成假赋值，极大项

21、不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码; (极大项与成假赋值的对应关系为： 变元对应0，而变元的否定对应1。) 任意两个不同的极大项的析取式为永真式; 全体极大项的合取式为永假式;,定义1.5.8 (主合取范式) 对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。 任何命题公式都存在着与之等价的主合取范式。也可由以下两种方法求得。 等价演算法 (2)真值表法,用等价演算法求主合取范式,步骤如下： 化归为合取范式。 除去所有永真的基本和。 在基本和中合并重复出现的析取项和相同的变元。 在基

22、本和中补入没有出现的命题变元。即增加(pp)，然后，应用分配律展开公式，最后合并相同的极大项。,用真值表求主合取范式的步骤如下： 构造命题公式的真值表。 找出公式的成假赋值对应的极大项。 这些极大项的析取就是此公式的主合取范式。,Remark: (1)矛盾式无成真赋值，因而矛盾式的主合取范式含2n (n为公式中命题变元的个数)个极大项。 (2)重言式无成假赋值，因而主合取范式记为1。,同一公式的主析取范式中m的下标和主合取范式中M的下标是互补的。因此，知道了主析(合)取范式就可以写出主合(析)取范式。,本小节学习目标: 1. 能熟练写出任一命题公式的等价主合取范式和主析取范式.,不可兼析取有下

23、列性质: (1)交换律 (2)结合律,定义1.6.2 (与非) 设p和q是两个命题，复合命题pq称作p和q的与非。 定义为： 当且仅当p和q真值都是真时，pq才为假。 由定义可以看出下式成立： pq(pq),联结词“”还有以下几个性质： pp(pp) p (pq)(pq) (pq) (pq)pq (pp)(qq)(p)(q) (pq)pq,定义1.6.3 (或非) 设p和q是两个命题，复合命题pq称作p和q的或非。 定义为：当且仅当p、q的真值都为假时，pq的真值为真。,由此定义可得： pq(pq),联结词还有下面的几个性质： pp(pp) p (pq)(pq) (pq) (pq) pq (p

24、p)(qq) pq (pq) pq,定义1.6.4 设S是一个联结词集合，如果任何n(n1)个变元组成的公式，都可以由S中的联结词来表示，则称S是全功能联结词集。 ， ，和，,定义1.6.5(最小全功能联结词集) 设S是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集. ，是最小全功能联结词集。,n个命题变元可以构成多少个不等价的命题公式? 上述问题就转化为n个命题变元构成的命题公式有多少个不同的真值表？,返回章目录,1.7对偶式与蕰含式 1.7.1对偶式 定义1.7.1 在仅含联结词，的命题公式A中， 将联结词 ，F，T 分别换成 ，T，F 所得的公式称为公式A的对偶式，记为

25、A*。 设A*是A的对偶式，那么A 是A*的对偶式，(A*)*A。A*和A互为对偶式。,【例1.27】求pq和pq的对偶式。 解： pq(pq) (pq)的对偶式是(pq)pq 故pq的对偶式是pq 对偶式概念可以推广为： 在仅含有联结词，的命题公式中， 将联结词，F，T 分别换成 ，T，F， 就得到了它的对偶式。,定理1.7.1 设A*是A的对偶式，p1，p2，pn是出现在A和A*中的原子变元，则 A(p1，p2，pn)A*(p1，p2，pn) A(p1，p2，pn)A*(p1，p2，pn),【例1.28】设命题公式A(p,q,r)(pq)r，试用此公式验证定理1.7.1的有效性。 证明：

26、验证 A(p,q,r)A*(p, q, r) A(p,q,r)(pq)r A(p,q,r)(pq)r)(pq)r A*(p,q,r)(pq)r A*(p, q, r)( pq)r 所以，A(p,q,r) A*(p,q,r) 验证 A(p,q,r)A*(p,q,r) A(p,q,r)(pq)r (pq)r)A*(p,q,r),定理1.7.2 (对偶原理) 设p1，p2，pn是出现在公式A和B中的所有原子变元，如果AB，则A*B* 证明： 因为 AB 所以A(p1，p2，pn)B(p1，p2，pn)是重言式 A(p1，p2，pn)B(p1，p2，pn)是重言式。 所以 A(p1，p2，pn)B(p

27、1，p2，pn) 由定理1.7.1A*(p1，p2，pn)B*(p1，p2，pn) 即 A*B* 由双条件否定等价式知 A*B*,由对偶定理显然有： 重言式的对偶式是矛盾式， 矛盾式的对偶式是重言式。,1.7.2蕴含式 定义1.7.2 （蕴含式） 设A和B是命题公式，若AB是重言式，则称A蕴含B，记为AB。 证明AB的方法： 对A指定真值T，若由此推出B的真值不为F，而为T，则AB是重言式，即AB。 对B指定真值F，若由此推出A的真值不为T，而为F，则AB是重言式，即AB。,【例1.31】推证p(pq)q 证法1： 假定p(pq)为Tp为T且pq为Tp为F且pq为Tq为T。 所以 p(pq)q

28、 证法2： 假定q为F，则p可以为T或F。 当p为T时，p为F，所以p(pq)为F。 当p为F时，(pq)为F，所以p(pq)为F。 故 p(pq)q,蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。 1.附加律 AAB， BAB 2.化简律 ABA， ABB 3.假言推理 A(AB)B 4.拒取式 B(AB)A 5.析取三段论 A(AB)B， B(AB)A 6.假言三段论 (AB)(BC)(AC) 7.等价三段论 (AB)(BC)(AC) 8.构造性二难 (AC)(AB)(CD)BD (AA)(AB)(AB)B 9.破坏性二难 (BD)(AB)(CD)(AC) 4、5的证明做为练习（作业

29、）,等价式和蕴含式有下面的关系。 定理1.7.3 设A，B为任意两个命题公式，则AB的充分必要条件是AB且BA 证明： 设AB，下证AB且BA 因为AB，所以ABT (AB)(BA)ABT AB与BA都是重言式，故有AB且BA。 设AB且BA，下证AB。 因为AB且BA， 所以AB与BA都是重言式， (AB)(BA)T (AB)(AB)(BA)T 即AB为重言式，故有AB。,定理1.7.4 设A、B、C为合式公式。 AA (即蕴含是自反的) 若AB且A为重言式，则B必为重言式。 若AB且BC，则AC 若AB且AC，则ABC 若AB且CB，则ACB 若AB，C是任意公式，则 ACBC,本小节学习目标： 1、理解对偶式和蕴含式的概念。 2、学会如何判断两个命题公式之间是否有蕴含关系。,1.8命题逻辑的推论理论 定义1.8.1 （前提和有效结论） 设A1，A2，An和C是n+1个命题公式， 若A1A2AnC， 则称C为A1，A2，An 的有效结论， A1，A2，An叫做C的一组前提。 要证明C是一组前提A1，A2，An 的有效结论，只需证明A1A2AnC为重言式。,找出C为假的行，若在每个这样的行中，A1，A2，An的真值至少有一个为假，则A1A2AnC，即C为一组前提A1，A2，An 的有效结论。,【例1.32】分析事实：“如果我有时间，那么我就去上街；如果我上街