离散数学教案－金锄头文库

资源描述

《离散数学教案》由会员分享，可在线阅读，更多相关《离散数学教案（647页珍藏版）》请在金锄头文库上搜索。

1、离散数学离散数学教案教案课程编号：课程编号：0946401509464015 课程学分：课程学分：4 4 课程学时：课程学时：6464 讲授：叶红讲授：叶红1课程性质离散数学离散数学（又称计算机数学计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。2课程目标离散数学离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。3与其他课程的关系离散数学离散数学与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切

2、的联系。它是这些课程的先导和基础课程。4n离散数学q上海科学技术文献出版社，1982n左孝凌等编著nDiscrete Mathematical Structures（Fourth Edition）qHigher Education Press，2001nBernard Kolman，Robert C.Busby，Sharon Cutler Ross教材与参考书5课程内容本课程根据大纲的内容和相关独立性，可分为四大部分第一部分数理逻辑数理逻辑包括命题逻辑;谓词逻辑第二部分集合论集合论包括集合与关系;函数 6课程内容第三部分代数系统代数系统包括代数结构;格与布尔代数第四部分图

3、论图论讲课时数：62学时7学习方法本课程有二个特点：（）定义、定理多。本课内容定义定义定理定理例题例题（）课外作业较多。8学习方法为了学好这门课，特提出三点要求：（）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；（）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。（3）做好课堂笔记.9学习方法最后，做两点说明：（1）考试内容以课堂上讲的为范围；（2）每次课后均布置作业。希望大家认真完成。和一个要求：为搞好教学，需要双方共同努力。10第一篇数理逻辑逻辑学逻辑学:研究思维形式及思维规律的科学。逻辑学分为二类辩证逻辑辩证逻辑:是研究事物发展的客观规律。形式逻辑

4、形式逻辑:对思维的形式结构和规律进行研究。数理逻辑数理逻辑：是用数学的方法研究概念、判断和推理的科学，属于形式逻辑。11第一篇数理逻辑在数理逻辑中，用数学的方法是指引进一套符号体系的方法来研究概念、判断和推理。即对符号进行判断和推理。数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础古典数理逻辑(命题逻辑和谓词逻辑)。12第一章命题逻辑1.1 命题1.2 命题联结词1.3 命题公式1.4 等价式1.5 永真蕴含式1.6 其他命题联结词1.7 范式 1.8 推论理论13第一章命题逻辑教学目的及要求：教学目的及要求：深刻理解和掌握命题逻

5、辑中基本概念和基本方法。教学内容：教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、对偶与范式、推理理论。教学重点：教学重点：命题逻辑中的基本概念和基本推理方法。教学难点：教学难点：推理理论。141.1 命题定义：定义：具有确定真假值的陈述句叫命题。讨论定义：（1）命题可以是真的，或者是假的，但不能同时为真又为假。（2）命题分类： )原子命题原子命题（基本命题、本原命题）：不能分解成为更简单的命题。例：我是一位学生。151.1 命题 )分子命题分子命题（复合命题）：若干个原子命题使用适当的联结词所组成的新命题例：我是一位学生和他是一位工

6、人（3）命题所用符号：常用大写个英文字母表示命题。用、表示。（4）命题中所有的“真”用“”表示，命题中所有的“假”用“”表示。161.1 命题例例：判断下列语句是否为命题。陈述句一般为命题（1）十是整数。（）（2）上海是一个村庄。（）（3）今天下雨。（4）加拿大是一个国家。（）（5）是偶数而是奇数。（6）她不是护士。（7）（8）今天是星期天。171.1 命题命令句，感叹句，疑问句均不是命题。（1）把门关上！（2）你到哪里去？语句既为真，同时又包含假的不是命题，这样的句子称为“悖论悖论”。（3）他正在说谎。（在命题逻辑中不讨论这类问题）181.2 命题联结词在命题演算中也有类似的

7、日常生活中的联结词称做： “命题联结词”,下面先介绍五个常用的命题联结词。否定词：否定词：（否定运算、非运算）（）符号 , ,读作“非”，“否定” 设命题为，则在的前面加否定词，变成，读做“的否定”或“非”191.2 命题联结词（）定义 P的真值表：（）举例：：每一种生物均是动物。F ：有一些生物不是动物。T 这里不能讲成“每一种生物都不是动物”。对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。TFFT PP201.2 命题联结词合取词合取词（“合取”、“积”、“与”运算） (1)符号“” 设，为两个命题，则称与的合取，读作：“与”、“与的合取”、“并且”等。

8、(2)定义（由真值表给出）：211.2 命题联结词TTTTFFFTFFTFFFFFQPP QQP的真值表：221.2 命题联结词当且仅当和的真值均为“”，则（）的真值为“”。否则，其真值为“”。注意注意：和是互为独立的；地位是平等的，和的位置可以交换而不会影响的结果。231.2 命题联结词(3)举例： (a) P：王华的成绩很好 Q：王华的品德很好。则：王华的成绩很好并且品德很好。 (b)P：我们去种树 Q：房间里有一台电视机则：我们去种树与房间里有一台电视机。241.2 命题联结词 (c) P：今天下大雨 Q：3+3=6 则：今天下大雨和3+3=6由例(b)(c)可见，在日常生活中，

9、合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。251.2 命题联结词 (d)P: 王大和王二是亲兄弟。 Q: 他打开箱子然后拿出一件衣服来。该语句不是合取联结词组成的命题。 261.2 命题联结词析取词析取词（或运算）（）符号“” 设、为二个命题，则（）称作与的“析取”，读作：“或”。（）定义（由真值表给出）：271.2 命题联结词当且仅当、均为“”时，（）为“”。否则，其真值为“”TTTTFTTTFFFFP QQP的真值表：281.2 命题联结词区分“可兼或”与“不可兼或（异或，排斥或）” “可兼或”即P或Q为“T”时（PQ）为“T” 例如：灯

10、泡有故障或开关有故障。今晚写字或看书。今天下雨或打雷。以上例句均为可兼或。291.2 命题联结词“不可兼或”即P和Q的真值不同时，PQ为T。（异或用“”表示）FTTTFTTTFFFFPQQPPQ的真值表：301.2 命题联结词例：他通过电视看杂技或或到剧场看杂技。他乘火车去北京或或乘飞机去北京。以上两句均为不“可兼或”。311.2 命题联结词单条件联结词：单条件联结词：（“蕴含”联结词、蕴含词）（）符号“”，读作：“如果则”、“蕴含” 、为二个命题，（）为新的命题，读作：“如果则”，“蕴含”，“仅当”， “当且”，“是的充分条件”。（）定义 321.2 命题联结词的真值表： T

11、TTFFTTTFTFFPQQP331.2 命题联结词当为“”，为“”时，则（）为“”，否则（）均为“”。：称为前件、条件、前提、假设：称为后件、结论。（）举例： P：我拿起一本书 Q：我一口气读完了这本书 341.2 命题联结词 PQ：如果我拿起一本书，则我一口气读完了这本书。(b) P：月亮出来了 Q：33=9 PQ：如果月亮出来了，则33=9。通常称： (a)为形式条件命题前提和结果有某种形式和内容上的联系。351.2 命题联结词 (b)为实质条件命题前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。所以,是形式条件命题一定是实质条件命题,反之不一定。“”是

12、实质条件命题。例：我买到了鱼；:我吃鱼。：如果我买到了鱼，则我吃鱼。但“如果我没买到鱼，则我吃鱼”，在日常生活中不可能，但在单条件命题的定义中是允许的。 361.2 命题联结词可以证明： Q P P 原命题逆反命题逆命题反命题371.2 命题联结词列出真值表,由真值表得：原命题逆反命题；逆命题反命题。 TTTTTTTTFFFTFFTTTFTTTTFFP QP PQQP381.2 命题联结词P Q的真值表:每当和的真值相同时，则（）的真值为“”，否则（）的真值为“”。 TTTFFTFTFTFFP QQP391.2 命题联结词（）举例：（a）设：ABC是等腰三角形：ABC有两只角

13、相等：ABC是等腰三角形当且仅当有两只角相等。401.2 命题联结词（b）下面均为等价联结词：春天来了当且仅当燕子飞回来了。平面上二直线平行，当且仅当二直线不相交。当且仅当雪是白色的。411.2 命题联结词（）,中，、的地位是平等的，、交换位置不会改变真值表中的值。（）当且仅当仅当当且421.2 命题联结词命题联结词在使用中的优先级命题联结词在使用中的优先级（）先括号内，后括号外（）运算时联结词的优先次序为：（由高到低）（）联结词按从左到右的次序进行运算（）最外层的括号一律均可省去（）可写成431.2 命题联结词例（）可省去括号因为“”运算是可结合的。而（）中的

14、括号不能省去，因“”不满足结合律。 441.2 命题联结词命题联结词小结：命题联结词小结：（1）五个联结词的含义与日常生活中的联结词的含义大致相同。（2）或”可分为可兼或（）和异或（）（不可兼或）（3） “”为一元运算，其余四个均为二元运算。451.2 命题联结词(4) “”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。461.2 命题联结词以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算

15、，为此，首先要把推理所涉及到的各命题符号化。步骤如下：找出各简单命题，分别符号化。找出各联结词，把简单命题逐个联结起来。471.2 命题联结词例. 将下列命题符号化：（1）李明是计算机系的学生，他住在312室或 313室。（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了车站。（4）只有一个角是直角的三角形才是直角三角形。（5）老王或小李中有一个去上海出差。481.2 命题联结词解：（1）首先用字母表示简单命题。 P：李明是计算机系的学生。 Q：李明住在312室。 R：李明住在313室。该命题符号化为：P（QR）（2）张三和李四是朋友。是一个简单句该命题符号化为：P

16、491.2 命题联结词（3）首先用字母表示简单命题。 P：交通堵塞。 Q：老王准时到达了车站。该命题符号化为：PQ（4）首先用字母表示简单命题。 P：三角形的一个角是直角。 Q：三角形是直角三角形。该命题符号化为：P Q501.2 命题联结词（5）首先用字母表示简单命题。 P：老王去上海出差。 Q：小李去上海出差。该命题符号化为：P Q 也可符号化为：（PQ）（PQ）或者（P Q）（PQ）511.3 命题公式约定：约定：（）我们只注意命题的真假值，而不再去注意命题的汉语意义。（）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。521.3 命题公式命题公式命题公式

17、命题常元：命题常元：表示确定的命题T，F。命题变元：命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母表示。命题公式命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。531.3 命题公式定义定义命题公式(wff)可按下述法则来生成：）单个的命题变元是一个命题公式。）若是命题公式，也为命题公式。）若、是命题公式，则（）、（）、（）、（）均为命题公式。）当且仅当有限次使用（）（）（）所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。 541.3 命题公式例如：(PQ)，(P(QR)，(PQ)R)，P都是命题公式。而(P)，

18、(P)都不是命题公式命题公式的真值表命题公式的真值表 :命题变元用特定的命题来取代，这一过程称为对该命题变元进行真值指派。指派。命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成(x)551.3 命题公式例如：公式 P (Q R) 定义三元函数 Y(P，Q，R) P (Q R) 定义定义命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。561.3 命题公式构造真值表的步骤如下： 1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。 2)按照从低到高顺序写出命题公式的各层次。 3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。57

19、1.3 命题公式FTTTTFTTFTTFTTFTFFFF（）（）P QQP例构造命题公式（）的真值表：581.3 命题公式例写出命题公式（）的真值表 T TTT T FTT T TFT T FFT T TTF F FTF F TFF F FFF（)RQP591.3 命题公式由上二例可见，个命题变元有组真值指派；个命题变元有23 组真值指派，个则有个2n个真值指派。601.3 命题公式命题公式的永真式、永假式和可满足式命题公式的永真式、永假式和可满足式定义定义设公式中有n个不同的原子变元 p1,pn,(n为正整数)。该变元组的任意一组确定的值（ u1,un）称为关于p1,pn的一个完全指派完

20、全指派，其中ui或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于该变元组的部分指派部分指派。定义定义使公式取真的指派称为成真指派成真指派。611.3 命题公式定义如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式永真式。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式永假式。既不是永真式，又不是永假式，则称此命题公式是可满足式。可满足式。讨论：（）永真式的否定为永假式（）；永假式的否定为永真式（）。（）二个永真式的析取、合取、蕴含、等价均为永真式。621.4 等价式等价式等价式定义定义如果对两个公式，不论作何种指

21、派，它们真值均相同，则称，是逻辑等价的，亦说（）等价于（）,并记作：631.4 等价式例：TTT TTTT FTTF TTTF F Q QPPP Q 641.4 等价式例：判断公式A：(PQ)(PQ)与 B：(PR)(PR)是否等价。解：列该公式的真值表：651.4 等价式FFFTTFTTFFFFFTFFFTTTFFFFFTTTFFFTFFFTFFTFFTTFTTTTTTTTFFTTTTTFTTTTFTTTTTTTTFFTTTTTTFTTFTTTBAPRPRRPQPQQRQP661.4 等价式定理定理命题公式的充要条件是为永真式。说明： “”为等价关系符，表示和有等价关系。不为命题公式 “

22、”为等价联结词（运算符），、为命题公式，则（）也为一命题公式。 671.4 等价式证明：（）充分性：为永真式，即、有相同的真值，所以。（）必要性：，即、有相同的真值表，所以为永真式。例：证明； 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，则691.4 等价式下面列出组等价公式（1）双重否定律双重否定律（2）同等律同等律；（3）交换律交换律；；（4）结合律结合律（）（）；（）（）；（）（）701.4 等价式（5）分配律分配律（）（）（）；

23、（）（）（）（6）摩根律摩根律（）；（）（7）吸收律吸收律（）；（） 711.4 等价式（8）蕴含律蕴含律（9）等价律等价律（）（）（10）零律零律；（11）同一律同一律；（12）互补律互补律；（13）输出律输出律（）721.4 等价式（14）归缪律归缪律（）（）（15）逆反律逆反律说明：（）证明上述组等价公式的方法可用真值表法，把改为所得的命题公式为永真式，则成立。731.4 等价式（2）、均满足结合律，则在单一用、联结词组成的命题公式中，括号可以省去。（3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。例如：(PQ) (P Q)， (PQ) (RS)

24、 (P Q) (R S)， (PQ) R) (P Q) R)741.4 等价式置换规则置换规则定义给定一命题公式，其中P1、 P2Pn 是中的原子命题变元，若（1）用某些命题公式代换中的一些原子命题变元Pi （2）用命题公式i代换Pi，则必须用i代换中的所有Pi由此而得到的新的命题公式称为命题公式的代代换实例换实例751.4 等价式讨论定义：讨论定义：（）用命题公式只能代换原子命题变元，而不能去代换分子命题公式。（）要用命题公式同时代换同一个原子命题变元。（）永真式的代换实例仍为永真式；反之代换实例为永真式时，则不能断定原公式也一定是永真式。761.4 等价式例：为一永真式，若用任

25、何命题公式代换，则仍为永真式为一个可满足的命题公式，若用代换，则得（）为永真式，但（）并不是永真式。（）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式 771.4 等价式例设：（Q）若用（）代换中的，得：（）（Q（）是的代换实例，而：（）（Q）不是B的代换实例。例的代换实例有：（），（），（）等所以，一个命题公式的代换实例有无限个。781.4 等价式下面讨论取代过程（置换规则）：定义给定一命题公式，是的任何部分，若也是一命题公式，则称是的子命题子命题公式公式。例：（）（）的子命题公式有：、（）、（）、（）、（）（）等。791.4 等价式定理给定一命题公式，是的子公式。设B是

26、一命题公式，若 B，并用B取代中的，从而生成一新的命题公式B，则B。从定理可见：一个命题公式A，经多次取代，所得到的新公式与原公式等价。例：证明：（）（） 801.4 等价式（）（）例：证明：（）（）（）（）为一永真式811.4 等价式证明：原式：（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）它是它是（永真式）的代换实例，永真式的代（永真式）的代换实例，永真式的代换实例仍为永真式！换实例仍为永真式！821.4 等价式对偶原理（对偶定律）对偶原理（对偶定律）定义定义给定二个命题公式和A* ，若用代换，用代换，用代换，用代换，其中一个命题公式由另一个命题公式得来，

27、则称和A*是互为对偶的，而联结词和也是互为对偶的例：写出下列命题公式的对偶式：（）（）对偶式 A* 831.4 等价式讨论定义：（）若命题公式中有联结词，则必须把化成由联结词，，组成的等价的命题公式，然后求它的对偶式；例：求(PQ)(PR)的对偶式841.4 等价式（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。例：（）对偶式写成（），而不能写成851.4 等价式定理（摩根推广定理）设和A*为对偶式P1,P2Pn 是出现在和A*中的所有原子命题变元，于是有：（P1，P2Pn） A* （P1，P2Pn）（1）（P1，P2Pn） A*

28、（P1，P2Pn）（）861.4 等价式证明：由摩根定理（）（）（）（）不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。例：设（，）（），验证上述定理：871.4 等价式证明：()（，）（，） A*（，） A*（，）（）（，） A*（，）（）有（，，） A*（，）881.4 等价式定理若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若，则A*B*成立。证明：已知：、为任一命题公式，且，要证明A*B*设：P1、P2Pn 是出现在和中的原子命题变元， 891.4 等价式由，即（P1，P2Pn）（P1，P2Pn）（P1，P2Pn）（P1，P

