当前位置：文档之家 › 离散数学模拟试卷

离散数学模拟试卷

  • 格式：doc
  • 大小：51.50 KB
  • 文档页数：2

离散数学模拟试卷
一.(10分)求与公式(x2 ∨ 1x )--->x3 逻辑等值的主合取范式和主析取范式.
二.(10分)判断下列各公式是: 1.永真式 2.永假式 3.其它
(1) (p-->(q-->r))-->(q-->(p-->r))

(2) ))(()(qppqp
(3) qprrqqp)(
(4))()(qppq
三.(10分)问),(),(yxxPyyxyPx是否谓词演算的有效式?证明你的结论.
四.(10分)将下列推理符号化并给出形式证明:
鸟会飞，猪不会飞;所以, 猪不是鸟.
五.(10分)令X={x1,x2,...,xm},Y={y1,y2,...,yn},问:
(1) 有多少不同的由X到Y的关系?
(2) 有多少不同的由X到Y的映射?

六.(10分) 设,R是一个代数系统，是R上的一个二元运算，使得对于R中的任意元
素ba,都有bababa,证明0是幺元且,R是独异点。
七.(10分) 设 是独异点，且H中任意x，有x*x=e,其中e为单位元，试证明：
是交换群。
八.(10分)把平面分成n个区域,每两个区域都相邻,问n最大为几?
九.(10) 设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，
问：G中至少有几个结点。
十.(10分) 一个树有2个4度结点，3个3度结点，其余结点都是叶子，则叶子数是多少？
参考答案

一.主合取范式:)()()(321321321xxxxxxxxx
主析取范式:

)()()()()(321321321321321xxxxxxxxxxxxxxx
二.(1) 1 (2) 3 (3) 2 (4) 1
三.不是.取一特定解释域 I 如下.[P(x,y)] I ="x≤y",论域D=N(自然数集)则显然有
tIyxyPx)],([
fIyxxPy)],([
故给定公式在 I 中为假,因此它不是谓词公式的有效式.
四.

(1) ))()((xflyxbirdx
(2) ))()((xflyxpigx
(3) )()(aflyabird
(4) )()(aflyapig
(5) )()(abirdafly
(6) )()(abirdapig
(7) ))()((xbirdxpigx
五.解:

(1) 一个x到y的关系对应于x*y的一个子集.因此,不同的x到y的关系数=|φ(x*y)|=mn2
(2)不同的由x到y的映射个数=|{f|f: x->y}|=|{(f(x1),f(x2),...,f(xm) )|,,}|
==
六. (1)、由运算 可知，a b∈R ，可知其在R上具有封闭性。
（2）、对于任意 a,b,c∈R
(ab) c=(a+b+ab) c=a+b+ab+c+ac+bc+abc
a(bc)=a(b+c+bc)=a+b+c+bc+ab+ac+abc
可见： (ab) c=a(bc)
即  在R上是可结合的。
(3) 因为 0i=i ，所以0是上一个幺元
根据上述 是独异点
七. 设有任意a,b∈H，e为幺元，则根据已知条件有：
a*b=(e*a)*(b*e)
=(b*b*a)*(b*a*a)
=b*((b*a)*(b*a))*a
=b*e*a=b*a
可见a*b=b*a,即是交换群。
八.在每个区域放一个结点,当两区域相临时就在响应的两个结点间连一条线,如此构造了
一个平面图且是完全图kβ.而最大的平面完全图为k4,所以,β最大为4.
九. 解：设度数小于3的结点有x个，则有
3×4＋4×3＋2x≥2×16
解得：x≥4
十. 解：设叶子数为n,则根据树的定义和图中总度数是边数的2倍，可列出方程如下：
2×4+3×3+n×1=2×(n+2+3-1)
解之得：n=9

合集下载

离散数学样卷参考答案

离散数学样卷参考答案

参考答案试卷一一、选择填空1.C2.A3.D4.D5.A6.A7.B8.C9.D 10.B二、填空1.主合取范式)()(q p q p ⌝∨∧∨⌝.前束范式))()((x G x F x →∀或))()((y G x F y x →∀∀ 2. n-k,93.=)(A ρ{Φ,{1}，{2}，{1，2}}，B A ⨯={〈1,a 〉,<1,b>,<2,a>,<2,b>}4. [b]R ={1,2,3}, X/R={{1,2,3},{4},{5}}.5． ,,G y x ∈∀ )()()(y f x f y x f *= 。

6.=-)(1R r { <2,1>,< 4,2>,<1,1>,<3,3>,<2,2>}，=S R {<1,4>,<2,2>}。

7.15，12.8. =τσ⎪⎪⎭⎫ ⎝⎛42134321 =(132) =-1στ⎪⎪⎭⎫ ⎝⎛41324321=(123) 9．0, 45 10．2,0三 1.× 2.√ 3. √ 4.× 5.×四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。

试求其共有多少个结点？多少片叶？解: 设该树其有x 片叶,则顶点数为x+7, 根据树的性质知,该树有x+6边,由握手定理有:3*2+2*3+2*4+x*1=2(x+6), 得x=8故该树共有15个结点,8 片叶 .2.已知X={a,b,c},给出X 上的所有等价关系。

解:X 的划分其有五种:S 1={{a,b,c}}, S 2={{a,b},{c}}, S 3={{a,c},{b}}, S 4={{a},{b,c}},S 5={{a},{b},{c}},因为X 上划分与等价关系一一对应,故x 上共有五个等价关系，它们是：R 1＝{<a,b>,<b,a>,<a,c><c,a>,<b,c>,<c,b>}X I ⋃R 2＝{<a,b>,<b,a>}X I ⋃, R 3＝{<a,c><c,a>}X I ⋃R 4＝{<b,c>,<c,b>}X I ⋃, R 5＝X I3.．画一棵权为2，3，3，4，5，6，7，8 的最优二叉树，并计算出它的树权。

离散数学期末考试试题及答案

离散数学期末考试试题及答案

离散数学期末考试试题及答案一、选择题（每题4分，共40分）1. 以下哪个命题是正确的？A. 如果p，则qB. 如果不p，则不qC. 如果q，则pD. 如果不q，则不p2. 设集合A={1,2,3,4}，B={2,4,6,8}，则A∪B等于？A. {1,2,3,4,6,8}B. {1,2,3,4}C. {2,4,6,8}D. {1,3}3. 一个图的欧拉回路是指？A. 从一个顶点出发，经过每条边一次且仅一次，回到该顶点的回路B. 从一个顶点出发，经过每个顶点一次且仅一次，回到该顶点的回路C. 从一个顶点出发，经过每条边两次，回到该顶点的回路D. 从一个顶点出发，经过每个顶点两次，回到该顶点的回路4. 以下哪个图是二分图？A. K3,3B. C5C. K4D. Q35. 以下哪个命题是正确的？A. 如果p∧q为假，则p为假B. 如果p∨q为假，则q为假C. 如果p→q为真，则q→p为真D. 如果p→q为假，则q→p为假二、填空题（每题5分，共30分）6. 设p是“今天下雨”，q是“我去图书馆”，则命题“如果今天下雨，那么我不去图书馆”可以用逻辑符号表示为______。

7. 设集合A={a,b,c}，B={a,b,d}，则A-B的元素是______。

8. 设图G有6个顶点，每两个顶点之间都有边相连，则该图的边数是______。

9. 一个具有5个顶点的连通图至少需要______条边。

10. 设p是“我生病了”，q是“我去医院”，则命题“如果我生病了，那么我可能去医院”可以用逻辑符号表示为______。

三、解答题（每题15分，共45分）11. 设集合A={1,2,3,4,5}，B={3,4,5,6,7}，求A∩B。

12. 给定图G如下，请判断G是否为二分图，并说明理由。

```1 --2 -- 3| | |4 --5 -- 6```13. 设p是“我睡觉”，q是“我醒着”，r是“现在是晚上”。

请用逻辑符号表示以下命题：- 如果我睡觉，那么不是晚上。

离散数学试卷

离散数学试卷

《 离散数学 》 试卷（A ） 一．单项选择题(每题2分，共30分)1．下列命题公式中不．是重言式的是（ ） A ．p →(q →r) B ．p →(q →p)C ．p →(p →p)D ．(p →(q→r))(q →(p →r))2．下列语句中为命题的是（ ） A ．这朵花是谁的？ B ．这朵花真美丽啊！ C ．这朵花是你的吗？ D ．这朵花是他的。

3．设个体域是整数集，则下列命题的真值为真的是（ ）A ．y x(x ·y=1)B．x y (x ·y ≠0) C ．x y (x ·y=y 2)D ．y x(x ·y=x 2)4．关于谓词公式（x）(y)(P(x,y)∧Q(y ,z))∧(x)p(x,y),下面的描述中错误．．的是（ ）A．（x ）的辖域是（y ）（P （x,y ）∧Q(y ,z)） B ．z 是该谓词公式的约束变元 C ．（x ）的辖域是P （x,y ） D ．x 是该谓词公式的约束变元 5．设论域D={a,b}，与公式xA （x ）等价的命题公式是（ ）A ．A （a ）∧A （b ）B ．A （a ）→A （b ）C ．A （a ）∨A （b ）D ．A （b ）→A （a ）6．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（ ） A ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡100010101B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101010101C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101110011D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡1110110017．设A={Ø}，B=P （P （A ）），以下不．正确的式子是（ ） A ．{{Ø }，{{Ø }}，{Ø ，{Ø }}}包含于B B ．{{{Ø }}}包含于B C ．{{Ø ，{Ø }}}包含于B D ．{{Ø }，{{Ø ，{Ø }}}}包含于B8．设Z 是整数集，E={…，-4，-2，0，2，4，…}，f ：Z →E ，f （x ）=2x ，则f （ ） A ．仅是满射 B ．仅是入射 C ．是双射D ．无逆函数9．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1 R-1的运算结果是（）A．{〈4，1〉，〈2，3〉，〈4，2〉} B．{〈2，4〉，〈2，3〉，〈4，2〉}C．{〈4，1〉，〈2，3〉，〈2，4〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）A．矛盾式B．重言式C．可满足式D．公式p∧q11．在实数集合R上，下列定义的运算中不．可结合的是（）A．a*b=a+b+2ab B．a*b=a+bC．a*b=a+b+ab D．a*b=a-b12．下列集合关于所给定的运算成为群的是（）A．已给实数a的正整数次幂的全体，且a∉{0，1，-1}，关于数的乘法B．所有非负整数的集合，关于数的加法C．所有正有理数的集合，关于数的乘法D．实数集，关于数的除法13．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A．3 B．4C．5 D．614．设无向图G的边数为m，结点数为n，则G是树等价于（）A．G连通且m=n+1 B．G连通且n=m+1C．G连通且m=2n D．每对结点之间至少有一条通路15．设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立二、填空题（每题2分，共20分）1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。

离散数学试卷及答案

离散数学试卷及答案

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( )A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )A.10B.12C.16D.143.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( )A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( )A.〈Z，+，/〉B.〈Z，/〉C.〈Z，-，/〉D.〈P(A)，∩〉6.下列各代数系统中不含有零元素的是( )A.〈Q，*〉Q是全体有理数集，*是数的乘法运算B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C.〈Z， 〉，Z是整数集， 定义为x xy=xy,∀x,y∈ZD.〈Z，+〉，Z是整数集，+是数的加法运算7.设A={1,2,3}，A上二元关系R的关系图如下：R具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )A.R∪I AB.RC.R∪{〈c,a〉}D.R∩I A9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}10.下列式子正确的是( )A. ∅∈∅B.∅⊆∅C.{∅}⊆∅D.{∅}∈∅11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R下为真的是( )A.( ∀x)( ∀y)( ∀z)(A(x,y))→A(f(x,z),f(y,z))B.( ∀x)A(f(a,x),a)C.(∀x)(∀y)（A(f(x,y),x))D.(∀x)(∀y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(∀x)(A(x)→B)等价于( )A.(∃x)A(x)→BB.(∀x)A(x)→BC.A(x)→BD.(∀x)A(x)→(∀x)B13.谓词公式(∀x)(P(x,y))→(∃z)Q(x,z)∧(∀y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q15.以下命题公式中，为永假式的是( )A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。