离散数学(6 学分)考试卷-
离散数学期终试题
6 学时
10,设图 T 为树,且 T 有度数为 4 的顶点 2 个,度数为 3 的顶点 5 个,其余 片树叶. 的顶点是树叶,则 T 有 二, 在谓词逻辑中,构造下面推理的证明: 每个大学生,不是文科生,就是理科生.有的大学生是优等生.小李不是 理科生,但是优等生.因此若小李是大学生,她就是文科生.
任课教师 ___________姓 名_____________学 号____________得 分 _____________
一, 填空题 1, 100 名学生中,有 33 人学数学,有 23 人学物理,有 47 人学电脑,有 13 人既学数学又学物理,有 14 人既学物理又学电脑, 有 16 人既学数学又 学电脑, 有 30 人什么都不学,则三门都学的人数为___________. 2, (( P ∨ Q) → R) → P 的主合取范式是_____________. 3, 设 R 为 A={2,3,4,5,6,7,8,10,12,16,24}上的整除关系, (A,R)为偏序 集,则 A 的极大元是_____________,极小元是___________________. 4, 设 A 为无限集,B 为有限集,按势的从小到大顺序排列下列各集 . _______ (1)有理数集 Q ; (3) Q ∪A ; (4) B; (2)A 的幂集 P(A); (5) B 的幂集 P(B)
三, 设 F 和 G 都是一元谓词符号,请给出一个解释来说明谓词公 式
1 2 3 4 5 1 2 3 4 5 5, 在 5 个文字的对称群 S5 中,σ = ,τ = , 5 4 3 1 2 3 4 5 2 1 则 στσ 1 写成不相交轮换之积的形式是 6, 记 2Z = { x x = 2n, n ∈ Z} , ( 2Z, +, × ) 具有性质 环 A, 是一个交换环; C,是一个无零因子的环. B,是一个含幺环; . .
((x)( F ( x) → G ( x)) ((x) F ( x) → (x)G ( x)) 不是逻辑有效式.
7, 在实数集 R 上定义运算 ⊕ 和 如下:对 a, b ∈ R , a ⊕ b = a + b 1 ,
a b = a + b ab ,则 2 ⊕ 2 关于 的逆元是
.
8 , 设 图 G 是 Hamilton 图 , 则 可 以 对 图 G 的 边 指 定 方 向 使 其 成 为 图. . 9,若图 G 中每个顶点的度数都不少于 2,则图 G 中必有
离散数学(6 学分)考试卷-
四,设 X , Y 为两个集合, P( X ), P(Y ) 分别 X , Y 为的幂集. (1) 设 f : X
五, S 是一个集合,G 是一个群,令 S G 表示从 S 到 G 的所有映射的集合,对 任意 f , g ∈ S G ,定义 ( f g )( s ) = f ( s ) g ( s ) , s ∈ S ,试证: ( S G , ) 是一 个群.
Y 为函数,
1
对 任 意 B ∈ P(Y ) , 定 义
g : P(Y )
P( X ) 使 g ( B) = f
( B) = {x ∈ X | f ( x) ∈ B}∈ P( X ) .
证明:⑴ f 为单射当且仅当 g 为满射. (2) 若 X 的势 ≤ Y的势 ,则 P ( X )的势 ≤ P(Y )的势 .
x ∨ a = b ,是一个 B 六, 设 B 是一个 Boole 代数,a, b ∈ B ,且 a ∧ b = a . x ∧ a = 0
中的方程组 ⑴ 试证: x = a ∧ b 是它的一个解; ⑵ 试证方程组只有唯一的一个解
离散数学(6 学分)考试卷-
七, 证明题 1.证明:若图 G 是有 10 个顶点,11 条边,则图 G 中至少有一个度数都不少 于 3 的顶点. 2.证明:若图 G 为连通的且所有的边都是割边,则图 G 必是树.
八, 计算 设 D 为有向图,如图. 求(1)图 D 的邻接矩阵 A ; (2)图 D 的可达矩阵 P .
1
2
3
4