离散小抄ppt课件

1,离散数学教案 课程编号： 课程学分：3.5 课程学时：56 讲授：贾美丽,2,课程性质,离散数学（又称计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。,3,课程目标,离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。,4,与其他课程的关系,离散数学与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切的联系。它是这些课程的先导和基础课程。,5,离散数学 上海科学技术文献出版社，1982 左孝凌等编著 Discrete Mathematical Structures（Fourth Edition） Higher Education Press，2001 Bernard Kolman，Robert C.Busby，Sharon Cutler Ross,教材与参考书,6,课程内容,本课程根据大纲的内容和相关独立性， 可分为四大部分 第一部分 数理逻辑 包括命题逻辑;谓词逻辑 第二部分 集合论 包括集合与关系;函数,7,课程内容,第三部分 代数系统 包括代数结构;格与布尔代数 第四部分 图论 讲课时数：62学时,8,学习方法,本课程有二个特点： （）定义、定理多。 本课内容定义定理例题 （）课外作业较多。,9,学习方法,为了学好这门课，特提出三点要求： （）弄懂定义、定理，弄懂例题，加深对定义、定理的理解； （）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。 （3）做好课堂笔记.,10,学习方法,最后，做两点说明： （1）考试内容以课堂上讲的为范围； （2）每次课后均布置作业。希望大家认真完成。 和一个要求： 为搞好教学，需要双方共同努力。,11,第一篇 数理逻辑,逻辑学:研究思维形式及思维规律的科学。 逻辑学分为二类 辩证逻辑:是研究事物发展的客观规律。 形式逻辑:对思维的形式结构和规律进 行研究。 数理逻辑：是用数学的方法研究概念、 判断和推理的科学，属于形式逻辑。,12,第一篇 数理逻辑,在数理逻辑中，用数学的方法是指引进一套符号体系的方法来研究概念、判断和推理。即对符号进行判断和推理。 数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础古典数理逻辑(命题逻辑和谓词逻辑)。,13,第一章 命题逻辑,1.1 命题 1.2 命题联结词 1.3 命题公式 1.4 等价式 1.5 永真蕴含式 1.6 其他命题联结词 1.7 范 式 1.8 推论理论,14,第一章 命题逻辑,教学目的及要求： 深刻理解和掌握命题逻辑中基本概念和基本方法。 教学内容： 命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、对偶与范式、推理理论。 教学重点： 命题逻辑中的基本概念和基本推理方法。 教学难点：推理理论。,15,1.1 命题,定义： 具有确定真假值的陈述句叫命题。 讨论定义： （1）命题可以是真的，或者是假的，但不能 同时为真又为假。 （2）命题分类： )原子命题（基本命题、本原命题）： 不能分解成为更简单的命题。 例：我是一位学生。,16,1.1 命题,)分子命题（复合命题）：若干个原子 命题使用适当的联结词所组成的新命题 例：我是一位学生和他是一位工人 （3）命题所用符号：常用大写个英文字母 表示命题。用、表示。 （4）命题中所有的“真”用“”表示， 命题中所有的“假”用“”表示。,17,1.1 命题,例：判断下列语句是否为命题。 陈述句一般为命题 （1）十是整数。 （） （2）上海是一个村庄。（） （3）今天下雨。 （4）加拿大是一个国家。（） （5）是偶数而是奇数。 （6）她不是护士。 （7） （8）今天是星期天。,18,1.1 命题,命令句，感叹句，疑问句均不是命题。 （1）把门关上！ （2）你到哪里去？ 语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。 （3）他正在说谎。 （在命题逻辑中不讨论这类问题）,19,1.2 命题联结词,在命题演算中也有类似的日常生活中的联结词称做： “命题联结词”,下面先介绍五个常用的命题联结词。 否定词：（否定运算、非运算） （）符号 ,读作“非”，“否定” 设命题为，则在的前面加否定词 ，变成，读做“的否定”或“非”,20,1.2 命题联结词,（）定义 P的真值表： （）举例： ：每一种生物均是动物。F ：有一些生物不是动物。T 这里不能讲成“每一种生物都不是动物”。 对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。,21,1.2 命题联结词,合取词（“合取”、“积”、“与”运算） (1)符号 “” 设，为两个命题，则称与的合 取，读作：“与”、“与的合取”、“并 且”等。 (2)定义（由真值表给出）：,22,1.2 命题联结词,的真值表 ：,23,1.2 命题联结词,当且仅当和的真值均为“”，则（） 的真值为“”。否则，其真值为“”。 注意：和是互为独立的；地位是平等的，和的位置可以交换而不会影响的结果。,24,1.2 命题联结词,(3)举例： (a) P：王华的成绩很好 Q：王华的品德很好。 则：王华的成绩很好并且品德很好。 (b)P：我们去种树 Q：房间里有一台电视机 则：我们去种树与房间里有一台电视机。,25,1.2 命题联结词,(c) P：今天下大雨 Q：3+3=6 则：今天下大雨和3+3=6 由例(b)(c)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。,26,1.2 命题联结词,(d)P: 王大和王二是亲兄弟。 Q: 他打开箱子然后拿出一件衣服来。 该语句不是合取联结词组成的命题。,27,1.2 命题联结词,析取词（或运算） （）符号“” 设、为二个命题，则（）称作与的“析取”，读作：“或”。 （）定义（由真值表给出）：,28,1.2 命题联结词,当且仅当、均为“”时，（）为“”。否则，其真值为“”,的真值表：,29,1.2 命题联结词,区分“可兼或”与“不可兼或（异或，排斥或）” “可兼或”即P或Q为“T”时（PQ）为“T” 例如： 灯泡有故障或开关有故障。 今晚写字或看书。 今天下雨或打雷。 以上例句均为可兼或。,30,1.2 命题联结词,“不可兼或”即P和Q的真值不同时，PQ为T。 （异或用“”表示）,PQ的真值表：,31,1.2 命题联结词,例： 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。 以上两句均为不“可兼或”。,32,1.2 命题联结词,单条件联结词：（“蕴含”联结词、蕴含词） （）符号“”，读作：“如果则”、“蕴含” 、为二个命题，（）为新的命题，读作：“如果则”，“蕴含”，“仅当”， “当且”，“是的充分条件”。 （）定义,33,1.2 命题联结词,的真值表：,34,1.2 命题联结词,当为“”，为“”时，则（）为“”， 否则（）均为“”。 ：称为前件、条件、前提、假设 ：称为后件、结论。 （）举例： P：我拿起一本书 Q：我一口气读完了这本书,35,1.2 命题联结词,PQ：如果我拿起一本书，则我一口气读完 了这本书。 (b) P：月亮出来了 Q：33=9 PQ：如果月亮出来了，则33=9。 通常称： (a)为形式条件命题前提和结果有某种形式 和内容上的联系。,36,1.2 命题联结词,(b)为实质条件命题前提和结果可以有联 系，也可以没有联系，只要满足单条件命 题的定义。 所以,是形式条件命题一定是实质条件命题,反 之不一定。“”是实质条件命题。 例：我买到了鱼；:我吃鱼。 ：如果我买到了鱼，则我吃鱼。 但“如果我没买到鱼，则我吃鱼”，在日常生活中不可能，但在单条件命题的定义中是允许的。,37,1.2 命题联结词,可以证明： Q P 原命题 逆反命题 逆命题 反命题,38,1.2 命题联结词,列出真值表,由真值表得： 原命题逆反命题；逆命题反命题。,39,1.2 命题联结词,P Q的真值表: 每当和的真值相同时，则（）的真值为“”，否则（ ）的真值为“”。,40,1.2 命题联结词,（）举例： （a）设 ：ABC是等腰三角形 ：ABC有两只角相等 ：ABC是等腰三角形当且仅当 有两只角相等。,41,1.2 命题联结词,（b）下面均为等价联结词： 春天来了当且仅当燕子飞回来了。 平面上二直线平行，当且仅当二直线不相交。 当且仅当雪是白色的。,42,1.2 命题联结词,（）,中，、的地位是平等的，、 交换位置不会改变真值表中的值。 （）当且仅当 仅当 当且 ,43,1.2 命题联结词,命题联结词在使用中的优先级 （）先括号内，后括号外 （）运算时联结词的优先次序为： （由高到低） （）联结词按从左到右的次序进行运算 （）最外层的括号一律均可省去 （）可写成,44,1.2 命题联结词,例 （）可省去括号 因为“”运算是可结合的。 而（）中的括号不能省去，因“”不满足结合律。,45,1.2 命题联结词,命题联结词小结： （1）五个联结词的含义与日常生活中的联结词 的含义大致相同。 （2）或”可分为可兼或（）和异或（ ） （不可兼或） （3） “”为一元运算，其余四个均为二元运算。,46,1.2 命题联结词,(4) “”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。 (5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。,47,1.2 命题联结词,以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。 步骤如下： 找出各简单命题，分别符号化。 找出各联结词，把简单命题逐个联结起来。,48,1.2 命题联结词,例. 将下列命题符号化： （1）李明是计算机系的学生，他住在312室或 313室。 （2）张三和李四是朋友。 （3）虽然交通堵塞，但是老王还是准时到达了 车站。 （4）只有一个角是直角的三角形才是直角三角 形。 （5）老王或小李中有一个去上海出差。,49,1.2 命题联结词,解： （1）首先用字母表示简单命题。 P：李明是计算机系的学生。 Q：李明住在312室。 R：李明住在313室。 该命题符号化为：P（QR） （2）张三和李四是朋友。是一个简单句 该命题符号化为：P,50,1.2 命题联结词,（3）首先用字母表示简单命题。 P：交通堵塞。 Q：老王准时到达了车站。 该命题符号化为：PQ （4）首先用字母表示简单命题。 P：三角形的一个角是直角。 Q：三角形是直角三角形。 该命题符号化为：P Q,51,1.2 命题联结词,（5）首先用字母表示简单命题。 P：老王去上海出差。 Q：小李去上海出差。 该命题符号化为：P Q 也可符号化为：（PQ）（PQ）或者 （P Q） （PQ）,52,1.3 命题公式,约定： （）我们只注意命题的真假值，而不再去注意命题的汉语意义。 （）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。,53,1.3 命题公式,命题公式 命题常元：表示确定的命题T，F。 命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母表示。 命题公式：由命题变元、常元、联结词、括号， 以规定的格式联结起来的字符串。,54,1.3 命题公式,定义命题公式(wff)可按下述法则来生成： ）单个的命题变元是一个命题公式。 ）若是命题公式，也为命题公式。 ）若、是命题公式，则（）、 （）、（）、（）均为 命题公式。 ）当且仅当有限次使用（）（）（）所得到的包含有命题变元和命题常元，联结词，括号的符号串 才是命题公式。,55,1.3 命题公式,例如：(PQ)，(P(QR)，(PQ)R)，P都是命题公式。而(P)，(P)都不是命题公式 命题公式的真值表 : 命题变元用特定的命题来取代，这一过程称为对该命题变元进行真值指派。 命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成(x),56,1.3 命题公式,例如：公式 P (Q R) 定义三元函数 Y(P，Q，R) P (Q R) 定义命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。,57,1.3 命题公式,构造真值表的步骤如下： 1)找出给定命题公式中所有的命题变元，列 出所有可能的赋值。 2)按照从低到高顺序写出命题公式的各层次。 3)对应每个赋值，计算命题公式各层次的值， 直到最后计算出整个命题公式的值。,58,1.3 命题公式,例构造命题公式（）的真值表：,59,1.3 命题公式,例写出命题公式 （）的真值表,60,1.3 命题公式,由上二例可见，个命题变元有组真值指派；个命题变元有23 组真值指派，个则有个2n个真值指派。,61,1.3 命题公式,命题公式的永真式、永假式和可满足式 定义设公式中有n个不同的原子变元 p1,pn,(n为正整数)。该变元组的任意一组确定的值（ u1,un）称为关于p1,pn的一个完全指派，其中ui或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于该变元组的部分指派。 定义使公式取真的指派称为成真指派。,62,1.3 命题公式,定义如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式。既不是永真式，又不是永假式，则称此命题公式是可满足式。 讨论： （）永真式的否定为永假式（）；永 假式的否定为永真式（）。 （）二个永真式的析取、合取、蕴含、等价 均为永真式。,63,1.4 等价式,等价式 定义如果对两个公式，不论作何种指派，它们真值均相同，则称，是逻辑等价的，亦说（）等价于（）,并记作：,64,1.4 等价式,例：,65,1.4 等价式,例：判断公式A：(PQ)(PQ)与 B：(PR)(PR)是否等价。 解：列该公式的真值表：,66,1.4 等价式,67,1.4 等价式,定理 命题公式的充要条件是为永真式。 说明： “”为等价关系符，表示和有等价关系。 不为命题公式 “”为等价联结词（运算符），、为命题公式，则（ ）也为一命题公式。,68,1.4 等价式,证明： （）充分性： 为永真式，即、有相同的真值，所以。 （）必要性：，即、有相同的真值表，所以 为永真式。 例：证明； ,69,1.4 等价式,由定理可知： 若，则 若，C，则,70,1.4 等价式,下面列出组等价公式 （1）双重否定律 （2）同等律 ； （3）交换律 ； ； （4）结合律 （）（）； （）（）； （） （）,71,1.4 等价式,（5）分配律 （）（）（）； （）（）（） （6）摩根律 （）； （） （7）吸收律 （） ； （） ,72,1.4 等价式,（8）蕴含律 （9）等价律 （）（） （10）零 律 ； （11）同一律 ； （12）互补律 ； （13）输出律 （）,73,1.4 等价式,（14）归缪律 （）（） （15）逆反律 说明： （）证明上述组等价公式的方法可用真值表法，把改为所得的命题公式为永真式，则成立。,74,1.4 等价式,（2） 、 均满足结合律， 则在单一用、 联结词组成的命题公式中，括号可以省去。 （3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。 例如：(PQ) (P Q)， (PQ) (RS) (P Q) (R S)， (PQ) R) (P Q) R),75,1.4 等价式,置换规则 定义给定一命题公式，其中P1、 P2Pn 是中的原子命题变元， 若（1）用某些命题公式代换中的一些原子命题变元Pi （2）用命题公式i代换Pi，则必须用i代换中的所有Pi 由此而得到的新的命题公式称为命题公式的代换实例,76,1.4 等价式,讨论定义： （）用命题公式只能代换原子命题变元，而不 能去代换分子命题公式 。 （）要用命题公式同时代换同一个原子命题变 元 。 （）永真式的代换实例仍为永真式；反之代换实 例为永真式时，则不能断定原公式也一定是 永真式。,77,1.4 等价式,例：为一永真式，若用任何命题公式代换，则仍为永真式 为一个可满足的命题公式，若用代换，则得（）为永真式，但（）并不是永真式。 （）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式,78,1.4 等价式,例 设：（Q）若用（）代换中的， 得：（）（Q（）是的代换实例， 而：（）（Q）不是B的代换实例。 例的代换实例有：（），（），（）等 所以，一个命题公式的代换实例有无限个。,79,1.4 等价式,下面讨论取代过程（置换规则）： 定义给定一命题公式，是的任何部分，若也是一命题公式，则称是的子命题公式。 例：（）（） 的子命题公式有：、（）、 （）、（）、（）（）等。,80,1.4 等价式,定理给定一命题公式，是的子公式。设B是一命题公式，若 B，并用B取代中的，从而生成一新的命题公式B，则B。 从定理可见：一个命题公式A，经多次取代，所得到的新公式与原公式等价。 例：证明：（）（） ,81,1.4 等价式,（） （） 例：证明： （）（）（）（）为一永真式,82,1.4 等价式,证明：原式： （）（）（）（） （）（）（）（） （）（）（）（）（） （）（）（）（） 它是（永真式）的代换实例，永真式的代换实例仍为永真式！,83,1.4 等价式,对偶原理（对偶定律） 定义给定二个命题公式和A* ，若用代换，用代换，用代换，用代换，其中一个命题公式由另一个命题公式得来，则称和A*是互为对偶的，而联结词和也是互为对偶的 例：写出下列命题公式的对偶式： （） （） 对偶式 A* ,84,1.4 等价式,讨论定义： （）若命题公式中有联结词，则必须把化成由联结词， ，组成的等价的命题公式，然后求它的对偶式； 例：求(PQ)(PR)的对偶式,85,1.4 等价式,（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。 例：（）对偶式写成 （），而不能写成,86,1.4 等价式,定理（摩根推广定理） 设和A*为对偶式P1,P2Pn 是出现在和A*中的所有原子命题变元，于是有： （P1，P2Pn） A* （P1，P2Pn）（1） （P1，P2Pn） A*（P1，P2Pn）（）,87,1.4 等价式,证明：由摩根定理 （）（） （）（） 不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。 例：设（，） （），验证上述定理：,88,1.4 等价式,证明： ()（，） （，） A*（，） A*（，） （）（ ，） A*（，）（ ） 有（ ， ， ） A*（，）,89,1.4 等价式,定理若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若，则A*B*成立。 证明：已知：、为任一命题公式，且，要证明A*B* 设：P1、P2Pn 是出现在和中的原子命题变元，,90,1.4 等价式,由， 即（P1，P2Pn） （P1，P2Pn） （P1，P2Pn） （P1，P2Pn） 由摩根推广定理 *（P1，P2Pn） *（P1，P2Pn）,91,1.4 等价式,*（P1，P2Pn） *（P1，P2Pn）为永真式 前面讲过永真式的代换实例仍为永真式，所以用 Pi代换A*和B*中的Pi （1in) 则得： *（ P1， P2 Pn） *（ P1， P2 Pn） 即为：*（P1，P2Pn） *（P1，P2Pn）,92,1.4 等价式,例：证明： （）（）（ ） （） （）（） （） （） 证明： （）左边(）（ ） （） （ ） （）（ ） （ ）,93,1.4 等价式,（）左边 （） （） （） （） （） 结论：（）和（）是互为对偶的。,94,1.5 永真蕴含式,定义命题公式称为永真蕴含命题公式，当且仅当 是一个永真式，记作： 说明：“ ”读作“永真蕴含”，“蕴含”，“能推得” “ ”是关系符， 不为命题公式。 例：证明： ； P （）列出真值表 证明：（）和（）为永真式,95,1.5 永真蕴含式,（）可用等价公式证： （） （） T （） （） T,96,1.5 永真蕴含式,定理设、是二个命题公式 的充分必要条件是 且 。 证明： 若，则为一永真式 由定律：（）（）（） （）且（）也为一永真式 即： 且成立 反之 且 则也成立 此定理把“”和“ ”之间建立了相应的关系。,97,1.5 永真蕴含式,下面给出常用的永真蕴含式 I1 （） I2 （ ） I3 （） I4 （） I5 （） I6 （）（） （） I7 （）（） （） I8 （）（） （） I9 P ,98,1.5 永真蕴含式,I10 I11 （） I12 （） I13 （）（）（） 证明上述永真蕴含式的方法有三种： （）把“ ”关系符改为“”联结词，证明它为永真式。 (a)真值表法 (b)命题演算法,99,1.5 永真蕴含式,（）找出使单条件命题前件为“”的所有真值指派，试看能否导致后件均为“”，若为“”，则永真蕴含关系成立。,100,1.5 永真蕴含式,例：（） 前件为“”的所有指派为、（）均为“”， 为“”，为“”，也应为“”， （） 成立 （）找出使单条件命题的后件均为“”的所有真值指派，试看前件的所有真值是否为“”，若是，则蕴含成立。,101,1.5 永真蕴含式,例：（） 后件为“”的所有条件是：为“”， 代入前件得 （）若为，则（）为“”； （）若为，则（）为“”； （） 成立 若后件简单则可选用(3)；若前件简单则可选用(2)。 二种方法是互为独立的，只需使用一种证明就行。,102,1.5 永真蕴含式,讨论一下永真式 可得出三个结论： （）若一个命题公式等价于一个永真式，则该公式一定为永真式。 （）若一个永真的命题公式永真蕴含一个命题公式，则此命题公式一定也为永真式。 （）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。,103,1.5 永真蕴含式,定理给定命题公式、， 若，且，则。 证明：，且， （）（）为永真式， 由I6：（）（） （）， （）也为永真式；即，成立,104,1.5 永真蕴含式,推论若B1 、B1 B2Bm ，则。 定理给定一个命题公式、，若,，则（） 证明： ， （）（）为永真式， 由条件，若一定为“”，则、均为“”， （）也为“”，结论：（）为“”。,105,1.5 永真蕴含式,上述也可用等价公式证明它： （）（） （）（ ） （） （）也为永真式 （）成立 定义设H1,H2.Hm,均为命题公式，若（H1H2 Hm ） ，则称 H1,H2.Hm,共同蕴含，并记作： H1,H2.Hm 。,106,1.5 永真蕴含式,定理若 （H1 H2Hm ）,P ， 则（H1 H2Hm ） （）。 证明：（H1 H2Hm P） （H1 H2Hm P）Q （ H1 H2 Hm ） （ P Q ） （H1 H2Hm ） （ P Q ） H1 H2 . Hm（）也为永真式 （ H1 ,H2 . Hm ）（）成立,107,1.6 其他联结词,其他命题联结词： (1)不可兼或（异或，异） (a)符号:(),读作“异或” (b)定义:（由真值表） (c)异或的性质： （）（ ） （）（ ） （） ()(),108,1.6 其他联结词,（）（） （） （对 可分配的） 若 ，则有： ， ,109,1.6 其他联结词,()“与非”联结词： (a)符号,读作“与的否定”或“与非” (b)定义：（由真值表） （）（）,110,1.6 其他联结词,(c)性质： （）（） （） （）（）（） （）（）（） （）（） 不可结合 （）（） 不可结合 ，,111,1.6 其他联结词,()“或非”联结词： (a)符号：“” （）读作：“或的否定”或 “或非” (b)定义（由真值表给出）： （） （）,112,1.6 其他联结词,(c)性质： （可交换的） （）（） （）（） （）（） 不可结合 （）（） 不可结合 ； (d)由（）和（）中的性质可见，和是互为对偶的。,113,1.6 其他联结词,(4)“ 蕴含否定”联结词： (a)符号： (b)定义(由真值表给出）： P Q (PQ),“”,c,c,c,114,1.6 其他联结词,()不同真值表的命题公式： 按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表： (a)若命题变元只有一个，则用联结词组成的命题公式由四种不同的真值表，即为：,115,1.6 其他联结词,所有依赖于的命题公式均等价于这四个中的一个 (b)若有二个命题变元、，则命题公式的不同真值表有：222=24=16种。 推广到一般：若有个变元的命题公式，则可构成不同的真值表为22n（个）。,116,1.6 其他联结词,（）二元运算中的全部联结词总结： 、 是五个基本联结词。 到此为止，一个符号系统已定义完毕，它们是： 命题变元 :、 值 :、 运算符 :、 、 括号 :（） 关系符 : 、,。,C,117,1.6 其他联结词,全功能联结词集合： 定义一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出来，则称此联结词集合为全功能联结词集合。 定义设有一联结词集合，若 （）用中的联结词的等价式能表达任何的一个命题公式； （）删除中的任一联结词，从而形成一个新的联结词集合，至少有一个命题公式不能用中的联结词的等价式来表示，则称A为最小的全功能联结词集合。,118,1.6 其他联结词,我们可以证明：，；，；，；均为全功能联结词集合，且均是最小的全功能联结词集合。 例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：,119,1.6 其他联结词,（） ， （） （ ） ， （） ， ( ) ， （ ） （）（） （ ） （ ） （） ,c,c,120,1.7 范式,如何判定命题公式为永真式、永假式和可满足式或二个命题公式等价，归纳有三种方法： （1）真值表法：对于变元的所有真值指 派，看对应命题公式的真值。 （2）命题演算方法：化简命题公式至最简式，看是否存在和 （）、（）等价，若不则为可满足的。 （3）范式方法：本节就介绍此法。,121,1.7 范式,什么叫范式 把命题公式化归为一种标准的形式，称此标准形式为范式。 什么叫判定 以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。 讨论范式和主范式的目的就是为了进行判定。,122,1.7 范式,析取范式和合取范式： 设命题变元为：、，则：（）的析取式称为“和”；（）的合取式称为“积”。 定义命题公式的变元和变元的否定之积称为基本积，而变元和变元的否定之和称为基本和。,123,1.7 范式,例：设、为二个命题变元，则：， ， 称为基本和；， ， ， 称为基本积。 若“基本和”或“基本积”中的子公式”，称为此基本积 （和）的因子。 例： 的因子有： 、 、 ,124,1.7 范式,定理一个基本积必定是永假式，它的充分必要条件是，它至少包含一对因子,其中一个是另一个的否定。 证明： （）充分条件：、为基本积中一对因子该 基本积一定为永假式。 （）（）（） （）必要条件：基本积为永假式基本积中包含、这对因子。,125,1.7 范式,反证法：假设基本积中不包含、这样的因子，且为永假式。若给基本积中的命题变元指派“”，而命题变元的否定指派为“”， 在基本积中不包含、这对因子， 基本积得到的真值为“”，这和假设相矛盾； 基本积中必然包含、这对因子才能使基本积为“”。,126,1.7 范式,定理一个“基本和”必定为永真式，其充要条件（当且仅当）是，它至少包含一对因子，其中一个是另一个的否定。 定义与给定命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题公式的析取范式。并记为：PP1 P2 Pn（nI+）。其中P1，P2Pn均为基本积。 方法可按下列三步（或四步）进行：,127,1.7 范式,（）利用等价公式：化去“”、“”联结词，把命题公式变为与其等价的用，表达的公式。 例: ， （）（） （）（） （）将“”深入到原子命题变元之前，并使变元之前最多只有一个“”词。 例：（） ,128,1.7 范式,（）利用“”对“”的分配，将公式化为析取范式。 （）除去永假项得最简析取范式。 例：求（）（）的析取范式： 解：原式 (（） （）) (（） （）),129,1.7 范式,( （） （）) ( （） （）) -（1）化去词 （ ）（）（ ） -（2）将“”深入到变元前面，并最多保留一个 （ ）（ ）（ ）（ ）（ ） -（3）“”对或“”的分配，化成为析取范式 （）（） -（4）最简析取范式,130,1.7 范式,讨论定义： （）从上例看出，一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。 （）若一个命题公式的析取范式中每一个基本积均为永假式，则该公式也一定为永假式。 即PP1P2Pn（P1，P2Pn均为基本积） 则当P1P2 Pn F时，一定为永假式。 (可用来判定是否为永假式),131,1.7 范式,例：（析取范式） （ ）（ ） 永假式 定义与给定命题公式等价的一个公式，如果它是由基本和之积所组成，则称它是给定命题公式的合取范式。 并表示成： Q Q1 Q2 Qn，(nI+),其中Q!,Q2,Qn均为基本和。,132,1.7 范式,求一个命题公式的合取范式的方法和求析取范式的方法类同： 第（）、（）步相同； 第（）利用“”对“”的分配就行； 第（）去掉永真的析取项。,133,1.7 范式,例：求（）（）的合取范式 原式 （）（） 化去“”词 （ ）（ ） “”深入到变元前，并最多保留一个 （）（ ）（ ） “”对“”的分配 （ ）（ ）（ ）（ ） （最简合取范式）,134,1.7 范式,讨论定义： （）给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。 （）若一个命题公式的合取范式中的各基本和的真值为“”，则该命题公式一定是永真式。 (可用来判定是否为永真式) 例: ）（）（）,135,1.7 范式,主析取范式。 定义在个变元的基本积中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为极小项。 例:对二个命题变元讲,极小项有22=4个,即、 、 对一个命题变元讲,极小项有21=2个,即:、,136,1.7 范式,对三个命题变元讲，极小项有23=8个， 即：、 、 、 推广到一般：个命题变元构成的不同极小项有2n个（nI+）。使得每个极小项为真的赋值仅有一个。,137,1.7 范式,定义对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的主析取范式。 定理在真值表中，一个公式的真值为的指派所对应的极小项的析取，即为此公式的主析取范式。,138,1.7 范式,例：求出、 （）、的主析取范式,139,1.7 范式,则可直接写出各命题公式的主析取范式： （ ）（ ）（） （）（）（） （）（）（）（） （） 讨论此定理：,140,1.7 范式,（1）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“”的行，对应写出极小项的析取式，且一定是唯一的。 （2）若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2n个极小项。 （3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。 （4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“”的个数。,141,1.7 范式,下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步： （）将命题公式化归为与其等价的析取范式； （）除去永假项，合并基本积中相同项（例：），变为最简析取范式。 （）利用添变元的方法，将所有基本积变为极小项。,142,1.7 范式,例：二个变元、，利用“”对或“”的分配添项 （） （）（） （） （）（） （）合并相同的极小项变为一项。 例：求（）的主析取范式 解：原式（）（） -（1）化为析取范式,143,1.7 范式, （） -（2）消去永假项，变为最简析取范式 （）（） （）（）（） -（3）添项 （）（） -（4）合并相同最小项,144,1.7 范式,例：证明（） 证明方法是写出二命题公式的主析范式，看其是否相同： （）（） （）（）（） 而 （）（） （）（）（）（） （）（）（） 主析范式相同，有（） ,145,1.7 范式,主合取范式 定义在个变元的基本和中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种基本和为极大项。 例：有二个变元