离散数学课堂PPT#校园专题

《离散数学课堂PPT#校园专题》由会员分享，可在线阅读，更多相关《离散数学课堂PPT#校园专题（442页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 命题逻辑命题逻辑11 命题及其表示法命题及其表示法1.什么是命题什么是命题命题：能判断真假的陈述句。命题：能判断真假的陈述句。命题的值叫它的真值。命题的值叫它的真值。 真值：真值：“真真”：表示判断正确。记作：表示判断正确。记作True，用，用T表示。表示。 “假假”：表示判断错误。记作：表示判断错误。记作False，用，用F表示。表示。1校园课件例例1 判断下列句子中哪些是命题？判断下列句子中哪些是命题？ （1）2是素数。是素数。 （2）雪是黑色的。）雪是黑色的。 （3）2+3=5 （4）明年）明年10月月1日是晴天。日是晴天。 （5）3能被能被2整除。整除。 （6）这朵花真好

2、看呀！）这朵花真好看呀！ （7）明天下午有会吗？）明天下午有会吗？ （8）请关上门！）请关上门！ （9）X+Y5 （10）地球外的星球上也有人。）地球外的星球上也有人。（11）我正在说谎。）我正在说谎。2校园课件2命题的符号化表示命题的符号化表示 命题的符号化就是用符号表示命题。命题的符号化就是用符号表示命题。简单命题（或原子命题）：简单陈述句表示简单命题（或原子命题）：简单陈述句表示的命题。用的命题。用P，Q，R,Pi,Qi,Ri,表示。表示。例例 P:2是偶数。是偶数。 Q:雪是黑色的。雪是黑色的。命题常量（或命题常元）：简单命题。命题常量（或命题常元）：简单命题。命题变项（或命题变元）：

3、真值可以变化的命题变项（或命题变元）：真值可以变化的简单陈述句。不是命题。简单陈述句。不是命题。 例：例：x+y5 3校园课件命题变项也用命题变项也用P，Q，R, Pi,Qi,Ri,表示。表示。复合命题：由简单命题用联结词联结而成的命题。复合命题：由简单命题用联结词联结而成的命题。4校园课件例例2 将下列命题符号化。将下列命题符号化。（1）3 不是偶数。不是偶数。（2）2 是素数和偶数。是素数和偶数。（3）林芳学过英语或日语。）林芳学过英语或日语。（4）如果角）如果角A和角和角B是对顶角，则角是对顶角，则角A 等于角等于角B。解：（解：（1）设）设P：3是偶数。是偶数。 P（：表示并非）：表示

4、并非）（2）设）设P：2 是素数；是素数；Q：2是偶数。是偶数。 P Q ( :表示和表示和) （3）设）设P：林芳学过英语；：林芳学过英语；Q：林芳学过日语。：林芳学过日语。P Q( :表示或表示或)（4）设）设P：角：角A和角和角B是对顶角；是对顶角；Q：角：角A 等于角等于角B。PQ（个表示如果个表示如果则则）5校园课件12.联结词定义定义12.1 设P为任一命题，P的否定是一个新的命题，称为P的否定式，否定式，记作P。为否定联结词。否定联结词。 PP T F F T例例 p：3是偶数。是偶数。 p：3不是偶数。不是偶数。6校园课件定义定义12.2 设P、Q为两命题，复合命题“P并且Q”

5、（或“P和Q”）称为 P与Q的合取式，合取式，记作PQ，为合取联结词。合取联结词。表示自然语言中的“既又”， “不仅而且”， “虽然但是”PQP QTTTTFFFTFFFF7校园课件例例3将下列命题符号化。将下列命题符号化。（1）李平既聪明又用功。）李平既聪明又用功。（2）李平虽然聪明，但不用功。）李平虽然聪明，但不用功。（3）李平不但聪明，而且用功。）李平不但聪明，而且用功。（3）李平不是不聪明，而是不用功。）李平不是不聪明，而是不用功。解：设解：设P：李平聪明；：李平聪明；Q：李平用功。：李平用功。（1）P Q（2）P Q（3）P Q（4）（P）Q注意：不是见到注意：不是见到“和和” 、“

6、与与”就用就用 。例：例：“李文和李武是兄弟李文和李武是兄弟”，“王芳和陈兰是好朋友王芳和陈兰是好朋友”是简是简单命题。单命题。8校园课件定义定义12.3 设P、Q为两命题，复合命题“P或Q”称为 P与Q的析取式，析取式，记作PQ，为析取联结析取联结词。词。PQP QTTTTFTFTTFFF9校园课件 析取式析取式P Q表示的是一种相容性或，即允许表示的是一种相容性或，即允许P和和Q同时为真。同时为真。例：例：“王燕学过英语或日语王燕学过英语或日语” P Q自然语言中的自然语言中的“或或”具有二义性，有时表示具有二义性，有时表示不相容的或。不相容的或。例：例：“派小王或小李中的一人去开会派小王

7、或小李中的一人去开会” 。为排斥。为排斥性的或。性的或。P：派小王去开会；：派小王去开会；Q：派小李去开会。：派小李去开会。（P Q）（P Q） ， （P Q）（P Q）10校园课件定义定义12.4 设P、Q为两命题，复合命题“如果P，则Q”称作 P与Q的蕴涵式，蕴涵式，记作PQ，为蕴涵联蕴涵联结词。结词。PQP QTTTTFFFTTFFT11校园课件 在PQ中，Q是P的必要条件，P是Q的充分条件。表示自然语言 “只要P就Q” ，“P仅当Q”，“只有Q，才P”注意：注意：1.在自然语言中，在自然语言中，“如果如果P，则，则Q”中的中的P与与Q往往有某往往有某 种内在的联系，但在数理逻辑中，种内

8、在的联系，但在数理逻辑中，PQ中的中的P与与Q不一定有内在的联系。不一定有内在的联系。2.在数学中，在数学中，“如果如果P，则，则Q”表示表示P为真，为真，Q为真的为真的逻辑关系，但在数理逻辑中，当逻辑关系，但在数理逻辑中，当P为假时为假时PQ为真。为真。12校园课件例例4将下列命题符号化。将下列命题符号化。(1)只要不下雨，我就骑自行车上班。只要不下雨，我就骑自行车上班。(2)只有不下雨，我才骑自行车上班。只有不下雨，我才骑自行车上班。(3)若若 2+24，则太阳从东方升起。，则太阳从东方升起。(3)若若 2+24，则太阳从东方升起。，则太阳从东方升起。(4)若若 2+24，则太阳从西方升起

9、。，则太阳从西方升起。(5)若若 2+24，则太阳从西方升起。，则太阳从西方升起。解：在（解：在（1）、（）、（2）中，设）中，设P：天下雨；：天下雨；Q：我骑自行车上：我骑自行车上班。班。（1）PQ（2）Q P在（在（3）（）（6）中，设）中，设P： 2+24；Q：太阳从东方升起；：太阳从东方升起；R: 太阳从西方升起。太阳从西方升起。（1）PQ， 真值为真值为T （2）PQ， 真值为真值为T（3）PR ， 真值为真值为F （4）PR 真值为真值为T13校园课件定义定义1-2.5 设P、Q为两命题，复合命题“P当且仅当 Q”称作 P与Q的等价式，等价式，记作P Q， 为等价联结等价联结词。词

10、。PQ表示表示P与与Q互为充分必要条件互为充分必要条件。 PQP QTTTTFFFTFFFT14校园课件例例5将下列命题符号化。将下列命题符号化。（1）2+24，当且仅当，当且仅当3是奇数。是奇数。（2）2+24，当且仅当，当且仅当3不是奇数。不是奇数。（3）2+24，当且仅当，当且仅当3是奇数。是奇数。（4）2+24，当且仅当，当且仅当3不是奇数。不是奇数。（5）两圆的面积相等，当且仅当它们的半径相同。）两圆的面积相等，当且仅当它们的半径相同。（6）两角相等当且仅当它们是对顶角。）两角相等当且仅当它们是对顶角。解：（解：（1）（）（4）设）设P：2+24；Q：3是奇数。是奇数。（1）PQ 真

11、命题真命题（2）PQ 假命题假命题（3）PQ假命题假命题（4）PQ真命题真命题（5）设）设P：两圆的面积相等；：两圆的面积相等；Q：两圆的面积相同。：两圆的面积相同。PQ真命题真命题（6）设）设P：两角相等；：两角相等；Q：它们是对顶角。：它们是对顶角。 PQ假命题假命题15校园课件4.5种联结词的优先级顺序：种联结词的优先级顺序：， 16校园课件 1-3命题公式与翻译命题公式与翻译 1.命题公式命题公式命题公式：由命题常量、命题公式：由命题常量、命题变元命题变元、联结词、括号、联结词、括号 等组成的符号串。等组成的符号串。 命题公式中的命题变元称作命题公式的分量。命题公式中的命题变元称作命题

12、公式的分量。17校园课件定义定义13.1 （1）单个命题常量或命题变）单个命题常量或命题变 元元,Q,R,Pi,Qi,Ri,，F，T是合式公式。是合式公式。（2）如果）如果A是合式公式，则（是合式公式，则（A）也是合式公式。）也是合式公式。（3）如果）如果A、B是合式公式，则（是合式公式，则（A B）、（）、（A B）、（）、（AB）、（）、（AB）也是合式公式。）也是合式公式。（4）只有有限次地应用（）只有有限次地应用（1）（）（3）组成的符号）组成的符号串才是合式公式。串才是合式公式。例：例：P, P, (P), (0 P),P(PQ), (P Q) R) (R)是公式；是公式； PQR,

13、 (P), PQ)不是公式。不是公式。18校园课件2.翻译 翻译就是把自然语言中的有些句子符号化。翻译就是把自然语言中的有些句子符号化。复合命题符号化的基本步骤：复合命题符号化的基本步骤：（1）分析出各简单命题，将它们符号化。）分析出各简单命题，将它们符号化。（2）使用合适的联结词，把简单命题逐个联结起来，）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。组成复合命题的符号化表示。19校园课件例例 将下列命题符号化。将下列命题符号化。（1）小王是游泳冠军或是百米冠军。）小王是游泳冠军或是百米冠军。P Q（2）小王现在在宿舍或在图书馆。）小王现在在宿舍或在图书馆。P Q （排

14、斥性或，不可能同时为真）（排斥性或，不可能同时为真）(3)选小王或小李中的一人当班长。选小王或小李中的一人当班长。（P Q） （P Q）或）或 （PQ）（排斥性或，可能同时为真）（排斥性或，可能同时为真）PQ原命题原命题PQ（PQ）TTFTFTFTFTFTTFTFFFTF20校园课件(4)如果我上街，我就去书店看看，除非我很累。如果我上街，我就去书店看看，除非我很累。R(PQ) 或或 （R P）Q （除非：如果不）（除非：如果不）(5)王一乐是计算机系的学生，他生于王一乐是计算机系的学生，他生于1968年或年或1969年，他年，他是三好学生。是三好学生。P （Q R）S（6）我们要做到身体好、

15、学习好、工作好，为祖国四化建设）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。而奋斗。A：我们要做到身体好：我们要做到身体好B：我们要做到学习好：我们要做到学习好C：我们要做到工作好：我们要做到工作好P：我们要为祖国四化建设面奋斗。：我们要为祖国四化建设面奋斗。命题符号化形式为：（命题符号化形式为：（A B C） P21校园课件 14真值表与等价公式真值表与等价公式1.真值表真值表定义定义14.1含含n个（个（n1）个命题变元（分量）的命题公式，）个命题变元（分量）的命题公式，共有共有2n组真值指派。将命题公式组真值指派。将命题公式A在所有真值指派之下取值在所有真值指派之下取值的情况

16、列成表，称为的情况列成表，称为A的真值表。的真值表。构造真值表的步骤：构造真值表的步骤：(1)找出命题公式中所含的所有命题变元找出命题公式中所含的所有命题变元P1,P2,Pn。列出所。列出所有可能的真值指派。有可能的真值指派。(2)对应每种真值指派，计算命题公式的各层次的值，直到最对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。后计算出命题公式的值。22校园课件例例1 构造求构造求P Q的真值表。的真值表。PQPP QTTFTTFFFFTTTFFTT23校园课件例例2 给出（给出（P Q）P的真值表。的真值表。PQP QP （P Q）PTTTFFTFFFFFTFTFFF

17、FTF24校园课件例例3 给出（给出（P Q）（P Q）的真值表。）的真值表。PQ P QP QP Q（P Q）（P Q）TTFFTFTTFFTFFFFTTFFFFFFTTFTT25校园课件例例4 给出给出（P Q） （P Q）的真值表。）的真值表。PQP Q（P Q）PQ P Q（P Q） （P Q）T T TFFFFTT F FTFTTTF T FTTFTTF F FTTTTT 由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为（假），我们把这类公式记为T（F）。如例）。如例4和

18、例和例226校园课件2等价公式等价公式 从真值表中可以看到，有些命题公式在分量的各从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如种指派下，其对应的真值都完全相同，如P Q与与PQ的对应真值相同。的对应真值相同。PQPP QPQTTFTTTFFFFFTTTTFFTTT（P Q）（P Q）与）与PQ对应的真值相同。对应的真值相同。27校园课件 定义定义14.2 给定两个命题公式给定两个命题公式A和和B，设，设P1，P2，Pn为所有出现于为所有出现于A和和B中的原子变元中的原子变元,若给若给P1，P2，Pn任一组真值指派任一组真值指派,A和和B的真值都相同的真值都相同

19、,则则称称A和和B是是等价等价的或的或逻辑相等逻辑相等。记作。记作AB。例例5 证明证明PQ（PQ）（ QP） 证明证明 列出真值表列出真值表P Q PQ QP (PQ）( QP）PQT T TTTTT F FTFFF T TFFFF F TTTT28校园课件24个重要的等价式个重要的等价式PP 双重否定律双重否定律PP P等幂律等幂律PP PP QQ P交换律交换律P QQ P（P Q）RP （Q R）结合律结合律（P Q）RP （Q R）P （Q R）（P Q）（P R）分配律分配律P （Q R）（P Q）（P R）（P Q）P Q 德德摩根律摩根律（P Q）P Q29校园课件P （P Q

20、）P吸收律吸收律P （P Q）PP T T零律零律P F FP FP同一律同一律P T PP P T排中律排中律P P F矛盾律矛盾律PQ P Q蕴涵等价式蕴涵等价式P Q （PQ）（QP）等价等价式等价等价式PQ QP假言易位假言易位P Q P Q等价否定等价式等价否定等价式（PQ）（PQ）P归谬论归谬论 其中其中P、Q和和R代表任意的命题公式代表任意的命题公式。30校园课件例例6 验证吸收律验证吸收律P （P Q）P和和 P （P Q）PP Q P QP （P Q） P QP （P Q）T T TTTTT F FTTTF T FFTFF F FFFF31校园课件定义定义1-4.3 如果如果

21、X是合式公式是合式公式A的一部分的一部分,且且X本身也是一本身也是一个合式个合式 公式公式,则称则称X为公式为公式 A的子公式。的子公式。定理定理14.1如果如果X是合式公式是合式公式A的子公式，若的子公式，若XY，如果，如果将将A中的中的X用用Y来置换，所得到公式来置换，所得到公式B与公式与公式A等价，即等价，即AB。 证明证明 因为在相应变元的任一种指派下，因为在相应变元的任一种指派下，X与与Y的真值相同，故的真值相同，故以以Y取代取代X后，公式后，公式B与公式与公式 A在相应的指派下，其真值必相同，在相应的指派下，其真值必相同，故故AB。 满足定理满足定理14.1的置换称为等价置换（等价

22、代换）的置换称为等价置换（等价代换）32校园课件例例7 证明证明PQ（P Q）证明证明 PQ P Q， （根据蕴涵等价式）（根据蕴涵等价式） P Q （P q），（德），（德摩根律）摩根律） 即即Pq（P q）33校园课件 例例8 证明证明P(QR) (P Q) R证明证明 P(QR) P (QR) （蕴涵等价式）（蕴涵等价式）P (Q R) （蕴涵等价式）（蕴涵等价式）(P Q) R（结合律）（结合律）(P Q) R（德（德摩根律）摩根律）(P Q) R（蕴涵等价式）（蕴涵等价式）34校园课件例例9 证明证明 P(P Q) (P Q)证明证明 P P 1 (同一律同一律) P (Q Q)（排

23、中律）（排中律） (P Q) (P Q) （分配律）（分配律）35校园课件练习练习 1.证明证明 Q ( (P Q) P)T; 2.证明证明 (P P) ( (Q Q) R) F 3.证明证明 (PQ) PP36校园课件1,证明证明Q ( (P Q) P)Q ( (P P) (P Q) ) （分配律）（分配律）Q ( F (P Q) )（矛盾律）（矛盾律）Q (P Q)（同一律）（同一律） Q (P Q) （德（德摩根律）摩根律）(Q Q) P（结合律）（结合律）T P（排中律）（排中律）T（零律）（零律）37校园课件2.证明证明(P P) ( (Q Q) R)T( (Q Q) R)（排中律）

24、（排中律）T(F R)（矛盾律（矛盾律 ）TF（零律）（零律）T F（蕴涵等值式）（蕴涵等值式）F FF（等幂律）（等幂律）38校园课件3. 证明证明 (PQ) P(P Q) P（蕴涵等价值式）（蕴涵等价值式）P（吸收律）（吸收律）39校园课件1-5 重言式与蕴涵式重言式与蕴涵式 定义定义15.1 给定一命题公式给定一命题公式 ，若无论对分量作什么样的指，若无论对分量作什么样的指派，其对应的真值永为派，其对应的真值永为T，则称该命题公式，则称该命题公式 为为重言式重言式或或永真式永真式。 定义定义15.2 给定一命题公式给定一命题公式 ，若无论对分量作什么样的指，若无论对分量作什么样的指派，其

25、对应的真值永为派，其对应的真值永为F，则称该命题公式，则称该命题公式 为为矛盾式矛盾式或或永假式永假式。40校园课件 定理定理15.1 任何两个重言式的合取或析取，仍然是一个任何两个重言式的合取或析取，仍然是一个重言式。重言式。 定理定理15.2 一个一个 重言式，对同一分量，都重言式，对同一分量，都 用任何合式公用任何合式公式式 置换，其结果仍为一重言式。置换，其结果仍为一重言式。 证明证明 由于重言式的真值与分量的指派无关，帮对同一分由于重言式的真值与分量的指派无关，帮对同一分量以任何合式公式置换后，重言式的真值仍永为真。量以任何合式公式置换后，重言式的真值仍永为真。 对于矛盾式也有类似于

26、定理对于矛盾式也有类似于定理15.1和定理和定理51.2的结果。的结果。41校园课件例例1 证明证明 （PS）R）（P S）R）为）为重言式。重言式。证明证明 因为因为 P PTT，用，用（P S）R）置换）置换P得得 （P S）R）（P S）R）T42校园课件 定理定理15.3 设设A 、B为两命题公式为两命题公式AB ，当且仅当，当且仅当ABB为为一个重言式。一个重言式。证明证明 若若 AB ，则，则A、B有相同的真值，即有有相同的真值，即有AB 永为永为T。 若若 AB 为重言式，则为重言式，则AB 永为永为T， 故故A、B的真值相同，的真值相同，即即AB 。43校园课件例例2 证明证明

27、 （P Q）（P Q） 证明证明 做做（P Q） （P Q）的真值表。）的真值表。PQ P QP Q（P Q）P Q（P Q） P QTT TFFFFTTF FFTTTTFT FTFTTTFF FTTTTT由以上真值表可知，由以上真值表可知， （P Q） P Q 为重言式，根为重言式，根据定理据定理15.3得得 （P Q）（P Q）44校园课件定义定义15.3 当且仅当当且仅当 PQ Q 是重言式是重言式时，我，我们称称“ “P P蕴涵涵Q Q” ”，并并记作作PQPQ。做做PQ QP，PQ，Qp 的真值表的真值表PQ P QPQ QPQPPQTT FFTTTTTF FTFFTTFT TFTT

28、FFFF TTTTTT由此得由此得 PQ QP， QP PQ， 因此要因此要PQ，只要证明，只要证明QP，反之亦然。，反之亦然。45校园课件要证明要证明PQ，即证，即证PQ 是重言式，对于是重言式，对于PQ 来说，来说，除除P的真值取的真值取T，Q的真值取的真值取F这样一种指派时，这样一种指派时，PQ 的真值的真值为为F外，其余情况外，其余情况PQ 的真值为的真值为T，故要征，故要征PQ，只要对条，只要对条件件PQ 的前件的前件P，指定真值为，指定真值为T，若由此指出，若由此指出Q的真值为的真值为T，则则PQ 为重言式，即为重言式，即PQ 成立；同理，如对条件命题成立；同理，如对条件命题PQ

29、中，假定后件中，假定后件Q的真值为的真值为F，若由此推出，若由此推出P的真值为的真值为F，即推证了即推证了QP。 故故PQ成立。即成立。即 若若P为为T时，推出时，推出Q为为T 或若或若Q为为F时，推出时，推出P为为F 则则PQ。46校园课件例例1 推证推证Q （PQ ）P证法证法1 假定假定Q （PQ ）为）为T，则，则Q为为T，且，且PQ 为为T。 所以所以Q为为F，PQ 为为T， 所以所以P为为F，故，故P为为T。证法证法2 假定假定P为为F，则，则P为为T， 若若Q为为F，则，则PQ 为为F，Q （PQ ）为）为F， 若若Q为为T，则，则Q为为F，Q （PQ ）为）为F， 所以所以 Q

30、 （PQ ）P47校园课件 常用的蕴涵式如下：常用的蕴涵式如下：1.P Q P2.P Q Q3.PP Q4.PPQ5.QPQ 6.（PQ） P7.（PQ） Q8.P （PQ）Q9.Q （PQ ）p10.P （ P Q）Q11.（PQ ）（QR）PR12.（P Q）（PR）（QR）R13.（PQ ）（RS）（P R）（Q S）14.（PQ）（QR）（PR）48校园课件 定理定理15.4 设设P、Q为任意两个为任意两个 命题公式，命题公式，PQQ的充分的充分必要条件是必要条件是 P PQQ且且 Q QP P证明证明 若若PQ，则，则PQ为重言式。为重言式。 因为因为PQ （ PQ）（QP），），

31、故故 PQ为为T， 且且QP 为为T， 因为因为PQ 且且QP成立。成立。 反之，若反之，若PQ 且且QP， 则则PQ为为T， 且且QP 为为T， 因此因此PQ （ PQ）（QP）为）为T， 即即PQ 这个定理也可以作为两个公式等价的定义。这个定理也可以作为两个公式等价的定义。49校园课件蕴涵的几个常用的性质：蕴涵的几个常用的性质：（1）设）设A、B、C为合式公式，若为合式公式，若AB且且A为重言式，则为重言式，则B也也是重是重 言式。言式。 证明证明 因为因为 AB 永为永为T，所以当，所以当A为为T时，时，B必必T。（2）若）若AB，BC，则，则 AC 证明证明 由由AB， BC 得得AB

32、 ，BC 为重言式为重言式 所以（所以（AB）（BC）为重言式，）为重言式， 根据（根据（PQ ）（QR）PR 所以所以 （AB）（BC）AC， 由性质（由性质（1）得：）得： AC为重言式，即为重言式，即 AC50校园课件（3）AB，且，且AC，那么，那么A（B C） 证明证明 由假设知由假设知AB ，AC为重言式。为重言式。 设设A这这T，则，则B、C为为T， 故故B C为为T， 因此因此A（B C）为）为T， 若若A为为F，则，则A（B C）为）为T， 所以所以A（B C）51校园课件（4）若）若AB 且且 CB ，则，则A CB 证明证明 因为因为AB 为为T，CB为为T， 故（故（A

33、A B）（ C B）为）为T， 则（则（A C）B 为为T， 即即（A C）B为为T， 即即 （A C）B为为T， 所以（所以（A C）B 52校园课件 16 其他联结词其他联结词 定义定义16.3 设设P、Q是两个命题公式，复合命题是两个命题公式，复合命题P Q称称作作P和和Q的的“与非与非”。PQ（P Q） PQP QTTFTFTFTTFFT53校园课件联结词联结词“”的几个性质：的几个性质：（1） PP （P P）p（2） （PQ）（PQ）（PQ）P Q（3）（）（PP）（QQ）PQ （P q）P Q54校园课件 定义定义16.3 设设P、Q是两个命题公式，复合命题是两个命题公式，复合命

34、题P Q称作称作P和和Q的的“或非或非”。P Q（P Q） PQP QTTFTFFFTFFFT55校园课件联结词联结词“ ”的几个性质：的几个性质：（1） P P （P P）p（2） （P Q）（PQ）（PQ）P Q（3）（）（PP）（QQ）PQ P Q当有当有n个命题变元时，可构成个命题变元时，可构成22 n种不等价的命题种不等价的命题公式，如公式，如n2时，有时，有16种不等价的命题公式。，见种不等价的命题公式。，见27页页表表16.5。56校园课件最小联结词组：对于任何一个命题公式，都能由仅含这些联最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。结词的命题公式

35、等价代换。由于（由于（1）（）（PQQ）（PQ）（QP） （2）（）（PQ）P Q （3） P Q（ P Q） （4）P Q（P q） 故由故由“”、“”、“”，“”、“ ”这五个这五个联结词组成的命题公式，必可以由联结词组成的命题公式，必可以由，或或，组成组成的命题公式所替代。的命题公式所替代。57校园课件 17 对偶与范式对偶与范式 定义定义17.1在给定的命题公式在给定的命题公式A中，将中，将换成换成，换成换成，若有特殊变元，若有特殊变元F和和T亦相互取代，所得命题公式亦相互取代，所得命题公式A*称为称为A的对的对偶式。偶式。A和和A*互为对偶式。互为对偶式。例例1: P Q与与 P Q

36、, (P Q )与与 (P Q) ( P Q) R与与 (P Q) R (P T) Q 与与(P F) Q 均为对偶式均为对偶式.例例2：PQ、 P Q的对偶式。的对偶式。 解：解： PQ (P Q )，PQ的对偶式为的对偶式为(P Q) P Q（P Q） ，P Q的对偶式为的对偶式为(P Q )58校园课件 定理定理17.1设设A和和A*互为对偶式互为对偶式, P1,P2,Pn，是出现在，是出现在A和和A*中的全部的命题变元中的全部的命题变元,则则(1)A(P1,P2,Pn) A*(P1, P2, Pn)(2)A(P1, P2, Pn) A*(P1, P2, Pn)例例:设设 A(P,Q,R

37、) P (Q R) 得得:A*(P,Q,R) P (Q R) (1)由由知知:A(P,Q,R) P (Q R) 由由知知: A*(P, Q, R) P (Q R)所以所以: A(P,Q,R) A*(P, Q, R)类似地类似地,有有A(P, Q, R) A*(P,Q, R)59校园课件 定理定理17.2设设P1,P2,Pn 是出现有命题公式是出现有命题公式A和和B中的所有中的所有命题变元，若命题变元，若A B，则，则A* B*。 证明：因为证明：因为A B， 即即A(P1,P2,Pn) B(P1,P2,Pn) 是重言式，是重言式， A(P1, P2, Pn) B(P1, P2, Pn) 是重是

38、重言式，言式， 故故A(P1, P2, Pn) B(P1, P2, Pn) 由定理由定理17.1得得 A*(P1,P2,Pn) B*(P1,P2,Pn) 因此因此A* B*60校园课件例例4 如果如果A(P,Q,R) 是是P（Q （RP），求它的对偶式），求它的对偶式A*(P,Q,R) 。并求与。并求与A及及 A*等价，但仅包含联结词等价，但仅包含联结词“”、“”、“”的公式。的公式。解：解： 因因 A(P,Q,R) 是是 P（Q （RP） 故故 A*(P,Q,R) 是是P （Q （RP） 但但P（Q （RP） P（Q （R P） （P （Q （R P） 所以所以P （Q （RP） (P （Q

39、 （R P）) 61校园课件 定义定义17.2 一个命题公式一个命题公式 称为称为合取范式合取范式，当且仅当它具有形，当且仅当它具有形式式A1A2 An（n1）。其中）。其中A1，A2，An 都是命题变都是命题变元或其否定所组成的析取式。元或其否定所组成的析取式。例例P(P Q) (P P ) (P R) 定义定义17.3 一个命题公式一个命题公式 称为称为析取范式析取范式，当且仅当它具有，当且仅当它具有形式形式A1 A2 An（n1）。其中）。其中A1，A2，An 都是命题都是命题变元或其否定所组成的合取式。变元或其否定所组成的合取式。例例 (P Q R) (P Q) (P Q R) 62校

40、园课件求合取范式或求合取范式或 析取范式的步骤：析取范式的步骤：（1）将公式中的联结词化归成）将公式中的联结词化归成、。（2）将）将消去或内移。消去或内移。（3）利用分配律、交换律求合取范式或析取范式。）利用分配律、交换律求合取范式或析取范式。 （求合取范式：（求合取范式：对对； 求析取范式：求析取范式： 对对 ）注意任何命题的析取范式和合取范式都不是唯一的。注意任何命题的析取范式和合取范式都不是唯一的。63校园课件例求下面命题公式的合取范式和析取范式。例求下面命题公式的合取范式和析取范式。（P Q）R）P解（解（1）求合取范式）求合取范式（P Q）R）P（P Q）R）P(P Q) R) P(

41、P Q) R) P(P Q) R) P(P Q) R) P(P Q) R) P(P Q P) (R P)（P Q）(R P) (2)求析取范式求析取范式(P Q) R) P(P R) (Q R) PP （P R） (Q R)P (Q R)64校园课件练习：求下面命题公式的合取范式和析取范式。练习：求下面命题公式的合取范式和析取范式。 （1）求合取范式）求合取范式(PQ) R (P Q) R(P Q) R) (R(P Q)(P Q) R) (R (P Q)(P Q) R) (R P Q)(P R) (Q R) (R P Q)（2）求析取范式）求析取范式(P Q) R) (R P Q)（(P Q)

