4、“所有的合数是可数集合”，这个说法是否正确？

5、“所有的无理数是不可数集合",这个说法是否正确？

第三章 命题逻辑 （第一部分）

命题逻辑第一部分单元测验

4、可满足公式的否定是不可满足的，也就是永假公式

5、在命题逻辑中，符号和的含义是相同的。

6、重言式的否定是_______公式。

第三章 命题逻辑 （第二部分）

命题逻辑第二部分单元测验

5、使用间接证明法进行演绎法推理的时候，是把结论的否定作为附加前提引入，然后推导出一个矛盾式。

6、自然演绎法的三个基本的推理规则是P,T和_________。（用字母缩写表示）

第四章 谓词逻辑 （第二部分）

谓词逻辑第二部分单元测验

3、在谓词逻辑的推导过程中，如既要使用规则US 又要使用规则ES 消去量词，而且选用的个体是 同一个符号，则必须先使用规则ES，再使用规则US。

4、在谓词推理过程中，若需消去量词，可以引用规则US 和规则ES。

5、在谓词推理过程中，如一个变量是用规则ES 消去量词，对该变量在添加量词时，则只能使用规则_____?(只能填写US\ES\UG\EG这四种)

第四章 谓词逻辑 （第一部分）

谓词逻辑第一部分单元测验

4、谓词公式中，量词的辖域是。

5、谓词公式中，变元y既是自由变元，又是约束变元。

6、设论域为{1,2},A(x):x是素数，则公式的真值是（ ）。（必须填0或1）

7、设论域为整数集，则表达式的真值为（）。（必须填0或1）

6、若集合A中有三个元素，则A上共有多少个不同的二元关系？（必须是准确的数值，不能用表达式）

第七八章 特殊关系和函数

特殊关系和函数单元测验

