1、离散数学主讲人：王改霞主讲人：王改霞1/169什么是离散数学？什么是离散数学？离散数学是计算机科学中基础理论关键课离散数学是计算机科学中基础理论关键课程，充分描述了计算机科学离散性特点。程，充分描述了计算机科学离散性特点。离散数学与计算机科学中数据结构、操作系统、离散数学与计算机科学中数据结构、操作系统、编译理论、算法分析、机器定理证实等课程联编译理论、算法分析、机器定理证实等课程联络紧密。络紧密。当代数学能够分为两大类：一类是研究连当代数学能够分为两大类：一类是研究连续对象，如分析、方程等；另一类就是研究续对象，如分析、方程等；另一类就是研究离散对象离散数学。离散对象离散数学。离散数学是很多
2、高校考研必考科目。离散数学是很多高校考研必考科目。2/169教材和主要参考教材和主要参考书屈婉玲、耿素云、张立昂编著，离散数学，屈婉玲、耿素云、张立昂编著，离散数学，高等教育出版社，年高等教育出版社，年6 6月第月第1 1版。版。王元元，张桂芸编著，离散数学导论，科学出王元元，张桂芸编著，离散数学导论，科学出版社，版社，2 2月月左孝凌等编著，离散数学，上海科学技术左孝凌等编著，离散数学，上海科学技术出版社，出版社，19821982年年9 9月月3/169课程内容数理逻辑数理逻辑集合论集合论代数系统代数系统图论图论计算机科学中应用计算机科学中应用4/169离散数学与离散数学与计算机关系算机关系
3、第二部分第二部分 集合论集合论 集合：一个主要数据结构集合：一个主要数据结构 关系：关系数据库理论基础关系：关系数据库理论基础 函数：全部计算机语言中不可缺乏函数：全部计算机语言中不可缺乏 一部分一部分第一部分第一部分 数理逻辑数理逻辑 计算机是数理逻辑和电子学相结合计算机是数理逻辑和电子学相结合 产物产物5/169第三部分第三部分 代数系统代数系统 计算机编码和纠错码理论计算机编码和纠错码理论 数字逻辑设计基础数字逻辑设计基础 计算机使用各种运算计算机使用各种运算第四部分第四部分 图论图论 数据结构、操作系统、编译原理、数据结构、操作系统、编译原理、计算机网络原理基础计算机网络原理基础第五部
4、分第五部分 计算机科学中应用计算机科学中应用6/169学学习要要领判断（准确）：判断（准确）：依据概念对事物属性进行判断依据概念对事物属性进行判断推理（可靠）：推理（可靠）：依据多个判断推出一个新判断依据多个判断推出一个新判断概念（正确）：概念（正确）：必须掌握好离散数学中大量概念必须掌握好离散数学中大量概念7/169教学要求教学要求准备作业本：要求作业写清日期而且不抄准备作业本：要求作业写清日期而且不抄 题做解答。题做解答。课堂上带好练习纸，做好课堂练习。课堂上带好练习纸，做好课堂练习。做好复习、预习。做好复习、预习。做好出勤。做好出勤。课程成绩课程成绩=作业成绩作业成绩+考试成绩考试成绩+
5、出勤成绩出勤成绩8/169第一篇第一篇 数理逻辑数理逻辑 一个土耳其商人想找一个十分聪明助手帮助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色，三顶是黑色，现在，我把灯关掉，而且把帽子摆位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴帽子是什么颜色。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴是一顶红帽子，其中一个人便喊道：“我戴是黑帽子。”推论是否正确？9/169q 数理逻辑是
6、研究推理数学学科，着重于推理过程以及推理是否正确研究。它分为辩证逻辑辩证逻辑与形形式逻辑式逻辑两种。q 数理逻辑是用数学方法数学方法研究逻辑学中形式逻辑一个分支学科。这里数学方法其主要待点是引进了一套符号体系作为主要伎俩，所以数理逻辑又称为符号逻辑符号逻辑。q 本篇包含命题逻辑和谓词逻辑。10/169前提前提结论结论推理（规则）推理（规则）11/169第一章第一章 命题逻辑命题逻辑 1-1 命题及其表示法1-2 联结词1-3 命题公式与翻译1-4 真值表与等价公式1-5 重言式与蕴含式1-6 其它联结词1-7 对偶与范式1-8 命题逻辑推理理论12/169引言引言 推理是数理逻辑主要研究内容，
7、推理最基本组成成份是什么呢？推理1：若华盛顿是美国首都，则多伦多是加拿大首都。华盛顿是美国首都，所以，多伦多是加拿大首都。推理2：假如今天天气晴朗，我就去公园。今天天气晴朗，所以，我就去了公园。组成推理最基本要素，除联结词外就是陈说句了。命题。13/1691-1 命题及其表示法命题概念命题概念 能够判断真假陈说句，有确定真值。能够判断真假陈说句，有确定真值。例：例：1、1+1=2；2、明天开会吗？明天开会吗？3、我正在说谎。我正在说谎。4、我学英语，或者我学日语。、我学英语，或者我学日语。14/169命题表示命题表示 命命题题通通常常使使用用大大写写字字母母A A，B B，Z Z或或带带下下标
8、标大大写字母或数字表示，如写字母或数字表示，如A Ai i，1010，R R等，比如等，比如 A A1 1：我是一名大学生。：我是一名大学生。10 10：我是一名大学生。：我是一名大学生。R R：我是一名大学生。：我是一名大学生。15/169命题标示符：表示命题符号；命题标示符：表示命题符号；命题常量：表示确定命题命题标识符；命题常量：表示确定命题命题标识符；命题变元：表示任意命题位置标识符；命题变元：表示任意命题位置标识符；原子变元：表示原子命题命题变元原子变元：表示原子命题命题变元。16/169例例 1 下述都是命题：(a)今天下雪；(b)3+3=6；(c)2 是偶数而 3 是奇数；(d)
9、陈涉起义那天,杭州下雨；(e)较大偶数都可表为两个质数之和。以上命题，(a)真值取决于今天天气，(b)和(c)是真，(d)已无法查明它真值，但它是或真或假，将它归属于命题。(e)当前还未确定其真假，但它是有真值，应归属于命题。17/169例例 2 下述都不是命题:(a)x+y4。(c)真好啊！(b)x=3。(d)你去哪里？(a)和(b)是陈说句，但不是命题，因为它真值取决于x和y值。(c)和(d)都不是陈说句，所以不是命题。18/169聪明囚徒 古希腊有个国王，对处死囚徒方法作了两种要求：一个是砍头，一个是绞刑。而且他自做聪明做出一个要求：囚徒能够说一句话，而且这句话是马上能够验证其真假。假如
10、囚徒说是真话，那么处以绞刑，假如囚徒说是假话，那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。有一位极其聪明囚徒，当轮到他来选择处死方法时，他说出一句巧妙话，结果使这个国王按照哪种方法处死他，都违反自己决定，只好将他放了。请问：这囚徒说是句什么话？19/1691-2 联结词否定联结词否定联结词 合取联结词合取联结词析取联结词析取联结词条件联结词条件联结词双条件联结词双条件联结词20/1691 1、原子命题和复合命题、原子命题和复合命题 若若一一个个命命题题不不能能分分解解成成更更简简单单命命题题,则则这这个个命命题题称之为本原命题或原子命题。称之为本原命题或原子命
11、题。由由简简单单命命题题和和联联结结词词(和和、且且、或或、假假如如则则 等等)复合而成一个陈说句称为复合命题。复合而成一个陈说句称为复合命题。21/169比如：比如：P P：明天下雪明天下雪 Q Q：明天下雨：明天下雨是是两两个个命命题题，利利用用联联结结词词“不不”、“而而且且”、“或或”等可分别组成新命题：等可分别组成新命题：“明天不下雪明天不下雪”；“明天下雪而且明天下雨明天下雪而且明天下雨”；“明天下雪或者明天下雨明天下雪或者明天下雨”等。等。22/169即即 ：“非非P”P”；“P“P而且而且Q”Q”；“P“P或或Q”Q”等。等。在在代代数数式式x+3 x+3 中中，x x、3 3
12、 叫叫运运算算对对象象，+叫叫运运算算符符，x+3 x+3 表表示示运运算算结结果果。在在命命题题演演算算中中，也也用用一一样样术术语语。联联结结词词就就是是命命题题演演算算中中运运算算符符，叫叫逻逻辑辑运运算算符符或或叫叫命命题题联联结结词词。惯用命题联结主要有。惯用命题联结主要有 5 5 个。个。23/1691）.否定词否定词 定义：设定义：设P P为任一命题。复合命题为任一命题。复合命题“非非P”(P”(或或“P“P否否定定”)”)称为称为P P否定，记作否定，记作 P P，读作，读作“非非P”P”。为否为否定联结词。定联结词。PP为真当且仅当为真当且仅当P P为假。为假。由定义可知，由
13、定义可知，P P 逻辑关系为逻辑关系为P P不成立，因而不成立，因而P P为为真时，真时，P P 为假，反之当为假，反之当P P为假时，为假时，P P 为真为真。2.2.惯用命题联结词惯用命题联结词24/169“”代表运算是一元运算(即只有一个运算对象)，常称为“非”运算，全部可能运算结果可用下表（真值表）表示。PPTFFT25/169例:(a)P:3是偶数。则 P：3不是偶数。(b)Q:4 是质数。则 Q：4 不是质数。或“说4 是质数是不正确”。(c)R:我们都是汉族人。则 R:我们不都是汉族人。(d)S:今天下雨而且今天下雪。则 S:今天不下雨或者今天不下雪。26/1692).合取词合取
14、词定义：设P和Q是两个命题。复合命题“P而且Q”(或“和”)称作P与Q合取式，记作PQ，读作“P且Q”，“P与Q合取”。为合取联结词。PQ为真当且仅当P和Q同时为真。由定义可知，PQ逻辑关系为P与Q同时成立，因而只有P与Q同时为真，PQ才为真，其它情况PQ都为假。27/169 代表运算是二元运算(即有两个运算对象)，常称为“与”运算，全部可能运算结果真值表可表示为：P QP QT TT FF TF FTFFF28/169 例例1 2是素数和偶数是素数和偶数解：设解：设P：2是素数是素数 Q：2是偶数是偶数 则则P Q：2是素数和偶数。是素数和偶数。因为因为p，q真值均为真值均为T，所以，所以p
15、 q真值为真值为T。29/169例例2 假如用假如用p表示表示“李平聪明李平聪明”，q表示表示“李平用李平用功功”。将以下命题符号化。将以下命题符号化:(1)李平既聪明又用功。李平既聪明又用功。(2)李平即使聪明，但不用功。李平即使聪明，但不用功。(3)李平不但聪明，而且用功。李平不但聪明，而且用功。(4)李平不是不聪明，而是不用功。李平不是不聪明，而是不用功。p qp qp q (p)q30/169课堂练习：课堂练习：将以下命题符号化将以下命题符号化:(1)8能被能被2整除，但不能被整除，但不能被6整除。整除。(2)5是奇数，是奇数，6是偶数。是偶数。(3)2与与3最小公倍数是最小公倍数是6
16、。(4)王丽和王鹃是亲姐妹。王丽和王鹃是亲姐妹。31/169总总 结结使用联结词应注意：其一是灵活性。日常语言中“既既，又，又”、“不但不但，而且，而且”、“即使即使，不过，不过”、“一面一面，一面，一面.”.”等等都应符号化为。其二，不要见到“与”或“和”就使用联结词。32/169 3）.析取词析取词定义：设定义：设P和和Q为两命题。复合命题为两命题。复合命题“P或或Q”称作称作P与与Q析取式，记作析取式，记作PQ，,读做读做“P或者或者Q”。为析取联结词。为析取联结词。PQ为真当且仅当为真当且仅当P和和Q中最少一中最少一个为真。个为真。PQ逻逻辑辑关关系系是是P与与Q中中最最少少有有一一个
17、个成成立立，因因而而，只只有有P与与Q同同时时为为假假时时，PQ 才才为为假假，其其它它情情况况下，下，PQ 均为真。均为真。33/169 “”代表运算是二元运算，常称为“或”运算，全部可能运算结果用真值表表示为：P QP QT TT FF TF FTTTF34/169 例例 1：今晚我写字或看书 用 P:今晚我写字,Q:今晚我看书。则可符号化为：PQ 注意注意自然语言中自然语言中“或或”含义有两种：含义有两种：一是一是“可兼或可兼或”，另一个是，另一个是“排斥或排斥或”析取式析取式PQ表示是一个可兼或，表示是一个可兼或，即允许即允许P与与Q同时为真。同时为真。这个例子中这个例子中“或或”是是
18、“可兼或可兼或”,”,因为它不排除今晚因为它不排除今晚既看书又写字这种情况。既看书又写字这种情况。35/169例例2：“派小王或小李中一人去开会派小王或小李中一人去开会”不能符号化为形式PQ，因为这里“或”表示是排斥或。它表示非此即彼，不可兼得。运算符表示可兼或，排斥或以后用另一符号表示。也能够借助于联结词 、共同来表示这种排斥或。36/169课堂练习：课堂练习：将以下命题符号化将以下命题符号化:(1)王东梅学过日语或俄语。王东梅学过日语或俄语。(2)张小燕生于张小燕生于1977年或年或1978年。年。(3)小元元只能拿一个苹果或一个梨。小元元只能拿一个苹果或一个梨。37/1694）.条件条件
19、定义：给定两个命题定义：给定两个命题P和和Q，其条件命题是一个复，其条件命题是一个复合命题，记作合命题，记作P Q。命题命题PQ是假是假,当且仅当当且仅当P是是真而真而Q是假。是假。运算符运算符可能运算结果以下表所表示。可能运算结果以下表所表示。P QP QT TT FF TF FTFTT38/169在使用蕴涵联结词时，除了注意其表示基本逻辑在使用蕴涵联结词时，除了注意其表示基本逻辑关系外，还应注意两点：关系外，还应注意两点：在数理逻辑中，在数理逻辑中，“假如假如”与与“那么那么”之之间不需要有因果联络，只要间不需要有因果联络，只要P、Q能够分别确定能够分别确定真值，真值，P Q即成为命题。即
20、成为命题。在在P Q中，只要前提为中，只要前提为F时，条件命题真值都时，条件命题真值都是是F。39/169例例1：(a)P：天不下雨。天不下雨。Q：草木枯黄。草木枯黄。PQ：假如天不下雨，假如天不下雨，则草木枯黄则草木枯黄。(b)R：G是正方形。是正方形。S：G四边相等。四边相等。RS：假如假如G是正方形，则是正方形，则G四边相等四边相等。(c)W：桔子是紫色。桔子是紫色。V：大地是不平。：大地是不平。WV：假如桔子是紫色，假如桔子是紫色，则大地是不平则大地是不平。40/169例例2：将以下命题符号化，并判断其真值：将以下命题符号化，并判断其真值1）.若若2+24，则太阳从东方升起。，则太阳从
21、东方升起。2）.若若2+24，则太阳从东方升起。，则太阳从东方升起。3）.若若2+24，则太阳从西方升起。，则太阳从西方升起。4）.若若2+24，则太阳从西方升起。，则太阳从西方升起。解解 设设：P:2+24，则其真值为，则其真值为T；q:太阳从东方升起，则太阳从东方升起，则其真值为其真值为T；r:太阳从西方升起，则其真值为太阳从西方升起，则其真值为F；则则(1)符号化为符号化为pq，该蕴涵式真值为，该蕴涵式真值为T。(2)符号化为符号化为 pq，该蕴涵式真值为，该蕴涵式真值为T。(3)符号化为符号化为pr，该蕴涵式真值为，该蕴涵式真值为F。(4)符号化为符号化为 pr，该蕴涵式真值为，该蕴涵
22、式真值为T。41/169 总总 结结1.1.蕴蕴含含式式PQPQ基基本本逻逻辑辑关关系系是是，Q Q是是P P必必要要条条件件，或或P P是是Q Q充充分分条条件件。有有各各种种等等价价方方式式表表示示：“只只要要P，就就Q”、“因因为为P，所所以以Q”、“P仅仅当当Q”、“只有只有Q才才P”、“除非除非P才才Q”等。等。2.给定命题PQ,我们把QP,P Q,Q P分别叫做命题PQ逆逆命命题题、反反命命题题和逆逆反反命题命题.42/169例例3 将以下命题符号化：将以下命题符号化：(1)只要只要不下雨，我就就骑自行车上班。(2)只有只有不下雨，我才才骑自行车上班。解解 令令p:天下雨；天下雨；
23、q:我骑自行车上班。我骑自行车上班。(1)只要不下雨，我就骑自行车上班：p是充是充分条件，因而应符号化为分条件，因而应符号化为 pq。(2)只有不下雨，我才骑自行车上班：p是必是必要条件，因而应符号化为要条件，因而应符号化为q p。43/169课堂练习：课堂练习：将以下命题符号化（其中命题中出现将以下命题符号化（其中命题中出现a是给定一个正整数）是给定一个正整数）:(1)只要只要a能被能被4整除，则整除，则a一定能被一定能被2整除。整除。(2)a能被能被4整除，仅当整除，仅当a能被能被2整除。整除。(3)除非除非a能被能被2整除，整除，a才能被才能被4整除。整除。(4)除非除非a能被能被2整除
24、，不然整除，不然a不能被不能被4整除。整除。(5)只有只有a能被能被2整除，整除，a才能被才能被4整除。整除。(6)只有只有a能被能被4整除，整除，a才能被才能被2整除。整除。44/169 5）.双条件（等值于）双条件（等值于）定定义义：假假如如P和和Q是是命命题题,那那么么“P等等值值于于Q”也也是是命命题题,记记为为P Q,称称为为等等值值式式,读读做做“P等等值值于于Q”，P当当且且仅当仅当Q。等值式所表示逻辑关系是与互为充充分分必必要要条条件件。只要P与Q真值同为真或同为假，P Q 真值就为真，不然真值为假。45/169运算符运算符全部可能结果以下表所表示：全部可能结果以下表所表示：P
25、 QP QT TT FF TF FTFFF46/169例：例：将以下命题符号化，并讨论它们真值将以下命题符号化，并讨论它们真值:(1)雪是白色当且仅当法国首都是里昂。雪是白色当且仅当法国首都是里昂。(2)n是奇数充分必要条件是是奇数充分必要条件是n2是奇数。是奇数。(3)若若两两圆圆O1，O2面面积积相相等等，则则它它们们半半径径相相等等。反之，若反之，若O1，O2半径相等，则它们面积相等。半径相等，则它们面积相等。(4)设设角角1与与角角2是是对对顶顶角角，则则角角1等等于于角角2。反反之之，若角若角1等于角等于角2，则它们是对顶角。，则它们是对顶角。47/169小结命题概念和表示；命题联结
26、词 否定；合取；析取；条件；双条件；48/1691-3 命题公式与翻译定义：命题公式合式公式，要求为：定义：命题公式合式公式，要求为：（1 1）单个命题变元是）单个命题变元是合式合式公式；公式；（2 2）假如）假如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)所所得得到到包包含含命命题题变变元元、联联结结词词和和括括号号符符号号串串是是合合式式公式
27、。公式。49/169 定义递归性：定义递归性：(1)(1)是递归基础，由是递归基础，由(1)(1)开始，使用开始，使用(2)(3)(2)(3)规规则，能够得到任意合式公式。则，能够得到任意合式公式。下面式子是合式公式：下面式子是合式公式：P PQQ，(PQ)R)(PQ)R)下面式子不是合式公式：下面式子不是合式公式：(P (P V R V R Q)Q)约定（约定（1 1）优先次序：）优先次序：，V,V,，。（2 2）为方便，最外层括号能够不写。）为方便，最外层括号能够不写。50/169命题翻译命题翻译 能够把自然语言中有些语句，转变成数理逻能够把自然语言中有些语句，转变成数理逻辑中符号形式，称
28、为命题翻译。辑中符号形式，称为命题翻译。命题翻译时应注意以下事项：命题翻译时应注意以下事项：（1 1）确定所给句子是否为命题。）确定所给句子是否为命题。（2 2）句子中联结词是否为命题联结词。）句子中联结词是否为命题联结词。（3 3）要正确选择原子命题和适当命题联结词。）要正确选择原子命题和适当命题联结词。51/169例1.说离散数学无用且枯燥无味是不正确。P：离散数学是有用。Q：离散数学是枯燥无味。该命题可写成：(PQ)52/169例2.假如小张与小王都不去，则小李去。P：小张去。Q：小王去。R：小李去。该命题可写成：(PQ)R 假如小张与小王不都去，则小李去。该命题可写成：(PQ)R 也能
29、够写成：(PQ)R53/169 所谓命题符号化，就是用命题公式符号串来表所谓命题符号化，就是用命题公式符号串来表示给定命题。示给定命题。命题翻译（命题符号化）方法命题翻译（命题符号化）方法 1.首先要明确给定命题含义。首先要明确给定命题含义。2.对于复合命题，找联结词，用联结词对于复合命题，找联结词，用联结词 断句，分解出各个原子命题。断句，分解出各个原子命题。3.设原子命题符号，并用逻辑联结词联设原子命题符号，并用逻辑联结词联 结原子命题符号，组成给定命题符结原子命题符号，组成给定命题符 号表示式。号表示式。54/169例3.仅当天不下雨且我有时间，才上街。P：天下雨。Q：我有时间。R：我上
30、街。分析：因为“仅当”是表示“必要条件”，既“天不下雨且我有时间”，是“我上街”必要条件。该命题可写成：R(PQ)55/169例4.人不犯我，我不犯人；人若犯我，我必犯人。P：人犯我。Q：我犯人。该命题可写成：(PQ)(PQ)P是Q必要条件P是Q充分条件P是Q充分且必要条件或写成：PQ56/1691-4真值表和等价公式 一个命题公式不是复合命题，所以它没有真值，不过给其中全部命题变元作指派以后它就有了真值。能够以表形式反应它真值情况。定义：在命题公式中，对于分量指派真值各种可 能组合，就确定了这个命题公式各种真值情况，把它汇列成表，就是命题公式真值表。57/169比如命题公式：(PQ)Q 真值
31、表以下所表示：PQPPQ(PQ)QFFTFFFTTTTTFFTTTTFTT58/169比如命题公式（PQ）P 真值表以下：PQ PQP（PQ）PTTTFFTFFFFFTFTFFFFTF59/169比如命题公式：（PQ）V（P Q）真值表以下所表示：PQP QPQ P Q（PQ）V（P Q）TTFFTFTTFFTFFFFTTFFFFFFTTFTT60/169因为对每个命题变元能够有两个真值因为对每个命题变元能够有两个真值(T,F)(T,F)被指派，被指派，所以有所以有n n个命题变元命题公式个命题变元命题公式 A(P A(P1 1,P,P2 2,P,Pn n)真真值表有值表有2 2n n行行。为
32、为有序地列出有序地列出A(PA(P1 1,P,P2 2,P,Pn n)真值表，可将真值表，可将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)。61/16901234567000001010011100101110111FFF FFT FTF FTT TFF TFT TTF TTT如如A(P,Q,R)真值表可按照以下次序指派：真值表可按照以下次序指派：A(P1,P2,Pn)真值
33、表，按照二进制数以下次序指派(0000 0001 00101110 11110122n-22n-162/169 结构真值表方法以下：结构真值表方法以下：（1）找出公式中全部命题变元）找出公式中全部命题变元（2）列出公式中）列出公式中2n个解释进行赋值个解释进行赋值（3）依据赋值依次计算各层次真值并最终计）依据赋值依次计算各层次真值并最终计算出公式真值。算出公式真值。63/169列出P(QR)真值表真值表PQRQRP(QR)FFFTTFFTTTFTFFTFTTTTTFFTTTFTTTTTFFFTTTTT00000101001110010111011164/169等价公式 1、例子 看下面三个公式
34、真值表 从真值表能够看出，不论对P、Q作何指派，都使得PQ、PQ和QP真值相同，表明它们之间彼此等价。PQPQPQQPFFTTTFTTTTTFFFFTTTTT65/1692.定义：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 PQQP66/169分配律分配律 P(QR)(PQ)(PR)P(QR)(PQ)(PR)吸收律吸收律 P(PQ)P P(PQ)P底底-摩根定律
35、摩根定律 (PQ)P Q (PQ)P Q 同一律同一律 PFP PTP 零律零律 PTT PFF 互补律互补律 P PT P PF PQ PQ PQ QP PQ(PQ)(QP)67/169等价置换定理定义：假如X是合式公式A一部分，且X本身也是一个合式公式，则称X为公式A子公式。定理：设X是合式公式A子公式，若XY，假如将A中X用Y来置换，所得到公式B与公式A等价，即AB。68/169例：证实Q（PV（PVQ）QP。证：设 A：Q（PV（PVQ）因为 PV（PQ）P 故B：QP。从而 A B。注：能够用真值表证实。69/169例例1:证实证实P QQ PQ 证：PQQ QP Q (QP)(Q
36、Q)(QP)T QP PQ 70/169例例2 2、用逻辑等价演算法处理下面问题:A，B，C，D 4人做百米竞赛。观众甲、乙、丙预测比赛名次为：甲：C得第一，B得第二；乙：C得第二，D得第三；丙：A得第二，D得第四。比赛结束后发觉甲、乙、丙每人预测情况都只对了二分之一，试问实际名次怎样(假设无并列者？)71/1691-5 重言式与蕴含式 可见不论P取什么真值PP 真值总是为真，PP真值总是为假。故称 PP为重言式(永真式)，称PP为矛盾式(永假式)。PPPPPFTFTTF1、例子72/169小结命题公式和符号化；真值表等价公式定义和证实 真值表 命题定律73/1692.重言式(矛盾式)定义 A
37、(P1,P2,Pn)是含有命题变元P1,P2,Pn命题公式，如不论对P1,P2,Pn作任何指派，都使得A(P1,P2,Pn)为真真(假假)，则称之为重言式(矛盾式矛盾式),也称之为永真式(永假式永假式)74/1693.重言式性质 1).假如A是重言式，则A是矛盾式。2).假如A，B是重言式，则(AB)、(AB)、(AB)和(AB)也都是重言式。3).假如A是重言式，则A置换例式也是重言式。75/169定理：任何两个重言式合取或析取，依然是一个定理：任何两个重言式合取或析取，依然是一个重言式。重言式。定理：一个重言式，对同一分量都用任何合式公定理：一个重言式，对同一分量都用任何合式公式置换，其结
38、果依然是一重言式。式置换，其结果依然是一重言式。设设A、B为两个命题，为两个命题，AB当且仅当当且仅当 AB是重言是重言式。式。76/1694.重言式证实方法 方法1：列真值表。方法2：公式等价变换，化简成“T”。方法3：用公式主析取范式。其中方法3 我们在以后讨论。77/169定义：假如公式AB是重言式，则称A(永真)蕴涵 B，记作AB。注意：注意：符号“”不是联结词，它是表示公式间“永真蕴涵”关系，也能够看成是“推导”关系。即AB能够了解成由A A可推出可推出B B，即由A为真，能够推出B也为真。78/169给定命题PQ,QP：逆换式（逆命题）逆命题）P Q：反换式（否命题）（否命题）Q
39、P：逆反式（逆否命题）逆否命题）重言蕴含式可用真值表证实，也可用以下方法证实：(1)假定前件是真,若能推出后件是真,则此蕴含式是 真。(2)假定后件是假,若能推出前件是假,则此蕴含式是 真。79/169 例：例：证实证实 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。80/169主要重言蕴涵式(如教材第43页所表示)I1.PQP I2.PQQ I3.PPQ I4.QPQ I5.P
40、PQ I6.QPQ I7.(PQ)P I8.(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)81/169 蕴含式性质：蕴含式性质：设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
41、B,则则A A CC B B。设设P P、Q Q为任意两个命题公式，为任意两个命题公式，P PQ Q充分必要条件是充分必要条件是P PQ Q 且且Q QP P。82/1691-6 其它联结词不可兼析取不可兼析取 条件否定条件否定与非与非或非或非83/1691 不可兼析取联结词不可兼析取联结词 定义：定义：当且仅当命题当且仅当命题 P 与命题与命题 Q 真值不一样时取值为真值不一样时取值为 T，不，不然取值为然取值为 F 命题称为命题命题称为命题 P 与与 Q 不可兼析取命题，记作不可兼析取命题，记作 P Q。命题。命题 P Q 真值与命题真值与命题 P 和命题和命题 Q 真值之间关系如表所真值
42、之间关系如表所表示：表示：PQP QTTFTFTFTTFFF84/169“不可兼析取不可兼析取不可兼析取不可兼析取”联结词。该联结词含有以下一些性质：联结词。该联结词含有以下一些性质：联结词。该联结词含有以下一些性质：联结词。该联结词含有以下一些性质：设设设设P P,QQ,R R为任意命题公式，则有为任意命题公式，则有为任意命题公式，则有为任意命题公式，则有 P Q P Q Q PQ P。（交换律）（交换律）（交换律）（交换律）(P P Q Q)R R P P (Q R Q R)。（结合律）（结合律）（结合律）（结合律）P P(Q R Q R)(P PQ Q)()(P PR R)。（分配律）（
43、分配律）（分配律）（分配律）P Q P Q (P PQ Q)(P PQ Q)P P QQ。P Q P Q(P P Q Q)。P P P P F,F F,F P P P P,T ,T P P P P。85/169定理定理:设设 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 F 86/1692 条件否定联结词条件否定联结词定定义义:当当且且仅仅当当命命题题 P 真真值值为为 T，命命题题 Q 真
44、真值值为为 F 时时取取值值为为 T，不不然然取取值值为为 F 命命题题称称为为命命题题 P 和和命命题题Q 条条件件否否定定命命题题，记记为为 P Q。命命题题 P Q 真真值值与与命命题题 P 和和命命题题 Q 真真值值之之间关系如表所表示：间关系如表所表示：PQP QTTFTFTFTFFFFc cc c87/1693 与非联结词与非联结词 定定义义:当当且且仅仅当当命命题题 P 和和命命题题 Q 真真值值都都为为 T 时时取取值值为为 F，不不然然取取值值为为 T 命命题题称称为为命命题题 P 和和命命题题 Q 与与非非命命题题，记记为为 P Q。命命题题 P Q 真真值值与与命命题题
45、P 和和命命题题 Q 真真值值之之间关系如表所表示：间关系如表所表示：PQP QTTFTFTFTTFFT88/169设设 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 不等价。不等价。89/1694 或非联结词或非联结词定定义义:当当且且仅仅当当命命题题 P 和和命命题题 Q 真真值值都都为为 F 时时取取值值为为 T，不不然然取取值值为为 F 命命题题称称为为命命题题 P
46、和和命命题题 Q 或或非非命命题题，记记为为 P Q。命命题题 P Q 真真值值与与命命题题 P 和和命命题题 Q 真真值值之之间间关关系如表所表示：系如表所表示：PQP QTTFTFFFTFFFT90/169设设 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 不等价。不等价。91/169联结词联结词1 列表示永假列表示永假F；联结词联结词2 列表示命题变元列表示命题变元P
47、；联结词联结词3 列表示命题变元否定：列表示命题变元否定：P；联结词联结词4 列表示永真列表示永真T；故除了常量故除了常量 T、F 及命题变元本身外，一个一元及命题变元本身外，一个一元联结词就足够了。联结词就足够了。P联结词1联结词2联结词3联结词4TFTFTFFFTT92/169P Q联结词1联结词2联结词3联结词4联结词5联结词6联结词7联结词8联结词9联结词10联结词11联结词12联结词13联结词14联结词15联结词16T TTFTTFFTFTFTFTFTFT FTFTFFTFTTFFTFTTFF TTFFTTFFTTFTFFTFTF FTFFFTTTTFTTFTFTF93/169联结词
48、联结词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；联结词联结词8、联结词、联结词10、联结词、联结词12、联结词、联结词14、联结词、联结词16是是我们补充其它联结词。我们补
49、充其它联结词。94/1695 联结词之间关系联结词之间关系到此为止，我们已讨论了到此为止，我们已讨论了 9 个联结词个联结词 ,。这些联结词之间含有以下一些性质：这些联结词之间含有以下一些性质：全部一元、二元联结词均可用全部一元、二元联结词均可用 与与 来表示。来表示。全部一元、二元联结词均可用全部一元、二元联结词均可用 与与 来表示。来表示。全部一元、二元联结词均可用全部一元、二元联结词均可用 与与 来表示。来表示。c c95/169定义定义:设设 S 是一个联结词集合，若是一个联结词集合，若:(1)任一公式都有一个仅用任一公式都有一个仅用 S 中联结词表示等价公式，则称中联结词表示等价公式
50、，则称 S 是是完备；完备；(2)从从 S 中去掉任一个联结词后得到联结词集合中去掉任一个联结词后得到联结词集合 S，若最少存，若最少存在一个公式在一个公式 B，不存在仅用，不存在仅用 S 中联结词表示且与中联结词表示且与 B 等价公等价公式，则称式，则称 S 是最小完备联结词集。是最小完备联结词集。定理定理:,、,和和,都是最小完备联结词集。都是最小完备联结词集。下面仅证下面仅证,是最小完备联结词集。是最小完备联结词集。证实：首先，任意公式都存在仅包含联结词与证实：首先，任意公式都存在仅包含联结词与等价公式。等价公式。再者，若从联结词集再者，若从联结词集,中去掉联结词得联结词集中去掉联结词得