42、 (R P Q)）(R (R P Q)(P Q) R) (P Q) P) (P Q) Q) (R R) (R P) (R Q) (P Q R) (P P Q) (P Q Q) (R R) (P R) (Q R) (P Q R) (P R) (Q R)65校园课件定义定义17.4 n个命题变元的合取式，称作布尔合取或小个命题变元的合取式，称作布尔合取或小项，其中变元与它的否定不能同时存在，但两者必须出项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。现且仅出现一次。 n个命题变元个命题变元 共有共有2n个小项。个小项。例两个命题变元例两个命题变元 P和和Q，其小项为：，其小项为：P

43、 Q，P Q，P Q，P Q66校园课件3个命题变项个命题变项P、Q、R可形成可形成8个小项：个小项：m000 P Q Rm001P Q Rm010P Q R m011P Q Rm100P Q R M101P Q R m110P Q R m111P Q R67校园课件小项的性质：小项的性质：（1）每一个小项当其真值指派与编码相同时，其真值为）每一个小项当其真值指派与编码相同时，其真值为T，其余均为，其余均为F。（2）任意两个不同小项的合取永为）任意两个不同小项的合取永为F。（3） m0 m1 m2 m3 m4 m5 m6 m7T68校园课件 定义定义17.3 对于给定的命题公式，如果有一个等对

44、于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。作原式的主析取范式。 定理定理17.3 在真值表中，一个在真值表中，一个 公式的真值为公式的真值为T的的指派所对小项的析取，即为此公式的主析取范式。指派所对小项的析取，即为此公式的主析取范式。69校园课件例例6给定给定P Q，P Q和和（P Q），求这些公式的主析），求这些公式的主析取范式。取范式。解：真值表如下：解：真值表如下：PQP QP Q（P Q）TTTTFTFFTTFTTTTFFTFT故故P Q（P Q）（P Q）（P Q） P Q（P Q）（P

45、Q）（P Q）（P Q）（P Q）（P Q）（P Q）70校园课件例例7 设一公式设一公式A的真值表如下，求公式的真值表如下，求公式 A的主析取范式。的主析取范式。PQRATTTTTTFFTFTFTFFTFTTFFTFFFFTFFFFT解解 公式公式A的主析取范式的主析取范式 为：为：A（P Q R）（P R R）（P Q R）71校园课件例例8 求（求（P Q）（P R）（Q R）的主析取范）的主析取范式。式。解：原式解：原式（P Q （R R） （P R （Q Q） （Q R （P p） （P Q R）（P Q R） （P Q R）（P Q R） （P Q R）（P Q R） （P Q R

46、）（P Q R） （P Q R）（P Q R）72校园课件例例9求求P（P PQ）（Q P）的主析取）的主析取范式。范式。解：原式解：原式P （P Q）（Q P） P （P Q P）（Q Q P） P （Q P） P （Q Q）（P Q） （P Q）（P Q）（P Q）73校园课件求主析取范式的步骤：求主析取范式的步骤：（1）求析取范式。）求析取范式。（2）去掉永假的析取项。）去掉永假的析取项。（3）去掉重复的合取项、合并相同变元。）去掉重复的合取项、合并相同变元。（4）对合取项补入没出现的命题变元。（）对合取项补入没出现的命题变元。（P P）74校园课件 定义定义17.6 n个命题变元的析取

47、式，称作布尔析取个命题变元的析取式，称作布尔析取或大项，其中变元与它的否定不能同时存在，但两者或大项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。必须出现且仅出现一次。 n个命题变元个命题变元 共有共有2n个小项。个小项。例例 两个命题变元两个命题变元 P和和Q，其小项为：，其小项为：P Q，P Q，P Q，P Q 75校园课件3个命题变项个命题变项P、Q、R可形成可形成8个大项：个大项：M000 P Q RM001P Q RM010P Q R M011P Q RM100P Q R M101P Q R M110P Q R M111P Q R76校园课件大项的性质：大项的性质：（

48、1）每一个大项当其真值指派与编码相同时，其真）每一个大项当其真值指派与编码相同时，其真值为值为F，其余均为，其余均为T。（2）任意两个不同大项的析取永为）任意两个不同大项的析取永为T。（3） M0 M1 M2 M3 M4 M5 M6 M7F77校园课件定义定义17.7 对于给定的命题公式，如果有一个等价公对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。的主合取范式。 定理定理17.4 在真值表中，一个公式的真值为在真值表中，一个公式的真值为F的指的指派所对大项的合取，即为此公式的主合取范式。派所对大项

49、的合取，即为此公式的主合取范式。78校园课件例例10 利用真值表求（利用真值表求（P Q）（P R）的主合取范式与主）的主合取范式与主析取范式。析取范式。PQRP QP R（P Q）（P R）TTTTFTTTFTFTTFTFFFTFFFFFFTTFTTFTFFFFFFTFTTFFFFFF79校园课件主合取范式：主合取范式：（P Q R）（P Q R）（P Q R）（P Q R）主析取范式：主析取范式：（P Q R）（P Q R）（P Q R）（P Q R）80校园课件求主合取范式的步骤：求主合取范式的步骤：（1）求合取范式。）求合取范式。（2）去掉所有为）去掉所有为T的合取项。的合取项。（3）

50、合并相同的析取项和变元。）合并相同的析取项和变元。（4）补入没出现的命题变元。（即添加）补入没出现的命题变元。（即添加P P）81校园课件例11 求（P Q）（P R）的主合取范式。）的主合取范式。解：原式解：原式 （P Q）P）（P Q）R） （P p）（Q p）（P R）（Q R） （Q p）（P R）（Q R） （Q P （R R） （ P R （Q Q） （Q R （P P） （Q P R）（Q P R） （P R Q）（P R Q） （Q R P）（Q R P） （P Q R）（P Q R） （P Q R）（P Q R）82校园课件用用表示小项的析取表示小项的析取用用表示大项的合取表

51、示大项的合取例如例如（P Q）（P R） （P Q R）（P Q R） （P Q R）（P Q R） M000 M010 M100 M101 0,2,4,5 m001 m011 m110 m111 1,3,6,783校园课件 1-8推理理论推理理论推理是从前提推出结论的思维过程推理是从前提推出结论的思维过程,前提是指已前提是指已知的命题公式知的命题公式,结论是从前提出发应用推理规则推出结论是从前提出发应用推理规则推出来的命题公式。前提可以是多个来的命题公式。前提可以是多个 。定义定义18.1设设H1，H2，H n ，C是命题公式，若是命题公式，若（H1 H2 Hn）C为重言式为重言式,则称则称

52、C是一组前提是一组前提H1,H2,Hn的有效结论。记作：的有效结论。记作： H1 H2 Hn C 真值表法真值表法推理方法推理方法 直接证法直接证法 间接证法间接证法84校园课件（1）真值表法）真值表法 若若H1，H2，H n 都为都为T的行，的行，C也为真；也为真；或若或若C为假的行，为假的行，H1，H2，H n 中至少有一个为假中至少有一个为假则则 H1 H2 Hn C 成立。成立。85校园课件例例1 一份统计表格的错误或者是由于材料不可靠，或者是由一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，于计算有错误；这份统计表格的错误不是由于材

53、料不可靠，所以这份统计表格是由于计算有错误。所以这份统计表格是由于计算有错误。解：设解：设 P：统计表格的错误是由于材料不可靠。：统计表格的错误是由于材料不可靠。 Q：统计表格的错误是由于计算不可靠。：统计表格的错误是由于计算不可靠。 前提是：前提是：P Q，P ，结论是：是：Q ，即，即证明明 （ P Q） P QPQP QPTTTFTFTFFTTTFFFT故（故（ P Q） P Q86校园课件 例例2 如果张老师来了，这个问题可以得到解答，如如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个

54、问题就可以得到解答。老师或李老师来了，这个问题就可以得到解答。解：设解：设P：张老师来了。：张老师来了。 Q：李老师来了。：李老师来了。 R：这个问题可以得到解答。：这个问题可以得到解答。 本题可译为：本题可译为： （P R）（QR）（P Q）R87校园课件PQRPRQRP QTTTTTTTTFFFTTFTTTTTFFFTTFTTTTTFTFTFTFFTTTFFFFTTF88校园课件（2）直接证法）直接证法 就是由一组前提，利用一些公认的推理规则，根据已知的等就是由一组前提，利用一些公认的推理规则，根据已知的等价公式或蕴涵公式，推出有效结论。价公式或蕴涵公式，推出有效结论。 P规则：前提在推导

55、过程中随时可以引用。规则：前提在推导过程中随时可以引用。 T规则：已经推出的公式在以后的推导过程中可随时引用。规则：已经推出的公式在以后的推导过程中可随时引用。 常用蕴涵式见常用蕴涵式见43页表页表18.389校园课件例例1 证明（证明（P Q）（PR）（ QS）S R 证法证法1 （1）P Q P （2）PQ T（1）E （3） QS P （4）PS T（2），（），（3）I （5）SP T（4）E （6）PR P （7）SR T（5），（），（6）I （8）S R T（7）E 90校园课件证法证法2 （1）PR P （2） P QR Q T（1）I （3）QS P （4）Q RS R T（

