离散数学作业
第一章 命题逻辑的基本概念
一、判断下列语句是否是命题,若是命题是复合命题则请将其符号化
(1)中国有四大发明。
(2)2是有理数。
(3)“请进!”
(4)刘红和魏新是同学。
(5)a+b
(6)你去图书馆吗?
(7)如果买不到飞机票,我哪儿也不去。
(8)侈而惰者贫,而力而俭者富。(韩非:《韩非子∙显学》)
(9)火星上有生命。
(10)这朵玫瑰花多美丽啊!
二、将下列命题符号化,其中p:2
(1)只要2
(2)如果2
(3)只有2
(4)除非2
(5)除非2
(6)2
三、将下列命题符号化
(1)小丽只能从筐里拿一个苹果或一个梨。
(2)王栋生于1992年或1993年。
- 1 -
四、设p 、q 的真值为0;r 、s 的真值为1,求下列各命题公式的真值。
(1)p ∨(q∧r)
(2)(p r )∧(﹁q ∨s)
(3)(⌝p ∧⌝q ∧r )(p∧q ∧﹁r)
(4)(⌝r ∧s )→(p∧⌝q)
五.判断下面一段论述是否为真:“π是无理数。并且,如果3是无理数,则2也是无理数。另外6能被2整除,6才能被4整除。”
六、用真值表判断下列公式的类型:
(1) p ∧(p→q) ∧(p→⌝q)
(2) (p∧r) (⌝p ∧⌝q)
(2)((p→q) ∧(q→r)) →(p→r)
- 2 -
第二章 命题逻辑等值演算
一、用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.
(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)
- 3 -
三、用等值演算求下列公式的主析取范式与主合取范式,并求成真赋值
(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)
- 4 -
第三章 命题逻辑的推理理论
一、填空
1. 数理逻辑的的主要任务是 。 推理是指 , 前提是 ,结论是 。
2. 推理正确是指:
3. 命题公式A 1,A ,2, ,A ,k 推B 的推理正确当且仅当
二、先把下列命题符号化,再写出前提、结论、推理的形式结构,然后用3种方法证明(真值表法、等值演算法、主析取范式法)证明下列推理是正确的。 若a 是奇数,则a 不能被2整除。若a 是偶数,则a 能被2整除。因此,若a 是偶数,则a 不是奇数。
设p: a是奇数,q: a能被2整除,r: a是偶数
- 5 -
三、在自然推理系统下用直接法或用附加前提法或用归谬法构造下列推
理的证明
(1)前提:p →q, ⌝(q∧r),r
结论:⌝p
(3)前提:p →(q→r),s →p,q (4)前提:p →⌝q, ⌝r ∨q,r ∧⌝s
结论:s →r 结论:⌝p (2)前提:q →p,q s,s t,t ∧r 结论:p ∧q
四、在自然推理系统下构造下列推理的证明
如果我学习,那么我数学不会不及格。如果不热衷于玩游戏,那么我将学习。 但我数学不及格。因此我热衷于玩游戏。
- 6 -
第四章 一阶逻辑的基本概念
一、将下列命题用0元谓词符号化.
(1) 小王学过英语和法语。
(2)除非李建是东北人,否则他一定怕冷。
(3)2大于3仅当2大于4。
(4)3不是偶数。
(5)2或3是素数。
二、在一阶逻辑中将下面将下面命题符号化, 并分别讨论个体域限制为(a),(b)条件时命题的真值:
(1) 对于任意x, 均有x 2-2=(x +2)(x -2)
(2) 存在x, 使得x+5=9.
其中(a)个体域为自然数集合.
(b)个体域为实数集合.
三、在一阶逻辑中将下列命题符号化:
(1) 没有不能表示成分数的有理数。
(2) 在北京卖菜的人不全是外地人。
(3)乌鸦都是黑的。
(4)有的人天天锻炼身体。
- 7 -
四、给定解释I 如下:
(a) 个体域D 为实数集合R.
(b) D中特定元素a =0.
(c) 特定函数f (x,y)=x-y,x,y∈D
(d) 特定谓词F (x,y):x=y, (x,y):x
说明下列公式在I 下的含义, 并指出各公式的真值:
(1)∀x ∀y (G (x , y ) →⌝F (x , y ))
(2)∀x ∀y (F (f (x , y ), a ) →G (x , y ))
(3) ∀x ∀y (G (x , y ) →⌝F (f (x , y ), a ))
(4) ∀x ∀y (G (f (x , y ), a ) →F (x , y ))
五、给定下列各公式一个成真的解释,一个成假的解释。
(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 ∃y F(x, y) →∃x ∀y F(x, y)
- 8 -
第五章 一阶逻辑的等值演算与推理
一、设个体域D={a,b,c},消去下列各式的量词
(1) ∀x ∃y(F(x) ∧G(y))
(2) ∀x ∃y(F(x) ∨G(y))
(3) ∀x F(x) →∃y G(y)
二、求下列公式的前束范式
(1)∀x F(x) →∀y G(x,y)
(2)∀x(F(x,y) →∃y G(x,y,z))
三、设个体域D={1,2,3,4},F(x):x是2的倍数,G(x):x是奇数。
将命题∀x (F(x) →⌝ G(y))中的量词消去,并讨论命题的真值。
四、在自然推理系统下用直接法或用附加前提法或用归谬法构造下列推理的证明
❑
❑
❑
❑
∀xA (x ) ∀xA (x ) 或1. 全称量词消去规则(UI) ∴A (y ) ∴A (c ) A (y ) 2. 全称量词引入规则 ∴∀xA (x ) A (c ) 3. 存在量词引入规则∴∃xA (x ) 4. 存在量词消去规则(EI) ∃xA (x ) ∴A (c ) - 9 -
(1)前提:∀x (F(x) →G(x)), ∀x F(x)
结论:∀x G(x)
(2) 前提:∀x(F(x)→G(x))
结论:∀xF(x)→∀x G(x)
(3) 前提:∀x(F(x)∨G(x)),┐∃x G(x)
结论:∃x F(x)
五、在自然推理系统下构造下列推理的证明
没有白色的乌鸦,北京鸭都是白色的。因此,北京鸭都不是乌鸦。
- 10 -
第六章 集合论
一、单项选择题
1.若集合A ={a ,b },B ={ a,b ,{ a,b }},则( ). A .A ⊂B ,且A ∈B B .A ∈B ,但A ⊄B C .A ⊂B ,但A ∉B D .A ⊄B ,且A ∉B 2.若集合A ={2,a ,{ a },4},则下列表述正确的是( ) . A .{a ,{ a }}∈A B .{ a }⊆A C .{2}∈A D .∅∈A
3.若集合A ={ a,{a },{1,2}},则下列表述正确的是( ) . A .{a ,{a }}∈A B .{2}⊆A
C .{a }⊆A D .∅∈A
4.若集合A ={a ,b ,{ 1,2 }},B ={ 1,2},则( ). A .B ⊂ A,且B ∈A B .B ∈ A,但B ⊄A C .B ⊂ A,但B ∉A D .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 .1024 B .10 C .100 D .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 是否成立?并说明理由.
- 11 -
四、 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个会打网球的人都会打篮球或排球。求不会打球的人数。
- 12 -
第七章 二元关系(1)
一、单项选择题
1.集合A ={1, 2, 3, 4, 5, 6, 7, 8}上的关系R ={|x +y =10且x , y ∈A },则R 的性质为( ).
A .自反的 B .对称的
C .传递且对称的 D .反自反且传递的 2.设集合A = {1,2,3,4,5,6 }上的二元关系R ={⎢a , b ∈A , 且a +b = 8},则R 具有的性质为( ). A .自反的 B .对称的
C .对称和传递的 D .反自反和传递的
3.如果R 1和R 2是A 上的自反关系,则R 1∪R 2,R 1∩R 2,R 1-R 2中自反关系有( )个.
A .0 B .2 C .1 D .3 4.设集合A ={1 , 2 , 3 , 4}上的二元关系
R = {,,,},
S = {,,,,},
则S 是R 的( )闭包.
A .自反 B .传递 C .对称 D .以上都不对 二、填空题
1.设集合A ={0, 1, 2, 3},B ={2, 3, 4, 5},R 是A 到B 的二元关系, R ={x ∈A 且y ∈B 且x , y ∈A ⋂B } 则R 的有序对集合为 . 2.设集合A ={0, 1, 2},B ={0, 2, 4},R 是A 到B 的二元关系,
R ={x ∈A 且y ∈B 且x , y ∈A ⋂B }
则R 的关系矩阵M R =
. 3.设集合A ={a , b , c },A 上的二元关系
R ={,},S ={,,}
则(R ∙S ) -1=.
4.设集合A ={a , b , c },A 上的二元关系R ={, , , },则二元关系R 具有的性质是 .
- 13 -
三、设A={a,b},构成集合ρ(A )×A 。
四、(1)列出集合A={2,3,4}上的恒等关系I A , 全域关系E A , 小于或等于关系L A , 整除关系D A .
(2)设A={a,b,c,d},R 1
,
R 2为A 上的关系,其中
R 1={a , a , a , b , b , d
2
3
} R 2={
a , b , c , , b
求R 1R 2, R 2R 1, R 1, R 2。
五、设集合A ={a , b , c , d }
如图1所示.
(1)写出R 的表达式; (2)写出R 的关系矩阵; (3)求出R .
2
图1
六、设集合A ={1,2,3,4},R ={|x , y ∈A ;|x -y |=1或x -y =0},试
(1)写出R 的集合表示; (2)画出R 的关系图; (3)说明R 满足自反性,不满足传递性.
- 14 -
第七章 二元关系(2)
一、选择题
1. 下列说法正确的是( )
A .A ⋃B =A ⋃C 则 B =C B .A ⋂B =A ⋂C 则 B =C C .A ⊕B =A ⊕C 则 B =C D .A -B =Φ 则 A =B
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 ⨯A 的元素个数为( )
A .n ,n B .2n 及 n 2 C .2n 及 n D .以上全不对 4. 设A 是非空集合,则A 上的空关系不具有( )
A .反自反性 B .自反性 C .对称性 D .传递性
2, . . 3. . ,. . ,10 },5.设A ={ 1,R 是A 上相等关系“=”,由R 产生等价类有( )
A .10个 B .50个 C .100个 D .1个 6. 集合A 的一个划分,确定A 的元素间的关系为( ).
A .全序关系 B .等价关系 C .偏序关系 D .拟序关系 7.集合A={1,2,3}上的下列关系矩阵中符合等价关系条件的是( )
⎡101⎤
⎥ 010A .⎢⎢⎥
⎢⎣001⎥⎦⎡110⎤
⎥ 011C .⎢⎢⎥
⎢⎣101⎥⎦
⎡101⎤
⎥ 010B .⎢⎢⎥
⎢⎣101⎥⎦⎡100⎤
⎥ 110D .⎢⎢⎥
⎢⎣111⎥⎦
8. 给定A={1、2、3}上的关系R={, , , , }则( )
A R 是自反的且传递 B R 不反自反且不对称 C R 是反对称且不对称 D R 不自反且传递
9.A={1、2、3},则A 上不同等价关系有( ) A. 5 B.10 C. 15 D.8
- 15 -
二、设A={1,2,3,4},R={,,,,,}是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 ,
∀,∈A ⨯A ,〈u,v> R ⇔u + y = x + v. (1)证明R 是A ⨯A 上的等价关系. (2)确定由R 引起的对A ⨯A 的划分.
- 16 -
第八章 函数
一、选择题
1.设A={a, b},B={1, 2},R1,R2,R3是A 到B 的二元关系,且R1={, },R2={, , },R3={, },则( )不是从A 到B 的函数.
A .R1和R2 B .R2 C .R3 D .R1和R3 2. 设A={a,b ,c},B={1,2},作f :A →B ,则不同的函数个数为( ) A . 6 B.5 C. 9 D.8 3. 下列函数中为双射的是( ).
3 B . A .f : I →I , f (j ) =j (mod)
f :N →N , f (j ) =
1,j 是奇数
0,j 是偶数
C .f :I →N , f (i ) = |2i |+1 D.f :R →R , f (r ) =2r -15
4. 设Z 是整数集,E={„,-4,-2,0,2,4,„},f :Z →E ,f (x )=2x,则f 是( ) A .仅是满射
二、判断下列函数中哪些是满射的? 哪些是单射的? 哪些是双射的? (1) f:N→N, f(x)=x2+2
(2) f:N→N,f(x)=(x)mod 3, x 除以3的余数
B .仅是单射 C .是双射 D .无逆函数
⎧1,若x 为奇数
(3) f:N→N,f(x)=⎨
⎩0,若x 为偶数
⎧0,若x 为奇数
(4) f:N→{0,1},f(x)=⎨
⎩1,若x 为偶数
(5) f:N-{0}→R,f(x)=lgx (6) f:R→R,f(x)=x2-2x-15
- 17 -
三、设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假: (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 的等价类。
- 18 -
第十四、十五章
一、单项选择题
1.一个无向图有4个结点,其中3个的度数为2,3,3,则第4个结点的度数不可能是( )
A.0 B. 1 C. 2 D. 4 2.无向完全图K n 有 ( )条边
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 .3 B .4 C .5 D .6
7.下列各图中既是欧拉图,又是汉密尔顿图的是( )
A . B . C . D .
8. 设G 为完全二部图K 2,3,下面命题中为真的是( )
A.G 为欧拉图 B.G 为哈密尔顿图 C.G 为平面图 D.G 为正则图 二、填空
1.简单无向图有21条边,3个4度结点, 其余均为3度结点, 则G 有___个结点. 2.无向图G=,V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,c)},则它的邻接矩阵为 ,该图的补图有 条边。
3. 设K 6是有6个点的完全图,则K 6共有____________条边。
4. .已知n 阶无向简单图G 有m 条边,则G 的补图G 有__________条边。 5. 若一条路中,所有边均不相同,则此路称作____________;若一条路中所
v 1有的结点均不相同,则称此路为____________。
6.图G 如图1所示,那么图G 的割点是 。
a b 7.如图2所示
G 的邻接矩阵A=_______ f c v 3
图2 图1 - 19 -
e
2
d
v 4
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。
六、画出彼德森图,K 5,K 3,3,并判断他们是否是欧拉图,是否是哈密顿图。
- 20 -
v 3
v 5
第十六、十七章
一、选择题
1
.一颗二叉树后序遍历的结果是bdeca ,中序遍历的结果是badce ,则 根结点的右子树有( )结点。
A .1 B.2 C.3 D.4
2.设G 是连通平面图,G 中有6个顶点8条边,则G 的面的数目是( )
A .2 B.3 C.4 D.5
3. 下列编码是前缀码的是( ).
A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000}
4. 下图所示的二叉树中序遍历的结果是( )
A .abcde B.edcba C.bdeca D.badce
5. 关于无向树的描述, 不正确的是( ).
A. 无向树是连通图、没有回路, 每个边都是桥;
B. 无向树是连通图、边数比顶点数少1, 任意两个顶点的路径是惟一的;
C. 无向树是连通图、没有回路, 每个顶点都是割点;
D. 无向树是连通图、没有回路,每条边都是割边。
6. 关于含有n 片树叶的最优二叉树描述, 不正确的是( ).
A. 含有n 片树叶的最优二叉树每个分支点都有两个孩子;
B. 含有n 片树叶的最优二叉树分支点的个数是n-1;
C. W(T)等于个分支点的权重(构造最优二叉树时产生)之和;
D. 在权重一定的前提下,含有n 片树叶的最优二叉树是惟一的。
7. 彼得森图是 ( )。
A. 平面图 B. 二部图 C. Euler图 D. 以上都不是
二、1. 一棵二叉树先序遍历得ABDECF ,中序遍历得DBEACF, 则后序遍历的结果是________________。
- 21 -
2. 一无向图存在生成树的充分必要条件是 。
3. 最优二叉树有n 片树叶,则它有 分支点。
三、1.(1)在一棵有2个2度顶点,4个3度顶点,其余顶点都是树叶的无向树中应该有几片树叶?
(2)画出两棵非同构的满足上述条件的无向树 。
2.
画一棵带权为2,2,2,3,3,4,5,8的最优二叉树T ,并计算它的权W (T )。
3. 求下2图的最小生成树。
B
A
C 46D E
4. 已知连通的平面图G 的阶数n=6,边数m=8,面数r=4。求G 的对偶图G*的阶数n*,边数m*,面数r*。
四、证明若图G 是自对偶的,则m=2n-2。其中n 为G 的结点数,m 为G 的边数。
- 22 -
第九章 代数系统
一、选择题
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 上的一个二元运算,使得∀x , y ∈R ,都有x*y=x+y+x∙y 。指出*运算的性质,并求出它的单位元,零元和所有可逆元素的逆元。(仿例9.6)
- 23 -
四、S=Q×Q, 其中Q 为有理数集合,定义S 上的二元运算*,
∀,∈ S,*=,
(1)求*.
(2)已知*=,求a,b.
(3)*是可交换的吗?是可结合的吗?
五、设A={0,1,2,3,4},定义 * 运算如下:a *b =(a +b ) mod 5,
(1) 列出 * 的运算表;
(2) * 是否有零元、幺元?如有,则求出相应值,求出具有逆元的元素和相应的逆元。
- 24 -