离散数学第一章

1、离散数学主讲人：王改霞主讲人：王改霞什么是离散数学？什么是离散数学？离散数学是计算机科学中基础理论的核心离散数学是计算机科学中基础理论的核心课程，充分描述了计算机科学离散性的特点。课程，充分描述了计算机科学离散性的特点。离散数学与计算机科学中的数据结构、操作离散数学与计算机科学中的数据结构、操作系统、编译理论、算法分析、机器定理证明等系统、编译理论、算法分析、机器定理证明等课程联系紧密。课程联系紧密。现代数学可以分为两大类：一类是研究连现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等；另一类就是研续对象的，如分析、方程等；另一类就是研究离散对象的离散数学。究离散对象的离散数学。离散

2、数学是很多高校考研的必考科目。离散数学是很多高校考研的必考科目。教材和主要参考教材和主要参考书书屈婉玲、耿素云、张立昂编著，离散数学，屈婉玲、耿素云、张立昂编著，离散数学，高等教育出版社，高等教育出版社，20052005年年6 6月第月第1 1版。版。王元元，张桂芸编著，离散数学导论，科学王元元，张桂芸编著，离散数学导论，科学出版社，出版社，20022002年年2 2月月左孝凌等编著，离散数学，上海科学技术左孝凌等编著，离散数学，上海科学技术出版社，出版社，19821982年年9 9月月课程内容 数理逻辑数理逻辑 集合论集合论 代数系统代数系统 图论图论 计算机科学中的应用计算机科学中的应用离

3、散数学与离散数学与计计算机的关系算机的关系第二部分第二部分 集合论集合论 集合：一种重要的数据结构集合：一种重要的数据结构 关系：关系数据库的理论基础关系：关系数据库的理论基础 函数：所有计算机语言中不可缺少函数：所有计算机语言中不可缺少 的一部分的一部分第一部分第一部分 数理逻辑数理逻辑 计算机是数理逻辑和电子学相结合计算机是数理逻辑和电子学相结合 的产物的产物第三部分第三部分 代数系统代数系统 计算机编码和纠错码理论计算机编码和纠错码理论 数字逻辑设计基础数字逻辑设计基础 计算机使用的各种运算计算机使用的各种运算第四部分第四部分 图论图论 数据结构、操作系统、编译原理、数据结构、操作系统、

4、编译原理、 计算机网络原理的基础计算机网络原理的基础第五部分第五部分 计算机科学中的应用计算机科学中的应用学学习习要要领领判断（准确）：判断（准确）： 根据概念对事物的属性进行判断根据概念对事物的属性进行判断推理（可靠）：推理（可靠）： 根据多个判断推出一个新的判断根据多个判断推出一个新的判断概念（正确）：概念（正确）： 必须掌握好离散数学中大量的概念必须掌握好离散数学中大量的概念教学要求教学要求 准备作业本：要求作业写清日期并且不抄准备作业本：要求作业写清日期并且不抄 题做解答。题做解答。 课堂上带好练习纸，做好课堂练习。课堂上带好练习纸，做好课堂练习。 做好复习、预习。做好复习、预习。 做

5、好出勤。做好出勤。 课程成绩课程成绩=作业成绩作业成绩+考试成绩考试成绩+出勤成绩出勤成绩第一篇第一篇 数理逻辑数理逻辑 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶

6、红帽子，其中一个人便喊道：“我戴的是黑帽子。” 推论是否正确？ q 数理逻辑是研究推理的数学学科，着重于推理过程以及推理是否正确的研究。它分为辩证逻辑辩证逻辑与形式逻辑形式逻辑两种。q 数理逻辑是用数学方法数学方法研究逻辑学中形式逻辑的一种分支学科。这里的数学方法其主要待点是引进了一套符号体系作为重要的手段，因此数理逻辑又称为符号逻辑符号逻辑。q 本篇包括命题逻辑和谓词逻辑。前提前提结论结论推理（规则）推理（规则）第一章第一章 命题逻辑命题逻辑 1-1 命题及其表示法1-2 联结词1-3 命题公式与翻译1-4 真值表与等价公式1-5 重言式与蕴含式1-6 其他联结词1-7 对偶与范式1-8 命

7、题逻辑推理理论引言引言 推理是数理逻辑的主要研究内容，推理最基本的组成成分是什么呢？ 推理1：若华盛顿是美国的首都，则多伦多是加拿大的首都。华盛顿是美国的首都，所以，多伦多是加拿大的首都。 推理2：如果今天天气晴朗，我就去公园。今天天气晴朗，所以，我就去了公园。构成推理最基本的要素，除联结词外就是陈述句了。命题。1-1 命题及其表示法 命题的概念命题的概念 能够判断真假的陈述句，有确定真值。能够判断真假的陈述句，有确定真值。例：例：1、 1+1=2；2、 明天开会吗？明天开会吗？3、 我正在说谎。我正在说谎。4、我学英语，或者我学日语。、我学英语，或者我学日语。 命题的表示命题的表示 命题通常

8、使用大写字母命题通常使用大写字母a a，b b，z z或带下标的或带下标的大写字母或数字表示，如大写字母或数字表示，如a ai i，1010，r r等，例如等，例如 a a1 1：我是一名大学生。：我是一名大学生。 1010：我是一名大学生。：我是一名大学生。 r r：我是一名大学生。：我是一名大学生。 命题标示符：表示命题的符号；命题标示符：表示命题的符号； 命题常量：表示确定命题的命题标识符；命题常量：表示确定命题的命题标识符； 命题变元：表示任意命题的位置标识符；命题变元：表示任意命题的位置标识符； 原子变元：表示原子命题的命题变元原子变元：表示原子命题的命题变元。例例 1 下述都是命题

