离散数学复习资料
第1章命题逻辑
本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)式，命题逻辑的推理理论.
一、重点容
1. 命题
命题表述为具有确定真假意义的述句。命题必须具备二个条件：其一，语句是述句；其二，语句有唯一确定的真假意义.
2. 六个联结词及真值表
“?”否定联结词，P是命题，?P是P的否命题，是由联结词?和命题P组成的复合命题.P取真值1，?P取真值0，P取真值0，?P取真值1. 它是一元联结词.
“∧”合取联结词，P∧Q是命题P，Q的合取式，是“∧”和P，Q组成的复合命题. “∧”在语句中相当于“不但…而且…”，“既…又…”. P∧Q取值1，当且仅当P，Q均取1；P∧Q 取值为0，只有P，Q之一取0.
“∨”析取联结词，“?∨”不可兼析取(异或)联结词， P∨Q是命题P，Q的析取式，是“∨”和P，Q组成的复合命题. P?∨Q是联结词“?∨”和P，Q组成的复合命题. 联结词“∨”或“?∨”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“P?∨Q”?“(?P∧Q)∨(P∧?Q)”. P∨Q取值1，只要P，Q之一取值1，P∨Q取值0，只有P，Q都取值0.
“→”蕴含联结词， P→Q是“→”和P，Q组成的复合命题，只有P取值为1，Q 取值为0时，P→Q取值为0；其余各种情况，均有P→Q的真值为1，亦即1→0的真值为0，0→1，1→1，0→0的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“P→Q”.
“?” 等价联结词，P?Q是P，Q的等价式，是“?”和P，Q组成的复合命题. “?”在语句中相当于“…当且仅当…”，P?Q取值1当且仅当P，Q真值相同.
3. 命题公式、赋值与解释，命题公式的分类与判别
命题公式与赋值，命题P含有n个命题变项P1，P2,…,P n，给P1，P2,…,P n各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P 的真指派；若使P的真值为0，则称这组值称为P的假指派.
命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；
判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)式法，该公式的主析取式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.
等值式A?B，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。
定理1 设Φ(A)是含命题公式A 的命题，Φ(B)是用命题公式B 置换Φ(A)中的A 之后得到的命题公式. 如果A ?B ，则Φ(A)?Φ(B).
4. 式
析取(合取)式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)式.
极小项(极大项)，n 个命题变项P 1,P 2,…,P n ，每个变项或它的否定两者只有其一出现且仅出现一次，第i 个命题变项或者其否定出现在从左起第i 个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项).
以两个命题变项为例，m 00=?P ∧?Q ，m 01=?P ∧Q,m 10=P ∧?Q,m 11=P ∧Q 是极小项;M 00=P ∧Q ，M 01=P ∧?Q,M 10=?P ∧Q,M 11=?P ∧?Q 是极大项.
主析取式(主合取式) 含有n 个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)式等值，则该等值式称为原命题公式的主析取(合取)式。 每项含有n 个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)式.
任意命题公式都存在与之等值的式，存在与之等值的主式，且是惟一的.
求式，包括求析取式、合取式、主析取式和主合取式. 关键有两点：其一是准确掌握式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律.
求析取(合取)式的步骤：
① 将公式中的联结词都化成?，∧，∨(即消去个数中的联结词→，?，?∨)；
② 将否定联结词?消去或移到各命题变项之前；
③ 利用分配律、结合律等，将公式化为析取(合取)式.
求命题公式A 的主析取(合取)式的步骤：
① 求公式A 的析取(合取)式；
② “消去”析取(合取)式中所有永假式(永真式)的析取项(合取项)，如P ∧?P(P ∨?P)用0(1)替代. 用幂等律将析取(合取)式中重复出现的合取项(析取项)或相同的变项合并，如P ∧P(P ∨P)用P 替代，m i ∨m i (M i ∧M i )用m i (M i )替代.
③ 若析取(合取)式的某个合取项(析取项)B 不含有命题变项P i 或?P i ，则添加P i ∨?P i (P i ∧?P i )，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；
④ 将极小(极大)项按由小到大的顺序排列，用∑(∏)表示.
5. 命题演算的推理理论
设A 1,A 2,…,A n ,C 是命题公式，如果C A A A n →∧∧∧Λ21是重言式，称C 是前提集合{ A 1,A 2,…,A n }的有效结论或{A 1,A 2,…,A n }逻辑地推出C 。记作C A A A n ?∧∧∧Λ21 掌握演绎或形式证明. 要理解并掌握14个重言蕴含式(即I 1～I 14)，17个等值式(E 1～E 17)；二是会使用三个规则(P 规则、T 规则和CP 规则)。
推理方法有：
真值表法；等值演算法；主析取式法，构造证明法(直接证明法、附加前提证明法和间接证明法)
第2章 谓词逻辑
本章重点：谓词与量词，公式与解释，前束式，谓词逻辑推理证明.
一、重点容
1. 谓词与量词
谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项(用a,b,c,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,…表示. 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.
量词，是在命题中表示数量的词，量词有两类：全称量词?，表示“所有的”或“每一个”；存在量词?，表示“存在某个”或“至少有一个”.
在谓词逻辑中，使用量词应注意以下几点：
(1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变.
(2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域.
(3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义. 谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.
在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。一般地，使用全称量词?，特性谓词后用→；使用存在量词?，特性谓词后用∧.
2. 公式与解释
谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式.
例如?x(F(x)→G(x))，?x(F(x)∧G(x))，?x ?y(F(x)∧F(y)∧L(x,y)→H(x,y))等都是谓词公式.
变元与辖域，在谓词公式?xA 和?xA 中，x 是指导变元，A 是相应量词的辖域. 在?x 和?x 的辖域A 中，x 的所有出现都是约束出现，即x 是约束变元，不是约束出现的变元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域的同一变元有效.
换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变.
代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号.
解释(赋值)，谓词公式A 的个体域D 是非空集合，则
(1) 每一个常项指定D 中一个元素；
(2) 每一个n 元函数指定D n 到D 的一个函数；
(3) 每一个n 元谓词指定D n 到{0,1}的一个谓词；
按这个规则做的一组指派，称为A 的一个解释或赋值.
在有限个体域下，消除量词的规则为：如D ＝{a 1,a 2,…,a n }，则
)(...)()()()(...)()()(2121n n a A a A a A x xA a A a A a A x xA ∨∨∨??∧∧∧?? 谓词公式分类，在任何解释下，谓词公式A 取真值1，公式A 为逻辑有效式(永真式)；在任何解释下谓词公式A 取真值0，公式A 为永假式；至少有一个解释使公式A 取真值1，公式A 称为可满足式.
3. 前束式 一个谓词公式的前束式仍是谓词公式. 若谓词公式F 等值地转化成 B x Q x Q x Q k k (2211)
那么B x Q x Q x Q k k ...2211就是F 的前束式，其中Q 1，Q 2，…，Q k 只能是?或?，x 1,x 2,…,x k 是个体变元，B 是不含量词的谓词公式.
每个谓词公式F 都可以变换成与它等值的前束式. 其步骤如下：
① 消去联结词→，?，?∨；
② 将联结词?移至原子谓词公式之前；
③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；
④将?x,?x 移至整个公式最左边；
⑤ 得到公式的前束式.
4.谓词逻辑的推理理论
谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言蕴含式以及P ，T ，CP 规则在谓词演算中仍然使用. 在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有US 规则(全称量词消去规则)，UG 规则(全称量词附加规则)，ES 规则(存在量词消去规则)，EG 规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行.
第3章 集合与关系
本章重点：集合概念，集合的运算，集合恒等式的证明，笛卡儿积.
一、重点容
1. 集合的概念
集合与元素，具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.集合A 中元素的个数为集合的元数∣A ∣.
集合的表示方法：列举法和描述法.
列举集合的元素，元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“∈”或不属于“?”关系.
2. 集合的关系：包含，子集，集合相等.
包含(子集)，若B a A a ∈?∈?，则B 包含A(或A 包含于B)，称A 是B 的子集，记B A ?，又A ≠B ，则A 是B 的真子集，记A ?B.
集合相等，若A ?B ，B ?A ，则A ＝B. 注意：元素与集合,集合与子集，子集与幂集，∈与?(?)，空集?与所有集合等的关系. 3. 特殊集合：全集、空集和幂集.
全集合E ，在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集. 空集?，不含任何元素的集合为空集. 空集是惟一的，它是任何集合的子集.
集合A 的幂集P(A)，有集合A 的所有子集构成的集合 P(A)=}
{A x x ?. 若∣A ∣＝n, 则∣P(A)∣=2n .
4. 集合的运算
集合A 和B 的并A ?B ，由集合A 和B 的所有元素组成的集合.
集合A 和B 的交A ?B ，由集合A 和B 的公共元素组成的集合.
集合A 的补集~A ，属于E 但不属于集合A 的元素组成的集合，~A. 补集总相对于一个全集.
集合A 与B 的差集A －B ，由属于A ，而不属于B 的所有元素组成的集合..
集合A 与B 的对称差A ⊕B ，A ⊕B ＝(A －B)?(B －A)或A ⊕B ＝）A ?B 〕－（A ?B ）
应该很好地掌握10条运算律(运算的性质)(教材P71～72)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等.
5. 恒等式证明
集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；其三是集合恒等式的推理证明.
集合恒等式的证明方法通常有二：(1)要证明A ＝B ，只需要证明A ?B ，又A ?B ；(2)通过运算律进行等式推导.
6. 有序对与笛卡儿积
有序对，就是有顺序的数组，如
注意：有序对≠
笛卡儿积，把集合A ，B 合成集合A ×B ，规定
A ×
B ＝{
由于有序对
A.
笛卡儿积也可以多个集合合成，A 1×A 2×…×A n .
笛卡儿积的运算性质. 一般不能交换.
第4章 二元关系与函数
本章重点：关系概念与其性质，等价关系和偏序关系，函数.
一、重点容
1. 关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.
二元关系，是一个有序对集合，设集合A,B ，},{B y A x y x R ∈∧∈><=，记作xRy
二元关系的定义域：Dom(R)A ?； 二元关系的值域：Ran(R)B ?
关系的表示方法：
集合表示法：关系是集合，有类似于集合的表示方法.
列举法，如R ＝{<1,1>,<1,2>}；描述法：如},{B y A x y x R ∈∧∈><=
关系矩阵： R ?A ×B ，R 的矩阵???? ??==?????/==?n j m i b R a Rb a r r M j i j i ij n m ij R ,...,2,1,...,2,101,)(
关系图： R 是集合上的二元关系，若∈R ，由结点a I 画有向弧到b j 构成的图形.
2. 几个特殊的关系
空关系?；唯一是任何关系的子集的关系. 全关系A A A b a b a E A ?≡∈><=},,{
恒等关系},{A a a a I A ∈><=，M I 是单位矩阵.
3. 关系的运算
关系的集合运算，有并、交、补、差和对称差.
复合关系 },,,{2121R c b R b a b c a R R R >∈<∧>∈<=?=使，有
复合关系矩阵：
21R R R M M M ?=(布尔运算)，有结合律：(R ?S)?T ＝R ?(S ?T) 逆关系},,{1R y x x y R >∈<><=-，T R R M M =-1，(R ?S)－1=S －1?R －1
. 4. 关系的性质
自反性 R x x A x >∈<∈?,,；矩阵R M 的主对角线元素全为1；关系图的每个结点都有自回路.
反自反性 R x x A x >?<∈?,,；矩阵R M 的主对角线元素全为0；关系图的每个结点都没有自回路.
对称性 若R y x >∈<,，则R x y >∈<,；矩阵R M 是对称矩阵，即ji ij r r =；关系
图中有向弧成对出现,方向相反.
反对称性 若R y x >∈<,且R x y >∈<,，则x=y 或若y x R y x ≠>∈<,,，则R x y >?<,；矩阵R M 不出现对称元素.
传递性 若R b a >∈<,且R c b >∈<,，则R c a >∈<,；在关系图中，有从a 到b 的弧，有从b 到c 的弧，则有从a 到c 的弧. 判断传递性较为困难.
可以证明：R 是集合A 上的二元关系，
(1)(1)R 是自反的?I A ?R; (2)R 是反自反的?I A ?R ＝?;
(3)R 是对称的 ?R ＝R －1； (4)R 是反对称的?R ?R －1?I A ；
(5)R 是传递的?R ?R ?R.
关系的性质所具有的运算见表4－1.
由表可见，I A 具有自反性，对称性、反对称性和传递性.E A 具有自反性，对称性和传递
性.故I A ，E A 是等价关系.?具有反自反性、对称性、反对称性和传递性。?是偏序关系.
关系性质的判定，可以用定义、关系矩阵或关系图.
传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如?可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；
5. 关系的闭包
设R 是非空集合A 上的二元关系，在关系R 中，添加最少的有序对，新关系用R '表示，使得R '具有关系的自反(对称、传递)性质，R '就是R 的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)。闭包的求法：
定理12：A I R R r Y =)(；定理13：1)(-=R R R s Y ；定理14的推论：
Y n i i R R t 1)(==
6. 等价关系和偏序关系 极大(小)元、最大(小)元问题 等价关系和偏序关系是具有不同性质的两个关系.
???==+??????+偏序关系等价关系传递性反对称性对称性自反性 等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a 到b ，从b 到c 各有一条有向弧线，则从a 到c 一定有有向弧线。
等价类，若R 是等价关系，与R 中的某个元素等价的元素组成的集合，就是R 的一个等价类，[a]R ={b ∣b ∈A ∧aRb}.
偏序集的哈斯图 偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若a ≤b ，则结点b 画在上边，a 画在下边，并画a 到b 的无向弧；(3) 若
确定任一子集的最大(小)元，极大(小)元.
极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样.
7. 函数
函数, 设f 是集合A 到B 的二元关系，?a ∈A,?b ∈B,且
集合A ×B 的任何子集都是关系，但不一定是函数. 函数要求对于定义域A 中每一个元素a ，B 中有且仅有一个元素与a 对应，而关系没有这个限制.
二函数相等是指：定义域相同，对应关系相同，而且定义域每个对应值都相同.
函数的类型
单射 若)()(2121a f a f a a ≠?≠
满射 f(A)=B. 即)(,,x f y A x B y =∈?∈?使得
双射 单射且满射.
复合函数,:,:,:C A g f C B g B A f →?→→则即))(()(x f g x g f =?. 复合成立的条件是：)(Dom )(Ran g f ?
一般f g g f ?≠?，但)()(h g f h g f ??=??
复合函数的性质：
如果f,g 都是单射的，则f ?g 是单射的； 如果f,g 都是满射的，则f ?g 是满射的； 如果f,g 都是双射的，则f ?g 是双射的； 如果f,g 是单射的，则f 是单射的； 如果f,g 是满射的，则g 是满射的；
如果f ?,g 是双射的，则f 是单射的，g 是满射的.
反函数 若f ：A →B 是双射，则有反函数f －1：B →A
},)(,,{1A a b a f B b a b f ∈=∈><=-，f f f g g f =?=?-----11111)(,)(
第5章 代数结构
本章重点：代数运算及性质，群的概念，置换和置换群、交换群和循环群.
一、重点容
1.代数运算及其性质
二元运算，非空集合A 上的函数(映射) f ：A 2→A 就是A 上的二元代数运算，
就是说二元运算是一个变换(对应关系).
代数运算的性质：
交换律 ?x,y ∈A ，有x y=y x ， 在A 上适合交换律.
结合律 ?x,y ∈A ，有(x y) z ＝x (y z)，运算 在A 上适合结合律.
分配律 ?x,y,z ∈A ，有x *(y z)=(x *y) (x *z) 或(y z)*x=(y *x) (z *x)，* 对 适合分配律.
幂等律 ?x ∈A ，有x x=x ，则运算 在A 上适合幂等律.
吸收律 ?x,y ∈A, 有x *(x y)=x, x (x *y)=x ， 和 * 满足吸收律.
单位元 e l , (或e r )∈A ，对?x ∈A, 有e l x=x (x e r =x), e l (或e r )是A 的运算 的左单位元(或右单位元). e 既是右单位元又是左单位元就是单位元.
逆元 对x ∈A ，若x －1∈A, 有x －1 x=x x －1=e ，x －1是x 的逆元.
代数系统 在非空集合A 上，定义了若干代数运算f 1,f 2,…,f m , (A, f 1,f 2,…,f m )称为代数系统. 若B ?A ，f 1,f 2,…,f m 在B 上成立，(B, f 1,f 2,…,f m )称为子代数系统.
2.群
代数系统
子群群半群）（存在逆元、单位元具有结合律,*)(,***H G G H ??→???????→?????→?? 注意：由上可见，代数系统、半群、群(子群)是一条线下来，条件逐步加强，半群和群是我们讨论的重点.
群的性质：(1) (a －1)－1=a; (2) (a*b)－1=b －1*a －1;(3) a m *a n =a m+n ;(4) (a m )n =a mn ; (5)(方
程的可解性) 方程a*x=b 或y*a=b 有唯一解； (6) (消去律) 由a*c=b*c 或 c*a=c*b ，可得a=b
3. 特殊群
交换群，群(G,*)的二元运算*满足交换律，(G,*)是交换群(阿贝尔群) .
循环群，群G 能表成
G={a k ∣k ∈Z ，a ∈G}
G 是循环群. 记作G ＝(a)，a 是群G 的生成元.
变换群 设A 是一个非空集合，A 上的所有一一变换构成的集合E(A), 对于变换乘法，E(A)构成一个群，称为集合A 上的一一变换群. E(A)的子群称为变换群.
置换群，n 元集合M 上的所有n 元置换S n ，关于置换乘法构成n 元对换群，它的子群叫置换群.
4. 置换，
置换，有限集合M ＝{a 1,a 2,…,a n }上的双射σ：M →M ，n 元置换
???? ??=)()()(11121a a a a a a n σσσσΛΛ
置换复合(乘法)，设???? ??=)()()(2121n n a a a a a a σσσσΛΛ,???? ??=)()()(21
21n n a a a a a a ττττΛΛ
那么???? ??===?))(())(())(())((*2121n n a a a a a a x στστστστσττσΛΛ
单位置换，???? ??=n n a a a a a a I ΛΛ2121
逆置换，σ－1=???? ??n n a a a a a a ΛΛ2121)()()(σσσ
n 元集合M 上的n 元置换有n!个，有n 元置换构成的集合，记作S n .
轮换，满足：(1)σ(a 1）=a 2, σ(a 2）=a 3, …,σ(a m ）=a 1； (2)σ(a)=a ，当a ≠a k ,(k=1,2,…,m)时. 则σ是一个长度为m 的轮换，记作(a 1,a 2,…,a m ).
重要结论：置换有结合律；不相交的轮换有交换律；S n 中任一置换都可以唯一地表示成一系列不相交的轮换之积.
5. 同态与同构
同态，代数系统(G,*)和(S, ?)，f 是从G 到S 上的一个映射. ?a,b ∈G ，有
f(a*b)=f(a) ?f(b)
则称f 是由(G,*)到(S, ?)的一个同态映射. 并称G 与S 同态. 如果f 是满射，则称G 与S 是满同态，记作G ～S ；如果f 是单射，则称G 与S 是单同态.
(f(G), ?)称为(G,*)在f 下的同态象..
同构，代数系统(G,*)到(S, ?)，如果f 是从G 到S 的一个双射，则称f 是从G 到S 的同构，
群同构，设群(G,*)和(S, ?)，存在从(G,*)到(S, ?)的同态双射，则称群(G,*)与(S, ?)同构.
第7章 几种特殊的图
本章重点：欧拉图和哈密顿图、平面图和树的基本概念.
一、重点容
1. 欧拉图 欧拉通路(回路)与欧拉图 通过图G 的每条边一次且仅一次，而且走遍每个结点的
通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图.
欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画.
欧拉图或通路的判定
(1) 无向连通图G 是欧拉图?G 不含奇数度结点(G 的所有结点度数为偶数):(定理1)
(2) 非平凡连通图G 含有欧拉通路?G 最多有两个奇数度的结点；(定理1的推论)
(3) 连通有向图D 含有有向欧拉回路(即欧拉图)?D 中每个结点的入度＝出度
连通有向图D 含有有向欧拉通路?D 中除两个结点外，其余每个结点的入度＝出度，且
此两点满足deg －(u)－deg ＋(v)＝±1. (定理2)
2. 哈密顿图
哈密顿通路(回路)与哈密顿图 通过图G 的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图.
判断哈密顿图是较为困难的.
哈密顿图的充分条件和必要条件
(1) 在无向简单图G=
(2) 有向完全图D ＝
(3) 设无向图G=
若此条件不满足，即?V 1?V ，使得P(G －V !)>∣V 1∣,则G 一定不是哈密顿图(非哈密顿图的充分条件).
3.平面图
平面图 一个图能画在平面上，除结点之外，再没有边与边相交.
面、边界和面的次数 由连通平面图G 的边围成的其部不含G 的结点和边的区域是面，常用r 表示. 围成面的各边组成的回路是边界. 边界回路的长度是面的次数，记作deg(r).
重要结论
(1)平面图e
r e E v V E V G r i i 2)deg(,,,,1===>=<∑=则(所有面的次数之和＝边的2
倍)(定理6).
(2)欧拉公式：平面图,,,,e E v V E V G ==>=<面数为r ，则2=+-r e v (结点数与面数之和＝边数＋2)(定理7)
(3)平面图633,,,,-≤≥==>= 判定条件：图G 是平面图的充分必要条件是G 不含与K 3，3或K 5在2度结点同构的子图. 4. 树 树 连通无回路的无向图. 树的判别 图m E n V E V T ==>=<,,,,T 是树的充分必要条件是(六个等价定义) (定理14): (1) T 是无回路的连通图； (2) 图T 无回路且m ＝n －1； (3) 图T 连通且m ＝n －1 (4) 图T无回路，若增加一条边，就得到一条且仅一条回路； (5) 图T连通，若删去任一边，G则不连通； (6) 图T的每一对结点之间有一条且仅有一条通路. 生成树图G的生成子图是树，该树就是生成树. 权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权，记作W(T). 最小生成树带权最小的生成树. 有向树有向图删去边的方向为树，该有向图就是有向树. 根树与树根非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树. 每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树). 哈夫曼树用哈夫曼算法得到的最优二叉树. 4. 有关树的求法 生成树的破圈法和避圈法求法； 最小生成树的克鲁斯克尔求法； 哈夫曼树的哈夫曼求法. 离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论 离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素； 7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}} 习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ → （4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ） 习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1. （2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表： 第一章部分课后习题参考答案 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 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，所以这一段的论述为真。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）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p) 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学第四版课后答案 第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9）， （10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： 全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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 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，所以这一段的论述为真。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 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列, 并给出各命题的: (1)2+2＝4 当且仅 当3+3＝6. (2)2+2＝4 的充要 条件是3+3 6. (3)2+2 4 与3+3 ＝6 互为充要条件. (4)若2+24, 则 3+36, 反之亦然. (1)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. (2)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (3) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (4) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p q 1. (2) q p 1. (3) p q 1. (4) p r 当p 0 时为真; p 1 时为假. 1.14．将下 列 . (1) 刘 晓月跑得快, 跳得高. (2) 老王是山东 人或河北人. (3)因为天气冷, 所以我穿了羽 绒服. (4)王欢与李乐组成一个 小组. (5)李辛与李末是兄弟. (6)王强与刘威都学 过法语. (7)他一面 吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他 迟到了. (12)2 与4 都是素数, 这是不对的. (13)“2或4 是素数, 这是不对的”是不对的. 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 证明 设A 上定义的二元关系R 为： ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ① 对任意＜x,y ＞∈A ，因为x y =x y ，所以 ＜＜x,y ＞, ＜x,y ＞＞∈R 即R 是自反的。 ② 设＜x,y ＞∈A ，＜u,v ＞∈A ，若 ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ?u v =x y ?＜＜u,v ＞,＜x,y ＞＞∈R 即R 是对称的。 ③ 设任意＜x,y ＞∈A ，＜u,v ＞∈A ，＜w,s ＞∈A ，对 ＜＜x,y ＞, ＜u,v ＞＞∈R ∧＜＜u,v ＞, ＜w,s ＞＞∈R ?（x y =u v ）∧（u v =w s ）?x y =w s ?＜＜x,y ＞, ＜w,s ＞＞∈R 故R 是传递的，于是R 是A 上的等价关系。 3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使 第十四章 图的基本概念 1. 设9阶无向图G 中，每个顶点的度数不是5就是6，证明G 中至少有5个6 度顶点或至少有6个5度顶点。 证明：由握手定理，顶点的度数之和为偶数，则5度的顶点度数之和必为偶数， 所以5度顶点的个数只能是0，2，4，6，8。而与之对应的6度顶点的个数为9，7，5，3，1。可以看出G 中至少有5个6度顶点或至少有6个5度顶点。 2．设G 是n 阶无向简单图，n ≥3且为奇数，证明G 与G -中奇度顶点的个数 相等。 证明：因为n 为奇数，所以n 阶无向完全图的每个顶点的度数都是偶数。设G 中有m 个奇度顶点，则在G -中和这m 个顶点对应的m 个顶点也必定是奇度顶点，因为偶数－奇数＝奇数。而G -中与G 中余下的n-m 个偶度顶点相对应的顶点也必定是偶数顶点，因为偶数－偶数＝偶数。 因此，G 与G - 中奇度顶点个数相等。 3. 设G 是n 阶自补图，证明n=4k 或n=4k+1,其中k 为正整数。 证明：由握手定理知2m=n(n-1)/2, 即4m=n(n-1)。m 是正整数，所以n 和n-1两 者必有一个是4的倍数，所以n=4k 或n=4k+1。 4．若无向图G 中恰有两个奇度顶点，证明这两个奇度顶点必然连通。 证明：每一个连通分支都是一个单独的图，而图的奇度顶点是偶数个，所以图G 中的两个奇度顶点必在同一连通分支内，所以这两个奇度顶点必然连通。 5．判断：存在7个结点的自补图。（选自离散数学典型题解析与实战模拟） 答：假设存在7个结点的自补图G ，则G 与它的补图G -同构，并且，G G -＝7k 。 但是7k 中有21条边，为一个奇数，所以这两个图的边数一定一奇一偶，不可能相等，于是假设不成立。 6. 设简单图G 连通，其每个结点的度均为偶数。证明对于任一结点v ，图G-v 的连通分支数不大于v 的度数的一半（选自离散数学典型题解析与实战模拟） 第十四章图的基本概念 14.1 图 (2) 一．无向图与有向图 (2) 1．无序积与多重集 (2) 2．无向图与有向图的定义及表示法 (2) 二．简单图与多重图 (4) 1．顶点的度数 (5) 2．握手定理 (5) 四．图的同构 (8) 1．两图同构的定义 (8) 2．图之间的同构关系是等价关系 (8) 五．完全图与正则图 (9) 1．完全图 (9) 2．正则图 (9) 六．子图与补图 (9) 1．子图 (9) 2．补图与自补图 (12) 14.2 通路与回路 (15) 一．通路与回路的定义 (15) 二. n阶图中通路与回路的性质 (17) 14.3 图的连通性 (17) 一、无向图的连通性 (17) 二、无向图中顶点之间的线程线及距离 (18) 三、无向图的连通度 (18) 四、有向图的连通性及其分类 (20) 五、扩大路径法及极大路径 (21) 六、二部图及判别定理 (22) 14.4 图的矩阵表示 (26) 一、无向图与有向图的关联矩阵 (26) 二、有向图的邻接矩阵 (27) 三、有向图的可达矩阵 (29) 典型习题 (29) 14.5 图的运算 (33) 14.1 图 主要内容 无向图与有向图。 简单图与多重图。 顶点的度数与握手定理。 图的同构。 完全图与正则图。 子图与补图。 学习要求 熟练掌握握手定理及其推论的内容及其应用。 掌握图同构的概念。 加深对简单图、完全图、正则图、子图、补图等概念的理解。 一．无向图与有向图 1．无序积与多重集 设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B. 为方便起见，将无序积中的无序对{a,b}记为(a,b),并且允许a=b.需要指出的是，无论a,b是否相等，均有(a,b)=(b,a),因而A&B=B&A. 元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1. 2．无向图与有向图的定义及表示法 定义14.1一个无向图是一个有序的二元组 第十四章图的基本概念 1.设9阶无向图G中，每个顶点的度数不是5就是6，证明G中至少有5个6度顶点或至少有6个5度顶点。 证明： 由握手定理，顶点的度数之和为偶数，则5度的顶点度数之和必为偶数，所以5度顶点的个数只能是0，2，4，6，8。而与之对应的6度顶点的个数为9，7，5，3，1。可以看出G中至少有5个6度顶点或至少有6个5度顶点。 2．设G是n阶无向简单图，n3且为奇数，证明G与G中奇度顶点的个数相等。 证明： 因为n为奇数，所以n阶无向完全图的每个顶点的度数都是偶数。设G中有m个奇度顶点，则在G中和这m个顶点对应的m个顶点也必定是奇度顶点，因为偶数－奇数＝奇数。而G中与G中余下的n-m个偶度顶点相对应的顶点也必定是偶数顶点，因为偶数－偶数＝偶数。 因此，G与G中奇度顶点个数相等。 3.设G是n阶自补图，证明n=4k或n=4k+1,其中k为正整数。 证明： 由握手定理知2m=n(n-1)/2,即4m=n(n-1)。m是正整数，所以n和n-1两者必有一个是4的倍数，所以n=4k或n=4k+1。 4．若无向图G中恰有两个奇度顶点，证明这两个奇度顶点必然连通。 证明： 每一个连通分支都是一个单独的图，而图的奇度顶点是偶数个，所以图G 中的两个奇度顶点必在同一连通分支内，所以这两个奇度顶点必然连通。 5．判断： 存在7个结点的自补图。（选自离散数学典型题解析与实战模拟）答： 假设存在7个结点的自补图G，则G与它的补图G同构，并且，G G＝k 7。 但是k 7中有21条边，为一个奇数，所以这两个图的边数一定一奇一偶，不可能相等，于是假设不成立。 6.设简单图G连通，其每个结点的度均为偶数。证明对于任一结点v，图G-v的连通分支数不大于v的度数的一半（选自离散数学典型题解析与实战模拟）证明： 由于简单图G中每个结点的度均为偶数，所以G-v中奇结点的数目等于v 的度数，并且原来与v相邻。由于G是连通的，所以G-v的每个连通分支中都有原来在G中与v相邻的结点。然而，G-v的每个连通分支都可以看作是一个完整的图，所以每个分支中原来与v相邻的结点至少有两个，并且不同的连通分支中没有公共的奇结点，所以G-v的连通分支数不大于奇结点数目的一半，也就是v的度数的一半。 7．设V(G),E(G)分别为无向图G的结点集合和边的集合，记W(G)为图G的连通分支数，证明对于E(G)中任意的e，有W(G)W(G-e)W(G)+1。（选自离散数学典型题解析与实战模拟） 证明： 由于图G-e中分支数目为W(G-e)个，而G可以通过G-e增加一条边得到，所以G不外乎以下两种情况： （1）e的两个端点处在G-e的同一连通分支当中： 这时，不会增加连通分支的数目，于是W(G-e)＝W(G)。 （2）e的两个端点分别处于G-e的两个连通分支当中，这时G-e的两个连通分支将与e一起合并成G的一个连通分支，于是W(G-e)=W(G)+1。 习题3.7 1. 列出关系}6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。 解 }6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z ,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><= ><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,1 2. 列出二维表 3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。 表3.18 航班信息 航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 322 34 底特律 09:44 解 略 3. 当施用投影运算5,3,2π到有序5元组>离散数学第三版课后习题答案
离散数学课后习题答案
离散数学习题解答
屈婉玲版离散数学课后习题答案【1】
离散数学课后习题答案(左孝凌版)
离散数学课后答案
离散数学第四版课后标准答案
最新离散数学习题答案
离散数学及答案
离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
离散数学最全课后答案(屈婉玲版)
离散数学习题详细答案
离散数学课后习题答案_(左孝
离散数学图的练习
离散数学结构 第14章 图的基本概念
离散数学图的练习
离散数学课后习题答案二
相关主题
文本预览