1、离散试卷及答案 第 1 页 共 21 页 离散数学试题 (A 卷 及 答案) 一、证明题 ( 10 分) 1)(P (Q R) (Q R) (P R)R 证明 : 左端 (P Q R) (Q P) R)(P Q) R) (Q P) R) (P Q) R) (Q P) R)(P Q) (Q P) R (P Q) (P Q) RT R(置换 )R 2)x(A(x)B(x) xA(x)xB(x) 证明 : x(A(x)B(x)x(A(x) B(x)xA(x) xB(x)xA(x)xB(x)xA(x)xB(x) 二、求命题公式 (P (Q R)(P Q R)的主析取范式和主合取范式 ( 10分) 证明
2、: (P (Q R)(P Q R)(P (Q R) (P Q R) ( P (Q R)) (P Q R) (P Q) (P R) (P Q R) (P Q R) (P Q R) (P Q R) (PQ R) (P Q R) m0 m1 m2 m7 M3 M4 M5 M6 三、推理证明题 ( 10 分) 1) C D, (C D) E, E(A B), (A B)(R S)RS 证明: (1) (C D)E (2) E(A B) (3) (C D)(A B) (4) (A B)(R S) (5) (C D)(R S) (6) C D 离散试卷及答案 第 2 页 共 21 页 (7) R S 2)
3、 x(P(x)Q(y) R(x) ,xP(x)Q(y) x(P(x) R(x) 证明 ( 1) xP(x) (2)P(a) (3)x(P(x)Q(y) R(x) (4)P(a)Q(y) R(a) (5)Q(y) R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a) R(a) (10)x(P(x) R(x) (11)Q(y) x(P(x) R(x) 四、 设 m是一个取定的正整数,证明:在任取 m 1 个整数中,至少有两个整数,它们的差是 m 的整数倍 证明 设 1a , 2a , 1ma 为任取的 m 1 个整数,用 m去除它们所得余数只能是 0, 1, m 1,由抽屉原理
4、可知 , 1a , 2a , 1ma 这 m 1 个整数中至少存在两个数 sa 和 ta ,它们被 m 除所得余数相同,因此 sa 和 ta 的差是 m 的整数倍。 五、已知 A、 B、 C 是三个集合,证明 A-(B C)=(A-B) (A-C) ( 15 分) 证明 x A-( B C) x A x( B C) x A( xB xC) ( x A xB)( x A xC) x( A-B) x( A-C) x( A-B)( A-C) A-( B C) =( A-B)( A-C) 六、已知 R、 S 是 N 上的关系,其定义如下: R=| x,yN y=x2,S=| x,yN y=x+1。求
5、R-1、 R*S、 S*R、 R 1,2、 S1,2( 10分) 解: R-1=| x,yN y=x2, R*S=| x,yN y=x2+1,S*R=| x,yN y=( x+1) 2, 七 、若 f:A B和 g:B C 是双射,则( gf) -1=f-1g-1( 10 分) 。 证明:因为 f、 g 是双射,所以 gf: A C 是双射,所以 gf 有逆函数离散试卷及答案 第 3 页 共 21 页 ( gf) -1: C A。同理可推 f-1g-1: C A是双射。 因为 f-1g-1存在 z( g-1 f-1) 存在 z( f g) gf( gf) -1,所以( gf) -1=f-1g-
6、1。 R 1,2=,, S1,2=1,4。 八 、 ( 15 分) 设 是半群,对 A中任意元 a和 b,如 a b 必有 a*bb*a,证明: (1)对 A中每个元 a,有 a*a a。 (2)对 A中任意元 a 和 b,有 a*b*a a。 (3)对 A中任意元 a、 b和 c,有 a*b*c a*c。 证明 由题意可知,若 a*b b*a,则必有 a b。 (1)由 (a*a)*a a*(a*a),所以 a*a a。 (2)由 a*(a*b*a) (a*a)*(b*a) a*b*(a*a) (a*b*a)*a,所以有a*b*a a。 (3) 由 (a*c)*(a*b*c) (a*c*a)
7、*(b*c) a*(b*c) (a*b)*c (a*b)*(c*a*c) (a*b*c)*(a*c),所以有 a*b*c a*c。 九 、 给定简单无向图 G ,且 |V| m, |E| n。试证:若 n 21mC 2,则 G 是哈密尔顿图 证明 若 n 21mC 2,则 2n m2 3m 6 ( 1)。 若存在两个不相邻结点 u 、 v 使得 d(u ) d(v ) m,则有 2n Vw wd )( m (m 2)(m 3) m m2 3m 6,与( 1)矛盾。所以,对于 G 中任意两个不相邻结点 u 、 v 都有 d(u ) d(v ) m,所以 G 是哈密尔顿图。 离散数学试题 (B 卷
8、 及 答案) 一、证明题 ( 10 分) 1)(P Q) (P (Q R) (P Q) (P R)T 离散试卷及答案 第 4 页 共 21 页 证明 左端 (P Q) (P (Q R) (P Q) (P R)(摩根律 ) (P Q) (P Q) (P R) (P Q) (P R)(分配律 ) (P Q) (P R) (P Q) (P R) (等幂律 ) T (代入 ) 2)x(P(x)Q(x) xP(x)x(P(x) Q(x) 证明 x(P(x)Q(x) xP(x)x(P(x)Q(x) P(x)x(P(x) Q(x) P(x)x(P(x) Q(x)xP(x) xQ(x)x(P(x) Q(x)
9、二、求命题公式 (PQ)(P Q) 的主析取范式和主合取范式 ( 10 分) 解: (PQ)(P Q)(PQ) (P Q)(P Q) (P Q)(P Q) (P Q) (P P Q) (Q P Q)(PQ)M1m0 m2 m3 三、推理证明题 ( 10分) 1)(P(QS) (R P) QRS 证明: ( 1) R 附加前提 (2)R P P (3)P T(1)(2),I (4)P(QS) P (5)QS T(3)(4),I (6)Q P (7)S T(5)(6),I (8)RS CP 2) x(P(x) Q(x), xP(x)x Q(x) 证明: (1)xP(x) P (2)P(c) T(1
10、),US (3)x(P(x) Q(x) P (4)P(c) Q(c) T(3),US (5)Q(c) T(2)(4),I (6)x Q(x) T(5),EG 离散试卷及答案 第 5 页 共 21 页 四、例 5 在边长为 1 的正方形内任意放置九个点,证明其中必存在三个点,使得由它们组成的三角形(可能是退化的)面积不超过 1/8( 10分) 。 证明: 把边长为 1的正方形分成四个全等的小正方形,则至少有一个小正方形内有三个点,它们组成的三角形(可能是退化的)面积不超过小正方形的一半,即 1/8。 五、已知 A、 B、 C 是三个集合,证明 A (B C)=(A B) (A C) ( 10 分
11、) 证明: x A( B C) x A x( B C) x A( xB xC) ( x A xB)( x A xC) x( A B) x A C x( A B)( A C) A( B C) =( A B)( A C) 六、 =A1, A2, An是集合 A 的一个划分,定义 R=|a、 b Ai, I=1,2, n,则 R是 A 上的等价关系 ( 15 分) 。 证明: a A 必有 i使得 a Ai,由定义知 aRa,故 R自反。 a,b A,若 aRb ,则 a,b Ai,即 b,a Ai,所以 bRa,故 R对称。 a,b,c A,若 aRb 且 bRc,则 a,b Ai及 b,c Aj
12、。因为 i j 时 Ai Aj=,故 i=j,即 a,b,c Ai,所以 aRc,故 R传递。 总之 R 是 A 上的等价关系。 七、若 f:A B是双射,则 f-1:B A是双射( 15 分)。 证明 : 对任意 的 x A,因为 f是从 A 到 B的函数,故存在 y B,使 f, f-1。所以 ,f-1是满射。 对任意的 x A,若存在 y1,y2 B,使得 f-1 且 f-1,则有 f 且 f。因为 f 是函数,则 y1=y2。所以, f-1是单射。 因此 f-1是双射。 八 、 设 是群, 和 是 的 子群,证明:若 A B G,则A G 或 B G( 10分) 。 离散试卷及答案 第
13、 6 页 共 21 页 证明 假设 A G 且 B G,则存在 aA, aB,且存在 bB, bA(否则对任意的 aA, aB,从而 AB,即 A B B,得 B G,矛盾。) 对于元素 a*bG,若 a*bA,因 A 是子群, a-1A,从而 a-1 * (a*b) b A,所以矛盾,故 a*bA。同理可证 a*bB,综合有 a*bA B G。 综上所述,假设不成立,得证 A G或 B G。 九、 若无向图 G 是不连通的,证明 G 的补图 G 是连通的 ( 10 分) 。 证明 设无向图 G是不连通的,其 k 个连通分支为 1G 、 2G 、 、 kG 。任取结点u 、 v G,若 u 和
14、 v 不在图 G的同一个连通分支中,则 u , v 不是图 G 的边,因而 u , v 是图 G 的边;若 u 和 v 在图 G的同一个连通分支中,不妨设其在连通分支 iG( 1 i k )中,在不同于 iG 的另一连通分支上取一结点 w ,则 u , w 和 w ,v 都不是图 G 的边,因而 u , w 和 w , v 都是 G 的边。综上可知,不管那种情况, u 和 v 都是可达的。由 u 和 v 的任意性可知, G 是连通的。 一、 选择题 .(每小题 2分,总计 30) 1. 给定语句如下: ( 1) 15 是素数(质数) ( 2) 10 能被 2整除, 3是偶数。 ( 3)你下午有
15、会吗?若 无会,请到我这儿来! ( 4) 2x+30. ( 5)只有 4是偶数, 3 才能被 2整除。 (6)明年 5 月 1 日是晴天。 以上 6 个语句中,是简单命题的为( A) ,是复合命题的为( B) ,是真命题的为( C) ,是假命题的是( D) ,真值待定的命题是( E) A: (1)(3)(4)(6) (1)(4)(6) (1)( 6) B: (2)(4) (2)(4)(6) (2)(5) 离散试卷及答案 第 7 页 共 21 页 C: (1)(2)(5)(6) 无真命题 ( 5) D: (1)(2) 无假命题 (1)(2)(4)(5) E: (4)(6) ( 6) 无真值待定的
16、命题 2. 将下列语句符号化: ( 1) 4 是偶数或是奇数。( A)设 p: 4 是偶数, q: 4 是奇数 ( 2)只有王荣努力学习,她才能取得好成绩。( B)设 p:王荣努力学习, q:王荣取得好成绩 ( 3)每列火车都比某些汽车快。( C)设 F(x):x是火车, G(y):y是汽车, H(x,y):x比 y 快。 A: p q p q p q B: p q q p p q C: x y (F(x) G(y) (H(x,y) x (F(x) y(G(y) H(x,y) x (F(x) y(G(y) H(x,y) 3. 设 S=1,2,3,下图给出了 S 上的 5 个关系 ,则它们只具有
17、以下性质 :R1 是( A) ,R2是 (B),R3是 (C)。 A B C:自反的,对称的,传递的 反自反的,对称的 自反的 反对称的 对称的 自反的,对称的,反对称的,传递的 4. 设 S=, 1, 1, 2,则有 ( 1)( A) S ( 2) (B) S ( 3) P(S)有( C)个元数。 ( 4)( D)既是 S的元素,又是 S的子集 离散试卷及答案 第 8 页 共 21 页 A: 1,2 1 B: 1,2 1 C: 3 6 7 8 D: 1 二、证明(本大题共 2 小题,第 1 小题 10分,第 2 小题 10分,总计 20分) 1、用等值演算算法证明等值式 (p q) (p q
18、)p 2、构造下面命题 推理的证明 如果今天是星期三,那么我有一次英语或数学测验;如果数学老师有事,那么没有数学测验;今天是星期三且数学老师有事,所以我有一次英语测验。 三、计算(本大题共 4 小题,第 1 小题 5 分,第 2 小题 10 分,第 3 小题 15分, 总计 30分) 1、设 212, ,个体域为为,整除为 xxQyxyxP ,求公式: xQyxPyx , 的真值。 2、设集合 AA ,4,3,2,1 上的关系 4,3,3,2,1,2,2,1,1,1R ,求出它的自反闭包,对称闭包和传递闭包。 3、 设 ,24,12,8,4,2,1A 上的整除关系 212121 , aaAaa
19、aaR 整除 , R 是否为 A 上的偏序关系?若是,则: 1、画出 R 的哈斯图; ( 10 分) 2、求它的极小元,最大元,极大元,最大元。 ( 5 分) 四、 用推导法求公式 pqp 的主析取范式和主合取范式。 (本大题 10 分) 答案: 一、 选择题 1. A: B: C: D: E: 2.A: B: C: 3.A: B: C: 4.A: B: C: D: 离散试卷及答案 第 9 页 共 21 页 二、证明题 1. 证明 左边 ( (p q) p) ( (p q) q)) (分配律) p( (p q) q)) (吸收律 ) p( (p q) (q q)) (分配律) p( (p q)
20、 1) (排 中律) p (p q) (同一律) p (吸收律) 2.解: p:今天是星期三。 q:我有一次英语测验。 r:我有一次数学测验。 s:数学老师有事。 前提: p(q r) , sr , p s 结论: q 证明: p s 前提引入 p 化简 p(q r) 前提引入 q r 假言推理 s 化简 sr 前提引入 r 假言推理 q 析取三段论 推理正确。 三、计算 离散试卷及答案 第 10 页 共 21 页 1. ,1 , 1 2 , 21 , 1 1 2 , 1 2 1 , 2 1 2 , 2 2x y P x y Q xy P y Q P y QP Q P Q P Q P Q 1
21、, 1 1 , 1 , 2 1 , 2 , 1 0 , 2 , 2 1 , 1 1 , 2 01 1 0 0 1 1 1 01P P P P Q Q 该公式的真值是 1,真命题。 或者 TTTFTTTFTFFTTTTQPQPQPQPxQxPxQxPxxQyxPyx22,221,212,111,12,1,2、 4,4,3,3,2,2,4,3,3,2,1,2,2,1,1,1)( Rr 3,4,2,3,4,3,3,2,1,2,2,1,1,1)( Rs 4,1,4,2,2,2,3,1,4,3,3,2,1,2,2,1,1,1)( Rt 3、( 1) R 是 A 上的偏序关系。 ( 2) 极小元、最小元是 1,极大元、 最大元是 24。 四、 2301p q p p q pp q ppp q qp q p q ,主 合 取 范 式 ,安徽大学 2004-2005 学年第二学期离散数学期末考试试卷( A卷)参考答案 一、单项选择