9、：(a) 今天下雪； (b) 3+3=6； (c) 2 是偶数而 3 是奇数； (d) 陈涉起义那天, 杭州下雨； (e) 较大的偶数都可表为两个质数之和。 以上命题， (a)的真值取决于今天的天气，(b)和(c)是真， (d)已无法查明它的真值，但它是或真或假的， 将它归属于命题。 (e)目前尚未确定其真假， 但它是有真值的，应归属于命题。 例例 2 下述都不是命题: (a) x+y4。 (c) 真好啊！ (b) x=3。 (d) 你去哪里？ (a)和(b)是陈述句， 但不是命题， 因为它的真值取决于x和y的值。 (c)和(d)都不是陈述句，所以不是命题。 聪明的囚徒 古希腊有个国王，对处死

10、囚徒的方法作了两种规定：一种是砍头，一种是绞刑。并且他自做聪明的做出一种规定：囚徒可以说一句话，并且这句话是马上可以验证其真假。如果囚徒说的是真话，那么处以绞刑，如果囚徒说的是假话，那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。 有一位极其聪明的囚徒，当轮到他来选择处死方法时，他说出一句巧妙的话，结果使这个国王按照哪种方法处死他，都违背自己的决定，只得将他放了。请问：这囚徒说的是句什么话？1-2 联结词 否定联结词否定联结词 合取联结词合取联结词 析取联结词析取联结词 条件联结词条件联结词 双条件联结词双条件联结词1 1、原子命题和复合命题、原子命题和复合命题

11、若一个命题不能分解成更简单的命题若一个命题不能分解成更简单的命题, , 则这个命则这个命题称之为本原命题或原子命题。题称之为本原命题或原子命题。 由简单命题和联结词由简单命题和联结词(和和 、 且且 、 或或 、 如如果果则则 等等) )复合而成的一个陈述句称为复合命题。复合而成的一个陈述句称为复合命题。 例如：例如：p p： 明天下雪明天下雪 q q：明天下雨：明天下雨是两个命题，利用联结词是两个命题，利用联结词“不不”、“并且并且”、 “ “或或”等可分别构成新命题：等可分别构成新命题：“明天不下雪明天不下雪”；“明天下雪并且明天下雨明天下雪并且明天下雨”；“明天下雪或者明天下雨明天下雪或

12、者明天下雨”等。等。 即即 ：“非非p”p”；“p p并且并且q”q”； “p p或或q”q”等。等。 在代数式在代数式x+3 x+3 中，中， x x 、 3 3 叫运算对象，叫运算对象， + +叫运算叫运算符，符，x+3 x+3 表示运算结果。在命题演算中，表示运算结果。在命题演算中， 也用同样术语。也用同样术语。联结词就是命题演算中的运算符，叫联结词就是命题演算中的运算符，叫逻辑运算符逻辑运算符或叫或叫命题联命题联结词结词。常用的命题联结主要有。常用的命题联结主要有 5 5 个。个。 1）. 否定词否定词定义：设定义：设p p为任一命题。复合命题为任一命题。复合命题“非非p”(p”(或或

13、“p p的的否定否定”) )称为称为p p的否定，记作的否定，记作 p p，读作，读作“非非p”p”。为否定联结词。为否定联结词。pp为真当且仅当为真当且仅当p p为假。为假。 由定义可知，由定义可知， p p 的逻辑关系为的逻辑关系为p p不成立，因而不成立，因而p p为真时，为真时， p p 为假，反之当为假，反之当p p为假时，为假时， p p 为真为真。2.2.常用命题联结词常用命题联结词 “ ”代表的运算是一元运算(即只有一个运算对象)，常称为“非”运算，所有可能的运算结果可用下表（真值表）表示。pptfft例: (a) p: 3是偶数。 则p： 3不是偶数。 (b) q: 4 是质

14、数。 则q： 4 不是质数。或 “说4 是质数是不对的”。 (c) r: 我们都是汉族人。 则r: 我们不都是汉族人。 (d) s: 今天下雨并且今天下雪。 则 s:今天不下雨或者今天不下雪。 2). 合取词合取词定义：设p和q是两个命题。复合命题“p并且q”(或“和”)称作p与q的合取式，记作pq ，读作“p且q”， “p与q的合取” 。 为合取联结词。 pq为真当且仅当p和q同时为真。由定义可知， pq的逻辑关系为p与q同时成立，因而只有p与q同时为真， pq才为真，其他情况pq都为假。 代表的运算是二元运算(即有两个运算对象)，常称为“与”运算，所有可能的运算结果的真值表可表示为：p q

