离散数学教案.pptx

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