怎样证明实数系的联系性_百度知道离散数学答案版(全) 25_离散数学答案-牛bb文章网
离散数学答案版(全) 25 离散数学答案
所属栏目：
命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法等证明方法。教学目的：1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 2．熟练掌握常用的基本等价式及其应用。3．熟练掌握（主）析/合取范式的求法及其应用。4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 5．熟练掌握形式演绎的方法。教学重点：1．命题的概念及判断 2．联结词，命题的翻译 3．主析（合）取范式的求法 4．逻辑推理教学难点：1．主析（合）取范式的求法 2．逻辑推理1.1命题及其表示法1.1.1
命题的概念数理逻辑将能够判断真假的陈述句称作命题。1.1.2
命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。1.2命题联结词（1） P↑P?（P∧P）?P； （2）（P↑Q）↑（P↑Q）?（P↑Q）? P∧Q； （3）（P↑P）↑（Q↑Q）?P↑Q? P∨Q。（1）P↓P?（P∨Q）?P； （2）（P↓Q）↓（P↓Q）?（P↓Q）?P∨Q； （3）（P↓P）↓（Q↓Q）?P↓Q?（P∨Q）?P∧Q。1.3
命题公式、翻译与解释1.3.1
命题公式定义
命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P?Q、 P?Q都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如，下面的符号串都是公式：（（（（P）∧Q）?R）∨S） （（P?Q）?（R∧S））
（P∨Q）∧R 以下符号串都不是公式：（（P∨Q）?（∧Q））
（∧Q） 1.3.2
命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。命题翻译时应注意下列事项： （1）确定所给句子是否为命题。（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命题联结词。例：假如上午不下雨，我去看电影，否则就在家里读书或看报。解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本例可表示为： （?P?Q）∧（P?（R∨S））。 1.3.3
命题公式的解释定义设P1，P2，…，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，…，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。例如，是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。1.4
真值表与等价公式1.4.1
真值表定义 将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。 构造真值表的方法如下：（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，Pn。
（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序写出各赋值，直到00…0为止），然后从低到高的顺序列出G的层次。（3）根据赋值依次计算各层次的真值并最终计算出G的真值。定义
设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式；（2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式；（3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。1.4.3
等价公式定义
设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为A?B。 性质定理设A、B、C是公式，则 （1）A?A（2）若A?B则B?A（3）若A?B且B?C则A?C定理
设A、B、C是公式，则下述等价公式成立： （1）双重否定律
??A?A（2）等幂律
A∨A?A （3）交换律
A∨B?B∨A （4）结合律
（A∧B）∧C?A∧（B∧C）（A∨B）∨C?A∨（B∨C）（5）分配律
（A∧B）∨C?（A∨C）∧（B∨C）（A∨B）∧C?（A∧C）∨（B∧C）（6）德?摩根律
?（A∨B）??A∧?B?（A∧B）??A∨?B（7）吸收律
A∨（A∧B）?A；A∧（A∨B）?A （8）零一律
A∧0?0 （9）同一律
A∧1?A （10）排中律
A∨?A?1 （11）矛盾律
A∧?A?0 （12）蕴涵等值式
A→B??A∨B （13）假言易位
A→B??B→?A（14）等价等值式
A?B?（A→B）∧（B→A）（15）等价否定等值式 A?B??A??B??B??A （16）归缪式
（A→B）∧（A→?B）??A1.4.4
置换规则定理（置换规则） 设?（A）是一个含有子公式A的命题公式，?（B）是用公式B置换了?（A）中的子公式A后得到的公式，如果A?B，那么?（A）??（B）。1.5
对偶与范式1.5.1
在仅含有联结词?、∧、∨的命题公式A中，将联结词∧换成∨，将∨换成∧，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。例：公式（?P∨Q）∧（P∨?Q） 的对偶式为：（?P∧Q）∨（P∧?Q）定理
设A和A*互为对偶式，P1，P2，…，Pn是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则（1）?A（P1，P2，…，Pn）?A*（?P1，?P2，…，?Pn） （2）A（?P1，?P2，…，?Pn）??A*（P1，P2，…，Pn）定理（对偶原理）设A、B是两个命题公式，若A?B，则A*?B*，其中A*、B*分别为A、B的对偶式。1.5.2
仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。定义
仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。1.5.3
主范式定义
在含有n个命题变元P1，P2，…，Pn的简单合取范式中，若每个命题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列），这样的简单合取式称为极小项。相应的，满足上述条件的简单析取式称为极大项。n个命题变元P1，P2，…，Pn的极小项用公式可表示为
Pi* ，极大项可表示为Pi*，其中，Pi*为Pi或?Pi（i=1，2，…，n）。定义
设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，…，Pn的一个极小项，则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。离散数学答案版(全) 25_离散数学答案定理
任意的命题公式都存在一个唯一的与之等价的主析取范式。用等值演算求主析取范式步骤如下：（1） 求G的析取范式G'；（2）若G中某个简单合取式m中没有出现某个命题变元Pi或其否定?Pi，则将m作如下等价变换：m?m∧（Pi∨?Pi）?（ m∧Pi）∨（m∧?Pi）（3）将重复出现的命题变元、矛盾式和重复出现的极小项都消去；（4）重复步骤（2）、（3），直到每一个简单合取式都为极小项；（5）将极小项按脚标由小到大的顺序排列，并用I表示。如m0∨m1∨m7可表示为I（0，1，7）。定义
设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，…，Pn的一个极大项，则称该合取范式为G的主合取范式。通常，主合取范式用?表示。重言式的主合取范式中不含任何极大项，用1表示。定理
任意的命题公式都存在一个唯一的与之等价的主合取范式。1.6
公式的蕴涵1.6.1
蕴涵的概念定义设G、H是两个公式，若G→H是永真式，则称G蕴涵H，记作G?H。蕴涵关系有如下性质：（1） 对于任意公式G，有G?G；（2）对任意公式G、H，若G?H且H?G，则G?H；（3） 若G?H且H?L，则G?L。广义的蕴涵概念定义
设G1，G2，…，Gn，H是公式，如果（G1∧G2∧…∧Gn）→H是永真式，则称G1，G2，…，Gn蕴涵H，又称H是G1，G2，…，Gn的逻辑结果，记作（G1∧G2∧…∧Gn）?H或（G1，G2，…，Gn）?H。1.6.2
基本蕴涵式（1）P∧Q?P；
（2）P∧Q?Q；（3）P?P∨Q；
(4) Q?P∨Q；（5）?P?（P→Q）；
（6）Q?（P→Q）；（7）?（P→Q）?P；
（8）?（P→Q）??Q；（9）P，P→Q?Q；
（10）?Q，P→Q??P；（11）?P，P∨Q?Q；
（12）P→Q，Q→R?P→R；（13）P∨Q，P→R，Q→R?R；
（14）P→Q，R→S?（P∧R）→（Q∧S）；（15）P，Q?P∧Q。1.7
其它联结词与最小联结词组1.7.1
其它联结词定义
设P、Q为命题公式，则复合命题P ?Q称为P和Q的不可兼析取，当且仅当P与Q的真值不相同时，P?Q的真值为1，否则P?Q的真值为假。c定义
设P、Q是两个命题公式，复合命题P??? Q称为命题P、Q的条件否cc定，当且仅当P的真值为1，Q的真值为0时，P?Q?? Q的真值为1，否则 P???的真值为0。1.7.2
最小联结词组定义 设S是一些联结词组成的非空集合，如果任何的命题公式都可以用仅包含S中的联结词的公式表示，则称S是联结词的全功能集。特别的，若S是联结词的全功能集且S的任何真子集都不是全功能集，则称S是最小全功能集，又称最小联结词组。定理
{?，∧，∨，→，?}是联结词的全功能集。定理
{?，∧，∨}是联结词的全功能集。定理
{?，∧}，{?、∨}，{?，→}是最小联结词组。定理
{↑}，{↓}是最小联结词组。1.8
命题逻辑推理理论1.8.1
命题逻辑推理理论定义
如果G1，G2，…，Gn蕴涵H，则称H能够由G1，G2，…，Gn有效推出，G1，G2，…，Gn称为H的前提，H称为G1，G2，…，Gn的有效结论。称（G1∧G2∧…∧Gn）→H是由前提G1，G2，…，Gn推结论H的推理的形式结构。1.8.2
推理规则下面给出推理中常用的推理规则。1．前提引入规则：可以在证明的任何时候引入前提；2．结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；3．置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。4．言推理规则：P，P→Q?Q5．附加规则：P?P∨Q；6．化简规则：P，Q?P；7．拒取式规则：?Q，P→Q??P；8．假言三段论规则：P→Q，Q→R?P→R；9．析取三段论规则：?P，P∨Q?Q；10.构造性二难规则：P∨Q，P→R，Q→R?R；11.合取引入规则：P，Q?P∧Q1.8.3
推理常用方法1.直接证法直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。
构造下列推理的证明。前提：P∨Q，P→R，Q→S
结论：S∨R证明（1）P∨Q
前提引入规则（2）P→R
前提引入规则（3）Q→S
前提引入规则（4）S∨R
（1）（2）（3）构造性二难规则2．间接证法间接证法主要有如下两种情况。（1）附加前提证明法 有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：（G1∧G2∧…∧Gn）?（R→C）设（G1∧G2∧…∧Gn）为S，则上述推理可表示为证明S?（R→C），即证明S→（R→C）为永真式。用附加前提证明法证明下面推理。前提：P→（Q→R），?S∨P，Q
结论：S→R证明：（1）?S∨P
前提引入规则（2）S
附加前提引入规则（3）P
（1）（2）析取三段论规则（4）P→（Q→R）
前提引入规则（5）Q→R
（3）（4）假言推理规则（6）Q
前提引入规则（7）R
（5）（6）假言推理规则2）归缪法定义
设G1，G2，…，Gn是n个命题公式，如果G1∧G2∧…∧Gn是可满足式，则称G1，G2，…，Gn是相容的。否则（即G1∧G2∧…∧Gn是矛盾式）称G1，G2，…，Gn是不相容的。例 用归缪法证明。前提：P∨Q，P→R，Q→S
结论：S∨R证明（1）?（S∨R）
附加前提引入规则（2）?S∧?R
（1）置换规则（3）?S
（2）化简规则（4）?R
（2）化简规则（5）Q→S
前提引入规则（6）?Q∨S
（5）置换规则（7）?Q
（3）（6）析取三段论（8）P∨Q
前提引入规则（9）P
（7）（8）析取三段论规则（10）P→R
前提引入规则（11）?P∨R
（10）置换规则（12）R
（9）（11）析取三段论规则（13）?R∧R
（4）（12）合取引入规则第二章 谓词逻辑本章学习目标命题逻辑中原子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，本章引入谓词逻辑。学习关于谓词逻辑的相关概念和定理，解决实际问题。内容：谓词、量词及谓词公式等概念，基本等价式、永真蕴涵式及谓词演算的形式推理方法，谓词范式的概念教学目的：1．深刻理解个体、谓词、量词的概念。2．深刻理解原子、公式、解释的概念。3．掌握用解释的方法证明等价式和蕴涵式。4．熟练掌握谓词演算的形式推理方法。教学重点：1．个体、谓词、量词的概念2．用解释的方法证明等价式和蕴涵式3．谓词演算的形式推理方法教学难点：1．解释的方法证明等价式和蕴涵式2．谓词演算的形式推理方法2.1
谓词逻辑命题的符号化1．个体词 ：个体词是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体个体常项或个体常元 ：个体变项或个体变元 ：个体域或论域 ：2．谓词：用来刻画个体词的性质或个体词之间关系的词一般来说，“x是A”类型的命题可以用A（x）表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“…大于…”谓词。我们把A（x）称为一元谓词,B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。例2.1
将下列命题在谓词逻辑中符号化，并讨论它们的真值：（1）只有4是素数，8才是素数。（2）如果2小于3，则8小于7。解（1）设谓词G（x）：x是素数，a：4，b：8；（1）中的题符号化为谓词的蕴涵式：G（a）→G（b）由于此蕴涵式的前件为假，所以（1）中的命题为真。（2）设谓词H（x，y）：x小于y，a：2，b：3，c：8，d：7（2）中的命题符号化为谓词的蕴涵式：H（a，b）→H（c，d）由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。例 2.2
在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。（2）有的人天生就近视。其中：（a）个体域D1为人类集合。（b）个体域D2为全总个体域。解（a）令F（x）：x要死的；G（x）：x天生就近视。（1）在个体域D1中除人外，没有其他的事物，因而（1）可符号化为：?x F（x）（2）在个体域D1中有些人是天生就近视，因而（2）可符号化为谓词的蕴涵式：??x G（x）（b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令M（x）：x是人。在D2中，（1）、（2）可分别描述如下：对于宇宙间的一切事物，如果事物是人，则他是要死的。（2） 在宇宙间存在着天生就近视的人。将（1）、（2）分别符号化为：（1）
?x（M（x）?F（x））（2）
?x（M（x）?G（x））在个体域D1、D2中命题（1）、（2）都是真命题。例2.3
在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6 =（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。（b）个体域D2为实数集合。解
（a）令F（x）：x2-5x+6 =（x-2）（x-3）；G（x）：x+1=0。（1）可符号化为：?x F(x)（2）可符号化为：?x G（x）在个体域D1中命题（1）为真命题，命题（2）为假命题。（b）在个体域D2中（1）、（2）符号化分别为离散数学答案版(全) 25_离散数学答案（1）
?x F（x）（2）
?x G（x）在个体域D2中命题（1）、（2）都是真命题。例2.4
将下列命题符号化，并指出真值情况。（1）没有人登上过月球。（2）所有人的头发未必都是黑色的。解
个体域为全总个体域，令M（x）：x是人。（1）令F（x）：x登上过月球。命题（1）符号化为：） ??x（M（x）∧F（x）设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）∧F（a）为真，故命题（1）为假。（2）令H（x）：x的头发是黑色的。命题（2）可符号化为：??x（M（x）?H（x））我们知道有的人头发是褐色的，所以?x（M（x）?H（x））为假，故命题（2）为真。例2.5 将下列命题符号化。（1）猫比老鼠跑得快。（2）有的猫比所有老鼠跑得快。（3）并不是所有的猫比老鼠跑得快。（4）不存在跑得同样快的两只猫。解
设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。这4个命题分别符号化为：（1）?x?y（C（x）∧M（y）?Q（x，y））；（2）?x（C（x）∧?y（M（y）?Q（x，y）））；（3）??x ?y（C（x）∧M（y）?Q（x，y））；（4）??x? y（C（x）∧C（y）∧L（x，y））2.2
谓词逻辑公式与解释2.2.1
谓词逻辑的合式公式定义2.1
设P（x1，x2，…，xn）是n元谓词公式，其中，x1x2，…，xn是个体变项，则称P（x1，x2，…，xn）为谓词演算的原子公式。定义2.2
谓词演算的合式公式定义如下：（1）原子公式是合式公式；（2）若A是合式公式，则（A）也是合式公式；（3）若A，B是合式公式，则（A∧B）、（A∨B）、（A→B）、（A?B）是合式公式；（4）若A是合式公式，则?x A、?x A是合式公式；（5）只有有限次地应用（1）－（4）构成的符号串才是合式公式。例2.5
在谓词逻辑中将下列命题符号化。（1）不存在最大的数。（2）计算机系的学生都要学离散数学。解
取个体域为全总个体域。（1）令F（x）：x是数，L（x，y）：x大于y；则命题（1）符号化为?x（F（x）∧ ?y（F（y）→ L（x，y）））（2）令C（x）：x是计算机系的学生，G（x）：x要学离散数学;则命题（2）可符号化为：
?x（C（x）→ G（x））例2.6
将下列命题符号化。（1）尽管有人聪明，但并非所有人都聪明。（2）这只大红书柜摆满了那些古书。解
（1）令C（x）：x聪明；M（x）：x是人。则命题（1）可符号化为）∧?x（M（x）→C（x）） ?x（M（x）∧C（x）（2）令F（x，y）：x摆满了y；R（x）：x是大红书柜；Q（x）:x是古书；a：这只；b：那些。则命题（2）可符号化为R（a）∧Q（b）∧F（a，b）2.2.2
约束变元与自由变元1．约束变元与自由变元的概念定义 2.3
在公式?x F（x）和?x F（x）中，称x为指导变元，F（x ）为相应量词的辖域或作用域。在?x和?x的辖域中，x的所有出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自由出现。例2.7
指出下列各式量词的辖域及变元的约束情况：（1）?x（F（x，y）→ G（x，z））（2）?x（P（x）→?y R（x，y））（3）?x（F（x）→ G（y））→ ?y（H（x）∧M（x，y，z））解 （1）对于?x的辖域是A=（F（x，y）→ G（x，z）），在A中，x是约束出现的，而且约束出现两次，y，z均为自由出现，而且各自由出现一次。（2）对于?x的辖域是（P（x）→?y R（x，y）），?y的辖域是R（x，y），x，y均是约束出现的。（3）对于?x的辖域是（F（x）→ G（y）），其中x是约束出现的，而y是自由出现的。对?y的辖域是（H（x）∧M（x，y，z）），其中y是约束出现的，而x，z是自由出现的。在整个公式中，x约束出现一次，自由出现两次，y约束出现一次，自由出现一次，z仅自由出现一次。2．约束变元的换名与自由变元的代入例2.8
对公式?x（P（x）→ R（x，y））∧Q（x，y）进行换名。解
对约束变元x换名为t后为?t（P（t）→ R（t，y））∧Q（x，y）同理，对公式中的自由变元也可以更改，这种更改称作代入。自由变元的代入规则是：（1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。（2）用以代入的变元与原公式中所有变元的名称都不能相同。例2.9
对公式?x（F（x）→ G（x，y））∧?y H（y）代入。解
对y实施代入，经过代入后原公式为）∧ ?y H（y） ?x（F（x）→ G（x，t）另外，量词作用域中的约束变元，当论域的元素是有限时，个体变元的所有可能的取代是可以枚举的。设论域元素为a1，a2，…，an，则
?x A（x）? A（a1）∧A（a2）∧…∧A（an）?x A（x）? A（a1）∨A（a2）∨…∨A（an）。2.2.3
谓词逻辑公式的解释定义2.4
谓词逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：（1）对每一个常项符号指定D中一个元素。（2）对每一个n元函数符号，指定一个函数。（3）对每一个n元谓词符号，指定一个谓词。显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下有一个真值，记作TI（G）。例2.10
指出下面公式在解释I下的真值。（1）G=?x（P（f（x））∧Q（x，f（a）））；（2）H=?x（P（x）∧Q（x，a））。给出如下的解释I：D={2，3}；a：2；f（2）：3、f（3）：2；P（2）：0、P（3）：1；Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1；解
（1）TI（G）= TI（（P（f（2））∧Q（2，f（2）））∨（P（f（3））∧Q（3，f（2））））= TI（（P（3）∧Q（2，3））∨（P（2）∧Q（3，3））= （1∧1）∨（0∧1）= 1（2）TI（H）= TI（P（2）∧Q（2，2）∧P（3）∧Q（3，2））=0∧1∧1∧0=0定义2.5
若存在解释I，使得G在解释I下取值为真，则称公式G为可满足的，简称I满足G。定义2.6
若不存在解释I，使得I满足G，则称公式G为永假式（或矛盾式）。若G的所有解释I都满足G，则称公式G为永真式（或重言式）。2.3
谓词逻辑约束公式的等价与蕴涵2.3.1
谓词逻辑的等价公式定义2.7
设A、B是命题逻辑中的任意两个公式，设它们有共同的个体域E，若对任意的解释I都有TI（A）= TI（B），则称公式A、B在E上是等价的，记作A?B。定理1
设A（x）是谓词公式，有关量词否定的两个等价公式：（1）?x A（x）??xA（x）（2）?x A（x）??xA（x）证明
（1）设个体域是有限的为：D={ a1，a2，…，an}，则有?x A（x）?（A（a1）∧A（a2）∧…∧A（an））） ?A（a1）∨A（a2）∨…∨A（an）??xA（x）（2）设个体域是有限的为：D={ a1，a2，…，an}，则有?x A（x）?（A（a1）∨ A（a2）∨…∨A（an））? A（a1）∧ A（a2）∧…∧A（an）??xA（x）定理2
设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有（1）?x（A（x）∨B）??x A（x）∨B（2）?x（A（x）∧B）??x A（x）∧B（3）?x（A（x）→ B）??x A（x）→ B（4）?x（B→A（x））?B→ ?x A（x）（5）?x（A（x）∨B）? ?x A（x）∨B（6）?x（A（x）∧B）??x A（x）∧B（7）?x（A（x）→ B）??x A（x）→ B（8）?x（B→A（x））?B→?x A（x）证明
（1）设D是个体域，I为任意解释，即用确定的命题及确定的个体代替出现在?x（A（x）∨B）和?x A（x）∨B中的命题变元和个体变元，于是得到两个命题，若对?x（A（x）∨B）代替之后所得命题的真值为真，此时必有A（x）∨B的真值为真；因而A（x）真值为真或B的真值为真，若B的真值为真，则?x A（x）∨B的真值为真；若B的真值为假，则必有对D中任意x都使得A（x）的真值为真，所以?x（A（x）∨B）为真，从而?x A（x）∨B为真。若对?x（A（x）∨B）代替之后所得命题的真值为假，则A（x）和B的真值必为假，因此?x A（x）∨B的真值为假；所以?x（A（x）∨B）为假，有?x A（x）∨B为假。（2）、（5）和（6）证明与（1）类似，证明过程略。（3）?x（A（x）→ B）??x（?A（x）∨B）??x?A（x）∨ B??x? A（x）∨B??x A（x）→ B（4）、（7）、（8）证明与（3）类似，证明过程略。定理3
设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有：（1）?x（A（x）∧B（x））??x A（x）∧?x B（x）（2）?x（A（x）∨B（x））??x A（x）∨?x B（x）证明
（1）设D是任一个体域，若?x（A（x）∧B（x））的真值为真，则对任意a?D，有A（a）和B（a）同时为真，即?x A（x）为真、?x B（x）为真，从而?x A（x）∧?x B（x）为真。若?x（A（x）∧B（x））的真值为假，则对任意a?D，有A（a）和B（a）不能同时为真，即?x A（x）和 ?x B（x）的真值不能同时为真，从而?x A（x）∧?x B（x）的真值为假。综上所述 ?x（A（x）∧B（x））??x A（x）∧?x B（x）（2）设D是任一个体域，若?x（A（x）∨B（x））的真值为真,则存在a?D，使得A（a）∨B（a）为真，即A（a）为真或B（a）为真，即?x A（x）为真或?x B（x）为真，从而?x A（x）∨?x B（x）为真。若?x（A（x）∨B（x））的真值为假，则存在a?D，使得A（a）∨B（a）为假，此时，A（a）为假，B（a）为假，从而?x A（x）∨?x B（x）的真值为假。综上所述 ?x（A（x）∨B（x））??x A（x）∨?x B（x）例2.11
证明下列各等价式（1）?x（A（x）∧B（x））??x（A（x）→B（x））（2）?x（A（x）→ B（x））??x（A（x）∧B（x））证明
（1）?x（A（x）∧B（x））??x （A（x）∧B（x））??x（A（x）∨B（x））? ?x（A（x）→B（x））（2）?x（A（x）→ B（x））??x （A（x）→ B（x））??x （A（x）∨B（x））??x（A（x）∧B（x））2.3.2
谓词逻辑的蕴涵公式定义2.8
设A、B是命题逻辑中的任意两个公式，若A→B是永真式，则称公式A蕴涵公式B，记作A?B。定理4
下列蕴涵式成立（1）?x A（x）∨?x B（x）??x（A（x）∨B（x））（2）?x（A（x）∧B（x））??x A（x）∧?x B（x）（3）?x（A（x）→ B（x））??x A（x）→ ?x B（x）（4）?x（A（x）→ B（x））??x A（x）→ ?x B（x）（5）?x A（x）→ ?x B（x）??x（A（x）→ B（x））证明：（1）设?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））成立。（2）设个体域为D，在解释I下?x（A（x）∧B（x））的真值为真，即存在a?D使得A（a）∧B（a）为真，从而A（a）为真，B（a）为真，故有?x A（x）、?x B（x）均为真，所以，蕴涵式?x（A（x）∧B（x））??x A（x）∧?x B（x）成立。（3）设个体域为D，在解释I下?x A（x）→ ?x B（x）的真值为假,即存在a?D使得A（a）→ B（a）为假，所以蕴涵式?x（A（x）→ B（x））??x A（x）→ ?x B（x）成立。离散数学答案版(全) 25_离散数学答案（4）?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））??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）（5）?x A（x）→ ?x B（x）???x A（x）∨?x B（x）??x ?A（x）∨?x B（x）??x（?A（x）∨B（x））??x（A（x）→ B（x））2.3.3
多个量词的使用定义2.9
设谓词公式G，不包含联结词→，?。把G中出现的联结词?，?互换；命题常量T，F互换；量词?，?互换之后得到的公式称为G的对偶公式，记作G*。定理5（对偶定理）
设A、B是任意两个公式并且不包含联结词→，?。若A?B，则A*?B*。2.4
前束范式定义2.10
一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。定理6
对任意一个谓词公式都可以化为与它等价的前束范式。证明
首先利用等价公式将谓词公式中的联结词→，?去掉。其次利用量词的转化律将量词前面的否定深入到谓词前面，在利用改名和代入规则以及量词辖域扩张的公式将量词移到全式的最前面，这样便得到前束范式。例2.12
求下列谓词公式的前束范式。（1）?x ?y（?z A（x，z）∧A（x，z））→?t B（x，y，t）解
（1）?x ?y（?z A（x，z）∧A（x，z））→ ?t B（x，y，t）??x ?y（?z A（x，z）∧A（x，z））∨?t B（x，y，t）??x ?y（?zA（x，z）∨A（x，z））∨?t B（x，y，t）（量词转化）??x ?y（?wA（x，w）∨A（x，z））∨?t B（u，v，t）（改名及代入规则）??x ?y ?w ?t（A（x，w）∨A（x，z）∨B（u，v，t））（量词辖域扩张）（2）?x（?y P（x，y）→ ?x ?y（Q（x，y）∧?y（P（y，x）→Q（x，y））））
（2）?x（?y P（x，y）→ ?x ?y（Q（x，y）∧?y（P（y，x）→Q（x，y））））??x（?y P（x，y）∨?x ?y（Q（x，y）∧?y（P（y，x）→Q（x，y））））
??x（?y P（x，y）∧?x?y（Q（x，y）∨?y（P（y，x）∧ Q（x，y））））
（量词转化、德?摩根定律））））
??x（?y P（x，y）∧?x ?y（Q（x，y）∨?z（P（z，x）∧Q（x，z）（改名原则））））
??x（?y P（x，y）∧?x ?y ?z（Q（x，y）∨（P（z，x）∧Q（x，z）（量词辖域扩张）??x（?y P（x，y）∧?u ?v ?z（Q（u，v）∨（P（z，u）∧Q（u，z））））（改名原则）??x ?y ?u ?v ?z （P（x，y）∧（? Q（u，v）∨（P（z，u）∧Q（u，z））））
（量词辖域扩张）定义2.11
若一个谓词公式，具有如下形式，则称该公式为前束析取范式。
若一个谓词公式，具有如下形式，则称该公式为前束合取范式。
任意谓词公式都可以化为与其等价的前束析取范式和前束合取范式。2.5
谓词演算的推理理论1．全称指定规则（简称US规则）这条规则有下面两种形式：(1)?x P（x）?P（y）(2)?x P（x）?P（c）其中，P是谓词，（1）中y为任意不在P（x）中约束出现的个体变元；（2）中c为个体域中的任意一个个体常元。2．存在指定规则（简称ES规则）?x P（x）?P（c）其中，c为个体域中使P成立的特定个体常元。必须注意，应用存在指定规则，其指定的个体c不是任意的。3．全称推广规则（简称UG规则）P（y）??x P（x）4．存在推广规则（简称EG规则）P（c）??x P（x）其中，c为个体域中的个体常元，这个规则比较明显，对于某些个体c，若P（c）成立，则个体域中必有?x P（x）。例2.13
证明 ?x（M（x）→ D（x））∧M（s）?D（s）这是著名的苏格拉底三段论的论证。其中
M（x）：x是一个人。D（x）：x是要死的。s：苏格拉底。证明
（1）?x（M（x）→ D（x））
P（2）M（s）→ D（s）
US（1）（3）M（s）
P（4）D（s）
T（2）（3）I例 2.14
判断下列的推理过程是否正确。（1）?x ?y G（x，y）
P（2）?y G（z，y）
US（1）（3）G（z，c）
ES（2）（4）?x G（x，c）
UG（3）（5）?y ?x G（x，y）
这个推理过程是错误的，因为从它可以得出结论：?x ?y G（x，y）??y ?x G（x，y）从前面的学习中我们知道这个式子不成立。它的推导错误出现在第（3）步。?xG（x，y）的含义是：对于任意的一个x，存在着与它对应的y，使得G（x，y）?y成立。但是，对?y G（z，y）利用ES规则消去存在变量后得到G（z，c）的含义却是：对于任意个体z，有同一个体c，使得G（z，c）成立。显然，G（z，c）不是?y G（z，y）的有效结论。因此，使用ES规则?x P（x）?P（c）消去存在量词的条件是:P（x）中除x外没有其他自由出现的个体变元。例2.15
证明：?x（C（x）→（W（x）∧R（x）））∧?x C（x）∧Q（x）? ?x Q（x）∧?x Q（x）证明
（1）?x C（x）
P（2）C（y）
ES（1）（3）?x（C（x）→（W（x）∧R（x）））
P（4）C（y）→（W（y）∧R（y））
US（3）（5）W（y）∧R（y）
T（2）（4）I（6）R（y）
T（5）I（7）?x R（x）
EG（6）（8）Q（x）
P（9）?x Q（x）
EG（8）（10）?x Q（x）∧?x Q（x）
T（7）（9）I例2.16
证明：?x（A（x）∨B（x））??x A（x）∨?x B（x）证明
（1）?x（A（x）∨B（x））
P（2）A（y）∨B（y）
US（1）（3）?x（A（x）∨B（x））
EG（2）（4）?x A（x）∨?x B（x）
T（3）E例2.17
给定前提：）） ?x（P（x）∧?y（Q（y）→ R（x，y）?x（P（x）→?y（S（y）→R（x，y）））证明下列结论：?x（Q（x）→S（x））证明：（1）?x（P（x）∧?y（Q（y）→ R（x，y）））
P（2）P（a）∧?y（Q（y）→ R（a，y））
ES（1）（3）P（a）
T（2）（4）?x（P（x）→ ?y（S（y）→R（x，y）））
P（5）P（a）→ ?y（S（y）→R（a，y））
US（4）（6）?y（S（y）→R（a，y））
T（3）（5）I（7）?y（Q（y）→ R（a，y））
T（2）I（8）S（z）→R（a，z）
US（6）（9）Q（z）→R（a，z）
US（7）（10）R（a，z）→S（z）
T（8）E（11）Q（z）→?S（z）
T（9）（10）I（12）?x（Q（x）→S（x））
UG（11）例2.18
符号化下面的命题“所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，所以任何虚数既不是有理数也不是无理数”，并推证其结论。证明
设：P（x）：x是有理数。Q（x）：x是无理数。R（x）：x是实数。S（x）：x是虚数。本题符号化为：?x（P（x）→ R（x）），?x（Q（x）→ R（x）），?x（S（x）→R（x））??x（S（x）→P（x）?R（x））（1）?x（S（x）→R（x））
P（2）S（y）→R（y）
US（1）（3）?x（P（x）→ R（x））
P（4）P（y）→ R（y）
US（3）（5）R（y）→P（y）
T（4）E（6）?x（Q（x）→ R（x））
P（7）Q（y）→ R（y）
US（6）（8）R（y）→Q（y）
T（7）E（9）S（y）→P（y）
T（2）（5）I（10）S（y）→Q（y）
T（2）（8）I（11）（S（y）→P（y））∧（S（y）→Q（y）
T（9）（10）I（12）（S（y）∨P（y））∧（?S（y）∨Q（y））
T（11）E（13）S（y）∨（P（y）∧Q（y））
T（12）E（14）S（y）→（P（y）∧Q（y））
T（13）E（15）?x（S（x）→P（x）∧R（x））
UG（14）第三章
集合本章学习目标：集合是一般数学及离散数学中的基本概念，几乎与现代数学的各个分支都有密切联系，并且渗透到很多科技领域。本章主要介绍集合的基本知识，通过本章学习，读者应该掌握以下内容：1. 集合的概念及表示方法2.子集、空集、全集、补集、幂集等概念3. 集合的基本运算：交、并、补和对称差4.集合的包含排斥原理内容：集合的概念及运算、幂集及笛卡尔积的运算、容斥原理的应用教学目的：1．深刻理解子集、空集、全集、集合表示、集合相等、幂集等基本概念。2．熟练掌握集合的并、交、补、运算；能用文氏图表示集合运算。3．熟练掌握集合运算的基本定律，能熟练地应用这些定律证明集合恒等式。4．深刻理解序偶与笛卡尔积的概念；了解递归定义的概念；理解容斥原理。 教学重点：1．集合的概念及表示方法2．子集、空集、全集、补集、幂集等概念3．集合的基本运算：交、并、补和对称差4．集合的包含排斥原理教学难点：集合的基本运算：交、并、补和对称差集合的包含排斥原理3.1集合的概念与表示3.1.1
集合的基本概念3.1.2
集合的表示1．列举法2．描述法3.文氏图法3.2
集合之间的关系定义3.1
如果集合A中的每一个元素都是集合B中的元素，则称A是B的子集，也可以说A包含于B，或者B包含A，这种关系写作A?B
B?A,如果A不是B的子集，即在A中至少有一个元素不属于B时，称B不包含A，记作B?A
A?B离散数学答案版(全) 25_离散数学答案定义3.2
如果两个集合A和B的元素完全相同，则称这两个集合相等，记作A＝B。例如：A＝｛1，2，3，4｝
B＝｛3，1，4，2｝
C＝｛x|x是英文字母且x是元音｝
D＝｛a，e，i，o，u｝显然有A＝B，C＝D定理3.1
集合A和集合B相等的充分必要条件是A?B且B?A。定义3.3
如果集合A是集合B的子集，但A和B不相等，也就是说在B中至少有一个元素不属于A，则称A是B的真子集，记作A?B
B?A例如：集合A＝｛1，2｝，B＝｛1，2，3｝，那么A是B的真子集定义3.4
若集合U包含我们所讨论的每一个集合，则称U是所讨论问题的完全集，简称全集。定义3.5
设A是有限集，由A的所有子集作为元素而构成的集合称为A的幂集，记作ρ(A)，即ρ(A)＝｛X|X?A｝。在A的所有子集中，A和?这两个子集又叫平凡子集。例如：A＝｛1，2，3｝，则
ρ(A)＝｛?，｛1｝，｛2｝，｛3｝，｛1，2｝，｛1，3｝，｛2，3｝，｛1，2，3｝｝定理3.2
设A是有限集，|A|=n，则A的幂集ρ(A)的基为2n。证明：由排列组合知： 0n?1n
?(A)?cn?c1n???cn?cn又由二项式定理知：0n?1n
cn?c1?cn?2n n???cn所以可得：
?(A)?2n3.3
集合的运算3.3.1 集合的并运算定义3.6
任意两个集合A、B的并，记作A∪B，它也是一个集合，由所有属于A或者属于B的元素合并在一起而构成的，即A∪B＝｛x | x?A或x?B｝例如，A＝｛a，b，c｝，B＝｛a，b，c，d，e｝，则A∪B＝｛a，b，c，d，e｝又如，A＝｛1，2，3，4，5｝，B＝｛1，3，5，7，9｝，则A∪B＝｛1，2，3，4，5，7，9｝用文氏图表示集合之间的并运算：用平面上的矩形表示全集U。用矩形内的圆表示U中的任一集合。图中表示了集合A和集合B的并集。阴影部分就是A∪B。由集合并运算的定义可知，并运算具有以下性质：（1）幂等律：A∪A＝A
（2）同一律：A∪?＝A（3）零律：A∪U＝U
（4）结合律：(A∪B)∪C＝A∪(B∪C)（5）交换律：A∪B＝B∪A3.3.2
集合的交运算定义3.7
任意两个集合A、B的交记作A∩B，它也是一个集合，由所有既属于A又属于B的元素构成，即A∩B ＝｛x | x?A且x?B｝例如，A＝｛a，b，c｝，B＝｛b，c，d，e｝，则A∩B＝｛b，c｝又如，A＝｛1，2，3，4，5｝，B＝｛1，3，5，7，9｝，则A∩B＝｛1，3，5｝
集合的交运算的文氏图表示，见图，其中阴影部分就是A∩B。由集合交运算的定义可知，交运算有以下性质：（1）幂等律：A∩A＝A（2）同一律：A∩U＝A（3）零律：A∩?＝?（4）结合律：(A∩B)∩C＝A∩(B∩C)（5）交换律：A∩B＝B∩A定理3.3
设A，B，C是三个集合，则下列分配律成立：A∩（B∪C）＝（A∩B）∪（A∩C）A∪（B∩C）＝（A∪B）∩（A∪C）定理3.4
设A，B为两个集合，则下列关系式成立：A∪（A∩B）＝A
A∩（A∪B）＝A这个定理称为吸收律，可以用文氏图验证3.3.3
集合的补定义3.8
设A、B是两个集合，A-B也是一个集合。它是由属于集合A但不属于集合B的所有元素组成的。A-B称为集合B关于A的补集(或相对补)。即Ａ-B＝｛x|x?Ａ且x?B｝A-B也称为集合A和B的差集。例如，Ａ＝｛a，b，c｝，B＝｛a，b｝，则Ａ-B＝｛c｝又如，Ａ＝｛a，b，c，d｝，B＝｛a，b，e，f｝，则Ａ-B＝｛c，d｝定义3.9
设U是全集，A是U的一个子集，称U-A为A关于全集的补集，也叫做A的绝对补集，简称为补集。记作~A。即U-Ａ＝｛x|x?Ｕ且x?Ａ｝例如，U＝｛x | x是江西理工大学的学生｝，A＝｛x | x是江西理工大学的女学生｝，则
~A＝｛x | x是江西理工大学的男学生｝集合的补运算有以下性质（1）双重否定律：~（~A）＝A（2）摩根律：~?＝U（3）摩根律：~U＝?（4）矛盾律：A∩（~A）＝?（5）排中律：A∪（~A）＝U为了简单，约定A∩（~B）表示为A∩~B，A∪（~B）表示为 A∪~B。定理3.5
设A、B是两个集合，则下列关系式成立：~（A∪B）＝~A∩~B~（A∩B）＝~A∪~B这个定理称为德摩根定律。可以用文氏图验证定理3.6
设A、B、C是任意三个集合，则下列关系式成立：A-B＝A∩~BA-B＝A-（A∩B）定理可由差运算的定义直接得到。3.3.4
集合的对称差定义3.10
设A、B是两个集合，集合A和B的对称差记作A?B，它是一个集合，其元素或属于A，或属于B，但不能既属于A又属于B。即A?B＝(A∪B)-(A∩B)例如，A＝｛a，b，c，d｝，B＝｛a，c，e，f，g｝那么A?B＝｛b，e，d，f，g｝集合的对称差的文氏图表示由对称差的定义易得下列性质：（1）A?A＝?（2）A??＝A（3）A?Ｕ＝~Ａ（4）A?B＝B?A（5）（A?B）?C＝A?（B?C）（6）A?B＝(A-B)∪(B-A)3.4
包含排斥原理定理3.7
设A、B为有限集合，|A|、|B|为其基数，则|A∪B|＝|A|+|B|-|A∩B|这个结论称作包含排斥原理。例3.1
假设某班有20名学生，其中有10人英语成绩为优，有8人数学成绩为优，又知有6人英语和数学成绩都为优。问两门课都不为优的学生有几名？解
设英语成绩是优的学生组成的集合是A，数学成绩是优的学生组成的集合是B，因此两门课成绩都是优的学生组成的集合是A∩B。由题意可知|A|＝10
|A∩B|＝6由包含排斥原理可得：|A∪B|＝|A|+|B|-|A∩B|＝10+8-6 = 12所以，两门课都不是优的学生数为：20-|A∪B|＝8。第四章 关系本章学习目标：在上一章讨论了集合及集合的运算，在这一章中我们将要研究集合内元素间的关系，这就是“关系”。关系是一个很重要的数学基本概念，它在计算机科学中的许多方面如数据结构、数据库、情报检索、算法分析等都有很多应用。本章主要讨论二元关系理论。通过本章学习，读者应该掌握以下内容：1.关系的表示2.关系的性质和运算3.等价关系和集合的划分4.偏序关系内容：二元关系的概念及表示、特性，乘积、逆及闭包运算，集合的划分，等价、偏序及相容关系教学目的：1．深刻理解关系的基本概念；掌握关系矩阵和关系图。2．熟练掌握关系的性质和判别方法。3．理解复合关系和逆关系的概念并熟练掌握其求法。4．深刻理解关系的自反、对称、传递闭包的概念并熟练掌握其求法。5．熟练掌握等价关系的判定与相关等价类的求法。6．深刻理解偏序关系的判定、偏序集的概念并熟练掌握其哈斯图表示法。 了解全序集、良序集及相容关系的概念。教学重点：1．关系的基本概念；关系矩阵和关系图；2．复合关系和逆关系的概念及求法；3．关系的自反、对称、传递闭包的概念及其求法。4．等价关系的判定与相关等价类的求法教学难点：1．关系的自反、对称、传递闭包的概念及其求法。2．等价关系的判定与相关等价类的求法4.1
序偶与笛卡儿积4.1.1
有序n元组定义4.1
由两个固定次序的个体x，y组成的序列称为序偶，记为&x，y&，其中x，y分别称为序偶的第一、二分量（或称第一、二元素）。定义4.2
两序偶&a，b&，&c，d&是相等的，当且仅当a=c，b=d；记作&a，b&=&c，d&。4.1.2
笛卡儿积的概念离散数学答案版(全) 25_离散数学答案定义4.3
给定两个集合A和B，如果序偶的第一个分量是A中的一个元素，第二个分量是B中的一个元素，则所有这种序偶的集合称为集合A和B的笛卡儿积，简称为卡氏积，记为A×B，即A×B={&x，y&x?A∧y?B}。例4.1（1）A={a，b}，B={c，d}，求A×B。（2）A={a，b}，B={c，d}，求B×A。（3）A={a，b}，B={1，2}，C={c}，求（A×B）×C和A×（B×C）。解（1）A×B={a，b}×{c，d}={&a，c&，&a，d&，&b，c&，&b，d&}。（2）B×A={c，d}×{a，b}={&c，a&，&c，b&，&d，a&，&d，b&}。（3）（A×B）={a，b}×{1，2}={&a，1&，&a，2&，&b，1&，&b，2&}。（A×B）×C={&&a，1&，c&，&&a，2&，c&，&&b，1&，c&，&&b，2&，c&}
={&a，1，c&，&a，2，c&，&b，1，c&，&b，2，c&}。B×C={1，2}×{c}={&1，c&，&2，c&}。A×（B×C）={&a，&1，c&&，&a，&2，c&&，&b，&1，c&&， &b，&2，c&&}。
笛卡儿积的性质定理4.1
设A，B，C为任意3个集合，则有（1）A×（B∪C）=（A×B）∪（A×C）（2）A×（B∩C）=（A×B）∩（A×C）（3）（A∪B）×C=（A×C）∪（B×C）（4）（A∩B）×C=（A×C）∩（B×C）定理4.2
设A，B，C为任意3个集合，且C??，则有A?B ?（A×C ? B×C）?（C×A ? C×B）定理4.3
设A，B，C，D为四个非空集合，则A×B?C×D的充分必要条件是：
A?C且B?D。反之，如果A?C且B?D，设任意x?C和y?B，有&x，y&?A×B ? x?A∧y?B?x?C∧y?D? x?C∧y?D? &x，y&?C×D所以，A×B?C×D。4.2
二元关系及其表示4.2.1
二元关系的概念定义4.4
设A，B是两个集合，R是笛卡儿积A×B的任一子集，则称R为从A到B的一个二元关系，简称关系。特别当A=B时，则称R为A上的二元关系（或A上的关系）。定义4.5
设R是二元关系，由&x，y&?R的所有x组成的集合称为R的定义域，记作D（R），即D（R）={x??y（y?B∧&x，y&?R）}。由&x，y&?R的所有y组成的集合称为R的值域，记作R（R），即R（R）={y??x（x?A∧&x，y&?R）}。例4.2
设A={a，b，c，d，e}，B={1，2，3}，R={&a，2&，&b，3&，&c，2&}，求R的定义域和值域。解
D（R）={a，b，c}
， R（R）={2，3}。例4.3
设A={1，3，5，7}，R是A上的二元关系，当a，b?A且a&b时，&a，b&?R，求R和它的定义域和值域。解
R={&1，3&，&1，5&，&1，7&，&3，5&，&3，7&，&5，7&}D（R）={1，3，5}，R（R）={3，5，7}。定义4.6
设IA为集合A上的二元关系，且满足IA={&x，x&|x?A}，则称IA为集合A上的恒等关系。4.2.2
二元关系的表示1．关系矩阵表示法设给定集合A={a1，a2，…，an}，集合B={b1，b2，…，bm}，R为从A到B的一个二元关系，构造一个n×m矩阵。用集合A的元素标注矩阵的行，用集合B的元素标注矩阵的列，对于a?A和b?B，若&a，b&?R，则在行a和列b交叉处标1，否则标0。这样得到的矩阵称为R的关系矩阵。2. 关系图表示法有限集的二元关系可以用有向图来表示，设集合A={a1，a2，…，an}，集合B={b1，b2，…，bm}，R为从A到B的一个二元关系，首先在平面上作出n个结点分别记作a1，a2，…，an，然后另外作出m个结点分别记作b1，b2，…，bm，如果a?A、b?B且&a，b&?R，则自结点a到结点b作出一条有向弧，其箭头指向b。如果&a，b&?R，则结点a和结点b之间没有线段联结。用这种方法得到的图称为R的关系图。例4.8
A={1，2，3，4}，B={5，6，7}，R={&1，7&，&2，5&，&3，6&，&4，7&}，作出R的关系图。解
R的关系图，如图所示：例4.9
设A={1，2，3，4}，R={&1，2&，&2，2&，&3，3&，&4，1&}。画出A上的关系图。解
A上的关系图如图所示4.3
关系的运算4.3.1
关系的交、并、差、补运算例4.10 设X={1，2，3，4，5}，若A={&x，y&|x与y的差能被2整除}，B={&x，y&|x与y的差为正且能被3整除}，求A∪B，A∩B，A-B，B-A，~A。解
A={&1，1&，&1，3&，&1，5&，&2，2&，&2，4&，&3，1&，&3，3&，&3，5&，&4，2&，&4，4&，&5，1&，&5，3&，&5，5&}B={&4，1&，&5，2&}A∪B={&1，1&，&1，3&，&1，5&，&2，2&，&2，4&，&3，1&，&3，3&，&3，5&，&4，1&，&4，2&，&4，4&，&5，1&，&5，2&，&5，3&，&5，5&}A∩B=??A-B={&1，1&，&1，3&，&1，5&，&2，2&，&2，4&，&3，1&，&3，3&，&3，5&，&4，2&，&4，4&，&5，1&，&5，3&，&5，5&}B-A={&4，1&，&5，2&}~A={1，2，3，4，5}×{1，2，3，4，5}-{&1，1&，&1，3&，&1，5&，&2，2&，&2，4&，&3，1&，&3，3&，&3，5&，&4，2&，&4，4&，&5，1&，&5，3&，&5，5&}={&1，2&，&1，4&，&2，1&，&2，3&，&2，5&，&3，2&，&3，4&，&4，1&，&4，3&，&4，5&，&5，2&，&5，4&}4.3.2
关系的复合运算定义4.7
设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则R?S称为R和S的复合关系，表示为R?S={&x，z&|x?A∧z?C∧?y（y?B∧&x，y&?R∧&y，z&?S）例4.10
（1）A={1，2，3，4}，B={3，5，7}，C={1，2，3}，R={&2，7&，&3，5&，&4，3&}，S={&3，3&，&7，2&}，R?S={&2，2&，&4，3&}。如图所示：（2）设R，S都是A上的关系，A={1，2，3，4}。R={&1，2&，&1，3&，&3，4&}，S={&1，1&，&2，2&，&3，3&，&4，4&}，即S为A上的恒等关系，则R?S=S?R=R。如图所示：（3）设R是A上的关系，S为A上的空关系，即S=?，则R?S=S?R=?。定理4.4
设R是从A到B的关系，S是从B到C的关系，其中A={a1，a2，…，am}，B={b1，b2，…，bn}，C={c1，c2，…，ct}。而MR，MS和MR ? S分别为关系R，S和R?S的关系矩阵，则有MR?S=MR?MS。定理4.5
设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，T是从集合C到集合D上的二元关系，则有：（1）R?（S∪T）=R?S∪R?T（2）R?（S∩T）?R?S∩R?T（3）（R∪S）?T= R?T∪S?T（4）（R∩S）?T?R?T∩S?T定理4.6
设R是从A到B的关系，S是从B到C的关系，T是从C到D的关系，则有
R?（S?T）=（R?S）?T。定义4.8
设R是从A上的关系，n为整数，关系R的n次幂定义如下：（1）R0={&x，x&x?A}=IA；
（2）Rn?1=Rn?R。从关系R的n次幂定义，可得出下面的结论：（1）Rn?m=Rn?Rm；
（2）(Rn)m?Rnm4.3.3
关系的逆运算定义4.9
设R是从集合A到集合B的二元关系，如果将R中每序偶的第一元素和第二元素的顺序互换，所得到的集合称为R的逆关系，记为R?1，即R?1 ={&y，x&|&x，y&?R}定理4.7
设R，S和T都是从A到B的二元关系，则下列各式成立：（1）（（R）?1）?1=R（2）（R∪S）?1=R?1∪S?1（3）（R∩S）?1=R?1∩S?1（4）（A×B）?1 =B×A（5）（~R）?1= ~（R?1）（这里~R=A×B-R）（6）（R-S）?1=R?1-S?1定理4.8
设R是从A到B的二元关系，S是从B到C的二元关系，则下面的式子成立：
（R?S）?1=S?1?R?1证明
&z，x&?（R?S）?1?&x，z&?R?S? ?y（y?B∧&x，y&?R∧&y，z&?S）? ?y（y?B∧&z，y&?S?1∧&y，x&?R?1）
?&z，x&?S?1?R?1。所以， （R?S）?1=S?1?R?1。4.4
关系的性质4.4.1
自反性和反自反性定义4.10
设R是集合A上的二元关系，如果对于每个x?A，都有&x，x&?R，则称二元关系R是自反的。R在A上是自反的??x（x?A?&x，x&?R）定义4.11
设R是集合A上的二元关系，如果对于每个x?A，都有&x，x &?R，则称二元关系R是反自反的。R在A上是反自反的??x（x?A?& x，x &?R）4.4.2
对称性和反对称性定义4.12
设R是集合A上的二元关系，如果对于每个x，y?A，当&x，y&?R，就有&y，x&?R，则称二元关系R是对称的。R在A上是对称的??x?y（x?A∧y?A∧&x，y&?R?&y，x&?R）
设R是集合A上的二元关系，如果对于每个x，y?A，当&x，y&?R和&y，x&?R时，必有x=y，则称二元关系R是反对称的。4.4.3
传递性定义4.14
设R是集合A上的二元关系，如果对于任意x，y，z?A，当&x，y&?R，&y，z&?R，就有&x，z&?R，则称二元关系R在A上是传递的。 R在A上是传递的??x?y?（zx?A∧y?A∧z?A∧&x，y&?R∧&y，z&?R?&x，z&?R）例4.13
设A={a，b，c}，R，S，T是A上的二元关系，其中R={&a，a&，&b，b&，&a，c&}S={&a，b&，&b，c&，&c，c&}T={&a，b&}说明R，S，T是否为A上的传递关系。解
根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为&a，b&?R，&b，c&?R，但&a，c&?R。4.4.4
关系性质的判定1．自反性的判定方法定理4.9
设R是A上的二元关系，则R在A上是自反的当且仅当IA?R。离散数学答案版(全) 25_离散数学答案证明
先证必要性。任取&x，y&，由于R在A上是自反的，则有&x，y&?IA?x，y?A∧x=y?&x，y&?R从而证明了IA?R。再证充分性。任取x?A，有x?A?&x，x&?IA?&x，x&?R因此，R在A上是自反的。1．自反性的判定方法R的关系矩阵为：
R的关系图为?1?0MR???1??1??001?
2．反自反性的判定方法定理4.10
设R是A上的二元关系，则R在A上是反自反的当且仅当IA∩R=?。例4.15
设集合A={a，b，c，d}，A上的二元关系R={&a，b&，&a，c&，&b，a&，&b，c&，&c，a&，&c，d&，&d，c&}，讨论R的性质，写出R的关系矩阵，画出R的关系图。解
由于&a，a&，&b，b&，&c，c&，&d，d&?R，即IA∩R=?，所以R是反自反的。R的关系矩阵为：
R的关系图为：?0?1MR???1???0??1??0?3．对称性的判定方法定理4.11
设R是A上的二元关系，则R在A上是对称的当且仅当R=R?1。
设集合A={a，b，c，d}，A上的二元关系R={&a，b&，&a，c&，&b，a&，&b，c&，&c，a&，&c，b&，&c，d&，&d，c&，&d，d&}，讨论R的性质，写出R的关系矩阵，画出R的关系图。解
因为&a，a&?R，所以R不是自反的。由于&d，d&?R，即IA∩R??，所以R不是反自反的。R?1={&a，b&，&a，c&，&b，a&，&b，c&，&c，a&，&c，b&，&c，d&，&d，c&，&d，d&}，R=RC1，由上面的定理可知，关系R是对称的。R的关系矩阵为
R的关系图为:?0?1MR???1??1??011?4．反对称性的判定方法定理4.12
设R是A上的二元关系，则R在A上是反对称的当且仅当R∩R?1?IA。例4.17
设集合A={a，b，c，d}，A上的二元关系R={&a，c&，&b，a&，&b，c&，&c，d&，&d，a&，&d，d&}，讨论R的性质，写出R的关系矩阵，画出R的关系图。解
因为&a，a&?R，所以R不是自反的。由于&d，d&?R，即IA ∩R??，所以R不是反自反的。因为R?1={&a，b&，&a，d&，&c，a&，&c，b&，&d，c&，&d，d&}，R?R?1，所以关系R不是对称的。R∩R?1={&d，d&}?IA），由上面的定理可知，R是反对称的。R的关系矩阵为：
R的关系图为：?0?1MR???0??1??001?ab5．传递性的判定方法定理4.3
设A，B，C，D为四个非空集合，则A×B?C×D的充分必要条件是：A?C且B?D。定理4.13
设R是A上的二元关系，则R在A上是传递的当且仅当R?R?R定理4.14
设集合A={a1，a2，…，an}，R是A上的二元关系，R的关系矩阵为MR，令M=MR?MR，则R在A上是传递的当且仅当矩阵M的第i行，第j列元素为1时，MR的第i行，第j列元素必为1。4.5
关系的闭包定义4.15
设是集合A上的二元关系，如果有另一个关系满足：（1）是自反的（对称的、传递的）；（2）?；（3）对于任何自反的（对称的、传递的）关系，如果有?，就有?。则称关系为R的自反（对称、传递）闭包。定理4.15
设R是集合A上的二元关系，则
r（R）=R∪IA.定理4.16
设R是集合A上的二元关系，则
s（R）=R∪R?1.定理4.17
设R是集合A上的二元关系，则
t（R）==R∪R2∪R3∪…
设A={a1，a2，…，an}，R是集合A上的二元关系，则存在一个正整数k≤n，使得t（R）= R∪R2∪R3∪…∪Rk定理4.19
设R是非空集合A上的关系，则（1）R是自反的，当且仅当r（R）=R；（2）R是对称的，当且仅当s（R）=R；（3）R是传递的，当且仅当t（R）=R。定理4.20
设R，S是非空集合A上的关系，且R?S，则（1）r（R）?r（S）；（2）s（R）?s（S）；（3）t（R）?t（S）。定理4.21
设R是非空集合A上的关系，则（1）rs（R）= sr（R）；（2）rt（R）= tr（R）；（3）ts（R）?st（R）。4.6
等价关系与集合的划分4.6.1
等价关系定义4.16
设R是非空集合A上的二元关系，如果有R是自反的、对称的和传递的，则称R是集合A上的等价关系例：设集合A={a，b，c，d，}，R={&a，a&，&a，d&，&d，a&，&d，d&，&b，b&，&b，c&，&c，b&，&c，c&}。验证R是A上的等价关系。证明
写出R的关系矩阵从关系矩阵主对角线元素都是1，可知R是自反的。关系?1?0??0???0??0??1?矩阵是对称的，故R是对称的。从R的序偶表达式中，可以看出R是传递的，逐个检查序偶，如&a，a&，&a，d&?R，有&a，d&?R。&a，d&，&d，a&?R，有&a，a&?R，&d，a&，&a，d&?R，有&d，d&?R，…。故R是A上的等价关系。4.6.2
等价类定义4.17
设R是非空集合A上的等价关系，对于任何a?A，集合[a]R={xOx?A且&a，x&?R}称为元素a形成的R等价类。定理4.22
设R是非空集合A上的等价关系，对于a，b?R，有&a，b&?R当且仅当[a]R=[b]R。定义4.18
设R是集合A上的等价关系，等价类集合{[a]ROa?A}称作A关于R的商集，记作A/R。定理4.22
设R是非空集合A上的等价关系，对于a，b?R，有&a，b&?R当且仅当[a]R=[b]R。定义4.19
设A是一个集合，A1，A2，…，Am是它的子集，如果它满足下列条件：（1）所有Ai间均是分离的，亦即对所有i，j（i=1，2，…，m，j=1，2，…，m），如果i?j，则Ai∩Aj=?。（2）A1∪A2∪…∪Am=A则称A={A1，A2，…，Am}为集合A的一个划分，而A1，A2，…，Am称为这个划分的块。定理4.23
设R是非空集合A上的等价关系，确定了A的一个划分，该划分就是商集A/R。定理4.24
集合A的一个划分确定A上的一个等价关系。定理4.25
设R1和R2是非空集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2。例4.28
设集合A={1，2，3，4，5}上的关系R为R={&1，1&，&1，2&，&2，1&，&1，3&，&3，1&，&2，2&，&2，3&，&3，2&，&3，3&，&4，4&，&4，5&，&5，4&，&5，5&}。解
它的关系图如图4.9所示：由此图可以看出关系R是等价关系，并且它的等价类分别为[1]R=[2]R=[3]R[4]R=[5]R由等价关系所构成的等价类在图中即是等价关系图中的完全图， 所谓完全图是指图形中每个结点与其它结点有边联结的图形。4.7
相容关系4.7.1
相容关系定义4.20
设R是集合A上的一个二元关系，如果R是自反的、对称的，则称R是相容关系。定义4.21
设R是集合A上的一个相容关系，C是A的子集，如果对于C中任意两个元素x，y，有&x，y&?R，称C是相容关系R产生的相容类。定义4.22
设R是集合A上的一个相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类，记作CR。定理4.26
设R是有限集A上的相容关系，C是一个相容类，那么一定存在一个最大相容类CR，使得C?CR。 。4.7.2 覆盖定理4.27
给定集合A的覆盖{A1，A2，…，An}，由它确定的关系R=A1×A1∪A2×A2∪…∪An×An是A上的相容关系。定理4.28
集合A上相容关系R与完全覆盖存在一一对应.例4.27
设A={a，b，c，d，e，f}，R为A上的相容关系，其图形表示如图所示。求R的完全覆盖。bcfdea解
由图可知，R产生的最大相容类为：{a，b，f}，{a，d，e}，{c，f}。所以R确定的完全覆盖S={{a，b，f}，{a，d，e}，{c，f}}。离散数学答案版(全) 25_离散数学答案4.8
偏序关系4.8.1
偏序关系定义4.25
设R是集合A上的一个关系，如果R是自反的、反对称的和传递的，则称R是A上的一个偏序关系，并将它记为“≤”。序偶&A，≤&称作偏序集。例4.30
设R是集合A={2，3，6，8}上的关系，R={&x，y&│x整除y}，验证R是偏序关系。证明
R={&2，2&，&2，6&，&2，8&，&3，3&，&3，6&，&6，6&，&8，8&}，容易验证R是自反的、反对称的和传递的。故它是偏序关系。定义4.26
设R是集合A上的一个关系，如果R是反自反的和传递的，则称R是A上的一个拟序关系。一般用符号“?”表示拟序关系。定理4.29
设R是集合A上的拟序关系，则R是反对称的。4.8.2 哈斯图定理4.30
设R是集合A上的关系，则有1）如果R是一个拟序关系，则R的自反闭包r（R）=R∪IA是一个偏序关系。2）如果R是一个偏序关系，则R-IA是一个拟序关系。定义4.27
设R是集合A上的偏序关系，如果x，y?A，&x，y&?R，x?y且在A中不存在z，使得&x，z&?R、&z，y&?R，则称元素y盖住元素x。例4.33
设A={a，b，c}，R是A幂集上的包含关系?，则R是偏序关系，画出R的哈斯图。解
R的哈斯图如图4.15所示所示。{b,c}{a,b}{c}{a}{b}{a,b,c}4.8.3 全序关系定义4.28
设&A，≤&是偏序集合，B是A的子集，如果B中任意两个元素都是有关系的，则称子集B为链。定义4.29
设&A，≤&是偏序集合，B是A的子集，如果B中任意两个元素都是没有关系的，则称子集B为反链。定义4.31
设&A，≤&是偏序集合，且B是A的子集，对于B中的一个元素b，如果B中不存在任何元素x，满足b?x且b≤x，则称b为B的极大元。同理，对于b?B，如果B中不存在任何元素x，满足b?x且x≤b，则称b为B的极小元。定义4.32
设&A，≤&是偏序集合，且B是A的子集，如果有某一个元素b?B，使得B中任何元素x，都满足x≤b，则称b为&B，≤&的最大元。同理，对于b?B，如果任意元素x?B，都有b≤x成立，则称b为&B，≤&的最小元。 。定理4.31
设&A，≤&是偏序集合，且B是A的子集，若B有最大（最小）元，则必是唯一的。定义4.33
设&A，≤&是偏序集合，且B是A的子集，如果有某一个元素a?A，使得B中任何元素x，都满足x≤a，则称a为子集B的上界。同理，对于a?A，如果任意元素x?B，都有a≤x成立，则称a为子集B的下界。定义4.34
设&A，≤&是偏序集合，且B是A的子集，元素a是集合B的任意上界，如果对于B的所有上界x都有a≤x，则称a为B的最小上界（上确界），记作LUB（B）。同理，b为集合B的任意下界，若对B的所有下界y都有y≤b，则称b为子集B的最大下界（下确界），记作GLB（B）。4.8.4 良序关系定义4.35
设&A，≤&是偏序集合，如果A的每一个非空子集都存在最小元，则这种偏序集称为良序集。定理4.32
每个良序集合一定是全序集合。定理4.33
每个有限的全序集合一定是良序集合。第七章
图论内容：图的基本概念与矩阵表示，连通性及其判别，欧拉图、哈密顿图、二分图、平面图、树及生成树的判别及应用， Dijkstra算法，对偶图与着色问题教学目的：1．掌握有关图的基本概念，理解图的同构。2．熟练掌握图的表示方法和Dijkstra算法求赋权图的最短路。3．深刻理解欧拉图、哈密顿图、二分图的概念、判别及应用。4．深刻理解平面图的欧拉公式及应用。5．了解树的概念及应用。教学重点：1．图的基本概念2．图的表示方法和Dijkstra算法求赋权图的最短路3．欧拉图、哈密顿图、二分图的概念、判别及应用4．树的概念及应用教学难点：1．Dijkstra算法求赋权图的最短路2．平面图的欧拉公式及应用7.1
图的基本概念7.1.1
图的基本类型定义7.1
所谓图G是一个三元组，G=&V(G)，E（G），φG&，其中V(G)是一个非空的结点集合，E（G）是边的集合，φG是从边集合E到结点无序偶或有序偶集合上的函数。定义7.2
如果两个结点之间有多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两相结点a，b间平行边的条数称为边的重数。含有平行边的图称为多重图，不含平行边和自回路的图称为简单图。7.1.2
图中结点的度数1．无向图中结点的度数定义7.3
设图G是无向图，v是图G中的结点，所有与v关联的边的条数，称为点v的度数，记作deg(v)。定理7.1
设图G是具有n个点，m条边的无向图，其中结点集合为V={v1，v2，…，vn}，则n2．有向图中结点的度数定义7.4
设图G是有向图，v是图G中的结点，以v为始点的有向边的条数称为v的出度，记个deg+(v)，以v为终点的有向边的条数称为v的入度，记作deg－(v)。定理7.2
设有向图G具有n个结点，m条边，其中结点构成的集合V={v1，v2，…，vn}，则有?degi?1n?(vi)??deg?(vi)?mi?1n7.1.3
完全图1．无向完全图定义7.6
在n阶无向图中，如果任意两个不同的结点之间都有一条边关联，则称此无向图为无向完全图，记作Kn。2定理7.3
n个结点的无向完全图Kn的边数是cn。2．有向完全图定义7.7
在n阶有向图中，如果任意两个结点都有两条方向相反的有向边关联，且每一个结点都有自回路，则称此有向图为有向完全图。定理7.4
n个结点的有向完全图Kn的边数是n2。3．竞赛图定义7.8
设G为n阶有向图，如果G的底图为无向完全图Kn，则称G为竞赛图。7.1.4
图的同构定义7.9
设图G的点集为V，边集为E，图G′的点集为V′，边集为E'。如果存在着V到V′的双射函数f，使对任意的u，v?V，(u，v)?E（或&u，v&?E），当且仅当（f（u），f（v））?E′（或&f（u），f（v）&?E′），则称图G和G′ 同构，记作GG′。7.1.5
补图定义7.10
设G=&V，E&为任意的n阶无向简单图，则所有使G成为Kn添加的边和G的n个结点构成的图称为图G的补图，记作G。定义7.11
设G=&V，E&是任意一个n阶无向图，V={v1，v2，…，vn}，称d（v1），d（v2），…，d（vn）为G的度数列。对于结点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列d=（d1，d2，…，dn），若存在以V={v1，v2，…，vn}为结点n阶无向图G，使得d（vi）=di，则称d是可图化的。特别地，若得到的图是简单图，则称d是可简单图化的。定理7.5
设非负整数列d=（d1，d2，…，dn），当且仅当为偶数时，d是可图化的。定理7.6
设非负整数列d=（d1，d2，…，dn），（n-1）≥d1≥d2≥…≥d n≥0，则d是可简单图化的，当且仅当对于每个整数r，1≤r≤（n-1），≤r（r-1）+且为偶数。定理7.7
设非负整数列d=（d1，d2，…，dn），（n-1）≥d1≥d2≥…≥d n≥0，则d是可简单化的当且仅当d′=（-1，-1，…，-1，，…，）。7.1.6
子图定义7.12
设G=&V，E&和G=&V'，E'&是两个图，（1）若V'?V且E'?E，则称G'是G的子图；（2）若G'是G的子图，但V'≠V或E'≠E，则称G'是G的真子图；（3）若G?是G的子图，且V?=V，则称G?是G的生成子图或支撑子图。7.2
路与回路7.2.1
通路与回路定义7.13
在无向图（或有向图）G=&V，E&中，设v0，v1，…，vn?V，e0，e1，…，en?E，其中ei是关联于结点vi-1，vi的边，交替序列v0e0v1e1…en-1 vn称为联结v0到vn的通路或路。v0和vn分别称为通路的起点和终点，通路中所含边的条数称为该通路的长度。如果通路中的始点与终点相同，则称这条路为回路。定理7.8
在n阶无向图中，如果存在一条从vi到vj的通路，则从vi到vj必有一条长度不大于n-1的基本通路。定理7.9
在n阶无向图中，如果存在一条通过vi的回路，则必有一条长度不大于n的通过vi 的基本回路。7.2.2
图的连通性1．无向图的连通性定义7.14
设图G是无向图，u和v是图G中的两个结点，如果u和v之间有通路，则称u，v是连通的，并规定u与自身是连通的。离散数学答案版(全) 25_离散数学答案定义7.15
若图G是平凡图或G中任意两点都是连通的，则称图G为连通图，否则称G为非连通图或分离图。定义7.16
设无向图G=&V，E&为连通图，若存在非空点集V'?V，使图G删除了V'的所有结点后，所得到的子图是不连通图，而删除V?的任何真子集后，得到的子图仍然是连通图，则称V?是G的一个点割集。若某一个结点构成一个点割集，则称该结点为割点。定义7.17
设无向图G=&V，E&为连通图，若存在非空边集E'?E，使图G删除了E'的所有边后，所得到的子图是不连通图，而删除E'的任何真子集后，得到的子图仍然是连通图，则称E'是G的一个边割集。若某一个边构成一个边割集，则称该边为割边（或桥）。定理7.10
对于任何图G，都有下面不等式成立：k≤λ≤δ其中，k、λ、δ分别为G的点连通度、边连通度和结点的最小度。定理7.11
一个无向连通图G中的结点w是割点的充分必要条件是存在两个结点u和v，使得结点u和v的每一条路都通过w。2．有向图的连通性定义7.18
在有向图G=&V，E&中，若从结点u到v有通路，则称u可达v。 定义7.19
有向图的连通性分为强连通、单向连通和弱连通三种。定义7.20
设G是有向图，G?是其子图，若G?是强连通的（单向连通的，弱连通的），且没包含G?的更大的强连通(单向连通，弱连通)子图，则称G?是G的极大强连通子图(极大单向连通子图，极大弱连通子图)，也称为强分支（单向分支，弱分支）。7.2.4
关键路径定义7.21
在计划评审图中，关键路径是从发点到收点的通路中权和最大的路径。处于关键路径上的结点称为关键状态，处于关键路径上的边称为关键活动或关键工序。定义7.22
设计划评审图G，任意的vi?V（G），称从发点沿着关键路径到达vi所需的时间，称为vi的最早完成的时间，记作TE（vi）。定理7.13
设PE={v|TE（v）已经算出}，TE=V-PE，若TE??，则存在v?TE，使得TE??PE定义7.23
在保证收点vn的最早完成时间TE（vn）不增加的条件下，自发点v1最迟到达vi所需要的时间，称为vi的最晚完成时间，记作TL（vi）。7.3
图的矩阵表示7.3.1
图的邻接矩阵表示定义7.25
设图G的结点集合为V，边集为E，且V={v1，v2，…，vn}，令?1?aij??0???vi,vj??E??? ?vi,vj??E??则称矩阵A＝[aij]为图G的邻接矩阵。定义7.26
设n阶简单有向图G=&V，E&，V={v1，v2，…，vn}令Pij??1??0vi可达vj,否则，则称矩阵P＝[pij]为图G的可达矩阵。记作P（G），简记为P。7.3.2
图的关联矩阵表示定义7.27
设无环无向图G=&V，E&，V={v1，v2，…，vn}，E={e1，e2，…，em}，则矩阵M（G）=（mij）n×m，其中mij=称M（G）为完全关联矩阵。?1??0若vi关联ej若vi不关联ej定义7.28
设简单有向图G=&V，E&，V={v1，v2，…，vn}，E={e1，e2，…，em}，则矩阵M（G）=（mij）n×m，其中称M（G）为G的完全关联矩阵。?1若在G中vi是ej的起点???1若在G中vi是ej的终点?0若在G中v与e不关联ij?7.4
欧拉图7.4.1
欧拉图的定义定义7.29
给定无孤立结点图G，如果图中存在一条通过图中各边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图，称为欧拉图。如果图中存在一条通过图中各边一次且仅一次的通路，则称此通路为欧拉通路，具有欧拉通路的图，称为半欧拉图。7.4.2
欧拉图的判定1．无向图的欧拉定理定理7.17
无向连通图G是欧拉图的充分必要条件是图中各点的度数为偶数。定理7.18
无向连通图是半欧拉图的充分必要条件是：图中至多有两个奇数度结点。2．有向图的欧拉定理定理7.19
设图G是有向连通图，图G是欧拉图的充分必要条件是：图中每个结点的入度和出度相等。定理7.20
设图G是有向连通图，图G是半欧拉图的充分必要条件是：至多有两个结点，其中一个结点的入度比它的出度多1，另一个结点的出度比它的入度多1，而其他结点的入度和出度相等。7.5
哈密尔顿图7.5.2
哈密尔顿图的判定定理7.21
设图G=&V，E&是哈密尔顿图，则对于结点集V的每个非空子集S，都有W（G-S）≤|S|成立，其中W（G-S）是G-S中的连通分支数。定理7.22
设图G是具有n个结点（v1，v2，…，vn）的无向简单图，如果图G中任意两个不同结点的度数之和大于等于n-1，即
deg(vi)+deg(vj)≥n-1则图G具有哈密尔顿通路，即G是半哈密尔顿图。定理7.23
设图G是具有n个结点（v1，v2，…，vn）的无向简单图，如果图G中任意两个不同结点的度数之和大于等于n，即deg（vi）+deg（vj）≥n则图G具有哈密尔顿回路，即G为哈密尔顿图。定义7.31
给定图G=&V，E&，V中有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得到图G′，对图G′重复上述步骤，直到不再有这样的结点存在为止，所得到的图，称为图G的闭包，记作C（G）。定理7.24
当且仅当一个简单图G的闭包是哈密尔顿图时，则图G是哈密尔顿图。定理7.25
竞赛图必有哈密尔顿通路.定理7.26
强连通的竞赛图必有哈密尔顿通路.7.6
无向树1．无向树的定义与性质定义7.32
设T是无回路的无向简单连通图，则称T为无向树，或简称为树。在树中，度数为1的点称为树叶，度数大于1的点称为内结点或分枝点。定理7.27
设T是含n个结点和m条边的简单无向图，则下列各结论都是等价的，都可作为无向树的定义。（1）T连通且无回路。（2）T中任意两个不同的结点间，有且仅有一条通路相连。（3）T无回路且n=m+1。（4）T连通且n=m+1。（5）T连通，但删去树中任意一条边，则变成不连通图。（6）T连通且无回路，若在T中任意两个不邻接的结点中添加一条边，则构成的图包含唯一的回路。2．生成树与最小生成树定理7.29
一条回路和任何一棵生成树的补图至少有一条公共边。定理7.30
有一个边割集和任何生成树至少有一条公共边。定义7.34
在图的所有生成树中，树权之和最小的生成树，称为最小生成树。定理7.31
设图有n个结点，可用下面的算法产生最小生成树。（1）选取最小边e1，设边数k=1；（2）若k=n-1，结束，否则转（3）；（3）设已选择边为e1，e2，…，ek，在G中选择不同于e1，e2，…，ek的边ek+1，使ek+1是满足{e1，e2，…，ek，ek+1}中无回路的权最小的边。（4）k=k+1，转（2）。定义7.35
如果一个有向图的底图为无向树，则该有向图称为有向树。定义7.36
在有向树T中，如果有且仅有一个入度为0的点。其他点的入度均为1，则称有向树T为有根树，简称根树。入度为0的点称为根，出度为0的点称为树叶或叶片，出度不为0的点称为分枝点或内结点。定义7.37
根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被分成有限个子根树。定义7.38
在根树中，如果每一个结点的出度小于或等于k，则称这棵树为k叉树。若每一个结点的出度恰好等于k或零，则称这棵树为完全k叉树，若所有树叶的层次相同，称为正则k叉树当k=2时，称为二叉树。7.6.3
周游算法1．前序周游算法设需要周游的2叉树为T，其左子树为T1，右子树为T2，则前序周游算法的递归定义为:（1）访问T的根；（2）用前序周游算法遍历左子树T1；（3）用前序周游算法遍历右子树T2。2．中序周游算法其递归定义如下：（1）用中序周游算法遍历T的左子树；（2）访问T的根；（3）用中序周游算法遍历T的右子树。7.6.4
前缀码与最优树定义7.40
如果在码中，没有一个码字是另一个码字的前缀，则称这样的码为前缀码。定理7.32
任意一棵给定的完全2叉树，可以产生唯一的一个二元前缀码。 定理7.33
任何一个前缀码都对应一棵完全2叉树.定义7.41
设T是具有n片树叶t1，t2，…，tn的完全二叉树，且各片树叶所含的权为w1，w2，…，wn，令W（T）=L1w1+L2w2+…+Lnwn其中，Li（i=1，2，…，n）是完全二叉树T的根到树叶ti的通路长度，则称W(T)为完全二叉树T的权。在所有带权w1，w2，…，wn的二叉树中，w(T)最小的那棵树，称为最优二叉树，简称最优树.定理7.34
设T为带权w1≤w2≤…≤wn的最优树，则（1）带权w1，w2的树叶v1，v2是兄弟；（2）以树叶v1，v2为儿子的分枝点，其通路最长。定理7.35
设T为带权w1≤w2≤…≤wn的最优树，若以带权w1，w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵新树T′，则T′也是最优树。7.7
二部图和平面图7.7.1
二部图定义7.42
若无向图G的点集V可以划分成两个子集V1和V2，即V1∪V2=VV1∩V2=?并使图中每一条边的端点一个在V1中，另一个在V2中，则称图G为二部图（或偶图），记作G(V1,V2)。V1,V2称为互补结点子集.定义7.43
若G(V1，V2)是二部图，且V1中的每一个结点都与V2中的每一个结点邻接，则称G(V1,V2)为完全二部图，记作Kn，其中n=|V1|,m=|V2|。 m，定义7.44
设图G(V1,V2)是二部图，M是G中的一些边组成的集合，如M中任意两条边都没有公共端点，则称M为G的匹配。M的边邻接点称为饱和点。离散数学答案版(全) 25_离散数学答案定义7.45
设G(V1,V2)是二部图，M是G的一个匹配，如果对于G中任意一个匹配M′，都有|M′|≤|M|，则称匹配M为二部图G的最大匹配。定义7.46
设G(V1,V2)是二部图，M是G的一个匹配，P是G中的一条通路，如果P中任何相邻的边中恰有一条属于M，也就是说P由G中属于M的边和不属于M的边交替组成的，则称P为二部图G的交替链。7.7.2
平面图1．平面图的定义定义7.48
设G=&V，E&是一个无向图，如果能把G的所有结点和边画在平面上，且使得任何两条边除端点外没有其他的交点，则称此图为平面图，或称此图是可平面的。2．欧拉公式定义7.49
设G是一连通图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为G的一个面，包含该面的所有边所构成的回路称为这个面的边界。定理7.38
一个有限平面图，面的次数之和等于其边数的两倍。定理7.39
设图G是无向连通平面图，它具有v个结点，e条边，r个面，则v-e+r=2。以上公式称为欧拉公式。定理7.40
设图G是具有v个结点，e条边的无向简单连通图，则e≤3v-6例7.18
证明K3，3是非平面图。证明
由于K3，3是完全二部图，因此每条回路有偶数条边组成，而K3，3又是简单图，所以，若K3，3是平面图，则其每一个面至少有4条边围成，于是有2e≥4r或e 2代入欧拉公式后可得
r≤由于K3，3中，v=6，e=9，不满足上述不等式，所以K3，3是非平面图。3．库拉托夫斯基定理定义7.50
如果两个图是由同一个图的边上插入或删除度数为2的结点后得到的，则称这两个图是在二度结点内同构的。定理7.41（库拉托夫斯基定理） 一个图是平面图的充分必要条件是该图不包含与K5或K3，3在二度结点内同构的子图。4．平面图的对偶图定义7.52
如果图G的对偶图同构于G，则称G是自对偶图。定理7.42
对于n个结点的完全图Kn，有x（Kn）=n。定理7.43
设G为一个至少具有三个结点的简单连通平面图，则G中必有一个结点v，使得
deg（v）≤5。定理7.44
（五色定理）任何简单平面图G，都有x（G）≤5。定理7.45
（四色定理）对于任何平面图G，都有x（G）≤4。例7.21
如果平面图G与其对偶图同构，则称图G为自对偶图。证明：（1）图G是自对偶图，且有n个结点，m条边，则m=2n-2。（2）图G是自对偶图，且图G是简单图，则图G中至少有4个3度点。证明
（1）由欧拉公式可知n-m+r=2由于图G是自对偶图，则有n=r，从而2n-m=2即得m=2n-2。（2）首先说明，当图G是简单连通平面图且又是自对偶图时，图G中不可能有1度和2度点。由以上分析可知，简单连通平面图如果是自对偶图，其各结点的度数至少为3。或写成2m=4n-4又由于图中各点的度数之和为边数的两倍，也即有2m=4n-4我们已经知道，当简单平面图G为自对偶图时，其各个结点的度数至少为3度，因此利用上面的式子容易证明自对偶图G中至少有4个3度结点。用反证法证明。设图G中至多有3个3度结点，则图G中其他结点的度数应大于等于4由此可得m≥4（n-3）+3′3=4n-3这与2m=4n-4矛盾，所以n阶简单连通平面图若是自对偶图，图中至少有4个3度结点。欢迎您转载分享：
更多精彩：}