15、p qt tt ff tf ftfff 例例1 2是素数和偶数是素数和偶数解：设解：设p：2是素数是素数 q：2是偶数是偶数 则则p q：2是素数和偶数。是素数和偶数。 由于由于p，q的真值均为的真值均为t，所以，所以p q的真值为的真值为t。例例2 如果用如果用p表示表示“李平聪明李平聪明”，q表示表示“李平用李平用功功”。将下列命题符号化。将下列命题符号化:(1)李平既聪明又用功。李平既聪明又用功。(2)李平虽然聪明，但不用功。李平虽然聪明，但不用功。(3)李平不但聪明，而且用功。李平不但聪明，而且用功。(4)李平不是不聪明，而是不用功。李平不是不聪明，而是不用功。p qp qp q (

16、p) q课堂练习：课堂练习： 将下列命题符号化将下列命题符号化:(1) 8能被能被2整除，但不能被整除，但不能被6整除。整除。(2) 5是奇数，是奇数，6是偶数。是偶数。(3) 2与与3的最小公倍数是的最小公倍数是6。(4) 王丽和王鹃是亲姐妹。王丽和王鹃是亲姐妹。总总 结结使用联结词应注意：其一是的灵活性。日常语言中的“既既，又又”、“不但不但，而且，而且”、“虽然虽然，但，但是是”、“一面一面，一面，一面.”.”等等都应符号化为。其二，不要见到“与”或“和”就使用联结词。 3）. 析取词析取词定义：设定义：设p和和q为两命题。复合命题为两命题。复合命题“p或或q”称作称作p与与q的析取式，

17、记作的析取式，记作pq ， , 读做读做“p或者或者q”。 为析取联结词。为析取联结词。 pq为真当且仅当为真当且仅当p和和q中至少中至少一个为真。一个为真。pq的逻辑关系是的逻辑关系是p与与q中至少有一个成立，因而，中至少有一个成立，因而，只有只有p与与q同时为假时，同时为假时， pq 才为假，其他情况才为假，其他情况下，下， pq 均为真。均为真。 “”代表的运算是二元运算，常称为“或”运算，所有可能的运算结果用真值表表示为： p qp qt tt ff tf ftttf 例例 1：今晚我写字或看书 用 p: 今晚我写字, q: 今晚我看书。 则可符号化为： pq 注意注意自然语言中的自然

18、语言中的“或或” 的含义有两种：的含义有两种：一是一是“可兼或可兼或”，另一种是，另一种是“排斥或排斥或”析取式析取式pq表示的是一种可兼或，表示的是一种可兼或，即允许即允许p与与q同时为真。同时为真。这个例子中的这个例子中的“或或”是是“可兼或可兼或”, , 因为它不排除今因为它不排除今晚既看书又写字这种情况。晚既看书又写字这种情况。例例2： “派小王或小李中的一人去开会派小王或小李中的一人去开会” 不能符号化为形式pq ，因为这里的“或”表示的是排斥或。它表示非此即彼，不可兼得。 运算符表示可兼或，排斥或以后用另一符号表达。也可以借助于联结词 、 、共同来表达这种排斥或。 课堂练习：课堂练

19、习： 将下列命题符号化将下列命题符号化:(1) 王东梅学过日语或俄语。王东梅学过日语或俄语。(2) 张小燕生于张小燕生于1977年或年或1978年。年。(3) 小元元只能拿一个苹果或一个梨。小元元只能拿一个苹果或一个梨。4）. 条件条件定义：给定两个命题定义：给定两个命题p和和q，其条件命题是一个复，其条件命题是一个复合命题，记作合命题，记作p q。命题命题pq是假是假, 当且仅当当且仅当p是是真而真而q是假。是假。运算符运算符可能的运算结果可能的运算结果如下表所示。如下表所示。 p qp qt tt ff tf ftftt在使用蕴涵联结词时，除了注意其表示的基本逻在使用蕴涵联结词时，除了注意

20、其表示的基本逻辑关系外，还应注意两点：辑关系外，还应注意两点：在数理逻辑中，在数理逻辑中，“如果如果”与与“那么那么”之之间不需要有因果联系的，只要间不需要有因果联系的，只要p、q能够分别确能够分别确定真值，定真值， p q即成为命题。即成为命题。在在p q中，只要前提为中，只要前提为f时，条件命题的真值时，条件命题的真值都是都是f。例例1：(a) p： 天不下雨。天不下雨。 q： 草木枯黄。草木枯黄。 pq： 如果天不下雨，如果天不下雨， 则草木枯黄则草木枯黄。(b) r： g是正方形。是正方形。 s： g的四边相等。的四边相等。rs： 如果如果g是正方形，则是正方形，则g的四边相等的四边相

21、等。 (c) w： 桔子是紫色的。桔子是紫色的。 v：大地是不平的。：大地是不平的。wv： 如果桔子是紫色的，如果桔子是紫色的， 则大地是不平的则大地是不平的。 例例2：将下列命题符号化，并判断其真值：将下列命题符号化，并判断其真值1）.若若2+24，则太阳从东方升起。，则太阳从东方升起。2）.若若2+24 ，则太阳从东方升起。，则太阳从东方升起。3）.若若2+24 ，则太阳从西方升起。，则太阳从西方升起。4）.若若2+24 ，则太阳从西方升起。，则太阳从西方升起。解解 设设 ：p: 2+24 ，则其真值为，则其真值为t；q:太阳从东方升起，则太阳从东方升起，则其真值为其真值为t；r:太阳从西

