中科院计算机技术研究所1999年硕士研究生入学考试试题 离散数学参考答案 主合取范式:( not xI or not x2orx3) and(xl or not x2orx3)and( xI or x2orx3) 主析取范式:( xI and not x2 and not x3)or( xI and x2andx3)or( xI and not x2and 3)or(not xI and x2 and x3 )or(not xl and not x2 and x3) 二(1)1 (2) (3 321 三不是取一特定解释域I如下[P(xy)I="xly(x)∥前提1 (2)anyx( monkey(x)->notl(x)/前提2 (3)bird(a)>fy(a)∥(1)脱帽 4) monkey(a)> not fly(a)∥(2)脱帽 (5) not fly(a)-> not bird(a)∥逆否律(3) (6) monkey(a)-> not bird(a)∥传递律(4)(5) (7)anyx( monkey(x)-> not bird(x)∥6)戴帽 五解 (1)一个x到y的关系对应于x*y的一个子集因此,不同的x到y的关系数=(x*y)=2^(mn) (2)不同的由x到y的映射个数={f6x->yH={(x1),x2),,xm)lfxi)iny,1=n则单射个数0 若 m!种不同的双射,共有单射Cn(m)*m!种 六证明:由于G为奇数阶交换群,由拉格朗日定理,其中不可能有2阶元因此 any a in G(a!=e),al=a^(-1),即a与a^(-1)是两个不同元素(al=e),因此G的所有元素之积 =e*al*al^(-1) am al in g-{e},ainG-{al,a^(-1),e} am in C-{e,alal^(-1)a2,a2^(-1)-,a(m-1)a(m-1)^(-1) 七(1)1.自反性 any a in G有:a=ea’e(e为单位元),而Hk为G的子群,从而enH,eink so: aRa
中科院计算机技术研究所 1999 年硕士研究生入学考试试题 离散数学 参考答案 一.主合取范式: (not x1 or not x2 or x3)and(x1 or not x2 or x3) and (x1 or x2 or x3) 主析取范式: (x1 and not x2 and not x3)or(x1 and x2 and x3)or(x1 and not x2 and x3) or (not x1 and x2 and x3)or (not x1 and not x2 and x3) 二.(1) 1 (2) 3 (3) 2 (4) 1 三.不是.取一特定解释域 I 如下.[P(x,y)] I ="xfly((x)) //前提 1 (2) any x(monkey(x)->not fly(x)) //前提 2 (3) bird(a)->fly(a) //(1)脱帽 (4) monkey(a)->not fly(a) //(2)脱帽 (5) not fly(a)->not bird(a) //逆否律(3) (6) monkey(a)->not bird(a) //传递律(4)(5) (7) any x(monkey(x)->not bird(x)) //(6)戴帽 五.解: (1) 一个 x 到 y 的关系对应于 x*y 的一个子集.因此,不同的 x 到 y 的关系数=|φ(x*y)|=2^(mn) (2)不同的由 x 到 y 的映射个数=|{f|f: x->y}|=|{(f(x1),f(x2),...,f(xm) )|,f(xi) in y, 1=n,则单射个数 0 若 m m!种不同的双射,共有单射 Cn(m)*m!种. 六.证明:由于 G 为奇数阶交换群,由拉格朗日定理,其中不可能有 2 阶元,因此 any a in G(a!=e),a!=a^(-1),即 a 与 a^(-1)是两个不同元素(a!=e),因此 G 的所有元素之积 =e*a1*a1^(-1)*a2*a2^(-1)*...*am*am^(-1)=e a1 in G-{e},a2 in G-{a1,a^(-1),e},...,am in G-{e,a1,a1^(-1),a2,a2^(-1),...,a(m-1),a(m-1)^(-1) |G|=2m+1 七.(1)1. 自反性:any a in G 有:a=e*a*e.(e 为单位元) ,而 H,k 为 G 的子群,从而 e in H ,e in k so: aRa
2.对称性若aRb,=>存在hinH,kinK使b=h*a+k=>a=h^(-1)+k^(-1),由于HK 为G的子群=h^(-1)inH,k(-1)inK,所以bRa 3传递性若 arb bRc→>存在hl,h2nH,kl,k2inK,使b=h1a*k1,c=h2*b*k2,由于 HK为G的子群得h2+ hI in hkI*k2inK,使c=(h2+hl)*a*(k1*k2),所以aRc, 因此R是等价关系 (2)设是的子群的那个的等价关系为 [a]R={ x in g and aRx}={ x]x in G且存在 h in h k in K,使x=h°a+k}={h°a+ k h in H, k ink} 由于该等价类为的子群,故对任意的hh2nH有h*a*k1)*(h2*a+k2)^(-1)inaR 取kl=k2则得anyR1,R2inH有h*a^2+h2^(-1)in[a]R 从而可以从中推出hl+a^(2n)+h2^(-1)inaR 由于G为有限群,必存在某个r使a^(2r)=e此时,有 any hl, h2 in hhI+h2(-1)in[aR 即H为aR的子群 同理,为K的子群,所以maR,叫|a]R而m与n互素=>mnl]R即Gi|aR 又aR为G的子群因此|aR|(G,从而Gi=aR,从而[aR=G,即 any g in G 有aRg,而R为等价关系 any gl,g2inG,由对称性aRgl=>glRa 由传递性Rgl,aRg2=glRa,aRg2=>g1Rg2 So R=GG 八在每个区域放一个结点,当两区域相临时就在响应的两个结点间连一条线,如此构造了 个平面图且是完全图kB而最大的平面完全图为k4所以,B最大为四 九必要性设G是强连通的此时若从s到vs没有有向边则s中的任一顶u到v-s中的任一 ⅴ均没有有向道路,从而与G是强连通的矛盾所以,从s到v-s至少有一条有向边 充分性:设G是一边连通的anyu,vinV(G) 则{u}到V(G-{u}至少有一条有向边,设为uul而{uul}到V(G)-{u,ul}至少有一条有向边 u2或ulu2.无论那种情况都有从u到u2的有向道路因G中结点数有限,通过如上递归地 求解,一定有u到v的有向道路所以G是强连通的 十设e是vl与v2间的最短边,G的最小生成树为T若e不在T中,则T+e有唯一的圈c,因 T是G的最小生成树所以,c上除e之外一定有另一条v1与v2间的边e1,而o(e)>o(e) T+eel是连通图且与T的边数相同,所以,T+e-el也是G的生成树,而o(T+e-el)= D)+o(e)-o(el)<o(D)所以T不是最小生成树矛盾
2. 对称性:若 aRb,=>存在 h in H ,k in K 使 b=h*a*k=>a=h^(-1)*k^(-1),由于 H,K 为 G 的子群=>h^(-1) in H ,k^(-1) in K,所以 bRa. 3.传递性:若 aRb,bRc=>存在 h1,h2 in H ,k1,k2 in K ,使 b=h1*a*k1,c=h2*b*k2,由于 H,K 为 G 的子群,得 h2*h1 in H,k1* k2 in K,使 c=(h2*h1)*a*(k1*k2),所以 aRc, 因此 R 是等价关系. (2)设是 的子群的那个 的等价关系为 [a]R={x|x in G and aRx}={x|x in G 且存在 h in H,k in K ,使 x=h*a*k}={h*a*k| h in H,k inK} 由于该等价类为 的子群,故对任意的 h1,h2 in H 有(h1*a*k1)*(h2*a*k2)^(-1) in [a]R 取 k1=k 2 则得 any R1,R2 in H 有 h1*a^2*h2^(-1) in [a]R 从而可以从中推出 h1*a^(2r)*h2^(-1) in [a]R 由于 G 为有限群,必存在某个 r 使 a^(2r)=e 此时 ,有 any h1,h2 in H,h1*h2^(-1) in [a]R 即 H 为[a]R 的子群. 同理, 为 K 的子群,所以 m| |[a]R| , n| |[a]R|而 m 与 n 互素=>mn| |[[a]R|即|G| | |[a]R| 又[a]R 为 G 的子群,因此|[a]R| | |G|,从而|G|=|[a]R| , 从而[a]R=G,即 any g in G 有 aRg,而 R 为等价关系. any g1,g2 in G, 由对称性 aRg1=>g1Ra 由传递性,aRg1,aRg2=>g1Ra,aRg2 =>g1Rg2 So:R=G*G 八.在每个区域放一个结点,当两区域相临时就在响应的两个结点间连一条线,如此构造了 一个平面图且是完全图 kβ.而最大的平面完全图为 k4,所以,β 最大为四. 九.必要性:设 G 是强连通的,此时若从 s 到 v-s 没有有向边,则 s 中的任一顶 u 到 v-s 中的任一 顶 v 均没有有向道路,从而与 G 是强连通的矛盾.所以,从 s 到 v-s 至少有一条有向边. 充分性:设 G 是一边连通的,any u,v in V(G) 则{u}到 V(G)-{u}至少有一条有向边,设为 uu1.而{u,u1} 到 V(G)-{u ,u1}至少有一条有向边 uu2 或 u1u2.无论那种情况都有从 u 到 u2 的有向道路.因 G 中结点数有限,通过如上递归地 求解,一定有 u 到 v 的有向道路.所以 G 是强连通的. 十.设 e 是 v1 与 v2 间的最短边,G 的最小生成树为 T.若 e 不在 T 中,则 T+e 有唯一的圈 c,因 T 是 G 的最小生成树,所以,c 上除 e 之外一定有另一条 v1 与 v2 间的边 e1,而 ω(e1)>ω(e). T+e-e1 是连通图且与 T 的边数相同,所以,T+e-e1 也是 G 的生成树,而 ω(T+e-e1)= ω(T)+ω(e)-ω(e1)<ω(T).所以 T 不是最小生成树.矛盾