离散数学(一)只是课件.ppt

离散数学(一)课程主要内容第一部分第一部分 数理逻辑数理逻辑第二部分第二部分 集合论集合论第三部分第三部分 代数系统代数系统第四部分第四部分 图论图论离散数学与计算机的关系离散数学与计算机的关系第一部分第一部分 数理逻辑数理逻辑 计算机是数理逻辑和电子学相结合的产物计算机是数理逻辑和电子学相结合的产物 第二部分第二部分 集合论集合论 集合：一种重要的数据结构集合：一种重要的数据结构 关系：关系数据库的理论基础关系：关系数据库的理论基础 函数：所有计算机语言中不可缺少的一部分函数：所有计算机语言中不可缺少的一部分 第三部分第三部分 代数系统代数系统 计算机编码和纠错码理论数字逻辑设计基础，计算机使计算机编码和纠错码理论数字逻辑设计基础，计算机使用的各种运算用的各种运算 第四部分第四部分 图论图论 数据结构、操作系统、编译原理、计算机网络原理的基数据结构、操作系统、编译原理、计算机网络原理的基础础 参考教材参考教材1、离散数学离散数学耿素云、屈婉玲、张立昂耿素云、屈婉玲、张立昂清华大学出版社清华大学出版社2、离散数学题解离散数学题解耿素云、屈婉玲、张立昂耿素云、屈婉玲、张立昂清华大学出版社清华大学出版社3、离散数学导论离散数学导论徐洁磐徐洁磐高等教育出版社高等教育出版社4、离散数学离散数学洪帆等编洪帆等编电子工业出版社电子工业出版社5、离散数学离散数学李盘林等编李盘林等编人民邮电出版社人民邮电出版社学习要求出勤出勤思考思考笔记笔记作业作业绪论绪论本课程是高校计算机专业学生的必修课之一，是计算机科本课程是高校计算机专业学生的必修课之一，是计算机科学与技术专业的核心、骨干课程，也是数学、信息与计算学与技术专业的核心、骨干课程，也是数学、信息与计算科学、信息管理与信息系统等专业的专业基础课程，是计科学、信息管理与信息系统等专业的专业基础课程，是计算机科学与技术的理论基础算机科学与技术的理论基础该课程主要学习数理逻辑、集合论、代数结构、图论等四该课程主要学习数理逻辑、集合论、代数结构、图论等四大方面的内容，包括：命题逻辑、谓词逻辑、集合与关系、大方面的内容，包括：命题逻辑、谓词逻辑、集合与关系、函数、代数结构、格与布尔代数、图论等函数、代数结构、格与布尔代数、图论等离散数学与计算机科学中的数据结构、操作系统、编译原离散数学与计算机科学中的数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构等课程联系紧密理、算法分析、逻辑设计、系统结构等课程联系紧密本课程重点在于培养和提高大学生的抽象思维、逻辑推理本课程重点在于培养和提高大学生的抽象思维、逻辑推理和概括能力，从而为以后专业课程的学习及工作需要打下和概括能力，从而为以后专业课程的学习及工作需要打下基础基础绪论绪论离散数学课程地位：离散数学课程地位：计算机专业（核心课程）计算机专业（核心课程）信息类专业（必修课程）信息类专业（必修课程）其它类专业（重要选修课程）其它类专业（重要选修课程）离散数学的后继课程：离散数学的后继课程：数据结构、操作系统、数据结构、操作系统、算法分析与设计、算法分析与设计、数据库、数据库、C+C+语言语言绪论绪论离散数学课程的学习方法离散数学课程的学习方法:强调强调：逻辑性、抽象性；：逻辑性、抽象性；注重注重：概念、方法与应用：概念、方法与应用离散数学的学习要领：离散数学的学习要领：概念（正确）概念（正确）必须掌握好离散数学中大量的必须掌握好离散数学中大量的 概念概念 判断（准确）判断（准确）根据概念对事物的属性进行判断根据概念对事物的属性进行判断 推理（可靠）推理（可靠）根据多个判断推出一个新的判断根据多个判断推出一个新的判断例1：说谎者与说真话者问题：说谎者与说真话者问题：N N夫妇晚上出门，邀请了夫妇晚上出门，邀请了W W小姐照小姐照看他们的看他们的4 4个孩子。在个孩子。在N N夫妇离家以前，向夫妇离家以前，向W W小姐交待了许小姐交待了许多注意事项，其中包括多注意事项，其中包括4 4个孩子的情况。个孩子的情况。N N夫妇说他们的夫妇说他们的4 4个孩子中只有一个孩子总是说真话，另外个孩子中只有一个孩子总是说真话，另外3 3个则总是说谎。个则总是说谎。N N夫妇告诉了夫妇告诉了W W小姐说真话的孩子的名字，但由于注意事项小姐说真话的孩子的名字，但由于注意事项太多，太多，W W小姐把名字忘记了。当她在为孩子们准备晚饭时，小姐把名字忘记了。当她在为孩子们准备晚饭时，一个孩子在邻室打碎了一个花瓶。一个孩子在邻室打碎了一个花瓶。这是孩子们的话：这是孩子们的话：B B说：是说：是S S干的。干的。S S说：是说：是J J干的。干的。L L说：不是我打碎的。说：不是我打碎的。J J说：说：S S说是我干的，他在说慌。说是我干的，他在说慌。由于由于W W小姐知道只有一个孩子说真话，她很快就找出了打碎小姐知道只有一个孩子说真话，她很快就找出了打碎花瓶的孩子。你知道是谁吗？花瓶的孩子。你知道是谁吗？例2：设整数集合为设整数集合为Z Z设自然数集合为设自然数集合为N N比较比较Z Z与与N N元素的多少元素的多少例3：对于给定自然数对于给定自然数1n的任意排列，能否通过的任意排列，能否通过反复交换反复交换1，2，3，n中的元素而得到中的元素而得到此排列？此排列？=(15236)(78)=(15)(12)(13)(16)(78)例4：任意任意6 6人聚会中，必有人聚会中，必有3 3人人彼此相识，或有彼此相识，或有3 3人彼此人彼此不相识不相识用两种颜色填涂完全图用两种颜色填涂完全图K K6 6的各边，必包含有同色的各边，必包含有同色的的“三角形三角形”K K3 3第一部分数理逻辑先看著名物理学家爱因斯坦出过的一道题：先看著名物理学家爱因斯坦出过的一道题：一个土耳其商人想找一个十分聪明的助手协助他经商，一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。说出自己头上戴的帽子是什么颜色的。”说完后，商人将说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：喊道：“我戴的是黑帽子。我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？请问这个人说得对吗？他是怎么推导出来的呢？主要内容1 1 命题逻辑基本概念命题逻辑基本概念2 2 命题逻辑等值演算命题逻辑等值演算 3 3 命题逻辑的推理理论命题逻辑的推理理论4 4 一阶逻辑基本概念一阶逻辑基本概念 5 5 一阶逻辑等值演算与推理一阶逻辑等值演算与推理1 1 命题逻辑基本概念命题逻辑基本概念本章的主要内容：本章的主要内容：命题、联结词、复合命题命题、联结词、复合命题 命题公式、赋值、命题公式的分类命题公式、赋值、命题公式的分类1.1 1.1 命题与联结词命题与联结词1.2 1.2 命题公式及其赋值命题公式及其赋值1.1 1.1 命题与联结词命题与联结词命题及其分类命题及其分类联结词与复合命题联结词与复合命题复合命题的真假值复合命题的真假值1.1.1 1.1.1 命题及其分类命题及其分类命题：命题：具有真假意义（判断结果唯一）的陈具有真假意义（判断结果唯一）的陈述句述句命题的真值：命题的真值：判断结果判断结果真值的取值：真值的取值：真（真（1 1）、假（）、假（0 0）真命题与假命题真命题与假命题注意：注意：感叹句、祈使句、疑问句、悖论都不感叹句、祈使句、疑问句、悖论都不是命题是命题例例1.11.1 下列句子中那些是命题？下列句子中那些是命题？(1)是无理数是无理数.(2)2+58.(3)x+53.(4)你有铅笔吗？你有铅笔吗？(5)这只兔子跑得真快呀！这只兔子跑得真快呀！(6)请不要讲话！请不要讲话！(7)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题1.1.1 1.1.1 命题及其分类命题及其分类1.1.1 1.1.1 命题及其分类命题及其分类命题的分类命题的分类（1）简单命题（原子命题）简单命题（原子命题）（2）复合命题）复合命题简单命题符号化简单命题符号化（1）用小写英文字母）用小写英文字母等来表示简单命题等来表示简单命题（2）用）用1表示真，用表示真，用0表示假表示假例如：例如：:3是无理数，则是无理数，则是假命题，是假命题，的真值为的真值为01.1.2联结词与复合命题例：例：3是无理数是不对的2是偶素数2或4是素数如果2是素数，则3也是素数2是素数当且仅当3也是素数。上述命题都是通过诸如上述命题都是通过诸如“或或”，“如果如果，则，则”等连词等连词联结而成，这样命题，称为复合命题。相对地，构成复合命联结而成，这样命题，称为复合命题。相对地，构成复合命题的命题称为简单命题。题的命题称为简单命题。1.1.2联结词与复合命题定义定义1.1设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式否定式,记作p，符号称作否定否定联结词联结词。并规定p为真当且仅当p为假。定义定义1.2设p,q为二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式合取式，记作pq，称作合取联结词合取联结词。并规定pq为真当且仅当p与q同时为真。定义定义1.3设p，q为二命题，复合命题“p或q”称作p与q的析取式析取式，记作pq，称作析取联结词析取联结词。并规定pq为假当且仅当p与q同时为假。1.1.2联结词与复合命题相容相容“或或”与排斥与排斥“或或”例例将下列命题符号化。将下列命题符号化。(1)(1)张晓静爱唱歌或爱听音乐。张晓静爱唱歌或爱听音乐。(2)(2)张晓静是江西人或安徽人。张晓静是江西人或安徽人。(3)(3)张晓静只能挑选张晓静只能挑选202202或或203203房间。房间。解解在解题时，先将原子命题符号化。在解题时，先将原子命题符号化。(1)p(1)p：张晓静爱唱歌。：张晓静爱唱歌。q q：张晓静爱听音乐。：张晓静爱听音乐。(2)r(2)r：张晓静是江西人。：张晓静是江西人。s s：张晓静是安徽人。：张晓静是安徽人。(3)t(3)t：张晓静挑选：张晓静挑选202202房间。房间。u u：张晓静挑选：张晓静挑选203203房间。房间。1.1.2联结词与复合命题思考题：只能在周二说的话思考题：只能在周二说的话某人在周一总是说谎话，而在其它日子总是某人在周一总是说谎话，而在其它日子总是说真话。那么，有没有他只能在周二才能说真话。那么，有没有他只能在周二才能说的话呢？说的话呢？“今天不是周一就是周二。今天不是周一就是周二。”1.1.2联结词与复合命题定义定义1.4设p，q为二命题，复合命题“如果p，则q”称作p与q的蕴涵式蕴涵式，记作pq，称作蕴涵联蕴涵联结词结词。并规定pq为假当且仅当p为真q为假。pq的逻辑关系表示q是p的必要条件。注意注意在使用联结词时，特别注意以下几点：1.1.2联结词与复合命题在自然语言里，特别是在数学中，在自然语言里，特别是在数学中，q q是是p p的必要条件有许的必要条件有许多不同的叙述方式。例如，多不同的叙述方式。例如，“只要只要p p，就，就q”q”，“因为因为p p，所以所以q”q”，“p p仅当仅当q”q”，“只有只有q q才才p”p”，“除非除非q q才才p”p”，“除非除非q q，否则非，否则非p”p”等等。以上各种叙述方式表面看来等等。以上各种叙述方式表面看来有所不同，但都表达的是有所不同，但都表达的是q q是是p p的必要条件，因而所用联的必要条件，因而所用联结词均应符号化为结词均应符号化为，上述各种叙述方式都应符号化为，上述各种叙述方式都应符号化为pqpq。在自然语言中，在自然语言中，“如果如果p p，则，则q”q”中的前件中的前件p p与后件与后件q q往往往往具有某种内在联系。而在数理逻辑中，具有某种内在联系。而在数理逻辑中，p p与与q q可以无任何可以无任何内在联系。内在联系。在数学或其它自然科学中，在数学或其它自然科学中，“如果如果p p，则，则q”q”往往表达的往往表达的是前件是前件p p为真，后件为真，后件q q也为真的推理关系。但在数理逻辑也为真的推理关系。但在数理逻辑中，作为一种规定，当中，作为一种规定，当p p为假时，无论为假时，无论q q是真是假，是真是假，pqpq均为真。也就是说，只有均为真。也就是说，只有p p为真为真q q为假这一种情况使得复为假这一种情况使得复合命题合命题pqpq为假。为假。1.1.2联结词与复合命题定义定义1.5设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式等价式，记作，称作等价联结词等价联结词。并规定为真当且仅当p与q同时为真或同时为假。的逻辑关系为p与q互为充分必要条件。以上定义了五种最基本、最常用、也是最重要的联结词以上定义了五种最基本、最常用、也是最重要的联结词，将它们组成一个集合，将它们组成一个集合，称为一个联结词集。其中，称为一个联结词集。其中为一元联结词，为一元联结词，其余的都是二元联结词。其余的都是二元联结词。1.1.2联结词与复合命题例例将下列命题符号化，并指出各复合命题的真值：(1)如果3+36，则雪是白的。(2)如果3+36，则雪是白的。(3)如果3+36，则雪不是白的。(4)如果3+36，则雪不是白的。以下命题中出现的a是一个给定的正整数：(5)只要a能被4整除，则a一定能被2整除。(6)a能被4整除，仅当a能被2整除。(7)除非a能被2整除，a才能被4整除。(8)除非a能被2整除，否则a不能被4整除。(9)只有a能被2整除，a才能被4整除。(10)只有a能被4整除，a才能被2整除。1.1.3复合命题真假值联结词可以嵌套使用，在嵌套使用时，规定如下优先顺序：()，对于同一优先级的联结词，先出现者先运算。1.2命题公式及其赋值命题公式及其赋值命题公式的定义命题公式的定义 公式的层次公式的层次 公式的赋值公式的赋值 真值表真值表 公式的真假值分类公式的真假值分类1.2.1命题公式的定义命题公式的定义由于简单命题是真值唯一确定的命题逻辑中最基由于简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为本的研究单位，所以也称简单命题为命题常项命题常项或或命题常元命题常元。从本节开始对命题进一步抽象，首先。从本节开始对命题进一步抽象，首先称真值可以变化的陈述句为称真值可以变化的陈述句为命题变项命题变项或或命题变命题变元元，也用，也用p,q,r,p,q,r,表示命题变项。当表示命题变项。当p,q,r,p,q,r,表表示命题变项时，它们就成了取值示命题变项时，它们就成了取值0 0或或1 1的变项，因的变项，因而命题变项已不是命题。这样一来，而命题变项已不是命题。这样一来，p,q,r,p,q,r,既既可以表示命题常项，也可以表示命题变项。在使可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是用中，需要由上下文确定它们表示的是常项还是变项。变项。1.2.1命题公式的定义命题公式的定义定义定义1.6(1)单个命题变项是合式公式合式公式，并称为原子命题公式原子命题公式。(2)若A是合式公式，则(A)也是合式公式。(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。(4)只有有限次地应用(1)(3)形式的符号串才是合式公式。合式公式合式公式也称为命题公式命题公式或命题形式命题形式，并简称为公式公式。如：(pq)(qr)，(pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。注意：注意：定义1.6给出的合式公式的定义方式称为归纳定义方式，后面还将多次出现这种定义方式。1.2.2公式的层次公式的层次1.2.3公式的赋值公式的赋值1.2.3公式的赋值公式的赋值定义定义1.8 1.8 设设p p1 1,p,p2 2,p,pn n是出现在公式是出现在公式A A中的中的全部命题符号，给全部命题符号，给p p1 1,p,p2 2,p,pn n各指定一个各指定一个真值，称为对真值，称为对A A的一个赋值或解释。若指定的一个赋值或解释。若指定的一组值使的一组值使A A的真值为的真值为1 1，则称这组值为，则称这组值为A A的的成真赋值；若使成真赋值；若使A A的真值为的真值为0 0，则称这组值，则称这组值为为A A的成假赋值。的成假赋值。不难看出，含不难看出，含n(n=1)个命题变项的公式共个命题变项的公式共有有2n个不同的赋值。个不同的赋值。1.2.4真值表定义1.9 将命题公式A在所有赋值下取值情况列成表，称作A的真值表。构造真值表的具体步骤如下：(1)找出公式中所含的全体命题变项p1,p2,pn(若无下角标就按字典顺序排列)，列出2n个赋值。本课件规定，赋值从000开始，然后按二进制加法依次写出各赋值，直到111为止。(2)按从低到高的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。1.2.4真值表例例1.8求下列公式的真值表，并求成真赋值和成假赋值。1.2.4真值表1.2.4真值表1.2.4真值表1.2.5公式的真假值分类定义定义1.10 1.10 设设A A为任一命题公式。为任一命题公式。(1)(1)若若A A在它的各种赋值下取值均为真在它的各种赋值下取值均为真,则称则称A A是是重言式重言式或或永真式永真式。(2)(2)若若A A在它的各种赋值下取值均为假在它的各种赋值下取值均为假,则称则称A A是是矛盾矛盾式式或或永假式永假式。(3)(3)若若A A不是矛盾式不是矛盾式,则称则称A A是是可满足式可满足式。注：关于n个命题变元P1,P2,Pn,可以构造多少个真值表呢?n个命题变元共产生2n个不同赋值,在每个赋值下,公式的值只有0和1两个值。于是n个命题变元的真值表共有种不同情况。1.2.5公式的真假值分类例例1.10 1.10 下列公式中下列公式中,哪些具有相同的真值哪些具有相同的真值表表?(1)pq (1)pq(2)qr(2)qr(3)(pq)(pr)p)(3)(pq)(pr)p)(4)(qr)(pp)(4)(qr)(pp)1.2.5公式的真假值分类第1章小结主要内容1.命题与真值（或真假值）。2.简单命题与复合命题。3.联结词：否定联结词，合取联结词，析取联结词，蕴涵联结词，等价联结词。4.命题公式（简称公式）。5.命题公式的层次和公式的赋值。6.真值表。7.公式的类型（重言式（或永真式），矛盾式（或永假式），可满足式）。第1章小结学习要求1.在5种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题：pq的逻辑关系pq的真值pq的灵活的叙述方法2.写真值表要特别仔细认真，否则会出错误。3.深刻理解各联结词的逻辑含义。4.熟练地将复合命题符号化。5.会用真值表求公式的成真赋值和成假赋值。2命题逻辑的等值演算命题逻辑的等值演算等值式等值式对偶与范式对偶与范式 联结词的完备集联结词的完备集2.1等值式等值式等值式的概念等值式的概念用真值表判断公式的等值用真值表判断公式的等值 等值演算等值演算 2.1.1等值式的概念等值式的概念两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，公式A与公式B的真值都相同。于是等价式AB应为重言式。定义2.1设A,B是两个命题公式，若A,B构成的等价式AB为重言式，则称公式A与公式B是等值的，记作AB.2.1.1等值式的概念等值式的概念判断等值式有如下方法：判断等值式有如下方法：真值表真值表等值演算等值演算范式范式 2.1.2用真值表判断公式的等值用真值表判断公式的等值例例2.1判断下面两个公式是否等值：(pq)与pq2.1.2用真值表判断公式的等值用真值表判断公式的等值例例2.2判断下列各组公式是否等值：（1）p(qr)与(pq)r（2）(pq)r与(pq)r2.1.3等值演算等值演算2.1.3等值演算等值演算2.1.3等值演算等值演算以上以上1616组等值式包含了组等值式包含了2424个重要等值式。由于个重要等值式。由于A,B,CA,B,C可可以代表任意的公式，因而以上各等值式都是用元语言符以代表任意的公式，因而以上各等值式都是用元语言符号书写的，称这样的等值式为号书写的，称这样的等值式为等值式模式等值式模式，每个等值式，每个等值式模式都给出了无穷多个同类型的具体的等值式。模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式（例如，在蕴涵等值式（2.122.12）中，取）中，取A=pA=p，B=qB=q时，得等时，得等值式值式 pq pq pq pq 当取当取A=pqrA=pqr，B=pqB=pq时，得等值式时，得等值式(pqr)(pq)(pqr)(pq)(pqr)(pq)(pqr)(pq)这些具体的等值式都被称为原来的等值式模式的这些具体的等值式都被称为原来的等值式模式的代入实代入实例例。每个具体的代入实例的正确性都可以用真值表证每个具体的代入实例的正确性都可以用真值表证明之，而每个等值式模式可用归纳法证明之。明之，而每个等值式模式可用归纳法证明之。2.1.3等值演算等值演算2.1.3等值演算等值演算2.1.3等值演算等值演算2.1.3等值演算等值演算2.1.3等值演算等值演算2.1.3等值演算等值演算2.1.3等值演算等值演算例例2.6在某次研讨会的中间休息时间，在某次研讨会的中间休息时间，3名与会者根据名与会者根据王教授的口音对他是哪个省市的人进行了判断：王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。丙说王教授既不是上海人，也不是杭州人。听完以上听完以上3人的判断后，王教授笑着说，他们人的判断后，王教授笑着说，他们3人人中有一人说的全对，有一人说对了一半，另一人说中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里的全不对。试用逻辑演算法分析王教授到底是哪里人人？2.1.3等值演算等值演算解解设命题设命题p：王教授是苏州人。：王教授是苏州人。q：王教授是上海人。：王教授是上海人。r：王教授是杭州人。：王教授是杭州人。p,q,r中必有一个真命题，两个假命题，要中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。设通过逻辑演算将真命题找出来。设甲的判断为甲的判断为A1=p q乙的判断为乙的判断为A2=p q丙的判断为丙的判断为A3=q r2.1.3等值演算等值演算则则甲的判断全对甲的判断全对B1=A1=p q甲的判断对一半甲的判断对一半B2=(p q)(p q)甲的判断全错甲的判断全错B3=p q乙的判断全对乙的判断全对C1=A2=p q乙的判断对一半乙的判断对一半C2=(p q)(p q)乙的判断全错乙的判断全错C3=p q丙的判断全对丙的判断全对D1=A3=q r丙的判断对一半丙的判断对一半D2=(q r)(q r)丙甲的判断全错丙甲的判断全错D3=q r2.1.3等值演算等值演算由王教授所说由王教授所说E=(B1 C2 D3)(B1 C3 D2)(B2 C1 D3)(B2 C3 D1)(B2 C1 D2)(B3 C2 D1)为真命题。为真命题。E=(p q r)(p q r)但因为王教授不能既是上海人，但因为王教授不能既是上海人，又是杭州人，因而又是杭州人，因而p,r必有一个必有一个假命题，即假命题，即p q r=0，于是，于是E=p q r为真命题，因而必有为真命题，因而必有p,r为假命为假命题，题，q为真命题，即王教授是上为真命题，即王教授是上海人。甲说的全对，丙说对了一海人。甲说的全对，丙说对了一半，而乙全说错了。半，而乙全说错了。2.2对偶与范式对偶与范式对偶式与对偶原理对偶式与对偶原理 析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式2.2.1对偶式与对偶原理对偶式与对偶原理定义定义在仅含有联结词在仅含有联结词,的命题公式的命题公式A中，将中，将换成换成,换成换成，若，若A中含有中含有0或或1，就将，就将0换成换成1，1换成换成0，所得命题公式称为，所得命题公式称为A的的对偶式对偶式，记为，记为A*.从定义不难看出，从定义不难看出，(A*)*还原成还原成A，即即(A*)*A。定理定理设设A和和A*互为对偶式，互为对偶式，p1,p2,pn是出现在是出现在A和和A*中的全部命题变项，将中的全部命题变项，将A和和A*写成写成n元函数形式，元函数形式，则则(1)A(p1,p2,pn)A*(p1,p2,pn)(2)A(p1,p2,pn)A*(p1,p2,pn)定理（对偶原理）定理（对偶原理）设设A，B为两个命题公式，为两个命题公式，若若A B，则，则A*B*.2.2.2 2.2.2 析取范式与合取范式析取范式与合取范式对应于同一个真值表，可以有很多公式，其形式可以不同，但彼此等值。是否有标准形式？pqG000011101110由“1”看：与有一种情形成立，G即取1G p qp q G(p q)(p q)由“0”看：与有一种情形成立，G即取0G(p q)(p q)2.2.2 2.2.2 析取范式与合取范式析取范式与合取范式文字文字:命题变项及其否定的总称命题变项及其否定的总称简单析取式简单析取式:有限个文字构成的析取式有限个文字构成的析取式如如p,q,pq,p q r,简单合取式简单合取式:有限个文字构成的合取式有限个文字构成的合取式如如p,q,pq,p q r,析取范式析取范式:由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式A1 A2Ar,其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式:由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式A1 A2Ar,其中其中A1,A2,Ar是是简单析取式简单析取式2.2.2 2.2.2 析取范式与合取范式析取范式与合取范式范式范式:析取范式与合取范式的总称析取范式与合取范式的总称公式公式A的析取范式的析取范式:与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式:与与A等值的合取范式等值的合取范式说明：说明：单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式形如形如 pq r,p qr 的公式既是析取范式，的公式既是析取范式，又是合取范式又是合取范式 (为什么为什么?)命题公式的范式命题公式的范式定理定理任何命题公式都存在着与之等值的析取范式任何命题公式都存在着与之等值的析取范式与合取范式与合取范式.求公求公式式A的范式的步骤：的范式的步骤：(1)消去消去A中的中的,（若存在）（若存在）(2)否定联结词否定联结词 的内移或消去的内移或消去(3)使用分配律使用分配律 对对 分配（析取范式）分配（析取范式）对对 分配（合取范式）分配（合取范式）公式的范式存在，但不惟一，这是它的局限性公式的范式存在，但不惟一，这是它的局限性求公式的范式举例求公式的范式举例例例求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1)A=(pq)r解解 (pq)r(pq)r（消去（消去）pqr（结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）求公式的范式举例求公式的范式举例(续续)(2)B=(pq)r解解(pq)r (pq)r（消去第一个（消去第一个）(pq)r（消去第二个（消去第二个）(p q)r（否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续：(p q)r(p r)(q r)（对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成）极小项与极大项极小项与极大项定义定义在含有在含有n个命题变项的简单合取式个命题变项的简单合取式(简单析取式简单析取式)中，中，若每个命题变项均以文字的形式在其中出现且仅出现一若每个命题变项均以文字的形式在其中出现且仅出现一次次，而而且且第第i（1 i n）个个文文字字出出现现在在左左起起第第i位位上上，称称这这样样的简单合取式（简单析取式）为的简单合取式（简单析取式）为极小项（极大项）极小项（极大项）.说明：说明：n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的十是该极小项成真赋值的十进制表示进制表示.用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成假是该极大项成假赋值的十进制表示赋值的十进制表示,mi(Mi)称为极小项称为极小项(极大项极大项)的名称的名称.mi与与Mi的关系的关系:mi Mi,Mi mi极小项与极大项极小项与极大项(续续)由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 p q p q p q p q00011011m0m1m2m3 p qp q p q p q00011011M0M1M2M3极小项极小项极大项极大项 由由p,q,r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项极小项极小项极大项极大项公式公式成真成真赋值赋值名称名称公式公式成假成假赋值赋值名称名称 p qr p q r p qr p q rp q rp q rp qrp q r000001010011100101110111m0m1m2m3m4m5m6m7p q rp qrp q rp qr p q r p qr p q r p qr000001010011100101110111M0M1M2M3M4M5M6M7主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式:由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式:由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3是是主析取范式主析取范式(p qr)(p qr)M1 M5是是主合取范主合取范式式 A的主析取范式的主析取范式:与与A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式:与与A等值的主合取范式等值的主合取范式.主析取范式与主合取范式主析取范式与主合取范式(续续)定理定理任何命题公式都存在着与之等值的主析取范任何命题公式都存在着与之等值的主析取范式和主合取范式式和主合取范式,并且是惟一的并且是惟一的.用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，并）表示，并按角标从小到大顺序排序按角标从小到大顺序排序.求公式的主范式求公式的主范式例例求公式求公式A=(pq)r的主析取范式与主合的主析取范式与主合 取范式取范式.(1)求主析取范式求主析取范式(pq)r(p q)r,（析取范式）（析取范式）(p q)(p q)(r r)(p qr)(p q r)m6 m7,求公式的主范式求公式的主范式(续续)r(p p)(q q)r(pq r)(p q r)(pq r)(p q r)m1 m3 m5 m7,代入代入并排序，得并排序，得(pq)rm1 m3 m5 m6 m7（主析取范式）主析取范式）求公式的主范式求公式的主范式(续续)(2)求求A的主合取范式的主合取范式(pq)r(p r)(q r),（合取范式）（合取范式）p rp(qq)r(p q r)(pq r)M0 M2,求公式的主范式求公式的主范式(续续)q r(pp)q r(p q r)(p q r)M0 M4,代入代入并排序，得并排序，得(pq)rM0 M2 M4（主合取范式）（主合取范式）主范式的用途主范式的用途与真值表相同与真值表相同(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值例如例如(pq)rm1 m3 m5 m6 m7，其成真赋值为其成真赋值为001,011,101,110,111，其余的赋值其余的赋值 000,010,100为为成假赋值成假赋值.类似地，由主合取范式也可立即求出成类似地，由主合取范式也可立即求出成 假赋值和成真赋值假赋值和成真赋值.主范式的用途主范式的用途(续续)(2)判断公式的类型判断公式的类型设设A含含n个命题变项，则个命题变项，则A为重言式为重言式A的主析取范式含的主析取范式含2n个极小项个极小项A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式A的主析取范式为的主析取范式为0A的主合析取范式含的主合析取范式含2n个极大项个极大项A为非重言式的可满足式为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项的主合取范式中至少含一个且不含全部极大项主范式的用途主范式的用途(续续)例例用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值：p(qr)与与(p q)r p(qr)与与(pq)r解解 p(qr)=m0 m1 m2 m3 m4 m5 m7(p q)r=m0 m1 m2 m3 m4 m5 m7(pq)r=m1 m3 m4 m5 m7显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值.(3)判断两个公式是否等值判断两个公式是否等值说明：说明：由公式由公式A的主析取范式确定它的主合取范式，反之亦然的主析取范式确定它的主合取范式，反之亦然.用公式用公式A的真值表求的真值表求A的主范式的主范式.主范式的用途主范式的用途(续续)例例某公司要从赵、钱、孙、李、周五名新毕某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习业的大学生中选派一些人出国学习.选派必须选派必须满足以下条件：满足以下条件：(1)(1)若赵去，钱也去；若赵去，钱也去；(2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去；(3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人；(4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去；(5)(5)若周去，则赵、钱也去若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出试用主析取范式法分析该公司如何选派他们出国？国？例例(续续)解此类问题的步骤为：解此类问题的步骤为：将简单命题