离散数学大作业
班级：15计算机2班
学号：20150200224
姓名：王鹏
时间：2017.6.3
第一章 命题逻辑
1.1命题及其表示法
命题的概念:
数理逻辑将能够判断真假的陈述句称作命题。
1.2命题联结词
1. 否定联结词﹁P
与原命题相反
2. 合取联结词∧
同时为真，才为真
3. 析取联结词∨
同时为假，才为假
4. 蕴涵联结词→
当且仅当p为真，q为假
5. 等价联结词
同时为真，或同时为假才为真
1.3 命题公式、翻译与解释
1. 命题公式
定义 命题公式，简称公式，定义为：
（1）单个命题变元是公式；
（2）如果P是公式，则﹁P是公式；
（3）如果P、Q是公式，则P∧Q、P∨Q、PQ、 PQ都是公式；
（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。
2. 命题的翻译
可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。
命题翻译时应注意下列事项：
（1）确定所给句子是否为命题。
（2）句子中联结词是否为命题联结词。
（3）要正确的选择原子命题和合适的命题联结词。
1.4 真值表与等价公式
1. 真值表
定义 将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。
构造真值表的方法如下：
（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，
…，P n。
（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序
依次写出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序
写出各赋值，直到00…0为止），然后从低到高的顺序列出G的层次。
（3）根据赋值依次计算各层次的真值并最终计算出G的真值
成真赋值+成假赋值=2n
2. 命题公式的分类
定义 设G为公式：
（1）如果G在所有解释下取值均为真，则称G是永真式或重言式； （2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式； （3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。
3. 等价公式
定义 设A和B是两个命题公式，如果A和B在任意赋值情况下都具有
相同的真值，则称A和B是等价公式。记为AB。
性质定理
设A、B、C是公式，则
（1）AA
（2）若AB则BA
（3）若AB且BC则AC
定理 设A、B、C是公式，则下述等价公式成立：
（1）双重否定律 AA
（2）等幂律 A∧AA ； A∨AA
（3）交换律 A∧BB∧A ； A∨BB∨A
（4）结合律 （A∧B）∧CA∧（B∧C）
（A∨B）∨CA∨（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∨11 ； A∧00
（9）同一律 A∨0A ； A∧1A
（10）排中律 A∨A1
（11）矛盾律 A∧A0
（12）蕴涵等值式 A→BA∨B
（13）假言易位 A→BB→A
（14）等价等值式 AB（A→B）∧（B→A）
（15）等价否定等值式 ABABBA
（16）归缪式 （A→B）∧（A→B）A
4. 置换规则
定理（置换规则） 设（A）是一个含有子公式A的命题公式，（B）是用公式B置换了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。
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，…，P n是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则
（1）A（P1，P2，…，P n）A*（P1，P2，…，P n）
（2）A（P1，P2，…，P n）A*（P1，P2，…，P n）
定理（对偶原理）设A、B是两个命题公式，若AB，则A*B*，其中
A*、B*分别为A、B的对偶式。
2. 范式
定义 仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。
定义 仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。
定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。
3. 主范式
定义 设G为公式，P1，P2，…，P n为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，…，P n的一个极小项，则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。
定理 任意的命题公式都存在一个唯一的与之等价的主析取范式。
定义 设G为公式，P1，P2，…，P n为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，…，P n的一个极大项，则称该合取范式为G的主合取范式。通常，主合取范式用∏表示。重言式的主合取范式中不含任何极大项，用1表示。
定理 任意的命题公式都存在一个唯一的与之等价的主合取范式。
1.6 公式的蕴涵
1. 蕴涵的概念
定义
设G、H是两个公式，若G→H是永真式，则称G蕴涵H，记作GH。
蕴涵关系有如下性质：
（1） 对于任意公式G，有GG；
（2）
（2）对任意公式G、H，若GH且HG，则GH；
（3） 若GH且HL，则GL。
2. 基本蕴涵式
（1）P∧QP； （2）P∧QQ；
（3）PP∨Q； (4) QP∨Q；
（5）P（P→Q）； （6）Q（P→Q）；
（7）（P→Q）P； （8）（P→Q）Q；
（9）P，P→QQ； （10）Q，P→QP；
（11）P，P∨QQ； （12）P→Q，Q→RP→R；
（13）P∨Q，P→R，Q→RR； （14）P→Q，R→S（P∧R）
→（Q∧S）；
（15）P，QP∧Q。
1.7 其它联结词与最小联结词组
1. 其它联结词
定义 设P、Q为命题公式，则复合命题P Q称为P和Q的不可兼析取，当且仅当P与Q的真值不相同时，PQ的真值为1，否则PQ的真值为假。
定义 设P、Q是两个命题公式，复合命题P Q称为命题P、Q的条件否定，当且仅当P的真值为1，Q的真值为0时，P Q的真值为1，否则 PQ 的真值为0。
2. 最小联结词组
定义 设S是一些联结词组成的非空集合，如果任何的命题公式都可以用仅包含S中的联结词的公式表示，则称S是联结词的全功能集。特别的，若S是联结词的全功能集且S的任何真子集都不是全功能集，则称S 是最小全功能集，又称最小联结词组。
定理 {，∧，∨，→，}是联结词的全功能集。
定理 {，∧，∨}是联结词的全功能集。
定理 {，∧}，{、∨}，{，→}是最小联结词组。
定理 {↑}，{↓}是最小联结词组。
1.8 命题逻辑推理理论
1.8.1 命题逻辑推理理论
定义 如果G1，G2，…，G n蕴涵H，则称H能够由G1，G2，…，G n有效推出，G1，G2，…，G n称为H的前提，H称为G1，G2，…，G n的有效结论。称（G1∧G2∧…∧G n）→H是由前提G1，G2，…，G n推结论H的推理的形式结构。
2. 推理规则
下面给出推理中常用的推理规则。
1． 前提引入规则：可以在证明的任何时候引入前提；
2． 结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；
3． 置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。
4． 假言推理规则：P，P→QQ
5． 附加规则：PP∨Q；
6． 化简规则：P，QP；
7． 拒取式规则：Q，P→QP；
8． 假言三段论规则：P→Q，Q→RP→R；
9． 析取三段论规则：P，P∨QQ；
10.构造性二难规则：P∨Q，P→R，Q→RR；
11.合取引入规则：P，QP∧Q
3. 推理常用方法
1.直接证法
直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。
2．间接证法
间接证法主要有如下两种情况。
（1）附加前提证明法
有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：
（G1∧G2∧…∧G n）（R→C）
设（G1∧G2∧…∧G n）为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，…，G n是n个命题公式，如果G1∧G2∧…∧G n是可满足式，则称G1，G2，…，G n是相容的。否则（即G1∧G2∧…∧G n是矛盾式）称G1，G2，…，G n是不相容的。
例 用归缪法证明。
前提：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）合取引入规则
第2章 谓词逻辑
第3章
2.1 谓词逻辑命题的符号化
1．个体词：个体词是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体
个体常项或个体常元：
个体变项或个体变元：
个体域或论域：
2．谓词：用来刻画个体词的性质或个体词之间关系的词
一般来说，“x是A”类型的命题可以用A（x）表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表
示“…大于…”谓词。我们把A（x）称为一元谓词,B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。
2.2 谓词逻辑公式与解释
1. 谓词逻辑的合式公式
定义2.1 设P（x1，x2，…，x n）是n元谓词公式，其中，x1x2，…，x n是个体变项，则称P（x1，x2，…，x n）为谓词演算的原子公式。
定义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. 约束变元与自由变元
1．约束变元与自由变元的概念
定义 2.3 在公式x F（x）和x F（x）中，称x为指导变元，F（x ）为相应量词的辖域或作用域。在x和x的辖域中，x的所有出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自由出现。
2．约束变元的换名与自由变元的代入
自由变元的代入规则是：
（1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。
（2）用以代入的变元与原公式中所有变元的名称都不能相同。
2.2.3 谓词逻辑公式的解释
定义2.4 谓词逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：
（1）对每一个常项符号指定D中一个元素。
（2）对每一个n元函数符号，指定一个函数。
（3）对每一个n元谓词符号，指定一个谓词。
显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下有一个真值，记作T I（G）。
定义2.5 若存在解释I，使得G在解释I下取值为真，则称公式G 为可满足的，简称I满足G。
定义2.6 若不存在解释I，使得I满足G，则称公式G为永假式（或矛盾式）。若G的所有解释I都满足G，则称公式G为永真式（或重言式）。
2.3 谓词逻辑约束公式的等价与蕴涵
3. 谓词逻辑的等价公式
定义2.7 设A、B是命题逻辑中的任意两个公式，设它们有共同的个体域E，若对任意的解释I都有T I（A）= T I（B），则称公式A、B在E 上是等价的，记作AB。
定理1 设A（x）是谓词公式，有关量词否定的两个等价公式：（1）﹁x A（x）x﹁A（x）
（2）﹁x A（x）x﹁A（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）
定理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）
x（A（x）∨B（x））x A（x）∨x B（x）
2.3.2 谓词逻辑的蕴涵公式
定义2.8 设A、B是命题逻辑中的任意两个公式，若A→B是永真式，则称公式A蕴涵公式B，记作AB。
定理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））
3. 多个量词的使用
定义2.9 设谓词公式G，不包含联结词→，?。把G中出现的联结词，互换；命题常量T，F互换；量词，互换之后得到的公式称为G的对偶公式，记作G*。
定理5（对偶定理） 设A、B是任意两个公式并且不包含联结词→，?。若AB，则A*B*。
2.4 前束范式
定义2.10 一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。
定理6 对任意一个谓词公式都可以化为与它等价的前束范式。
定义2.11 若一个谓词公式，具有如下形式，则称该公式为前束析取范式。
定义2.12 若一个谓词公式，具有如下形式，则称该公式为前束合取范式。
定理7 任意谓词公式都可以化为与其等价的前束析取范式和前束合取范式。
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）。
第3章 集合论
3.1集合的概念与表示
集合的表示 ：
1．列举法
2．描述法
3.文氏图法
3.2 集合之间的关系
定义3.1 如果集合A中的每一个元素都是集合B中的元素，则称A 是B的子集，也可以说A包含于B，或者B包含A，这种关系写作
AB 或 BA,如果A不是B的子集，即在A中至少有一个元素不属于B时，
称B不包含A，记作
BA 或 AB
定义3.2 如果两个集合A和B的元素完全相同，则称这两个集合相等，记作
A＝B。
定理3.1 集合A和集合B相等的充分必要条件是AB且BA。
定义3.3 如果集合A是集合B的子集，但A和B不相等，也就是说在B中至少有一个元素不属于A，则称A是B的真子集，记作
AB 或 BA
定义3.4 若集合U包含我们所讨论的每一个集合，则称U是所讨论问题的完全集，简称全集。
定义3.5 设A是有限集，由A的所有子集作为元素而构成的集合称为A的幂集，记作ρ(A)，即ρ(A)＝｛X|XA｝。
在A的所有子集中，A和这两个子集又叫平凡子集。
定理3.2 设A是有限集，|A|=n，则A的幂集ρ(A)的基为2。
3.3 集合的运算
3.3.1 集合的并运算
定义3.6 任意两个集合A、B的并，记作A∪B，它也是一个集合，由所有属于A或者属于B的元素合并在一起而构成的，即
A∪B＝｛x | xA或xB｝
用文氏图表示集合之间的并运算：
用平面上的矩形表示全集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∪A
3.3.2 集合的交运算
定义3.7 任意两个集合A、B的交记作A∩B，它也是一个集合，由所有既属于A又属于B的元素构成，即
A∩B ＝｛x | xA且xB｝
集合的交运算的文氏图表示，见图，其中阴影部分就是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Ａ且xB｝
A-B也称为集合A和B的差集。
定义3.9 设U是全集，A是U的一个子集，称U-A为A关于全集的补集，也叫做A的绝对补集，简称为补集。记作~A。即
U-Ａ＝｛x|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∩~B
A-B＝A-（A∩B）
3.3.4 集合的对称差
定义3.10 设A、B是两个集合，集合A和B的对称差记作AB，它是一个集合，其元素或属于A，或属于B，但不能既属于A又属于B。即
AB＝(A∪B)-(A∩B)
集合的对称差的文氏图表示
由对称差的定义易得下列性质：
（1）AA＝
（1）
（2）A＝A
（3）AＵ＝~Ａ
（4）AB＝BA
（5）（AB）C＝A（BC）
（6）AB＝(A-B)∪(B-A)
3.4 包含排斥原理
定理3.7 设A、B为有限集合，|A|、|B|为其基数，则
|A∪B|＝|A|+|B|-|A∩B|
这个结论称作包含排斥原理。
第七章图论
7.1 图的基本概念
7.1.1 图的基本类型
定义7.1 所谓图G是一个三元组，G=
定义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，…，v n}，则
2．有向图中结点的度数
定义7.4 设图G是有向图，v是图G中的结点，以v为始点的有向边
的条数称为v的出度，记个deg+(v)，以v为终点的有向边的条数称为v的入度，记作deg－(v)。
定理7.2 设有向图G具有n个结点，m条边，其中结点构成的集合V= {v1，v2，…，v n}，则有
7.1.3 完全图
1．无向完全图
定义7.6 在n阶无向图中，如果任意两个不同的结点之间都有一条边关联，则称此无向图为无向完全图，记作K n。
定理7.3 n个结点的无向完全图K n的边数是。
2．有向完全图
定义7.7 在n阶有向图中，如果任意两个结点都有两条方向相反的有向边关联，且每一个结点都有自回路，则称此有向图为有向完全图。
定理7.4 n个结点的有向完全图K n的边数是n2。
3．竞赛图
定义7.8 设G为n阶有向图，如果G的底图为无向完全图K n，则称G 为竞赛图。
7.1.4 图的同构
定义7.9 设图G的点集为V，边集为E，图G′的点集为V′，边集为。如果存在着V到V′的双射函数f，使对任意的
u，vV，(u，v)E（或
7.1.5 补图
定义7.10 设G=
定义7.11 设G=
…，v n}，称d（v1），d（v2），…，d（v n）为G的度数列。对于结点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数
列d=（d1，d2，…，d n），若存在以V={v1，v2，…，v n}为结点n阶无向图G，使得d（v i）=d i，则称d是可图化的。特别地，若得到的图是简单图，则称d是可简单图化的。
定理7.5 设非负整数列d=（d1，d2，…，d n），当且仅当为偶数
时，d是可图化的。
定理7.6 设非负整数列d=（d1，d2，…，d n），（n-1）
≥d1≥d2≥…≥d n≥0，则d是可简单图化的，当且仅当对于每个整数r，1≤r≤（n-1），≤r（r-1）+且为偶数。
定理7.7 设非负整数列d=（d1，d2，…，d n），（n-1）≥d1≥d2≥…≥d n≥0，则d是可简单化的当且仅当d′=（-1，-1，…，-1，，…，）。
7.1.6 子图
定义7.12 设G=
（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 n V，e0，e1，…，e n E，其中e i是关联于结点v i-1，v i的边，交替序列v0e0v1e1…e n-1 v n称为联结v0到v n的通路或路。v0和v n分别称为通路的起点和终点，通路中所含边的条数称为该通路的长度。如果通路中的始点与终点相同，则称这条路为回路。
定理7.8 在n阶无向图中，如果存在一条从v i到v j的通路，则从v i到v j必有一条长度不大于n-1的基本通路。
定理7.9 在n阶无向图中，如果存在一条通过v i的回路，则必有一条长度不大于n的通过v i 的基本回路。
7.2.2 图的连通性
1．无向图的连通性
定义7.14 设图G是无向图，u和v是图G中的两个结点，如果u和v之间有通路，则称u，v是连通的，并规定u与自身是连通的。
定义7.15 若图G是平凡图或G中任意两点都是连通的，则称图G为连通图，否则称G为非连通图或分离图。
定义7.16 设无向图G=
定义7.17 设无向图G=
定理7.10 对于任何图G，都有下面不等式成立：
k≤λ≤δ
其中，k、λ、δ分别为G的点连通度、边连通度和结点的最小度。
定理7.11 一个无向连通图G中的结点w是割点的充分必要条件是存在两个结点u和v，使得结点u和v的每一条路都通过w。
2．有向图的连通性
定义7.18 在有向图G=
定义7.19 有向图的连通性分为强连通、单向连通和弱连通三种。
定义7.20 设G是有向图，G‘是其子图，若G’是强连通的（单向连通的，弱连通的），且没包含G‘的更大的强连通(单向连通，弱连通)子图，则称G‘是G的极大强连通子图(极大单向连通子图，极大弱连通子图)，也称为强分支（单向分支，弱分支）。
7.2.4 关键路径
定义7.21 在计划评审图中，关键路径是从发点到收点的通路中权和最大的路径。处于关键路径上的结点称为关键状态，处于关键路径上的边称为关键活动或关键工序。
定义7.22 设计划评审图G，任意的v i V（G），称从发点沿着关键路径到达v i所需的时间，称为v i的最早完成的时间，记作TE（v i）。
定理7.13 设P E={v|TE（v）已经算出}，T E=V-P E，若T E，则存在vT E，使得
P E
定义7.23 在保证收点v n的最早完成时间TE（v n）不增加的条件下，自发点v1最迟到达v i所需要的时间，称为v i的最晚完成时间，记作
TL（v i）。
7.3 图的矩阵表示
7.3.1 图的邻接矩阵表示
定义7.25 设图G的结点集合为V，边集为E，且V={v1，v2，
…，v n}，令
则称矩阵A＝[a ij]为图G的邻接矩阵。
定义7.26 设n阶简单有向图G=
则称矩阵P＝[p ij]为图G的可达矩阵。记作P（G），简记为P。
7.3.2 图的关联矩阵表示
定义7.27 设无环无向图G=
{e1，e2，…，e m}，则矩阵M（G）=（m ij）n×m，其中m ij=
称M（G）为完全关联矩阵。
定义7.28 设简单有向图G=
{e1，e2，…，e m}，则矩阵M（G）=（m ij）n×m，其中
称M（G）为G的完全关联矩阵。
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=
定理7.22 设图G是具有n个结点（v1，v2，…，v n）的无向简单图，如果图G中任意两个不同结点的度数之和大于等于n-1，即 deg(v i)+deg(v j)≥n-1
则图G具有哈密尔顿通路，即G是半哈密尔顿图。
定理7.23 设图G是具有n个结点（v1，v2，…，v n）的无向简单图，如果图G中任意两个不同结点的度数之和大于等于n，即
deg（v i）+deg（v j）≥n
则图G具有哈密尔顿回路，即G为哈密尔顿图。
定义7.31 给定图G=
C（G）。
定理7.24 当且仅当一个简单图G的闭包是哈密尔顿图时，则图G 是哈密尔顿图。
定理7.25 竞赛图必有哈密尔顿通路.
定理7.26 强连通的竞赛图必有哈密尔顿通路.
7.6 树
7.6.1 无向树
1．无向树的定义与性质
定义7.32 设T是无回路的无向简单连通图，则称T为无向树，或简称为树。在树中，度数为1的点称为树叶，度数大于1的点称为内结点或分枝点。
定理7.27 设T是含n个结点和m条边的简单无向图，则下列各结论都是等价的，都可作为无向树的定义。
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}
{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨Q ）→R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) ． 4．设P (x )：x 是人，Q (x )：x 去上课，则命题“有人去上课．” 可符号化为 ?x(P(x) ∧Q(x)) ． 5．设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名：
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
第5章作业答案 1. 用枚举法给出下列集合 解(2) {-3，2} (4) {5，6，7，8，9，10，11，12，13，14，15} 2. 用抽象法说明下列集合 解(6) {x|?k (k∈I∧x = 2k + 1)} 6．写出下列集合的幂集 解(2) ρ({1, ?}) = {?, {1}, {?}, {1, ?}} (4) ρ({?, {a}, {?}}) = {?, {?}, {{a}}, {{?}}, {?, {a}}, {?, {?}}, {{a}, {?}}, {?, {a}, {?}}} 9. 证明：如果B?C，则ρ(B) ?ρ(C)。 证明任取x∈ρ(B)，则x?B，又因为B?C，所以x?C，x∈ρ(C)。 10．设U = {1, 2, 3, 4, 5}，A = {1, 4}，B = {1, 2, 5}和C = {2, 4}，试写出下列集合。解(8) ρ(A) -ρ(C) = {?, {1}, {4}, {1, 4}} - {?, {2}, {4}, {2, 4}} = {{1}, {1, 4}} 11．证明下列恒等式 (7) (A-B) -C = (A-C) - (B-C) 证法1 对于任意x， x∈ (A-C) - (B-C) ?x∈A-C ∧x? B-C ?x∈A∧x?C ∧?(x∈ B∧x?C) ? x∈A∧x?C ∧ ( x?B ∨ x∈C) ?( x∈A∧x?C ∧ x?B)∨( x∈A∧x?C ∧ x∈C) ? x∈A∧x?C ∧ x?B ? x∈A∧ x?B∧x?C ? x∈A-B ∧ x?C ? x∈(A-B) -C 证法2 (A-C) - (B-C) = A?~C?~( B?~C) = A?~C? (~ B? C) = ( A?~C?~ B) ?( A?~C? C) =(A?~C?~ B) ?? = A?~B?~ C = (A-B) ?~ C = (A-B) -C 12．设A, B, C是集合，下列等式成立的条件是什么？ (3) (A-B ) ? (A-C) = ? 解因为(A- B) ?( A-C) = (A?~B) ? ( A?~C) = A? (~B?~C) = A?~(B ?C) = A- (B ?C) 所以(A-B)?(A-C) = ?iff A- (B?C) = ?iff A? (B?C)
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
吉林大学网络教育学院2019-2020学年第一学期期末考试《离散数学》大作业 学生姓名专业 层次年级学号 学习中心成绩 年月日
作业完成要求：大作业要求学生手写，提供手写文档的清晰扫描图片，并将图片添加到word 文档内，最终wod文档上传平台，不允许学生提交其他格式文件（如JPG，RAR等非word 文档格式），如有雷同、抄袭成绩按不及格处理。 一、简答题（每小题7分，共56分） 1、什么是命题公式的演绎？ 答：首先定义了消解复杂性的两种范式:最简范式和文字范式,在此基础上采用演绎方法证明了L中的可判定性定理,并设计了命题公式的演绎判定算法P(F).P(F)的时间复杂度为O(n3),远远小于基于真值表法的O(2n)和基于策略方案HAL的O(n5)。 2、什么是子句？请给出一例。 答：子句是一组包含一个主词和一个动词的关连字。子句与片语有明显的不同，后者为一组不含主词与动词关系的关连字，如"in the morning" 或"running down the street" 或"having grown used to this harassment." 3、什么是短语？请给出一例。 答：短语是由句法、语义和语用三个层面上能够搭配的语言单位组合起来的没有句调的语言单位，又叫词组。它是大于词而又不成句的语法单位。简单的短语可以充当复杂短语的句法成分，短语加上句调可以成为句子。由语法上能够搭配的词组合起来的没有句调的语言单位 例如：粮食//丰收（名//动）（什么//怎么样） 4、什么是命题逻辑中的文字？ 答：检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类。 5、什么是析取范式？请给出一例。 答：在离散数学中，仅由有限个文字构成的合取式称为简单合取式，而由有限个简单合取式构成的析取式称为析取范式。范式存在定理说明了它的存在性：任一命题公式都存在着与之等值的析取范式与合取范式。但它并不是惟一的。主析取范式是惟一的。
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）：
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P
华南理工大学网络教育学院 2018–2019学年度第一学期 《离散数学》作业 1、用推理规则证明?（P∧?Q），?Q∨R，? R??P 证（1）?Q∨R P （2）? R P （3）?Q（1）（2）析取三段论 （4）?（P∧?Q）P （5）?P ∨ Q （4）等价转换 （6）?P （3）（5）析取三段论 2、用推理规则证明Q，?P → R，P → S，? S?Q∧R 证（1）P → S P （2）? S P （3）?P（1）（2）拒取式 （4）?P → R P （5）R （3）（4）假言推理 （6）Q P （7）Q∧R（5）（6）合取 3．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解（1）真值表如下 P Q ?Q P→Q ?Q∧（P→Q）?P?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??（?Q∧（?P∨Q））∨?P ?（Q∨?（?P∨Q））∨?P??（?P∨Q）∨（Q∨?P）?1（析取范式）?（?P∧?Q）∨（?P∧Q）∨（P∧?Q）∨（P∧Q）（主析取范式） （3）该公式为重言式 4．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解前提：?x（F（x）→? G（x）），?x（G（x）∨H（x））， ? x? H（x）。 结论：? x ?F（x）。 证(1)? x ?H（x）P (2)?H（c）ES(1) (3)?x（G（x）∨H（x））P (4) G（c）∨H（c）US(3) (5) G（c）T(2，4)I (6)?x（F（x）→? G（x））P (7)F（c）→? G（c）US(6) (8)? F（c）T(5,7)I (9)（?x）? F（x）EG(8) 5．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证(1)（?x）（C（x）∧Q（x））P (2)C（c）∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P (4) C（c）→W（c）∧R（c）US(3) (5) C（c）T(2)I (6)W（c）∧R（c）T(4,5)I (7)R（c）T(6)I (8)Q（c）T(2)I (9)Q（c）∧R（c）T(7,8)I (10) （?x）（Q（x）∧R（x））EG(9) 6．设R是集合A = {1, 2, 3, 4, 5, 6, 7, 8, 9}上的整除关系。 （1）给出关系R；（2）画出关系R的哈斯图； （3）指出关系R的最大、最小元，极大、极小元。 解R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>，<1,7>,<1,8>,<1,9>,<2,4>,<2,6>，<2,8>，<3,6>，<3,9>，<4,8>}∪I A COV A={<1,2>,<1,3>,<1,5>,<1,7>,<2,4>,<2,6>，<3,6>，<3,9>，<4,8>} 作哈斯图如右： 极小元和最小元为1； 极大元为5,6,7,8,9, 无最大元 8
离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A )
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外） 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出 掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在 03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{3}，{1,3}，{2,3}， A B {1,2,3}} ，A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3,3> ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝ {<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
一、简要回答下列问题（每小题5分，共30分） 1、请给出集合的吸收率。 2、设A={1，2}，请给出A上的所有关系。 答：集合A上的全部关系有2^(2^2)=16种：空关系{}，全关系 {<1,1>,<1,2>,<2,1>,<2,2>}{<1,1>}{<2,2>}{<1,2>}{<2,1>}{<1,1>,<1,2>}{<1,1>,<2,1>}{<1,1> ,<2,2>}{<1,2>,<2,1>}{<1,2>,<2,2>}{<2,1>,<2,2>}{<1,1>,<1,2>,<2,1>}{<1,1>,<1,2>,<2,2>}{< 1,1>,<2,1>,<2,2>}{<1,2>,<2,1>,<2,2>} 3、什么是子句？请给出一例。 答：子句集S称为是可满足的，如果存在一个个体域和一种解释，使S中的每一个子句均为真，或者使得S的每一个子句中至少有一个文字为真。否则, 称子句集S是不可满足的 4、什么是前束范式？ 答：前束范式亦称前束式，一种谓词演算公式。指其一切量词都未被否定地处于公式的最前端且其辖域都延伸至公式的末端的谓词演算公式。设Q∈{?，?}，一个公式α是前束范式，当且仅当存在一个不含量词的公式β，使得 α=(Q?x?)(Q?x?)…(Q?x?)β. 5、什么是谓词逻辑中的项？ 答：谓词逻辑中的项指变项和常项，变项又分为自由变项和约束变项。 6、什么是命题公式的演绎？ 答：用A'表示非A,则 (A+B)'=A'B', (AB)'=A'+B'. 二、设A是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A={a，b}，B={1， 2}，试写出A到B上的全部二元关系。（8分） 答：解：A 到B 上共有2mn 个二元关系。本题中A×B 的全部子集φ，{(a,1)}，{(a,2)}，{(b,1)}， {(b,2)}， {(a,1),(a,2)}，{(a,1),(b,1)}，{(a,1),(b,2)}，{(a,1),(b,2)}，{(a,2),(b,1)}，{(a,2),(b,2)}， {(a,1),(a,2),(b,1)}，{(a,1),(a,2),(b,2)}，{(a,1),(b,1),(b,2)}，{(a,2),(b,1),(b,2)}，{(a,1),(a,2),(b,1),(b,2)}为A 到B 的全部二元关系。 三、R，S是集合A上的两个关系。试证明下列等式：（10分） （1）(R?S)-1= S-1?R-1 （2）(R-1)-1= R 证明：先证(R?S)--1?R-1，对任意(x，-1，则(y，，则存在，满足(y，且(a，，那么(x，-1且(a，-1，
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G=