22、方升起，则其真值为太阳从西方升起，则其真值为f；则则(1)符号化为符号化为pq，该蕴涵式的真值为，该蕴涵式的真值为t。(2)符号化为符号化为 pq ，该蕴涵式的真值为，该蕴涵式的真值为t。(3)符号化为符号化为pr ，该蕴涵式的真值为，该蕴涵式的真值为f。(4)符号化为符号化为 pr ，该蕴涵式的真值为，该蕴涵式的真值为t。 总总 结结1.1. 蕴含式蕴含式pqpq基本逻辑关系是，基本逻辑关系是，q q是是p p的必要条的必要条件，或件，或p p是是q q的充分条件。的充分条件。有多种等价方式表有多种等价方式表达：达：“只要只要p，就，就q”、 “因为因为p，所以，所以q”、 “p仅当仅当q”

23、、 “只有只有q才才p”、 “除非除非p才才q”等。等。2. 给定命题pq, 我们把qp, p q, q p分别叫做命题pq的逆命逆命题题 、反反命题命题和逆反命题逆反命题. 例例3 将下列命题符号化：将下列命题符号化：(1)只要只要不下雨，我就就骑自行车上班。(2)只有只有不下雨，我才才骑自行车上班。解解 令令p:天下雨；天下雨；q:我骑自行车上班。我骑自行车上班。(1)只要不下雨，我就骑自行车上班：p是的是的充分条件，因而应符号化为充分条件，因而应符号化为 pq。(2)只有不下雨，我才骑自行车上班：p是的是的必要条件，因而应符号化为必要条件，因而应符号化为q p 。课堂练习：课堂练习： 将

24、下列命题符号化（其中命题中出将下列命题符号化（其中命题中出现的现的a是给定的一个正整数）是给定的一个正整数）:(1) 只要只要a能被能被4整除，则整除，则a一定能被一定能被2整除。整除。(2) a能被能被4整除，仅当整除，仅当a能被能被2整除。整除。(3) 除非除非a能被能被2整除，整除，a才能被才能被4整除。整除。 (4) 除非除非a能被能被2整除，否则整除，否则a不能被不能被4整除。整除。 (5)只有只有a能被能被2整除，整除，a才能被才能被4整除。整除。 (6)只有只有a能被能被4整除，整除，a才能被才能被2整除。整除。 5）. 双条件（等值于）双条件（等值于） 定义：如果定义：如果p和

25、和q是命题是命题, 那么那么“p等值于等值于q”也是命题也是命题, 记为记为p q, 称为等值式称为等值式, 读做读做“p等值于等值于q”，p当且当且仅当仅当q。等值式所表达的逻辑关系是与互为充分必要条件充分必要条件。只要p与q的真值同为真或同为假，p q 的真值就为真，否则真值为假。 运算符运算符所有可能的结果如下表所示：所有可能的结果如下表所示：p qp qt tt ff tf ftfff例：例： 将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值:(1) 雪是白色的当且仅当法国的首都是里昂。雪是白色的当且仅当法国的首都是里昂。(2) n是奇数的充分必要条件是是奇数的充分

26、必要条件是n2是奇数。是奇数。(3) 若两圆若两圆o1，o2的面积相等，则它们的半径相的面积相等，则它们的半径相等。反之，若等。反之，若o1，o2的半径相等，则它们的面积相的半径相等，则它们的面积相等。等。 (4) 设角设角1与角与角2是对顶角，则角是对顶角，则角1等于角等于角2。反之，。反之，若角若角1等于角等于角2，则它们是对顶角。，则它们是对顶角。小结 命题的概念和表示； 命题联结词 否定； 合取； 析取； 条件； 双条件；1-3 命题公式与翻译 定义：命题公式的合式公式，规定为：定义：命题公式的合式公式，规定为：（1 1）单个命题变元是）单个命题变元是合式合式公式；公式；（2 2）如果

27、）如果p p是是合式合式公式，则公式，则p p是是合式合式公式；公式；（3 3）如果）如果p p、q q是是合式合式公式，则公式，则p pq q、p pq q、p pq q、p pq q都是都是合式合式公式；公式；（4 4）当且仅当能够有限次的应用）当且仅当能够有限次的应用( (1) 1) 、(2)(2)、( (3)3) 所得到的包括命题变元、联结词和括号的符号串所得到的包括命题变元、联结词和括号的符号串是是合式合式公式。公式。 定义的递归性：定义的递归性： (1)(1)是递归的基础，由是递归的基础，由(1)(1)开始，使用开始，使用(2)(3)(2)(3)规则，可以得到任意的合式公式。规则，

28、可以得到任意的合式公式。 下面的式子是合式公式：下面的式子是合式公式： p pqq， (pq)r)(pq)r) 下面的式子不是合式公式：下面的式子不是合式公式： (p (p v r v r q) q) 约定（约定（1 1）优先次序：）优先次序：，?，v, v, ， 。 （2 2）为方便，最外层括号可以不写。）为方便，最外层括号可以不写。 命题的翻译命题的翻译 可以把自然语言中的有些语句，转变成数理可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项：命题翻译时应注意下列事项： （1 1）确定所给句子是否为命题。）确

29、定所给句子是否为命题。 （2 2）句子中联结词是否为命题联结词。）句子中联结词是否为命题联结词。 （3 3）要正确的选择原子命题和合适的命题联结词。）要正确的选择原子命题和合适的命题联结词。例1.说离散数学无用且枯燥无味是不对的。 p：离散数学是有用的。 q：离散数学是枯燥无味的。 该命题可写成： (pq)例2.如果小张与小王都不去，则小李去。 p：小张去。 q：小王去。 r：小李去。 该命题可写成： (pq)r 如果小张与小王不都去，则小李去。 该命题可写成： (pq)r 也可以写成： (pq)r 所谓命题符号化，就是用命题公式的符号串来所谓命题符号化，就是用命题公式的符号串来表示给定的命题