56、3）I （5）P QS R T（2），（），（4）I （6）P Q P （7）S R T（5），（），（6）I91校园课件例例2 证明（证明（W R）V，VC S，SU，C U W证明证明 （1） C U P （2）U T（1）I （3） SU P （4）S T（2）,（3）I (5) C T（1）I (6) C S T(4),(5) I (7) (C S) T(6)E (8) （W R）V P (9) V(C S) P (10) （W R）(C S) T(8),(9)I (11) (（W R） T(7),(10)I (12) W R T(11)E (13) W T(12)E92校园课件(3)

57、 间接证法间接证法1(归谬法归谬法) 要证要证 H1 H2 Hn C 即要证即要证 H1 H2 Hn C 为重言式为重言式 H1 H2 Hn C (H1 H2 Hn ) C (H1 H2 Hn C)因此只要证因此只要证 H1 H2 Hn C 为矛盾式为矛盾式. 93校园课件例例3 证明证明 AB, (B C)可逻辑推出可逻辑推出A证明证明 (1) AB P (2) A P(附加前提附加前提) (3) (B C) P (4) B C T(3)E (5) B T(1),(2)I (6) B T(4) I (7) B B (矛盾矛盾) T(5),(6) I 94校园课件例例4 证明证明 (P Q)

58、(PR) (QS) S R证明证明 (1) (S R) P (2) S R T(1)E (3) P Q P (4) PQ T(3)E (5) QS P (6) PS T(4),(5) I (7) SP T(6) (8) (S R ) (P R) T(7) I (9) P R T(2),(8) I (10) PR P (11) P R T(10)E (12) (P R ) T(11)E (13) (P R ) (P R ) (矛盾) T(9),(12) I95校园课件(4) 间接证法间接证法2(附加前提法附加前提法)要证要证 H1 H2 Hn RC 只要证只要证 ( H1 H2 Hn )(R C

59、) 为重言式为重言式 (H1 H2 Hn )(R C) ( H1 H2 Hn ) (R C)( H1 H2 Hn R ) C ( H1 H2 Hn R) C 只要证只要证 ( H1 H2 Hn R) C 由由 (S R) C 证得证得S(R C) 称为称为CP规则规则。96校园课件例例5 证明证明 A (BC), D A, B 重言蕴涵重言蕴涵 DC证明证明 (1) D P(附加前提附加前提) (2) D A P (3) A T(1),(2) I (4) A (BC) P (5) BC T(3),(4) I (6) B P (7) C T(5),(6) I (8) DC CP97校园课件例例6

60、 设有下列情况设有下列情况,结论是否有效结论是否有效?(a) 或者是天晴或者是天晴,或者是下雨。或者是下雨。(b) 如果是天晴，我去看电影。如果是天晴，我去看电影。(c) 如果我去看电影，我就不看书。如果我去看电影，我就不看书。结论：如果我在看书则天在下雨。结论：如果我在看书则天在下雨。解解 若设若设 M：天晴。：天晴。 Q：下雨：下雨 。 S：我看电影。：我看电影。 R：我看书。：我看书。即证：即证：MQQ，MMS，SR，推出，推出RQ其中其中 M Q (MQQ）98校园课件 (1) R P（附加前提）（附加前提） (2) SR P (3) R S T(2) E (4) S T(1),(3)

61、 I (5) MS P (6) M T(4),(5) I (7) (M Q） P (8) M Q T(7) E (9) ( MQ) (QM) T(8) E (10) QM T(9) I (11) MQ T(10) E (12) Q T(6),(11) I (13) RQ CP 99校园课件第二章第二章 谓词逻辑谓词逻辑 原子命题是命题逻辑研究的基本单位原子命题是命题逻辑研究的基本单位,没有对原子没有对原子的内部结构及其相互之间的逻辑关系进行分析的内部结构及其相互之间的逻辑关系进行分析,这样这样就无法处理一些简单而又常见的推理问题。就无法处理一些简单而又常见的推理问题。例如例如: 所有的人都是要

62、死的，苏格拉底是人，所以所有的人都是要死的，苏格拉底是人，所以,苏苏格拉底是要死的。格拉底是要死的。P: 所有的人是要死的所有的人是要死的.Q: 苏格拉底是人苏格拉底是人.R: 所以所以,苏格拉底是要死的苏格拉底是要死的P QRR 不是重言式。不是重言式。 100校园课件 21 谓词的概念与表示谓词的概念与表示原子命题由主语和谓语两部分组成。原子命题由主语和谓语两部分组成。主语一般是客体。主语一般是客体。客体：可以是一个具体的事物，也可以是一种抽象客体：可以是一个具体的事物，也可以是一种抽象事物。是命题所研究的对象。事物。是命题所研究的对象。谓词：用以刻划客体的性质或客体之间的性质。谓词：用以

63、刻划客体的性质或客体之间的性质。例例 李明是一个学生。李明是一个学生。 李明比王杰高。李明比王杰高。 哥白尼指出地球绕着太阳转。哥白尼指出地球绕着太阳转。101校园课件谓词用大写字母表示。谓词用大写字母表示。客体名称用小写字母表示。客体名称用小写字母表示。客体常元：客体常元：表示具体或特定的客体的词。表示具体或特定的客体的词。一般用小写字母一般用小写字母a,b,c,表示。表示。客体变元：客体变元：表示抽象的或泛指的客体的词。表示抽象的或泛指的客体的词。一般用小写字母一般用小写字母x,y,z,表示。表示。 例如：例如：A表示表示“是个大学生是个大学生”， c表示张三，表示张三， e表示李四，表示

64、李四， 则则 A（c）表示）表示“张三是个大学生张三是个大学生”， A（e）表示）表示“李四是个大学生李四是个大学生”，102校园课件 “b是是A” 类型的命题可用类型的命题可用A（b）表示。）表示。 两个客体之间关系的命题可表示为两个客体之间关系的命题可表示为B（a,b）。）。 A（b）为一元谓词。）为一元谓词。 B（a,b）为二元谓词。依此类推。）为二元谓词。依此类推。 单独一个谓词不是命题，只有将变元单独一个谓词不是命题，只有将变元x,y,z等取特等取特定客体时，才确定了一个命题。定客体时，才确定了一个命题。103校园课件 22 命题函数与量词命题函数与量词 定义定义22.1 由一个谓词

65、，一些客体变元组成的表达由一个谓词，一些客体变元组成的表达式称为式称为简单命题函数简单命题函数。 例例 B（x,y）。）。 n元谓词就是有元谓词就是有n个客体变元的命题函数。个客体变元的命题函数。 当当n0时，它本身就是一个命题。时，它本身就是一个命题。 104校园课件由一个或几个简单命题函数以及联结词组合而成由一个或几个简单命题函数以及联结词组合而成的表达式称为的表达式称为复合命题函数复合命题函数。 例例1 （1） 2是素数且是偶数。是素数且是偶数。 解：解： 设设A（x）：）：x是素数；是素数； B（x）：）：x是偶数；是偶数； a：2 则命题表示为：则命题表示为： A（a）B（a） （2

66、）如果）如果2大于大于3，则，则2大于大于4。 解：解： 设设L（x,y）：）：x大于大于y； a ：2； b：3 ； c：4 则命题表示为：则命题表示为：L（a,b）L（a,c）。）。105校园课件（3）如果张明比李民高，李民比赵亮高，则张明）如果张明比李民高，李民比赵亮高，则张明比赵亮高。比赵亮高。 解：设解：设 H（x,y）：）：x比比y高；高； a：张明；：张明； b：李民；：李民； c：赵亮。：赵亮。 则命题符号化为则命题符号化为 ： H（a,b）H（b，c）H（a,c）。）。 命题函数不是命题，只有客体变元取特定客体命题函数不是命题，只有客体变元取特定客体名称时，才能成为命题。名称

67、时，才能成为命题。106校园课件 个体域个体域：客体变元的取值范围。：客体变元的取值范围。 个体域可以是有限的，也可以是无限的。个体域可以是有限的，也可以是无限的。 例例 学生、工人，实数，学生、工人，实数，a,b，c。 全总个体域：全总个体域：宇宙间的一切事物。宇宙间的一切事物。107校园课件量词：表示数量的词。量词：表示数量的词。全称量词全称量词“” 用用来来表表达达“对所有的所有的”、“每一每一个个”，“对任何一任何一个个”。例例2 （1）所有的人都是要呼吸的。）所有的人都是要呼吸的。解：设解：设M（x）：）：X是人；是人； H（x）：）：x要呼吸。要呼吸。 则符号化为：（则符号化为：（

68、x）（）（ M（x） H（x） 域为全总域。域为全总域。108校园课件（2）每个学生都要参加考试。）每个学生都要参加考试。 解：设解：设P（x）：）：x是学生；是学生；Q（x）：）：x要参加考试。要参加考试。符号化为符号化为: （x）（）（ P（x）Q（x） (3) 任何整数或是正的或是负的。任何整数或是正的或是负的。 解：设解：设 I（x）：）：x是整数；是整数； R（x）：）：X是正数；是正数； M（x）：）：x是负数。是负数。符号化为：（符号化为：（x）（）（ I（x）R（x） M（x）109校园课件存在量词存在量词“”：表示表示“存在一些存在一些”。例例3 （1）存在一个数是质数。）存

69、在一个数是质数。解：设解：设 P（x）：）：x是质数。是质数。 符号化为：符号化为： （x ）（ P（x） （2）一些人是聪明的。）一些人是聪明的。 解：设解：设 M（x）：）：x是；是； R（x）：）：x是聪明的。是聪明的。 符号化为：（符号化为：（x ）（ M（x）R（x） 110校园课件注意：注意：（1）在不同的个体域中，命题符号化的形式可）在不同的个体域中，命题符号化的形式可能不一样。能不一样。（2）如果事先没有给出个体域，都应以全总个）如果事先没有给出个体域，都应以全总个体域为个体域。体域为个体域。（3）在引入特性谓词后，使用全称量词与存在）在引入特性谓词后，使用全称量词与存在量词符

70、号化的形式是不同的。量词符号化的形式是不同的。 对全称量词，特性谓词常作蕴涵的前件；对全称量词，特性谓词常作蕴涵的前件； 对存在量词，特性谓词常作合取对存在量词，特性谓词常作合取 项。项。111校园课件例：（例：（1）所有的人都是要死的。）所有的人都是要死的。 （2）有的人活百岁以上。）有的人活百岁以上。 解：解：第一种情况：考虑个体域第一种情况：考虑个体域D为人类集合。为人类集合。（1）符号化为：）符号化为：x F(x)。 其中其中F(x)：x是要死的。是要死的。（2）xF(x)。 其中其中F(x)：x活百岁以上。活百岁以上。第二种情况：考虑个体域为全总个体域，第二种情况：考虑个体域为全总个

71、体域，对所有个体而言，如果它是人，则它是要死的。对所有个体而言，如果它是人，则它是要死的。存在着个体，它是人并且活百岁以上存在着个体，它是人并且活百岁以上/引进特性谓词：引进特性谓词：M（x）：）：X是人。是人。（1）符号化为：）符号化为：x（M（x） F(x)）（2）符号化为：）符号化为：x（M（x）F(x)）112校园课件 23 谓词公式与解释谓词公式与解释原子谓词公式：若原子谓词公式：若P（x1,x2,xn）是）是n元谓词，则元谓词，则称称P（ x1,x2,xn）是）是原子谓词公式原子谓词公式。 其中其中x1,x2,xn是客体变元。是客体变元。例例 Q， R（x），），A（x,y), A

72、(f(x),y), A(a,y,z) 113校园课件合式公式合式公式定义如下：定义如下：（1）原子公式是合式公式；）原子公式是合式公式；（2）若）若A是合式公式，则（是合式公式，则（A）也是合式公式；）也是合式公式；（3）若）若A、B是合式公式，则（是合式公式，则（A B）、（）、（A B）、）、（A B）、（）、（AB）也是合式公式；）也是合式公式；（4）若）若A是合式公式，则是合式公式，则xA、xA也是合式公也是合式公式；式；（5）只有有限次地使用）只有有限次地使用(1)(4）生成的符号串才是）生成的符号串才是合式公式合式公式.114校园课件例例1并非每个实数都是有理数。并非每个实数都是有

73、理数。解：设解：设 R（x）：）：x是实数；是实数； Q（x）：）：x是有理数。是有理数。 谓词公式为：谓词公式为：（x R(x) Q（x）例例2 一切人都不一样高。一切人都不一样高。解：设解：设M（x）：）：x是人；是人； H（x，y）：）：x y； L（x，y）：）：x与与y一样高。一样高。谓词公式为：谓词公式为：x y （M(x) M（x）H（x，y）L（x，y） 115校园课件例例3 每个自然数都有后继数。每个自然数都有后继数。解：设解：设F（x）：）：x是自然数；是自然数； H（x，y）：）：y是是x的后继数。的后继数。谓词公式为：谓词公式为： x（ F(x) y（ F(y) H（x

74、，y）例例4 这只大红书包摆满了那些古书。这只大红书包摆满了那些古书。解：设解：设F（x，y）：）：x摆满了摆满了y； Q（y）：）：y是古书；是古书； a: 这只；这只； b：那些。：那些。谓词公式为：谓词公式为： R（a）Q（b）F(a, b)116校园课件 24 变元的约束变元的约束1、变元的约束、变元的约束 定义定义24.1 在合式公式在合式公式xA或或xA中中,称称x为指导为指导变项，称变项，称A为相应量词的辖域。在辖域中，为相应量词的辖域。在辖域中，x的所有的所有出现称为出现称为约束出现（即约束出现（即x受相应量词指导变元的约束），受相应量词指导变元的约束），A中不是约束出现的其它

75、变元称为中不是约束出现的其它变元称为自由出现自由出现。117校园课件例例1 指出下列合式公式中的指导变元、量词的辖域指出下列合式公式中的指导变元、量词的辖域与客体变元的自由出现和约束出现。与客体变元的自由出现和约束出现。(1) x(F(x) yH(x,y);(2) xF(x) G(x,y);(3) xy(R(x,y) L(y,z) x H(x,y) 118校园课件2、变元的改名（1） 约束变元的改名：约束变元的改名： 将量词的辖域中出现的某个约束出现的客体变元及对应的指导变元，改成作用域上未出现的变元名称，公式其余部分不变。（换名规则）（2）自由变元的改名：）自由变元的改名： 将自由变元用原公

76、式中的所有客体变元符号不同的变元符号去代替，且处处代替。（代替规则） 119校园课件例例2：在：在xF(x) G(x,y)中，中，利用换名规则，将约束出现的利用换名规则，将约束出现的x改成改成z,得：得： z F(z) G(x,y)。利用代替规则，将自由出现的利用代替规则，将自由出现的x用用z代替，得：代替，得：xF(x) G(z ,y)。例例3：在：在x y(R(x,y) L(y,z) x H(x,y)中，中，将将x H(x,y)中的中的x利用换名规则换成利用换名规则换成t,对对y利用代替规利用代替规则，用则，用w代替，得：代替，得：x y(R(x,y) L(y,z) t H(t,w).12

77、0校园课件3、谓词公式的解释、谓词公式的解释谓词公式的解释谓词公式的解释:对谓词公式中各种变项用具体的常项对谓词公式中各种变项用具体的常项元去代替。通过对谓词的解释，求出谓词公式的真值。元去代替。通过对谓词的解释，求出谓词公式的真值。谓词公式的解释由四部分组成谓词公式的解释由四部分组成（1）非空的个体域）非空的个体域D；（2）D中的一些特定元素；中的一些特定元素；（3）D上一些特定函数；上一些特定函数；（4）D上的一些特定的谓词。上的一些特定的谓词。121校园课件例例4 给定解释给定解释I如下：如下：1）DI2，3；2）DI中特定元素中特定元素a=2;3）函数）函数f(x)为为 f(2)=3,

78、f(3)=2;4）谓词）谓词 F(x)为为 F(2)=F,F(3)=T;G(x,y) 为为G(i,j)= T, i,j=2,3;L(x,y)为为 L(2,2)=L(3,3)=T, L(2,3)=L(3,2)=F;在解释在解释I下下,求求x(F(x) G(x, a)的真值。的真值。 解解: x(F(x) G(x, a) （F（2）G（2，2）（F（3）G （3，2） （F T）（T T） F122校园课件例例5给定解释给定解释I如下：如下：1）DI2，3；2）DI中特定元素中特定元素a=2;3）函数）函数f(x)为为 f(2)=3,f(3)=2;4）谓词）谓词 F(x)为为 F(2)=F,F(3

79、)=T;G(x,y) 为为G(i,j)=T,i,j=2,3;L(x,y)为为 L(2,2)=L(3,3)=T, L(2,3)=L(3,2)=F;在解释在解释I下下,求求x (F(f(x) G(x,f(x)的真值。的真值。 解：解： x (F(f(x) G(x,f(x) （F(f(2）G（2，f（2） (F(f(3) G(3,f(3) (F(3) G(2,3) (F(2) G(3,2) (T T) (F T) T123校园课件例例6 给定解释给定解释I如下：如下：1）DI2，3；2）DI中特定元素中特定元素a=2;3）函数）函数f(x)为为 f(2)=3,f(3)=2;4）谓词）谓词 F(x)为

80、为 F(2)=F,F(3)=T;G(x,y) 为为G(i,j)=T, i,j=2,3;L(x,y)为为 L(2,2)=L(3,3)=T, L(2,3)=L(3,2)=F;在解释在解释I下下,求求 x yL(x,y)的真值。的真值。 解：解： x yL(x,y) (L(2,2) (L(2,3) (L(3,2) L(3,3) T TT124校园课件4、谓词公式的类型、谓词公式的类型定义定义 设设A为一谓词公式，如果为一谓词公式，如果A在任何解释下在任何解释下都是真的，则称都是真的，则称A为为逻辑有效式逻辑有效式（或称（或称永真式永真式）；）；如果如果A在任何解释下都是假在任何解释下都是假 的，则称

81、的，则称A是是矛盾式矛盾式（或称（或称永假式永假式）；若至少存在一个解释使）；若至少存在一个解释使A为真，为真，则称则称A是是可满足式可满足式。 125校园课件例例7 判断下列公式中哪些是逻辑有效式判断下列公式中哪些是逻辑有效式?哪些是哪些是矛盾式矛盾式?（1）x F（x）xF（x）解解:(1)设设I为任意的解释为任意的解释,其个体域为其个体域为D. 若存在若存在x0 D,使得使得F（x0）为假）为假,则则x F（x）为假）为假,所以所以x F（x）xF（x）为真）为真. 若对任意的若对任意的x D,都有都有F（x）为真）为真, 则有则有 x F（x）, xF（x）为真）为真,所以所以x F（

82、x）xF（x）为）为真真. 故在任何解释故在任何解释I下下,原公式为真原公式为真,由于由于I的任意的任意性性,所以原公式为逻辑有效式。所以原公式为逻辑有效式。126校园课件（2）x F（x）( x yG（x, y）x F（x）)解：因为解：因为P(QP) P(Q P) P (Q P) (P P) QT由于由于P(QP) 是重言式是重言式,而而(2)中公式是该式的代换中公式是该式的代换实例实例,因而（因而（2）是逻辑有效式。）是逻辑有效式。（3）x F（x）( xF(x) yG（y）)解：因为解：因为 P(P Q) P (P Q) (P P) Q T由于由于P(P Q) 是重言式是重言式,而而(

83、3)中公式是该式的代换中公式是该式的代换实例实例,因而是逻辑有效式。因而是逻辑有效式。127校园课件（4）(F(x,y) R(x,y) R(x,y)解：因为解：因为(PQ) Q (P Q) Q P Q Q F (4) 中公式是中公式是(PQ) Q的代换实例的代换实例,而而(PQ) Q是重言式是重言式, 因而因而(4)中的公式是逻辑有效式。中的公式是逻辑有效式。128校园课件 25 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式 定义定义25.1 设设A和和B是谓词公式，若是谓词公式，若A和和B在任何解释在任何解释下的取值都相同，则称下的取值都相同，则称A和和B是等价的，记为是等价的，记为AB

84、。（1）命题公式的推广：）命题公式的推广：如：如： x（ P(x)Q(x) x(P（x） Q(x) ) x P(x) yR（x, y） ( x P(x) yR(x, y) ) x H（x, y） x H（x, y）F129校园课件(2)量词与联结词量词与联结词之间的关系之间的关系例例1 设设P(x): x今天来上课今天来上课,则则p(x):x今天没来上课今天没来上课. 不是所有的人今天来上课与存在一些人今天没来上课不是所有的人今天来上课与存在一些人今天没来上课意义相同意义相同.即即: x P（x）x P（x）不存在一些人今天来上课与所有的人今天都没来上课不存在一些人今天来上课与所有的人今天都没

85、来上课相同相同. x P（x）x P（x） 关于量词的转化律可以在有限个体域上证明关于量词的转化律可以在有限个体域上证明.130校园课件(3)量词作用域的扩张与收缩量词作用域的扩张与收缩x (A（x）B) ( x A（x）B) x (A（x）B) ( x A（x）B) x (A（x）B) ( x P（x）B) x (A（x）B) ( x P（x）B) ( x A（x）B) x ( A（x）B)( x A（x）B) x (A（x）B)(B x A（x）) x (BA（x）)(B x A（x）) x (B A（x）)131校园课件例例2 证明证明 ( x A（x）B) x ( A（x）B)证明:

86、( x A（x）B) x A（x）B x A（x）B x ( A（x）B) x (A（x）B) 132校园课件(4)量词与命题联结词之间的一些等式量词与命题联结词之间的一些等式例如例如 联欢会上所有人既唱歌又跳舞和联欢会上所有联欢会上所有人既唱歌又跳舞和联欢会上所有人唱歌且所有人跳舞意义相同人唱歌且所有人跳舞意义相同.故有故有: x( A（x）B(x ) )x A（x）x B(x ) x (A（x）B(x ) ) x A（x）x B(x )133校园课件(5) 量词与命题联结词之间的一些蕴涵式量词与命题联结词之间的一些蕴涵式 设设 A(x ):x 聪明聪明; B(x ) : x努力努力; 个体

87、域个体域 为为:学生学生. x A（x）x B(x ) x (A（x）x B(x ) x ( A（x）B(x ) ) x A（x）x B（x） 类似有类似有: x (A（x） B(x ) x A（x）x B(x ) x (A（x） B(x )x A（x）x B(x )134校园课件(6) 多个量词的使用多个量词的使用例如例如 设设A( x,y ): x和和 y同姓同姓 个体域个体域x是甲村的人是甲村的人, y是乙村的人是乙村的人. x y A（x,y）y x A( x,y ) x y A（x,y）y x A( x,y ) x y A（x,y）y x A( x,y ) 错错135校园课件 x y

88、 A（x,y）y x A( x,y ) y x A（x,y）x y A( x,y ) y x A（x,y）x y A( x,y ) x y A（x,y）y x A( x,y ) x y A（x,y）y x A( x,y ) y x A（x,y）x y A( x,y )136校园课件2-6 前束范式前束范式前束范式前束范式: 量词均在全式的开头量词均在全式的开头,它的作用域延伸到它的作用域延伸到整个公式末尾。整个公式末尾。前束范式前束范式 的形式：的形式：Q1x1Q2x2Qkxk B其中其中Qi (1ik)为量词为量词 或或， xi (1ik)为客体变元，为客体变元， B为不包含为不包含 量词量

89、词 的谓词公式。的谓词公式。 137校园课件例 x y （F（x,y）G G（x,y），）， F（x,y），）， x y Z( F（x,y,z） G（x,y）是）是 而而x F（x）xG（x,y），）， x （F（x）x G（y）不是。）不是。138校园课件例例1 求求x P（x） xQ（x）的前束范式。）的前束范式。解：原式解：原式 x P（x） xQ（x） x P（x） xQ（x） x（ P（x） Q（x）139校园课件例例2 求求x y( z( P (x,z）P( y,z ) uQ(x,y,u)的前束范式。的前束范式。解解: 原式原式 x y( z( P (x,z) P( y,z ) u

90、Q(x,y,u) x y(z(P (x,z）P( y,z ) uQ(x,y,u) x yz u (P (x,z）P( y,z ) Q(x,y,u) x P（x）x P（x）140校园课件例3 求求 x P（x） xQ（x）的前束范式）的前束范式.解解: 原式原式 x P（x） xQ（x） x P（x） y yQ（y） x (P（x） yQ（y）) x y (P（x） Q（y）)141校园课件 2-7 谓词演算的推理理论谓词演算的推理理论 在谓词推理上消去和添加量词在谓词推理上消去和添加量词 的规则的规则:(1)全称量词消去规则全称量词消去规则(简称简称US规则规则) x P（x）P(c )P(

91、c ) 其中其中c为个体域为个体域 中任意客体中任意客体.(2)全称量词引入规则全称量词引入规则(简称简称UG规则规则) P（y）x P（x） 其中其中y为客体域中的任意客体为客体域中的任意客体.142校园课件(3)存在量词消去规则存在量词消去规则(简称简称ES规则规则) x P（x）P(c ) 其中其中c为个体域为个体域 中的某个客体中的某个客体.(4)存在量词引入规则存在量词引入规则(简称简称EG规则规则) P（ c ） x P（x） 其中其中c 为客体域中的某个客体为客体域中的某个客体.143校园课件例例1 证明苏格拉底三段论证明苏格拉底三段论证明证明 设设 s:苏格拉底苏格拉底; H(

92、x):x是人是人; M(x):x是要死的是要死的.则则 x( H(x)M(x) ) H(s) M(s) (1) x( H(x)M(x) ) P (2) H(s)M(s) US(1) (3) H(s) P (4) M(s) T(2),(3) I144校园课件例例2 证明证明 x( F(x)G(x) H(x), x(F(x) R(x) x(F(x) R(x) G(x)证明证明(1) x(F(x) R(x) P (2) F(c) R(c) ES(1) (3) x( F(x)G(x) H(x) P (4) F(c)G(c) H(c) US(1) (5) F(c ) T(2) I (6) G(c ) H

93、(c ) T(4),(5) I (7) R(c ) T(2) I (8) G(c ) T(6) I (9) F(c) R(c) G(c) T(5),(7),(8) I (10) x(F(x) R(x) G(x)145校园课件例例3 证明证明 x( P(x) Q(x) x P(x) xQ(x) 证明证明 (1) ( xP(x) xQ(x) ) P (2) xP(x) xQ(x) T(1)E (3) xP(x) T(2) I (4) xP(x) T(3)E (5) xQ(x) T(2)I (6) xQ(x) T(5)E (7) P(c ) ES(4) (8) Q(c ) US(6) (9) P(c

94、 ) Q(c ) T(7),(8)I (10) (P(c ) Q(c ) ) T(9)E (11) x( P(x) Q(x) P (12) P(c) Q(c) US(11) (13) (P(c ) Q(c ) ) (P(c) Q(c) ) T(10),(12) I 矛盾矛盾146校园课件第三章第三章 集合与关系集合与关系31 集合的概念和表示法集合的概念和表示法1.集合的概念集合的概念集合集合：是具有某种特定性质的对象汇集成的一个整体。：是具有某种特定性质的对象汇集成的一个整体。通常用大写字母表示集合的名称。通常用大写字母表示集合的名称。元素元素：集合中的每一个对象都称为该集合的元素。用小：集

95、合中的每一个对象都称为该集合的元素。用小写字母表示。写字母表示。若元素若元素a属于集合属于集合A，记作，记作a A,亦称亦称A包含包含a，或，或a是是A的的元素。元素。若元素若元素a不属于集合不属于集合A，记作，记作a A,亦称亦称A不包含不包含a，或，或a不是不是A的元素。的元素。147校园课件集合集合 有限集合有限集合 无限集合无限集合集合的表示方法有两种：集合的表示方法有两种：一种是列举法。一种是列举法。例：例：Aa,b.c.d. 一种是用谓词概括该集合中元素的属性一种是用谓词概括该集合中元素的属性.集合集合 B=x| P(x )表示表示B由使由使P(x )为真的全体为真的全体x组成组成

96、.例例B=x| x Z 3 x6 则则B=4,5,6.148校园课件例例:A=a,b,c,d,d其中其中a A, b,c A, d A,d A, b A, d A在集合中在集合中,元素之间是彼此不同的元素之间是彼此不同的,并且没有次序关系并且没有次序关系.例如例如,3,4,5和和5,3,4、5,3,4,4是同一集合是同一集合.149校园课件2.集合之间的关系集合之间的关系子集合子集合: 设设A、B为集合，若为集合，若A的每一个元素都是的每一个元素都是B的元的元素，由称素，由称A为为B的子集，或的子集，或A被被B包含，或包含，或B包含包含A。记。记作作A B，或，或B A。A Bx（x Ax B

97、）例如，例如，A=0,1,2,B=0,1,C=1,2 则有则有B A, C A,但但B C, C B由定义可得由定义可得: 对任何集合对任何集合S, 都有都有S S.150校园课件集合相等集合相等: 设设A、B为集合为集合,如果有完全相同的元素，如果有完全相同的元素，则称这两个集合相等。记作则称这两个集合相等。记作A=B；否则否则A和和B不相等，则记为不相等，则记为 AB。例例 3,4,5=5,3,4， 1，2，31，2，3151校园课件真子集真子集：设：设A、B为集合，如果若为集合，如果若B A且且BA，则称，则称B为为A 的真子集，记作的真子集，记作B A。如果。如果B不是不是A的真子集，

98、的真子集，则记为则记为 B A。例例 0，1是是 0，1，2 的真子集，的真子集，但但1，3 和和0，1，2都不是都不是0，1，2的真子集。的真子集。152校园课件定理定理13.1设设A、B、C为任意集合，下列结论成立。为任意集合，下列结论成立。（1）A A（2）若）若A B且且B A，则，则AB。（3）若）若A B，B C，则，则A C。153校园课件空集空集：不含任何元素的集合叫空集，记作：不含任何元素的集合叫空集，记作。=x|P(x)P(x). 其中其中P(x)为任意的谓词。为任意的谓词。 例例A x| x Rx2+10 A154校园课件定理定理31.2对于任意一个集合对于任意一个集合A

99、， A。证明：假设证明：假设 A是假，则至少有一个元素是假，则至少有一个元素x，使，使x 且且x A，因为空集，因为空集不包含任何元素，所以这是不可不包含任何元素，所以这是不可能的。能的。155校园课件全集全集：在一定范围内，如果所有的集合均为某一集：在一定范围内，如果所有的集合均为某一集合的子集，则称该集合为合的子集，则称该集合为全集全集。记作。记作E。 例在研究整数时，把全体整数看作全集。在研究例在研究整数时，把全体整数看作全集。在研究平面解析几何时，把全体坐标看作全集。平面解析几何时，把全体坐标看作全集。156校园课件幂集幂集：设：设A为集合，把为集合，把A的全部子集构成的集合叫做的全部

100、子集构成的集合叫做A的的幂集幂集。记作。记作P（A）.例：例：Aa,b,cP(A)= ,a,b,c,a,b,a,c,b,c,a,b,c 定理定理31.3 如果有限集合如果有限集合A有有n个元素，则其幂集个元素，则其幂集P(A)有有2n个元素。个元素。157校园课件32 集合的运算集合的运算集合的交集合的交: 设设A、B为集合，由集合为集合，由集合A和集合和集合B的所有共的所有共同元素组成的集合，称为同元素组成的集合，称为A和和B的交集。记作的交集。记作AB。 ABx|（x A）（x B）例例 A0，2，4，6，8，10，12， B1，2，3，4，5，6 AB2，4，6 例例 设设A是所有矩形的

101、集合，是所有矩形的集合，B是所有菱形的集合，则是所有菱形的集合，则AB是所有正方形的集合。是所有正方形的集合。158校园课件例例 设设A B，求证，求证AC BC证明：若证明：若x A则则x B， 对任一对任一x AC，则，则x A 且且x C， 即即x B且且x C，故，故x BC 因此因此AC BC159校园课件交运算的性质：交运算的性质：1）AA=A2）A=3）AE=A4）AB= BA5）(AB)C= A(BC) n个集合的交记为个集合的交记为：Ai= A1A2A n 160校园课件(2) 集合的并集合的并: 设设A 、B为集合，所有属于为集合，所有属于A或属于或属于B的元素组成的集合，

102、称为的元素组成的集合，称为A和和B的并集。记作的并集。记作A B。A Bx|（x A）（x B）例例: A1，2，3,4，B2，4，5A B1,2，3,4，5 161校园课件并运算的性质：并运算的性质：1) A AA2）A EE3）A A4）A BB A5） (A B) C A (B C) 162校园课件例例2 设设A B，C D，同，则，同，则A C B D。证明：对任意证明：对任意x A C，则有，则有x A或或x C。 若若x A，由，由A B，则，则x B，故，故x B D； 若若x C，由，由C D，则，则x D，故，故x B D。 因此因此A C B Dn个集合的并记为个集合的并记

103、为Ai= A1 A2 A n 163校园课件定理定理3-2.1 设设A、B、C为三个集合，则下列分配律为三个集合，则下列分配律成立。成立。1）A(B C)=(AB) (AC)2）A (BC)=(A B) (A C)164校园课件定理定理32.2 设设A、B为集合，则下列关系式成立。为集合，则下列关系式成立。1）A （AB）A2）A（A B）A证明证明 1) A （AB）=(AE) (AB) =A(E B)=A2) A（A B）(A A) (A B) =A (AB)=A165校园课件定理定理3-2.3 A B, 当且仅当当且仅当 A B=B或或AB=A证明证明 若若A B,对任意对任意x A 必

104、有必有x B,对任意对任意x A B,则则x A或或x B,即即x B,所以所以A B B.又又B A B,故故A B=B.反之反之,若若A B=B,因为因为A A B,故故A B.同理可证同理可证A B, 当且仅当当且仅当 AB=A166校园课件(3) 集合的相对补集（差）集合的相对补集（差）: 设设A 、B为集合，所有属为集合，所有属于于A而不属于而不属于B的元素组成的集合，称为的元素组成的集合，称为A和和B的差的差集。记作集。记作AB。ABx|（x A）（x B）例例3: A1，2，3,4，B2，4，5解解 AB1,3 例例4 设设A是素数集合，是素数集合，B是奇数集合，求是奇数集合，求

105、AB。解解 AB2167校园课件(4)补集补集：设：设E为全集，对任一集合为全集，对任一集合A关于关于E的补的补EA，称为集合，称为集合A的绝对补，记作的绝对补，记作 A。 AEAx|x E x A168校园课件补运算的性质：补运算的性质：a) （ A）=Ab) E=c) =Ed) AA=Ee) A A= 169校园课件定理定理32.4 设设A、B为集合，则下列关系式成立。为集合，则下列关系式成立。a) （A B）= A Bb) （AB）= AB证明证明 a） （A B） x| x（A B） x| x （A B） x| （x A） （ x B） A Bb.）其证明方法与）其证明方法与a）类似。

106、）类似。170校园课件定理定理32.5设设A、B为集合，则下列关系式成立。为集合，则下列关系式成立。a) ABA Bb)ABA（AB）证明证明 b）设）设x （AB），即），即x A且且x B。 因因 x B，必有，必有x （AB），故），故x A（AB），即即 AB A（AB）又设又设x A（AB），则，则x A且且x （AB），），即即x A且且x （AB）x A 且且xA或或xB ， （ （AB）= AB）但但x A且且xA是不可能的，故是不可能的，故x A且且xB，即，即x AB，得到得到A（AB） AB因此因此ABA（AB）171校园课件定理定理32.6 设设A、B、C为集合，为集合

107、， 则则 A（BC）（）（AB）（）（AC）证明证明 A（BC）A（B C） AB C又（又（AB）（）（AC） （AB） （AC） （AB）（ AC） （AB A）（AB C） （AB C）AB C 因此因此A（BC）（）（AB）（）（AC）172校园课件定理定理32.7设设A、B为集合，若为集合，若A B，则，则a） B Ab） （BA）AB证明证明 a）若）若x A，则，则x B， 因此若因此若x B，则，则x A， 故故xB 必有必有xA， 即即 B A173校园课件集合的对称差：集合的对称差：设设A、B为集合，所有属于为集合，所有属于A或属或属于于B，但不能既属于，但不能既属于A又属

108、于又属于B的元素组成的集的元素组成的集合，称为合，称为A和和B的对称差。记作的对称差。记作AB。AB（AB）（BA）x|x A x B174校园课件对称差的性质：对称差的性质：a) ABBA b）AA c) AAd) AB=(A B) ( AB) e) (AB) C=A(BC)175校园课件 34 序偶与笛卡尔积序偶与笛卡尔积1、序偶、序偶序偶序偶：由两个元素：由两个元素x和和y（允许（允许xy）按一定顺序排）按一定顺序排列成的二元组叫做一个有序对（也称序偶），记作列成的二元组叫做一个有序对（也称序偶），记作x，y.其中其中x是它的第一个元素，是它的第一个元素，y是它的第二个元素。序偶是它的第

109、二个元素。序偶中的两个元素不一定来自同一集合中的两个元素不一定来自同一集合.例例 平面直角坐标系中点的坐标就是有序对，平面直角坐标系中点的坐标就是有序对，1，1、2，0复数复数 3+6i 可表示成序偶可表示成序偶 176校园课件序偶的特点：序偶的特点：（1）当）当xy时，时，（2）两个有序对相等）两个有序对相等,即即 的充分必的充分必要条件是要条件是xu,yv177校园课件n元组元组:一个有序一个有序n元组是一个有序对元组是一个有序对,其中第一个元素其中第一个元素是一个有序是一个有序n-1元组元组,记为记为 ，xn178校园课件笛卡尔积：笛卡尔积：设设A、B为集合，用为集合，用A中元素为第一元

110、素，中元素为第一元素，B中元素为第二元素，构成有序对，所有这样的有序对组中元素为第二元素，构成有序对，所有这样的有序对组成的集合叫做成的集合叫做A和和B的的笛卡尔积笛卡尔积，记作，记作 AB。ABx，y|x A y B例例 A a,b，B0，1，2，则，则 ABa,0，a,1，a,2， b，0， b，1， b，2BA0，a，0，b，1，a， 1，b，2，a, AA=, , 179校园课件笛卡尔积运算的性质：笛卡尔积运算的性质：(1)若若A、B中有一个空集，则中有一个空集，则AA(2)当当AB且且A、B都不是空集时，有都不是空集时，有ABBA (3)当当A、B、C都不是空集时，有都不是空集时，有

111、 （AB）CA（BC）(4) A（B C）（）（AB）（AC） A（BC）（）（AB）（AC） （A B）C（A C）（B C） （A B）C（A C）（B C）180校园课件证明证明 A（B C）=（AB）（AC） 对于任意的对于任意的 ，若若 A（B C） x A y （B C） x A (y B y C)(x A y B) (x A y C) AB AC （AB）（AC）所以所以A（B C）（AB）（AC）181校园课件证明证明 （A B）C（A C）（B C）对于任意的对于任意的 ，若若 x，y (A B)Cx A B y C (x A x B) y C(x A y C ) (x B

112、y C ) AC BC (AC) (BC )所以（所以（A B）C（A C）（B C）182校园课件定理定理 3-4.2 若若C 则则A B AC BC CA CB证明证明 假定假定 A B 有有 AC (x A y C) (x B y C) BC所以所以 AC BC反之反之,若若C,AC BC,取取y C ,则有则有x A(x A) (y C) AC BC(x B) (y C)x B因此因此 A B同样同样A B CA CB183校园课件定理定理3-4.3 设设A、B、C、D 为四个非空集合，则为四个非空集合，则 AB CD 的充分必要条件为的充分必要条件为A C，B D。证明证明 若若AB

113、 CD，则对任意的，则对任意的x A和和y B，有，有 （x A）（y B） AB CD(x C) (y D)即即A C，B D反之反之,若若A C，B D,设任意设任意x A和和y B,有有 AB (x A y B) (x C y D) CD因此因此AB CD184校园课件n阶笛卡尔积阶笛卡尔积: A1A2An=| (x1 A1) (x2 A2) (xn An)n阶笛卡尔积阶笛卡尔积: A1A2An是是n元组构成的集合元组构成的集合.AA=A2 , AA A=A3, AAA=A n 185校园课件3-5 关系及其表示关系及其表示定义定义3-5.1 有序对的集合构成了一个二元关系。有序对的集合

114、构成了一个二元关系。一般记作一般记作R，如果，如果 R，则记作，则记作x R y； 如果如果 R ,则记作则记作 xR y。例例 R , 186校园课件定义定义 3-5.2 关系关系R的定义域的定义域domR, 值域值域(前域前域)ranR和和域域fldR 分别是分别是:domR=x| y ( R)ranR=y| x ( R)fldR=dom RranR例例 1 设设A=1,2,3,5,B=1,2,4,H=,求求domR,ranR和和fldR.解解domR=1,2,3,ranR=2,4,fldR=1,2,3,4187校园课件定义定义3-5.3 设设A、B为集合，笛卡尔积为集合，笛卡尔积AB的子

115、集称作的子集称作X到到Y的关系。的关系。因此因此domR A, ranR B ，R AB。对于对于X到到Y的关系可以用图表示的关系可以用图表示.如例如例1188校园课件全域关系全域关系：AB 。空关系空关系：。恒等关系恒等关系:对任何集合对任何集合A, A上的恒等关系上的恒等关系 IA=| x A 例例 设设A=1,2,3,则则 IA=,当当AB时，时，AB上的关系上的关系R称为称为A上的关系。上的关系。189校园课件例例 设设A为实数集为实数集R上的某个子集，则上的某个子集，则A上的小于等于关上的小于等于关系定义为系定义为L | x，y A xy 若若A4，0.5,-1,则则L=, ,.19

116、0校园课件例例 A=a,b,R是是P(A)上的包含关系上的包含关系,R= | x，y P(A) x y则有则有 P(A)= , a,b, a,bR=, , , 因为关系是序偶的集合因为关系是序偶的集合,所以同一域上的关系所以同一域上的关系,可以进行可以进行集合的所有运算集合的所有运算.191校园课件例例5 设设X=1,2,3,4,若若H=| x-y/2是整数是整数, S=| x-y/3是正整数是正整数,求求H S, HS, H, S-H.解解 H=, S= H S=,HS= H=,. S-H=.192校园课件定理定理3-5.1 若若Z和和S是从集合是从集合X到到Y的两个关系的两个关系,则则Z、

117、S的并、交、补、差仍是的并、交、补、差仍是X到到Y的关系。的关系。193校园课件关系矩阵：关系矩阵：设给定两个有限集合设给定两个有限集合X x1，x2，,xnm，Y y 1，y2，, y n，R为从为从X到到Y的一个二元关系，令的一个二元关系，令rij= 1 当当 R 0 当当 R（i=1,2,m, j=1,2,n）R的关系矩阵为的关系矩阵为: r11 r12 r1nMR= r21 r22 r2n rm1 rm2 rmn194校园课件例例5设设X= x1，x2，x3，x4,Y= y 1，y2, y 3 R=,写出关系写出关系矩阵矩阵MR 1 0 1 0 1 1解解MR= 1 0 0 1 1 0

118、195校园课件例例6设设A1，2，3，4，写出集合，写出集合A上大于关系上大于关系 的的关系矩阵关系矩阵.解解 =, 0 0 0 0MR= 1 0 0 0 1 1 0 0 1 1 1 0196校园课件关系图关系图: 设给定两个有限集合设给定两个有限集合X x1，x2，,xm，Y y 1，y2，, y n，R为从为从X到到Y的一个二元关系，的一个二元关系，首先在平面上画出结点首先在平面上画出结点 x1，x2，,xm , y 1，y2，, y n, 然后如果然后如果xi R yj,则在结点则在结点xi，yj之间之间作一有向弧作一有向弧.197校园课件例例7画出例画出例5的关系图的关系图.198校园

119、课件例例8 设设A=1,2,3,4,5, 在在A上的二元关系上的二元关系R给定为给定为:R=,画出画出R的的关系图关系图.199校园课件3-6 关系的性质关系的性质 设设R是集合是集合X上的二元关系上的二元关系,R的性质有以下的性质有以下5种种: 自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性。传递性。自反性自反性：对于每个：对于每个x X，有，有 R. 关系矩阵主对关系矩阵主对角线上全为角线上全为1. 关系图中每个顶点都有环关系图中每个顶点都有环.例如在实数集合上例如在实数集合上” ”关系是自反的关系是自反的.集合之间的集合之间的” ”关系也是自反的关系也是自反的.2

120、00校园课件反自反性反自反性：对于每个：对于每个x X，有，有 R . 关系矩阵关系矩阵主对角线上全为主对角线上全为0. 关系图中每个顶点都没有环关系图中每个顶点都没有环.例如在实数集合上例如在实数集合上” ”关系是反自反的关系是反自反的.集合之间的集合之间的 ” ”关系也是反自反的关系也是反自反的. 201校园课件对称性对称性: 若若 R,有有 R . 关系矩阵为对关系矩阵为对称矩阵称矩阵. 在关系图中在关系图中,如果两个顶点之间有边如果两个顶点之间有边,一定是一一定是一对方向相反的边对方向相反的边.例如同学关系例如同学关系,兄弟关系兄弟关系.反对称性反对称性: 若若 R,且且x y, 有有

121、 R . 如如果果ri j =1,且且i j, 则则rj i =0. 关系图中关系图中,如果两个顶点之间如果两个顶点之间有边有边,一定是一条有向边一定是一条有向边.例如父子关系例如父子关系,上下级关系上下级关系, 实实数集合上数集合上” ”关系和集合之间的关系和集合之间的” ”关系关系.202校园课件传递性传递性: 若若 R且且 R, 则有则有 R. 关系图中关系图中,如果顶点如果顶点xi 到到xj有边有边,xj到到 xk有边有边,则从则从xi到到 xk有边有边. 例上下级关系例上下级关系.祖先关系祖先关系, 实数集合上实数集合上” ”关系关系.集合集合之间的之间的” ”关系关系203校园课件

122、例例1 设设A= 1,2,3 R1=, 是自反的是自反的 R2=, 是反自反的是反自反的 R3=, 既不是自反的也不是反自既不是自反的也不是反自反的反的 R4=, 对称的对称的 R5=, 反对称的反对称的 R6=对称的对称的,反对称的反对称的 R7=, 既不对称又不反对称既不对称又不反对称 R8=, 传递的传递的 R9= 传递的传递的 R10=, 不是传递的不是传递的204校园课件例判断下图中各关系的性质.解 自反的 反自反的 对称的 反对称的 传递的 (1) 否 否 是 否 否(2) 否 是 否 是 是(3) 是 否 否 是 否205校园课件3-7 复合关系和逆关系复合关系和逆关系1.复合关

123、系复合关系关系的复合关系的复合:设设R为为X到到Y 上的关系上的关系,S为为Y到到Z上的关上的关系系,则则RS 称为称为R和和S的复合关系的复合关系,表示为表示为:RS=| y( R S)例若例若x是是y的母亲的母亲, y是是z的妻子的妻子,则则x是是z的岳母的岳母.例例1令令R=,和和S= ,试求试求RS, SR, R (S R),( RS) R, R R.解解RS= ,206校园课件例例1令令R=, 和和S= ,试求试求RS, SR, R (S R), ( RS) R, R R.解解RS= ,S R =,RS R (S R) =(R S) R =R R=,207校园课件关系的复合运算不满足

124、交换律关系的复合运算不满足交换律,但满足结合律但满足结合律.即即:S R RS(R S) P =R (S P) 208校园课件例例2 设设R1和和R2是集合是集合X=0,1,2,3上的关系上的关系,R1=| j= i+1 或或j=(1/2) i ,R2=| j=i- 2,求求R1R2, R2R1 , R1R2R1 , R1R1, R1R1R1 解解R1=, R2=, R1R2=, R2R1 =, R1R2R1 =, R1R1=, R1R1R1=, 209校园课件RR可记为可记为R(2) , RRR 可记为可记为 R(3) m-1 个个R RRR R=R(m-1) R=R(m)210校园课件用关

125、系矩阵表示复合关系用关系矩阵表示复合关系已知从集合已知从集合X= x1，x2，,xm 到集合到集合Y y 1，y2，, y n有关系有关系R,从集合从集合Y y 1，y2，, y n 到集合到集合Z= z1，z2，,zp有关系有关系S,表示复合关系的矩阵表示复合关系的矩阵M RS可构造如下：可构造如下： 如果如果Y至少有一个元素至少有一个元素yj, 使得使得 R 且且 S, 则则 R S .即即MRS=MRMS=wik其中其中其中其中 0 0=0, 0 1=0, 1 0=0, 1 1=1 0 0=0, 0 1=1, 1 0=1, 1 1=1211校园课件A=1,2,3,4,5,集合集合A上的关

126、系上的关系R=, S=,求求RS和和S R 的关系矩阵的关系矩阵. 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1MRS = 0 0 0 1 0 1 0 0 0 0 = 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0MSR = 1 0 0 0 0 0 0 0 1 0 = 0 1 0 0 0 0 1 0 0 0 0

127、0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 212校园课件2.关系的逆关系关系的逆关系逆关系逆关系: 设设R为为X到到Y的二元关系的二元关系,R的逆关系记为的逆关系记为RC(或或R-1), 即即:RC=| R 显然显然,若若R AB,则则RC BA.例例 大于关系大于关系”的逆关系为小于的逆关系为小于”2,则则23,集合的包含关系集合的包含关系” ”的逆关系为的逆关系为”关关系系,如如A B ,则则B A.关系关系” x 是是y的老师的老师”的逆关的逆关系为系为” y是是x的学生的学生”.213校园课件例例1 设设A=a,b,c,d,B=1,

128、2,3,若若R=,求求RC .解解RC =, . 由逆的定义可知由逆的定义可知, (RC )C =R.214校园课件定理定理3-7.1 设设R,R1和和R2都是从都是从A到到B的二元关系的二元关系,则下则下列各式成立列各式成立.(1) (R1 R2 ) C = R1C R2C (2) (R1R2 ) C = R1CR2C (3) (AB) C=BA(4)(5) (R1-R2 ) C = R1C - R2C 215校园课件证明证明(1) (R1 R2 ) C R1 R2 R1 R2 R1C R2C R1C R2C 证明证明(4) (R)C R R R C R C216校园课件定理定理 3-7.2

129、 设设T为为X到到Y的关系的关系, S为为Y到到Z的关系的关系,则则(TS)C=SCT C证明证明 (TS) C TS ( y)(y Y T S)( y)(y Y TC SC ) SC TC217校园课件定理定理 3-7.3 设设R为为X上的二元关系上的二元关系,则则(1) R 是对称的是对称的,当且仅当当且仅当R= R C(2) R 是反对称的是反对称的,当且仅当当且仅当RR C IA证明证明 (1) 因为因为R是对称的是对称的, 所以所以 R R RC 所以所以R=RC反之反之,若若RC =R, 因为因为 R RC R ,所以所以 R是对称的是对称的.218校园课件 关系关系RC的关系图的

130、关系图,是将关系是将关系R的关系图中的箭头方的关系图中的箭头方向反向即可向反向即可. 关系关系RC的关系矩阵的关系矩阵MRC是是R的关系矩阵的关系矩阵MR的转置的转置矩阵矩阵.219校园课件例例4 设设X= a,b,c,R是是X上的二元关系上的二元关系,R的关系矩阵的关系矩阵 1 0 1MR= 1 1 0 ,求求RC和和RRC的关系矩阵的关系矩阵. 1 1 1 解解 1 1 1MRC= 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1MRRC= 1 1 0 0 1 1 = 1 1 1 1 1 1 1 0 1 1 1 1220校园课件3-8 关系的闭包运算关系的闭包运算定义定义 3-8

131、.1 设设R是是X上的二元关系上的二元关系,如果有另一个关系如果有另一个关系R 满足满足:(1) R 是自反的是自反的(对称的对称的,传递的传递的);(2) R R;(3)对于任何自反对于任何自反(对称对称,传递传递)的关系的关系R, 如果有如果有R R,就有就有R R .则称关系则称关系R 为为R的自反的的自反的(对称的对称的,传递的传递的)闭包闭包. 记作记作 r(R),(s(R), t(R) ) 须要注意的是须要注意的是, 自反自反(对称对称,传递传递)闭包是包含闭包是包含R的最的最小自反小自反(对称对称,传递传递)关系关系.221校园课件定理定理3-8.1设设R是是X上的二元关系上的二

132、元关系,那么那么(1) R 是自反的是自反的,当且仅当当且仅当r(R)=R(2) R 是对称的是对称的,当且仅当当且仅当,s(R)=R(3) R 是传递的是传递的,当且仅当当且仅当, t(R)=R.证明证明 (1) 如果如果R是自反的是自反的,因为因为R R,且任何包含且任何包含R的自的自反关系反关系R ,有有R R,故故r(R)=R反之反之,如果如果r(R)=R, 根据自反闭包的定义根据自反闭包的定义(1) ,R必是自必是自反的反的.222校园课件定理定理3-8.2设设R是是X上的二元关系上的二元关系, 则则r(R)=R IX,定理定理 3-8.3设设R是是X上的二元关系上的二元关系, 则则

133、s (R)=R R C 定理定理3-8.4设设R是是X上的二元关系上的二元关系, 则则t (R)=R R2 R3 223校园课件例例1 设设A=a,b,c,d,R=, 求求r(R),s(R), t(R).用关系图求解用关系图求解224校园课件直接求解直接求解:r(R)=R IX= , , = , , s(R)=R RC= , , ,= , , 225校园课件对于有限集来说对于有限集来说,R的不同的幂只有有限种的不同的幂只有有限种,所以所以R R2 R3 只有有限项只有有限项,但对于无限集来说就不一但对于无限集来说就不一定是有限项了定是有限项了.R2= , R3= , R4= , =R2因为因为

134、R2=R4,所以所以R3=R5所以所以R2=R4=R6,R3=R5= R7 t (R)=R R2 R3= , , , = , ，, , , , 226校园课件用关系矩阵求解用关系矩阵求解 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0Mr= 0 0 0 1 + 0 0 1 0 = 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0Ms= 0 0 0 1 + 0 1 0 0 = 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0

135、0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1MR2= 0 0 0 1 0 0 0 1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 227校园课件 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0MR3= 0 0 0 0 0 0 0 1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1MR4= 0 0 0 0 + 0 0 0 1 = 0 0 0 0 =MR2 0 0

136、 0 0 0 0 0 0 0 0 0 0Mt= MR+ MR2+ MR3 0 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1Mt= 0 0 0 1 + 0 0 0 0 + 0 0 0 0 = 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 228校园课件定理定理 3-8.5 设设X是含有是含有n个元素的集合个元素的集合,R是是X上的二元上的二元关系关系,则存在一个整数则存在一个整数kn,使得使得t(R)=R R2 R3 Rk从本定理可知从本定理可知:t(R)=R R2 R3 Rn229校

137、园课件当有限集的元素较多时当有限集的元素较多时,进行矩阵运算比较麻烦进行矩阵运算比较麻烦, 一个一个有效算法如下有效算法如下:(1) 置新矩阵置新矩阵A:=M;(2) 置置i=1;(3) 对所有对所有j如果如果Aj ,i=1,则对则对k=1,2,n Aj, k=Aj, k+Ai, k; (即将第即将第i行加到第行加到第j行上去行上去) (4) i加加1;(5) 如果如果in,则转到步骤则转到步骤(3),否则停止否则停止.230校园课件例例 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0已知已知 M= 0 1 0 0 0 0 0 求求t(R). 0 0 0 0

138、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 解解 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0A:= M= 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 231校园课件 i=1时时,A1,1=1 ,将第将第1行逻辑加到第行逻辑加到第1行上去行上去, 得得: 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0A:= 0 1 0 0 0 0 0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 i=2

139、时时,A1,2=1 ,A4,2=1,分别将第分别将第2行逻辑加到第行逻辑加到第1行和第行和第4行行 上去上去, 得得: 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0A:= 0 1 0 1 0 0 0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 232校园课件i=3时时,第三列全为第三列全为0. i=4时时A1,4=1 ,A2,4=1,A4, 4=1分别将第分别将第4行逻辑行逻辑加到第加到第1行行,第第2行和第四行上去行和第四行上去, 得得: 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0

140、1 0 0A:= 0 1 0 1 0 0 0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 233校园课件i=5时时,A3,5=1 ,将第将第5行逻辑加到第行逻辑加到第3行上去行上去, 第五第五得全得全0,第三行不变第三行不变. 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0A:(R+)= 0 1 0 1 0 0 0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 i=6,7时时,第第6列第列第7列全列全0 ,所以矩阵不变所以矩阵不变.234校园课件定理定理3-8.6 设设X是

141、集合是集合,R是是X上的二元关系上的二元关系,则则(1) rs(R)=sr(R)(2) rt(R)=tr(R)(3) ts(R) st(R)证明证明(1) sr(R)= s( IX R)= ( IX R) ( IX R)C = ( IX R) ( IXC RC) (定理定理3-7.1) = IX R RC = IX s(R)=rs(R)235校园课件3-9 集合的划分和覆盖集合的划分和覆盖定义定义 3-9.1 设设A为给定的非空集合为给定的非空集合,S=S1,S2,Sm,其中其中Si A, Si (i=,1,2, m),且且S1 S2 Sm=A,集合集合S称作集合称作集合A的的覆盖覆盖. 如果

142、除此条件外如果除此条件外,另有另有SiS j =(ij),则称则称S是是A的的划划分分(或分划或分划).236校园课件例如例如,A=a,b,c, S=a,b,b,c (覆盖覆盖), Q=a,a,b,a,c (覆盖覆盖) D=a,b,c, (覆盖，划分覆盖，划分) G=a,b,c (覆盖、最小划分覆盖、最小划分) E=a,b,c, （覆盖、最大划分）（覆盖、最大划分） F=a,a,c （都不是）（都不是）最小划分：由这个集合的全部元素组成的一个分块最小划分：由这个集合的全部元素组成的一个分块的集合。的集合。最大划分：由每个元素构成一个单元素分块的集合。最大划分：由每个元素构成一个单元素分块的集合

143、。237校园课件定义定义 39.2 若若A1，A2，A r与与 B1，B2，Bs 是同一集合是同一集合A的两种划分，则其中所有的两种划分，则其中所有AiBj 组成组成的集合，称为是原来两种划分的的集合，称为是原来两种划分的交叉划分交叉划分。例如，所有生物的集合为例如，所有生物的集合为X，可分割为，可分割为P，A， 其中，其中，P表示所有植物的集合，表示所有植物的集合，A表示所有动物的表示所有动物的集合，集合， X又可分割为又可分割为E，F 其中其中 E表示史前生物的集合，表示史前生物的集合，F表示史后生物的集表示史后生物的集合。则交叉划分为合。则交叉划分为QPE，PF，AE，AF238校园课件

144、定理定理 39.1 设设A1，A2，A r与与 B1，B2，Bs是同一是同一集合集合X的两种划分，则其交叉划分亦是原集合的一种划分。的两种划分，则其交叉划分亦是原集合的一种划分。证明证明 因为交叉划分为因为交叉划分为 A1B 1，A1B 2，A1Bs， A2B 1，A2B2，A2B s， ArB 1，ArB 2，ArB s 在交叉划分中，任取两元素，在交叉划分中，任取两元素， (AiBh )(AjB k)= AiBh AjB k =(AiA j )(BhB k )= 又因为又因为(A1B 1) (A1B 2) ,， (A1Bs) (A2B 1) (A2B2) ,，(A2B s) (ArB 1)

145、 (ArB2) ,，(ArB s)=( A1( B1 B2 B s) (A2( B1 B2 B s) (A r( B1 B2 Bs)=(A1 A2 A r) ( B1 B2 B s)=XX=X所以所以X的交叉划分也是的交叉划分也是X的一种划分的一种划分.239校园课件定理定理 3-9.3 给定给定X的任意两个划分的任意两个划分A1，A2，A r与与 B1，B2，B s,若对于每一个若对于每一个Aj 均有均有Bk 使使Aj Bk ,则则A1，A2，A r称为称为 B1，B2，,B s的加细的加细.定理定理 3-9.4 任何两种划分的交叉划分任何两种划分的交叉划分,都是原来各划分都是原来各划分一种

146、加细一种加细.240校园课件3-10 等价关系与等价类等价关系与等价类等价关系等价关系: 设设R为为A上的关系，若上的关系，若R 具有自反性、对称具有自反性、对称性和传递性，则称性和传递性，则称R为等价关系。为等价关系。例如平面上三角形集合中，三角形的相似关系例如平面上三角形集合中，三角形的相似关系为等价关系。朋友关系不是等价关系。为等价关系。朋友关系不是等价关系。241校园课件例例1 设集合设集合T1，2，3，4，R=, ，,.验证验证R是是T上的等价关系上的等价关系.解解 R的关系矩阵和关系图如下的关系矩阵和关系图如下: 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1242

147、校园课件例例2 设设I为整数集合，为整数集合，R= |x,y I xy(mod k),其中其中xy(mod k) : xy可以被可以被k 整除整除,证明证明 R是等价关系。是等价关系。 证明证明 设任意设任意 a,b,c,d I, : 因为因为aak0，所以，所以 R : 若若ab(mod k) , 则则abkt(t为整数为整数),则则b- a-kt(t为为整数整数), 所以所以ba(mod k) : ab(mod k) ,bc(mod k),则则 abkt,b-c=ks (t,s为整为整数数),则则c- aa-b+b-c=k(t +s), 所以所以ac(mod k)因此因此R是等价关系是等价

148、关系. 243校园课件等价类等价类: 设设R为集合为集合A上的等价关系上的等价关系,对任何对任何a A, 集合集合 aR= x | x A, aR x 称为元素称为元素a形成的形成的R等价类等价类.因为因为a a R, 因此任给集合因此任给集合A及其上的等价关系及其上的等价关系R,必可必可写出写出A上各个元素的等价类上各个元素的等价类. 例如例如 , T1，2，3，4，R=, ，,. T的各元素的各元素的等价类为的等价类为:1 R=4 R=1,42 R=3 R=2,3244校园课件例例3 设设I是整数集合是整数集合,R是同余模是同余模3的关系的关系,即即R= |x I,y I xy(mod 3

149、),确定由确定由I的元的元素所产生的等价类素所产生的等价类.解解 由例由例2 得知得知R为等价关系为等价关系, R的各元素的等价类为的各元素的等价类为:0 R=,-6,-3,0,3,6,1 R=,-5,-2,1,4,7,2 R=,-4,-1,2,5,8,由此可得由此可得:0 R=3 R=-3 R= 1 R=4 R=-2 R= 2 R=5 R=-1 R=245校园课件定理定理 3-10.1 设给定集合设给定集合A上的等价关系上的等价关系R,对于对于a, b A,有有aR b, 当且仅当当且仅当 a R= b R商集商集: 集合集合A上的等价关系上的等价关系R,其等价类集合其等价类集合 a R |

150、 a A称作称作A关于关于R的商集的商集,记作记作 A/R.246校园课件例如例例如例1中中,T/R= 1 R, 2 R例如例例如例3中中,I/R= 0 R, 1 R, 2 R在在I/R中中, 0 R 1 R 2 R=I,且任意两个等价类的交集且任意两个等价类的交集为为, 247校园课件定理定理3-10 2 集合集合A上的等价关系上的等价关系R, 决定了决定了A的一的一个划分个划分,该划分就是商集该划分就是商集A/R。 即商集中的每个等价类为划分中的一个块即商集中的每个等价类为划分中的一个块,所有所有的等价类构成了划分中的所有的块的等价类构成了划分中的所有的块.248校园课件例例 设设A=1,

151、2,3, 求出求出A上所有的等价关系上所有的等价关系.解解 先求出先求出A的各种划分的各种划分 1 2 3 4 5R5=,=IAR1=, IA=EAR2= , IAR3=, IAR4=, IA249校园课件定理定理3-10.3 集合集合A的一个划分确定的一个划分确定A的元素间的一个等的元素间的一个等价关系价关系.设集合设集合A有一个划分有一个划分S= S1，S2，S m,定定义关系义关系R, aRb当且仅当当且仅当a,b在同一块中。在同一块中。 可以证明可以证明R为等价关系为等价关系(即即R且有自反性、对称且有自反性、对称 性和传递性性和传递性)。 250校园课件设设Aa,b,c,d,e, 有

152、一个划分有一个划分S=a,b,c,d,e, 试试由划分由划分S确定确定A上的一个等价关系上的一个等价关系R.解解 R1= a,ba,b =,R2=c c= R3=d,ed,e= ,R=R1 R2 R3=, , , , , , , , 定理定理3-10.4 设设R和和R2为非空集合为非空集合A上的等价关系，则上的等价关系，则R1=R2当且仅当当且仅当 A/R1=A/R2。251校园课件定理定理3-10.4 设设R和和R2为非空集合为非空集合A上的等价关系，上的等价关系，则则R1=R2当且仅当当且仅当 A/R1=A/R2252校园课件 311 相容关系相容关系相容关系相容关系：给定集合：给定集合A

153、上的关系上的关系r, 若若r是自反的，对是自反的，对称的，则称称的，则称r是相容关系。是相容关系。253校园课件例如，例如，Acat, teacher, cold, desk, knife, by, r=|x,y A且且x和和y有相同的字母有相同的字母。显然。显然r是个相是个相容关系。令容关系。令x1cat ，x2teacher , x3cold， x4desk ，x5knife，x6by。r的关系图：的关系图： r的关系矩阵为：的关系矩阵为： 1 1 1 0 0 0 1 1 1 1 1 0 M r 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1

154、254校园课件关系矩阵简化为梯形如下：关系图可简化为：关系矩阵简化为梯形如下：关系图可简化为： x2 x3 x4 x5 x6255校园课件相容类相容类：设：设r是集合是集合A上的相容关系，若上的相容关系，若C A，如果，如果对于对于C上任意两个元素上任意两个元素a1 ，a 2有有a1 r a2 ，称，称C 是由是由相容关系相容关系r产生的相容类。产生的相容类。例如上例相容关系例如上例相容关系r右产生相容类右产生相容类 x1，x2 ，x1，x3， x2，x3，x6 ， x2 ，x4 ， x5等等。等等。若一个相容类，加入任一新元素，就不再组成相容若一个相容类，加入任一新元素，就不再组成相容类，称

155、为最大相容类。如类，称为最大相容类。如x6 ， x2 ，x4 ， x5，而，而 x1，x2 ，x1，x3， x2，x3就不是最大相容类。就不是最大相容类。256校园课件最大相容类：最大相容类：设设r是集合是集合A上的相容关系，不能包含在上的相容关系，不能包含在任何其它相容类中的相容类，称为最大相容类。记作任何其它相容类中的相容类，称为最大相容类。记作Cr。 若若Cr为最大相容类，显然它是为最大相容类，显然它是A的子集，对于任意的子集，对于任意x Cr ，x必与必与Cr中所有元素有相容关系。而在中所有元素有相容关系。而在ACr中没有任何元素与中没有任何元素与Cr所有元素有相容关系。所有元素有相容

156、关系。257校园课件在相容关系图中，在相容关系图中，最大完全多边形的顶点集合就是最最大完全多边形的顶点集合就是最大相容类大相容类。所谓完全多边形，就是每个顶点都与其它。所谓完全多边形，就是每个顶点都与其它顶点连接的多边形。例如三角形，有对角线的四边形。顶点连接的多边形。例如三角形，有对角线的四边形。此外，一个孤立结点，以及不是完全多边形的两个结此外，一个孤立结点，以及不是完全多边形的两个结点的连线，也是最大相容类。点的连线，也是最大相容类。例例1 设给定相容关系图如下，写出最大相容类。设给定相容关系图如下，写出最大相容类。 解解 最大相容类为：最大相容类为： a1,a2 a4,a6, a3,a

157、4 ,a6, a4,a5, a7258校园课件定理定理311.1 设设r是有限集是有限集A上的相容关系，上的相容关系，C是一个是一个相容类，那么必存在一个最大相容类相容类，那么必存在一个最大相容类Cr，使得，使得C Cr。完全覆盖完全覆盖：在集合：在集合A上给定的相容关系上给定的相容关系r，其最大相容，其最大相容类的集合称作集合类的集合称作集合A的完全覆盖。记作的完全覆盖。记作Cr（A）。）。 对于一个集合来说，集合上相容关系的相容类的对于一个集合来说，集合上相容关系的相容类的集合可以有许多种，它的覆盖也不是唯一的，但给定集合可以有许多种，它的覆盖也不是唯一的，但给定相容关系相容关系r，只能对

158、应唯一的完全覆盖。如上例。，只能对应唯一的完全覆盖。如上例。259校园课件定理定理3-11.2：给定集合：给定集合A的覆盖的覆盖A1，A2，An，由它确定的关系由它确定的关系RA1A1 A2A2 AnAn是相是相容关系。容关系。例例 设设A1，2，3，4，集合，集合1, 2, 3，3, 4和和 1, 2,2, 3,1, 3,3, 4都是都是A的覆盖，但它们可以产生的覆盖，但它们可以产生相同的相容关系。相同的相容关系。r, ,260校园课件定理定理3-11.3 集合集合A上相容关系上相容关系r与完全覆盖与完全覆盖Cr(A)存在一一对应存在一一对应.261校园课件3-12 序关系序关系偏序关系偏序

159、关系:设设A是一个集合是一个集合,如果如果A上的一个关系上的一个关系R,满满足自反性、反对称性和传递性，则称足自反性、反对称性和传递性，则称R是是A上的一上的一个偏序关系。记为个偏序关系。记为“ ”，序偶，序偶称为偏序集称为偏序集.例如例如,任何集合上的恒等关系、集合的幂集任何集合上的恒等关系、集合的幂集P（A）上的包含关系、实数集上小于等于关系，正整数集上的包含关系、实数集上小于等于关系，正整数集上的整除关系都是偏序关系。上的整除关系都是偏序关系。262校园课件例例1 在实数集在实数集R上，证明小于等于关系上，证明小于等于关系“”是偏序是偏序关系。关系。证明证明 1）对于任何实数）对于任何实

160、数a R，有，有aa成立，故成立，故是自是自反的。反的。 2）对于任何实数）对于任何实数a，b R，如果，如果ab且且 ba，则，则必有必有 a=b，故，故是反对称的。是反对称的。 3) 如果如果ab,bc ，那么必有，那么必有ac，故，故是传递的。是传递的。因此因此是偏序关系。是偏序关系。263校园课件例例2 给定集合给定集合A2，3，6，8，令，令“ ”|x整除整除y，验证，验证“ ”是偏序关系。是偏序关系。解解“ “, 关系矩阵和关系图如下关系矩阵和关系图如下: 1 0 1 1 0 1 1 0 M= 0 0 1 0 0 0 0 1 由关系图和关系矩阵可以看由关系图和关系矩阵可以看 出出”

161、 ”是自反的是自反的,反对称的和传递的反对称的和传递的.264校园课件盖住盖住:在偏序集合在偏序集合中中,如果如果x, y A, x y, xy且没有其它元素且没有其它元素z满足满足x z, z y, 则称元素则称元素y盖住了盖住了元素元素x .并且记并且记COV A=|x, y A; y盖住盖住x.如例如例2 中中,8盖住了盖住了2.265校园课件例例3 设设A是正整数是正整数m=12的因子的集合的因子的集合,并设并设 为整除关为整除关系系,求求COV A.解解m=12的因子的集合的因子的集合A=1,2,3,4,6,12“ ”=,COV A=, ,.266校园课件 对于给定的偏序集对于给定的

162、偏序集,它的盖住关系是唯它的盖住关系是唯一的一的,所以可用盖住的性质画出偏序集合图所以可用盖住的性质画出偏序集合图,或称哈或称哈斯图。哈斯图作图规则为斯图。哈斯图作图规则为(1)用小圆圈代表元素用小圆圈代表元素.(2)如果如果x y且且x y, 则将代表则将代表y 的小圆圈画在代表的小圆圈画在代表x 的小圆圈之上的小圆圈之上.(3)如果如果 COV A, 则在则在x与与 y之间用直线连接之间用直线连接. 267校园课件例 COV A=, ,.268校园课件链链: 设设是一个偏序集合是一个偏序集合,在在A的一个子集中的一个子集中,如如果每两个元素都是有关的果每两个元素都是有关的,则称这个子集为链

163、则称这个子集为链.反链反链:在在A的一个子集中的一个子集中,如果每两个元素都是无关的如果每两个元素都是无关的,则称这个子集为反链则称这个子集为反链.若若A的子集只有一个元素的子集只有一个元素,则这个子集既是链又则这个子集既是链又是反链是反链.269校园课件例例4设集合设集合A=a,b,c,d,e,上的二元关系为上的二元关系为R=,d,d,验证验证是偏序集是偏序集,画出哈斯图画出哈斯图,举例说明链及反链举例说明链及反链.解解 R的关系矩阵的关系矩阵 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1由关系矩阵可知由关系矩阵可知R具有自反性、反对称性

164、和传递性具有自反性、反对称性和传递性,得得是偏序集是偏序集,集合集合a,b,c, e,a,b,c,a,b,a,a,d,e等都是的子集也是链等都是的子集也是链.而而b,d,c,d,a等都是反链等都是反链.270校园课件全序关系全序关系(或线序关系或线序关系): 在偏序集在偏序集中中, 如果如果A是是一个链一个链,则称则称为全序或线序集合为全序或线序集合, 二元关系二元关系 称称为全序关系或线序关系为全序关系或线序关系. 全序集全序集就是对任意就是对任意x,y A,或者或者x y或者或者y x成立成立.例如例如,实数集上的小于关系就是全序关系实数集上的小于关系就是全序关系, 而正整数集合上的整除关

165、系就不是全序关系而正整数集合上的整除关系就不是全序关系 .271校园课件例例5 给定给定P=, a, a,b, a,b,c上的包含关系上的包含关系,证明证明是全序集合是全序集合.证明证明 因为因为 a a,b a,b,c,所以所以P中任意两中任意两个元素都有包含关系个元素都有包含关系.其哈斯图如下其哈斯图如下:272校园课件定义定义 设设为偏序集为偏序集,且且B A, (1) 若有若有b B, 使得使得B中不存在元素中不存在元素x,满足满足bx且且b x,则称则称b是是B的的极大元极大元.(2) 若有若有b B, 使得使得B中不存在元素中不存在元素x,满足满足bx且且x b,则称则称b是是B的

166、的极小元极小元.即即;如果如果B中没有比中没有比b大的其它元素大的其它元素, b就是就是B的一的一个极大元个极大元; 如果如果B中没有比中没有比b小的其它元素小的其它元素, b就是就是B的的一个极小元一个极小元.273校园课件例例6设设A=1,2,3,12,R为定义在为定义在A上的整除关系上的整除关系,求求A的极大元和极小元的极大元和极小元. 解解 的哈斯图如下的哈斯图如下.A的极大元有的极大元有:7,8,9,10,11,12; 极小元为极小元为1由此可知极大元和极小元由此可知极大元和极小元,有时不是唯一的有时不是唯一的.274校园课件定义定义 设设为偏序集为偏序集,且且B A, (1) 若有

167、若有b B, 对于对于B中的每一个元素中的每一个元素x,有有x b,则称则称b是是B的的最大元最大元.(2) 若有若有b B, 对于对于B中的每一个元素中的每一个元素x,有有b x,则称则称b是是B的的最小元最小元.在上例中在上例中A的最小元为的最小元为1 ,没有最大元没有最大元.275校园课件例偏序集例偏序集 的哈斯图如下的哈斯图如下:若若B=a,则则a是是B的最大元的最大元,是是B的最小的最小元元.若若B=a,b, 则则B没有最大元和最小元没有最大元和最小元.276校园课件定理定理 3-12.1 令令为偏序集为偏序集,且且B A,若若B有最大有最大(最小最小)元元,则必是唯一的则必是唯一的

168、.证明证明 假定假定a和和b都是都是B的最大元素的最大元素,则则a b和和b a,由由 的反对称性的反对称性,得得a=b.B的最小元情况与此类似的最小元情况与此类似.277校园课件定义定义 设设为偏序集为偏序集,且且B A,(1) 若若a A,且对且对B的任意元素的任意元素x,都满足都满足x a,则称则称a为为子集子集B的上界的上界.(2) 若若a A,且对且对B的任意元素的任意元素x,都满足都满足a x,则称则称a为为子集子集B的下界的下界.278校园课件例如例如,给定偏序集给定偏序集哈斯图如下哈斯图如下: B=a,b,c,d,e,f,g的上界是的上界是h,iB=h,i,j,k 的下界是的下

169、界是f,g ,a,b,c,d,e,h,i,f,g的下界为的下界为a ,而不是而不是b,c,d,e,上界是上界是k.279校园课件定义定义 设设为偏序集为偏序集,且且B A,(1) a为为B的任一上界的任一上界,若对若对B的所有上界的所有上界 y均有均有 a y, 则称则称a为为B的最小上界的最小上界(上确界上确界),记作记作LUB B.(2) b为为B的任一下界的任一下界,若对若对B的所有下界的所有下界 z均有均有 z b, 则称则称b为为B的最大下界的最大下界(下确界下确界),记作记作GLB B.280校园课件例如例如,在上例中在上例中, a是是f,h,j,i,g的最大下界的最大下界,没有最

170、小上没有最小上界界. 在右边的图中在右边的图中,2,3,6的最小上界为的最小上界为6,没有最大下界没有最大下界 6,12 的最大下界为为的最大下界为为6;最小上界为最小上界为12.281校园课件良序良序:任一偏序集合任一偏序集合,假如它的每一个非空子集存在最假如它的每一个非空子集存在最小元素小元素,则称为良序集则称为良序集.例例,在自然数的集合中在自然数的集合中, 小于等于关系是良序集小于等于关系是良序集.定理定理 3-12.3 每一个良序集合每一个良序集合,一定是全序集合一定是全序集合.定理定理3-13.4 每一个有限的全序集合每一个有限的全序集合,一定是良序集合一定是良序集合.例如例如,大

171、于零小于大于零小于1的全部实数的全部实数,按大小次序关系是一个按大小次序关系是一个全序集合全序集合,但不是良序集合但不是良序集合,因为集合本身不存在最小因为集合本身不存在最小元素元素.282校园课件第四章第四章 函数函数 4-1 函数的概念函数的概念函数函数: 设设f是从是从X到到Y的关系的关系,如果对于每一个如果对于每一个x X,有唯有唯一的一的y Y, 使得使得 f, 则称则称f为函数为函数.记为记为f: XY, 或或 假如假如 f, 则称则称x为为自变元自变元, y称在称在f作用下作用下x的的象象. f也可记为也可记为: y= f(x).从从X到到Y的函数也叫作从的函数也叫作从X到到Y的

172、的映射映射.283校园课件例例,X=x1,x2,x3, f=, 是函数是函数 F=,是关系是关系,不是函数不是函数.函数与关系的区别函数与关系的区别;a) 函数的定义域是函数的定义域是X,而关系的定义域是而关系的定义域是X的某个子集的某个子集.b )函数一个函数一个x X只能对应于唯一的一个只能对应于唯一的一个y,而关系不是而关系不是这样这样.284校园课件函数函数y=f(x)的定义域记作的定义域记作dom f=X, f的值域的值域ran f Y,有时也记为有时也记为Rf,Rf=y | ( x)( x X) (y=f(x)集合集合Y称为称为f的共域的共域, ran f亦称为函数的象集合亦称为函

173、数的象集合 285校园课件例例1 设设X=1,5,p,张明张明, Y=2,q,t,9,G,f=,即即f(1)=2, f(5)= q, f(p)=7, f(张明张明)=G,故故 dom f=X, Rf=2, q,7,G, Rf Y 286校园课件例例3 判别下列关系哪个能构成函数判别下列关系哪个能构成函数. a) f=, | x1, x2 N,且且x1+ x210 b) f= | y1, y2 R, y22 = y1 c) f=, | x1, x2 N, x2 为小于为小于x1 的素数个数的素数个数函数相等函数相等: 设函数设函数f:AB, g:CD,如果如果A=C,B=D,且且对于所有对于所有

174、x A和和x C有有f(x)=g(x),则称函数则称函数f和和g相等相等,记记作作f=g.287校园课件例如例如,设设X= a,b,c, Y=0,1, XY=, ,， XY的子集有的子集有26个个,其中只能其中只能23个是从个是从X到到Y的函数的函数.f0=,f1=, f2=, f3 =, f4 =, f5 =, f6 =, f7 =,288校园课件 设设X和和Y都为有限集都为有限集,分别有分别有m 和和n个不同的元素个不同的元素,由于从由于从X到到Y任意一个函数的定义域是任意一个函数的定义域是X,在这些函数中在这些函数中每一个有每一个有 m个序偶个序偶.另外任何元素另外任何元素x X,可以有

175、可以有Y的的n个个元素中的任何一个作为它的象元素中的任何一个作为它的象,故共有故共有nm个不同的函数个不同的函数.在上例中在上例中n=2,m=3 ,故有故有23个不同的函数个不同的函数.今后我们用今后我们用符符YX表示从表示从X到到Y的所有函数的集合的所有函数的集合.甚至当甚至当X和和Y是无是无限集时限集时,也用这个符号也用这个符号.289校园课件满射满射: 设函数设函数f:XY, 如果如果ran f=Y,则称则称f是满射的是满射的(或或到上映射到上映射). ran f=Y,即即Y的每一个元素是的每一个元素是X中一个或多个元素中一个或多个元素的象点的象点. 设设f:XY 是满射是满射,即对任意

176、即对任意y Y,必存在必存在x X使得使得f(x)= y成立成立.290校园课件例如例如, A=a,b,c,d, B=1,2,3,如果如果 f: AB为为:f(a)=1, f(b)=1, f(c)=3, f(d)=2则则f是满射的是满射的.291校园课件入射入射: 设函数设函数 f:XY, 若对于若对于x1,x2 X, x1x2都有都有f(x1)f(x2),则称则称f是是X到到Y入射入射(或单射、一对一映射或单射、一对一映射)的。的。即对于即对于x1,x2 X, 若有若有f(x1)f(x2)，则有，则有x1x2 。 例函数例函数f：NN，f（x）2 x 是入射的，但不是是入射的，但不是满射的。

177、满射的。例函数例函数f：ZZ，f（x）x+1 是入射的，也是是入射的，也是满射的。满射的。292校园课件双射双射：设函数：设函数f:XY,若若f既是入射的又是满射的，则称既是入射的又是满射的，则称f是双射的。是双射的。例如，上例的函数就是双射的。例如，上例的函数就是双射的。例如，令例如，令a,b表示的闭区间，表示的闭区间， 即即a,b x |axb，令令f：0，1a,b，f（x）(b-a)x+a, 这个函数是双这个函数是双射的。射的。293校园课件例例 (a) (b) (c)其中其中 (a),(c)是满射是满射 , (b),(a)是入射是入射, (c)是双射是双射.294校园课件定理定理 4-

178、1.1 令令X和和Y为有限集为有限集,若若 |X|=|Y|, 则则f:XY是是入射的入射的,当且仅当它是满射的当且仅当它是满射的.证明证明a. 若若f 是入射是入射,则则 |X|=| f(X)| ,因为因为| f(X)|=|Y|,从从f的定义有的定义有f(X) Y,而而| f(X)|=|Y|,又因为又因为|Y| 是有限的是有限的,故故f(X)=Y, 因此因此f 是满射是满射. b. 若若f 是一个满射是一个满射,根据满射定义根据满射定义f(X)=Y,于是于是|X|=|Y|= |f(X)|。因为。因为|X|= |f(X)| 和和|X|是有限的，故是有限的，故f是一个入射。是一个入射。295校园课

179、件 42 逆函数和复合函数逆函数和复合函数任意给定一个函数，它的逆不一定是函数，例如任意给定一个函数，它的逆不一定是函数，例如, 函数函数f , , fc=, , .296校园课件定理定理42.1设设f:XY是双射函数，那么是双射函数，那么fc是是Y:X的双的双射函数。射函数。证明证明 设设f= | x X y Y f (x)=y fc = | f 因为因为f是满射的是满射的,故每一故每一y Y 必存在必存在 f , 因此必有因此必有 fc,即即fc的前域为的前域为Y. 又因为又因为f是入射是入射, 对每一个对每一个y Y恰有一个恰有一个x X, 使使 f,因此仅有一个因此仅有一个x X,使使

180、 fc, 即即y对应于唯一的对应于唯一的x,故故fc是函数是函数. 297校园课件 又因又因ran fc =dom f =X,故故fc 是满射是满射, 又因为若又因为若y1y2有有fc(y1)fc(y2), 因为因为fc(y1)=x1, fc(y2)= x2, 即即x1=x2, 故故f(x1)=f(x2) , 即即y1=y2 得出矛盾得出矛盾,因此因此f是双射函数是双射函数.298校园课件逆函数逆函数: 设设f:XY是双射函数是双射函数,称称YX的双射函数的双射函数fc为为f的逆函数的逆函数,记作记作f-1。例如，设例如，设A1，2，3，B a,b,c，f:AB为为 f , , 则则f-1 =

181、, , 若若f , , 则则fc =, , 不是函数不是函数.299校园课件复合函数复合函数: f:XY, g:WZ, 若若f(X) W,则则 g f= | x X z Z ( y)(y Y y=f (x) z=g(y),称称g在函数在函数f的左边可复合的左边可复合. x和和z的关系即的关系即z=g(f(x)当当W=Y时时,则则f:XY, g:YZ.g f= | x X z Z ( y)(y Y y=f (x) z=g(y)300校园课件定理定理4-2.2 两个函数的复合是一个函数两个函数的复合是一个函数.例例1 设设X=1,2,3, Y=p,q, Z=a,b,f=, g=,q,b, 求求g

182、f.解解 g f=,.301校园课件定理定理4-2.2 令令g f是一个复合是一个复合 函数函数.a) 若若g 和和 f是满射的是满射的,则则g f是满射的是满射的.b) 若若g 和和 f是入射的是入射的,则则g f是入射的是入射的.c) 若若g 和和 f是双射的是双射的,则则g f是双射的是双射的.证明证明 a) 设设f:XY, g:WZ, 对任意对任意z Z, 因因g 是满射的是满射的,必有必有y Y,使使g (y)= z, 又因又因f是满射的是满射的, 必有必有x X,使使f(x)= y,故故 g f(x)= g(f(x)= g(y)= z, 因此因此g f 是满射的是满射的.302校园

183、课件b) 对任意对任意x1 ,x2 X, x1 x2 ,由由f 是入射的是入射的,故故f(x1) f(x2), 又因又因g是入射的是入射的,且且f(x1) f(x2), 故故g(f(x1 )g(f(x2)于是于是 x1 x2 g f (x1 )g f (x2 ), 因此因此g f 是入射的是入射的. c) 由由a),b) 得得c).303校园课件例例 : 设设g RR, g(x)= x+1, f:RR, f(x)=lnx,求求fg fg(x)= f(g(x)=ln(x+1). fg= | x R x -1例例2 设设R为实数集合为实数集合,对对x R有有f(x)= x+2, g(x)= x-2

184、, h(x)=3 x,求求gf, h(g f).解解 g f(x)= g(f(x)= g (x+2)=( x+2)-2= x 即即g f=| x R h(g f)( x)= h(g ( f(x) = h(x)=3 x, 即即 h(g f)= | x R304校园课件常函数常函数: 对于函数对于函数f:XY,如果存在如果存在y0 Y,对于每个对于每个 x X都有都有f(x)= y0 即即f(X)= y0,则称则称f为常函数为常函数.恒等函数恒等函数: 如果如果 IX=| x X , 则称函数则称函数 IX:XX为恒等函数为恒等函数.305校园课件定理定理 4-2.4 设函数设函数f: XY, 则

185、则 f=f IX =IY f 这个定理的证明可以由定义直接得到这个定理的证明可以由定义直接得到.306校园课件定理定理4-2.5 如果函数如果函数f: XY,有逆函数有逆函数f-1: YX,则则 f-1 f= IX且且 f f-1= IY307校园课件例例3 令令f:0,1,2a,b,c,其定义如下图其定义如下图, 求求f-1 f和和 f f-1 . f f-1 f-1 f f f-1解解f-1 f和和f f-1如右图如右图.308校园课件 第七章第七章 图论图论 7-1 图的基本概念图的基本概念 图是由一些结点和一些线构成的, 309校园课件图图: 图是一个三元组图是一个三元组,其中其中V(

186、G)是非空的结点的集合是非空的结点的集合,E(G)是边的集合是边的集合,G是从边集合是从边集合E到结点无序偶到结点无序偶(有序偶有序偶)集合上的函集合上的函数数.例例1 G= ,其中其中V(G)=a,b,c,d, E(G)=e1,e2,e3,e4,e5,e6,G( e1)=( a,b), G( e2)=( a, c ), G( e3)=( b,d), G( e4)=( b,c),G( e5)=( c,d), G( e6)=( a,d).310校园课件 若把图中的边看作是两个结点的联系若把图中的边看作是两个结点的联系,图可记为图可记为G=. 若边若边ei与结点无序偶与结点无序偶(vj,vk)相关

187、联相关联,则称该边为无向则称该边为无向边边. 若边若边ei与结点有序偶与结点有序偶相关联相关联,则称该边为有则称该边为有向边向边. 其中其中vj 称为称为ei的起始结点的起始结点; vk称为称为ei的终止结点的终止结点.311校园课件 每一条边都是无向边的图称为无向图每一条边都是无向边的图称为无向图. 如图如图(a) 每一条边都是有向边的图称为无向图每一条边都是有向边的图称为无向图. 如图如图(b) 如果在图中一些边是有向边如果在图中一些边是有向边,另一些边是无向边另一些边是无向边,则称这个图是混合图则称这个图是混合图.(如图如图(c)312校园课件G=G= v1,v2 ,v3,v4, , ,

188、 , G= v1,v2 ,v3,v4,( v1,v4), (v2 ,v4), , 313校园课件邻接点邻接点:在一个图中在一个图中,若两个结点由一条有向边或一条若两个结点由一条有向边或一条无向边关联无向边关联,则这两个结点称为邻接点则这两个结点称为邻接点.孤立结点孤立结点:在一个图中不与任何结点人邻接的结点在一个图中不与任何结点人邻接的结点.零图零图: 仅由孤立结点构成的图仅由孤立结点构成的图.平凡图平凡图: 仅由一个孤立结点构成的图仅由一个孤立结点构成的图.邻接边邻接边:关联于同一结点的两条边关联于同一结点的两条边.314校园课件回路回路(或环或环): 关联于同一结点的一条边关联于同一结点的

189、一条边. 环的方向是环的方向是没有意义的没有意义的,它既可作为有向边它既可作为有向边,也可作为无向边也可作为无向边. 例例下列两个图中下列两个图中,各有一个环各有一个环.315校园课件结点的度结点的度:在图在图G=中中,与结点与结点v(v V)关联的边关联的边 数称为该结点的度数数称为该结点的度数,记作记作deg(v).例例,在上图在上图(1)中中, v1的为的为3, v4的度数为的度数为1, v2的度数的度数为为4, 因为每个环在对应结点上度数加因为每个环在对应结点上度数加2.316校园课件图图G=的最大度数的最大度数: A(G)=max deg(v) | v V(G)图图G=的最小度数的最

190、小度数: A(G)=min deg(v) | v V(G)317校园课件定理定理7-1.1 每个图中每个图中,结点度数的总和等于边数的两倍结点度数的总和等于边数的两倍.证明证明 因为每条边必关联两个结点因为每条边必关联两个结点, 而一条边给于关联的每个结点的度数为而一条边给于关联的每个结点的度数为1, 因此在一个图中因此在一个图中,结点的度数总和等于边数的结点的度数总和等于边数的2倍倍.318校园课件定理定理 7-1.2 在任何图中在任何图中, 度数为奇数的结点必定是偶度数为奇数的结点必定是偶数个数个.证明证明 设设V1和和V2分别是分别是G中奇数度数和偶数度数的结中奇数度数和偶数度数的结点集

191、点集,则由定理定理则由定理定理7-1.1,有有 由此得由此得 为偶数为偶数,即即 | V1 | 是偶数是偶数.319校园课件入度入度:在有向图中在有向图中,射入一个结点的边数称为该结点的射入一个结点的边数称为该结点的入度入度.出度出度:在有向图中在有向图中,由一个结点射出的边数称为该结点由一个结点射出的边数称为该结点的出度的出度.结点的入度与出度之和就是该结点的度数结点的入度与出度之和就是该结点的度数.320校园课件定理定理7-1.3 在任何有向图中在任何有向图中,所有结点的入度之和等所有结点的入度之和等于所有结点的出度之和于所有结点的出度之和.平行边平行边:连接于同一对结点间的多条边称为是平

192、行的连接于同一对结点间的多条边称为是平行的.多重图多重图:含有平行边的图含有平行边的图. 例例 见见273页图页图7-1.5321校园课件简单图简单图: 不含有平行边和环的图不含有平行边和环的图.完全图完全图: 简单图简单图G=中中,若每一结点间都有边相若每一结点间都有边相连连,则称该图为完全图则称该图为完全图. Kn:有有n个结点的无向完全图个结点的无向完全图. 322校园课件定理定理 7-1.4 n个结点的无向图个结点的无向图Kn的边数为的边数为证明证明 在在Kn中中,任意两点间都有边相连任意两点间都有边相连, n个结点中任取个结点中任取两点的组合数为两点的组合数为:故故Kn的边数为的边数

193、为 有向完全图的边数也为有向完全图的边数也为:323校园课件补图补图: 给定一个图给定一个图G, 由由G中所有结点和所有能使中所有结点和所有能使G成成为完全图的所添加边组成的图为完全图的所添加边组成的图,称为称为G的相对于完全的相对于完全图的补图图的补图,或简称为或简称为G的补图的补图, 记作记作G.例下图互为补图例下图互为补图.324校园课件子图子图:设图设图G=, 如果有图如果有图G=,且且E E, V V, 则称则称G为为G的子图的子图.例下图中例下图中, (b)和和(c)是是(a)的子图的子图.325校园课件如果如果G的子图包含的子图包含G的所有结点的所有结点,则称该子图为则称该子图为

194、G的生的生成子图成子图.在下图在下图 中中,(2)和和(3)是是(1)的生成子图。的生成子图。326校园课件相对补图相对补图:设设G=是图是图G=的子图的子图,若给若给定另外一个定另外一个 图图G=使得使得E=E-E,且且 V中仅中仅包含包含E的边所关联的结点的边所关联的结点.则称则称G是子图是子图G的相对的相对于图于图G的子图的子图.例例 图图(c) 是图是图(b)相对于图相对于图(a)的补图的补图,而图而图(b)不是图不是图 (c)相对于图相对于图(a)的补图。的补图。327校园课件同构同构:设图设图G= 及图及图G=, 如果存在一一对如果存在一一对应的映射应的映射g:vivi且且e=(v

195、i, vj) (或或)是是G的一条边的一条边,当且仅当当且仅当e=(g(vi), g( vj)(或或是是G的一条的一条边边,则称则称G与与G同构同构,记作记作G G。 即即,若若G与与G同构同构,充要条件是充要条件是:两个图的结点和边分别两个图的结点和边分别存在着一一对应存在着一一对应,且保持关联关系且保持关联关系,例如例如,下图中下图中, (a)和和(b)同构同构,(c)和和(d)同构。同构。328校园课件 (a) (b)在在(a) 和和(b)中中, g(a)=a, g (b)= b,329校园课件在在(c)和和(d)中中, g (a) =u3, g(b)= u1, g (c)= u4, g

196、(d)= u2, , , 与与, , , 一一一对应一对应.330校园课件两图同构的必要条件是两图同构的必要条件是1.结点数目相同结点数目相同;2.边数相同边数相同;3.度数相同的结点数目相等。度数相同的结点数目相等。例如例如,下列两图不同构。下列两图不同构。P279331校园课件 7-2 路与回路路与回路路路:给定给定G=, 设设v0,v1,vn V, e1,e2,en E,其其中中ei是关联结点是关联结点 vi-1, vi 的边的边,交错序列交错序列v0 e1v1 e2en vn 称联结称联结v0到到vn 的路。的路。 其中其中v0和和vn分别称为起点和终点分别称为起点和终点, 边的数目边

197、的数目n称为路称为路的长度。的长度。332校园课件回路回路:当当v0=vn时时,这条路称为回路。这条路称为回路。迹迹:若一条路中所有的边若一条路中所有的边e1,e2,en都不相同都不相同,称为迹。称为迹。通路通路:若一条路中所有的结点若一条路中所有的结点v0,v1,vn 都不相同都不相同,则则称作通路。称作通路。圈圈:除除v0=vn外外,其余的结点都不相同。其余的结点都不相同。333校园课件例在下图中例在下图中:路路: v1 e2 v3 e3 v2 e3 v3 e4 v2 e6 v5 e7 v3 迹迹: v5 e8 v4 e5 v2 e6 v5 e7 v3 e4 v2 通路通路: v4 e8

198、v5 e6 v2 e1 v1 e2 v3 圈圈: v2 e1 v1 e2 v3 e7 v5 e6 v2334校园课件在简单图中一条通路由它的结点序列在简单图中一条通路由它的结点序列v0,v1,vn确定确定,所以简单图的路所以简单图的路,可由其结点序列表可由其结点序列表示。示。 在有向图中在有向图中,结点数大于结点数大于1 的一条路亦可由边的一条路亦可由边序列序列e1,e2,en表示。表示。335校园课件定理定理7-2.1 在一个具有在一个具有n个结点的图中个结点的图中,如果从结点如果从结点vj,到结点到结点vk存在一条路存在一条路,则从结点则从结点vj 到结点到结点vk 必存在一必存在一条不多

199、于条不多于n-1条边的路。条边的路。证明证明 如果从结点如果从结点vj 到结点到结点vk 存在一条路存在一条路, vj vi vk ,如果这条路有如果这条路有l l条边条边,则序列中必有则序列中必有l+1个结点个结点,若若ln-1, 则必有结点则必有结点vs,它在序列中出现不止一次它在序列中出现不止一次,即必即必有结点序列有结点序列vj vs vs vk,去掉从去掉从vs到结点到结点vs 之之间的边间的边,仍是从结点仍是从结点vj 到结点到结点vk的一条边路的一条边路,如此反复如此反复进行下去进行下去,就会得到一条从结点就会得到一条从结点vj 到结点到结点vk不多于不多于n-1条边的路条边的路

200、.336校园课件推论推论 在一个具有在一个具有n个结点的图中个结点的图中,若从结点若从结点vj 到结点到结点vk 必存在一条路必存在一条路,则必存在一条从则必存在一条从vj 到到vk边数小于边数小于n的通路的通路.337校园课件连通连通:在无向图在无向图G中中,结点结点u和和v之间若存在一条路之间若存在一条路,则称则称结点结点u和结点和结点v是连通的是连通的.结点之间的连通性是结点集结点之间的连通性是结点集V上的等价关系上的等价关系. 因因此对应这个等价关系此对应这个等价关系, 必可以将结点集必可以将结点集V作出一个划作出一个划分分,把把V分成非空子集分成非空子集V1,V2,Vm,使得两个结点

201、使得两个结点vj 和和vk是连通的是连通的,当且仅当它们属于同一个当且仅当它们属于同一个Vi . 我们把我们把G(V1),G(V2),G(Vm)称为图称为图G的连通分支的连通分支(图图),并把图并把图G的连的连通分支数度记作通分支数度记作W(G).338校园课件连通图连通图: 若图若图G只有一个连通分支只有一个连通分支,则称则称G是连通图。是连通图。 在连通图中在连通图中,任意两个结点都是连通的。任意两个结点都是连通的。339校园课件如果删除了连通图中的点或边如果删除了连通图中的点或边,就会影响图的连就会影响图的连通性通性.在图中删除结点在图中删除结点v,即是把即是把v以及与以及与v关联的边都

202、删除关联的边都删除.在图中删除某边在图中删除某边,仅需把该边删去仅需把该边删去. 例例,在下图中在下图中, 图图(a)删除删除v1 后后,变成图变成图(b),图图(a)删除边删除边e后变成图后变成图(c).340校园课件点割集点割集:设无向图设无向图G=为连通图为连通图,若有点集若有点集V1 V, 使图使图G删除了删除了V1 的所有结点后的所有结点后,所得的子图是不连通所得的子图是不连通图图,而删除了而删除了V1 的任何真子集后的任何真子集后,所得到的子图仍是连所得到的子图仍是连通图通图,则称则称V1 是是G的一个点割集的一个点割集. 若一个结点构成一个若一个结点构成一个点割集点割集,则称该结

203、点为则称该结点为割点割点。341校园课件例在左图中例在左图中, v3,v5,v2,v6为点割为点割集。集。v2,v6为割点。为割点。v2,v4,v1,v6不是点不是点割集。割集。342校园课件若若G不是完全图不是完全图,定义定义k(G)=min|V1| V1 是是G的点割集的点割集为为G的点连通度。的点连通度。连通度连通度k(G)是为了产生一个不连通图是为了产生一个不连通图,需要删除需要删除的点的最少数目。的点的最少数目。 一个不连通图的连通度为一个不连通图的连通度为0,存在割点的连通图的连通度为存在割点的连通图的连通度为1, 完全图完全图Kp ,删除删除p-1个结点后产生一个平凡图个结点后产

204、生一个平凡图（孤立结点）（孤立结点）, 故故k(Kp)= p-1.343校园课件边割集边割集: 设无向图设无向图G=为连通图为连通图,若有边集若有边集E1 E, 使图使图G删除了删除了E1 的所有边后的所有边后,所得的子图是不连通图所得的子图是不连通图,而删除了而删除了E1 的任何真子集后的任何真子集后,所得到的子图仍是连通所得到的子图仍是连通图图,则称则称E1 是是G的一个的一个边割集边割集。 若一个边构成一个边若一个边构成一个边割集割集,则称该边为则称该边为割边割边(或桥或桥)。344校园课件例在图中，例在图中，e3,e4,e4,e5,e1,e2,e3,e1,e2,e4,e9是边割集是边割

205、集, e9是桥是桥.e6,e7,e9,e1,e2,e5,e6,e8 不是边不是边割集割集.345校园课件非平凡图非平凡图G的边连通度为的边连通度为(G)=min|E1| E1 是是G的边割集的边割集为为G的边连通度。的边连通度。边连通度边连通度(G)是为了产生一个不连通图是为了产生一个不连通图,需要删需要删除的边的最少数目。除的边的最少数目。 一个不连通图的连通度一个不连通图的连通度(G)=0,平凡图的平凡图的(G)=0.346校园课件定理定理7-2.3 一个连通无向图一个连通无向图G中的结点中的结点v是割点的充分是割点的充分必要条件是存在两个结点必要条件是存在两个结点u和和w,使得结点使得结

206、点u和和w的每一的每一条路都通过条路都通过v。 例上图的例上图的v2,v6无向图的连通性无向图的连通性,不能推广到有向图。不能推广到有向图。347校园课件可达可达:在有向图在有向图G=中中,从结点从结点u到结点到结点v有一条路有一条路,称从称从u可达可达v。 可达性是有向图结点集上的二元关系可达性是有向图结点集上的二元关系,它具有自它具有自反性和传递性。反性和传递性。 如果如果u可达可达v,最短路的长度称为结点最短路的长度称为结点u和和v之间的之间的距离距离(或短程线或短程线)。记作。记作 d。 它满足下列性质它满足下列性质: d0 d+ dd348校园课件如果如果u和和v是不可达的是不可达的

207、,则则d=.d不一定等于不一定等于d有关距离对无向图也适用。有关距离对无向图也适用。 D=max d (u,v V) 称作图称作图G的直径的直径.349校园课件单侧连通单侧连通:在有向图在有向图G中中,任何一对结点间任何一对结点间,至少有一个至少有一个结点到另一个结点是可达的结点到另一个结点是可达的,则称这个图是单侧连通的。则称这个图是单侧连通的。强连通强连通: 在有向图在有向图G中中,任何一对结点间是任何一对结点间是相互相互可达的可达的,则称这个图是强连通的。则称这个图是强连通的。弱连通弱连通: 在有向图在有向图G中中,如果略去边的方向如果略去边的方向,将它看作无将它看作无向图向图,图是连通

208、的图是连通的,则称这个图是弱连通的。则称这个图是弱连通的。350校园课件例在左图中例在左图中, 图图(a)是强连通图是强连通图;图图(b)是单侧连通图是单侧连通图;图图(c)是弱连通图。是弱连通图。从上述定义看出从上述定义看出,若图若图G是强连通的是强连通的,则必是单侧连通则必是单侧连通的的,若图若图G是单侧连通的是单侧连通的,则必是弱连通的。则必是弱连通的。351校园课件定理定理 7-2.4 一个有向图是强连通的一个有向图是强连通的,当且仅当图当且仅当图G中有中有一个回路一个回路,它至少包含每个结点一次。它至少包含每个结点一次。强分图强分图:在简单有向图中在简单有向图中,具有强连通性质的最大

209、子图。具有强连通性质的最大子图。单侧分图单侧分图: 在简单有向图中在简单有向图中,具有单侧连通性质的最大具有单侧连通性质的最大子图子图.弱分图弱分图: 在简单有向图中在简单有向图中,具有弱连通性质的最大子图。具有弱连通性质的最大子图。352校园课件例在左图例在左图(a)中中,v1,v2,v3,v4 v5是强分图。是强分图。 v1,v2,v3,v4,v5是单侧分图是单侧分图,也是弱分图。也是弱分图。在图在图(b)中中v1,v2,v3,v4是强分图。是强分图。 v1,v2,v3, v1,v3,v4是单侧分图。是单侧分图。v1,v2,v3,v4 是弱分图。是弱分图。353校园课件定理定理 7-2.5

210、 在有向图在有向图G=中中,它的每一个结点位它的每一个结点位于且只位于一个强分图中于且只位于一个强分图中. 354校园课件7-3 图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵: 设设G=是一个简单图是一个简单图,它有它有n个结点个结点V=v1,vn,则则n阶方阵称为阶方阵称为G的邻接矩阵。的邻接矩阵。其中其中 aij= 1 vi adj vj 0 vi nadj vj 或或 i=j355校园课件图图(a)的邻接矩阵为的邻接矩阵为: 0 1 1 1 1 1 0 1 0 0 A(G)= 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0356校园课件图图(b)的邻接矩阵为的邻接矩阵为: 0

211、1 0 0 0 0 1 1A(G)= 1 1 0 1 1 0 0 0图图(c) 的邻接矩阵为的邻接矩阵为: 0 0 1 1 1 0 0 0A(G)= 1 1 0 1 0 1 0 0其中其中, 图图(c)是将图是将图(b)中的中的v1和和v2互换得到的。互换得到的。将图将图(c)的邻接矩阵的第一行的第二行互换的邻接矩阵的第一行的第二行互换,第一列第一列和第二列互换就得到图和第二列互换就得到图(b)的邻接矩阵。的邻接矩阵。357校园课件置换等价置换等价: 一个一个n阶方阵阶方阵A的某些行作一些置换的某些行作一些置换,再把相再把相应的列作同样的置换应的列作同样的置换,得到一个新的方阵得到一个新的方阵

212、A,则称则称A与与A置换等价。置换等价。显然置换等价是显然置换等价是n阶布尔矩阵集合上的一个等价阶布尔矩阵集合上的一个等价关系。关系。 有向图的结点有向图的结点,按不同次序写出的邻接矩阵是按不同次序写出的邻接矩阵是彼此置换等价的。彼此置换等价的。358校园课件在邻接矩阵在邻接矩阵A中中,第第i 行元素是由结点行元素是由结点vi出发的出发的,第第i行中值为行中值为1的元素数目等于的元素数目等于vi 的出度；的出度；同理第同理第j列中值为列中值为1的元素数目是的元素数目是vj的入度。的入度。359校园课件设有向图设有向图G的结点集合的结点集合V=v0,v1,vn, 它的邻接矩阵它的邻接矩阵A(G)

213、= (aij) nn,计算从结点计算从结点v vi i 到结点到结点 v vj j的的长度为长度为2的路的数目的路的数目, 必有必有结点结点vk,即即v vi i v vk k v vj j。 (1kn),如果图如果图G中有路中有路v vi i v vk k v vj j存存在在,则则aik=akj=1,即即aikakj=1,从结点从结点vi 到结点到结点 vj的长度为的长度为2的数目为的数目为: ai1a1j+ ai2a2j+ + ainanj=aikakj (1kn)恰好等于恰好等于(A(G)2中第中第i行、第行、第j列的元素值。列的元素值。360校园课件从结点从结点vi 到结点到结点 v

214、j的长度为的长度为3的路，可以看作从的路，可以看作从结点结点vi 到结点到结点 vk的长度为的长度为1的路，再联结结点的路，再联结结点vk 到结点到结点 vj的长度为的长度为2的路。故从结点的路。故从结点vi 到结点到结点 vj的长度为的长度为3的路的路的数目为：的数目为：aij（3）=aikakj（2）上述结论对无向图也成立。上述结论对无向图也成立。361校园课件定理定理73.1 设设A（G）是图）是图G的邻接矩阵，则的邻接矩阵，则(A(G)l中第中第i行、第行、第j列的列的元素元素aij（l）等于等于G中联结中联结vi 到到vj的长的长度为度为l路路的数目。的数目。362校园课件例例1给定

215、一图给定一图G=， 如图所示如图所示 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 2 0 0 0A 0 1 0 0 0 A2 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 2 0 0 0 2 0 2 0 0 2 0 2 0 0 0 4 0 0 0A3 0 2 0 0 0 A4 2 0 2 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1363校园课件在许多实际问题中常常要判断有向图中的一个结在许多实际问题中常常要判断有向图中的一个结点点vi 到另一个结点到另一个结点 vj是否存在

216、路的问题。是否存在路的问题。如果利用图如果利用图G的邻接矩阵的邻接矩阵A， 由可计算由可计算A，A2 ，A n ，当发现其中某个当发现其中某个Al的的aij（l）1，就表明结点，就表明结点vi 到结点到结点 vj中达。中达。(1ln).364校园课件可达性矩阵可达性矩阵：设：设G=是一个简单有向图，是一个简单有向图，V=v0,v1,vn，n阶方阵阶方阵P（pij)。 pij= 1 从从vi 到到 vj至少存在一条路至少存在一条路 0 从从vi 到到 vj不存在路不存在路求求p的方法：先求的方法：先求Bn，Bn= A+A2 + +An ，再从再从Bn 中将不为零的元素均改为中将不为零的元素均改为

217、1，而为零的元素不，而为零的元素不变。变。PA（1）A（2） A（ n）365校园课件 例例3 设图设图G如图所示，求可达矩阵。如图所示，求可达矩阵。 解解 0 1 0 0 0 0 0 0 1 0 A 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1A(2)= 1 0 0 0 0 1 0 0 0 0 = 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0

218、1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0A(3)= 0 1 0 0 0 1 0 0 0 0 = 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 366校园课件同理可得同理可得: 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1A(4)= 0 0 0 0 1 A(5)= 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1P=A A(2)

219、 A(3) A(4) A(5)= 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 367校园课件如果把邻接矩阵看作结点集如果把邻接矩阵看作结点集V上的关系上的关系R的关系的关系矩阵，则可达性矩阵矩阵，则可达性矩阵P即为即为MR+，因此可达性矩阵，因此可达性矩阵P亦可用以前学过的简便方法来求。亦可用以前学过的简便方法来求。上述可达性概念，可以推广到无向图中，只要上述可达性概念，可以推广到无向图中，只要将无向图中每条边看成是具有相反方向的两条边，将无向图中每条边看成是具有相反方向的两条边，这样，一个无向图就可以看成一个有向图，无向图这样，一个无向图就可以看成一个有向图，无向图的邻接矩阵

220、是一个对称矩阵，其可达的邻接矩阵是一个对称矩阵，其可达 性矩阵称为连性矩阵称为连通矩阵。通矩阵。368校园课件无向图的完全关联矩阵无向图的完全关联矩阵：给定一个无向图：给定一个无向图G，令，令v0,v1,vp,和和e1,e2,，eq,分别记为分别记为M（G）的结点）的结点和边，则和边，则p q阶矩阵阶矩阵M（G）（）（mij），其中），其中 ， mij 1 若若vi关联关联ej 0 若若vi不关联不关联ej369校园课件完全关联矩阵的性质完全关联矩阵的性质:1) 图中每一边关联两个结点，故图中每一边关联两个结点，故M（G）的每一）的每一列中只有两个列中只有两个1。2) 每一行中元素的和数是对应

221、结点的度数。每一行中元素的和数是对应结点的度数。3) 一行中元素全为一行中元素全为0，其对应的结点为孤立结点。，其对应的结点为孤立结点。4) 两个平行边其对应的两列相同。两个平行边其对应的两列相同。5) 同一个图当结点或边的编序不同时，其对应的同一个图当结点或边的编序不同时，其对应的 M（G）仅有行序，列序的差别。）仅有行序，列序的差别。370校园课件有向图的关联矩阵有向图的关联矩阵：给定简单有向图，：给定简单有向图，G=，Vv0,v1,vp，Ee1,e2,，eq，则，则p q阶矩阵阶矩阵M（G）（）（mij），其中），其中 ， mij 1 若在若在G中中vi是是ej的起点的起点 1 若在若在

222、G中中vi是是ej的终点的终点 0 若若vi不与不与ej关联关联371校园课件例如下图的完全关联矩阵为：例如下图的完全关联矩阵为：372校园课件图图G的完全关联矩阵中第的完全关联矩阵中第i行与第行与第j行相加：行相加：对有向图是指对应分量的普通加法运算；对有向图是指对应分量的普通加法运算；对无向图是指对应分量的模对无向图是指对应分量的模2加法运算，这种运算记加法运算，这种运算记为：为：vi vj vij ， 这种运算实际上是把结点这种运算实际上是把结点vi 与与vj 合并。合并。若若airajr=1,说明说明vi和和vj 之中只有一个结点是边之中只有一个结点是边er的的端点，将两个结点合并后的

223、结点端点，将两个结点合并后的结点vi，j 仍是仍是er的端点。的端点。若若airajr=0 则有两种情况则有两种情况: a) vi , vj 都不是都不是er的端点，那么的端点，那么vi，j也不是也不是er的端点。的端点。 b) vi , vj 都是都是er的端点，那么合并后在的端点，那么合并后在G中成为中成为vi，j的自回路，按规定应删去。不是的自回路，按规定应删去。不是er的端点。的端点。373校园课件 此外，在此外，在M（G）中若有某些列，其元素全为零，）中若有某些列，其元素全为零，说明由说明由G中的一些结点合并后，消失了一些对应边。中的一些结点合并后，消失了一些对应边。 例例1 下图中

224、，下图中，v4和和v5合并合并 。374校园课件例例2 下图中，合并结点下图中，合并结点v2和和v3 。其完全关联矩阵其完全关联矩阵M（G）与合并后的完全关联矩阵）与合并后的完全关联矩阵M（G）见）见297页。页。375校园课件 7-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图定义定义74.1 给定无孤立结点的图给定无孤立结点的图G，若存在一条路，若存在一条路，经过图中每条边一次且仅一次，该条路称为经过图中每条边一次且仅一次，该条路称为欧拉路欧拉路；若存在一条回路，经过图中每条边一次且仅一次，该若存在一条回路，经过图中每条边一次且仅一次，该回路称为回路称为欧拉回路欧拉回路。存在欧拉回路的图称为。存

225、在欧拉回路的图称为欧拉图欧拉图。376校园课件例在下图中，例在下图中，(a),(b)都不是欧拉路，都不是欧拉路，(c)是欧拉路，是欧拉路，但不是欧拉回路，但不是欧拉回路，(d)是欧拉回路。是欧拉回路。377校园课件定理定理 74.1 无向图无向图G具有一条欧拉路，当且仅当具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数结点。是连通的，且有零个或两个奇数结点。推论推论 无向图无向图G具有一条欧拉回路，当且仅具有一条欧拉回路，当且仅 当当G是连是连通的，并且所有结点度数全为偶数。通的，并且所有结点度数全为偶数。 例七桥问题答案是否定的。因为它有例七桥问题答案是否定的。因为它有4个结点，个结点

226、，度数是奇数。度数是奇数。 欧拉路问题也是一笔画问题。欧拉路问题也是一笔画问题。378校园课件例在下图中，例在下图中，(a是欧拉路是欧拉路,(b)是欧拉回路。是欧拉回路。379校园课件单向欧拉路单向欧拉路（回路）：给定有向图（回路）：给定有向图G，通过图中每，通过图中每边一次且仅一次的一条单向路（回路）。边一次且仅一次的一条单向路（回路）。定理定理74.2有向图有向图G具有一条单向欧拉回路，当且具有一条单向欧拉回路，当且仅当仅当G是连通的，且每个结点入度等于出度。是连通的，且每个结点入度等于出度。一个有向图一个有向图G具有单向欧拉路，当且仅当它是具有单向欧拉路，当且仅当它是连通的，而且除两个结

227、点外，每个结点的入度等于连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小，另一个结点的入度比出度小1 。 380校园课件例例1 计算机鼓轮的设计。如图，旋转鼓轮表面分成计算机鼓轮的设计。如图，旋转鼓轮表面分成24个部分，其中阴影部分表示导体，输出信号个部分，其中阴影部分表示导体，输出信号1；空白；空白部分表示绝缘体，输出信号部分表示绝缘体，输出信号0，根据鼓轮的位置，触，根据鼓轮的位置，触点得到信息点得到信息1101，旋转一个位置后，触点将输出信，旋转一个位置后，触点将输出信息息10

228、10。问鼓轮上。问鼓轮上16个部分怎样设计，才能使鼓轮个部分怎样设计，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。二进制数信息。381校园课件汉密尔顿路汉密尔顿路：经过图中每个结点一次且仅一次的通：经过图中每个结点一次且仅一次的通路。路。汉密尔顿回路汉密尔顿回路：经过图中每个结点一次且仅一次的：经过图中每个结点一次且仅一次的回路。回路。汉密尔顿图汉密尔顿图：具有汉密尔顿回路的图。：具有汉密尔顿回路的图。例例;(a)是汉密尔顿路；是汉密尔顿路；(b)是汉密尔顿图；是汉密尔顿图；(c)不是汉不是汉密尔顿路。密尔顿路。382校园课件

229、定理定理74.3 若图若图G=具有汉密尔顿回路具有汉密尔顿回路,则对于则对于结点集结点集V的每个非空子集的每个非空子集S均有均有W(G-S)|S|成立成立.其中其中W(G-S)是是G-S中连通分支数中连通分支数.利用以上定理可以证明某些图不是汉密尔顿图利用以上定理可以证明某些图不是汉密尔顿图,但不能但不能证明一个图是汉密尔顿图证明一个图是汉密尔顿图.383校园课件例下图例下图(a)中中,若取若取S=V1,V4 ,则则G-S 中有三个分图中有三个分图,故故 G不是汉密尔顿图不是汉密尔顿图.在图在图(b)中满足条件中满足条件W(G-S)|S|,但它不是汉密尔顿但它不是汉密尔顿图图.(删去一个或任意

230、两个结点删去一个或任意两个结点,不能使它不连通不能使它不连通,.)384校园课件定理定理7-4.4 设设G具有具有n个结点的简单图个结点的简单图,如果如果G中每一中每一对结点度数之和大于等于对结点度数之和大于等于n-1,则在则在G中存在一条汉中存在一条汉密尔顿路。密尔顿路。这个定理是判断汉密尔顿路存在的充分条件这个定理是判断汉密尔顿路存在的充分条件,但不是必要条件但不是必要条件.如在下图中如在下图中, n=6,每对结点度数之每对结点度数之和是和是4,但在图中存在一条汉密尔顿路。但在图中存在一条汉密尔顿路。385校园课件例例1 考虑在七天内安排七门课程的考试考虑在七天内安排七门课程的考试,使得同

231、一门使得同一门教师所任的两门课程考试不排在接连的两天中教师所任的两门课程考试不排在接连的两天中,试证试证明如果没有教师担任多于四门课程明如果没有教师担任多于四门课程,则符合上述要求则符合上述要求的考试安排总是可能的。的考试安排总是可能的。证明证明 设设G为具有七个结点的图为具有七个结点的图,每个结点对应于一门每个结点对应于一门课程的考试课程的考试,如果这两个结点对应的课程考试是由不如果这两个结点对应的课程考试是由不同教师担任的同教师担任的,那么这两个结点之间有一条边那么这两个结点之间有一条边,因为每因为每个教师所担任课程数不超过个教师所担任课程数不超过4,故每个结点的度数至少故每个结点的度数至

232、少是是3,任意两个结点的度数之和至少是任意两个结点的度数之和至少是6,故故G总是包含总是包含一条汉密尔顿路一条汉密尔顿路,它对应于一个七门考试课目的一个它对应于一个七门考试课目的一个适当的安排。适当的安排。386校园课件定理定理7-4.5 设设G是具有是具有n个结点的简单图个结点的简单图,如果如果G中每中每一对结点度数之和大于等于一对结点度数之和大于等于n,则在则在G中存在一条汉中存在一条汉密尔顿回路。密尔顿回路。387校园课件闭包闭包: 给定图给定图G=有有n个结点个结点,若将图若将图G中度数之中度数之和至少是和至少是n的非邻接结点连接起来得图的非邻接结点连接起来得图G,对图对图G重重复上述

233、步骤复上述步骤,直到不再有这样的结点对存在为止直到不再有这样的结点对存在为止,所得所得到的图到的图,称为是原图称为是原图G的闭包的闭包,记作记作C(G)。388校园课件例例389校园课件例例2 指出图指出图G中没有汉密尔顿路。中没有汉密尔顿路。解解 在上图中若存在着汉密尔顿路在上图中若存在着汉密尔顿路,一定是一定是ABAB交错着交错着,但在图中有但在图中有9个个A,7个个B,所以上图中不存在所以上图中不存在汉密尔顿路。汉密尔顿路。390校园课件注意注意:如果在标记过程中如果在标记过程中,遇到相邻结点出现相同标遇到相邻结点出现相同标记时记时,可在此对应边上增加一个结点可在此对应边上增加一个结点,

234、并标上相异标并标上相异标记记.如图所示。如图所示。391校园课件 7-5 平面图平面图在现实生活中，要画一些图，希望边与边之间在现实生活中，要画一些图，希望边与边之间尽量减少相交的情况。尽量减少相交的情况。定义定义75.1 设设 G=是一个图，若能够把是一个图，若能够把G画在一画在一个平面上，同时使得任意两条边仅仅在结点处才相交，个平面上，同时使得任意两条边仅仅在结点处才相交，则称则称G是一个是一个平面图平面图。 画出的没有边交叉出现的图称为画出的没有边交叉出现的图称为G的的平面嵌入平面嵌入。例例 下列图为平面图下列图为平面图 392校园课件有些图不管选样画，除去结点外，总有边相交。有些图不管

235、选样画，除去结点外，总有边相交。例例 下列图为非平面图。下列图为非平面图。393校园课件定义定义75.2 设设G 是连通平面图，（是连通平面图，（G 的某个平面嵌入）的某个平面嵌入），G的边将的边将G所在的平面划分成若干个区域，每个区所在的平面划分成若干个区域，每个区域称为域称为G的一个的一个面面。包围着一个面的诸边所构成的回。包围着一个面的诸边所构成的回路称为这个面的路称为这个面的边界边界。不受边界约束的面称作。不受边界约束的面称作无限面无限面。面的边界的回路长度称作该面的面的边界的回路长度称作该面的次数次数。记为记为deg(r).例例 deg(r1)3deg(r2)3deg(r3)5deg

236、(r4)4deg(r5)3394校园课件定理定理 75.1 一个有限平面图，面的次数之和等于其一个有限平面图，面的次数之和等于其边数的两倍。边数的两倍。定理定理 75.2 （欧拉定理）（欧拉定理）设有一个设有一个 连通的平面图连通的平面图G，共有，共有 v 个结点个结点 e 条边和条边和 r 个面，则欧拉公式个面，则欧拉公式 v e + r =2成立。成立。395校园课件证明证明 （1）若）若G为一个为一个 孤立的结点，孤立的结点，则则v1， e 0， r1，故，故v e + r=2 成立成立 。（2）若）若G为一条边，即为一条边，即v2， e 1， r1， 故故v e + r =2 成立成立

237、 。（3）设）设G为为k条边时，条边时，v k e k + r k 2 成立成立 。 下面考察下面考察G为为k+1条边时的情况。条边时的情况。 因为在因为在k条边的连通图增加一条边使它仍为连通条边的连通图增加一条边使它仍为连通图，只有下述两种情况：图，只有下述两种情况：396校园课件a)加上一个新结点加上一个新结点Q2，Q2与图上的一点与图上的一点Q1相连，相连，此时此时vk 和和ek都增加都增加1，而面数，而面数rk不变，故不变，故 (vk +1) (ek+1) + rk = v k e k + r k =2b) 用一条边连接图上的两已知点用一条边连接图上的两已知点Q1和和Q2 ， 此时此时

238、ek和和rk都增加都增加1，而面数，而面数vk 不变，故不变，故 vk (ek+1) + （rk +1） = v k e k + r k =2397校园课件定理定理75.3 设设G是一个有是一个有v个结点个结点e条边的连通简单条边的连通简单平面图，若平面图，若 v3 则则 e 3v- 6。证明证明 设连通平面图设连通平面图G的面数为的面数为 r ， 当当v3，e2时上式成立，时上式成立， 若若 e 3 ，则每一面的次数不小于，则每一面的次数不小于3， 由定理由定理75.1 各面次数之和为各面次数之和为2e，因此，因此 2e 3r，r e代入欧拉定理：代入欧拉定理： 2ve+ r ve+ e 2

239、ve/3 63v e e3v6398校园课件例例1 K5是非平面图。是非平面图。解解 因为有因为有5个结点个结点10个边，故个边，故35610，即，即 3v-6e 不成立，不成立， 故故K5是非平面图。是非平面图。399校园课件例例2 证明证明K3，3是非平面图。是非平面图。证明证明 如果如果K3，3是平面图，是平面图，因因 为在为在K3，3中任取中任取3个结点，个结点，其中必有两个结点不邻接，其中必有两个结点不邻接，故每个面的次数都不小于故每个面的次数都不小于4， 由由4r2e，（，（定理定理 75.1 ） 即即 re/2即即ve+e/2 ve+r=2. 即即 2v-4e在在K3，3中有中有

240、6个结点个结点9条边，故条边，故 2649，即，即K3，3是非平面图。是非平面图。400校园课件定义定义 75.8 给定两个图给定两个图G1和和G2，如果它们是同构，如果它们是同构的，或者通过反复插入或删除度数为的，或者通过反复插入或删除度数为2 的结点后，的结点后，使使G1和和G2同构，则称该两图是在同构，则称该两图是在2度结点内同构。度结点内同构。401校园课件定理定理75.4（库拉托夫斯基定理）（库拉托夫斯基定理） 一个图是平面图，一个图是平面图，当且仅当它不包含与当且仅当它不包含与K3，3或或K5在在2 度结点内同构的度结点内同构的子图。子图。402校园课件 76 对偶与着色对偶与着色

241、定义定义 76.1 给定平面图给定平面图 G,它具有面它具有面F1，F2，Fn, 若有图若有图G* 满足下述条件：满足下述条件：1）对于图）对于图G的任一个面的任一个面Fi,内部有且仅有一个结点内部有且仅有一个结点vi*V*。2）对于于图G的面的面Fi，Fj的公共边界的公共边界ek,存在且仅存在一条存在且仅存在一条 边边ek* E*,使使ek* （vi*,vj*),且且ek* 与与ek相交。相交。3）当且仅当）当且仅当ek只是一个面只是一个面Fi的边界时，的边界时，vi*,存在一个环存在一个环ek* 和和 ek相交。相交。 则称图则称图G*是图是图G的对偶图。的对偶图。例右图例右图403校园课

242、件由对偶图的定义得，如果由对偶图的定义得，如果G*是是G的对偶图，则的对偶图，则G也也是是G*的对偶图。一个连通的平面图的对偶图也是平的对偶图。一个连通的平面图的对偶图也是平面图。面图。404校园课件定义定义76.2 如果图如果图G的对偶图的对偶图G*同构于同构于G，则称，则称G是是自对偶图。自对偶图。例例405校园课件 从对偶图的问题，我们可以看到，对于地从对偶图的问题，我们可以看到，对于地图的着色问题，可以归纳为对于平面图的结点的图的着色问题，可以归纳为对于平面图的结点的着色问题。因此四色问题可以归结为要证明对于着色问题。因此四色问题可以归结为要证明对于任何一个平面图，一定可以用四种颜色，

243、对它的任何一个平面图，一定可以用四种颜色，对它的结点进行着色，使得邻接的结点都有不同的颜色。结点进行着色，使得邻接的结点都有不同的颜色。406校园课件定义定义76.3 给图给图G 的每个结点着色，使得没有两个的每个结点着色，使得没有两个相邻结点着上相同的颜色，这种着色称为相邻结点着上相同的颜色，这种着色称为正常着色正常着色。如果图如果图G的结点可用的结点可用n种颜色正常着色，则称种颜色正常着色，则称G为为 n色的。色的。对于图对于图G着色时，需要的最少颜色数称为着色时，需要的最少颜色数称为G的的着色数，记为着色数，记为x(G)。407校园课件韦尔奇韦尔奇鲍威尔法（鲍威尔法（Welch Powe

244、ll)1）将图）将图G中的结点按照度数的递减次序进行排列。中的结点按照度数的递减次序进行排列。2）用第一种颜色对第一点着色，并且按排列次序，）用第一种颜色对第一点着色，并且按排列次序，对与前面着色点不邻接的每一点着上同样的颜色。对与前面着色点不邻接的每一点着上同样的颜色。3）用第二种颜色对尚未着色的点重复）用第二种颜色对尚未着色的点重复 2），用第），用第三种颜色继续这种做法。直到所有的点都着上色为三种颜色继续这种做法。直到所有的点都着上色为止。止。408校园课件例例1 用韦尔奇用韦尔奇鲍威尔法对下图着色。鲍威尔法对下图着色。解解 1）排列结点次序：）排列结点次序：A5，A3，A7，A1，A2

245、，A4，A6，A82）对）对A5和和A1着第一种颜色。着第一种颜色。3）对）对A3，A4，A8着第二种颜色。着第二种颜色。4）对结点）对结点A7和和A2、A6着第三种颜色。着第三种颜色。 因此因此G是是3色的。即色的。即x(G)3.409校园课件定理定理76.1 对于对于n个结点的完全图个结点的完全图K n，有，有x(Kn） n定理定理76.2 设设G为一个至少具有三个结点的连通平面为一个至少具有三个结点的连通平面图，则图，则G中必有一个结点中必有一个结点u, 使得使得deg(u) 5.证明证明 设设G, |V|=v, |E|=e,若若G的每一个结点的每一个结点u,都有都有 deg(u) 6,

246、 但因但因故故 2e6v ,所以所以 e3v 3v-6, 矛盾。矛盾。 定理定理76.3 任意平面图任意平面图G最多是最多是5-色的。色的。410校园课件7-7 树与生成树树与生成树树树:一个连通且无回路的无向图。一个连通且无回路的无向图。树叶树叶:树中度数为树中度数为1 的结点。的结点。内点内点:树中度数大于树中度数大于1 的结点。的结点。森林森林:多个无回路的无向图多个无回路的无向图,它的每个连通分图是它的每个连通分图是树。树。411校园课件定理定理77.1 给定图给定图T，以下关于树的定义是等价的，以下关于树的定义是等价的，1）无回路的连通图。）无回路的连通图。2）无回路且）无回路且e=

247、v-1,其中其中e是边数，是边数，v是结点数。是结点数。3）连通且）连通且e=v-1。4）无回路，但增加一条新边，得到一个且仅有一个）无回路，但增加一条新边，得到一个且仅有一个回路。回路。5）连通，但删去一边后便不连通。）连通，但删去一边后便不连通。6）每一对结点之间有且仅有一条）每一对结点之间有且仅有一条路。路。 412校园课件定理定理77.2 任意一棵非平凡树中至少有两片树叶。任意一棵非平凡树中至少有两片树叶。 有一些图它本身不是树，但是它的子图却是树。有一些图它本身不是树，但是它的子图却是树。生成树生成树：若图：若图G的生成子图是一棵树，则称它为的生成子图是一棵树，则称它为G的的生成树。

248、生成树。树枝树枝：生成树：生成树T中的边。中的边。弦弦：图：图G不在生成树中的边。不在生成树中的边。补补：所有弦的集合称作：所有弦的集合称作 生成树生成树T的补。的补。413校园课件定理定理77.3 连通图至少有一棵生成树。连通图至少有一棵生成树。例如在下图中，图例如在下图中，图(b),图图(c)都是图都是图(a)的生成树。的生成树。414校园课件G是一个有是一个有n个结点和个结点和m条边的连通图，由条边的连通图，由G的的生成树正好有生成树正好有n1条边。因此要确定条边。因此要确定G的一棵生成树，的一棵生成树，必须删去必须删去G的的m-(n-1)=m-n+1条边。数条边。数m-n+1称为图称为

249、图G的秩。的秩。秩秩：m-n+1。其中。其中n和和m分别为连通图的结点数和边分别为连通图的结点数和边数。数。415校园课件定理定理77.4 一条回路和任何一棵生成树的补至少一条回路和任何一棵生成树的补至少有一条公共边。有一条公共边。证明证明 若有一条回路和一棵生成树的补没有公共边。若有一条回路和一棵生成树的补没有公共边。那么这回路包含在生成树中，这是不可能的。因那么这回路包含在生成树中，这是不可能的。因为生成树不能包含回路。为生成树不能包含回路。416校园课件定理定理77.5 一个边割集和任何生成树至少有一条公共一个边割集和任何生成树至少有一条公共边。边。证明证明 若有一个边割集和一棵生成树的

250、补没有公共边。若有一个边割集和一棵生成树的补没有公共边。那么删除这个边割集后所得子图必包含该生成树，这那么删除这个边割集后所得子图必包含该生成树，这意味着删除边割集后仍是边通图，与边割集定义矛盾。意味着删除边割集后仍是边通图，与边割集定义矛盾。417校园课件图图G中结点表示一些城市，各边表示城市间道中结点表示一些城市，各边表示城市间道路，边的权表示道路的长度。如果要用通讯线路把路，边的权表示道路的长度。如果要用通讯线路把这些城市联系起来，要求线路最短，这就是要求生这些城市联系起来，要求线路最短，这就是要求生成树，使该生成树是图成树，使该生成树是图G的所有生成树中边权的和的所有生成树中边权的和为

251、最小。为最小。C（e）:表示边表示边e的权。的权。树权树权：设：设T是图是图G的一棵生成树，的一棵生成树，T的各边边权的和。的各边边权的和。记为记为C(T)。最小生成树最小生成树：在图：在图G的所有生成树中，树权最小的的所有生成树中，树权最小的那棵生成树。那棵生成树。418校园课件克鲁斯卡尔算法克鲁斯卡尔算法：设图：设图G有有n个结点，以下算法产个结点，以下算法产生最小生成树。生最小生成树。a) 选取最小权边选取最小权边e1，置边数，置边数i=1;b) i=n-1 结束，否则转结束，否则转 c);c) 设已选择边为设已选择边为e1，e2，ei，在，在G中选取不同中选取不同于于e1，e2，ei的

252、边的边ei+1，使，使 e1，e2，ei，ei+1中无回路且中无回路且ei+1是满足此条件的最小权的边。是满足此条件的最小权的边。 d) i+1i，转，转b)419校园课件例左图中，最小生成树由绿色的边组成。例左图中，最小生成树由绿色的边组成。 右图中，最小生成树由边（右图中，最小生成树由边（x1,x2）, （x2,x5）, （x2,x4）, （x4,x3）组成。）组成。420校园课件78 根树及其应用根树及其应用有向树有向树：如果一个有向图在不考虑边的方向时是：如果一个有向图在不考虑边的方向时是一棵树，那么这个有向图称为有向树。一棵树，那么这个有向图称为有向树。例如下图。例如下图。421校园

253、课件根树：根树：一棵有向树，如果有一个结点的入度为一棵有向树，如果有一个结点的入度为0，其余，其余所有结点的入度都为所有结点的入度都为1 ，则称为根树。，则称为根树。根根：根树中入度为：根树中入度为0的结点。的结点。叶叶：根树中出度为：根树中出度为0 的结点。的结点。分枝点或内点分枝点或内点;出度不为出度不为0 的结点。的结点。422校园课件层次层次：在根树中，任一结点的层次为从根到该结点的：在根树中，任一结点的层次为从根到该结点的单向通路的长度。单向通路的长度。例在上图中，例在上图中，v1 的层次为的层次为0，v2, v3, v4层次为层次为1，v5, v6, v7, v8, v9层次为层次

254、为2。根树的递归定义根树的递归定义：根树包含一个或多个结点，这些结：根树包含一个或多个结点，这些结点中某个称为根，其它所有结点被分成有限个子根树。点中某个称为根，其它所有结点被分成有限个子根树。423校园课件对于一棵根树，可以有树根在下和树根在上两对于一棵根树，可以有树根在下和树根在上两种不同的画法，见书上种不同的画法，见书上329页。页。书上的三个根树的彼此同构的。书上的三个根树的彼此同构的。424校园课件一棵根树可以看成一棵家庭树，设一棵根树可以看成一棵家庭树，设a是一棵根是一棵根树的分枝结点，树的分枝结点，假若从假若从a到到b有一条边，则结点有一条边，则结点b称为称为a的的“儿儿子子”，

255、或称，或称a为为b的的“父亲父亲”。 假若从假若从a到到c有一条单向通路，则结点有一条单向通路，则结点a称为称为c的的“祖先祖先”，或称，或称c为为a的的“后裔后裔”。同一分枝结点的同一分枝结点的“儿子儿子”称为称为“兄弟兄弟”。425校园课件m叉树叉树：在根树中，若每一个结点的出度小于或等于：在根树中，若每一个结点的出度小于或等于m，则称这棵树为，则称这棵树为m叉树叉树。完全完全m叉树叉树：在根树中，若每一个结点的出度恰好等：在根树中，若每一个结点的出度恰好等于于m或零，则称这棵树为完全或零，则称这棵树为完全m叉树。叉树。正则正则m叉树叉树：其所有树叶层数相同。：其所有树叶层数相同。426校

256、园课件当当m2时，称为二叉树。时，称为二叉树。任何一个有序树都可以把它转换为一棵对应的二叉树。任何一个有序树都可以把它转换为一棵对应的二叉树。427校园课件一个有序森林，也可以转换成一棵二叉树，如下图。一个有序森林，也可以转换成一棵二叉树，如下图。428校园课件定理定理78.1 设有完全设有完全m叉树，其树叶数为叉树，其树叶数为t,分枝结点分枝结点数为数为i， 则则 (m-1)i=t-1。证明证明 当当i0，t1， 每增加一个分枝结点，就增加每增加一个分枝结点，就增加(m-1)个树叶结点，个树叶结点，所以所以t1+(m-1) i 所以有所以有 (m-1) i=t-1。429校园课件例例1 设有

257、设有28盏电灯，拟用一个电源插座，问需用多盏电灯，拟用一个电源插座，问需用多少块具有四插座的接线板。少块具有四插座的接线板。解解 将四叉树的每个分枝结点看作是具有四插座的将四叉树的每个分枝结点看作是具有四插座的接线板，树叶看作是电灯，由接线板，树叶看作是电灯，由(m-1) i=t-1。则有则有 （41）i281， i9，所以需要所以需要9块接线板。块接线板。430校园课件例例2 假设有一台计算机，它有一条加法指令，可计算假设有一台计算机，它有一条加法指令，可计算三个数的和，如果要计算三个数的和，如果要计算9个数的和，至少要执行几个数的和，至少要执行几次加法指令。次加法指令。解解 把把9个数看作

258、是完全个数看作是完全3叉树的叉树的9片树叶，则有片树叶，则有 （31）i91， i4，所以需要执行所以需要执行4次加法指令。次加法指令。431校园课件结点的通路长度结点的通路长度：从树根到此结点的通路中的边数。：从树根到此结点的通路中的边数。内部通路长度内部通路长度：分枝结点的通路长度。：分枝结点的通路长度。外部通路长度外部通路长度：树叶结点的通路长度。：树叶结点的通路长度。定理定理78.2 若完全二叉树有若完全二叉树有n个分枝结点，且内部通个分枝结点，且内部通路长度的总和为路长度的总和为I，外部通路长度的总和为，外部通路长度的总和为E，则，则 EI+2n432校园课件带权二叉树带权二叉树：设

259、有一棵二叉树，共有：设有一棵二叉树，共有t 片树叶，分片树叶，分别带权别带权w1, w2, wt, 该二叉树称为带权二叉树。该二叉树称为带权二叉树。二叉树的权二叉树的权：在带权二叉树中，若带权为：在带权二叉树中，若带权为wi的树的树叶，其通路长度为叶，其通路长度为L(wi), w(T)=wi L(wi) (i=1,2 , t)433校园课件最优树最优树: w(T)最小的树。最小的树。求最优树的算法求最优树的算法Huffman算法算法:给定一组权给定一组权w1, w2, wt,且有且有w1 w2wt,(1) 连接连接w1, w2,为权的两片树叶，得一分枝结点，其为权的两片树叶，得一分枝结点，其权

260、为权为w1+ w2；(2) 在在w1+ w2，w3, wt中选出两个最小的权，连接中选出两个最小的权，连接它们对应的顶点，得分枝结点，得分枝结点所带的它们对应的顶点，得分枝结点，得分枝结点所带的权；权；(3) 重复（重复（2），直到形成），直到形成t1 枝结点，枝结点，t片树叶为止。片树叶为止。434校园课件例例3求带权为求带权为2，3，5，7，11，13，17，19，29的最优二叉树。的最优二叉树。解解 2，3，5，7，11，13，17，19，29 5，5，7，11，13，17，19，29 10，7，11，13，17，19，29 17，11，13，17，19，29 17, 24，17，19，

261、29 24，34，19，29 34，43，29 43，63 106435校园课件二叉树的另一个应用，就是二叉树的另一个应用，就是前缀码前缀码问题。问题。在远距离通讯中，常常用在远距离通讯中，常常用0 和和1的字符串作为英的字符串作为英文字母传送信息，因为英文字母有文字母传送信息，因为英文字母有26个，用不等长的个，用不等长的二进制序列表示二进制序列表示26个英文字母时，有个英文字母时，有2+22+2i262i+1 226, i4故用长度不超过故用长度不超过4的二进制序列就可以表示的二进制序列就可以表示26个字母。由于字母使用的频率不同，为了减少信息量，个字母。由于字母使用的频率不同，为了减少信

262、息量，可以用长度短的序列表示使用频繁高的字母，用长的可以用长度短的序列表示使用频繁高的字母，用长的序列表示使用频率小的字母。为了在接收信息时保证序列表示使用频率小的字母。为了在接收信息时保证译码正确，要使用前缀码表示英文字母。译码正确，要使用前缀码表示英文字母。436校园课件前缀码：前缀码： 给定一个序列的集合，若没有一个序列是给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。另一个序列的前缀，该序列集合称为前缀码。例如，例如，000，001，01，10，11是前缀码。是前缀码。 而而 1，10，101，100就不是前缀码。就不是前缀码。437校园课件定理定理78.5

263、 任意一棵二叉树的树叶可对应一个前缀码任意一棵二叉树的树叶可对应一个前缀码。证明证明 给定一棵二叉树，从每一个分枝点引出两条边，给定一棵二叉树，从每一个分枝点引出两条边，对左侧边标以对左侧边标以0，右侧边标以，右侧边标以1，则每片树叶将可以标，则每片树叶将可以标定一个定一个0和和1的序列，的序列，它是由树根到这片树叶上各边标它是由树根到这片树叶上各边标号所组成的序列号所组成的序列，显然，没有一片树叶的标定序列是，显然，没有一片树叶的标定序列是另一片树叶标定序列的前缀，因此，任何一棵二叉树另一片树叶标定序列的前缀，因此，任何一棵二叉树的树叶可以对应一个前缀码。的树叶可以对应一个前缀码。438校园课件定理定理78.6 任何一个前缀码都对应一棵二叉树。任何一个前缀码都对应一棵二叉树。例例 下面的二叉树对应的前缀码是下面的二叉树对应的前缀码是 00，1，011，0100，0101439校园课件例例4 在通讯中，在通讯中，a,b,c,d,e,f,g,h,I 出现的频率分别是出现的频率分别是 2%,3%,5%,7%,11%,13%,17%,19%,23%,求传输它们求传输它们的最佳前缀码。的最佳前缀码。解解 最佳前缀码为：最佳前缀码为：10，11，011，000,001，010101001010000010001440校园课件441校园课件442校园课件