5、设，上的等价关系，则对应于的的划分是(

$已知图G中有30个结点，每个结点的度数均为3，问G中有多少条边？ $

$5阶无向完全图的边数为()？ $

$下面四组数能构成无向图的度数列的有() ？$

$在有n个结点的连通图中，其边数() $

$在如下的有向图中，从V_1到V_4长度为3 的通路有()条 $

$ 在下列关于图论的命题中，为真的命题是()$

$完全二分（部）图K_{m,n}的邻接矩阵有多少行？ $

$ 一个连通平面图共有9个结点，它们的度数分别为：2,2,2,3,3,3,4,5,6，这个图共有()个面$

$对C_n(n为奇数)图的结点着色，最少用几种颜色？ $

$ 在下图中，()是半欧拉图。$

$下面的各图中, ( )是强连通？ $

$一个树有2个4度结点，3个3度结点，其余结点都是叶子，这棵树有多少片树叶? $

$下面给出的各符号串集合，哪个是前缀码？ $

$下面哪一种图不是树？ $

$设G是一个哈密顿图，则G一定是? $

$设T是如下的二元树T，下面()是对T先根遍历访问所有点的顺序？ $

B  若两个图同构，它们的对偶图也同构。错。

D  一棵完全二元树，必有奇数个结点。

A  $ 设e是无向连通图G中的一条边,e不在G的任何生成树中，则e一定是环。 $

C  $ 一个有向图G，仅有一个结点入度为0，其余所有结点入度均为1，G一定是根树。 $

D  $ 已知n阶m条边的无向图G，要求G的一棵生成树，则要删去G中的m-n条边 $

获取标准答案请阅读全文

《离散数学复习(08)》由会员分享，可在线阅读，更多相关《离散数学复习(08)（20页珍藏版）》请在人人文库网上搜索。

1、Ch1命题逻辑命题逻辑数理逻辑：研究一种形式语言，其本质是将数理逻辑：研究一种形式语言，其本质是将数学中的逻辑证明加以数学中的逻辑证明加以符号化符号化，因而推动各，因而推动各数学分支的迅速发展。数学分支的迅速发展。命题：表示判断的具有确定真值的陈述句。命题：表示判断的具有确定真值的陈述句。 命题只要能判断真假，不一定已知真假命题只要能判断真假，不一定已知真假 非陈述性语句不是命题非陈述性语句不是命题 方程不是命题方程不是命题 悖论不是命题悖论不是命题联结词联结词 否定否定 合取合取 析取：析取： 条件条件 双条件双条件 翻译提示：翻译提示： 不可兼或：不可兼或： (P Q ) 当当 P则则Q(

2、如果如果P，那么，那么Q) : P Q P仅当仅当 Q(仅当仅当Q，则，则P) : P Q 除非除非P否则否则Q： P P Q Q 只要，就有：只要，就有： P P Q Q 只有，才能：只有，才能： Q Q P P 定义一般翻译为定义一般翻译为双条件双条件优先级：优先级：高高低低1、只有你主修计算机科学或者不是新生，才能从校园内、只有你主修计算机科学或者不是新生，才能从校园内 访问因特网。访问因特网。2、除非你已满、除非你已满16周岁，否则只要你身高不足周岁，否则只要你身高不足4英尺就不英尺就不能乘公园滑行铁道。能乘公园滑行铁道。3、只要充分考虑一切论证，就能得到可靠见解。、只要充分考虑一切论

3、证，就能得到可靠见解。4、只有充分考虑一切论证，才能得到可靠见解。、只有充分考虑一切论证，才能得到可靠见解。5、我们不能既唱歌又看书。、我们不能既唱歌又看书。6、如果天下雨，我出不出去看你是否同意而定。、如果天下雨，我出不出去看你是否同意而定。7、我唱歌，仅当你伴奏。、我唱歌，仅当你伴奏。8、或者你没有给我写信，或者信在路上丢失了。、或者你没有给我写信，或者信在路上丢失了。9、如果天下雨，我就在家看书，否则我就去看电影。、如果天下雨，我就在家看书，否则我就去看电影。10、只有你考试不及格或者缺考，才能参加补考。、只有你考试不及格或者缺考，才能参加补考。11、除非你缺考，否则只要你考试不满、除非

A(BF) 原子命题拆成：原子命题拆成：客体客体 谓词谓词 全称量词全称量词“ ”，存在量词存在量词“ ”翻译注意：翻译注意： 特性谓词的位置：在特性谓词的位置：在全称量词全称量词的作用域内作的作用域内作条件条件句

5、的前件句的前件，在，在存在量词存在量词的作用域内作的作用域内作合取项合取项。1、所有的人都犯错误。、所有的人都犯错误。2、有且仅有一个偶质数。、有且仅有一个偶质数。3、有些人对所有酒都感兴趣。、有些人对所有酒都感兴趣。4、所有的人都对某些酒感兴趣。、所有的人都对某些酒感兴趣。5、尽管有人可恶，但并不是所有的人都可恶。、尽管有人可恶，但并不是所有的人都可恶。6、对于任意实数，存在更大的实数。、对于任意实数，存在更大的实数。7、某些火车比所有飞机慢，但至少有一架飞机比所有火车快。、某些火车比所有飞机慢，但至少有一架飞机比所有火车快。 8、并非所有的人都喜欢喝酒。、并非所有的人都喜欢喝酒。Ch2谓词

6、逻辑谓词逻辑量化断言与命题的关系量化断言与命题的关系假设个体域假设个体域D=a1, a2，an( x) (P(x) P(a1) P(a2) P(an)( x)(P(x) P(a1) P(a2) P(an)谓词演算的推理理论谓词演算的推理理论消去、添加量词规则消去、添加量词规则 全称指定全称指定 US 全称推广全称推广 UG 存在指定存在指定 ES 存在推广存在推广 EG在谓词推理中，必须注意的两点：在谓词推理中，必须注意的两点： 不能在量词的作用域内使用等价式和蕴含式不能在量词的作用域内使用等价式和蕴含式 在同一证明中，若既要使用存在指定，又要使用全称在同一证明中，若既要使用存在指定，又要使用

7、全称指定，则先用存在指定，后用全称指定。指定，则先用存在指定，后用全称指定。谓词推理理论谓词推理理论 P规则、规则、T规则、规则、 US、UG、ES、EG证明方法：直接证法证明方法：直接证法 反证法反证法 CP规则规则1、( x)(P(x) Q(x) ( x)P(x) ( x)Q(x)2、( x)A(x) ( x)B(x) ( x)(A(x) B(x) 3、( x)P(x) (

(绝对绝对补补)、 ( (对称差对称差) 运算的性质运算的性质 序偶与笛卡儿积序偶与笛卡儿积1、若、若C ， 则则 AB ACBC 2、设、设A,B为两个集合，若为两个集合，若AB ，则，则 (AB)(AB)(AA)(BB)3

9、、证明、证明 P(A)P(B)=P(AB) 4、设A和和B是论域是论域E的子集，的子集，B= A A B=E A B= 关系性质的证明方法：关系性质的证明方法： 要证明要证明R R在在X X上自反上自反 假设假设 x xX X ，证出，证出 R 要证明要证明R R在在X X上对称上对称 对对 x,x,y y X,X,设设R ，证出，证出 R 要证明要证明R R在在X X上传递上传递 对对 x,y,zX,x,y,zX,设设R R ，证出，证出 R 要证明要证明R R在在X X上反自反上反自反 假设假设 x xX X，证出，证出 R ） 要证明要证明R R在在X X上反对称上反对称 对对 x,x,

10、y yX X，设，设RR ，证出，证出 x xy y 关系的性质关系的性质自反、对称、自反、对称、传递、反自反、传递、反自反、反对称反对称关系的关系的的运算：的运算： 、 、( (相对补相对补) )、 ( (绝对补绝对补)、 ( (对称差对称差) 关系的复合、关系的复合、关系的逆、关系的闭包运算关系的逆、关系的闭包运算集合的划分与覆盖集合的划分与覆盖划分可以确定一个等价关系划分可以确定一个等价关系覆盖可以确定一个相容关系覆盖可以确定一个相容关系等价关系与等价类及其性质等价关系与等价类及其性质序关系序关系偏序关系、哈斯图、极大元、极小元、最大元、偏序关系、哈斯图、极大元、极小元、最大元、最小元、

11、最小元、上界、下界、上确界、下确界上界、下界、上确界、下确界1、设、设R是集合是集合X上的一个自反关系。则上的一个自反关系。则R是对称和传递的，当是对称和传递的，当 且仅当且仅当RR，有，有在在R之中。之中。2、若关系、若关系R和和S在集合在集合X上是等价的，证明上是等价的，证明RS也是等价的。也是等价的。3、如果关系如果关系R在集合在集合X上是等价的，证明上是等价的，证明Rc也是等价的。也是等价的。4、设、设R是集合是集合A上的等价关系，则对于所有上的等价关系，则对于所有a,b A ，或者，或者 aR=bR或者或者aR bR= 。5、设集合设集合A有一个划分有一个划分S=S1,S2,Sm，试

12、由此划分确定一，试由此划分确定一 个等价关系。个等价关系。6、设、设S是是X上的二元关系，上的二元关系，S是传递的当且仅当是传递的当且仅当S S S。7、设、设R是是X上的二元关系，则上的二元关系，则: a）R是对称的，当且仅当是对称的，当且仅当R=Rc b）R是反对称的，当且仅当是反对称的，当且仅当R R c Ix函数函数 函数的概念函数的概念 入射、满射、双射入射、满射、双射 逆函数逆函数(当当f 是是双射双射函数时逆函数才有意义。函数时逆函数才有意义。) 复合函数复合函数(注意写法与关系的复合不同。注意写法与关系的复合不同。) 求求go of时，若时，若ranf 不包含于不包含于 dom

13、g，则，则go of为空为空1、令、令gof是一个复合函数，则是一个复合函数，则 (1)若若g 和和f 是满射的是满射的,则则 gof 是满射的；是满射的； (2)若若g 和和f 是入射的是入射的,则则 gof 是入射的；是入射的； (3)若若g 和和f 是双射的是双射的,则则 gof 是双射的。是双射的。2、令、令gof是复合函数，则是复合函数，则 (1)若若gof 是满射的是满射的,则则g是满射的；是满射的； (2)若若gof 是入射的是入射的,则则f是入射的；是入射的； (3)若若gof 是双射的是双射的,则则g是满射的，是满射的，f是入射的。是入射的。Ch5 代数系统代数系统 运算的性

14、质运算的性质(封闭性、交换性、结合性、分配律、吸收封闭性、交换性、结合性、分配律、吸收律、等幂律律、等幂律) 特殊的元素特殊的元素(幺元、零元、逆元幺元、零元、逆元) 广群、半群、独异点、群和子群广群、半群、独异点、群和子群 阿贝尔群和循环群阿贝尔群和循环群设设是一个半群，如果是一个半群，如果S是一个有限集，则必有是一个有限集，则必有对于对于 b S , b*b S，记，记b2=b*b b2*b=b*b2 S，记，记b3=b2*b=b*b2 由于由于S是有限集，所以必存在是有限集，所以必存在 ji，使得，使得bi=bj 证明方法举例：证明方法举例：证明证明a是是b的逆元的逆元? a * b=

15、b * a =e例如：例如：(a * b)-1=b-1 * a-1 群中满足消去律群中满足消去律 群中不可能有零元。群中不可能有零元。 任何一个循环群必定是阿贝尔群。任何一个循环群必定是阿贝尔群。 群群中的幺元中的幺元 e 必定也是其子必定也是其子群群中的幺元。中的幺元。 子群的判定定理：当是子群的判定定理：当是有限集有限集： *在上封闭在上封闭 当是当是无限集无限集： a，bS， 有有a*b-1S 任何质数阶的群必定是循环群。任何质数阶的群必定是循环群。陪集与拉格朗日定理陪集与拉格朗日定理设设是群是群 的一个子群，的一个子群，aG，则集合，则集合 aH称为由称为由a所确所确定的定的H在在G中

16、的左陪集，记为中的左陪集，记为aH。拉格朗日定理。拉格朗日定理。1、设、设是一个半群，如果是一个半群，如果S是一个有限集，则必有是一个有限集，则必有aS，使，使得得a*a=a。2、设、设是一个群，是一个群，B是是G的非空子集，如果的非空子集，如果B是一是一 个有限集，个有限集，那末只要运算那末只要运算*在在B上封闭，上封闭，必定是必定是的子群。的子群。3、设、设是群，是群，S是是G的非空子集，如果对于的非空子集，如果对于S中的中的 任意元素任意元素a和和b有有a*b-1S，则，则是是的子群。的子群。4、设、设是有限的可交换独异点，且对任意的是有限的可交换独异点，且对任意的a,b,cS，等式，等

17、式 a*b=a*c 蕴含着蕴含着 b = c，证明，证明是阿贝尔群。是阿贝尔群。5、设、设是一个群，是一个群，是阿贝尔群的充要条件是阿贝尔群的充要条件 是对任意是对任意的的a,bG，有，有(a*b)*(a*b)=(a*a)*(b*b)6、设、设是群是群的子群，的子群， A=x|xG , x*H*x-1=H，证明，证明是是的一个子群。的一个子群。7、设、设是群是群的子群，的子群， aH和和bH是是H在在G中的任意中的任意两个左陪集，证明：或者两个左陪集，证明：或者aH=bH，或者，或者aHbH=。 8、若、若是半群，是半群，e是左幺元且对每一个是左幺元且对每一个xA，存在，存在x1A使得使得x1

18、 * x = e。 a)证明：对于任意的证明：对于任意的a，b，cA，如果，如果a*ba*c，则，则bc。 b)通过证明通过证明e是是中的幺元，证明中的幺元，证明是群。是群。9、证明：循环群的同态象必定是循环群。、证明：循环群的同态象必定是循环群。 每个图中每个图中结点度数结点度数的总和等于的总和等于边数边数的两倍。的两倍。 deg(v)= 2|E|deg(v)= 2|E| 在任何有向图中，所有结点的出度之和等于所有结点的在任何有向图中，所有结点的出度之和等于所有结点的入度之和。入度之和。 无向图的连通性无向图的连通性:连通性是结点集合上的一种连通性是结点集合上的一种等价关系等价关系。 点割集

19、、边割集点割集、边割集 有向图的可达性：强连通有向图的可达性：强连通=单侧连通单侧连通弱连通弱连通 强分图、单侧分强分图、单侧分图、图、弱分图弱分图在有向图在有向图G=中，它的每一个结点位于且只位于一中，它的每一个结点位于且只位于一个强分图中。个强分图中。Ch7 图论图论欧欧拉图与汉密尔顿图拉图与汉密尔顿图 给定给定无孤立结点图无孤立结点图G ，若存在一条回路，经过图中的，若存在一条回路，经过图中的每边一次且仅一次，该回路为每边一次且仅一次，该回路为欧拉回路欧拉回路。具有。具有欧拉回欧拉回路路的图，称为的图，称为欧拉图欧拉图。 无向图无向图G具有一条具有一条欧拉回路欧拉回路当且仅当当且仅当G是

20、是连通连通的，且的，且所所有结点度数全为偶数有结点度数全为偶数。 给定图给定图G G，若存在一条回路，经过图中每个结点恰好一，若存在一条回路，经过图中每个结点恰好一次，这条回路称为次，这条回路称为汉密尔顿回路汉密尔顿回路。具有具有哈密尔顿回路哈密尔顿回路的图，称为的图，称为汉密尔顿图汉密尔顿图。平面图平面图 一个有限平面图，面的次数之和等于其边数的两倍。一个有限平面图，面的次数之和等于其边数的两倍。 设有一个连通的平面图设有一个连通的平面图G，共有，共有v个结点个结点e条边和条边和r个面，个面，则欧拉公式则欧拉公式vr成立。成立。 设是一个有个结点条边的设是一个有个结点条边的连通连通简单简单平面图平面图， 若若v3，则，则v。树与生成树树与生成树一个一个连通且无回路连通且无回路的无向图称为的无向图称为树树。一个无回路的无向图称作一个无回路的无向图称作森林森林任一树中任一树中e=v-1任一棵树中至少有两片树叶。任一棵树中至少有两片树叶。连通图至少有一颗生成树。连通图至少有一颗生成树。以下关于树的定义是等价的。以下关于树的定义是等价的。 无回路的连通图。无回路的连通图。 无回