30、。表示给定的命题。 命题翻译（命题符号化）的方法命题翻译（命题符号化）的方法 1.首先要明确给定命题的含义。首先要明确给定命题的含义。 2.对于复合命题，找联结词，用联结词对于复合命题，找联结词，用联结词 断句，分解出各个原子命题。断句，分解出各个原子命题。 3.设原子命题符号，并用逻辑联结词联设原子命题符号，并用逻辑联结词联 结原子命题符号，构成给定命题的符结原子命题符号，构成给定命题的符 号表达式。号表达式。 例3. 仅当天不下雨且我有时间，才上街。 p：天下雨。q：我有时间。r：我上街。 分析：由于“仅当”是表示“必要条件” 的，既“天不下雨且我有时间”，是“我上街”的必要条件。 该命题

31、可写成： r(pq) 例4.人不犯我，我不犯人；人若犯我，我必犯人。 p：人犯我。q：我犯人。 该命题可写成：(pq)(pq)p是q的必要条件p是q的充分条件p是q的充分且必要条件或写成： pq1-4真值表和等价公式 一个命题公式不是复合命题，所以它没有真值，但是给其中的所有命题变元作指派以后它就有了真值。可以以表的形式反应它的真值情况。 定义：在命题公式中，对于分量指派真值的各种可 能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。例如命题公式：(pq)q 的真值表如下所示：pqppq(pq)qfftffftttttffttttftt 例如命题公式（p?q） ?

32、 p 的真值表如下：pq p?qp（p?q） ? ptttfftffffftftfffftf例如命题公式：（p?q）v （p ? q）真值表如下所示：pqp qp?q p ? q（p?q）v （p ? q）ttfftfttfftffffttffffffttftt 由于对每个命题变元可以有两个真值由于对每个命题变元可以有两个真值(t,f)(t,f)被指派，被指派，所以有所以有n n个命题变元的命题公式个命题变元的命题公式 a(pa(p1 1,p,p2 2,p,pn n) ) 的的真值表有真值表有2 2n n行行。 为为有序地列出有序地列出a(pa(p1 1,p,p2 2,p,pn n) )的真值

33、表，可将的真值表，可将f f看看成成0 0、t t看成看成1 1，按，按二进制数次序列表。二进制数次序列表。 如如a(p,q)a(p,q)的真值表可按照如下次序指派：的真值表可按照如下次序指派： 00(ff)00(ff)，01(ft)01(ft)，10(tf)10(tf)，11(tt)11(tt)。01234567000001010011100101110111fff fft ftf ftt tff tft ttf ttt如如a(p,q,r)的真值表可按照如下次序指派：的真值表可按照如下次序指派：a(p1,p2,pn)的真值表，按照二进制数如下次序指派(0000 0001 00101110 1

34、1110122n -22n -1 构造真值表的方法如下：构造真值表的方法如下：（1）找出公式中的全部命题变元）找出公式中的全部命题变元（2）列出公式中的）列出公式中的2n个解释进行赋值个解释进行赋值（3）根据赋值依次计算各层次的真值并最终）根据赋值依次计算各层次的真值并最终计算出公式的真值。计算出公式的真值。列出p(qr)的真值表的真值表pqrqrp(qr)fffttfftttftfftftttttfftttftttttfffttttt000001010011100101110111等价公式 1、例子 看下面三个公式的真值表 从真值表可以看出，不论对p、q作何指派，都使得pq、pq和qp的真值

35、相同，表明它们之间彼此等价。pqpqpqqpfftttftttttffffttttt2. 定义：a、b是含有命题变元p1,p2, pn的命题公式，如不论对p1, p2 , , pn作任何指派，都使得a和b的真值相同，则称之为a与b等价，记作ab。 显然 pqpqqp3. 重要的等价公式 对合律 p p 幂等律 ppp ppp 结合律 p(qr)(pq)r p(qr)(pq)r 交换律 pqqp pqqp分配律分配律 p(qr)(pq)(pr) p(qr)(pq)(pr) 吸收律吸收律 p(pq)p p(pq)p底底-摩根定律摩根定律 (pq)p q (pq)p q 同一律同一律 pfp ptp

36、 零律零律 ptt pff 互补律互补律 p pt p pf pq pq pq qp pq (pq)(qp)等价置换定理 定义：如果x是合式公式a的一部分，且x本身也是一个合式公式，则称x为公式a的子公式。 定理：设x是合式公式a的子公式，若xy，如果将a中的x用y来置换，所得到公式b与公式a等价，即ab。 例：证明q（pv（pvq） qp。证： 设 a： q（pv（pvq） 由于 pv（p?q） p 故b： qp。 从而 a b。注：可以用真值表证明。例例1 :证明证明p qq pq 证： p qq qp q (qp)(q q) (qp)t qp pq 例例2 2、 用逻辑等价演算法解决下面

37、问题:a，b，c，d 4人做百米竞赛。观众甲、乙、丙预测比赛的名次为：甲：c得第一，b得第二；乙：c得第二，d得第三；丙：a得第二，d得第四。比赛结束后发现甲、乙、丙每人预测的情况都只对了一半，试问实际名次如何(假设无并列者？)1-5 重言式与蕴含式 可见不论p取什么真值pp 的真值总是为真，pp的真值总是为假。故称 pp为重言式(永真式)，称pp为矛盾式(永假式)。pppppftfttf1、例子小结命题公式和符号化；真值表等价公式的定义和证明 真值表 命题定律2 .重言式(矛盾式)定义 a(p1,p2,pn) 是含有命题变元p1,p2, pn的命题公式，如不论对p1, p2 , , pn作任

38、何指派，都使得a(p1,p2, pn) 为真真(假假)，则称之为重言式(矛盾式矛盾式), 也称之为永真式 (永永假式假式)3. 重言式的性质 1).如果a是重言式，则a是矛盾式。 2).如果a，b是重言式，则(ab)、(ab)、(ab)和(ab)也都是重言式。 3).如果a是重言式，则a的置换例式也是重言式。 定理：任何两个重言式的合取或析取，仍然是一定理：任何两个重言式的合取或析取，仍然是一个重言式。个重言式。 定理：一个重言式，对同一分量都用任何合式公定理：一个重言式，对同一分量都用任何合式公式置换，其结果仍然是一重言式。式置换，其结果仍然是一重言式。 设设a、b为两个命题，为两个命题，a

