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卷）参考答案 一、单项选择
