离散数学网上作业题
- 格式：doc
- 大小：809.00 KB
- 文档页数：16
三、回答问题
完全图 是否是欧拉图？是否是哈密尔顿图？为什么？
四、画图
对于下图，利用克鲁斯克尔算法求一棵最小生成树。
五、计算
一棵树有两个结点度数为2，1个结点度数为3，3个结点度数为4，其余结点度数为1。问该树有几个度数为1的结点。
六、证明
是无向简单图，其中 ，证明： 。
证明因为 是简单图，所以图 中没有环和平行边，任意两结点间最多有一条边，故 。
证明：f是<G，>到<G，>的自同构。
复习题七
一、证明
1、对任意两个集合 ，证明
2、构造下面命题推理的证明
如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，因此我热衷与玩游戏机。
二、计算
1、画一个有一条欧拉回路和一条汉密顿回路的图。
2、设 ，求公式：
的真值。
3一棵树有 个结点度数为2， 个结点度数为3，…， 个结点度数为k，问它有几个度数为1的结点。
五、设复数集合 ，定义 ： 当且仅当 ，证明： 为等价关系。
六、证明：若 。
七、设集合 ， 是普通乘法，证明： 是一个群。
八、设实数集合R，+和x是普通加法和乘法，定义映射 ， ，证明 的单一同态。
复习题五
一、填空
1、实数集合R（是/不是）可数的。
2、设A和B为有限集，|A|=m，|B|=n，则有个从A到B的关系，有个从A到B的函数，其中当mn时有个入射，当m=n时，有个双射。
五、设正整数集合 上的二元关系 ，证明： 为等价关系。
六、证明：若 。
七、设集合 ， 是普通乘法，证明： 是一个群。
八、设正实数集合R+和实数集合R，+和x是普通加法和乘法，定义映射 ， ，证明 的同构。
复习题六
一、求公式q∧(p∨┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明：
10．若连通图 ，其中 ，则要删去G中（）条边，才能确定G的一棵生成树。
A． B． C． D．
二．填空题
11．公式 的对偶式为。
12．子集公理的逻辑表达式为。
13．设集合A= {a,b,c,d}，A上的二元关系R= {<a,b>,<b,d>,<c,c>,<c,d>}，那么Dom(R) =，Ran(R) =。
A．集合上 的关系如果不是自反的，就一定是反自反的；
B．若关系 都是反自反的，那么 必也为反自反的；
C．若关系 都是自反的，那么 必也为自反的；
D．每一个全序集必为良序集.
4．下列结论中不正确的结论是：（）
A．三个命题变元的布尔小项 的编码是 ；
B．三个命题变元的布尔大项 的编码是 ；
C．任意两个不同的布尔小项的合取式必为永假式；
2证明 是偏序集。
3画出偏序集 的哈斯图。
4在 上定义两个二元运算 和 ：对任意 ， ， 。请填空（在横线上填是或不是并回答为什么）：
代数系统 格，因为。
代数系统 有界格，因为。
代数系统 有补格，因为。
代数系统 分配格，因为。
代数系统 布尔代数，因为。
二、计算
设 是布尔代数 上的一个布尔表达式。试写出 的析取范式和合取范式（用列函数表的方法）。
三、画出满足下列要求的图
有一条欧拉回路和一条汉密尔顿回路。
有一条欧拉回路但没有汉密尔顿回路。
没有欧拉回路但有汉密尔顿回路。
既没有欧拉回路也没有汉密尔顿回路。
四、证明在完全二叉树中，边的总数等于2(n-1)，这里n是叶子数。
五、计算
求带权2、3、5、7、11、13的最优二叉树。
六、证明
在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。
前提(x)(F(x)∧S(x))→(y)(M(y)→W(y))，(y)(M(y)∧┐W(y))
结论(x)(F(x)→┐S(x))
三、计算题
1.证明逻辑等价式A→(A→B)A→B成立。
2.对任意集合A，B，C，证明：（A - B）B = AB
3.设二元关系R={<{a},b>,<a,b>, <b,c>}求：
(1) dom R
(2) ran R
(3) RοR
4.求集合A={<p,q>|p,q都是整数}的势。
5.在20名青年中有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。
四、假设给定了正整数的序偶集合A，在A上定义二元关系R如下：<<x,y>,<u,v>>R,当且仅当xv=yu，证明R为等价关系。
完成下列各小题。
1、证明 是 上的偏序关系。
2、画出偏序集 的哈斯图。
3、在 上定义两个二元运算 和 ：对任意 ， ， 。请填空（在横线上填是或不是）：
代数系统 格。 代数系统 有界格。
代数系统 有补格。 代数系统 分配格。
二、求布尔函数的析取范式和合取范式
设 是布尔代数 上的一个布尔表达式。试写出 的析取范式和合取范式（用推导法或列函数表的方法均可）。
D．任意两个不同的布尔大项的合取式必为永假式.
5．设集合A和二元运算*，可交换的代数运算是（）。
A．设
B．设
C．设 ，运算 是矩阵的乘法
D．设
6．以下命题中不正确的结论是（）
A．素数阶群必为循环群；B．Abel群必为循环群；
C．循环群必为Abel群D．4阶群必为Abel群.
7．设代数系统 和 ，存在映射 ，如果 ，都有（），称K1与K2同态。
2、求 。
六、设<G，>为一群。证明：
（1）若对任意aG有a2=e，e为幺元，则G为阿贝尔群。
（2）若对任意a，bG有(ab)2=a2b2，则G为阿贝尔群。
七、设N4=｛0，1，2, 3｝，f：N4→N4定义如下：
令F = {f0,f1,f2,f3}，其中f0为N4上恒等函数。给定一代数结构<F,ο>，且 （这里ο为函数合成运算，+4为模4加运算）。
4设集合 上的关系 ，求出它的自反闭包，对称闭包和传递闭包。
三、设 上的整除关系 ， 是否为 上的偏序关系？若是，则：
1、画出 的哈斯图；2、求 的极大值和 的极小值。
四、用推导法求公式 的主析取范式和主合取范式。
五、设自然数集 上的关系 定义为： ，
证明： 是 上的等价关系。
六、设 分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数 为 ，证明 的同构映射。
五、给出偏序集<A, R>上偏序关系R的关系图（如下图所示）。
（1）求偏序集<A, R>的哈斯图。
（2）指出A的最大、最小元（如果有的话），极大、极小元。
六、设<G，>为群。若在G上定义二元运算о,使得对任何元素x，yG，有
xоy = yx。
证明<G，о>也是群
七、设<G，>为群,a为G中给定元素。定义函数f：G→G，使得对每一xG有f(x)=axa-1
2、求 。
四、用推导法求公式 的主析取范式和主合取范式。
五、设实数集 上的关系 ，
证明： 是 上的等价关系。
六、设 分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数 为 ，证明 的同构映射。
七、设 是实数集合， ，在 上定义二元运算 为： ，试证明 是一个群。 是否阿贝尔群？
复习题二
一、设上的整除关系
七、设 是整数集合，＋是普通加法，试证明 是一个群。 是否循环群？
复习题八
一、求公式(┐p∨┐q)→(p┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明：
前提(x)P(x)→(x)((P(x)∨Q(x))→R(x))，(x)P(x)，(x)Q(x)
结论(x)(y)(R(x)∧R(y))
试证
七、证明
设 是有限字母表，给定代数系统 ，其中 是串的连接运算。对于任一串 ，建立 到 的映射 ， 。证明 是 到 的一个满同态，且当 时， 是同构映射。
八、应用
给定有限状态机 ，它的状态图如附图所示。
1、求状态 的011010的后继以及可接受状态序列。
2、求 对于激励010110的响应。
3、构造一台与 相似的转换赋值机 ，画出 的状态图。
(3)画一个没有欧拉回路但有一条汉密顿回路的图
2、设 ，求公式：
的真值。
3、一棵树有 个结点度数为2， 个结点度数为3，…， 个结点度数为k，问它有几个度数为1的结点。
4、设集合 上的关系 ，求出它的自反闭包，对称闭包和传递闭包。
三、设 上的整除关系 ，
是否为 上的偏序关系？若是，
则：1、画出 的哈斯图；
19．给定平面图G，如下图所示，则G的面数为，G中面的总次数为。
20．若二部图 为完全二部图，则其边数为
三．计算题(一)
21．符号化下述两个语句，并说明其区别：
（1）如果天不下雨，我们就去旅游；（2）只有不下雨，我们才去旅游。
A． B．
C． D．
8．图G有21条边，3个4度结点，其余均为3度结点，则G有（）个结点。
A．13 B．15 C．17 D．19
9．以下命题中正确的结论是（）
A． 时，完全图 必为欧拉图
B．如果一个连通图的奇结点的个数大于2，那么它可能是一个Euler图；
C．一棵树必是连通图，且其中没有回路；
D．图的邻接矩阵必为对称阵.
三、计算题
1.证明逻辑等价式AB(A∧B)∨(┐A∧┐B)成立。
2.设AB，求证A∩CB∩C。
3.设集合A={a，b，c，d}，A上的关系R={<b,b>,<a,b>,<c,b>,<d,c>}，求R的自反闭包、对称闭包。
完全图 是否是欧拉图？是否是哈密尔顿图？为什么？
四、画图
对于下图，利用克鲁斯克尔算法求一棵最小生成树。
五、计算
一棵树有两个结点度数为2，1个结点度数为3，3个结点度数为4，其余结点度数为1。问该树有几个度数为1的结点。
六、证明
是无向简单图，其中 ，证明： 。
证明因为 是简单图，所以图 中没有环和平行边，任意两结点间最多有一条边，故 。
证明：f是<G，>到<G，>的自同构。
复习题七
一、证明
1、对任意两个集合 ，证明
2、构造下面命题推理的证明
如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，因此我热衷与玩游戏机。
二、计算
1、画一个有一条欧拉回路和一条汉密顿回路的图。
2、设 ，求公式：
的真值。
3一棵树有 个结点度数为2， 个结点度数为3，…， 个结点度数为k，问它有几个度数为1的结点。
五、设复数集合 ，定义 ： 当且仅当 ，证明： 为等价关系。
六、证明：若 。
七、设集合 ， 是普通乘法，证明： 是一个群。
八、设实数集合R，+和x是普通加法和乘法，定义映射 ， ，证明 的单一同态。
复习题五
一、填空
1、实数集合R（是/不是）可数的。
2、设A和B为有限集，|A|=m，|B|=n，则有个从A到B的关系，有个从A到B的函数，其中当mn时有个入射，当m=n时，有个双射。
五、设正整数集合 上的二元关系 ，证明： 为等价关系。
六、证明：若 。
七、设集合 ， 是普通乘法，证明： 是一个群。
八、设正实数集合R+和实数集合R，+和x是普通加法和乘法，定义映射 ， ，证明 的同构。
复习题六
一、求公式q∧(p∨┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明：
10．若连通图 ，其中 ，则要删去G中（）条边，才能确定G的一棵生成树。
A． B． C． D．
二．填空题
11．公式 的对偶式为。
12．子集公理的逻辑表达式为。
13．设集合A= {a,b,c,d}，A上的二元关系R= {<a,b>,<b,d>,<c,c>,<c,d>}，那么Dom(R) =，Ran(R) =。
A．集合上 的关系如果不是自反的，就一定是反自反的；
B．若关系 都是反自反的，那么 必也为反自反的；
C．若关系 都是自反的，那么 必也为自反的；
D．每一个全序集必为良序集.
4．下列结论中不正确的结论是：（）
A．三个命题变元的布尔小项 的编码是 ；
B．三个命题变元的布尔大项 的编码是 ；
C．任意两个不同的布尔小项的合取式必为永假式；
2证明 是偏序集。
3画出偏序集 的哈斯图。
4在 上定义两个二元运算 和 ：对任意 ， ， 。请填空（在横线上填是或不是并回答为什么）：
代数系统 格，因为。
代数系统 有界格，因为。
代数系统 有补格，因为。
代数系统 分配格，因为。
代数系统 布尔代数，因为。
二、计算
设 是布尔代数 上的一个布尔表达式。试写出 的析取范式和合取范式（用列函数表的方法）。
三、画出满足下列要求的图
有一条欧拉回路和一条汉密尔顿回路。
有一条欧拉回路但没有汉密尔顿回路。
没有欧拉回路但有汉密尔顿回路。
既没有欧拉回路也没有汉密尔顿回路。
四、证明在完全二叉树中，边的总数等于2(n-1)，这里n是叶子数。
五、计算
求带权2、3、5、7、11、13的最优二叉树。
六、证明
在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。
前提(x)(F(x)∧S(x))→(y)(M(y)→W(y))，(y)(M(y)∧┐W(y))
结论(x)(F(x)→┐S(x))
三、计算题
1.证明逻辑等价式A→(A→B)A→B成立。
2.对任意集合A，B，C，证明：（A - B）B = AB
3.设二元关系R={<{a},b>,<a,b>, <b,c>}求：
(1) dom R
(2) ran R
(3) RοR
4.求集合A={<p,q>|p,q都是整数}的势。
5.在20名青年中有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。
四、假设给定了正整数的序偶集合A，在A上定义二元关系R如下：<<x,y>,<u,v>>R,当且仅当xv=yu，证明R为等价关系。
完成下列各小题。
1、证明 是 上的偏序关系。
2、画出偏序集 的哈斯图。
3、在 上定义两个二元运算 和 ：对任意 ， ， 。请填空（在横线上填是或不是）：
代数系统 格。 代数系统 有界格。
代数系统 有补格。 代数系统 分配格。
二、求布尔函数的析取范式和合取范式
设 是布尔代数 上的一个布尔表达式。试写出 的析取范式和合取范式（用推导法或列函数表的方法均可）。
D．任意两个不同的布尔大项的合取式必为永假式.
5．设集合A和二元运算*，可交换的代数运算是（）。
A．设
B．设
C．设 ，运算 是矩阵的乘法
D．设
6．以下命题中不正确的结论是（）
A．素数阶群必为循环群；B．Abel群必为循环群；
C．循环群必为Abel群D．4阶群必为Abel群.
7．设代数系统 和 ，存在映射 ，如果 ，都有（），称K1与K2同态。
2、求 。
六、设<G，>为一群。证明：
（1）若对任意aG有a2=e，e为幺元，则G为阿贝尔群。
（2）若对任意a，bG有(ab)2=a2b2，则G为阿贝尔群。
七、设N4=｛0，1，2, 3｝，f：N4→N4定义如下：
令F = {f0,f1,f2,f3}，其中f0为N4上恒等函数。给定一代数结构<F,ο>，且 （这里ο为函数合成运算，+4为模4加运算）。
4设集合 上的关系 ，求出它的自反闭包，对称闭包和传递闭包。
三、设 上的整除关系 ， 是否为 上的偏序关系？若是，则：
1、画出 的哈斯图；2、求 的极大值和 的极小值。
四、用推导法求公式 的主析取范式和主合取范式。
五、设自然数集 上的关系 定义为： ，
证明： 是 上的等价关系。
六、设 分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数 为 ，证明 的同构映射。
五、给出偏序集<A, R>上偏序关系R的关系图（如下图所示）。
（1）求偏序集<A, R>的哈斯图。
（2）指出A的最大、最小元（如果有的话），极大、极小元。
六、设<G，>为群。若在G上定义二元运算о,使得对任何元素x，yG，有
xоy = yx。
证明<G，о>也是群
七、设<G，>为群,a为G中给定元素。定义函数f：G→G，使得对每一xG有f(x)=axa-1
2、求 。
四、用推导法求公式 的主析取范式和主合取范式。
五、设实数集 上的关系 ，
证明： 是 上的等价关系。
六、设 分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数 为 ，证明 的同构映射。
七、设 是实数集合， ，在 上定义二元运算 为： ，试证明 是一个群。 是否阿贝尔群？
复习题二
一、设上的整除关系
七、设 是整数集合，＋是普通加法，试证明 是一个群。 是否循环群？
复习题八
一、求公式(┐p∨┐q)→(p┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明：
前提(x)P(x)→(x)((P(x)∨Q(x))→R(x))，(x)P(x)，(x)Q(x)
结论(x)(y)(R(x)∧R(y))
试证
七、证明
设 是有限字母表，给定代数系统 ，其中 是串的连接运算。对于任一串 ，建立 到 的映射 ， 。证明 是 到 的一个满同态，且当 时， 是同构映射。
八、应用
给定有限状态机 ，它的状态图如附图所示。
1、求状态 的011010的后继以及可接受状态序列。
2、求 对于激励010110的响应。
3、构造一台与 相似的转换赋值机 ，画出 的状态图。
(3)画一个没有欧拉回路但有一条汉密顿回路的图
2、设 ，求公式：
的真值。
3、一棵树有 个结点度数为2， 个结点度数为3，…， 个结点度数为k，问它有几个度数为1的结点。
4、设集合 上的关系 ，求出它的自反闭包，对称闭包和传递闭包。
三、设 上的整除关系 ，
是否为 上的偏序关系？若是，
则：1、画出 的哈斯图；
19．给定平面图G，如下图所示，则G的面数为，G中面的总次数为。
20．若二部图 为完全二部图，则其边数为
三．计算题(一)
21．符号化下述两个语句，并说明其区别：
（1）如果天不下雨，我们就去旅游；（2）只有不下雨，我们才去旅游。
A． B．
C． D．
8．图G有21条边，3个4度结点，其余均为3度结点，则G有（）个结点。
A．13 B．15 C．17 D．19
9．以下命题中正确的结论是（）
A． 时，完全图 必为欧拉图
B．如果一个连通图的奇结点的个数大于2，那么它可能是一个Euler图；
C．一棵树必是连通图，且其中没有回路；
D．图的邻接矩阵必为对称阵.
三、计算题
1.证明逻辑等价式AB(A∧B)∨(┐A∧┐B)成立。
2.设AB，求证A∩CB∩C。
3.设集合A={a，b，c，d}，A上的关系R={<b,b>,<a,b>,<c,b>,<d,c>}，求R的自反闭包、对称闭包。
