《离散数学 Discrete Mathematics》课程教学资源（习题集）北京大学1997年研究生入学考试

北京大学1997年研究生入学考试离散数学试题(共50分) 在一阶逻辑自然推理系统F中,构造下面推理的证明。个体域是人的集合。 每位科学家都是勤奋的,每个勤奋又身体健康的人在事业中都会获得成功。存在着身体 健康的科学家。所以,存在着事业获得成功的人或事业半途而废的人。” 2(8分) 在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断 甲说:王教授不是苏州人,是上海人。 乙说:王教授不是上海人,是苏州人 丙说:王教授既不是上海人,也不是杭州人。 王教授听后,笑曰:你们3人中有一人全说对了,有一人全说错了,还有一人对错各半 试用逻辑演算法判断王教授是哪里人? 3(3分) 设根树T有17条边,12片树叶,4个4度内点,1个3度内点。求T的树根的度数。 4(7分) 设无向图G是m(n≥3)个顶点的极大平面图,证明G的对偶图G*的边连通度IG)≥2,并且 G*是3-正则图(△(G)=d(G)=k的无向图G称作k-正则图) 设R={ x, lInUX+3y=12},求R2。 设A为集合,B=P(A){E}-{A},且B≠E 求偏序集的极大元,极小元,最大元和最小元。 7(4分)

北京大学 1997 年研究生入学考试 离散数学试题（共 50 分） 1 (7 分) 在一阶逻辑自然推理系统 F 中，构造下面推理的证明。个体域是人的集合。 “每位科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体 健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。” 2 (8 分) 在某次研讨会的休息时间，3 名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后，笑曰：你们 3 人中有一人全说对了，有一人全说错了，还有一人对错各半。 试用逻辑演算法判断王教授是哪里人？ 3 (3 分) 设根树 T 有 17 条边，12 片树叶，4 个 4 度内点，1 个 3 度内点。求 T 的树根的度数。 4 (7 分) 设无向图 G 是 n(n≥3)个顶点的极大平面图，证明 G 的对偶图 G*的边连通度 l(G)≥2，并且 G*是 3-正则图(Δ(G)=d(G)=k 的无向图 G 称作 k-正则图)。 5 (4 分) 设 R={| x,yÎnÙx+3y=12}，求 R2。 6 (6 分) 设 A 为集合，B=P(A)-{Æ}-{A}，且 B≠Æ。 求偏序集的极大元，极小元，最大元和最小元。 7 (4 分)

设A={1,2,3},fAA,且f(1)=f(2)=1,f3)=2,定义G:A→P(A),G(x)=f1(x)。说明G有 什么性质(单射、满射和双射),计算值域ranG 设I是格L的非空子集,如果 (1)"a,b,有aUb, (2)"al,"xlL,有x≤ axiL 则称I是格L的理想 证明:格L的理想是一个子格 9(7分) 设G为n阶群,aiG。令 H=(xax-llxIG), N(a(x/xIGUax=xa) ①H=[GN(a) ②设C={ x/xIGU"yIG(x=yx)}是群G的中心,且CF=m,则H|nm

设 A={1,2,3}，fÎAA，且 f(1)=f(2)=1，f(3)=2，定义 G：A→P(A)，G(x)=f-1(x)。说明 G 有 什么性质(单射、满射和双射)，计算值域 ranG。 8 (4 分) 设 I 是格 L 的非空子集，如果 (1) "a,bÎI，有 aÚbÎI， (2) "aÎI，"xÎL，有 x≤aÞxÎI。 则称 I 是格 L 的理想。 证明：格 L 的理想是一个子格。 9 (7 分) 设 G 为 n 阶群，aÎG。令 H={xax-1|xÎG}，N(a)={x|xÎGÙax=xa}。 证明： ① |H|=[G:N(a)]； ② 设 C={x|xÎGÙ"yÎG(xy=yx)}是群 G 的中心，且|C|=m，则|H|∣n/m