39、b当且仅当当且仅当 ab是重是重言式。言式。4.重言式的证明方法 方法1：列真值表。 方法2：公式的等价变换，化简成“t”。 方法3：用公式的主析取范式。 其中方法3 我们在以后讨论。 定义：如果公式ab是重言式，则称a(永真)蕴涵 b，记作ab。 注意：注意：符号“”不是联结词，它是表示公式间的“永真蕴涵”关系，也可以看成是 “推导”关系。即ab可以理解成由a a可推出可推出b b，即由a为真，可以推出b也为真。给定命题pq, qp： 逆换式（逆命题）逆命题） p q： 反换式（否命题）（否命题） q p： 逆反式（逆否命题）逆否命题） 重言蕴含式可用真值表证明，也可用以下办法证明：(1)

40、假定前件是真,若能推出后件是真,则此蕴含式是 真。(2) 假定后件是假,若能推出前件是假,则此蕴含式是 真。 例：例： 证明证明q(pq) p 方法1: 设q(pq)是真, 则q , pq是真。所以, q是假, p是假。因而p是真。 故q(pq) p 方法2: 设p是假, 则p是真。以下分情况讨论： (i) 若q为真, 则q是假, 所以q(pq)是假。 (ii) 若q是假, 则pq是假, 所以q(pq)是假。故 q(pq) p。 重要的重言蕴涵式(如教材第43页所示) i1. pqp i2. pqq i3. ppq i4. qpq i5. ppq i6. qpq i7. (pq)p i8. (

41、pq)q i9. p,q pq i10. p(pq)q i11. p(pq)q i12. q(pq)p i13. (pq)(qr)pr i14. (pq)(pr)(qr)r i15. ab (ac)(bc) i16. ab (ac)(bc) 蕴含式的性质：蕴含式的性质： 设a、b、c为合式公式，（1 1）若）若a ab b 且且a a是重言式，则是重言式，则b b必为重言式。必为重言式。（2 2）若）若a ab b , , b bc c，则则a ac c。（3 3）若）若a a b b , , a a c c, , 则则a a b bc c。 （4 4）若）若a a b b , , c c b

42、 b, , 则则a a cc b b。 设设p p、q q为任意两个命题公式，为任意两个命题公式， p pq q充分必要条件是充分必要条件是p pq q 且且q qp p。1-6 其他联结词 不可兼析取不可兼析取 条件否定条件否定 与非与非 或非或非 1 不可兼析取联结词不可兼析取联结词 定义：定义： 当且仅当命题当且仅当命题 p 与命题与命题 q 的真值不同时取值为的真值不同时取值为 t，否，否则取值为则取值为 f 的命题称为命题的命题称为命题 p 与与 q 的不可兼析取命题，记作的不可兼析取命题，记作 p q。命题。命题 p q 的真值与命题的真值与命题 p 和命题和命题 q 的真值之间的

43、的真值之间的关系如表所示：关系如表所示：pqp qttftftfttfff定理定理: 设设 p, q, r 是命题公式，如果是命题公式，如果 p q r，则则 p r q，q r p，且，且 p q r 是永假式。是永假式。 证明：由于证明：由于p q r，则，则 p r p p q f q q q r q p q f p p p q r r r f2 条件否定联结词条件否定联结词定义定义: 当且仅当命题当且仅当命题 p 的真值为的真值为 t，命题，命题 q 的真值为的真值为 f 时取时取值为值为 t，否则取值为，否则取值为 f 的命题称为命题的命题称为命题 p 和命题和命题q 的条件的条件否

44、定命题，记为否定命题，记为 p q。命题。命题 p q 的真值与命题的真值与命题 p 和和命题命题 q 的真值之间的关系如表所示：的真值之间的关系如表所示：pqp qttftftftffff c3 与非联结词与非联结词 定义定义: 当且仅当命题当且仅当命题 p 和命题和命题 q 的真值都为的真值都为 t 时取值时取值为为 f，否则取值为，否则取值为 t 的命题称为命题的命题称为命题 p 和命题和命题 q 的与的与非命题，记为非命题，记为 p q。命题。命题 p q 的真值与命题的真值与命题 p 和命和命题题 q 的真值之间的关系如表所示：的真值之间的关系如表所示：pqp qttftftfttf