29、2Pn）由摩根推广定理*（P1，P2Pn） *（P1，P2Pn）901.4 等价式*（P1，P2Pn） *（P1，P2Pn）为永真式前面讲过永真式的代换实例仍为永真式，所以用 Pi代换A*和B*中的Pi （1in)则得： *（ P1， P2 Pn） *（ P1， P2 Pn）即为：*（P1，P2Pn） *（P1，P2Pn）911.4 等价式例：证明：（）（）（）（）（）（）（）（）证明：（）左边(）（）（）（）（）（）（）921.4 等价式（）左边（）（）（）（）（）结论：（）和（）是互为对偶的。931.5 永真蕴含式永真蕴含式定义命题公式称为永真蕴含命题

30、公式，当且仅当是一个永真式，记作：说明：“ ”读作“永真蕴含”，“蕴含”，“能推得” “ ”是关系符，不为命题公式。例：证明：； P （）列出真值表证明：（）和（）为永真式941.5 永真蕴含式永真蕴含式（）可用等价公式证：（）（） T（）（） TT T TT T T T TF T TT T TF TF T FF T TTFF T FF T FFF（）（）QP951.5 永真蕴含式永真蕴含式定理定理设、是二个命题公式的充分必要条件是且。证明：若，则为一永真式由定律：（）（）（）（）且（）也为一永真式即：且成立反之且则也成立此定理把“”和“ ”之间建立了相应的关系。961

31、.5 永真蕴含式永真蕴含式下面给出常用的永真蕴含式 I1 （）I2 （）I3（） I4 （） I5 （） I6 （）（）（） I7 （）（）（）I8 （）（）（）I9 P 971.5 永真蕴含式永真蕴含式I10 I11 （） I12 （） I13 （）（）（）证明上述永真蕴含式的方法有三种：（）把“ ”关系符改为“”联结词，证明它为永真式。 (a)真值表法 (b)命题演算法981.5 永真蕴含式永真蕴含式（）找出使单条件命题前件为“”的所有真值指派，试看能否导致后件均为“”，若为“”，则永真蕴含关系成立。TTTFFTTTFTFFPQQP991.5 永真蕴含式永真蕴含式例：（）前件

32、为“”的所有指派为、（）均为“”，为“”，为“”，也应为“”，（）成立（）找出使单条件命题的后件均为“”的所有真值指派，试看前件的所有真值是否为“”，若是，则蕴含成立。1001.5 永真蕴含式永真蕴含式例：（）后件为“”的所有条件是：为“”，代入前件得（）若为，则（）为“”；（）若为，则（）为“”；（）成立若后件简单则可选用(3)；若前件简单则可选用(2)。二种方法是互为独立的，只需使用一种证明就行。1011.5 永真蕴含式永真蕴含式讨论一下永真式可得出三个结论：（）若一个命题公式等价于一个永真式，则该公式一定为永真式。（）若一个永真的命题公式永真蕴含一个命题公式，则

33、此命题公式一定也为永真式。（）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。 1021.5 永真蕴含式永真蕴含式定理给定命题公式、，若，且，则。证明：，且，（）（）为永真式，由I6：（）（）（），（）也为永真式；即，成立1031.5 永真蕴含式永真蕴含式推论推论若B1、B1 B2Bm ，则。定理定理给定一个命题公式、，若,，则（）证明：，（）（）为永真式，由条件，若一定为“”，则、均为“”，（）也为“”，结论：（）为“”。1041.5 永真蕴含式永真蕴含式上述也可用等价公式证明它：（）（）（）（）（）（）也为永真式（）成立定义定义设

34、H1,H2.Hm,均为命题公式，若（H1H2 Hm ），则称 H1,H2.Hm,共同蕴含，并记作： H1,H2.Hm 。 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 ）（）成立 1061.6 其他联结词联结词其他命题联结词：其他命题联结词： (1)不可兼或（异或，异）(a)符号:(),读作“异或” (b)定义:（由真值表）(c)异或的性

35、质：（）（）（）（）（） ()() FTTTFTTTFFFFP QQP1071.6 其他联结词联结词（）（）（）（对可分配的）若，则有：， 1081.6 其他联结词联结词()“与非”联结词：(a)符号,读作“与的否定”或“与非”(b)定义：（由真值表）（）（）FTTTFTTTFTFFP QQP1091.6 其他联结词联结词(c)性质：（）（）（）（）（）（）（）（）（）（）（）不可结合（）（）不可结合，1101.6 其他联结词联结词()“或非”联结词：(a)符号：“” （）读作：“或的否定”或 “或非” (b)定义（由真值表给出）：（）（）FTTFFTFTFTF

36、FQP1111.6 其他联结词联结词(c)性质：（可交换的）（）（）（）（）（）（）不可结合（）（）不可结合；(d)由（）和（）中的性质可见，和是互为对偶的。 1121.6 其他联结词联结词(4)“ 蕴含否定”联结词：(a)符号：(b)定义(由真值表给出）：P Q (PQ)“” cFFFFTFTFTFTTP QQPcc1131.6 其他联结词联结词()不同真值表的命题公式：按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表：(a)若命题变元只有一个，则用联结词组成的命题公式由四种不同的真值表，即为：TFTFTTTFFF3210P1141.6 其他联

37、结词联结词所有依赖于的命题公式均等价于这四个中的一个 (b)若有二个命题变元、，则命题公式的不同真值表有：222=24=16种。推广到一般：若有个变元的命题公式，则可构成不同的真值表为22n（个）。 1151.6 其他联结词联结词（）二元运算中的全部联结词总结：（）二元运算中的全部联结词总结：、是五个基本联结词。到此为止，一个符号系统已定义完毕，它们是：命题变元 :、值 :、运算符 :、、括号 :（）关系符 : 、。C1161.6 其他联结词联结词全功能联结词集合：全功能联结词集合：定义一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出来，则称此联结词集合为全功

38、能联结词集合全功能联结词集合。定义设有一联结词集合，若（）用中的联结词的等价式能表达任何的一个命题公式；（）删除中的任一联结词，从而形成一个新的联结词集合，至少有一个命题公式不能用中的联结词的等价式来表示，则称A为最小的最小的全功能联结词集合全功能联结词集合。 1171.6 其他联结词联结词我们可以证明：，；，；，；均为全功能联结词集合，且均是最小的全功能联结词集合。例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：1181.6 其他联结词联结词（），（）（），（）， () ，（）（）（）（）（）（） cc1191.7 范式范式如何判定命题公式为

39、永真式、永假式和可满足式或二个命题公式等价，归纳有三种方法：（1）真值表法：对于变元的所有真值指派，看对应命题公式的真值。（2）命题演算方法：化简命题公式至最简式，看是否存在和（）、（）等价，若不则为可满足的。（3）范式方法：本节就介绍此法。1201.7 范式范式什么叫范式把命题公式化归为一种标准的形式，称此标准形式为范式。什么叫判定以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。讨论范式和主范式的目的就是为了进行判定。1211.7 范式范式析取范式和合取范式：析取范式和合取范式：设命题变元为：、，则：（）的析

40、取式称为“和”；（）的合取式称为“积”。定义定义命题公式的变元和变元的否定之积称为基本基本积积，而变元和变元的否定之和称为基本和基本和。1221.7 范式范式例：设、为二个命题变元，则：，，称为基本和；，，，称为基本积。若“基本和”或“基本积”中的子公式”，称为此基本积（和）的因子因子。例：的因子有：、、 1231.7 范式范式定理定理一个基本积必定是永假式，它的充分必要条件是，它至少包含一对因子,其中一个是另一个的否定。证明：（）充分条件：、为基本积中一对因子该基本积一定为永假式。（）（）（）（）必要条件：基本积为永假式基本积中包含、这对因子。1241.7 范式范

41、式反证法：假设基本积中不包含、这样的因子，且为永假式。若给基本积中的命题变元指派“”，而命题变元的否定指派为“”，在基本积中不包含、这对因子，基本积得到的真值为“”，这和假设相矛盾；基本积中必然包含、这对因子才能使基本积为“”。1251.7 范式范式定理定理一个“基本和”必定为永真式，其充要条件（当且仅当）是，它至少包含一对因子，其中一个是另一个的否定。定义定义与给定命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题公式的析取范式析取范式。并记为：PP1 P2 Pn（nI+）。其中P1，P2Pn均为基本积。方法可按下列三步（或四步）进行： 1261.7 范式范式（）利用等价公式

42、：化去“”、“”联结词，把命题公式变为与其等价的用，表达的公式。例: ，（）（）（）（）（）将“”深入到原子命题变元之前，并使变元之前最多只有一个“”词。例：（） 1271.7 范式范式（）利用“”对“”的分配，将公式化为析取范式。（）除去永假项得最简析取范式。例：求（）（）的析取范式：解：原式 (（）（）) (（）（）)1281.7 范式范式( （）（）) ( （）（）) -（1）化去化去词词（）（）（）-（2）将将“”深入到变元前面，并最多保留一深入到变元前面，并最多保留一个个（）（）（）（）（）-（3）“”对或对或“”的分配，化成为析取的分配，化成为析取

43、范式范式（）（） -（4）最简析取范式）最简析取范式1291.7 范式范式讨论定义：（）从上例看出，一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。（）若一个命题公式的析取范式中每一个基本积均为永假式，则该公式也一定为永假式。即PP1P2Pn（P1，P2Pn均为基本积）则当P1P2 Pn F时，一定为永假式。(可用来判定是否为永假式)1301.7 范式范式例：（析取范式）（）（）永假式定义定义与给定命题公式等价的一个公式，如果它是由基本和之积所组成，则称它是给定命题公式的合取范式合取范式。并表示成： Q Q1 Q2 Qn，(nI+),其中Q!,Q2,Qn均为

44、基本和。 1311.7 范式范式求一个命题公式的合取范式的方法和求析取范式的方法类同：第（）、（）步相同；第（）利用“”对“”的分配就行；第（）去掉永真的析取项。1321.7 范式范式例：求（）（）的合取范式原式（）（）化去化去“”词词（）（） “”深入到变元前，并最多保留一个深入到变元前，并最多保留一个（）（）（） “”对对“”的分配的分配（）（）（）（）（最简合取范式） 1331.7 范式范式讨论定义：（）给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。（）若一个命题公式的合取范式中的各基本和的真值为“”，则该命题公式一定是永真式

45、。 (可用来判定是否为永真式) 例: ）（）（）1341.7 范式范式主析取范式。主析取范式。定义定义在个变元的基本积中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为极小项极小项。例:对二个命题变元讲,极小项有22=4个,即、、对一个命题变元讲,极小项有21=2个,即:、1351.7 范式范式对三个命题变元讲，极小项有23=8个，即：、推广到一般：个命题变元构成的不同极小项有2n个（nI+）。使得每个极小项为真的赋值仅有一个。1361.7 范式范式定义定义对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的主析取范式。主析取范式。定理定理在真

46、值表中，一个公式的真值为的指派所对应的极小项的析取，即为此公式的主析取范式。1371.7 范式范式例：求出、（）、的主析取范式TFFTTTFTTTFTTFTFTFTFTTFF（）1381.7 范式范式则可直接写出各命题公式的主析取范式：（）（）（）（）（）（）（）（）（）（）（）讨论此定理：1391.7 范式范式（1）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“”的行，对应写出极小项的析取式，且一定是唯一的。（2）若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2n个极小项。（3）若二个命题公式对应的主析取范式相同，则此二

47、个命题公式一定是等价的。（4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“”的个数。1401.7 范式范式下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步：（）将命题公式化归为与其等价的析取范式；（）除去永假项，合并基本积中相同项（例：），变为最简析取范式。（）利用添变元的方法，将所有基本积变为极小项。1411.7 范式范式例：二个变元、，利用“”对或“”的分配添项（）（）（）（）（）（）（）合并相同的极小项变为一项。例：求（）的主析取范式解：原式（）（） -（1）化为析取范式 1421.7 范式范式（） -（2）消去永假项，变为最简析取范式（）（）（）（

48、）（） -（3）添项（）（） -（4）合并相同最小项1431.7 范式范式例：证明（）证明方法是写出二命题公式的主析范式，看其是否相同：（）（）（）（）（）而（）（）（）（）（）（）（）（）（）主析范式相同，有（） 1441.7 范式范式主合取范式主合取范式定义在个变元的基本和中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种基本和为极大项。例：有二个变元,的极大项有22=4个，（）、（）、（）、（）有个变元，则有2n个极大项（nI+）。 1451.7 范式范式定理在真值表中，一个公式的真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。在

49、真值表中真值为“”的个数等于主合取范式中极大项的个数。例：求出（）、（）、（）、（）的主合取范式1461.7 范式范式（）TTFTTTFFTTFTTFTTTFTFTFFF直接写出其主合取范式：（）（）（极大项）（）（）（）1471.7 范式范式（）（）（）（）（）（）（）（）（）（）（）（）（）（）1481.7 范式范式讨论（）与命题公式等价的主合范式中极大项的个数等于其真值表中真值为“”的个数。由真值表找极大项的方法为：将表中值为“”的对应真值指派中，把变元写成否定，把变元的否定写成变元。（）只要命题公式不是永真式，则一定可以写出对应与其等价的唯一的主合取

50、范式。1491.7 范式范式（）若命题公式为含有个变元的永假式，则主合取范式包含了2n个极大项的合取式。（）可用主合取范式判定二个命题公式是否等价。（）已知一个命题公式的主析取范式，则一定可以直接写出与其等价的主合取范式来。反之也行。例：（）（）（）主析取范式（）主合取范式1501.7 范式范式（）对应于有个变元的命题公式，则一定有：主析范式极小项数主合范式极大项数主析范式极小项数主合范式极大项数2n下面介绍不用真值表求一命题公式主合取范式的方法：（1）化为与命题公式等价的合取范式；（2）除去真值为“T”的析取项和除去析取项中相同变元且只保留一个，变为最简合取式；（3）添项

51、，使析取项均变为极大项；1511.7 范式范式例如：、为二个变元，即：（）（）（）（4）合并相同的极大项，保留一项。例：求（）的主合取范式解：原式（）（）（）（）（）1521.7 范式范式主范式序（列）的唯一性主范式序（列）的唯一性（）极小项极其编码为了确保主范式的唯一性，二个安排：（a）各命题变元的位置安排一固定次序；（b）对极小项、极大项安排一个次序。对于有个变元的命题公式，则最多可有2n个极小项，用m0 m1 m2n-1来表示。下面列出三个变元，且、的位置已排定，则 153P Q R1117m(7)十P Q R1106m(6)十P Q R1015m(5)十P

52、Q R1004m(4)十P Q R0113m(3)十 P Q R0102m(2)十 P Q R0011m(1)十P Q R0000m(0)十极小项表示二进制数十进制数m(i)十1.7 范式范式1541.7 范式范式例：设一命题公式有五个变元，P0,P1,P2,P3,P4（次序已定），则必可写出25=32个极小项，下列出m(11)十和m(18)十的极小项表示：即， m(11)十 m(01011)二（ P0 P1 P2 P3 P4 ）m(18)十 m(10010)二（ P0 P1 P2 P3 P4 ）1551.7 范式范式通过上例归纳出一求极小项m(i)十的方法：(a)把(i)十变换成等价的

53、(J0,J1Jn-1)二(b)由二进制写出其对应的极小项：例：求（）（）的编码表达式：（设、次序已定）解：原式（）（）（）（） 1561.7 范式范式 m(001) 二 m(010)二 m(100)二 m(101)二 m(1)十 m(3)十 m(7)十 m(6)十 m1,m3,m7,m61,3,6,7 （）极大项及其编码用M0,M1,M2n-1表示个变元的命题公式的极大项。求极大项的方法： 1571.7 范式范式(a)把(i)十变换成等价的(J0,J1Jn-1)二(b)由二进制数写出其对应的极大项：例：求（）（）的极大项编码表示（设、次序已定）1581.7 范式范式解：原式（）（）

54、（）（） M(000) 二 M(010)二 M(100)二 (110)二 M (0)十 M (2)十 M (4)十 M (5)十 M0,M2,M4,M5 0,2,4,5 1591.7 范式范式极大项和极小项编码约定刚好相反，从上例中，（）（） 1,3,6,7 0,2,4,5 例：写出（）的主析和主合编码表示1601.7 范式范式TTTTFTFTFTFFP QQPP Q1 0,2,3主析范式为:( ）（）（）主合范式为： P Q且PQ( ）（）（）1611.7 范式范式主范式的个数主范式的个数在介绍联结词总结时讲到：一个原子命题变元有四个不同的真值表（221个）；二个原子命题变元

55、有16个不同的真值表（222个）；以此类推，若有个变元的命题公式，则可构成 22n个不同的真值表。得到结论：对于含有个变元的命题公式，必定可写出 22n个主范式，若排除永真式或永假式，则实际可写出（ 22n ）个主析（或主合）范式。1621.8 推理理论推理理论按公认的推论规则，从前提集合中推导出一个结论来，这样的推导过程称为演绎演绎，或者叫形式证明形式证明。在任何论证中，若认定前提是真的，且从前提集合推导出结论的论证是遵守了逻辑规则的，则我们称此结论是合法的合法的。根据逻辑规则推导出来的任何结论称为有效结论有效结论。推推论论规规则则就是指确定论证的有效性的判据，常是用命题形式表示这些规则

56、，而不涉及实际命题和它的真值。1631.8 推理理论推理理论本节介绍的证明方法，归纳分成三类：（一）真值表技术；（二）推论规则；（三）间接证明法。真值表技术的主要依据是“”的真值表定义。若当且仅当（）为永真式。TTTFFTTTFTFFQP1641.8 推理理论推理理论真值表技术：真值表技术：定义给定二个命题公式和，当且仅当是一个永真式，才可以说是从推导出来的，或称是前提的有效结论。定义设H1，H2,Hm,都是命题公式，当且仅当H1 H2 Hm ，才可以说是前提集合 H1，H2,Hm 的有效结论。1651.8 推理理论推理理论从给定真值表常用的判断方法有二种：（）检查真值表中H1，H2,Hm

57、全部为“”的所有行，看结论是否也均为“”，若均为“”，则结论有效。否则结论无效。（）看结论为“”的所有行，检查每行前提H1，H2,Hm中是否至少有一个为，若有“”，则结论有效；若有均为“”的行，则结论无效。例：试证明下列结论是否有效：画出真值表：1661.8 推理理论推理理论由真值表可见：（），有效（），无效（），（）有效（），（）有效TFFFTTTFTTFFFTFTFTTTFTTTTTFF （）QQP1671.8 推理理论推理理论（），无效例：H1：如果大连是一个大城市，则大寨是一个乡村； H2：大寨是一个乡村；：大连是一个大城市；则：，或者称：不能从前提集合中推导出来。

58、1681.8 推理理论推理理论推理（论）规则：推理（论）规则：从这节开始，我们只讨论命题论证的有效性，而不去讨论命题的真假值；在推论规则中不需要有真值表，也不需要对命题进行真值指派。推理规则的依据是常用的永真蕴含式和等价公式。I1；I2； I3，1691.8 推理理论推理理论I4 （）， I5 ，（） I6 （），（）（）I7 （）（）（）I8 （），（）（）I9 （），（）（）I10 1701.8 推理理论推理理论下面介绍二个规则：P规则：在推导的任何步骤上都可以引入前提（条件）T规则：在推导过程中，如果前面有一个或多个公式永真蕴含S，则可以把S引入推导过程之中。例1：证明：PQ,

59、Q R,PR推理过程：1711.8 推理理论推理理论步骤推理过程规则根据 (1) PQ P (2) P P (3) Q T I(1)(2) (4) Q R P (5) R T I(3)(4)也可以这样推理： (1) PQ P (2) Q R P (3) PR T I(1)(2) 1721.8 推理理论推理理论 (4) P P (5) R T I(3)(4)例2 证明： (PQ),(P R),(Q S)SR (1) (PQ) P (2) P Q T(1) E16 (3) Q S P (4) P S T(2)(3) I6 (5) S P T(4) E18 1731.8 推理理论推理理论 (

60、6) P R P (7) S R T(6) I6 (8) SR T(7)E16下面引进条件证明规则CP：如果能从Q和给定的前提集合P中推导出R来，则就能从前提集合中推导出（Q R）来。即: (PQR)则：P (QR)1741.8 推理理论推理理论例1： P(Q S), RP,Q RS证: (1) R 附加前提 (2) RP P (3) RP T(2) E (4) P T(1)(3) I (5) P(Q S) P (6) Q S T(4)(5) I1751.8 推理理论推理理论 (7) Q P (8) S T(6)(7) I (9) RS CP例2: PQ P(P Q) (1) P 附加前提 (

61、2) PQ P (3) Q T(1)(2) I (4) P Q T(1)(3) (5) P(P Q) CP1761.8 推理理论推理理论3间接证明法间接证明法：（反证法、归谬法）定义定义给出命题公式H1,H2Hm， H1H2 Hm具有真值为“T”，则命题公式集合H1,H2Hm称为是一致的。否则称H1,H2Hm是非一致的。1771.8 推理理论推理理论定理定理设H1,H2Hm是一致的，同时设C是一个命题公式，如果前提集合H1,H2Hm,C是非一致的，则一定有H1,H2HmC成立。证明：由条件H1H2 Hm C F H1H2 Hm C必定为永假式。而H1H2 Hm是一致的，即为永真式，从而只有C为

62、永假式，则C 一定为永真式，故H1H2 HmC成立。1781.8 推理理论推理理论例：证明 P Q (PQ) 证: (1) ( (PQ) 假设前提 (2) PQ T(1) (3) P T(2) (4) P Q P (5) P T(4) (6) P P T(3)(5) (7) F1791.8 推理理论推理理论例2:证明: RQ, RS , SQ, PQ P (1) (P) 假设前提 (2) P T(1) (3) PQ P (4) Q T(2)(3) (5) SQ P (6) QS T(5) (7) S T(4)(6) (8) RS P (9) RT(7)(8) 1801.8 推理理论推理理论

63、(10) RQP (11) QT(9)(10) (12)Q QT(4)(11)讨论：由上例可见，间接证明法在结论较为简单的条件下，使用是比较方便的，实际上间接证明法也可以用CP规则代替它。1811.8 推理理论推理理论间接证明法：特殊条件下的CP规则 H1H2 Hm C F由CP规则： H1H2 Hm C F CF C H1,H2HmC成立 1821.8 推理理论推理理论例：一位计算机工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。（1）会计张某或邻居王某谋害了厂长。（2）如果会计张某谋害了厂长，则谋害不可能发生在半夜。（3）如果邻居王某的证词不正确，则在半夜时房里灯光

64、未灭。（4）如果邻居王某的证词是正确的，则谋害发生在半夜。（5）在半夜房子里的灯光灭了，且会计张某曾贪污过。1831.8 推理理论推理理论解：设 P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋害发生在半夜 O：邻居王某的证词是正确的 R：半夜时房子的灯光灭了 A：会计张某曾贪污过列出条件公式： 1841.8 推理理论推理理论 (1) PQ (4) QN (2) PN (5) RA (3) O R推导过程为： (1) RA P (6) N T (2) R T (7) PN P (3) OR P (8) P T (4) O T (9) PQ P (5) O R P (10) Q T结论

65、：邻居王某谋害了厂长； 185第一章小结学习第一章要注意以下几点：（1）弄清命题与陈述句的关系。（2）弄清由6种基本联结词联结的复合命题的逻辑关系及其真值。特别是要弄清蕴含式”PQ“的逻辑关系及其真值。（3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键问题。（4）会准确地求出给定公式的主析取范式和主合取范式。掌握主析取范式与真值表、成真赋值、主合取范式的关系。186第一章小结（5）会用多种方法判断公式的类型及判断两个公式是否等价。（6）会用等价变换法将一个联结词集中的公式等价地化为另一个联结词全功能集中的公式。（7）掌握推理和判断推理是否正确的方法。187习题选讲例1.符号化下列命题：（1

66、）辱骂和恐吓决不是战斗；（2）除非天气好，否则我是不会去公园的；（3）如果晚上做完作业且没有其它的事，他就会去看电视或听音乐。解：（1）设P：辱骂不是战斗。 Q：恐吓不是战斗。 PQ （2）设P：今天天气好。 Q：我去公园。 QP188习题选讲（3）设P：他晚上做完了作业。 Q：他晚上没有其它事情。 R：他看电视。 S：他听音乐。（PQ）（RS）例2.证明P （Q R）（P Q）（P R）给出本题的各种证明：（1）列真值表：设 M P （Q R） K （P Q）（P R） S P （Q R）（P Q）（P R）189习题选讲TTTTTTF F FTTTTTTF F TTTTTTFF

67、T FTTTTTTF T TTTFFTT T F FTTTFTTT F TTFFTFFT T FTTTTTTT T TSKP RP QMQ RP Q R190习题选讲a)直接证法： P （Q R）的真值为T，其对应指派下（P Q）（P R）的真值均为T。b)反证法：（P Q）（P R）的真值为F，其对应指派下P （Q R）的真值为F。c)条件永真式：（P （Q R）（（P Q）（P R）的真值都为T，及为永真式。（2）逻辑推证a)直接证法：设P （Q R）为T，则 P为T， Q R为T，有三种情况： P为T,Q为T,R为T,则（P Q）（P R）为T。191习题选讲 P为T,Q为F

68、,R为T,则(PQ)(PR)为T。 P为T,Q为F,R为F,则(PQ)(PR)为T。P为F， Q R为F，则： P为F，Q为T，R为F，所以P Q为T， P R为T，得（P Q）（P R）为T。P为F， Q R为T，则： P为F,Q为T,R为T,则(P Q)(PR)为T。 P为F,Q为F,R为F,则(PQ)(PR)为T。 P为F,Q为F,R为T,则(PQ)(PR)为T。综上:当P(QR)为T时,必有(PQ)(PR)为T。192习题选讲b)间接证法：设（P Q）（P R）为F，则必有P Q为T， P R为F，故得P为T，Q为T，R为F。所以P （Q R）为F。（3）等价变换S (P (Q

69、 R)(P Q) (P R) (P( Q R) ( P Q) (P R) (PQ R) ( P Q) (P R) (PQ R) (P Q) (P R) (PQ R) (P R P) (Q P R) (PQ R) (P Q R) (PQ R) (PQ R)T193习题选讲例3.证明，不是最小联结词组。证明:设变元P,Q,用联结词,作用于P,Q得到： P,Q,P,Q,PQ,PP,QQ,QP。但(PQ)(QP),(PP)(QQ),故实际有： P,Q,P,Q,PQ,PP(T) (A) 用作用于(A)类,得到扩大的公式类(包括原公式类):P,Q,P,Q,PQ,(PQ),T,F (B) 用作用于(A)

70、类得到： PQ， P P(F)， P Q (PQ)， P (PQ) Q ， P (PP) P, QP(PQ),QQ(F),Q(PQ)P, QT Q，194习题选讲 P Q (PQ)， P (PQ) Q， PT P， Q (PQ) P， QT Q， (PQ) (PP) PQ。因此(A)类使用运算后，仍在(B)类中。同样，对(B)类使用，运算后，结果仍在(B)中。由上证明：用，两个联结词，反复作用在两个变元的公式中，结果只能产生(B)类中的公式，总共仅八个不同公式，而两个变元所形成的公式共有222=16个彼此不等价的公式，因此，不是功能完备的，更不可能是最小联结词组。 195习题选讲例4. 求

71、(ABC) (A(BC)的主析取范式与主合取范式。解：(1)列表法：设 S (ABC) (A(BC)， R ABC， M A(BC)，根据真值表中S真值为T的指派，所对应的小项析取即为S的主析取范式，S真值为F的指派，所对应的大项合取即为主合取范式。S的真值表如下： 196习题选讲TTTTTFF F FFFFTTFF F TFFFTTFF T FFFFTTTF T TFFTFFFT F FFTFFFFT F TFTFF FFT T FTTFFTTT T TSMBCARBCA B C197习题选讲 S (AB C)(A B C) 主析取范式 S(ABC)(ABC)(ABC)(AB C)(ABC)

72、(ABC)主合取范式(2)公式推导法： S (ABC) (A(BC) (A(BC)(A(BC)(BC) A) 198习题选讲 (A (BC) (A (BC) (BC) A) (A BC) (A BC) (BC A) (A BC) (A BC) m000 m111 0,7199习题选讲当求出主析取范式的编码表达式后可直接利用编码关系，解出主合取范式。即： S (ABC) (A(BC) (A BC) (A BC) m000 m111 0,71,2,3,4,5,6 M001 M010 M011 M100 M100M101 M110 (A BC)(ABC)(ABC)(A BC)(ABC)(ABC)20

73、0习题选讲例5.用推理规则论证下述问题：或者是天晴，或者是下雨。如果是天晴，我去看电影。如果我去看电影，我就不看书。所以，如果我在看书，则天在下雨。解：设 S：今天天晴。 R：今天下雨。 E：我去看电影。 B：我去看书。本题符号化为：SR，SE，EBBR 因为 SR(SR) 故本题为(SR)，SE，EBBR201习题选讲直接证法： (1) (SR) P (2) S R T(1),E (3) (SR)(RS) T(2),E (4) RST(3),I (5)SE P (6) RE T(4)(5),I (7)EB P (8) RB T(6)(7),I (9)BR T(8),E202习题选讲间接证

74、法：a) (1) (SR) P (2) S R T(1) (3) (SR)(RS) T(2) (4) RS T(3) (5) (BR) P(附加前提) (6)BR T(5) (7)B T(6) (8)R T(6) (9)S T(4)(8)203习题选讲(10) SE P(11)E T(4)(10)(12)EB P(13) B T(11)(12)(14)BB 矛盾(7)(13)b)(1)B P(附加前提)(2)EB P(3)E T(1)(2) (4) SE P204习题选讲(5) ST(3)(4)(6) (SR) P (7) S R T(6)(8) (SR)(RS) T(7)(9) RST(8)

75、(10) SRT(9)(11)RT(5)(10)(12) BRCP205第二章第二章谓词逻辑谓词逻辑 2.1 谓词的概念与表示法 2.2 命题函数与量词 2.3 谓词公式与翻译 2.4 变元的约束 2.5 谓词演算的等价式与蕴含式 2.6 前束范式 2.7 谓词演算的推理理论206第二章第二章谓词逻辑谓词逻辑教学目的及要求：教学目的及要求：深刻理解和掌握谓词逻辑的基本概念和基本推理方法。教学内容：教学内容：谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴涵式、前束范式、谓词演算的推理理论。教学重点：教学重点：谓词逻辑中的基本概念和基本推理方法。

76、教学难点：教学难点：谓词演算的推理理论。2072.1 谓词的概念与表示法在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解，这样会产生二大缺点：（1）不能研究命题的结构，成分和内部逻辑的特征（2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。“所有的人总是要死的。 A “苏格拉底是人。 B “所以苏格拉底是要死的。” C2082.1 谓词的概念与表示法1.谓词：谓词：定义定义用以刻划客体的性质或关系的即是谓词谓词。我们可把陈述句分解为二部分：主语（名词，代词）

77、和谓语（动词）。例：张华是学生，李明是学生。则可把它表示成：H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用下列符号表示上述二个命题：H(j)，H(m)。 H作为“谓词”（或者谓词字母）用大写英文字母表示，j,m为主语，称为“客体”或称“个体”。2092.1 谓词的概念与表示法（1）谓词填式）谓词填式：谓词字母后填以客体所得的式子。例：H(a, b)（2）若谓词字母联系着一个客体，则称作一元谓词一元谓词；若谓词字母联系着二个客体，则称作二元谓词二元谓词；若谓词字母联系着n个客体，则称作n元谓词元谓词。（3）客体的次序必须是有规定的。例：河南省北接河北省。 n L b写成二元谓词

78、为：L(n,b)，但不能写成L(b,n) 。2102.2 命题函数与量词命题函数与量词1. 命题函数命题函数客体在谓词表达式中可以是任意的名词。例：C“总是要死的。” j：张三；t：老虎；e：桌子。则C(j), C(t), C(e)均表达了命题。在上面的例子中，C：表示“总是要死的”；x：表示变元（客体变元），则C(x)表示“x总是要死的”，则称C(x)为命题函数。定义定义:由一个谓词字母和一个非空的客体变元的集合所组成的表达式，称为简单命题函数。2112.2 命题函数与量词命题函数与量词讨论定义：（a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；（b）若用任何客体去取代客体变

79、元之后，则命题函数就变为命题；（c）命题函数中客体变元的取值范围称为个体域（论述域）。例：P(x)表示x是质数。这是一个命题函数。其值取决于个体域。可以将命题函数命题，有两种方法：2122.2 命题函数与量词命题函数与量词 a)将x取定一个值。如：P(4)，P(5) b)将谓词量化。如：（x）P(x)，（x）P(x)个体域的给定形式有二种：具体给定。如：j, e, t 全总个体域任意域：所有的个体从该域中取得。2132.2 命题函数与量词命题函数与量词2.量词量词（1）全称量词“”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。例：“这里所有的都是苹果” 可写成：（x）A

80、(x)或(x)A(x)几种形式的读法：（x）P(x)： “对所有的x，x是”；（x）P(x) ： “对所有x，x不是”；（x）P(x) ： “并不是对所有的x，x是”；（x）P(x) ： “并不是所有的x，x不是”。2142.2 命题函数与量词命题函数与量词例：将“对于所有的x和任何的y，如果x高于y，那么y不高于x”写成命题表达形式。解：（ x）（ y）(G(x,y) G(y,x) G(x,y)：x高于y（2）存在量词“”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”,“至少存在一个”，“这里存在着这样的”“”表达式的读法：（ x） A(x) ：存在一个x,使x是；

81、（ x）A(x) ：存在一个x, 使x不是；（ x） A(x) ：不存在一个x, 使x是；（ x）A(x) ：不存在一个x, 使x不是。2152.2 命题函数与量词命题函数与量词例：（a）存在一个人；（b）某个人很聪明；（c）某些实数是有理数将（a）,（b）,（c）写成命题。解：规定：M(x)：x是人；C(x)：x是很聪明； R1(x)：x是实数(特性谓词) R2(x)：x是有理数。则（a）（ x） M(x) ；（b）（ x ）(M(x) C(x)；（c）（ x） (R1(x) R2(x) 。（3）量化命题的真值：决定于给定的个体域给定个体域：a1an以a1an中的每一个代

82、入（x）P(x)P(a1) P(an) （x）Q(x)Q(a1) Q(an) 2162.3 谓词公式与翻译谓词公式与翻译1.谓词公式原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用P(x1xn)来表示。（P称为n元谓词， x1xn称为客体变元），当n=0时称为零元谓词公式。定义（谓词公式的归纳法定义）原子谓词公式是谓词公式；若A是谓词公式，则A也是谓词公式；若A, B都是谓词公式，则(AB),(AB),(AB),(AB)都是谓词公式；若A是谓词公式，x是任何变元，则（x）A,（ x）A也都是谓词公式； 2172.3 谓词公式与翻译谓词公式与翻译只有按-所求得的那些

83、公式才是谓词公式（谓词公式又简称“公式”）。例1：任何整数或是正的，或是负的。解：设：I(x): x是整数； R1(x)：x是正数；R2(x)：x是负数。此句可写成：（x）(I(x)(R1(x) R2(x) )。例2：试将苏格拉底论证符号化：“所有的人总是要死的。因为苏格拉底是人，所以苏格拉底是要死的。”解：设M(x)：x是人；D(x)：x是要死的； M(s)：苏格拉底是人；D(s)：苏格拉底是要死。2182.3 谓词公式与翻译谓词公式与翻译写成符号形式：（ x）(M(x) D(x)， M(s) D(s)2.由于对个体描述性质的刻划深度不同，可翻译成不同形式的谓词公式。2192.4 变元的约

84、束变元的约束1.辖域：紧接在量词后面括号内的谓词公式。例：（x）P(x) , （x）(P(x) Q(x) 。若量词后括号内为原子谓词公式，则括号可以省去。2.自由变元与约束变元约束变元：在量词的辖域内，且与量词下标相同的变元。自由变元：当且仅当不受量词的约束。例：（x）P(x,y) ,（ x）(P(x) y(P(x,y) 。2202.4 变元的约束变元的约束3.约束变元的改名规则任何谓词公式对约束变元可以改名。我们认为（x）P(x,y)和（z）P(z,y)是一等价的谓词公式，但是需注意，不能用同一变元去表示同一谓词公式中的二个变元。例如：（ y）P(y,y)是不正确的。下面介绍约

85、束变元的改名规则：（a）在改名中要把公式中所有相同的约束变元全部同时改掉；（b）改名时所用的变元符号在量词辖域内未出现的。2212.4 变元的约束变元的约束例：（x）P(x) （y）R(x,y)可改写成（x）P(x) （z）R(x,z) ，但不能改成（x）P(x) （ x）R(x,x) ，（x）R(x,x)中前面的x原为自由变元，现在变为约束变元了。4.区别是命题还是命题函数的方法（a）若在谓词公式中出现有自由变元，则该公式为命题函数；（b）若在谓词公式中的变元均为约束出现，则该公式为命题。例：（x）P(x,y,z)是二元谓词，（y）（x）P(x,y,z)是一元谓词，而谓词公式中如果

86、没有自由变元出现，则该公式是一个命题。 2222.4 变元的约束变元的约束举例：例1：“没有不犯错的人。”解:设F(x)为“x犯错误”,M(x)为“x是人”（特性谓词）。可把此命题写成:(x）(M(x) F(x)（x）(M(x)F(x)例2：“x是y的外祖父” “x是z的父亲且z是y的母亲”设P(z)：z是人；F(x,z)：x是z的父亲；M(z,y)：z是y的母亲。则谓词公式可写成：（z）(P(z) F(x,z) M(z,y) 。5.代入规则：代入规则：对公式中的自由变元的更改叫做代入。 (a)对公式中出现该自由变元的每一处进行代入， (b)用以代入的变元与原公式中所有变元的名称不能相同。22

87、32.4 变元的约束变元的约束6.个体域（论述域，客体域）:用特定的集合表示的被约束变元的取值范围。(1)个体域不同，则表示同一命题的谓词公式的形式不同。例：“所有的人必死。”令D(x)，x是要死的。下面给出不同的个体域来讨论：()个体域为：人类，则可写成（x）D(x)；()个体域为任意域（全总个体域），则人必须首先从任意域中分离出来，设M(x)，x是人，称M(x)为特性谓词。命题可写成（ x）(M(x) D(x)2242.4 变元的约束变元的约束（2）个体域不同，则表示同一命题的值不同。Q(x): x5 F T TxQ(x) F F TxQ(x)15,30-3,6,2-1,0,3（3）对于

88、同一个体域，用不同的量词时，特性谓词加入的方法不同。对于全称量词，其特性谓词以前件的方式加入；对于存在量词，其特性谓词以与的形式加入。2252.4 变元的约束变元的约束例：设个体域为:白虎(白猫),黄咪（黄猫），同时令C(x):x是猫(特性谓词);B(x):x是黑色的;A(x):x是动物。（）描述命题：“所有的猫都是动物”。即：（x）(C(x) A(x)（T）（真命题）写成（x）(C(x) A(x) （F）则为假命题了。（x）(C(x) A(x)TT T TT （x）(C(x) A(x) TT F FF（）描述命题：“一些猫是黑色的” 。（x）(C(x) B(x) FF F F F

89、而（x）(C(x) B(x)F F T TT2262.4 变元的约束变元的约束7.量词对变元的约束，往往与量词的次序有关。例：（y）（x）(xy-2)表示任何y均有x，使得x3 ,则可写出：（x）P(x)P(0) P(1) P(i) （x）P(x) P(0)P(1) P(i) 下面分类介绍在谓词公式中含有量词的等价式和永真蕴含式。（1）量词转换律： E25(Q3) （x）P(x) （x）P(x) E26(Q4) （x）P(x) （x）P(x) 下面证明：设个体域为： S=a1,a2,an 2322.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式（x）P(x) (P(a1) P(

90、a2) P(an) P(a1) P(a2) P(an)（x）P(x) 下面举例说明量化命题和非量化命题的差别:否定形式不同例：否定下列命题： (a)上海是一个小城镇 A(s) (b)每一个自然数都是偶数（x）(N(x)E(x)上述二命题的否定为： (a)上海不是一个小城镇 A(s) (b)有一些自然数不是偶数（x）(N(x)E(x)（x）(N(x)E(x) （x）(N(x)E(x) （x） (N(x) E(x)2332.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方法是： x

91、的否定变为x ， x的否定变为x 。（2）量词辖域的扩张及其收缩律 E27(Q6) （ x）A(x) P （x）(A(x) P) (Q7) （ x）A(x) P （x）(A(x) P) E28(Q9) （x）A(x) P （x）(A(x) P) (Q8) （ x）A(x) P （x）(A(x) P)P为不含有变元的任何谓词公式2342.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式证明E27(Q6)，设个体域为： S=a1,a2,an （x）A(x) P(A(a1) A(a2) A(an) P (A(a1)P)(A(a2)P) (A(an) P ) （x）(A(x) P) E30 (Q

92、14) （x）A(x)B （x）(A(x)B) E31 (Q15)（ x）A(x)B （x）(A(x)B) E32(Q16) A（x）B(x) （x）(AB (x) E33 (Q17) A （x） B(x) （x）(AB (x)证明E30 (Q14) ，设个体域为： S=a1,a2,an （x）(A(x)B) (A(a1)B) (A(an)B) (A(a1) B) (A(an) B) 2352.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 (A(a1) A(an) B （x ）A(x) B （x）(A(x) B) （ x）A(x)B（3）量词分配律E24(Q10) （x）(A(x)B(

93、x) （x）A(x)（ x）B(x)E23 (Q11) （x） (A(x) B(x) （x）A(x) （ x）B(x) I18(Q12) （x） (A(x) B(x) （x）A(x) （ x）B(x)I17(Q13) （x）A(x) （x）B(x) （ x）(A(x) B(x) E29(Q18) （x） (A(x) B(x) （x）A(x) （x）B(x)I19(Q19) （x）A(x) （x）B(x) （x）(A(x) B(x)2362.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式证明E24(Q10)和I19(Q19) ，设个体域为： S=a1,a2,anE24(Q10) （x）(A

94、(x)B(x) (A(a1)B(a1) . (A(an)B(an) (A(a1) A(an) (B(a1) B(an) （x）A(x)（ x） B(x)I19(Q19) （x）A(x) （x）B(x) （x）A(x) （x）B(x) （x）A(x) （x）B(x) (A(a1) A(an) (B(a1) B(an) (A(a1) B(a1) (A(a1) B(an) (A(an) B(a1) (A(an) B(an)2372.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 (A(a1) B(a1) (A(an) B(an) （x）(A(x) B(x) （x）(A(x) B(x)（4）量词

95、的添加和除去的永真蕴含式Q1 （x）P(x) P(y) Q2 P(y) （x）P(x) Q5 （x）P(x) （x）P(x) （x）P P （x）P P (P为不含x变元）Y是个体域中任一元素2382.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式（5）含有多个量词的永真式：（）量词出现的次序直接关系到命题的含义： “（x）（y）”表示：“无论选定一个什么样的x值总能找到一个y能使x和y” “（y）（x）”表示：“只选取一个y值，以致无论怎样选定一个x，能够使y和x” 下面列出对应的表达式可以看出其不同处：设x的个体域为： a1,a2,an ， y的个体域为： b1,b2,bn ，则：

96、（x）（y）P(x,y) （y）P(a1,y) （ y）P(an,y) 2392.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 (P(a1, b1) P(a1, bn) (P(an, b1) P(an, bn)（y）（x）P(x,y) （x）P(x, b1) （x）P(x, bn) (P(a1, b1) P(an, b1) (P(a1, bn) P(an, bn)例：x,y的个体域鞋子，P(x,y):和配成一双鞋子。（x）（y）P(x,y) T （y）（x）P(x,y) F2402.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式（）在含有多个量词的谓词公式中, （x）（y）,（

97、 x）（y）的位置是可以改变的,且不影响命题的真值。例：x,y的个体域为N=0,1,2，则（x）（y）P(x,y) （y）P(0,y) （ y）P(i,y) (P(0,0) P(0,1) P(0,j) ) (P(i,0) P(i,1) P(i,j) ) (P(0,0) P(1,0) P(i,0) ) (P(0,1) P(1,1) P(i,1) ) （x）P(x,0) （ x）P(x,1) xP(x,j) （ y）（x）P(x,y) 2412.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式同样：（x）（y）P(x,y) （y）（x）P(x,y)（）量词转换律的推广应用:把深入到谓词公

98、式前面去的方法。（x）（y）（z）P(x,y,z) （x）（y）（z）P(x,y,z) （x）（y）（z）P(x,y,z) （x）（y）（z）P(x,y,z) （）两个量词, 所组成的谓词公式的等价式和永真蕴含式（8个）（x）（y）P(x,y) （y）（x）P(x,y) （x）（y）P(x,y) （y）（x）P(x,y) （ y）（x）P(x,y) （x）（y）P(x,y) （y）（x）P(x,y) （x）（y）P(x,y) 2422.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式（x）（y）P(x,y) （y）（x）P(x,y) （x）（y）P(x,y) （y）（x）P(x,y

99、) （ y）（x）P(x,y) （x）（y）P(x,y) （x）（y）P(x,y) （y）（x）P(x,y) （6）谓词公式的对偶式定义定义在一个谓词公式A中（其中不出现,词）把公式A中 , , F, T, , , 变为公式A*中 , , T, F, , , 则称A*是A的对偶式。定理定理若谓词公式A B，则A* B* ；若谓词公式A B ，则B* A* （这里A,B有同样的个体域）。2432.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式例： I17(Q13)（ x）A(x)（ x）B(x) （x）(A(x)B(x)I18(Q12) （x）A(x) （ x）B(x) （x）(A(

100、x) B(x) 2442.6 前束范式前束范式定义定义一个公式，如果量词均非否定地在全式的开头，它们的作用域延伸到整个公式的末尾，则称此公式叫前束范式。例：（x）（y）（z）( Q(x,y) R(z) (前束范式) 定理定理任何一个谓词公式均和一个前束范式等价。证明:利用量词转换把深入到原子谓词公式前, 利用约束变元的改名规则，利用量词辖域的扩张收缩律,把量词移到全式的最前面，这样一定可得到等价的前束范式。2452.6 前束范式前束范式例：（x）P(x) R(x) （y）P(y) R(x) （ y）(P(y) R(x) 例：把（x）P(x)（ x）Q(x) 变成前束范式。（x）P(x)

101、（x）Q(x) （x）P(x)（x）Q(x) （x）P(x) （x）Q(x) （x）(P(x) Q(x) 2462.7 谓词演算的推理理论谓词演算的推理理论1.含有量词的特殊永真式含有量词的特殊永真式定义定义设A(x)是一个谓词公式，x是其中的自由变元，若把y代入到A(x)里而不会产生变元的新的约束出现，则称A(x)对于y是自由的。例：下面A(x)对于y是自由的： A(x) （ z）P(z) Q(x,z),这里x为自由变元,若用y去取代A(x)中的x, A(y) （z）P(z) Q(y,z),这里y也仍为自由变元；2472.7 谓词演算的推理理论谓词演算的推理理论下面A(x)对于y不是自由

102、的： A(x) （y）(S(x) S(y), x为自由变元，若用y代入A(x)的x中去得： A(y) （y）(S(y) S(y) ，y变为约束变元了，产生了新的约束出现。如有必要代入y，则应先将式中的约束变元y改名。（z）(S(x)S(z)然后代入y （z）(S(y)S(z)y仍为自由变元。归结归结：判定A(x)对于y是自由的，只要看公式A(x)中y, y的辖域内有没有x的自由出现就行：若有x的自由出现则A(x)对于y不是自由的，若无的x自由出现则一定可以肯定A(x)对于y是自由的。2482.7 谓词演算的推理理论谓词演算的推理理论下面分别介绍四个推理规则（1）全称指定规则（US规则）。如

103、果对个体域中所有客体x, A(x)成立，则对个体域中某个任意客体c， A(c) 成立。该规则表示成：（x）A(x) A(c) (x,c个体域) （2）全称推广规则（UG规则）如果能够证明对个体域中每一个客体c，命题A(c) 都成立，则可得到结论（x）A(x) 成立。该规则表示成： A(x) （x）A(x) 2492.7 谓词演算的推理理论谓词演算的推理理论（3）存在指定规则（ES规则）如果对于个体域中某些客体A(x)成立，则必有某个特定的客体c，使A(c)成立。该规则表示成：（ x）A(x) A(c) 例：x的个体域为I=整数，P(x):x是偶数，Q(x): x是奇数。（x）P(x)

104、（x）Q(x) T 但P(c) Q(c) F2502.7 谓词演算的推理理论谓词演算的推理理论（4）存在推广规则（EG规则）如果对个体域中某个特定客体c，有A(c) 成立，则在个体域中，必存在x，使A(x)成立。该规则表示成： A(c) （x）A(x) 2 推论规则及使用说明推论规则及使用说明命题逻辑中的P,T,CP规则和简接证明法，都可以引用到谓词逻辑的推论规则中来，不过要注意对量词做适当处理，其方法是：用US,ES在推导中去掉量词，用UG,EG使结论量化。2512.7 谓词演算的推理理论谓词演算的推理理论规则使用说明：（1）在使用ES,US时一定要是前束范式（2）推导中连续使用US规则

105、可用相同变元（ x）P(x) P(y),（ x）Q(x) Q(y), （3）推导中既ES用，又用US，则必须先用ES ，后用US方可取相同变元，反之不行。（x）P(x) P(y) （x）Q(x) Q(y) （4）推导中连续使用ES规则时，使用一次更改一个变元。2522.7 谓词演算的推理理论谓词演算的推理理论例：证明苏格拉底论证（x）(M(x)D(x)M(s) D(s)(1) M(s) P(2)（ x）(M(x)D(x) P(3) M(s)D(s) US(4) D(s) T例：证：（x）(H(x)M(x) , （x）H(x) （x）M(x)2532.7 谓词演算的推理理论谓词演算的推理理

106、论(1) （x）H(x) P(2) H(c) ES(3) （x）(H(x)M(x) P(4) H(c) M(c)US(5) M(c)T(6) （x）M(x) EG例：证: （x） (P(x)Q(x) （x） P(x) （x）Q(x) (1)（ x） P(x)引入前件 (2) （x） (P(x)Q(x) P (3)P(c) Q(c)ES 2542.7 谓词演算的推理理论谓词演算的推理理论 (4) P(c) US (5) Q(c) T (6) （x）Q(x) EG (7) （x ）P(x)（x）Q(x) CP例：证明：（x）(P(x)Q(x), （x）P(x) （ x）Q(x) (1) （x）Q

107、(x) 假设前提 (2) （x）Q(x) T (3) Q(c)US (4) （x）P(x) P 2552.7 谓词演算的推理理论谓词演算的推理理论 (5) P(c) US (6) P(c)Q(c) T (7) （x）(P(x)Q(x) UG (8) （x）(P(x)Q(x) P (9) （x）(P(x)Q(x) （x）(P(x)Q(x) T (10) F例：下列结论能否从前提中推出：（x ）(P(x)Q(x) , Q(a) （x） P(x) a为x个体域中一个元素 (1) Q(a) P (2)（ x） (P(x)Q(x) P2562.7 谓词演算的推理理论谓词演算的推理理论(3) P(a)Q

108、(a)US(4) P(a)T(5) （x） P(x)UG在使用US,ES,UG,EG这四条规则时,要注意严格按照它们的规定去使用。2572.7 谓词演算的推理理论谓词演算的推理理论书中例4证明：(1)（x）(y）(S(x,y)M(y)（z）(P(z)R(x,z) P(2)（y）(S(b,y) M(y)（z）(P(z)R(b,z) US(1)(3)(z)P(z)附加前提(4)（z）(P(z)T(3)(5)P(a)US(4)(6)P(a)R(b,a) T(5)(7)(P(a)R(b,a) T(6)(8)（z）(P(z)R(b,z) UG(7)(9)（z）(P(z)R(b,z) T(8)2582.7

109、谓词演算的推理理论谓词演算的推理理论(10)（y）(S(b,y) M(y)T(2)(9)(11)（y）(S(b,y) M(y)T(10)(12)(S(b,c) M(c) US(11)(13)S(b,c) M(c) T(12)(14) S(b,c) M(c) T(13)(15)（y）(S(b,y) M(y) UG(14)(16)（x）（y）(S(x,y) M(y) UG(15)(17) (z)P(z) （x）（y）(S(x,y) M(y) CP(3)(16)2592.7 谓词演算的推理理论谓词演算的推理理论例：二个量词的推理比较复杂：（ x）P(x)（x）(P(x)Q(x) R(x) ,

110、（x）P(x), （x）Q(x) （x）（ y）(R(x) R(y) (1) （ x）P(x) P (2) P(w) ES (3) P(w) Q(w) T (4) （x）P(x) （x）(P(x)Q(x) R(x) P (5)（ x）(P(x)Q(x) R(x) T2602.7 谓词演算的推理理论谓词演算的推理理论(6) P(w)Q(w) R(w)US(7) R(w) T(8) （x）R(x) EG(9) （x）Q(x) P(10) Q(z) ES(11) P(z) Q(z) T(12) P(z)Q(z) R(z) US2612.7 谓词演算的推理理论谓词演算的推理理论(13) R(z) T(

111、14) （y）R(y) EG(15) （x）R(x) （ y）R(y)T(16) （x）（ y）(R(x) R(y)T 三个量词的推理过程更为复杂262第二章小结学习第二章要注意以下几点：(1)同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，必须弄清个体域。(2)在将命题符号化时，要特别注意量词与联结词的搭配。经常的情况是全称量词与蕴含词搭配，存在量词与合取词搭配。因此有下面两种形式的公式：（x）(A(x) B(x) （x）(A(x) B(x) 而（x）(A(x) B(x) （x）(A(x) B(x) 263第二章小结与，与的含义完全不同。

112、(3)记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。(4)在谓词演算的推理证明中，要特别注意US，UG，ES，EG规则成立的条件。 264习题选讲例1.符号化下列命题：(1)没有不犯错误的人；(2)发光的不都是金子；(3)在南京高校学习的学生，未必都是南京籍的学生。解：(1)设M(x)：x是人。 Q(x)：x犯错误。本题符号化为：（x）(M(x)Q(x)或者： (x)(M(x)Q(x)(2)设L(x)：x是发光的东西。G(x)：x是金子。（x）(L(x)G(x) 或（x）(L(x)G(x)265习题选讲(3)设S(x)：x是南京高校学习的学生。 F(

113、x)：x是南京籍的学生。则（x）(S(x)F(x) 本题也可加深刻划：S(x)：x是学生。L(x)：x在学习。H(x)：x在南京高校。G(x)：x是南京籍的人。则(x)(S(x)L(x)H(x)G(x) S(x)266习题选讲例2.写出（x）(F(x)G(x)(xF(x) （x）G(x)的前束范式。解：原式（x）(F(x)G(x)(x)F(x) (x)G(x) (x)(F(x)G(x) (x)F(x) (x)G(x) (x)(F(x) G(x) G(x) (x) F(x) (x)(F(x) G(x) (x) F(x) (x)(F(x) G(x) (y) F(y) (x) (y) (F(x)

114、 G(x) F(y) 267第二编集合论集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。在现代数学中，每个对象（如数、函数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支，本质上都是在研究这种或那种对象的集合的性质。集合论已成为全部现代数学的理论基础。268第二编集合论集合论的特点是研究对象的广泛性。它总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛地应用于各种科学和技术领域。269第二编集合论由于集合论的语言适合于描述和研究离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、

115、排队论、开关理论，形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍：集合、二元关系和函数，以及集合的基数问题。 270第三章第三章集合与关系集合与关系 3.1 集合概念和表示3.2 集合的运算3.3 序偶与笛卡尔积3.4 关系及其表示3.5 关系的性质3.6 复合关系和逆关系3.7 关系的闭包运算 3.8集合划分和覆盖3.9等价关系与等价类3.10相容关系3.11序关系271第三章第三章集合与关系集合与关系教学目的及要求：教学目的及要求：深刻理解和掌握有关集合和关系的基本概念和基本运算。教学内容：教学内容：集合的概念与表示、集合的运算、序偶与笛卡尔积、关系及表示、关系的

116、性质、复合关系和逆关系、关系的闭包运算、等价关系与等价类、序关系。教学重点：教学重点：关系及关系的运算、等价关系、序关系。教学难点：教学难点：关系的闭包运算、等价关系、等价类。2723.1 集合的概念和表示法1、集合与元素（1）集合：具有某种特殊性质的客体的聚合。讨论：一些不同的确定的对象之全体。客体：是泛指一切，可以是具体的、抽象的元素（成员）：属于任何集合的任何客体。符号：用大写英文字母A，B.表示集合，用小写英文字母a，b.或其它符号表示元素。元素与集合间的关系： a是集合S中的元素，则写成a S ；b不是集S合中的元素，则写成b S 。2733.1 集合的概念和表示法集合S的基数(

117、势)：S中的元素个数。用|S|表示。有限集合：集合的基数（元素）是有限的。无限集合：集合的基数（元素）是无限的。本书中常用集合符: Im(m1) 有限个正数的集合1,2,3m Nm(m0) 有限个自然数的集合0,1,2m 以上是有限集合,下面是无限集合：2743.1 集合的概念和表示法N 然数集合 0,1,2I+ 正整数集合 1,2,3I 整数集合 -1,0,1,2P 素数集合大于1的正整数，只能被1和自己整除Q 有理数集合 i/j. i、j均为整数且j0R 实数集合有理数、无理数C 复数集合 a+bi，a、b可为实数 i= -1 2753.1 集合的概念和表示法(2)集合的表示方法:(

119、的元素。例：S=a,1,2,p,q 2773.1 集合的概念和表示法(3)三个特殊集合全集全集:如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用E表示。 E=x | p(x) p(x) p(x)为任何谓词公式空集空集:不拥有任何元素的集合称为空集（或称零集），用表示, =x | p(x) p(x) = 注意, 前者是空集，是没有元素的集合；后者是以作为元素的集合。2783.1 集合的概念和表示法集合族集合族:集合中的元素均为集合，称这样的集合为集合族。例A=a，b，c、d2、集合之间的关系相等相等:给定二个集合A和B，当且仅当A和B具有同样的元素（成员

120、），则A和B相等，记作A=B, 并规定：（A=B）x (x A x B) 例：a, b, c=b, a, a, c, c 例：设P=1,2,4，Q=1,2,4，则PQ2793.1 集合的概念和表示法包含包含:设A、B是任意二个集合，如果集合A的每一个元素都是B的一个元素，则称A 是B的子集，或者说A包含于B，或者说B包含A，记作 AB，或者BA。并规定： ABBAx(x A x B) 例：A1=1,2,3 A2=0 A3=1,2,3,0 B=1,2,3,0 则A1、A2、A3均为B的子集合，并记为 A1B，A2B，A3B2803.1 集合的概念和表示法真包含真包含:设A、B是任意二个集

121、合，若AB且AB，则称 A是B的真子集，记作AB（A真包含于B）,并规定：AB（AB AB）注意区分“”和“”的关系： “”关系是指集合和该集合中元素间的关系。例：S=a,b,c 则a S，bS，c S 而“”关系是指二个集合之间的关系。例：S1=a, b S2=a,b,1,2 则S1 S2 若A不包含于B，则也可表示成AB2813.1 集合的概念和表示法定理定理设E是全集，A是一个集合，则一定有AE。证明：x（x A x E）而x E始终为“T”，所以x A x E一定为“T”故有x（x A x E）为“T”，则有AE2823.1 集合的概念和表示法定理定理设A、B是任意

122、二个集合，当且仅当A B和 BA 才有A=B。证明：()充分性：（A=B）（A B B A） (A=B)x (x A xBxB xA) x(xA xB)x(xB xA) (AB)(BA) ()必要性：ABBAA=B (AB)(BA)x(xA xB)x(xB xA) (A=B)2833.1 集合的概念和表示法推论推论对于任一集合A，则有A A。定理定理设A、B、C是任意集合，如果AB和 BC，则AC 。推论推论若AB和BC，则AC 。2843.1 集合的概念和表示法定理定理设有空集和任一集合A，则A证明：设xA，要证明A，只要证：（x）(x xA)为“T”中没有元素，x为假，（x

123、）（x xA）为“T” 定理定理是唯一的。证明：设有二个空集合1和2 是任何集合的子集（1 22 1） (1=2) 2853.1 集合的概念和表示法3、幂集和索引集合（1）幂集：例：S1=a 则子集为，a S2=1，2 则子集为，1，2，1，2 S3= 则子集有（而不是）由此可见,给定一个集合S,则和S一定是S的子集。 2863.1 集合的概念和表示法幂集幂集:设A是集合，A的所有子集（作为元素）的集合称为A的幂集,记作(A)或2A ,且有： (A)(=2A)=x | x A 例：若A1=，则(A1)= 若A2=a，则(A2)=，a 若A3=1，2,则(A3)=，1，2，1，2

124、2873.1 集合的概念和表示法讨论：(a)集合的元素个数称为集合的“基数”或叫“势” |(S)|=2 |s| 为幂集(S)的基数(b)若A为有限集合，则(A)也为有限集合。若A为无限集合，则(A)也为无限集合。(c)一定有A(A)， (A)，即对非空集合，在幂集中至少有两个子集和A。 2883.1 集合的概念和表示法（2）索引集合为了在计算机上表示集合，必须给每一个集合的元素加上标记，以用来表示元素在集合中的位置。例：S1=a，b 假设集合S1中，a,b的位置已经固定。则用二进制下标法来表示S的所有子集：= =B00，a=B10，b=B01，a，b=B11这样(S1)=B00，B01，B

125、10，B11=Bi | iJ 而其中J=00，01，10，11（索引集合或指标集合） 2893.1 集合的概念和表示法例：已知集合S=a1，a2，a3，a4，a5，a6，S的子集有26 个,可以分别表示成B0，B1B( 26-1)则B7=B000111=a4，a5，a6 B15=B001111=a3，a4，a5，a6 B22=B010110=a2，a4，a5等等2903.2 集合的运算 1.交集（交运算）交集交集:二个集合A和B的交集AB是由A和B所共有的全部元素构成的集合，即： AB=x | x A x B 例：A=a，b B=a，c AB=a 定理定理集合的相交运算是可交换的和可结合的

126、，即对于任何集合A，B，C有 AB=BA，（AB）C=A（BC）证明：设x是AB中任一元素则x ABx x | x A x Bx x | x B x Ax BA AB=BA 2913.2 集合的运算定理定理设A是E的任一子集，则有（1）AA=A （2）A= （3）AE=A不相交不相交:A、B是二个集合，若AB=，则称A和B 是不相交的，或者说A和B没有相同的元素。若C是一个集合族（集合族：元素均为集合的集合）使C的任何二个元素都不相交，则称C为不相交的集合族。例：A=a，b，c A为不相交的集合族 2923.2 集合的运算2.并集（并运算）定义定义 A、B是任意二个集合，

127、A和B的并集AB是由A和B的所有元素构成的集合，即： AB=x xAxB。例：A=a, b, c B=1,2,3 则 AB=a,b,c,1,2,3 定理定理集合的并运算是可交换的和可结合的，即对任何A，B，C,有 AB=BA和（AB）C=A（BC） 2933.2 集合的运算定理定理集合的并和交运算，每一个对另一个都是可分配的。即： (1)A（BC）=（AB）（AC） (2)A（BC）=（AB）（AC）定理定理设A、B、C是全集E的任意子集，则有： (1)AA=A (2)A=A (3)AE=E2943.2 集合的运算3.相对补集：定义定义设A和B是二个任意集合，B对A的相对补

128、集（A-B）是由A中且不属于B的所有元素组成的集合。即： A-B=xxAxB=xxAxB例：设A=0，1，2 B=2，3，4 则 A-B=0,1 B-A=3，4注意，A-BB-A。2953.2 集合的运算定理定理设A，B，C，D是E的子集，则有： (1 )A-BA， (2 )若AB和CD，则ACBD， (3 )若AB和CD，则AC BD， (4 ) 若AAB，则 BAB (5 ) 若ABA，则ABB (6 ) 若AB，则AB=B (7 ) 若AB，则AB=A (8 )A-=A (9 )A(B-A)= (10)A(B-A)=AB2963.2 集合的运算 (11)A-（BC）=（A-B）（

129、A-C） (12)A-（BC）=（A-B）（A-C）4、绝对补集（补运算）定义定义设E是全集，任一集合A对E的相对补集称为A的绝对补集（或称补集）记作A（或 A）。即： A=E-A=x| xExA=x| xA例：设E=a，b，c，d A=a，b 则A=c，d 2973.2 集合的运算定理定理 A是E的任一子集，则有 (1)AA=E (2)AA= 定理定理设A、B是E的二个子集，当且仅当 AB=E和AB=才有B= A（或A= B）证明： () 充分性：B= A （AB=E）（AB=）B=A AB=AA=E AB=AA=成立2983.2 集合的运算 ()必要性： (AB=E)(AB=)B

130、=A B=EB=(AA)B =(AB)(AB) =（AB） =（AA）（AB） =A（AB） =AE=A 2993.2 集合的运算补集的性质：（1）（A）=A（2）（AB）=AB（3）（AB）=AB（4）=E（5）A-B=AB 例：设A=2，5，6，B=2，3，4，C=1，3，4， E=1，2，3，4，5，6则A-B=5，6=AB =2，5，61，5，6=5，63003.2 集合的运算5、环和(对称差) 定义定义设A、B是任意二集合，A和B的环和记作 AB。即： AB=(A-B)(B-A)=(AB)(BA) 或者x(AB)xx |xAxB 例：设A=2，5，6，B=2，3，4 则 AB=3，

131、4，5，6 3013.2 集合的运算对称差的性质：(1)AB=BA (可交换)(2)(AB)C=A(BC) (可结合)(3)AB=(A-B)(B-A) =(AB)(BA)=(AB)(AB)(4)AA=(5)A=A(6)AB=(A(B)(B(A) =(AB)(BA)=(B-A)(A-B)=AB(7)A(BC)=(AB)(AC) (对可分配)3023.2 集合的运算6、文氏图(1)文氏图的画法规则：规定矩形表示E。子集用圆画在E中。(2)文氏图应用：（a）表示集合和运算的关系可用文氏图画出各种运算：（b）证明集合恒等式例：A（BC）=（AB）（AC）3033.3 序偶与笛卡尔乘积 1.序偶：

132、定义定义由二个具有给定次序的客体所组成的序列称为序偶。记作x，y例：XY二维平面上点的坐标x，y就是序偶。说明：在序偶中二个元素要有确定的排列次序。即：若ab时，则a，bb，a 若x，y=a，b（x=ay=b）下面定义多重序元：三重序元=x,y,z n重序元=x1，x2,x3，xn 3043 序偶与笛卡尔乘积2.笛卡尔乘积定义定义设A，B为二个任意集合，若序偶的第一个成员（左元素）是A的一个元素，序偶的第二个成员（右元素）是B的一个元素，则所有这样的序偶的集合称为A和B的笛卡尔乘积。记作：AB=x，y|（xA）（yB）例：设A=1，2 B=a，b 则AB=,2,b BA=,

133、ABBA 即“”是不满足交换律。3053.3 序偶与笛卡尔乘积例：设A=a，b，B=1，2，C=z 则 (AB)C=,z =, A ( BC ) =a,b1,z,2,z =a,a,b,b, （AB）CA（BC） “”不满足结合律。 3063.3 序偶与笛卡尔乘积定理定理若A，B，C是三个集合，则有： (1)A（BC）=（AB）（AC） (2)A（BC）=（AB）（AC） (3)（AB）C=（AC）（BC） (4)（AB）C=（AC）（BC）证明：（2）设是A(BC)中的任一元素,则A（BC） x,y |xAyBC |xAyByC3073.3 序偶与笛卡尔乘积 |(xAyB)(xAyC) (

134、AB)(AC)即 A(BC)=(AB)(AC)例：设A=1，B=1，2，C=2，3 则A（BC） =11，2，3 =1，1，1，2，1，3 3083.3 序偶与笛卡尔乘积（AB）（AC）=11，212，3 =1，1，1，2，1，3 A（BC）=12=1，2 （AB）（AC） =1,1,1，21,2,1,3 =1，2 n个集合的笛卡儿乘积的定义个集合的笛卡儿乘积的定义：设A=Ai，iIn Ai=A1A2An = （A1A2）A3）An 3093.4 关系及其表示序偶a，b实际上反映了二个元素之间的关系，关系反映了事物的结构。1.关系：指事物之间（客体之间）的相互联系。日常生活中：父子关系，母子

135、关系，兄弟关系等均为二个客体之间的关系。而祖孙关系是三个客体之间的关系（父子关系和父子关系的合成）。n元笛卡尔积A1A2An是n元关系。 3103.4 关系及其表示定义若则是一个二元关系。即：序偶作为元素的任何集合。关系表示方法关系表示方法（1）枚举法（直观法、列举法）设R表示二元关系，用表示特定的序偶，若，则也可写成：x R y。3113.4 关系及其表示例：二元关系定义如图：可写成：由定义可见：关系是一个集合，定义集合的方法都可以来定义关系。（2）谓词公式表示法前面讲述，一个集合可用谓词公式来表达，所以关系也可用谓词公式来表达。3123.4 关系及其表示例：实数集合R上

136、的“”关系可表达为：大于关系：“”= 父子关系：“F”=（3）关系矩阵表示法规定：(a)二元关系中的序偶中左元素表示行，右元素表示列；(b)若，则在对应位置记上“1”，否则为“0”。3133.4 关系及其表示例1：设并定义为列出关系矩阵：例2：设X=a,b,c,Y=1,2, R2是的关系， 3143.4 关系及其表示是的全域关系， 3153.4 关系及其表示（4）关系图表示法规定：(a)把、集合中的元素以点的形式全部画在平面上；(b)若，则xi和yi之间画一箭头弧线，反之不画任何联线。例：是X中的二元关系，3163.4 关系及其表示用关系图表示：关系的定义域和值域：关系的定义域和

137、值域：定义定义设S是一个二元关系，D(s)是所有客体x的集合，对于一些y来说，若有，则称D(s)为 S的定义域（简称“域”），即 3173.4 关系及其表示设R(S)是所有客体y的集合，对于一些X来说，若有，则称集合R(S)是S的值域（简称“值”）,即：例：例：X=1,2,3,4,5,6, R为X到Y的二元关系，则一般情况，称X为R的前域前域，称Y为R的陪域陪域。 3183.4 关系及其表示关系和笛卡尔乘积关系和笛卡尔乘积笛卡尔乘积的任何子集都可以定义一种二元关系。例：X=1,2,3,4，Y=1,2，则 3193.4 关系及其表示均为二元关系。三个特殊关系：空白关系，全域关系，

138、恒等关系三个特殊关系：空白关系，全域关系，恒等关系定义定义集合X2定义了X集合中的一种关系，通称为X中的全域关系，用Ex表示：3203.4 关系及其表示空集也是的一个子集，它也定义了一种关系称为空白关系； X集合中的恒等关系，在全域关系和恒等关系中前域=定义域，陪域=值域。例：=，则同一域上的关系,可进行集合的所有运算。3213.5 关系的性质自反性自反性：定义定义设是集合中的二元关系，对于每一个（所有的）有，则称是自反关系，X中R是自反的例：设是自反的关系。 R的关系矩阵 3223.5 关系的性质定义定义设R是X中的二元关系，对于每一个，有x x，则称R是反

139、自反的关系，表示成：R是X中的反自反的关系 x x 。例：设X=1,2,3, 3233.5 关系的性质对称性对称性定定义设R是X中的二元关系，对于每一个来讲，如果每当有xRy，则必有yRx，则称R是X中的对称关系，并表示成：R是X中的对称关系 S4既不是自反的，又不是反自反的3243.5 关系的性质例：设X=1,2,3,R= 则R是对称的关系定义定义设R是X集合中的二元关系，对于每一个来讲，如果每当xRy和yRx就必有x=y，则称R是反对称的关系。3253.5 关系的性质即当且仅当 X中的R才是反对称的。讨论定义：（1）前件为“T”，则x=y也为“T”,则为反对称的；（

140、2）前件为“F”，则有三种情况：后件（x=y）不论是真还是假，命题公式为“T”。下面举例说明：3263.5 关系的性质例：设X=a,b,c均是反对称的3273.5 关系的性质例：X=a,b,c,下列关系不是对称的，也不是反对称的3283.5 关系的性质X上的恒等关系是自反、对称、反对称的。 3293.5 关系的性质X上的全域关系：是自反的，对称的 X上的空关系是反自反、对称、反对称的。 3303.5 关系的性质传递性传递性：定义定义设R是X中的二元关系，对于每一个来说，如果每当，就必有则称R是可传递的，并表示成：X中R可传递讨论定义：（1）前件为“T”，则xRz也为“

141、T”，R是可传递的；（2）前件为“F”，有三种情况后件不论是真还是假，命题为“T”，则R是可传递的 3313.5 关系的性质例：设X=a,b,c，则下列关系均是可传递的3323.5 关系的性质下列关系是不可传递的：3333.5 关系的性质确定二元关系性质举例确定二元关系性质举例（1）设X=1,2,3，反自反，反对称，可传递的；反对称的； 3343.5 关系的性质自反，对称，反对称，可传递的；自反，对称，可传递的；反自反的，对称的，反对称的，可传递的。 3353.5 关系的性质（2）若，则X上的空关系自反的，反自反的，对称的，反对称的，可传递的。3363.6 复合关系和逆关系关系的

142、复合关系的复合定义定义设（R关系），（S关系），于是可用（RS）的关系，称 RS为R和S的复合关系，并规定为：例：设A=1,2,3,4,5，R,S均为AA的关系，且R=,S=则RS=， SR=3373.6 复合关系和逆关系“”是不可交换的。讨论：（1）RS为新的二元关系（2） RSXZ（3）当R与S，才有 RS3383.6 复合关系和逆关系定理定理设则有：可见合成关系图下面定义关系R 的幂次3393.6 复合关系和逆关系定义定义给定集合X，R是X中的二元关系，设于是R的n次幂可以定义成：（1） =X集合中的恒等关系（2）例：设R,S是中的二元关系，且则：3403.

143、6 复合关系和逆关系例：3413.6 复合关系和逆关系若|X|=n，则X中的二元关系R的幂次值是有限的。一般不用求出超过X的基数次幂。复合关系的矩阵表示复合关系的矩阵表示设有三个集合：而|X|=m,|Y|=n,|Z|=p，则关系矩阵3423.6 复合关系和逆关系例：设X=1,2,3,4,5,R,S均是X中的二元关系，R=,S= 3433.6 复合关系和逆关系逆关系逆关系定义定义设X,Y是二个集合，若R是XY的关系，从YX的关系，称为R的逆关系，用表示，或用表示。讨论定义：（1）只要将R中每一个序偶中的元素全部调换位置，就可得到R的逆关系（2）设的关系矩阵为的转置矩阵；（3

144、）在R的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭头改变与否无关） 3443.6 复合关系和逆关系例：X=0,1,2，R=, =,3453.6 复合关系和逆关系定理定理设，则可有：证明：对于任一来讲，若有同样 x,y,z分别为X,Y,Z中的任一元素， 3463.6 复合关系和逆关系例：，试求： 3473.6 复合关系和逆关系定理定理设R是X中的二元关系，当且仅当则R才是对称的。3483.6 复合关系和逆关系证明：充分性：R是对称的对于任一必要性： R是对称的，对任一 R一定是对称的3493.6 复合关系和逆关系定理定理给定集合X,Y, ，于是可有 3503.6

145、复合关系和逆关系证明：（1）设是R中的任一元素，则（10）设，对任一 3513.6 复合关系和逆关系由（2）由（7） 3523.7 关系的闭包运算定义定义给定集合X，R是X中的二元关系，若有另一R满足下列条件：（1）R是自反的（对称，可传递的）；（2）（3）对于任一自反（对称，传递的）关系R，若，则则称R是R的自反（对称，传递的）闭包，并依次用r(R),s(R),t(R)来表示之。3533.7 关系的闭包运算讨论定义：（1）已知一个集合中的二元关系R，则r(R),s(R),t(R)是唯一的，它是包含R的最小的自反（对称，传递）关系；（2）若R是自反（对称，传递）的，则r(R

146、),s(R),t(R)就是R本身。（3）若R不是自反（对称，传递）的，则我们可以补上最少序偶，使之变为自反、对称、传递关系，从而得到r(R),s(R),t(R)；3543.7 关系的闭包运算例：设X=a,b,R=，r(R)=,s(R)=,t(R)=R例：求t(R)需要特别小心，要进行多次添项。设X=a,b,c,R=，求r(R),s(R),t(R)解：r(R)= s(R)= t(R)=3553.7 关系的闭包运算定理定理给定集合X，R是X中的二元关系，于是可有：（1）当且仅当r(R)=R，则R是自反的；（2）当且仅当s(R)=R，则R是对称的；（3）当且仅当t(R)=R，则R是可传递的

147、。定理定理R是X中的二元关系是X中的恒等关系，则有证明：按定义证：（1）设，则R是自反的， 3563.7 关系的闭包运算（3）设有任一R也是自反的，且则定理定理给定集合X，R是X中的二元关系，则有定理定理设X是一集合，R是X中的二元关系，则： 3573.7 关系的闭包运算例：X=a,b,c,R=，|X|=3,则定理定理设|X|=n，R是X中的二元关系，则 3583.7 关系的闭包运算例：X=a,b,c,d,R=,则定理定理设X是一集合，R是X中的二元关系，则有：（1）r(S(R)=S(r(R); （2）r(t(R)=t(r(R);（3）t(S(R) S(t(R)。 3593.

148、7 关系的闭包运算证明：（1）r(S(R)常用下列符号表示一些闭包： “R加”：，传递闭包， “R星”：，自反可传递闭包， 3603.7 关系的闭包运算例：设X=a,b,c,R=（1）rS(R)=r = Sr (R)=s =（2）rt(R)=r= tr(R)=t=（3）tS(R)=t = St(R)=S= t(S(R) St(R) 3613.8 集合的划分和覆盖集合的划分和覆盖定义定义给定一非空集合，又设若（1）（2）则称A为S的覆盖。例：S=a,b,c，A=a,b,b,c，B=a,a,b,c， C=a,b,c，D=a,b,a,c 均为S的覆盖。 3623.8 集合的划分和覆盖集合

149、的划分和覆盖例：四个半圆覆盖一正方形。定义定义给定一非空集合S，设非空集合如果有：或（i,j=1,2,m） 363 3.8 集合的划分和覆盖集合的划分和覆盖则称集合A是集合S的一个划分。讨论定义：（1）划分和覆盖主要差别在第（2）条；（2）划分A中的元素，称为划分的类，在定义中均是A中的一个类，类的个数称为划分的秩；（3）若A为有限集合，则A的秩是有限的，为|A|，若A为无限集合，则划分的秩是无限的；（4）集合的划分必定是一个覆盖，而覆盖不一定是划分；（5）集合S上的秩最大的划分称最大划分，最小的称最小划分。 364 3.8 集合的划分和覆盖集合的划分和覆盖例：设S=a,b,

150、c，下列均为S的一个划分：类有二个a,b,c, =2（秩）；类有二个a ,b ,c, =2（秩）；类有二个a,c,b, =2（秩）；最大划分，秩为3=|S|；最小划分，秩为1。例：四个直角三角形组成了正方形的一个划分秩=4365 3.8 集合的划分和覆盖集合的划分和覆盖定义定义设A和A是非空集合S的二种划分，并可表示成：若A的每一个类都是A的某一个类的子集，则称划分A是划分A的加细，或讲A加细了A，若A加细了A且则称A是A的真加细。讨论定义： A加细了A，一定有|A|A|（秩），若|A|A|，则一定为真加细。 3663.8 集合的划分和覆盖集合的划分和覆盖例：S=a

151、,b,c,d,S的划分：A=a,b,c,d,A=abc,d，则A是A的真加细 A=abcd,则A 是A的真加细 3673.9 等价关系等价关系与等价类定义定义设X是一个集合，R是X中的二元关系，若R是自反的，对称的和可传递的，则称R是等价关系。例：下列关系均为等价关系（1）实数（或I、N集上）集合上的“=”关系（相等）（2）人类中的同姓关系（3）命题集合上的等价关系例：设X=1,2,3,4,5,6,7，为整数3683.9 等价关系等价关系与等价类试验证R是等价关系，画出R的关系图，列出R的关系矩阵解：（1）R=（2）R的关系矩阵 3693.9 等价关系等价关系与等价类R满足自反、对称

152、和可传递的，R是一等价关系定义定义设若对于某个整数n有(x-y)=n m, （整数），则称x模m等于y，记作：定理定理任何集合（I的任何子集X中）的模m等价，是一个等价关系。 3703.9 等价关系等价关系与等价类定义定义设R是X集合中的等价关系，对于任何的来讲，可把集合规定成：并称是由生成的R等价类。讨论定义：（1）等价类是一个集合，由定义中可见（2）中的元素是在等价关系R中，所有与x 具有关系的元素所组成的集合，且 3713.9 等价关系等价关系与等价类例：设X=a,b,c,d,R是X中的等价关系，R=则定理定理设X是一个集合，R是X中的等价关系，则（1）若，则

153、（2）对于所有的，或者或者（3） 3723.9 等价关系等价关系与等价类例：设X=N，关系R= 可被3整除是一等价关系，则R可以找出三个等价类：=0，3，6，9，此集合中的元素除以3的余数为“0”； =1，4，7，10，此集合中的元素除以3的余数为“1”；=2，5，8，11，此集合中的元素除以3的余数为“2”。例：X为全班同学的集合，则班中同姓关系是一个等价关系，（1）任何一个人均某一个等价类，王某某王 R张某张R 3733.9 等价关系等价关系与等价类（2）任何二个姓的等价类，只有二种可能一种：王 R= 李R 二种：王 R李R= （3）全班同学的集合=同姓关系等价类的并集=王

154、李（4）所有等价类的集合，一定导致全班同学集合的一个划分：A=王R，李R. 3743.9 等价关系等价关系与等价类定理定理设X是一非空集合，R是X中的等价关系，R等价类的集合xR| x X是X的一个划分，且此集合称为X按R的商集，用表示之。例：设X=x1,x2.xn （1）X集合中的全域关系，，它是一个等价关系， X按 R1的商集它形成了X的一个最小划分 3753.9 等价关系等价关系与等价类（2）X中的恒等关系它形成了X的一个最大划分例：X为全班同学的集合，|X|=n, (nN)（1）同学关系R1是一个等价关系，（2）按指纹的相同关系R2是一个等价关系，它形成了全班同学的最大划

155、分 3763.9 等价关系等价关系与等价类（3）同姓关系R3是一等价关系张 R3，李R3，它形成了全班同学的既不是最大，又不是最小划分3773.9 等价关系等价关系与等价类定理定理X是一非空集合， A为X的一个划分，且A=A1,A2,.An，则由A导出的X中的一个等价关系例：Xa,b,c,d，A=a,b,c,d则 R(a,b a,b)(c,d c,d) =, 由此我们看到：集合X上的等价关系与X的划分之间有对应关系。3783.10 相容关系关系定义定义给定一个集合X，R是X中的二元关系，如果R是自反、对称的，则称R是相容关系。例：设X=ball,bed,dog,let,egg,5个英文单词

156、定义X中一个二元关系：R= 有相同的字母则R是自反的，对称的，但不可传递(ball R bed) (bed R egg) (ball R egg)则R= 3793.10 相容关系关系3803.10 相容关系关系定义定义设X是一个集合， R是X中的相容关系，假定 AX，若任一 xA都与A中的其它所有元素有相容关系，而（X-A）中没有一个元素与A中的所有元素有相容关系，则称子集A为相容关系R的一个最大相容类。例：上例中均是X中的最大相容类,且定义了X的一个覆盖。同样已知X集合的一个覆盖 3813.10 相容关系关系则一定可以求出相对应的相容关系来：讨论等价关系和相容关系后可得到结论：集

157、合X上的相容关系R的所有最大相容类集合A1,A2,.Am构成集合X的一个覆盖。即：而集合X上的等价关系R的所有等价类集合构成X的一个划分3823.10 相容关系关系求最大相容类的方法：关系图法：确定最大完全多边形每个顶点都与其他所有顶点相联结的多边形。 (1)孤立结点是最大的完全多边形； (2)二个相互联结的结点是最大完全多边形； (3)三角形是三个结点的最大完全多边形； 3833.10 相容关系关系(4)四个结点； (5)五个结点; 画出简化相容关系的关系图后，先结点最多的完全多边形，以后逐次减少。3843.10 相容关系关系例：已知相容关系图，求出最大相容类3853.10 相容关系关系

158、最大相容类集合为3863.11 序关系定义定义设R是P中的二元关系，如果R是自反的，反对称和可传递的，则称R是P中的偏序关系（或称偏序），并用符号“”表示，而序偶P，则称为偏序集合。讨论定义：（1）“”不单纯意味着在实数中的关系，而是代表更为普遍的关系（具有自反，反对称和可传递性的关系）；（2）若，“xy”读作： “x小于或等于y”“y包含x”“x在y的前面”等；3873.11 序关系（3）R是集合P中的偏序关系，则也是P中的偏序关系，即R用“”表示，则用“”表示；（4）若P，是一个偏序集合，则P，也一定是偏序集合，且偏序集合是一个序偶，左元素为集合P，右元素为偏序关系。例：（1）在

159、领导机构的集合中“领导和被领导的关系”是偏序关系；（2）在I（整数）集合中，“”、“”均是偏序关系； 3883.11 序关系例：中的“”（整除）=而“”（整倍数）=均是偏序关系。 3893.11 序关系定义定义R是集合X中的二元关系，若R是非自反的，反对称的和可传递的，则称R是拟序关系（串序），并用符号“”表示。而X,称为拟序集合。讨论：（1）拟序关系一定反对称的（2）拟序关系也可用偏序关系来定义： 3903.11 序关系定义定义设P，是一个偏序集合，若对于每一个，或者xy，或者yx，即，则“” 称为全序关系，而P，称为全序集合（线序集合）。定义定义在偏序集合P，中，若且具有xy或y

160、x，则称x和y是可以比较的，否则称x,y是不可比较的。推论推论在偏序集合中，一般情况下，一定是有的元素可以比较的，有的元素是不可比较的。在全序关系中，所有的元素均是可以比较的。 3913.11 序关系定义定义若集合X上的二元关系R是全序关系，且X的任一非空子集，都有一个最小元素，则称R为良序关系，并称为良序集合。讨论定义：（1）良序关系比全序关系多了一个条件，即在全序关系中，X集合的任一非空子集均有一个最小元素；（2）每一个有限集合X上的全序关系必定是良序关系。例：设A=1,2,3,4定义A上的“” = 3923.11 序关系偏序集合和哈斯图偏序集合和哈斯图定义定义在偏序集合P，中，若有

161、且xy和，又不存在其它元素z能使则称元素y盖住x，盖住集记为COV(P)= Y盖住x给定偏序集P，它的盖住集是唯一的。我们可以画出盖住集的关系图，称为P，的哈斯图。3933.11 序关系（2）若，且xy和，则把x画在y的下面；（3）若y盖住x，则在x和y之间画一条联线，并箭头向上，若y不盖住x，但又存在“”关系，则必定通过x和y之间的其它中间结点把x和y联结起来；（4）所有边的方向均是向上的，所以实际画时，箭头均可省去。例：(a)设 “”表示P中元素的小于和等于关系，（1）用“”表示P中的结点（具有自反性）；画P，的哈斯图的方法： 3943.11 序关系则P1，是一偏序集合，全序

162、集合，良序集合其哈斯图为： (b)若设是一偏序集合，例：设X=2,3,6,12,24,36“”定义为：若 x整除y，则xy，X，是一偏序集合,3953.11 序关系例：(a)设X=a,b,(X)= 是一偏序关系，其哈斯图为： (b)设X=a,b,c的哈斯图为： 3963.11 序关系定义定义设为一偏序集，且QP(1)若对每一个qQ有qq,则称qQ为Q的最小元素。(2)若对每一个qQ有qq,则称qQ为Q的最大元素。(3)若qQ，且不存在一个qQ，使q q且q q，则称q为Q的极小元素。(4)若qQ，且不存在一个qQ，使q q且q q，则称q为Q的极大元素。讨论：(1) qQ，Q的极

163、大，小，最大，小元，若有的话，必定在Q中。3973.11 序关系(2)最大，最小元是Q中所有元素比较而言的，极大，极小元是对Q中能够比较的元素而言的。(3)Q中如有最大，最小元则一定是唯一的，极大，极小元一定存在，且不一定是唯一的。定义定义给，且QP，若(1)对每个qQ有qq,则称qP为Q的上界，其中最小的一个，称为Q的最小上界，记为LUB(上确界)。(2)对每个qQ有qq,则称qP为Q的下界，其中最大的一个，称为Q的最大下界，记为GLB(下确界)。3983.11 序关系讨论定义：(1)上，下界是对Q中所有元素比较而言的。(2)Q若有上，下界，则不一定是唯一的。(3)Q若有LUB，GLB

164、，则Q一定有上，下界，且是唯一的。(4)Q的上，下界，LUB，GLB，则可能在Q中，可能不在Q中，但一定在P中。3993.11 序关系例：设X=a,b,c,是一偏序集合，其哈斯图如右，求下列子集的上界、下界、最小上界和最大下界4003.11 序关系bb ,bba,bb,ca,b,cbcc ,a,ca,ca,b,ca,ccbb ,a,b,ca,b,ca,bb,ca,b,ca,b,ca,bca,b,ca,b,cabca,ca,ca,b,cacGLB下界下界LUB上界上界子集子集401第四章函数函数是二元关系中特殊的一类，也就是说，函数是一种特定类型的二元关系。本章讨论的是离散函数，它能把一个

165、有穷集合变换到另一个有穷集合。在这章我们主要讨论：函数定义、特殊函数及其性质、函数的运算。402第四章函数4.1 函数的概念4.2 逆函数和复合函数403第四章函数教学目的及要求：教学目的及要求：深刻理解和掌握函数的基本概念。教学内容：教学内容：函数的概念、逆函数和复合函数。教学重点：教学重点：函数和复合函数。教学难点：教学难点：4044.1 函数的概念函数的定义函数的定义：定义定义设X和Y是任意两个集合，f是从XY的一种关系，若对于每一个xX，都存在一个唯一的 yY，能使 f ，则称关系f为函数（映射）,并记为： f：XY。讨论定义：（1）f：XY中，若，则称x为自变量

166、，与x对应的y称作f作用下的象点（值）；也可用y=f(x)表示，y称作函数f在x点处的值。4054.1 函数的概念（2）X中每一个元素均有定义，函数f的定义域（3）对应于某一个，其值f(x)是唯一的，即（4）f 值域有时也记为Rf 集合 Y称为f 的共域4064.1 函数的概念例：判定下列关系是否为函数是函数不是函数值不是唯一的不是函数 4074.1 函数的概念例：设X=Y=R（实数）值是唯一的这不是函数，不满足值唯一性4084.1 函数的概念定义定义给定函数f:AB和g:CD，如果A=C，B=D，并对所有的或都有f(x)=g(x)，则称函数f和g是相等的，即f=g。函数

167、的构成函数的构成例：设X=a,b,c，Y=0,1，则中，有个子集，4094.1 函数的概念但在64个子集中只有8个符合函数的定义，这8个函数为：4104.1 函数的概念讨论：从此例中可得到三点结论：（1）设|X|=m，|Y|=n，则函数f: XY中均是m个序偶的集合；（即序偶个数=定义域的基数）（2）X中每一个元素所对应的象点f(x)可能是Y中n个，从X-Y的所有函数个数 4114.1 函数的概念（3）XY有别函数的个数和子集个数的关系为：即二个集合之间能构成的函数个数比能构成的二元关系数少得多 3.几种特殊函数几种特殊函数定义定义给定函数f: XY，如果值域则称f为满射函数

168、。 4124.1 函数的概念例：满射函数一定有： (1)|X|Y|定义定义给定f: XY，如果有或者：则称f是入射函数。 4134.1 函数的概念入射函数有：定义定义给定函数f: XY，如果f既是满射函数，又是入射函数，则称f为双射函数。（或称“一一对应函数”，“一对一满射函数”） 4144.1 函数的概念双射函数一定有：（1）（值域）（2）（定义域）|X|=|Y| 例：在全班同学的集合中，设：X=序号，Y=姓名则：f: XY是一双射函数（序号和姓名的关系）4154.2 逆函数和复合函数设，则现在讨论函数能否像二元关系那样得到逆函数呢？先举一例例：定义一函数由例题可见：

169、的定义域不是Y，而是Y的子集不满足函数定义：即值是唯一的是一种二元关系，而不是函数 4164.2 逆函数和复合函数（3）一个函数的反函数存在的话，则此函数一定是双射函数，而入射，满射函数的逆关系均不满足函数的定义（4）为了和逆关系相区别，函数f的用“逆函数” 来表示定理定理如果f: XY是双射函数，则有：也为双射函数。定义定义设是一双射函数，称为f的逆函数。4174.2 逆函数和复合函数定义定义设f: XY和g:WZ是二个函数，若则：称g在函数f的左边可复合。讨论定义： (1)两个函数的复合是一个函数。 (2)函数称为f和g的左复合，这里和习惯上符合函数的书写求得一致。例：s

170、in(ln x)，先求ln x，然后求sin(ln x)4184.2 逆函数和复合函数定理定理设f:XY和g:YZ是二个函数，于是复合函数是一个从X到Z的函数，对于每一个有：证明：有定义可知是从XZ的函数，即设：xX 由f: XY得y=f(x)设：yY 由g:YZ得z=g(y)由得： 4194.2 逆函数和复合函数例：设X=1,2,3, Y=p,q, Z=a,b f: XY= g:YZ=则：是XZ的函数上例的函数复合图为：4204.2 逆函数和复合函数f: XY g:YZ ：XZ函数的复合运算不满足交换律。 4214.2 逆函数和复合函数定理定理函数的复合运算是可结合的，即如果f,

171、g,h均为函数，则有：证明：函数也是一种二元关系，二元关系的复合是满足结合律的，函数的复合也是满足结合律的。例：I是整数集合，f：II定义成f(i)=2i+1，求复合函数并证明它满足结合律。4224.2 逆函数和复合函数解： 4234.2 逆函数和复合函数定理定理设f: XY，g:YZ，是一合成函数，则： (1)如果f和g都是满射函数，则也是满射函数； (2)如果f和g都是入射函数，则也是入射函数； (3)如果f和g都是双射函数，则也是双射函数。证明：（2）设任一 f为入射函数，又g为入射函数,且 4244.2 逆函数和复合函数即是任一的，也是单射函数。可用同样的方法

172、证明（1）和（3）4254.2 逆函数和复合函数例：设是负整数集合，定义二个双射函数f和g， f(x)= - x =，g(x)= x-1=，是一双射函数。4264.2 逆函数和复合函数定义定义给定f: XY，如果对于所有的和某一个yY ，有f(x)=y，则称f为常函数。例：4274.2 逆函数和复合函数定义定义给定，若对所有的有，即则称为恒等函数。例：4284.2 逆函数和复合函数定理定理对于任何函数f: XY，其中是XX的恒等函数，是YY的恒等函数，则有 XXYY4294.2 逆函数和复合函数定理定理如果函数f: XY有逆函数则且证明：设任一，则此定理说明：可用

173、双射函数f和的复合来生成恒等函数。 4304.2 逆函数和复合函数定理定理若f是一双射函数，则证明：设任一则定理定理设f: XY和g:YZ,且f和g均为双射函数，则有 4314.2 逆函数和复合函数证明：由给定条件f,g均为双射函数, 则均为双射函数设任一则y=f(x)，z=g(y) 且 x是任意的有 432集合论小结通过第三，第四章的学习应该达到下面的基本要求：（1 1）能够正确地表示一个集合，会画文氏图。（2 2）能判定元素是否属于给定的集合。（3 3）能判断两个集合之间是否存在包含、相等或真包含的关系。（4 4）能熟悉地进行集合的并，交，相对补，绝对补，对称差运

174、算，会计算幂集。（5 5）能正确地使用集合表达式、关系矩阵和关系图表示给定的二元关系。（6 6）给定A上的关系R（可能是集合表达式，也可能是关系矩阵或关系图），能判别R的性质。433集合论小结（7 7）给定关系R和S，求RS；给定A上的关系R，求Rn，r(R)， s(R)，t(R)。（8 8）给定A上的等价关系R，求所有的等价类和商集A/R，或者求与R相对应的划分，以及给定A的划分，求对应的等价关系。（9 9）给定A上的偏序关系，画出偏序集的哈斯图；给定偏序集的哈斯图，求A和的集合表达式。（1010）确定偏序集的极大元、极小元、最大元、最小元、最大下界和最小上界。（1111）给定集合A

175、，B和f，判别f是否为A到B的函数，如果是，说明是否为入射、满射、双射。434习题选讲例例1.设A，B，C，D代表任意集合，判断以下命题是否恒真，如果不是，请举一反例。(1)AB CDAC BD(2)AB CDA-DB-C(3)AB B=A(B-A)(4)A-B=B-A A=B解：(1)不为真。举反例如下：令A1,B=1,4,C=2,D=2,3则AB且CD，但AC BD，与结论矛盾。435习题选讲(2)由于CDDC，又由A B可得 ADBC即AD BC成立。(3)由于A(BA)=A B故有：B= A(BA) B= A B A B即A B的充要条件为B= A B或A=AB或AB= 436习题选

176、讲(4)易见，当A=B时，必有A-B=B-A 由A-B=B-A得(A-B)B=(B-A)B 即：(AB)B=(BA) B 即：B-A= BA同理可证：AB从而得到：AB437习题选讲例例2.设：A、B是任意的集合(1) 试证明(A)(B)=(AB)(2) (A)(B)=(AB)成立吗？为什么？解：(1)证明 S(A)(B)，则S(A)且S(B)，因此： SA且SB S AB 即S(AB) (A)(B)(AB)反之，设S(AB)，则S AB， 438习题选讲因此SA且SBS(A)且S(B)于是S(A)(B)(AB)(A)(B)由上知(A)(B)(AB)(2) (A)(B)(AB)成立。其证明如

177、下：设：S(A)(B)，则S(A)或S(B)因此 SA或SB SAB即S(AB)故(A)(B)(AB)成立439习题选讲(AB) (A)(B)不成立设：S(AB)，则SAB。但此时无法推断SA，也无法推断SB，因此既不能得出S(A)，也不能得出S(B)。例如：设 A=a,c，B=c,b则 AB=a,b,c，设 S=a,b，则SAB即 S(AB)但 S(A)且S(B)因此 S (A)(B)440习题选讲例3.设S=1,2,3,10，是S上的整除关系，求的哈斯图，并求其中的最大元，最小元。最小上界，最大下界。分析：画哈斯图的关键在于确定结点的层次和元素间的盖住关系。画图的基本步骤是：(1)确定

178、偏序集中的极小元，并将这些极小元放在哈斯图的最底层；(2)若第n层的元素已确定完毕，从A中剩余的元素中选取至少能盖住第n层中一个元素的元素，将这些元素放在哈斯图的第n+1层。441习题选讲在排列结点的位置时，注意把盖住较多元素的结点放在中间，将只盖住一个元素的结点放在两边，以减少连线的交叉；(3)将相邻两层的结点根据盖住关系进行连线。442习题选讲在画哈斯图时应该注意下面几个问题：(1)哈斯图中不应该出现三角形，如果出现三角形，一定是盖住关系没找对。纠正的方法是重新考察这3个元素在偏序集中的顺序，然后将不满足盖住关系的那条边去掉。(2)哈斯图中不应该出现水平线段。出现这种错误的原因在于没有将“

179、较大”元素放在“较小”元素的上方。纠正时只要根据“大小”顺序将“较大”的元素放到更高的一层，将水平线改为斜线就可以了。(3)哈斯图中要尽量减少线的交叉。图形中线的交叉多少主要取决于同一层结点的排列顺序，443习题选讲如果出现交叉过多，可以适当调整结点的排列顺序。最后，如何确定哈斯图中极大元、极小元、最大元、最小元、最小上界和最大下界。方法如下：(1)如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图中既无最小元，也无最大元。（除只有唯一孤立结点的情况）(2)除了孤立结点以外，其它的极小元是图中所有向下通路的终点，其它的极大元是图中所有向上通路的终点。444习题选讲例例4.设Z+=x

180、|xZx0，1， 2是Z+的2个划分， 1=x|x Z+， 2=Z+ ，求划分1， 2所确定的Z+上的等价关系。分析：等价关系和划分是两个不同的概念。等价关系是有序对的集合，而划分是子集的集合。但对于给定的集合A，A上的等价关系R和A的划分是一一对应的。即：Rx 和y在的同一划分块里。本题中， 1的划分块都是单元集，没有含两个以上元素的划分块；445习题选讲2中只有一个划分块Z+， Z+包含了集合中的全体元素。R1就是Z+上的恒等关系； R2就是Z+上的全域关系。例例5.对下面给定的集合A和B，构造从A到B的双射函数分析：构造从集合A到B的双射函数，一般可采用下面的方法：(1)若A，B

181、都是有穷集合，可以先用列元素的方法表示A，B446习题选讲然后，顺序将A中的元素与B中的元素建立对应。(2)若A，B是实数区间，可以采用直线方程作为从A到B的双射函数。例如：A1,2， B2,6是实数区间。先将A，B区间分别标记在直角坐标系的x轴和y轴上，过(1,2)和(2,6)两点的直线方程将A中的每个数映到B中的每一个数。因此，该直线方程：就是从A到B的双射函数。447习题选讲这种通过直线方程构造双射函数的方法对任意两个同类型的实数区间(同为闭区间、开区间或半开半闭区间)都是适用的。此外，对于某些特殊的实数区间，可能选择其它严格单调的初等函数更方便。对于本题:(3)A是一个无穷集合，B是自

182、然数集N 只须将A中的元素排成一个有序序列，且指定这个序列的初始元素，这就叫做把A“良序化”。例如：构造从整数集Z到自然数集N的双射，如下排列：448习题选讲Z：0，-1，1，-2，2，-3，3，.N：0， 1，2， 3，4， 5，6，.即：显然f是从Z到N的双射。 449第三编第三编代数系统代数系统本篇用代数方法来研究数学结构,故又叫代数结构,它将用抽象的方法来研究集合上的关系和运算。代数的概念和方法已经渗透到计算机科学的许多分支中,它对程序理论,数据结构,编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义。本篇讨论一些典型的代数系统及其性质（包括格）。 450第五章第五章代数结构

183、代数结构 5.1 代数系统的引入5.2 运算及其性质5.3 半群5.4 群与子群5.5 阿贝尔群和循环群5.6* 陪集与拉格朗日定理5.7 同态与同构451第五章第五章代数结构代数结构教学目的及要求：教学目的及要求：深刻理解和掌握代数系统的基本概念和运算。教学内容：教学内容：代数系统的引入、运算及性质、半群、群与子群、阿贝尔群和循环群、陪集与拉格朗日定理、同态与同构、环和域。教学重点：教学重点：群、环、域的概念及运算、同态与同构。教学难点：教学难点：同态与同构的概念。4525.1 代数系统的引入定义定义设Z是一个集合,f是一个函数,f:ZnZ,则称f为Z中的n元运算,整数n称为

184、运算的阶。若n=1,则称f： ZZ为一元运算；若n=2,则f： Z2Z为二元运算。本章主要讨论一元运算和二元运算。例：（1）在整数I和实数R中,+,-,均为二元运算,而对而言就不是二元运算（2）在集合Z的幂集(z)中,均为二元运算,而“”是一元运算；4535.1 代数系统的引入（3）命题公式中,均为二元运算,而“”为一元运算（4）双射函数中,函数的合成运算是二元运算；二元运算常用符号：+,等等。定义定义一个非空集合A连同若干个定义在该集合上的运算f1,f2,.,fk所组成的系统就称为一个代数系统，记作。4545.1代数系统的引入定义定义若对给定集合中的元素进行运算,而产生的象点仍在该

185、集合中,则称此集合在该运算的作用下是封闭的。在f：Z2Z二元运算的定义中,本身要求满足运算是封闭的。例：（1）在正整偶数的集合E中,对,+运算是封闭的；在正整奇数的集合中,对运算是封闭的,而对+运算不是封闭的。（2）在前例中,R,I集合中+,-,运算； (z)的元素中, ,运算等均为封闭的。4555.2 运算及其性质定义定义设*是集合S上的二元运算,对任一x,yS有xyS则称运算在S上是封闭的。定义定义设*是集合S上的二元运算,对任一x,yS有xy=y x,则称运算在S上是可交换的（或者说在S上满足交换律）。456 5.2 运算及其性质定义定义设*是集合S上的二元运算,对任一x,y,z

186、 S都有（x y） z=x （y z）,则称运算在S上是可结合的（或者说*在S上满足结合律）。定义定义设和是集合S上的二个二元运算, 对任一x,y,z S有 x （y z）=（x y）（x z）；（y z） x=（y x）（z x）,则称运算对是可分配的（或称对满足分配律）。 4575.2 运算及其性质定义定义设，是定义在集合S上的两个可交换二元运算，如果对于任意的x,yS，都有：x (x y)=x；x (xy)=x则称运算和运算满足吸收律。定义定义设*是S上的二元运算,若对任一x S有x x=x,则称满足等幂律。讨论定义：1)S上每一个元素均满足xx=x,称在S上满足幂等律；2)若在

187、S上存在元素xS有x x=x,称x为S上的幂等元；3)由此定义,若x是幂等元素,则有x x=x和xn=x成立。4585.2 运算及其性质例：（1）在实数集合R中,+,是可交换,可结合的,对+是满足分配律的,“0”对+是等幂元素,而其它不为等幂元素,对“-”法是不可交换,不可结合的；（2）在(z)中, ,均是可交换,可结合的, 对 , 对均是可分配的； (z)中任一元素,对,均是等幂元素。满足等幂律；而(z)中,对称差分是可交换,可结合的。除(s) =以外不满足等幂律。 = ,而除以外的A (z)有A AA。4595.2 运算及其性质定义设*是S上的二元运算,对任一xS,则：x1=x, x2=x

188、*x,xn=xn-1*x定理设*是S上的二元运算,且x S,对任一m,n I+有（1）xmxn=xm+n（2）(xm)n=xmn证明：(1) xmxn= (xm x) x x = (xm+1 x) x x n n-1 =.= xm+n (2)(xm)n= xm xm= xm+m xm xm =xmn n n-1 4605.2 运算及其性质下面定义特异元素幺元,零元和逆元。定义定义设*是集合Z中的二元运算,(1)若有一元素el Z,对任一x Z有el*x=x；则称el为Z中对于*的左幺元(左单位元素)；(2)若有一元素er Z,对任一x Z有x* er=x；则称er为Z中对于*的右幺元（右单元元

189、素）。定理定理若el和er分别是Z中对于*的左幺元和右幺元,则对于每一个x Z，可有el= er = e和e*x=x* e=x，则称e为Z中关于运算* 的幺元，且e Z是唯一的。4615.2 运算及其性质 el和er分别是对*的左,右左元，则有el * er = er = el 有el = er = e成立。（2）幺元e是唯一的。用反证法：假设有二个不同的幺元e1和e2,则有e1* e2= e2= e1,这和假设相矛盾。若存在幺元的话一定是唯一的。例：（1）在实数集合R中,对+而言, e+=0；对而言, e*=1 ；（2）在(E)中,对而言, e =E（全集合）；对而言, e =（空集）

190、；4625.2 运算及其性质（3）双射函数中,对“”而言， e =Ix（恒等函数）；（4）命题逻辑中，对而言，e =F（永假式）；对而言， e =T（永真式）。定义定义设*是对集合Z中的二元运算，（1）若有一元素l Z，且对每一个x Z有 l *x= l ，则称l 为Z中对于*的左零元；（2）若有一元素r Z，且对每一个x Z有 x* r= r ，则称r为Z中对于*的右零元。4635.2 运算及其性质定理定理若l和r分别是Z中对于*的左零元和右零元，于是对所有的x Z，可有l = r =，能使*x=x*=。在此情况下， Z是唯一的，并称是Z中对*的零元。证明：方法同幺元。例：（1）在实数集合

191、R中，对而言,，L = r =0 （2）在(E)中，对而言， = ；对而言， = E ；（3）命题逻辑中，对而言， =T ；对而言， = F。4645.2 运算及其性质定义定义设*是Z中的二元运算，且Z中含幺元e，令x Z，（1）若存在一xlZ，能使xl *x= e，则称xL是x的左逆元,并且称x是左可逆的；（2）若存在一xr Z，能使x* xr = e，则称xr是x的右逆元，并且称x是右可逆的；（3）若元素x既是左可逆的，又是右可逆的，则称x是可逆的，且x的逆元用x-1表示。4655.2 运算及其性质定理定理设Z是集合，并含有幺元e 。*是定义在Z上的一个二元运算，并且是可结合的。若x

192、Z是可逆的，则它的左逆元等于右逆元，且逆元是唯一的。证明：（1）先证左逆元=右逆元：设xL和xr分别是x Z的左逆元和右逆元，x是可逆的和*是可结合的（条件给出） xl *x=x* xr = e xl *x* xr =（ xl*x）* xr = e * xr= xr ； xl *x* xr = xl*(x* xr) = xl* e = xl xr = xl4665.2 运算及其性质（2）证明逆元是唯一的（若有的话）：假设x1-1和x2-1均是x的二个不同的逆元，则x1-1= x1-1*e= x1-1 *（x* x2-1 ）=（ x1-1 *x）* x2-1 = e * x2-1 = x2-

193、1，这和假设相矛盾。x若存在逆元的话一定是唯一的。推论推论(x-1)-1 =x , e-1= e证明： x-1 *x= (x-1)-1 *（ x-1 ）=x* x-1 = e 有(x-1)-1 =x e-1 * e= e= e* e 有e-1= e 例：（1）在实数集合R中，对“+”运算，对任一xR有 x-1 =-x，x+（-x）=0，加法幺元4675.2 运算及其性质对“”运算，对任一x R有x-1 =1x（x0） x 1x =1，乘法幺元；（2）在函数的合成运算中,每一个双射函数都是可逆的， f-1（f的逆关系）；（3）在所有的二元运算中,零元一定不存在逆元，*x=x*=。定义定义设*是

194、Z集合中的二元运算，且a Z和x,y Z，若对每一x，y有（a*x=a*y）（x*a=y*a）（x=y），则称a是可约的（或称可消去的）4685.2 运算及其性质定理定理设*是Z集合中的二元运算,且*是可结合的,若元素a Z,且对于*是可逆的,则a也是可约的。（反之不一定,即可约的不一定是可逆的。）证明：设任一x，y Z,且有a*x=a*y，下面证明，在*可结合和a对*是可逆的条件下，a是可约的。 *是可结合的和a Z对*是可逆的（条件给出） a-1*（a*x）=（ a-1 *a）*x=e*x=x 而 a-1 *（a*y）=（ a-1 *a）*y= e *y=y,即x=y。由定义可知a是

195、可约的。4695.2 运算及其性质下面举例证明，若元素是可约的，但不一定是可逆的。例：I为整数集合，对“”运算，运算是可结合的。任何非零元素均是可约的，但除1和（-1）以外其他元素均没有逆元。1-1=1 ，(-1)-1=(-1) 例：Z=0,1,2,3,4,定义Z中二个运算为，对任一x，y Z有 x+5y=（x+y）mod 5 x5y=（xy）mod 54705.2 运算及其性质e+5=0, 0-1=0, 1-1=4, 2-1=3,3 -1=2,4-1=1。 e*5=1,*5=1,1-1=1, 2-1=3, 3-1=2, 4-1=4, 0没有逆元。以上二元运算性质均可运用到代数系统进行讨论。

196、0 1 2 3 41 2 3 4 02 3 4 0 13 4 0 1 24 0 1 2 3012340 1 2 3 4+50 0 0 0 00 1 2 3 40 2 4 1 30 3 1 4 20 4 3 2 1012340 1 2 3 4*54715.3 3 半群半群定义定义一个代数系统，S为非空集合，是S上的二元运算，如果运算是封闭的，则称代数系统为广群。定义定义设是一代数系统，S为非空集合，是S上的二元运算，若(1)运算是封闭的。(2) 运算满足结合律，则称为半群。例： , , ,均为半群定义定义对于*运算，拥有幺元的半群称为含幺半群。（拟群，幺半群，独异点）。例： , 均为含幺半群

197、，而就不为幺半群。 4725.3 3 半群半群例：设S为非空集合， (S)是S的幂集，则 ,均为含幺半群。而，其中max(x1,x2)取二者之大值；，其中min(x1,x2)取二者之小值，均不为幺半群（不存在幺元）。则为含幺半群，其中 e =0定义定义设是一半群，TS，且*在T上是封闭的，那么也是半群，称是的子半群。4735.3 3 半群半群讨论定义：（1）因为*在S上是可结合的，而TS且*在T上是封闭的，所以*在T上也是可结合的。（2）由定义可知， SS ，也是的子半群（子含幺半群）。为了和其它子半群相互区别，称是的“平凡子半群”;定义定义设是一个含幺半群，TS，且*在T上是封闭的，则

198、也是一个含幺半群，称是的子含幺半群。4745.3 3 半群半群讨论定义：（1）在幺半群中，由于幺元e的存在，保证在运算表中一定没有相同的行和列。设任一x1,x2 Z，且x1x2 ，则e * x1 = x1 e * x2 = x2 ；（2）在中若存在零元的话，上述性质继续存在。例：半群是的子半群，而不是子含幺半群。*运算由运算表定义： 4755.3 3 半群半群 10100010*101100001010*由运算表可见：中幺元为1，而在中幺元为。定理定理如果半群的载体S为有限集，则必有aS，使a*a=a。4765.3 3 半群半群证明：因是半群，对任意的bS，由*的封闭性，b*bS，b3

199、S，b4S，由于S是有限集，必有ij，使bi=bj设：p=j i，则bj=bp*bi，即： bi=bp*bi当qi时，bq=bp*bq，又因p1，总可以找到k1，使kpi，对S中的bkp有bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp =b2p*(bp*bkp)=b3p*bkp=.=bkp*bkp令a=bkp，则a*a=a。4775.3 3 半群半群定理定理设是独异点，对于任意a，bS，且a， b均有逆元，则 a)(a-1)-1=a b)a*b有逆元，且(a*b)-1=b-1*a-1 证明：a)因为a-1是a的逆元，即a* a-1= a-1*a=e 所以 (a-1)-1=a b)

200、因为(a*b)*(b-1*a-1)= a*(b*b-1)*a-1=a*e*a-1=e 同理可证：(b-1*a-1) * (a*b)=e 所以 (a*b)-1=b-1*a-14785.4 4 群与子群群与子群1.群的定义群的定义定义定义设是一代数系统，S是非空集合，*为S上的二元运算，它满足以下四个条件时，则称为群（1）*运算是封闭的；（2） *运算是可结合的；（3）存在幺元e；（4）S中每一个元素均有逆元。例：, ,等均为群（其中Z2 =0,1, Z3 =0,1,2 ），而,只是含幺半群而不是群。4795.4 4 群与子群群与子群例：设M= 0,60,120,240,300,180表示平

201、面上几何图形顺时针旋转的六种位置，定义一个二元运算*，对M中任一元素a,b有a*b=图形旋转(a+b)的角度，并规定当旋转到360时即为0，试验证是一个群。240180120600300300180120600300240240120600300240180180600300240180120120030024018012060603002401801206000300240180120600*4805.4 4 群与子群群与子群（1）运算是封闭的（2）*是可结合的（3）幺元为0 ；（4）每一个元素均有逆元： (0 )-1= 0 , (60 )-1=300 , (120 )-1=240 , (1

202、80 )-1= 180 , (240 )-1=12 0 , (300 )-1= 60 是一个群。 4815.4 4 群与子群群与子群定义定义设是一个群，如果G是有限集合，则称为有限群，并把|G|称为群的阶数，如果G为无限集合，则称为无限群。例：为无限群，上例中为有限群，群的阶为|M| =6。至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。2.群的性质群的性质由群的定义可知:4825.4 4 群与子群群与子群（1）群具有半群和含幺半群所具有的所有性质；（2）由于群中存在幺元，在群的运算表中一定没有

203、相同的行（和列）（3）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。下面以定理形式介绍群的性质 4835.4 4 群与子群群与子群定理定理1 若是一个群，则对任一a,bG有：（1）存在唯一的元素x G ，使a * x= b；（2）存在唯一的元素y G ，使y * a= b。证明：（1）（a）在G中存在x，使a * x= b成立。a * (a-1 * b) = (a * a-1 ) *b =e* b=b，至少有一x = (a-1 * b)满足a * x= b成立。（b）下面证明这样的x是唯一的。若x是G中任一元素，且能使a* x= b成立，则有x =e *x

204、 = (a-1 * a) * x = a-1 * (a * x) = a-1 * b， x = (a-1 * b)是满足a * x= b的唯一元素，即x是唯一的。（2）的证明同上。4845.4 4 群与子群群与子群定理定理22若是一个群，则对任一a,b,cG有：（1）a * b = a * c b = c（a是左可消去的）；（2）b * a = c * a b = c（a是右可消去的）。结论：在代数系统中，二元运算是可结合的，且a是可逆的，则a是可约的。此定理说明群满足消去律。4855.4 4 群与子群群与子群定理定理33一个群中一定不存在零元。零元不存在逆元。定义定义代数系统中，

205、如果存在aG,有a*a=a，则称a为等幂元。4865.4 4 群与子群群与子群定理定理4一个群中，除了幺元e之外，不存在其它等幂元素。证明：若任一a G ，有a * a = a的话，则a = e 。 e = a * a-1 = (a * a ）* a-1 =a * (a * a-1 ) =a * e = a定义定义设S是一个非空集合，从集合S到S的一个双射称为S的一个置换。4875.4 4 群与子群群与子群定理定理5：群的运算表中的每一行或每一列都是G的元素的一个置换。证明：首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。（反证法）如果对应于元素aG的那一行中有两个元

206、素都是c，即有a*b1=a*b2=c，且b1b2 由可约性，得： b1b2，这与b1b2矛盾。其次，证明G中的每一个元素都在运算表的每一行和每一列中出现。4885.4 4 群与子群群与子群考察对应于元素aG的那一行，设b是G中的任一元素由于b=a*(a-1*b)，所以b必定出现在对应于a的那一行。再由运算表中没有两行（或两列）是相同的，所以，的运算表中的每一行都是G的元素的一个置换，且每一行都是不相同的。同样，对于每一列结论同样成立。4895.4 4 群与子群群与子群3.子群子群定义定义设是一个群，且SG是一个非空集合。若满足下列三个条件，则称是的子群：（1）e是的幺元，且eS；

207、（保持幺元）（2）对任一 aS一定有a-1 S ；（保持逆元）（3）对任一a,bS一定有a*bS （运算的封闭性）讨论定义：（1）任一群至少可找到二个子群，即和，称此二子群为平凡子群；（2）除了平凡子群以外的子群称为的真子群。4905.4 4 群与子群群与子群定义定义设是群的真子群，若不再有一个真子群（其中ST），则称是的极大子群。例：是一个群，设S=x|x是6的倍数，T =y|y是3的倍数，则,是的真子群。 ST，不是的极大子群。定理定理设是一个群，B是G的非空子集，如果B是一个有限集，那么，只要运算*在B上是封闭的，则必定是的子群。4915.4 4 群与子群群与子群证明：设

208、bB，已知*在B上封闭，则b*b B，即b2 B， b2 *b B，即： b3 B，于是b ， b2 ， b3均在B中。由于B是有限集，必存在正整数i和j，ij,使得：bi=bj即： bi=bi*bj-i由此可说明bj-i是中的幺元，且这个幺元也在子集B中。如果j-i1，那么由bj-i=b*bj-i-1可知bj-i-1是b的逆元，且bj-i-1 B；4925.4 4 群与子群群与子群如果j-i=1，那么由bi=bi*b可知b就是幺元，且以自身为逆元。因此，是的一个子群。例：设G4=p=|pi0,1，是上的二元运算，定义为，对任意X=，Y= G4，X Y=，其中的运算表如图所示：证明, 是

209、群的子群。011100104935.4 4 群与子群群与子群证明：4945.4 4 群与子群群与子群定理定理设是一个群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1S，则是的子群。证明：先证，G中的幺元e也是S中的幺元。任取 aS， a*a-1S，而a*a-1e，eS 再证，每个元素都有逆元。又e*a-1S，即a-1S。最后说明，*对S是封闭的。 a,b S，因b-1S， (b-1)-1 S4955.4 4 群与子群群与子群a*b=a*(b-1)-1 S，而(b-1)-1 b a*b S 是的子群例：设和都是群的子群，试证明也是的子群。4965.5 5 阿贝尔群和循环群阿贝尔

210、群和循环群定义定义如果群中运算*是可交换的，则称该群为阿贝尔群（或称为交换群）。例：为阿贝尔群。例：离散函数代数系统是阿贝尔群。Z=1,2,3,4， F=f0 , f1 , f2 , f3 1 2 3 42 3 4 1, f2 =1 2 3 43 4 1 2, f3 =1 2 3 44 1 2 3, f0 =1 2 3 41 2 3 4 f =4975.5 5 阿贝尔群和循环群阿贝尔群和循环群由运算表可见：（1）运算是封闭的；（2）“ ”可结合；（3）幺元f0 ；（4）每一个元素均可逆; （5）以主对角线为对称。为阿贝尔群。 f2 f1f0f3f3f1f0f3 f2 f2 f0f3 f2

211、 f1f1f3 f2 f1f0f0f3 f2 f1f04985.5 5 阿贝尔群和循环群阿贝尔群和循环群定理定理设是一个群，是阿贝尔群的充分必要条件是对任一a ,bG有 (a*b)*(a*b) = (a*a)*(b*b)。证明：（1）充分性： (a*b)*(a*b) = (a*a)*(b*b) 是阿贝尔群。对任一a ,bG有(a*b)*(a*b) = (a*a)*(b*b)成立， *是可结合的，且是可消去的， a*(a*b)*b = (a*a)*(b*b) =(a*b)*(a*b) =a*(b*a)*b 得a*b =b*a，是阿贝尔群。4995.5 5 阿贝尔群和循环群阿贝尔群和循环群（

212、2）必要性：是阿贝尔群 (a*b)*(a*b) = (a*a)*(b*b) 。阿贝尔群满足交换律，对任一a ,bG有a*b =b*a ， (a*a)*(b*b) = a*(a*b)*b = a*(b*a)*b =(a*b)*(a*b) 推论推论在阿贝尔群中，对任一a ,bG有 (a*b) 1 =b-1*a-1 =a-1*b-15005.5 5 阿贝尔群和循环群阿贝尔群和循环群定义定义设是一个群，I 是整数集合，若存在一个元素gG，对于G中每一个元素a都能表示成gn的形式（n I），则称是一个循环群，g称为群的生成元。例： 60就是群的生成元，所以该群为循环群。定义定义设是由g 生成的循环群,

213、若存在一个正整数m ,使gm=e成立,则整数中最小的m 称为生成元g 的周期,若不存在这样的m,则称周期为无穷大。 5015.5 5.5 阿贝尔群和循环群阿贝尔群和循环群例：（1）是一个群，生成元g=1，而g的周期为无穷大；（2）I为整数集合。“模m同余”是一个等价关系。设：m=4，N4表示“模4同余”所产生的等价类的集合，N4=0,1,2,3，定义运+4：i+4j=(i+j)(mod 4)(i,j=0,1,2,3)则：是群210331032203211321003210+4运算表：5025.5 5.5 阿贝尔群和循环群阿贝尔群和循环群由运算表可见：（1）由0可生成（2）由1或3可生成（3）

214、由2可生成讨论定义：（1）在循环群中，由生成元的周期分为有限循环群和无限循环群二类；5035.55.5 阿贝尔群和循环群阿贝尔群和循环群（2）在循环群中，生成元的周期是指gm=e中最小的m（这里m0且mI+）。定理定理每一个循环群必然是阿贝尔群。证明：设是一循环群，g为生成元，对任一p,q G一定存在 i ,j I（整数）使得p=gi , q=gj，则p*q = gi * gj = gi+j = gj * gi =q*p 。循环群一定是阿贝尔群。 5045.55.5 阿贝尔群和循环群阿贝尔群和循环群定理定理设是由元素gG生成的循环群，若是n阶的（即|G|=n），则gn=e ，以致G=g

215、1 , g2 , gn = e ，而且n是能使gn = e的最小正整数。证明：5055.55.5 阿贝尔群和循环群阿贝尔群和循环群例：为一群,G中元素和* 运算见运算表： c1=c ,c2=b ,c3=d ,c4=a(幺元); d1=d, d2=b, d3=c ,d4=a (幺元); 而a1=a, a2=a, a3=a, a4 =a ; b1=b, b2=a ,b3=b ,b4=a , 由上可见：生成元c ,d的阶为4，等于群的阶bacddabdcccdabbdcbaadcba*5065.55.5 阿贝尔群和循环群阿贝尔群和循环群定理定理设是由元素gG生成的循环群，若是n阶的（即|G|

216、=n），则gn=e ，以致G=g1 , g2 , gn = e ，而且n是能使gn = e的最小正整数。证明：5075.65.6 同态与同构同态与同构1.代数系统的概念代数系统的概念：定义定义由集合和集合上的一个或多个n元运算所组成的系统称为代数系统，用符号=表示，其中S为非空集合， f1,f2fm表示n元运算。讨论定义：（1）构成一个代数系统必须具备三个条件：一个非空集合S，称为载体；在S上的运算f1,f2fm,；在S上的运算是封闭的。（2）有些书上把特异元素（常数）放在代数系统之中，形成； 5085.6 5.6 同态与同构同态与同构2.同态和同构同态和同构同态和同构是讨论二个代数系

217、统之间的关系。定义定义设U =和V =是二个代数系统，又设U到V存在一个映射 f : AB，对任一a1,a2A，若有f (a1a2) = f (a1) * f (a2)，则称 f 是从代数系统U到V的同态映射。称U同态于V。把称为的一个同态象。其中： f(A)=x|x=f(a)，aAB 讨论定义：5095.65.6 同态与同构同态与同构（1）f : AB为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；（2）对同态讲，二个代数系统的基数可以不相等，只要满足函数的条件就行；（3）上述定义可以推广到多个n元运算的同一类型的代数系统中去。（4）一个代数系统到另一个代

218、数系统可能存在多于一个同态。5105.6 5.6 同态与同构同态与同构例：给定二代数系统 F =I , +，I为整数，“+”为一般加；G = Nm , +m ，其中， Nm = 0,1,2m-1 ,“+m ”为模m加法并定义成 x1 +m x2 = (x1 + x2) mod m 。对任一iI和mI +， (i) mod m 定义了除以m所得之非负余数且0 (i) mod m m。5115.6 5.6 同态与同构同态与同构定义FG的一个函数：f : I Nm且有 f (i) = i ( mod m)，(其中iI ， f (i) Nm ), f (i1+i2) = (i1+i2) mod

219、m = (i1 mod m) +m (i2 mod m)(其中 i1I , i2I) ； i1 mod m Nm , i2 mod m Nm 。则 f 是一同态函数：自变量和象点的对应，并保持运算的对应。5125.65.6 同态与同构同态与同构定义定义若 f : AB 是从U = 到 V = 的同态，于是有：（1）若 f 是满射函数，则称 f 是从U到V的满同态；（2）若 f 是入射函数，则称 f 是从U到V的单一同态；（3）若 f 是双射函数，则称 f 是从U到V的同构。定义定义设V是一个代数系统，如果f是由V到V的同态，则称f为自同态。如果g是V到V的同构，则称g为自同构。5135.65.

220、6 同态与同构同态与同构 f =1 2 3 4 2 3 4 1 f 2f 1f 0f 3f 3f 1f 0f 3f 2f 2f 0f 3f 2f 1f 1f 3f 2f 1f 0f 0f 3f 2f 1 f 0210331032203211321003210+4例：离散函数代数系统和剩余类加代数系统是同构的。5145.65.6 同态与同构同态与同构定义一函数 h: F N4，h( f i) = i,其中i 0,1,2,3，元素一一对应； h( f i f j) = h( f i) +4 h( f j) =i +4 j，运算是一一对应的；和是二个同构的代数系统。在实际中，把对应的元素和运算进行

221、交换，就能得到相同的运算表。例：试考定下列二代数系统U和V是否同构：U=,V=,其运算表如下： 5155.65.6 同态与同构同态与同构EAAAAESSEEEEEEAEAAEEAAAEAAEAAEAAEAAAAAAEAA5165.65.6 同态与同构同态与同构1102552101XX101010101010510551010222105211105211052110551152121211111105215175.65.6 同态与同构同态与同构定义V 中：：求二数的最小公倍数；：求二数的最大公约数；“ ”：10被x除所得之商。由运算表可见：定义一函数 f :1, 2, 5, 10 ,A

222、,A ,Ef (1) = ， f (2) = A ,，f (5) = A ,，f (10) = E 元素一一对应；x5185.65.6 同态与同构同态与同构对任一 a,b 1,2,5,10有 f ( ) = f (a)af (a b) =f (a) f (b) f (a b) =f (a) f (b)运算一一对应。 f 是一双射函数，U和V 二个代数系统同构。若二个代数系统同构，则此二个代数系统具有完全相同的性质,所以对于同构的代数系统, 只要研究其中一个代数系统,其它的代数系统的问题也就解决了,给我们研究问题带来了方便。5195.65.6 同态与同构同态与同构定理定理代数系统中的同构关

223、系是一个等价关系。证：（1）自反性：因为任何一个代数系统可以通过恒等映射与它自身同构；（2）对称性：设U和V同构且有对应的同构映射f，f是双射函数， f的逆是V到U的同构映射，即V和U同构；（3）传递性：设f是U到V的同构映射，g是V到W的同构映射，因为f和g是双射函数，f g是U到W的同构映射。即U和W同构。所以，同构关系是等价关系。5205.65.6 同态与同构同态与同构定理定理设f是从代数系统U = 到 V = 的同态映射，（1）如果U是半群，那么在f作用下，同态象也是半群；（2）如果U是独异点，那么在f作用下，同态象也是独异点；（3）如果U是群，那么在f作用下，同态象也是群；52

224、15.65.6 同态与同构同态与同构证明：5225.5.6 同态与同构同态与同构3.同余关系：同余关系：这是讨论同一代数系统中的关系。同余关系是代数系统的集合中的等价关系，在运算的作用下，能保持运算的等价类，同余关系是相等关系的推广。在介绍同余关系之前先看一个例子。例：设是一代数系统,其中F是所有分数的集合,+,-, 为一般的加,减,乘法。则在F中,可把相等的分数作为元素的集合是F的子集:1/2= , -2/-4 ,-1/-2 ,1/2 ,2/4 ,3/6 , 1/3= , -2/-6 ,-1/-3 ,1/3 ,2/6 ,.。若对二个等价类中的元素进行+,-, 运算，则运算结果必定属于同一

225、等价类中。5235.65.6 同态与同构同态与同构如： 1/2 +1/3 = (1/2+2/6) = (2/4 +1/3 ) 5/6 ;1/2 1/3 = (1/2 2/6) =( 2/4 1/3 ) 1/6;1/2 1/3 = (1/2 2/6 ) =( 2/4 1/3 ) 1/6 。在F中，二个等价类的元素对+,-, 运算均满足代换性质，即分数集合的相等关系，对+,-, 运算满足代换性质。5245.65.6 同态与同构同态与同构定义定义设代数系统 U =, * 是二元运算，R是Z中的等价关系，当且仅当对任一x1,x2 Z y1,y2 Z有 x1R x2 y1Ry2 x1 *y1 R x2

226、* y2时，则对于运算*，等价关系R满足代换（置换)性质。定义定义设U =是一代数系统，R是Z中的等价关系，于是对于二元运算*，若等价关系R满足代换性质，则称R是代数系统U中的同余关系，与此相对应，R的等价类称为同余类。5255.65.6 同态与同构同态与同构例：在整数I集合中是一个同余关系，为一代数系统，对任一定义*运算：*(i) =(i2) mod m , (m I+) 定义R关系：设R是I中的一个关系，当i1 mod m = i2 mod m 时，则有i1R i2 下面证明(i2) mod m是一个同余关系证明：（1）前面已证明：在I中，i(i I)模 m 等价是一个等价关系

227、。（2）对于*运算，R满足代换性质。5265.65.6 同态与同构同态与同构设i1 ,i2 I ，且i1 R i2（即i1 mod m = i2 mod m ），又设i1 = a1m + r， i2 = a2m + r ,由定义有： *(i1) =(i12) mod m =(a1m + r)2 mod m =(a12m2 + 2 a1mr + r2) mod m= r2 mod m *(i2) =(i22) mod m =(a2m + r)2 mod m =(a22m2 + 2 a2mr + r2) mod m= r2 mod m *(i1) = *(i2),具有等价关系的元素i1 ,i2经

228、“*”运算后属于同一等价类,R对于*满足代换性质。R是中的同余关系。5275.65.6 同态与同构同态与同构在同余关系的定义中，等价关系，对于某一运算满足代换性质，这二条均是必须的。只满足R是等价关系，而不去证明对于运算满足代换性质不能说它就是同余关系，可见下例。5285.65.6 同态与同构同态与同构例：是一代数系统，其中 A = a ,b , c ,d，*由运算表给出定义： abdcdbabccadabbcdaaadcba*定义A中一个等价关系R，且aRb,cRd,R=但等价关系对*运算不满足代换性质。c*a=c而c*b=b但cRb并不成立。R不是A中对于*运算的同余关系。5295.65

229、.6 同态与同构同态与同构定理定理设是一个代数系统，R是A上的一个同余关系，BA1,A2,.,Ar是由R诱导的A上的一个划分，那么，必定存在新的代数系统，它是的同态象。证明：由于R是A上的同余关系，我们设B上的二元运算*为：对于任意的Ai，AjB,任取a1Ai，a2Aj，如果a1a2 Ak，则Ai*Aj=Ak且是唯一的。作映射f(a)=AiaAi显然，f是从A到B的满射。x,y A， x,y必属于B中的某两个同余类，不妨设5305.65.6 同态与同构同态与同构 x Ai，yAj，则x y必属于B中某个同余类，不妨设x y Ak，于是有： f(x y )= Ak=Ai*Aj=f(x)*f(y

230、)因此，f是由到的满同态，即是的同态象。形象地说，一个代数系统的同态象可以看作是抽去该系统中某些元素的次要特性的情况下，对该系统的一种粗糙描述。5315.65.6 同态与同构同态与同构定理定理设f是由到的一个同态映射，如果在A上定义二元关系R为：R当且仅当 f(a)=f(b)那么,R是A上的一个同余关系。证明：首先证明R是A上的等价关系。(1)R是自反的，由f(a)=f(a)，aA，R。(2)R是对称的，由f(a)=f(b)可得f(b)=f(a)， a,bA，由R可得R。(3)R是可传递的，当R且R时，有f(a)=f(b),f(b)=f(c)则f(a)=f(c)，即有R。其次证明R对于运算

231、满足代换性质 5325.65.6 同态与同构同态与同构R， R时，有f(a)=f(b)，f(c)=f(d)因为： f是由到的一个同态映射。f(a c)=f(a)*f(c)， f(b d)=f(b)*f(d) f(a c)= f(b d)，即 R。综上所述，R是A上的同余关系。533第六章第六章格和布尔代数格和布尔代数 6.1 格的概念6.2 分配格6.3 有补格6.4* 布尔代数534第六章第六章格和布尔代数格和布尔代数教学目的及要求：教学目的及要求：深刻理解和掌握格与布尔代数的基本概念和基本运算。教学内容：教学内容：格的概念、分配格、有补格、布尔代数、布尔表达式。教学重点：教

232、学重点：格、布尔代数、布尔表达式。教学难点：教学难点：布尔代数、布尔表达式。5356.6.1 格的概念1.偏序集合格偏序集合格定义定义格是一个偏序集合，其中每一对元素都拥有一个最小上界和最大下界。通常用表示a和b的最大下界，用表示a和b的最小上界。即：称为元素a和b的保交运算，称为元素a和b的保联运算。 5366.6.1 格的概念例：以下均为偏序集合格（D为整除关系，Sn为n的因子集合）。 5376.6.1 格的概念2.2.代数系统格代数系统格定义定义设是一个格，如果在A上定义两个二元运算和，使得对于任意的a，bA，ab等于a和b的最小上界，ab等于a和b的最大下界，那么就

233、称为由格所诱导的代数系统。5386.6.1 格的概念3.3.格的主要性质：格的主要性质：(1)格的对偶原理设是格，“”的逆关系“”与L组成的偏序集也是格。两者互为对偶。前者的GLB，LUB恰好是后者的LUB，GLB。如有关于的有效命题，将“”换成“”，“”换成“”， “”换成 “”，便能得到的有效命题。反之亦然。5396.6.1格的概念(2)对格中任意a和b，有aab及aba。(3)是格。对任意a,b,c,dL，如ab， cd，则ac bd， acbd(4)（交换律）交和并运算是可交换的。(5)（结合律）交和并运算是可结合的。5406.6.1 格的概念(6)（幂等律）对L中每一个a，有a

234、a=a，aa=a。(7)（吸收律）对L中任意a，b，有 a(ab)=a a(ab)=a。5416.6.2 分配格对格所定义的代数系统，其运算和不一定满足分配律。定义定义设是由所诱导的代数系统。如果对任意的a,b,cL，满足：a (b c)=(a b) (a c) 及 a (b c)=(a b) (a c) 则称是分配格。5426.6.2 分配格讨论定义：(1)定义中的两式互为对偶式。(2)如非为分配格，则有下面的分配不等式： a (b c) (a b) (a c) a (b c) (a b) (a c) 以及模不等式： aca (b c) (a b) c6.5436.6.2 分配格定义定

235、义如对L中任意a，b，c有：aca (b c) (a b) c 则称为模格。例：5446.6.2 分配格定理定理如果格中交对并是分配的，那么并对交也是分配的，反之亦然。证明：已知a(bc)(ab)(ac)(ab)(ac)=(ab)a)(ab)c) =a(ab)c) =a(ac)(bc) =(a(ac)(bc) =a(bc)即：并对交也是分配的。5456.6.2 分配格定理定理分配格是模格。证明：由于a (b c) (a b) (a c)(1)若ac，则a c=c，代入上式得a (b c) (a b) c(2)若a (b c) (a b) c，则a a (b c) (a b) cc，即：

236、 ac分配格是模格5466.6.2 分配格定理定理每个链均是分配格。证明：设是链。对任意a，b，cL(1)若ab或ac，则 a (b c) a， (a b) (a c)a即： a (b c) (a b) (a c)(2)若ab且ac，则 a (b c) b c， (a b) (a c) b c即：a (b c) (a b) (a c)。得证。5476.6.3 有补格定义定义设是一个格，如果存在元素aL，对于任意的x L，都有：ax 则称a为格的全下界，记格的全下界为0。例：5486.6.3 有补格定理定理如果格有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b

237、，则由定义 ab，且ba，由“”的反对称性， ab。定义定义设是一个格，格中存在全上界和全下界，则称该格为有界格。5496.6.3 有补格定理定理如果是有界格，全上界和全下界分别是1和0，则对任意元素aL，有： a1=1a=1 ，a1=1a=a， a0=0a=a ，a0=0a=0。证明：因为1a1，又因(a1)L且1是全上界，a11， a1=1。由交换律：1aa1=1。因为aa，a1，a aa1，即：aa1，又a1a， a1=a。仿此可得另两式。5506.6.3 有补格定义定义设是一个有界格，对于L中的一个元素a，如果存在bL，使得ab=1和ab=0，则称元素b是元素a的补元。讨

238、论定义：（1）和是可交换的，补元是相互的。（2） ,在有界格中，1和0互为补元；（3）由定义可知L中一个元素的补元不一定唯一；例： 5516.6.3 有补格定义定义在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。请看下例： 5526.6.3 有补格定义定义在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。请看下例

239、： 5536.6.3 有补格定理定理在有界分配格中，若有一个元素有补元，则必是唯一的。证明：5546.6.4 布尔代数布尔代数定义定义一个有补分配格称为布尔格。定义定义一个格如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。讨论定义：(1)布尔格中，每个元素有唯一的补元。(2)我们可以定义L上的一个一元运算，称为补运算，记为“-”。-5556.6.4 布尔代数布尔代数定义定义由布尔格，可以诱导一个包括交，并和补运算的代数系统，称此代数系统为布尔代数。例：设S是一个非空有限集，是一个格，且是一个布尔格。由所诱导的代数系统为是一个布尔代数。其中“,-”

240、分别是集合的交、并、补运算。5566.6.4 布尔代数布尔代数定理定理对于布尔代数中任意两个元素a,b，必定有5576.6.4 布尔代数布尔代数证明：5586.6.4 布尔代数布尔代数定理定理设是由有限布尔格所诱导的一个有限布尔代数，S是布尔格中的所有原子的集合，则和同构。讨论定理：(1)当布尔代数的载体A的基数|A|是有限数时,则称之为有限布尔代数。(2)设是一个布尔代数，aA,如果a盖住0，则称元素a是该布尔代数的一个原子原子。例如：5596.6.4 布尔代数布尔代数例：，其中S=a,b,c，在这个布尔代数中的元素分三种情况：（）界：全上界S，全下界；（）a,b,c单个元素集合的元素；

241、（）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述：a,b=ab ,a,c=ac, b,c=bc, a,b,c=abc 。 a,ca,b,ca,bb,cacb5606.6.4 布尔代数布尔代数(3)A中除0外的每个元素，都可以唯一地表示成原子的并。该定理可得以下两个推论：a)与同构，|p(S)|=2|s|所以，|B|=2|s|，故任一有限布尔代数任一有限布尔代数载体的基数是载体的基数是2 2的幂。的幂。b)任一有限布尔代数和它的原子集合S构成的幂集集合代数同构，但后者又与任一基数相同的幂集集合代数同构，故具有相同载具有相同载体基数的有限布尔代数都同构。体基数的有限布尔代数都

242、同构。 5616.6.4 布尔代数布尔代数格格有界格有界格有补格有补格布尔代数布尔代数分配格分配格结合律结合律吸收律吸收律交换律交换律幂等律幂等律同一律同一律零一律零一律互补律互补律分配律分配律德德摩根律摩根律双重否定律双重否定律5626.6.4 布尔代数布尔代数例：设A是一非空集合,(A)是A的幂集,可以验证,是个布尔代数,称此为集合代数,其中运算为, , ,最小元,最大元A。S是命题公式的全体,则是一个布尔代数,称之为命题代数。其中运算为, , ,最小元是恒假公式0,最大元是恒真公式1。5636.6.4 布尔代数布尔代数因此，从逻辑观点看，布尔代数是命题演算系统。从集合论观点看，布尔代

243、数是集合代数。从抽象代数的观点看，布尔代数是一个代数系统。564第三篇小结通过本篇的学习应该达到以下基本要求：(1)给定集合与运算的解析表达式，写出该运算的运算表。(2)给定集合和运算，判别该集合对运算是否封闭。(3)给定二元运算，说明运算是否满足交换律、结合律、幂等律、分配律和吸收律。(4)给定集合S上的二元运算，求出该运算的幺元、零元、幂等元和所有可逆元素的逆元。(5)给定集合S和二元运算*，能判定是否构成半群、独异点和群。565第三篇小结(6)给定半群S和子集B，判定B是否为S的子半群；给定独异点V和子集B，判定B是否为V的子独异点，给定群G和子集H，判定H是否为G的子群。(7)求循环群

244、的所有生成元。(8)给定代数系统V1=，V2=，其中“”和”*“为二元运算，判定： S1 S2是否为V1到V2的同态映射。如果是，说明是否为单同态、满同态和同构，并求出同态象(V1)。(9)判别格、分配格、有界格、有补格和布尔格。求有界格的全上界、全下界和给定元素的补元。566习题选讲例1.设：Sa,b，则S上可以定义多少个二元运算？其中有4个运算如下表所示，则有哪些满足交换律，哪些满足幂等律，哪些有幺元，哪些有零元？aabaaaba1abbbaaba2aabababa3babbaaba4567习题选讲例2.对以下定义的集合和运算判别它们能否构成代数系统？如能，请说明是构成哪一种代数系统？(

245、1) ，为普通加法；(2) ，*为普通乘法；(3) ，为小于等于关系；568第四篇图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。 569第四篇图论图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。对于这样一门应用广泛的学科，其包含的内容是

246、丰富的，本篇我们只准备介绍基本的概念和定理，为今后有关学科及课程的学习和研究提供方便。570第七章第七章图论图论7.1 图的基本概念7.2 路与回路7.3 图的矩阵表示7.4 欧拉图和汉密尔顿图7.5 平面图7.6 树与生成树571第七章图论教学目的及要求：教学目的及要求：深刻理解和掌握图的有关概念和表示。教学内容：教学内容：图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用。教学重点：教学重点：图、路、图的矩阵表示、平面图、对偶图与着色、树与生成树。教学难点：教学难点：树与生成树。5727.1 图的基本概念1.1.基本

247、名词和定义基本名词和定义定义定义一个图G是一个三元组, 其中V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集合，G是从边集E到结点偶对集合上的函数。讨论定义： (1). V(G) =V1，V2，Vn为有限非空集合, Vi称为结点,简称V是点集。 (2). E(G)=e1，em为有限的边集合,ei称为边，每个ei都有V中的结点对与之相对应,称E为边集。即每条边是连结V中的某两个点的。5737.1 图的基本概念(3).若中每一条边e与有序偶对或无序偶对 (vi,vj)相关系，则可说边e连接结点vi和vj(4).可用e 或e (vi,vj)，以结点来表示图的边，这样可把图简化成：。

248、例：有图如下，试写成定义表达式，其中v1,v2,v3,v4,v5 x1,x2,x3,x4,x5,x65747.1 图的基本概念例：对有向图可表示为：、，其中a、b、c、d, 下面定义一些专门名词：(1)有向边：有向边：在图中对应有序偶对的边（或者：在图中带有箭头方向的边或弧线） 5757.1 图的基本概念(2)无向边：无向边：在图中对应无序偶对的边（或：在图中不带箭头的边）(3)邻接结点：邻接结点：由一条边（有向或无向）连接起来的结点偶对 (4)（，）图：（，）图：具有个结点（顶点），条边的图(5)有向图：有向图：在中每一条边均为有向边(5)有向完全图：有向完全图：在n个结点的

249、有向图G=中，如果EVV，则称G为有向完全图。例：5767.1 图的基本概念对有向简单完全图讲： n(n-1) （没有自回路） 5777.1 图的基本概念(6)无向图：无向图：每一条边均为无向边的图(7)无向完全图：无向完全图：每两个结点之间均有连线的无向图。n个结点的无向完全图的边数为：例：5787.1 图的基本概念(8)混合图：混合图：既有有向边，又有无向边的图(9)互相邻接的边：互相邻接的边：连接于同一结点的二条（或若干条）边例：5797.1 图的基本概念(10)闭路（自回路）：闭路（自回路）：图中起始且终止于同一结点的边(闭路的箭头方向是没有意义的 )例：(11)多重边（平行边）：

250、多重边（平行边）：二个结点之间方向相同的二条（多条）边例：5807.1 图的基本概念定义定义含有多重边的图称为多重图多重图，非多重图称为线图线图。简单图：简单图：无自回路的线图称为简单图。简单图。由定义可见，简单图是没有自回路和多重边的图。例：5817.1 图的基本概念定义定义有权图有权图（赋权图）是一个三元组、或四元组、，其中为结点集合，为边的集合，f是定义在上的函数，g是定义在边集合上的函数。实际上，有权图可以用一句话概括：每一条边或结点均注上数字的图（数字可以为整数、正实数）例：给出一个有权图、，其图如下：其中 v1,v2,v3 e1,e2 5827.1 图的基本概念(12)孤立结点

251、：孤立结点：不与任何结点相连接的结点(13)零图：零图：仅包含孤立结点的图，又称（，）图(14)平凡图：平凡图：只有一个结点的图（1，0）图定义定义在有向图中,对于任何结点v,以v为始点的边的条数,称为结点v的引出度数,记作 ;以v点为终点的边的条数称为v的引入度数，记作结点的v的引入度数和引出度数之和称为v的度数，用deg（v）表示。deg（v）对无向图讲:结点的度数等于与其关联的边的条数5837.1 图的基本概念例：(15)正则图：正则图：所有结点均具有同样度数的简单无向图例：5847.1 图的基本概念定理定理每个图中，结点度数的总和等于边数的两倍。5857.1 图的基本概念例：若图有

252、n个顶点，（n+1）条边，则中至少有一个结点的度数。证明：设中有n个结点分别为v1,v2,vn，则由握手定理：而结点的平均度数=结点中至少有一个顶点的度数 5867.1 图的基本概念推论推论(1)在图中，所有度数之和必为偶数；(2)在图中，度数为奇数的结点必定有偶数个。5877.1 图的基本概念定理定理在任何有向图中，所有结点的入度之和等于所有结点的出度之和。5887.1 图的基本概念子图和图的同构子图和图的同构：定义定义设,是二个图若,则称是的子图；若或,则称是的真子图；若,则称是的生成子图(支撑子图)。例：图如下：的真子图：支撑子图：5897.1 图的基本概念说明：（1）也是的生成子图；

253、（2），也是的生成子图。它们统称为平凡子图。定义定义设，是的子图，若有另一个图，且满足关系，为E中边的相关结点的集合，即（），则称：为关于的补图（相对补图）。例：5907.1 图的基本概念关于的补图定义定义给定一个图，由中的所有结点和使成为完全图的边所组成的图，称为的补图（绝对补图），记为: 5917.1 图的基本概念定义定义设、和，是两个图，若存在一双射函数：，当且仅当eg(vi),g(vj)是中的一条边，才能使evi,vj是中的一条边，则称和同构。 5927.1 图的基本概念讨论定义：（1）和是互为同构的；（2）对无向图讲“一一对应”是指保持结点之间的邻接关系；（3）对有向图讲“一

254、一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。例1：5937.1 图的基本概念例：下面给出二个无向图，试求出同构函数：1,2,3,4,5,6 5947.1 图的基本概念两图同构的必要条件：1.结点数相等。2. 边数相等3.度数相同的结点数相等不是充分条件。5957.2 路与回路1.路径和循环路径和循环定义定义在一个图中，从某一结点出发经过某些结点到达终点的边的序列称为图的路径，而路径中边的条数称为路径的长度（路长）。讨论定义：（1）从一个结点到某一结点的路径不一定唯一；（2）路径的表示方法： (a)边的序列表示法：设，为一有向图，，则路径可以表示成：(,.

255、) 5967.2 路与回路 (b)结点表示法：（3）路径长度：若二个结点之间有一条路经，则路径|中边的条数。例：给出有向图，求起始于，终止于的路径 5977.2 路与回路下面介绍一些专有名词：(1)穿程全部结点的路径穿程全部结点的路径：经过图中所有结点的路径。(2)简单路径：简单路径：在有向图中经过边一次且仅一次的路径。(3)基本路径：基本路径：在有向图中，穿程结点均不相同的路径。(4)循环：循环：起始且终结于同一结点的路径。 (5)简单循环：简单循环：每一条边出现一次且仅一次的循环。(6)基本循环：基本循环：通过每个结点一次且仅一次的循环。例：在上例中，列出下列循环，判断为何种循环5987

256、.2 路与回路(7)非循环图：非循环图：没有任何循环的简单有向图。讨论：一定不包含自循环不是基本路径的任何路径都会包含循环，去掉这些循环就可以得到基本路径 2.可达性：可达性：定义定义设图为简单有向图，且，若从vi 到vj存在任何一条路径的话，则称vi到vj是可达的。可达性一定满足：自反性; 可传递性： 5997.2 路与回路定义定义从vi到vj的最短路径的长度称为距离，并记作：讨论定义：(1) d=0(2) d0(3) d+dd6007.2 路与回路(4)规定：若vi到vj是不可达的，则(5)若vi到vj是可达的，且vj 到vi也是可达的，则d不一定等于d 例：6017.2 路与回路

257、3.连通性连通性定义定义对于无向图中的任何结点偶对来讲，若任何二个结点是相互可达的，则称此图是连通的。对于有向图来讲定义定义对于简单有向图的伴随无向图（或称底图），若是连通的，则称此图为弱连通的；若图中任何结点偶对中至少有一点到另一结点是可达的，则称此图是单侧连通的；如果两结点均是互相可达的，则称是强连通的。注：伴随无向图即为去掉箭头方向的图 6027.2 路与回路例：判定下列图是何种连通图：6037.2 路与回路定理定理一个有向图是强连通的充要条件是：它包含一个循环，该循环至少包含每个结点一次。证明：6047.2 路与回路定义定义设，为一简单有向图，且是的子图。对于某一性质而言，若没有

258、其他包含的子图具有这种性质，则称子图是相对于该性质的极大子图。具有强连通性质的极大子图称为强分图；具有单侧连通性质的极大子图称为单侧分图；具有弱连通性质的极大子图称为弱分图。6057.2 路与回路例： 6067.2 路与回路定理定理在任一简单有向图，中，有向图的每一个结点恰好处于一个强分图之中。证明： 6077.3 图的矩阵表示矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出图的路径、循环和其它一些性质。图的邻接矩阵表示方法图的邻接矩阵表示方法定义设，是简单有向图，其中 V=v1,v2,vn定义一个nxn的矩阵A，并把其中各元素aij表示成：则称矩阵A为图G的邻接矩阵。6087

259、.3 图的矩阵表示例：设图，如下图所示讨论定义：（1）图G的邻接矩阵中的元素为0和1，又称为布尔矩阵；（2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和行、列和列的交换，则得到相同矩阵。6097.3 图的矩阵表示若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。（3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；（5）在图的邻接矩阵中，行中1的个数就是行中相应结点的引出次数列中1的个数就是列中相应结点的引入次数6107.3 图的矩阵表示矩阵

260、的计算矩阵的计算：6117.3 图的矩阵表示主对角线上的数表示结点i（或j）的引出次数。主对角线上的数表示结点i（或j）的引入次数。 6127.3 图的矩阵表示表示i和j之间具有长度为2的路径数，表示i和j之间具有长度为3的路径数，表示i和j之间具有长度为4的路径数，6137.3 图的矩阵表示bij表示从结点vi到vj有长度分别为1，2，3，4的不同路径总数。此时， bij0，表示从vi到vj是可达的。6147.3 图的矩阵表示定义设，是简单有向图，其中|V|=（），定义一个矩阵P，它的元素为：则P称为图G的可达性矩阵。由矩阵可计算出可达性矩阵，其方法是：若中（i ,j）是非“0

261、”元素，则对应的，否则 6157.3 图的矩阵表示定义定义设无向图，其中，则称B为无向图G的完全关联矩阵。令6167.3 图的矩阵表示例：讨论定义：（1）完全关联矩阵为布尔矩阵；（2）对应B中行均为0的结点为孤立结点，只有一个“1”的行的结点一定为悬挂的边，且一定不在任一循环中全部为1的行的结点必定联结图中所有的结点。 6177.4 欧拉图和汉密尔顿图欧拉路径：穿程图G的每一条边一次且仅一次的路径。欧拉循环：穿程图G的每一条边一次且仅一次的循环。欧拉图：具有欧拉循环的图。定理无向图G具有一条欧拉路径，当且仅当G是连通的，且有零个或两个奇数度数的结点。推论无向图G具有一条欧拉循环，当且

262、仅当G是连通的，且所有结点度数全为偶数。6187.4 欧拉图和汉密尔顿图例：用定理解决哥尼斯堡桥的问题 6197.4 欧拉图和汉密尔顿图定理设G是一连通有向图，则当且仅当G中每一个结点的，G才有欧拉循环；当且仅当除了二个结点（其中一个的引入次数比引出次数大，另一个的引入次数比引出次数小）以外的所有结点的，则图G才有欧拉路径。6207.4 欧拉图和汉密尔顿图汉密尔顿路径：穿程无向图的每一个结点一次且仅一次的路径。汉密尔顿循环：穿程无向图的每一个结点一次且仅一次的循环。汉密尔顿图：具有汉密尔顿循环的图。到目前为止，还没有找到哈密尔顿路径存在的充分必要条件。下面介绍两个定理。6217.4 欧拉图

263、和汉密尔顿图定理定理设，是具有n 个结点的简单无向图，若在G中每对结点次数之和大于或等于(n-1)，则在G中一定存在一条汉密尔顿路径。实际上，此定理只是充分条件，而不是充分必要条件。例：，见图：每对结点次数为，但确有一条汉密尔顿路径。6227.4 欧拉图和汉密尔顿图定理定理若图G=具有汉密尔顿循环，则对于结点集V的每个非空子集S均有W(GS)|S|成立。讨论：(1)W(GS)为从G中删除S后，所得图的连通分支数。(2)该定理给出的条件是哈密尔顿图的必要条件。例：6237.5 平面图先看一个例子：有六个结点的图如右，试问：能否转变成与其等价的，但没有任何交线的平面上的图？定义定义设G=是一个无向

264、图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称G是一个平面图。6247.5 平面图讨论定义：（1）平面上的图，一开始就画成如定义所讲的图；例：（2）原来在平面上的图形似交叉，但经过若干次的改画后，变成符合定义所规定的图；6257.5 平面图（3）并非所有的图经过处理之后都可变为平面图。如何判断一个图是否为平面图，介绍以下几种方法：1.观察法：找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。6267.5 平面图2欧拉定理：定义定义平面图中四周为边所包围之最小平面块称为平面图的区域亦称面。包围区域的诸边称为此区域的边界。区域面积为有限者称为有限

265、区域，区域面积为无限者称为无限区域。例：6277.5 平面图定理定理(欧拉公式)设图G是一个(n,m)连通平面图，它的区域数为r，则有nmr2。推论推论设图G是一个(n,m)连通简单平面图，若n3则m3n-6。定理和推论给出了是平面图的必要条件，若不满足这些条件，则一定不是平面图。例：6287.5 平面图3库拉托夫斯基（Kuratowski 波兰数学家）定理：给定两个图：我们做以下的工作：(1)在左边图的中间联线上插入一个度数为2的结点，则把一条边分成了二条边；(2)在右边图中去掉一个度数为2的结点，则把二条边变成一条边。此二项工作不会影响图的平面性。2度结点内同构度结点内同构。6297.5

266、平面图定义定义设G1、G2是二个图，如果它们是同构的，或可以通过反复插入或删除度数为2的结点，使得G1和G2同构，则称G1 、 G2为2度结点内同构。例：下列二对图是度数为2的结点同构6307.5 平面图定理定理（Kuratowski定理）设G是一个图，当且仅当G不包含任何在度数为2的结点内与K3,3和K5图同构的子图时，则G才是平面图。这一定理给出了一个图是平面图的充要条件。6317.6 树与生成树1.1.无向树（树）无向树（树）定义定义连通的且无循环的无向图称为无向树。例：专用名词：树叶(终点)：树中度数为1的结点。内点(分枝点)：树中度数大于1的结点。森林：每个连通分图均为树的图。6

267、327.6 树与生成树树的性质：定理定理1：设T是一棵树，vi,vj为T中两个不同的结点，则：1) vi和vj仅有一条路径相连通。 2)在T中加一条边vi,vj，则由此而形成的图，仅有一个循环。例：6337.6 树与生成树定理定理2：在一棵(n,e)树中有e=n-1。(n表示结点数，e表示边数)证明：6347.6 树与生成树推论推论设F是由t棵树组成的(n,e)森林，则有e=n-t。定理定理3：在结点大于2的(n,e)树中，所有结点的度数之和为2(n-1)。定理定理4：在任一(n2)的树T中，至少有二片树叶。6357.6 树与生成树2.生成树生成树定义定义一个无向图G的生成子图是树TG，则称

268、TG是G的生成树(支撑树)。讨论定义：1)G的生成树不是唯一的。例：6367.6 树与生成树2)如何在连通图G中寻找一棵生成树：若G没有循环，则G本身就是一棵树；若G仅有一条循环，从此循环中删去一条边，仍保持图的连通性，得到一棵生成树。若G有多条循环，则逐个对每条循环重复中操作，直到打断G中所有循环，得到一棵生成树为止。定理定理任何连通图至少有一棵生成树。6377.6 树与生成树给定一个连通图，寻找其生成树的数目是图论中树的计数问题。定理定理含n(n1)个结点的标记完全图Kn有nn-2棵标记生成树。例：6387.6 树与生成树定义定义生成树T中的边称为树枝，不在生成树T中但属于图G的边，称为树

269、T的弦，弦的集合称为树T的补。例：定义定义在一个连通赋权图中，树枝的权之和为最小的生成树称为最小生成树。Kruskal算法：设G有n个结点，m条边，先将G中所有边按权的大小次序进行排列，不妨设：W(e1)W(e2)W(em)，6397.6 树与生成树k1，A。若Aek导出的子图中不包含简单循环，则 A Aek若A中已有n-1条边，则算法终止，否则K K+1，转至。例：6407.6 树与生成树这一算法假设G中权均不相同，对于边权任意情况也完全适用。这时求得的最小生成树不唯一。例：6417.7 有向树与根树定义定义若有向图在不考虑边的方向时是一棵树，称之为有向树。定义定义一棵有向树，如果恰有一个

270、结点的入度为0，其余所有结点的入度都为1，则称为根树。入度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分枝点或内点。任何结点的级(高度)是从根出发到该结点的路径长度(边的条数)。例：6427.7 有向树与根树定义定义指明了根树中结点或边的次序的树称为有序树。在有序树中，如每个结点有明确的级，同一级的结点排在同一行，并明确它们的位置，则这样的树称位置树。例：6437.7 有向树与根树定义定义在根树中，若每一个结点的出度小于或等于m，则称这棵树为m叉树。若每个结点的出度恰好等于m或零，则称这棵树为完全m叉树，若其所有树叶层次相同，称为正则m叉树。特别，当m=2时，称为二叉树。很多实

271、际问题可用二叉树或m叉树表示。任何一棵任何一棵有序树都可以把它改写为一棵对应的二叉树。有序树都可以把它改写为一棵对应的二叉树。定义定义在有向树T中，由结点V和它的所有子孙所构成的结点子集V以及从V出发的所有有向路中的边所构成的边集E组成T的子图T=，称为是以V为根的子树。6447.7 有向树与根树方法：设有序树T中结点Vi的r棵子树有根Vi1,Vi2,Vir,其顺序自左向右，则在二叉树T中Vi1是Vi的左儿子，Vi2是Vi1的右儿子，Vi3是Vi2的右儿子.， Vir是Vir1的右儿子。例：645本章小结通过本篇的学习应达到以下基本要求：(1)牢记图论基本定理(握手定理)，(2)记住简单图的概

272、念，弄清楚那些概念是用简单图定义的。(3)明白图之间同构的概念，会根据定义判断阶数n较小的两个图是否同构。(4)弄清图中路径和循环的概念及其分类。(5)在讨论图的连通性时，要特别注意有向连通图的分类及它们之间的关系。(6)在图的矩阵表示中，可以用有向图的邻接矩阵及各次幂，求图中的路径数。646本章小结(7)明确只存在欧拉路径而无欧拉循环的图不是欧拉图，同样，只存在汉密尔顿路径不含汉密尔顿循环的图不是汉密尔顿图。(8)对于汉密尔顿图，我们只给出了存在的充分条件和必要条件。仍没有找到充分必要条件。(9)掌握平面图的概念及判定平面图的几种方法。(10)掌握树的定义和性质并利用握手定理求树中结点的度数，会求连通图的生成树，用Kruskal算法求最小生成树。(11)掌握根树、有序树、m叉树的概念，任何一棵有序树都可以改写成为二叉树。647

展开阅读全文

离散数学教案

最新文档