离散数学作业Word文档格式.docx
《离散数学作业Word文档格式.docx》由会员分享，可在线阅读，更多相关《离散数学作业Word文档格式.docx（25页珍藏版）》请在冰点文库上搜索。
（1）p∧（p→q）∧（p→
（2）（p∧r）
（
q）
（2）（（p→q）∧（q→r））→（p→r）
第二章命题逻辑等值演算
一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
（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）
三、用等值演算求下列公式的主析取范式与主合取范式，并求成真赋值
（1）（
p→q）→（
q∨p）
（2）
（p→q）∧q∧r
（3）（p∨（q∧r））→（p∨q∨r）
四、用真值表法求下列公式的主析取范式,再用主析取范式求主合取范式
（1）（p∨q）∧r
（2）p→（p∨q∨r）
第三章命题逻辑的推理理论
一、填空
1.数理逻辑的的主要任务是。
推理是指，前提是，结论是。
2.推理正确是指：
3.命题公式A1，A,2，⋯，A,k推B的推理正确当且仅当
二、先把下列命题符号化，再写出前提、结论、推理的形式结构，然后用3种方法证明（真值表法、等值演算法、主析取范式法）证明下列推理是正确的。
若a是奇数，则a不能被2整除。
若a是偶数，则a能被2整除。
因此，若a是偶数，则a不是奇数。
设p:
a是奇数,q:
a能被2整除,r:
a是偶数
三、在自然推理系统下用直接法或用附加前提法或用归谬法构造下列推理的证明
（1）前提：
p
q,
（q
r）,r
结论：
p
（2）前提：
q
p,q
s,s
t,t
r
（3）前提：
r）,s
p,q（4）前提：
r
q,r
s
r结论：
p
四、在自然推理系统下构造下列推理的证明
如果我学习，那么我数学不会不及格。
如果不热衷于玩游戏，那么我将学习。
但我数学不及格。
因此我热衷于玩游戏。
第四章一阶逻辑的基本概念
一、将下列命题用0元谓词符号化.
（1）小王学过英语和法语。
（2）除非李建是东北人，否则他一定怕冷。
（3）2大于3仅当2大于4。
（4）3不是偶数。
（5）2或3是素数。
二、在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为（a）,（b）条件时命题的真值:
（1）对于任意x,均有
（2）存在x,使得x+5=9.
其中（a）个体域为自然数集合.
（b）个体域为实数集合.
三、在一阶逻辑中将下列命题符号化:
（1）没有不能表示成分数的有理数。
（2）在北京卖菜的人不全是外地人。
（3）乌鸦都是黑的。
（4）有的人天天锻炼身体。
四、给定解释I如下:
（a）个体域D为实数集合R.
（b）D中特定元素
=0.
（c）特定函数
（x,y）=x-y,x,y
（d）特定谓词
（x,y）:
x=y,
x<
y,x,y
.
说明下列公式在I下的含义,并指出各公式的真值:
（3）
（4）
五、给定下列各公式一个成真的解释，一个成假的解释。
（1）∀x（F（x）∨G（x））
（2）∃x（F（x）∨G（x）∧H（x））
六、判断下列公式的类型
（1）F（x,y）→（G（x,y）→F（x,y））
（2）∀x∃yF（x,y）→∃x∀yF（x,y）
第五章一阶逻辑的等值演算与推理
一、设个体域D={a,b,c},消去下列各式的量词
（1）∀x∃y（F（x）∧G（y））
（2）∀x∃y（F（x）∨G（y））
（3）∀xF（x）→∃yG（y）
二、求下列公式的前束范式
（1）∀xF（x）→∀yG（x,y）
（2）∀x（F（x,y）→∃yG（x,y,z））
三、设个体域D={1,2,3,4}，F（x）:
x是2的倍数，G（x）:
x是奇数。
将命题∀x（F（x）→⌝G（y））中的量词消去，并讨论命题的真值。
四、在自然推理系统下用直接法或用附加前提法或用归谬法构造下列推理的证明
❑
1.全称量词消去规则（UI）
❑2.全称量词引入规则（UG）
3.存在量词引入规则（EG）
4.存在量词消去规则（EI）
∀x（F（x）→G（x））,∀xF（x）
结论：
∀xG（x）
（2）前提：
∀x（F（x）→G（x））
∀xF（x）→∀xG（x）
（3）前提：
∀x（F（x）∨G（x）），┐∃xG（x）
∃xF（x）
五、在自然推理系统下构造下列推理的证明
没有白色的乌鸦，北京鸭都是白色的。
因此，北京鸭都不是乌鸦。
第六章集合论
一、单项选择题
1．若集合A={a，b}，B={a，b，{a，b}}，则（）．
A．A⊂B，且A∈BB．A∈B，但A⊄B
C．A⊂B，但A∉BD．A⊄B，且A∉B
2．若集合A＝{2，a，{a}，4}，则下列表述正确的是（）．
A．{a，{a}}∈AB．{a}⊆A
C．{2}∈AD．
∈A
3．若集合A＝{a，{a}，{1，2}}，则下列表述正确的是（）．
A．{a，{a}}∈AB．{2}⊆A
C．{a}⊆AD．∅∈A
4．若集合A={a，b，{1，2}}，B={1，2}，则（）．
A．B⊂A，且B∈AB．B∈A，但B⊄A
C．B⊂A，但B∉AD．B⊄A，且B∉A
5．设集合A={1,a}，则P（A）=（）．
A．{{1},{a}}B．{
{1},{a}}
C．{
{1},{a},{1,a}}D．{{1},{a},{1,a}}
6．若集合A的元素个数为10，则其幂集的元素个数为（）．
A．1024B．10C．100D．1
二、1．设集合A有n个元素，那么A的幂集合P（A）的元素个数为．
2．设集合A＝{a，b}，那么集合A的幂集是．
三、
（1）B、C为任意的三个集合，如果A∪B=A∪C，判断结论B=C是否成立？
并说明理由．
（2）B、C为任意的三个集合，如果A⊕B=A⊕C，判断结论B=C是否成立？
四、1．设集合A＝{a,b,c}，B={b,d,e}，求
（1）B⋂A；
（2）A⋃B；
（3）A－B；
（4）B⊕A．
2．设A={{a,b},1,2}，B={a,b,{1},1}，试计算
（1）（A-B）
（2）（A∪B）（3）（A∪B）-（A∩B）
五．证明集合等式：
A⋃（B⋂C）=（A⋃B）⋂（A⋃C）
六、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。
已知6个会打网球的人都会打篮球或排球。
求不会打球的人数。
第七章二元关系
（1）
1．集合A={1,2,3,4,5,6,7,8}上的关系R={<
x，y>
|x+y=10且x,y
A}，则R的性质为（）．
A．自反的B．对称的
C．传递且对称的D．反自反且传递的
2．设集合A={1，2，3，4，5，6}上的二元关系R={
a,b
⎢a,b
A,且a+b=8}，则R具有的性质为（）．
A．自反的B．对称的
C．对称和传递的 D．反自反和传递的
3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．
A．0B．2C．1D．3
4．设集合A={1,2,3,4}上的二元关系
R={
1,1
，
2,2
2,3
4,4
}，
S={
3,2
则S是R的（）闭包．
A．自反B．传递C．对称D．以上都不对
二、填空题
1．设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，
则R的有序对集合为 ．
2．设集合A={0,1,2}，B={0,2,4},R是A到B的二元关系，
则R的关系矩阵MR＝
．
3．设集合A={a,b,c}，A上的二元关系
R={<
a,b>
<
c.a>
}，S={<
a,a>
c,c>
}
则（R∙S）－1= ．
4．设集合A=｛a,b,c｝，A上的二元关系R={<
<
b,a>
b,c>
c,d>
}，则二元关系R具有的性质是 ．
三、设A={a，b}，构成集合ρ（A）×
A。
四、
（1）列出集合A={2,3,4}上的恒等关系IA,全域关系EA,小于或等于关系LA,整除关系DA.
（2）设A={a,b,c,d}，
为A上的关系，其中
=
求
。
五、设集合A＝{a,b,c,d}上的二元关系R的关系图
如图1所示．
（1）写出R的表达式；
（2）写出R的关系矩阵；
（3）求出R2．
六、设集合A={1，2，3，4}，R={<
x,y>
|x,y∈A；
|x-y|=1或x-y=0}，试
（1）写出R的集合表示；
（2）画出R的关系图；
（3）说明R满足自反性，不满足传递性．
第七章二元关系
（2）
一、选择题
1.下列说法正确的是（）
A．
B．
C．
D．
2.若A={（x，y）|（y－4）/（x+2）=1}和B={（x，y）|y=3x－2}，则A∩B为（）
A．{（x，y）|（y－3）/（x－1）=1}
B．{（x，y）|x=4，y=10}
C．{（x，y）|y=x+2}
D．Ф
3.设A为有限集，元素个数为n个，P（A）为A的幂集，则P（A）的元素个数及
的元素个数为（）
A．
B．
及
C．
D．以上全不对
4.设A是非空集合，则A上的空关系不具有（）
A．反自反性 B．自反性C．对称性D．传递性
5．设
，R是A上相等关系“=”，由R产生等价类有（）
A．10个 B．50个 C．100个 D．1个
6.集合A的一个划分，确定A的元素间的关系为（）.
A．全序关系 B．等价关系 C．偏序关系 D．拟序关系
7．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（ ）
8.给定A={1、2、3}上的关系R={<
1,1>
2,2>
1,3>
3,1>
2,3>
}则（）
AR是自反的且传递
BR不反自反且不对称
CR是反对称且不对称
DR不自反且传递
9．A={1、2、3}，则A上不同等价关系有（）
A.5B.10C.15D.8
二、设A={1，2，3，4},R={<
1,1>
2,2>
3,3>
4,4>
2,3>
3,2>
}是A上的等价关系吗？
如果是,给出给出每个元素的等价类；
如果不是,请说明理由。
三、设集合A={1，2，3，6，8，12，24，36}，R为A上整除关系，画出R的哈斯图，并指出B={2，6，8}的极大元，极小元、最大元，最小元、及上确界和下确界。
四、设A={1，2，3，4}，在A
A上定义二元关系R，
<
u,v>
x,y>
A
A，〈u,v>
R<
u+y=x+v.
（1）证明R是A
A上的等价关系.
（2）确定由R引起的对A
A的划分.
第八章函数
1．设A={a,b}，B={1,2}，R1，R2，R3是A到B的二元关系，且R1={<
a，2>
b，2>
}，R2={<
a，1>
b，1>
}，R3={<
}，则（）不是从A到B的函数．
A．R1和R2B．R2C．R3D．R1和R3
2.设A={a，b，c}，B={1，2}，作f：
A→B，则不同的函数个数为（）
A．6B.5C.9D.8
3.下列函数中为双射的是（）.
C．
4.设Z是整数集，E={…,-4,-2,0,2,4，…}，f：
Z→E，f（x）=2x，则f是（）
A．仅是满射B．仅是单射C．是双射D．无逆函数
二、判断下列函数中哪些是满射的?
哪些是单射的?
哪些是双射的?
（1）f:
N
N,f（x）=x2+2
（2）f:
N,f（x）=（x）mod3,x除以3的余数
（3）f:
N,f（x）=
（4）f:
{0,1},f（x）=
（5）f:
N-{0}
R,f（x）=lgx
（6）f:
R
R,f（x）=x2-2x-15
三、设X={a,b,c,d},Y={1,2,3},f={<
a,1>
b,2>
c,3>
}判断以下命题的真假:
（1）f是从X到Y的二元关系,但不是从X到Y的函数;
（2）f是从X到Y的函数,但不是满射,也不是单射的;
（3）f是从X到Y的满射,但不是单射;
（4）f是从X到Y的双射.
四、设A={1,2}，B={a,b,c},写出所有A到B的函数，并说明所具有的性质。
五、已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？
A到B的函数数是多少？
六、设N是自然数集合，定义N上的二元关系R：
R={（x,y）:
x∈N,y∈N,x+y是偶数}
（1）证明R是等价关系。
（2）求关系R的等价类。
第十四、十五章
1．一个无向图有4个结点，其中3个的度数为2，3，3，则第4个结点的度数不可能是（）
A.0B.1C.2D.4
2．无向完全图
有
（
）条边
A.n
B.n2
C.
n（n-1）
D.n（n-1）/2
3．整数列（1，3，3，5，4）（）
A．可以简单图化B.不可图化C.可图化，不可简单图化
4．若答案中的数值表示一个简单图中各个顶点的度，能画出图的是（）.
A.（1,2,2,3,4,5）B.（1,2,3,4,5,5）C.（1,1,1,2,3）D.（2,3,3,4,5,6）.
5．设简单图G所有结点的度之和为12，则G一定有（）.
A．3条边B．4条边C．5条边D．6条边
6．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（ ）
A．3B．4C．5D．6
7．下列各图中既是欧拉图，又是汉密尔顿图的是（ ）
A．B．C．D．
8.设G为完全二部图K2,3，下面命题中为真的是（）
A.G为欧拉图B.G为哈密尔顿图 C.G为平面图D.G为正则图
二、填空
1．简单无向图有21条边,3个4度结点,其余均为3度结点,则G有___个结点.
2．无向图G=<
V,E>
V={a,b,c,d},E={（a,b）,（a,c）,（a,d）,（b,c）},则它的邻接矩阵为，该图的补图有条边。
3.设K6是有6个点的完全图，则K6共有____________条边。
4..已知n阶无向简单图G有m条边，则G的补图G有__________条边。
5.若一条路中，所有边均不相同，则此路称作____________；
若一条路中所有的结点均不相同，则称此路为____________。
6．图G如图1所示，那么图G的割点是。
7．如图2所示G的邻接矩阵A=_______
8.下图的点连通度等于，边连通度等于_________。
9.已知n阶无向图G中有m条边，各顶点的度数均为3。
又已知2n-3=m，
则m=.
三、
（1）已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点度数均为4，求4度顶点的个数。
（2）假设在图G（有向图或无向图）中，有10条边，4个3度的结点，其余结点的度数不大于2。
问G中至少有几个结点？
四、判断下图是否欧拉图，若是，找出一个欧拉回路。
五．设简单无向图G有n个结点,n+1条边，证明G中至少有一上结点的度≥3。
六、画出彼德森图，K5，K3,3，并判断他们是否是欧拉图，是否是哈密顿图。
第十六、十七章
1．一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则
根结点的右子树有（）结点。
A．1B．2C．3D．4
2．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（
）
A．2B．3C．4D．5
3.下列编码是前缀码的是（
）.
A.{1,11,101}
B.{1,001,0011}C.
{1,01,001,000}
D.{0,00,000}
4.下图所示的二叉树中序遍历的结果是（
A．abcdeB．edcbaC．bdecaD．badce
5.关于无向树的描述,不正确的是（）.
A.无向树是连通图、没有回路,每个边都是桥；
B.无向树是连通图、边数比顶点数少１,任意两个顶点的路径是惟一的；
C.无向树是连通图、没有回路,每个顶点都是割点；
D.无向树是连通图、没有回路，每条边都是割边。
6.关于含有n片树叶的最优二叉树描述,不正确的是（）.
A.含有n片树叶的最优二叉树每个分支点都有两个孩子；
B.含有n片树叶的最优二叉树分支点的个数是n-1；
C. W（T）等于个分支点的权重（构造最优二叉树时产生）之和；
D.在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。
7.彼得森图是（）。
A.平面图B.二部图C.Euler图D.以上都不是
二、1.一棵二叉树先序遍历得ABDECF，中序遍历得DBEACF,则后序遍历的结果是________________。
2.一无向图存在生成树的充分必要条件是。
3.最优二叉树有n片树叶，则它有分支点。
三、1.
（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中应该有几片树叶？
（2）画出两棵非同构的满足上述条件的无向树 。
2.画一棵带权为2，2，2，3，3，4，5，8的最优二叉树T，并计算它的权W（T）。
3.求下2图的最小生成树。
4.已知连通的平面图G的阶数n=6，边数m=8，面数r=4。
求G的对偶图G*的阶数n*，边数m*，面数r*。
四、证明若图G是自对偶的，则m=2n－2。
其中n为G的结点数，m为G的边数。
第九章代数系统
1.下述*运算为实数集上的运算，其中可交换且可结合的运算是[
]
A.a*b=a+2b
B.a*b=a+b-ab
C.a*b=a
D.a*b=|a+b|
2.
二、A={1，2}，
代数系统，
是集合的对称差运算。
该运算满足
，并且
单位元是，{1}的逆元是。
三、设R为实数集，+为普通加法，∙为普通乘法，<
R，*>
是一个代数系统，*是R上的一个二元运算，使得
，都有x*y=x+y+x∙y。
指出*运算的性质，并求出它的单位元，零元和所有可逆元素的逆元。
（仿例9.6）
四、S=Q×
Q,其中Q为有理数集合，定义S上的二元运算*，
a,b>
∈S，<
*<
=<
ax,ay+b>
（1）求<
3,4>
1,2>
（2）已知<
-1,3>
-5,1>
求a,b.
（3）*是可交换的吗？
是可结合的吗？
五、设A={0，1，2，3，4}，定义*运算如下：
（1）列出*的运算表；
（2）*是否有零元、幺元？
如有，则求出相应值，求出具有逆元的元素和相应的逆元。
升级会员 