离散数学试卷.doc

1、离散数学试题 A 第 1 页（共 6 页） 新疆大学 2013 2014 学年度第 二 学期期末考试 离散数学试卷 A 第一部分 选择题（共 20 分） 一、单项选择题 （本大题共 10 小题，每题只有一个正确答案，答对一题得 2 分共 20 分） 1、对任意集合 A、 B、和 C，下列论断中正确的是： 【 】 A. 若 A B， B C，则 A C B. 若 A B， B C，则 A C C. 若 A B， B C，则 A C D. 若 A B， B C，则 A C 2、设 A=a,a,下列式子中正确的有： 【 】 A. a (A) B. a (A) C. a (A) D. 以上都不是 3、

2、 P：我将去镇上。 Q：我有时间。命题“我将去镇上，当且仅当我有时间”符号化 为： 【 】 A. P Q B. Q P C. P Q D. Q P 4、命题公式：（ P （ P Q） Q 是 【 】 A矛盾式 B. 可满足式 C. 重言式 D. 不能确定 5、 谓词公式 )()()( xQyyRxPx 中，量词 x 的辖域是： 【 】 A. )()( yyRxPx B. )(xP C. )(),( xQxP D. )()( yyRxP 6、 在如下各图中，哪一个是欧拉图？ 【 】 7、设 |V|1， G= 是强连通图，当且仅当： 【 】 A G 中至少有一条通路 B G 中至少有一条回路 C

3、G 中有通过每个结点至少一次的通路 D G 中有通过每个结点至少一次的回路 8、 设 2,1,1,S ，则 (S) 有多少个元素？ 【 】 A 3； B 6； C 7； D 8 ； 9、 集合 A=1， 2， 3， 4， 5， 6， 7， 8， 9， 10上的关系 R= | x + y = 10，则 R 的性质为： 【 】 A自反的； B对称的； C传递的、对称的； D反自反的、传递的 10、集合 A 上的等价关系 R，其等价类集合 aR | a A称为： 【 】 A A 与 R 的并集，记作 A R B A 与 R 的交集，记作 A R C A 与 R 的商集，记作 A/R D A 与 R

4、的差集，记作 A - R 二、填空题 (本大题共 10 小题，每题 2 分 ,共 20 分 ) 离散数学试题 A 第 2 页（共 6 页） 11、 已知集合 A= , ，则 A 的幂集为 。 12、 已知序偶 =，则 x= ; y= 。 13、 P、 Q为两个命题，当且仅当 时， P Q 的真值为 0 14、（ P Q）（ P Q）可化简为： 。 15、 设 整除，2被,121 ZxxxxM ， 整除，3被,121 ZxxxxN 则 M N= ， M N= 16、 个体域为自然数集， P（ x）： x 为奇数， Q（ x）： x 为偶数，则命题“不存在既是奇数又是偶数的自然数”形式化为： 。

5、17 、 设 R 为非空集合 A 上的等价关系，其等价类记为 x R。 x,y A，若 x,y R，则 x R与 y R 的关系是 _ _，而若 x,y R，则 x R y R=_。 18 Kn为汉米顿图，当且仅当 。 19设 A、 B 为集合， |A|=n， |B|=m，则 A 到 B 的二元关系共有 个， A 上的二元关系共有 个。 20一棵树有两个结点度数为 2，一个结点度数为 3，三个结点度数为 4，它有 个度数为 1 的结点？ 三、 计算题 （ 本大题共 6 小题，其中 21、 22、 23 三题每题 5 分， 24、 25、 26 三题每题7分，共 36 分） 21、 某班有学生

6、50 人，有 26 人在第一次考试中得优，有 21 人在第二次考试中得优，有 14 人在两次考试都得优，那么两次考试中都没得优的学生有多少人？ 22、是否可以分别画出无向简单图，使各点的度与下面给出的序列一致。如可能，画出符合条件的无向图，如不可能，说明原因。 （ 1） 1， 1， 2， 2， 3 （ 2） 1， 1， 2， 2， 2 23、给定个体域 D=3， 5， 7， P（ x）解释为“ x 是素数”，求公 式 )(xxP 的真值。 离散数学试题 A 第 3 页（共 6 页） 24、 设集合 A=1,2,3， A 上关系 R=|x A y A x +3y,。求Dom（ R）， Ran（

7、R）， R S， R， r（ R）及 s（ R） 25. 求公式 q（ p q）的析取范式、合取范式、主析取范式，并根据主析取范式直接确定公式的弄真指派和弄假指派。 26、 对 2， 3， 6， 12集合上的整除关系画出哈斯图，并对子集 2， 3， 6找出最大元素，最小元素，极大元素，极小元 素。 四、证明题 (3 小题，每题 5 分，共 15 分。 )27、 证明： A(B C)=(AB) (AC) 28、 证明逻辑等价式 xy(P(x) Q(y) x P(x) y Q(y)。（方法不限） 五、应用题 （本大题共 1 小题， 9 分） 30、 有七位客人入席， A 只会讲英语； B 会讲汉语

8、； C 会讲英语、意大利语及俄语； D 会讲汉语及日语； E 会讲意大利语及德语； F 会讲法语，日语及俄语； G 会讲德语和法语。问主人能否把七位客人安排在一张圆桌上，使每一位客人与左右邻不用翻译便可交谈。若能安排， 请给出一个方离散数学试题 A 第 4 页（共 6 页） 案。 新疆大学 2013 至 2014 学年第第二学期期末考试 离散数学 试题 A 标 第一部分 选择题（共 20 分） 一、单项选择题（ 每题只有一个正确答案，答对一题得 2 分，共 20 分 ） 1、 C 2、 A 3、 C 4、 B 5、 6、 B 7、 D 8、 D 9、 B 10、 C 第二部分 非选择题（共 8

9、0 分） 二、填空题 (本大题共 10 小题，每题 2 分，共 20 分。 ) 11、 P(A)= ,1,1， 2,1,1， 2 12、 R 13、 P 与 Q的真值相同时 14、 合取（或 ），出现一个 15、 M=3， 6， 9， 12， 15， 18， N=4， 8， 12， 16， NM 12, NM 3， 6， 9， 15， 18 16、 )()( XQxPx ） 17、相等、 18、 n=3,且每一对顶点度之和 =n 19、 16、 2 20、 9 三、 简答题 （ 本大题共 6 小题， 每题 6 分， 共 36 分 。） 21、真值表如下： p q r q r p (q r) p

10、 (p (q r)p 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 离散数学试题 A 第 5 页（共 6 页） 22、 (1) 不符合握手定理，所以不能画出图 （ 2）符合条件的无向图为 ： 23、主析取范式： (P Q R) (P Q R) (P Q R) (P Q R) 或者 主析取范式 =m1 m3 m6 m7 成真赋值为： 001， 011， 110， 111 成假赋值为： 000， 010， 100， 101

11、 24、 dom（ R） =A， Ran(R)=1,2,R S=， R-1=， ， ， r(R)=， ， ， ， ， s（ R） =， ， ， ， 25、不会打这三种球的人数为： X=10 A、 B、 C 为会打篮球、排球、网球的人的集合，则有： |S|=30 |A|=16,|B|=14,|C|=11,|A B|=10,|A C|=8,|B C|=8,|A B C|=5 X=|S|-(|A|+|B|+|C|)+(|A B|+|A C|+|B C|)-|A B C|=10 26、 四、证明题 (2 小题，每题 5 分，共 10 分。 ) 27、 28、 证明 ： x(A(x)B(x) x(A(x

12、) B(x) xA(x) xB(x) xA(x) xB(x) xA(x)xB(x) R=, 根据 R 中元素，可知 R是偏序关系，其哈斯图为： 最大元 ： 45， 最小元 ： 1， 极大元 ： 45，极 小元 ： 1 离散数学试题 A 第 6 页（共 6 页） 五、综合应用题 （本题共 2 小题，每题 7 分，共 14 分） 29、 解 能安排，其方案为： H=（ A， C， B， E， D， G， F， A） 将每个人作为一个项点，如果两个人会讲同一种语言，就在代表他们的二个项点间连一条边，边上标明二人公用的语言，这样就可得一简单无向图 G。所求问题转化为图 G 中有无 Hamilton 回

13、路问题。 而上边指出的回路 H 正好是图 G 的一条Hamilton 回路，因此问题得到解决。 30、 令 p：他是计算机系本科生 q：他是计算机系研究生 r：他学过 DELPHI 语言 s:他学过 C+语言 t:他会编程序 前提： (p q)(r s),(r s)t 结论： pt 证 p P(附加前提 ) p q T附加规则 (p q)(r s) (前提引入 ) r s T假言推理规则 r T花间规则 r s T附加规则 (r s)t (前提引入 ) t T假言推理规则 离散数学试题 A 第 7 页（共 6 页） 新疆大学 2013 2014 学年度第 二 学期期末考试 离散数学试卷 A 一

14、、单项选择题 （本大题共 10 小题，每题只有一个正确答案，答对一题得 2 分共 20 分） 1、设 P=x| (x+1)2 4, Q=x | x2+16 5x ，则下列各式中成立的是： 【 】 A. Q P B. Q P C. P Q D. P Q 2、 2,1,1,S ,下列式子中正确的有： 【 】 A. 1 (S) B. 1 (S) C. 1 (S) D. 以上都不是 3、 P：你努力， Q：你失败。“虽然你努力了，但还是失败了”符号化为： 【 】 A. P Q B. Q P C. P Q D. P Q 4、设论域 E=a, b ，且 P(a,a)=T， P(a,b)=F， P(b,a)

15、=T， P(b,b)=F； 则在下列公式中真值为 T的是： 【 】 A xyP (x, y) B xyP(x, y) C xP(x,x) D xyP(x , y) 5、 谓词公式 )()()( xQyyRxPx 中，变元 x 是： 【 】 A自由出现 B约束出现 C既是约束出现，又是自由出现 D以上都不是 6、 .一个连通的无向图 G，如果它的所有结点的度数都是偶数，那么它具有一条 ： 【 】 A 汉密尔顿回路 B 欧拉回路 C 汉密尔顿通路 D 初级回路 7、设 |V|1， G= 是强连通图，当且仅当： 【 】 A G 中至少有一条通路 B G 中至少有一条回路 C G 中有通过每个结点至少

16、一次的通路 D G 中有通过每个结点至少一次的回路 8、 由 5 个结点构成的根树中，其边数 m 最多为： 【 】 A 2； B 3； C 5； D 4 ； 9、 设 A=1， 2， 3， A 上二元关系 S=， ， ， ，则 S 具有的性质是： 【 】A自反关系 B传递关系 C对称关系 D反自反关系 10、集合 A 上的等价关系 R，决定了 A 的一个划分，该划分就是： 【 】 A A 与 R 的并集 A R B A 与 R 的交集，记作 A R C A 与 R 的商集，记作 A/R D A 与 R 的差集，记作 A - R 二、填空题 (本大题共 10 小题，每题 2 分 ,共 20 分

17、) 11、 已知集合 A=1， 1， 2，则 A 的幂集为 。 12、 设 P 是所有 人的集合，在 P 上定义关系 R、 S 为 R=|a， b P a 是 b 的父亲 ， S=|a， b P a 是 b 的母亲 ，那么关系 |a， b x a 是 b 的祖母 的表达式为 .。 离散数学试题 A 第 8 页（共 6 页） 13、 P、 Q 为两个命题，当且仅当 时， PQ 的真值为 1 14、 n 个命题变元的 _称为 极 小项，其中每个变元与它的否定不能同时出现，但两者必须 _。 15、 设 整除，3被,181 ZxxxxM ， 整除，4被,181 ZxxxxN 则 M= ， N= ， M

18、 N= ， M N= 。 16、 个体域为自然数集， P（ x）： x 为奇数， Q（ x）： x 为素数，则命题“存在既是奇数又是素数的自然数”形式化为： 。 17 、 设 R 为非空集合 A 上的等价关系，其等价类记为 x R。 x,y A，若 x,y R，则 x R与 y R 的关系是 _ _，而若 x,y R，则 x R y R=_。 18 Kn 是 个结点的完全图，则 K5 有 _条边，每个结点的度数为 _。 19设 S=1， 2，则 S 上可以定义 个不同的二元关系，其中有 个是等价关系。 20在一棵树中有 7 片树叶， 3 个 3 度顶点，其余都是 4 度顶点，则该树有 个 4

19、度顶点。 三、 简答题（ 本大题共 6 小题，每题 6 分， 共 36分） 四、 21、 构造命题公式 (p (q r)p 的真值表 。 22、是否可以分别画出无向简单图，使各点的度与下面给出的序列一致。如可能，画出符合条件的无向图，如不可能，说明原因。 （ 1） 1， 1， 2， 2， 3 （ 2） 1， 2， 2， 2， 1 23、 求公式 （ P Q） （ P R） 的主析取范式，并根据主析取范式直接确定公式的成真赋值和成假赋值。 离散数学试题 A 第 9 页（共 6 页） 24、 设集合 A=1,2,3， A 上关系 R=|x A y A x +3y,。求Dom（ R）， Ran（ R

20、）， R。 S， R-1， r（ R）及 s（ R） 25. 某班有学生 30 人，其中 16 人会打篮球， 14 人会打排球， 10 人会打篮球和排球， 8 人会打篮球和网球，还有 5 人会打这三种球，而 11 个会打网球的人都会打两外一种球（指篮球或排球），求不会打这三种球的人数。 26、 设 A 1， 3， 5， 9， 15， 45， R 为 A 上整除关系，试画 的哈斯图，并求 A 中的最大元，最小元，极大元，极小元。 四、 证明题 (2 小题，每题 5 分，共 10 分。 ) 27、 设 A,B,C 是任意四个集合，证明 : A（ B C） =(A B) (A C) 28、证明： x

21、(A(x)B(x) xA(x)xB(x) 五、综合应用题 （本题共 2 小题，每题 7 分，共 14 分） 29、 今有 a， b， c， d， e， f， g 共 7 人，已知下列事实： a 会讲汉语和英语； b 会讲英语和韩语； c会讲英语和意大利语； d会讲法语、俄语和意大利语； e会讲俄语和韩语； f会讲汉语； g会讲法语和汉语。试问这 7 个人应如何排座位（圆桌），才能使每个人和他身边的人交谈 ?。 30、 如果他是计算机系本科生或者是计算机系研究生，那么他一定学过 DELPHI 语言而且学 过 C+语言。只要他学过 DELPHI语言或者 C+语言，那么他就会编程序。因此如果他是计算

22、机系本科生，那么他就会编程序。请用命题逻辑推理方法，构造 该 推理的证明 。 新疆大学 2013 至 2014 学年第一学期期末考试 离散数学试题 A 第 10 页（共 6 页） 离散数学 试题 A 标准 答案及评分标准 第一部分 选择题（共 20 分） 一、单项选择题（ 每题只有一个正确答案，答对一题得 2 分，共 20 分 ） 1、 A 2、 A 3、 C 4、 C 5、 D 6、 B 7、 D 8、 D 9、 B 10、 C 第二部分 非选择题（共 80 分） 二、填空题 (本大题共 10 小题，每题 2 分，共 20 分。 ) 11、 P(A)= , , , , 12、 x=11, y

23、=4 13、 P为真， Q 为假（ p=1， q=0） 14、 P 15、 NM 6,12, NM 2,4,8,10 16、 （ )()( XQxPx ） 17、相等 （ 等价 ） 、 18、 n=3,且每一对顶点度之和 =n 19、 2nm、 2n2 20、 9 三、 简答题 （本大题有 4 个小题 ,每题 5 分，共 20 分。） 21、 |s|-|A B|=50-(26+21-14)=17 人 22、 (1) 不符合握手定理，所以不能画出图 （ 2）符合条件的无向图为： 23、 )(xxP =P（ 3） P（ 5） P（ 7） =1 1 1=1 为真 24、 dom（ R） =A， R S=， R=， ， ， r(R)=， ， ， ， ， s（ R） =， ， ， ， 25、 析取范式： p q，合取范式： q（ p q）； 主析取范式： p q 弄真指派：（ 1,1） ，弄假指派： （ 0,0），（ 0,1），（ 1,0） 26、 哈斯图为： 2 3 6 12 最大元： 6 极大元： 6 最小元：没有 极小元： 2， 3