1. (6分) 已知 a=,a,b}, b=, a}, 求 a×b, ab, p(a).
解： a×b=,)a), a, )a, a), b, )b, a
ab=(a-b) ∪b-a)=,b, }
p(a)=,a, b, ,a}, b}, a}.
2. (4分) 已知r1,r2是a上的对称关系， r1r2对称吗？ 证明或举反例说明。
解： 一般地， r1r2≠ r1r2.
反例： r1= 对称！
r2= 对称！
r1r2 = 不对称！
3. (6分) g是一个群， h是g的子群。 g1,g2g, (g1,g2) r g1g2-1 h. 证明r是g上等价关系。
证明： ◆对于任意的ag，∵ a·a-1=eh，a,a) r，故r是自反的。
对于任意的a，bg，若(a,b) r，a·b-1h，∴(a·b-1)-1=b·a-1h，b,a) r，故r是对称的。
对于任意的a,b,cg，若(a,b) r，(b,c) r，a·b-1h且 b·c-1h，a·b-1)·(b·c-1)=a·c-1h，a,c) r，故r是传递的。
4. (6分) a=, x,ya, xyx|y.
(1) 画出(a, )的哈斯图。
(2) 判断(a, )是格否？分配格吗？有补格？布尔格吗？
5. 已知 f: a→b, g: b→c, f是单射，g是单射，证明gf 是单射。 若gf是满射，证明g是满射。
证明： (1) 对于任意的x1,x2a, 若gf (x1)= gf (x2),
即有 g(f(x1))=g(f(x2)).
由于g是单射，故有f(x1)=f(x2).
由于f是单射，故有x1=x2.
因而， gf 是单射。
(2) 对于任意zc, 存在xa, 使得。
gf (x)=z,即 g(f(x))=z.
故存在 y=f(x) b, 使得。
g(y)=z.
故 g是满射。
6. (4分) 已知： a是可数无限集，b是有限集， 且a∩b=，求证：|a|=|a∪b|
证明： 不妨记。a=b=
作映射 φ:a→a∪b
ai)=bi (i=1,…,m)
ai)=ai-m (i=m+1,m+2,…)
则可以说明φ为a→a∪b的双射，故结论得证。
如果只用一句话说， a∪b也是可数无限集，可以得2分）
7. (5分) 画出5个顶点的自互补图。证明当n=4k 或4k+1时才有。 若一个图和它的补图同构，说它是自互补图。
8. (5分) 证明： g或者g有一个是连通图。
9. (4分) 一个有奇数条边、偶数个顶点的欧拉图，但不是哈密尔顿图。
10 (6分) 画出k4,4，判断k4,4是否平面图。
11. (5分) 证明： 多于一个顶点的树，至少有两片树叶。
12. (8分) (g, ·是一个群，取定u g. g1,g2g，定义：
g1*g2= g1·u-1·g2. 证明： (g,*)是群。
证明： (1) 封闭性。
2) 可以结合性。
3) 幺元 e*=u.
事实上， g*e*=g*u=g·u-1·u=g·e=g
e**g=u*g=u·u-1·g=e·g=g
(4) 逆元。
对于gg, 在代数运算*下的逆元记为g*-1
于是， g*-1=u·g-1·u
这里， g-1是在代数运算·下的逆元。
13. (5分) g是一个群，h,k是g正规子群。
证明： h∩k是g正规子群。
证明： (1) (3分)
a,b hk,就有a,b h, a,b k，因为h, k是群g的子群，所以，a*b-1h，a*b-1k，因此a*b-1 hk。故 hk是g的子群。
2) (2分)
对于a hk, gg, 就有a h，ak。
因为h，k是群g的正规子群，所以。
g*a*g-1h,
g*a*g-1k,从而有g*a*g-1hk，故hk是g的正规子群。
14. (4分) 已知(g, *a, △是两个群，f: g→a是群同态的。
证明： (1) f(eg)=ea (eg g是幺元， ea a是幺元).
2) gg, f(g-1)=(f(g))-1.
15. (4分) 下列哪些是循环群：zn
qz616. (4分) 试证明联结词集合是完备的。
证明： p∨q= p q
p∧q=( p ∨ q)
pq =（p ∨ q） ∧p ∨ q）
即可以用表示出来。
所以任何公式均可以由集合中的联结词表达出来的公式与之等价。
故集合是完备的。
17. (4分) 试求公式 (p∧q)((q→r)p)的主析取范式和主合取范式。
解： (p∧q)((q→r)p)
p∧q)((q∨r)p)
p∧q)((q∨r) ∧p) ∨q∨r) ∧p))
p∧q)((q∧p)∨(r∧p) ∨q∧r) ∧p))
p∨q∨ (q∧p)∨(r∧p) ∨q∧r∧p)
p∨q∨ (q∧r∧p)
p∧q∧r) ∨p∧q∧r) ∨p∧q∧r) ∨p∧q∧r) ∨p∧q∧r) ∨p∧q∧r) ∨p∧q∧r)
7)= p∨q∨r
18. (6分) 将下列语句化为含有量词的谓词演算公式。
不是每个人都能干，但一定有人能干。
有一种气体可以腐蚀任何金属。
凡是对顶角一定相等。
19. (5分) 已知公理 a: (pq) (qp) (pq))
b: pp∨q
c: ppd: (pr) (qr) (p∨q) r))
e: p∧qp
证明定理： p(p∨p)
证明：1) pp∨q公理b
2) pp∨p代入。
3) (pr) (qr) (p∨q) r公理d
4) (pp) (pp) (p∨p) p代入。
5) p p公理c
6) (pp) (p∨p) p4)(5)分离。
7) (p∨p) p5)(6)分离。
8) (pq) (qp) (pq公理a
9) (p(p∨p)) p∨p)p) (p(p∨p)))代入。
10) (p∨p)p) (p(p∨p2)(9)分离。
11) (p(p∨p7)(10)分离
20. (5分) 试求公式 x((yx(x,y))(zy(z) ∧z(x))
解： 原式= xyx(x,y) ∨zy(z) ∧z(x))
xy z(x(x,y) ∨y(z) ∧z(x))
离散数学试题
网络学院离散数学模拟试题1 考试时间 90 分钟考试方式 开卷。专业年级姓名学号 一 选择填空题 每个空格3分，共30分。答案写在答题纸上。1b.b.cd.2 若集合p q满足，则 必成立。c abcd 3 设，则是 d a 从x到y的双射。b 从x到y的满射，但不是单射。c 从x到y的映射，但不是...
离散数学试题
一 填空题 每题2分，共14分 1 若g为连通的平面图，有n个顶点，k个面，则g的边数为。2 设a b 则a b 3 集合的幂集。4 设表示 会飞 论述域为，则命题 一切鸟都会飞 可译为 5 若集合a上的二元关系r的关系矩阵主对角线上元素全是1，则关系r具有性质。6 公式的对偶公式为。7 连通无向图...
离散数学试题
1 设a是m元集合，b是n元集合。问a到b共有多少个不同的二元关系？设a b 试写出a到b的全部二元关系。p18 2 用演绎法证明共同蕴涵p s。p48 3 将下面的命题符号化 已知每一个运动员都是强壮的，而每一个既强壮又聪明的人在他所从事的事业中都将获得成功，彼得是运动员并且是聪明的，证明彼得在他...