45、ft设设 p, q 为任意命题公式，则：为任意命题公式，则： p q q p。 p p (pp ) p。 (p q ) (p q ) (p q )pq。 (p p ) (q q ) p q (pq ) p q联结词联结词 服从交换律，但不服从结合律。服从交换律，但不服从结合律。即即 p (q r ) 与与 (p q ) r 不等价。不等价。4 或非联结词或非联结词定义定义: 当且仅当命题当且仅当命题 p 和命题和命题 q 的真值都为的真值都为 f 时取值为时取值为 t，否则取值为否则取值为 f 的命题称为命题的命题称为命题 p 和命题和命题 q 的或非命题，的或非命题，记为记为 p q。命题。

46、命题 p q 的真值与命题的真值与命题 p 和命题和命题 q 的真的真值之间的关系如表所示：值之间的关系如表所示：pqp qttftffftffft设设 p, q 为任意命题公式，则：为任意命题公式，则：p q q p。p p (p p ) p。 (p q ) (p q ) (p q ) p q。(p p ) (q q ) p q (p q ) pq联结词服从交换律，但不服从结合律即联结词服从交换律，但不服从结合律即 p ( q r ) 与与 (p q ) r 不等价。不等价。联结词联结词1 的列表示永假的列表示永假f；联结词联结词2 的列表示命题变元的列表示命题变元p；联结词联结词3 的列表

47、示命题变元的否定：的列表示命题变元的否定：p；联结词联结词4 的列表示永真的列表示永真t；故除了常量故除了常量 t、f 及命题变元自身外，一个一元及命题变元自身外，一个一元联结词就足够了。联结词就足够了。p联结词联结词1联结词联结词2联结词联结词3联结词联结词4tftftfffttp q联联结结词词1联联结结词词2联联结结词词3联联结结词词4联联结结词词5联联结结词词6联联结结词词7联联结结词词8联联结结词词9联联结结词词10联联结结词词11联联结结词词12联联结结词词13联联结结词词14联联结结词词15联联结结词词16t ttfttfftftftftftft ftftfftfttfftftt

48、ff ttffttffttftfftftf ftfffttttfttftftf联结词联结词1、联结词、联结词2的列分别表示永真的列分别表示永真t及永假及永假f；联结词联结词3、联结词、联结词4的列分别表示命题变元的列分别表示命题变元p, q；联结词联结词5、联结词、联结词6的列分别表示命题变元的列分别表示命题变元p, q的否定：的否定：p, q；联结词联结词7的列表示合取命题：的列表示合取命题：pq；联结词联结词9的列表示析取命题：的列表示析取命题：pq；联结词联结词11、15的列表示条件命题：的列表示条件命题：p q, q p；联结词联结词13的列表示双条件命题：的列表示双条件命题：p q；

49、联结词联结词8、联结词、联结词10、联结词、联结词12、联结词、联结词14、联结词、联结词16是是我们补充的其他联结词。我们补充的其他联结词。5 联结词之间的关系联结词之间的关系到此为止，我们已讨论了到此为止，我们已讨论了 9 个联结词个联结词 , , , , , , , , 。这些联结词之间具有如下一些性质：这些联结词之间具有如下一些性质： 所有一元、二元联结词均可用所有一元、二元联结词均可用 与与 来表达。来表达。 所有一元、二元联结词均可用所有一元、二元联结词均可用 与与 来表达。来表达。 所有一元、二元联结词均可用所有一元、二元联结词均可用 与与 来表达。来表达。定义定义: 设设 s

50、是一个联结词集合，若是一个联结词集合，若: (1) 任一公式都有一个仅用任一公式都有一个仅用 s 中联结词表达的等价公式，则称中联结词表达的等价公式，则称 s 是完备的；是完备的； (2) 从从 s 中去掉任一个联结词后得到联结词集合中去掉任一个联结词后得到联结词集合 s ，若至少存，若至少存在一个公式在一个公式 b，不存在仅用，不存在仅用 s 中联结词表达且与中联结词表达且与 b 等价的等价的公式，则称公式，则称 s 是最小完备联结词集。是最小完备联结词集。定理定理: , 、, 和和 , 都是最小完备联结词集。都是最小完备联结词集。 下面仅证下面仅证 , 是最小完备联结词集。是最小完备联结词

51、集。证明：首先，任意公式都存在仅包含联结词与证明：首先，任意公式都存在仅包含联结词与的等价公式。的等价公式。 再者，若从联结词集再者，若从联结词集 , 中去掉联结词得联结词集中去掉联结词得联结词集。显然，公式。显然，公式 p 不存在仅用联结词不存在仅用联结词 表达的等价公表达的等价公式。可知式。可知 , 是最小完备联结词集。是最小完备联结词集。 定理定理1.19 和和 均是最小完备联结词集。均是最小完备联结词集。证明：根据定理证明：根据定理1.18和下面的等价关系：和下面的等价关系： p p p, p q (p p ) (q q ), p p p, p q (p p ) (q q ) 很容易证

