三套离散卷子
试卷六试题与答案
一、 填空 15% （每小题 3分）
1、 n 阶完全图结点v 的度数d(v) = 。
2、 设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个
k+1度顶点，则N k = 。 3、 算式 )*()*)*(((f e d c b a ÷+的二叉树表示为
。 4、 如图
给出格L ，则e 的补元是 。
5、 一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 。
二、选择 15% （每小题 3分）
1、设S={0,1,2,3},≤为小于等于关系，则{S ，≤}是（ ）。
A 、群；
B 、环；
C 、域；
D 、格。 2、设[{a , b , c}，*]为代数系统，*运算如下：
则零元为（ ）。
A 、a ；
B 、b ；
C 、c ；
D 、没有。
3、如右图 相对于完全图K 5的补图为（ ）。
4、一棵无向树T 有7片树叶，3个3度顶点，其余顶点均为4度。则T 有（ ）4度结点。
A 、1；
B 、2；
C 、3；
D 、4。
5、设[A ，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（ ）时，[A ，+，·]是整
环。
A 、},2|{Z n n x x ∈=；
B 、},12|{Z n n x x ∈+=；
C 、},0|{Z x x x ∈≥且；
D 、},,
5|{4
R b a b a x x ∈+=。
三、证明 50%
1、设G 是（n,m ）简单二部图，则42
n m ≤
。（10分）
2、设G 为具有n 个结点的简单图，且
)2)(1(21
-->
n n m ，则G 是连通图。（10分）
3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：
（144、 ],,[⊕?L 是一代数格，“≤”为自然偏序，则[L ，≤]是偏序格。（16分）
四、10%
设)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=是布尔代数],,},1,0[{-∧∨上的一个布尔表达式，试写出),,(321x x x E 的析取范式和合取范式（10分）
五、10%
如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。
答案：
一、填空 15%（每小题3分）
1、n-1；
2、n(k+1)-2m ；
3、如右图；
4、0 ；
5、臂力小者 二、选择 15%（每小题 3分）
50%
1、 证：设G=（V ，E ）n n n n Y n X Y X V =+==?=2121
,,,
对完全二部图有
4)2()(2
21121
1121n n n n n n n n n n n m +
--=+-=-=?= 当
21n
n =
时，完全二部图),(m n 的边数m 有最大值42n 故对任意简单二部图),(m n 有
42
n m ≤
。 2、 证：反证法：若G 不连通，不妨设G 可分成两个连通分支G 1、G 2，假设G 1和G 2的顶点数分别
为n 1和n 2，显然n n n =+21
11112121-≤-≤∴≥≥n n n n n n 2)2)(1(2)2)(1(2)1(2)1(212211--=-+-≤-+-≤
∴n n n n n n n n n m
与假设矛盾。所以G 连通。 3、 （1）[{0，1}，+，·]是环
①[{0，1}，+]是交换群
乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。 群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；
（0+1）+0=0+（1+0）=1 ； （0+1）+1=0+（1+1）=0； （1+1）+1=1+（1+1）=0 …… 结合律成立。
题目 1 2 3 4 答案
D
C
A
A
幺：幺元为0。
逆：0，1逆元均为其本身。 ②[{0，1}，·]是半群 乘：由“· ”运算表知封闭
群： （0·0）·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）= 0；
（0·1）·0=0·（1·0）=0 ； （0·1）·1=0·（1·1）=0； （1·1）·1=1·（1·1）=0 。 ③·对+的分配律 }1,0{,∈?y x Ⅰ 0·（x+y ）=0=0+0=(0·x)+(0·y)； Ⅱ 1·（x+y ） 当x=y (x+y)=0 则
)
1()1()11()11()01()01(1100001)(1y x y x ?+?=???
????+??+?=??????++==?=+?；
当y x ≠（1=+y x ）则
)
1()1()11()01()01()11(1001111)(1y x y x ?+?=???
????+??+?=??????++==?=+?
所以}1,0{,,∈?z y x 均有)()()(y z x z y x z ?+?=+? 同理可证：)()()(z y z x z y x ?+?=?+ 所以·对+ 是可分配的。
由①②③得，[{0，1}，+，·]是环。 （2）[{0，1}，+，·]是域
因为[{0，1}，+，·]是有限环，故只需证明是整环即可。 ①乘交环： 由乘法运算表的对称性知，乘法可交换。 ②含幺环：乘法的幺元是1 ③无零因子：1·1=1≠0
因此[{0，1}，+，·]是整环，故它是域。
4、证：（1 ）“≤”是偏序关系， ≤ 自然偏序 a b a L
b a =?∈?,
①反自反性：由代数格幂等关系：a a a a a ≤∴=?。 ②反对称性：L b a ∈?, 若 a b b a ≤≤, 即：b a b a b a =?=?,，
则 b a b b a a =?=?= a b ≤ ③传递性：c b b a ≤≤,则：
a b a b a a b c b b a c b a a
b a b a
c b a c a =?≤==?≤?=??==?≤??=?即即结合律即 c b )()(
c a ≤∴
（2）L
y x ∈?,在L 中存在{x,y}的下（上）确界
设L y x ∈,则：},inf{y x y x =?
事实上：y x y x x y x x ?=??=??)()(
y y x x y x ≤?≤?∴:同理可证
若{x , y }有另一下界c ，则c y c y x c y x c =?=??=??)()(
y x c ?≤∴ y x ?∴是{x , y }最大下界，即},inf{y x y x =?
同理可证上确界情况。 四、14% 解：函数表为：
析取范式：
)
()()
()()(),,(321321321321321321x x x x x x x x x x x x x x x x x x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧=
合取范式：)()()(),,(321321321321x x x x x x x x x x x x E ∨∨∧∨∨∧∨∨∨=
五、10%
解： 用库斯克（Kruskal ）算法求产生的最优树。算法为：
43433733727227711713
),(9),(4),(1),(v v e v v w v v e v v w v v e v v w v v e v v w ========选选选选
结果如图：
树权C(T)=23+1+4+9+3+17=57（万元）即为总造价
/*********************************************************************************/
试卷十四试题与答案
一、 填空 10% （每小题 2分）
1、 设>-∧∨<,,,A 是由有限布尔格≤><,A 诱导的代数系统，S 是布尔格≤><,A ，中所有原
子的集合，则>-∧∨<,,,A ～ 。 2、 集合S={α，β，γ，δ}上的二元运算*为
那么，代数系统
]3mod )[(][][3j i j i +=+，则+3的运算表为 ；
4、 设G 是n 阶完全图，则G 的边数m= 。
5、 如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要
执行 次这个加法指令。
二、 选择 20% （每小题 2分）
1、 在有理数集Q 上定义的二元运算*，Q y x ∈?,有xy y x y x -+=*，
则Q 中满足（ ）。
A 、 所有元素都有逆元；
B 、只有唯一逆元；
C 、1,≠∈?x Q x 时有逆元1
-x ； D 、所有元素都无逆元。
2、 设S={0，1}，*为普通乘法，则< S , * >是（ ）。
A 、 半群，但不是独异点；
B 、只是独异点，但不是群；
C 、群；
D 、环，但不是群。
3、图 给出一个格L ，则L 是（ ）。
A 、分配格；
B 、有补格；
C 、布尔格；
D 、 A,B,C 都不对。
3、 有向图D=
，则41v v 到长度为2的通路有（ ）条。
A 、0；
B 、1；
C 、2；
D 、3 。
4、 在Peterson 图中，至少填加（ ）条边才能构成Euler 图。
A 、1；
B 、2；
C 、4；
D 、5 。
三、 判断 10% （每小题 2分）
1、 在代数系统
-e a 存在，
则它一定唯一且1
1--=e a a 。（ ）
2、 设
3、 设},,3|{均为有理数b a b a x x A +==， +,·为普通加法和乘法，则代数系统
是域。（ ）
4、 设G=
5、 如果一个有向图D 是欧拉图，则D 是强连通图。（ ）
四、证明 46%
1、 设
A x ∈?∈??,，使得e x x =*?， 则是群。（10分）
2、 循环群的任何非平凡子群也是循环群。（10分）
3、 设aH 和bH 是子群H 在群G 中的两个左陪集，证明：要末Φ=?bH aH ，要末
bH aH =。（8分）
4、 设，是一个含幺环，|A|>3，且对任意A a ∈?，都有a a a =?，则
不可能是整环（这时称是布尔环）。（8分） 5、 若图G 不连通，则G 的补图G 是连通的。（10分）
五、布尔表达式 8%
设)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=是布尔代数>∧∨<,,},1
,0{上的一个布尔表
达式，试写出其的析取范式和合取范式。
六、图的应用 16%
1、 构造一个结点v 与边数e 奇偶性相反的欧拉图。（6分）
2、 假设英文字母，a ，e ，h ，n ，p ，r ，w ，y 出现的频率分别为12%，8%，15%，7%，6%，10%，5%，
10%，求传输它们的最佳前缀码，并给出happy new year 的编码信息。（10分） 答案
二、
填空 10%（每小题2分）
1
、
(S), ~ ,,??>；2、β，γ；3、 是； 4、)1(21 -n n ；5、9 三、 选择 10%（每小题 2分） 四、 判断 10%（每小题2分） 五、 证明 46% 1、（10分）证明： （1）c b c a b a A c b a ==∈?则若**,,, c b c e b e c a a b a a c a a b a a a c a b a ==∴==?∴=:**,*)*?(*)*?()*(*?)*(*??**:即使事实上 (2) e 是之幺元。 事实上：由于e 是左幺元，现证e 是右幺元。 为右幺元 即由使e x e x x x e e e e x x e x x x A e x A x ∴=====?∈∈?,*)1(*?**)*?()*(*??,*, （3） A x A x ∈∈?-1 ,则 x x e x x x x e x x x e x e x x x x x x x A x ??**??***)*?(**)?*(:有逆元故有事实上∴=======∈? 由（2），（3）知： 设 S a m ∈，对任意S a l ∈，必有0,0,><≤+=t m r r tm l ， 故：S a a a a a a t m l tm l tm l r ∈===---)(** 即：S a a a t m r l ∈=)(* 所以S a r ∈但m 是使S a m ∈的最小正整数，且m r <≤0，所以r=0即：t m l a a )(= 这说明S 中任意元素是m a 的乘幂。 所以 a 为生成元的循环群。 3、（8分）证明： 对集合bH aH 和，只有下列两种情况： （1）Φ≠?bH aH ； （2）Φ=?bH aH 对于Φ≠?bH aH ，则至少存在H h h ∈21,，使得21 bh ah =，即有1 12-=h bh a ，这时任意aH ah ∈， 有bH h h bh ah ∈=-1 12，故有bH aH ? 同理可证：aH bH ?所以 bH aH = 4、（8分）证明： 反证法：如果，是整环，且有三个以上元素，则存在a a a a a A a =?≠≠∈且1,,θ 即有：θθθ=-=-?=-?≠-≠a a a a a a a a a )1(1,但这与整环中无零因子条件矛盾。因此 不可能是整环。 5、（10分）证明： 因为G=< V ，E>不连通，设其连通分支是)2() (,),(1≥k V G V G k ，V v u ∈?,，则有两种情况： （1） u , v ，分别属于两个不同结点子集V i ，V j ，由于G(V i ) , G(V j )是两连通分支，故(u , v)在不G 中， 故u , v 在G 中连通。 （2） u ,v ，属于同一个结点子集V i ，可在另一结点子集V j 中任取一点w ，故(u , w),(w , v )均在G 中， 故邻接边( u ,w ) ( w , v ) 组成的路连接结点u 和v ，即u , v 在G 中也是连通的。 五、布尔表达式 8% 函数表为： 析取范式： ) ()() ()()(),,(321321321321321321x x x x x x x x x x x x x x x x x x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧= 合取范式：)()()(),,(321321321321x x x x x x x x x x x x E ∨∨∧∨∨∧∨∨= 六、 树的应用 16% 1、（6分）解： 2、（10分）解： 根据权数构造最优二叉树： 传输它们的最佳前缀码如上图所示，happy new year 的编码信息为： 10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最优二叉树求解过程如下： /*********************************************************************************/ 试卷十三试题与答案 四、 填空 10% （每小题 2分） 1、}0|{>∧∈=+ x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算的幺元 是 ，零元是 。 2、代数系统 则θ和e 的关系为 。 3、设 4、图的完全关联矩阵为 。 5、一个图是平面图的充要条件是 。 五、 选择 10% （每小题 2分） 1、 下面各集合都是N 的子集，（ ）集合在普通加法运算下是封闭的。 A 、{x | x 的幂可以被16整除}； B 、{x | x 与5互质}； C 、{x | x 是30的因子}； D 、{x | x 是30的倍数}。 2、 设>=< },2,1,0{1G ，>=<},*1,0{2G ，其中 表示模3加法，*表示模2乘法，则积代数2 1G G ?的幺元是（ ）。 A 、<0,0>； B 、<0,1>； C 、<1,0>； D 、<1,1> 。 3、 设集合S={1,2,3,6}，“≤”为整除关系，则代数系统< S , ≤ >是（ ）。 A 、域； B 、格，但不是布尔代数； C 、布尔代数； D 、不是代数系统。 4、 设n 阶图G 有m 条边，每个结点度数不是k 就是k+1，若G 中有N k 个k 度结点， 则N k =（ ）。 A 、n ·k ； B 、n(k+1)； C 、n(k+1)-m ； D 、n(k+1)-2m 。 5、 一棵树有7片树叶，3个3度结点，其余全是4度结点， 则该树有（ ）个4度结点。 A 、1； B 、2； C 、3； D 、4 。 三、判断10% （每小题 2分） 1、（ ）设S={1,2}，则S 在普通加法和乘法运算下都不封闭。 2、（ ）在布尔格 个成立。 3、（ ）设N x Z x x S =≥∧∈=}0|{，+,·为普通加法和乘法，则 4、（ ）一条回路和任何一棵生成树至少有一条公共边。 5、（ ）没T 是一棵m 叉树，它有t 片树叶，i 个分枝点，则(m-1)i = t-1。 四、证明 38% 1、（8分）对代数系统 （2）每个元素的逆元是唯一的。 2、（12分）设>-∧∨<,, , A 是一个布尔代数，如果在A 上定义二元运算☆，为)()(☆b a b a b a ∧∨∧=，则 3、（10分）证明任一环的同态象也是一环。 4、（8分）若), (,e E v V E V G ==> =<是每一个面至少由k(k ≥3)条边围成的连通平面图，则 2) 2(--≤ k v k e 。 五、应用 32% 1、 （8分）某年级共有9门选修课程，期末考试前必 须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？ 2、 用washall 方法求图 的可达矩阵， 并判断图的连通性。（8分） 3、 设有a 、b 、c 、d 、e 、f 、g 七个人，他们分别会讲的语言如下：a ：英，b ：汉、英，c ：英、西班牙、 俄，d ：日、汉，e ：德、西班牙，f ：法、日、俄，g ：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分） 4、 用 Huffman 算法求出带权为2，3，5，7，8，9的最优二叉树T ，并求W （T ）。 若传递a ，b ， c ， d ，e ， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。（8分） 答案： 六、 填空 10%（每小题2分） 1、1， 不存在； 2、θ≠e ； 3、G b a ∈?,有)*(*)*()*(*)*(b b a a b a b a =； 4、 3, 35 七、 选择 10%（每小题 2分） 八、 判断 10% 九、 证明 38% 1、（8分）证明： （1）设A c b a ∈,,，b 是a 的右逆元，c 是b 的右逆元，由于b e b b a b ==*)*(*， a b e a b c b a b c b a b c b e **)*()*(*)*(*)*(**===== 所以b 是a 的左逆元。 （2）设元素a 有两个逆元b 、c ，那么 c c e c a b c a b e b b =====**)*()*(** a 的逆元是唯一的。 2、（12分）证明： [乘]，A ，，上封闭在-∧∨ ∴ 运算☆在A 上也封闭。 [群] A c b a ∈?,, )()()()()(:) ()()()()))()((()()())()(()()())()(()))()((())()(()(c b a c b a c b a c b a c b a c b a c b a c b a c b a c a b a c b a c b a c b a b a c b a c b a c b a b a c b a b a c b a b a c b a ∧∧∨∧∧∨∧∧∨∧∧=∧∧∨∧∧∨∧∧∨∧∧=∧∧∨∧∨∧∧∨∧∧=∧∨∧∨∨∧∧∨∧∧=∧∧∨∧∨∧∧∨∧=∧∨∧=☆☆同理可得☆☆☆ )()(c b a c b a ☆☆☆☆=∴ 即☆满足结合性。 [幺] A a ∈?,a a a a a a a =∨=∧∨=∧∨∧==0)1(0)0()0(00☆☆ 故全下界0是A 中关于运算☆的幺元。 [逆] A a ∈?,000)()()(=∨=∧∨∧=a a a a a a ☆ 即A 中的每一个元素以其自身为逆元。 [交] a b a b a b b a b a b a ☆☆=∧∨∧=∧∨∧=)()()()( 即运算☆具有可交换性。 所以 设>?+<,,A 是一环,且>?⊕<,,)(A f 是关于同态映射f 的同态象。 由>+<,A 是Abel 群，易证>⊕<,)(A f 也是Abel 群。 >?<,A 是半群，易证>?<,)(A f 也是半群。 现只需证：?对⊕是可分配的。 3,2,1,)(:,,),(,,321321==∈?i b a f a a a A f b b b i i 使得则必有相应的 于是 ) ()())()(())()(()()())()(())(())(()())()(()()(3121312131213121321321321321b b b b a f a f a f a f a a f a a f a a a a f a a a f a a f a f a f a f a f b b b ?⊕?=?⊕?=?⊕?=?+?=+?=+?=⊕?=⊕? 同理可证)()()(1312132b b b b b b b ?⊕?=?⊕ 因此>?⊕<,,)(A f 也是环。 5、（8分）证明： 设G 有r 个面， k e r kr e r i k r e r i r i i 22)1()deg(,2)deg(1 ≤ ≥∴≤≤≥=∑=即而 2)2(22,2--≤=≥+ -=+-k v k e k r e v r e v 即故而 。 十、 应用32% 1、（8分） 解：)(G χ即为最少考试天数。 用Welch-Powell 方法对G 着色：685421739v v v v v v v v v 第一种颜色的点 6419v v v v ，剩余点85273v v v v v 第二种颜色的点 573v v v ，剩余点82v v 第三种颜色的点 82v v 所以)(G χ≤3 任932v v v 构成一圈，所以)(G χ≥3 故)(G χ=3 所以三天下午即可考完全部九门课程。 2、（8分） 解： ??????? ??=00 1010000101 110 )(G A =i 1：A[2，1]=1，??? ???? ? ?=00 10 10001101110 A ； =i 2： A[4，2]=1，??????? ? ?=111110001101 110 0A =i 3： A[1，3]=A[2，3]=A[4，3]=1，??????? ??=1111 10001101110 A =i 4： A[k ，4]=1，k=1，2，3，4，??????? ? ?=111 1 11111111111 1 A p 中的各元素全为1，所以G 是强连通图，当然是单向连通和弱连通。 3、（8分） 解：用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为 此图中的Hamilton回路即是圆桌安排座位的顺序。 Hamilton回路为a b d f g e c a。 4、（8分） 解：(1) ? + + + ? ? + T W = ? ? ? + 2 7 2 2 8 83 2 (= 9 4 ) 3 3 4 5 （1）用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e 传输它们的最优前缀码为{0000，0001，001，01，10，11} 。 华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x 2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数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∈Z D.〈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 A B.R C.R∪{〈c,a〉} D.R∩I A 9.设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 《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答:(1),(4) 2、下列公式中哪些就是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个就是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答:(2),(3),(4),(5),(6) 4、公式?x((A(x)→B(y,x))∧ ?z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。 答:x,y, x,z 5、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (2) 陕西师大就是一座工厂。 (3) 您喜欢唱歌不？ (4) 若7+8＞18,则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答:(1) 就是,T (2) 就是,F (3) 不就是 (4) 就是,T (5) 不就是 (6) 不就是 6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。 答:所有人都不就是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义就是( )。 (1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0) 答:(1)对任一整数x 存在整数 y 满足x+y=0(2)存在整数y 对任一整数x 满足x+y=0 9、设全体域D 就是正整数集合,确定下列命题的真值: (1) ?x ?y (xy=y) ( ) (2) ?x ?y(x+y=y) ( ) (3) ?x ?y(x+y=x) ( ) (4) ?x ?y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 就是奇数,Q(x):x 就是偶数,谓词公式 ?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2就是偶数或-3就是负数”的否定就是( )。 答:2不就是偶数且-3不就是负数。 12、永真式的否定就是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 一、 填空 10% （每小题 2分） 1、}0|{>∧∈=+ x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算 的幺元是 ，零元是 。 2、代数系统 A 、1； B 、2； C 、3； D 、4 。 三、判断10% （每小题 2分） 1、（ ）设S={1,2}，则S 在普通加法和乘法运算下都不封闭。 2、（ ）在布尔格 山东大学考研有靠谱的辅导机构吗 随着考研人数日趋增多，考研的竞争也是日渐加大。对于考名校的同学来说，竞争对手数量多实力强，怎么才能突出重围成功考上呢？有没有什么捷径可走呢？ 我的回答是真的没有，要想成功上岸只能靠自己一步一个脚印去努力，一蹴而就是没可能的，但是可以有策略。就我自己而言，我是成功考上山东大学的计算机专业。其实我本科并不是计算机专业，但是择校的时候通过各方信息收集，实现了曲线救国。 具体过程是这样的：19年4月份了解到山东大学的数学学院的网络空间安全专业要独立出来成立网络空间安全(研究院)学院，而我本科也很喜欢计算机方向，本科也上了不少课程，但当时就心动了，就进一步进行了解，原来山东大学的网络空间安全原来属于数学系，在数学系下招生，而且有一个非常厉害的教授叫王小云院士，破解了几个非常难以破解的密码，一举带领山东大学走上国际顶级水平；并且在国家大力推行人工智能、数据分析、网络安全的研究，山东大学成立网络空间安全学院，顺势而为，非常具有吸引力，我感觉找到了一个非常不错的专业，看了学院的2020年的招生计划，计划2020年招收17个学硕，20个专硕和10个左右的非全，感觉招生人数虽然只有37个左右，但是考虑到今年第一年招生，是第一个吃螃蟹的人，报 考的人应该不会很多，所以机会还是很大的，但是弊端就是由于第一年招生没有往年的真题，所以准备专业课可能有一点困难，但是看到招生目录上的专业课有三个方向，专业课都是数据结构+计算机网络(824)或是离散数学(826)，可以根据自己选择考824还是826，这些专业课本科都学过而且也学得不错，但是离散数学感觉难度有一点大，就选择了数据结构和计算机网络。 其实择校的话就是一个信息收集的过程，能够获得一手信息就能领先一步。对于考山大的学弟学妹们来说，如果你对哪个专业有疑问，可以多向专业的机构咨询，这就是策略。 在这方面我推荐新祥旭考研辅导机构，他们做一对一的辅导已经15年了。对山大各专业的情况都有非常全面的信息，能够结合你的实际情况快速的帮你分析各专业方向的利弊，把专业确定下来。 当然除此之外，他们也有各专业比较优秀的辅导老师，只要你考虑辅导，他们就能结合你的实际情况快速的给你匹配到适合你学习风格的辅导老师，提高整体的复习效率。 考研不易，择校有策略。备考找辅导也是策略，只要能实现梦想突出重围大家可以多多尝试。 安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈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 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x是域。华南农业大学 离散数学 期末考试2013试卷及答案
(完整版)离散数学试卷及答案
中国石油大学大学《离散数学》期末复习题及答案
离散数学试卷及答案一
山东大学离散数学题库及答案
离散数学期末试卷A卷及答案
大学离散数学期末重点知识点总结(考试专用)
最新离散数学试卷及答案(13)
是域。 4、（ ）一条回路和任何一棵生成树至少有一条公共边。 5、（ ）没T 是一棵m 叉树，它有t 片树叶，i 个分枝点，则(m-1)i = t-1。 四、证明 38% 1、（8分）对代数系统山东大学考研有靠谱的辅导机构吗
安徽大学期末试卷离散数学上卷及参考答案.doc