52、明此定理。很容易证明此定理。 1-7 对偶与范式对偶式对偶式 定义：在给定的命题中，将联结词定义：在给定的命题中，将联结词v换成换成?，将，将?换成换成v，如果有特殊变元，如果有特殊变元f和和t也也相互交换，所得公式相互交换，所得公式a*称为称为a的对偶式。的对偶式。 练习：写出下列表达式的对偶式（1）（pvq）?r （2）（p ? q）v （）（）?（ （? ） 定理定理 1 设a和a*是对偶式。p 1, p2, pn是出现于a和a *中的所有命题变元，于是a(p1, p2, , pn) a *(p1, p2, , pn)a(p，q，r) pqra(p，q，r) (pqr) (p) (qr)

53、 (p)(q r)a*(p, q, r) p(qr)a*(p, q, r) (p)(q r) 所以, a(p, q, r) a *(p, q, r) 定理 2 若ab, 且a、b为命题变元p1, p2,., pn及联结词、 、构成的公式, 则a* b*。此定理常称为对偶原理。证明：证明： ab意味着 a(p1, p2, , pn) b(p1, p2, , pn) 永真 所以 a(p1, p2, , pn) b( p1, p2, , pn)永真 由定理1 得 a*(p1, p2, , pn) b* (p1, p2, , pn)永真 以pi代pi, 1in, 得 a*(p1, p2, , pn)

54、b*(p1, p2, , pn) 永真 所以, a* b*。证毕。 定理 3 如果ab，且a、b为命题变元p1, p2, , pn及联结词、 构成的公式, 则b*a*。 证明：证明： a b意味着 a(p1, p2 , ,pn)b(p1, p2, . , pn)永真。 则，b(p1, p2, , pn) a (p1, p2, , pn)永真。 由定理由定理 1 得得b*(p1, p2 , , pn)a*(p1, p2 , , pn) 永真。因为上式是永真式, 可以使用代入规则, pi代pi, 1in, 得b* a*。 证毕。 范式就是命题公式形式的规范形式。这里约定在范式中范式就是命题公式形式

55、的规范形式。这里约定在范式中 只含有联结词只含有联结词 、和和。简单合取式简单合取式：用：用“”联结命题变元或变元的否定构成的式联结命题变元或变元的否定构成的式子。子。 如如 p 、 p 、p q、p q r简单简单析取式析取式：用：用“” 联结命题变元或变元的否定构成的式联结命题变元或变元的否定构成的式子。子。 如如 p 、 p 、p q、p q r注注: ppp ppp p是合是合(析析)取式取式.范式析取范式：析取范式： 公式公式a如果写成如下形式：如果写成如下形式： a1a2.an (n1) 其中每个其中每个ai (i=1,2,n)是简单合取式，称之为是简单合取式，称之为a的的析取范式

56、析取范式。 合取范式：合取范式： 公式公式a如果写成如下形式：如果写成如下形式： a1a2.an (n1) 其中每个其中每个ai (i=1,2,n)是简单析取式，称之为是简单析取式，称之为a的的合取范式合取范式。 例如，例如，pq 的的析取范式与合取范式：析取范式与合取范式： pq (pq)( p q)-析取范式析取范式 pq ( pq)(p q)-合取范式合取范式析取范式与合取范式的写法析取范式与合取范式的写法 先用相应的公式去掉先用相应的公式去掉和和。（如果有）。（如果有） 公式公式e16 pq pq 公式公式e21 pq (pq)( p q) 公式公式e20 pq (pq)(qp) 再用

57、再用e16 pq ( pq)(p q) 用公式的否定公式或摩根定律将用公式的否定公式或摩根定律将 后移到命题后移到命题变元之前。变元之前。 a(p1,p2,pn)a*( p1, p2, pn) 底底-摩根定律摩根定律 (pq) p q (pq)p q 用分配律、幂等律等公式进行整理，使之成用分配律、幂等律等公式进行整理，使之成为所要求的形式。为所要求的形式。求公式的范式举例求公式的范式举例 例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1) a=(pq)r解解 (pq)r ( pq)r （消去（消去） pqr （结合律）（结合律）这既是这既是a的析取范式（由的析取范式（由

58、3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是a的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）求公式的范式举例求公式的范式举例( (续续) )(2) b=(pq)r解解 (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续： (p q) r (p r) (q r) （ 对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合

59、取范式（由两个简单析取式构成） 主析取范式与主主析取范式与主合取范式合取范式 一个公式的一个公式的析取范式与合取范式的形析取范式与合取范式的形式是不唯一的。下面定义形式唯一的式是不唯一的。下面定义形式唯一的主析主析取范式与主取范式与主合取范式。合取范式。主析取范式主析取范式 1. 小项小项 定义：在一个有定义：在一个有n个命题变元的简单合取式中，个命题变元的简单合取式中，每个变元必出现且仅出现一次，则称这个简单合每个变元必出现且仅出现一次，则称这个简单合取式是个取式是个小项小项。 例如，有两个变元的小项：例如，有两个变元的小项： pq、p q、 pq、 p q m3m2m1m0pqpqp q

60、pq p qffffftftfftftfftfftttfffa). 有有n个变元，则有个变元，则有2n个小项；个小项；b). 每一组指派有且只有一个小项为每一组指派有且只有一个小项为t； 分别记作分别记作m0,m1,m2,m2n-1 。 上例中：上例中： m0 p q m1 pq m2p q m3pq c).任意两个不同小项的合取式永假；任意两个不同小项的合取式永假； d).全体小项的析取式永为真。全体小项的析取式永为真。小项的性质：小项的性质：主析取范式定义 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称为原式的主析取范式。形式：形式：a1a2.an, , 每个