东北大学考试试卷(A卷)2003-2004学年第2学期离散数学试卷答案

总分一二三四五六七总分一二三四五六七八2003—2004学年第2学期课程名称：离散数学┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄一．将下面命题符号化(8分) 三．(8分)写出命题公式P((RQ)∧(RQ))的主析取范式。如果天气好，我将去游乐场，否则我将呆在家中。 解：P((RQ)∧(RQ))(PQ)(PR) P((RQ)∧(RQ))(PRQ)∧(PRQ)只有计算机专业的学生和非大一学生才可以访问校园网。 即命题公式的主合取范式中的大项为M6和M2R(PQ) 所以其主析取范式中的小项有m0,m3,m4,m5,m6,m7即主析取范式为：3．并非所有学习好的大学生都想成为科学家。 (P∧R∧Q)(P∧R∧Q)(P∧R∧Q)(P∧R∧Q)(P∧R∧Q)(P∧R∧Q)x((A(x)B(x))C(x))4．尽管有人聪明，但未必一切人都聪明。

四．(10分)R1R2R1∪R2、R1∩R2、R1-R2、、r((A×A)-R1)中哪些是A上的等价关系？如果不是说明理由，或举反例。如果是请给予证明。、1 2 1 x(A(x)B(x))x((A(x)B(x)) 答：(1)R1∪R2不是等价关系。设A＝{1,2,3}1为R12为R2的关系3R∪R的关系图，显然R∪R不是A（21 2 1 二．(10分)填空(每空1分)1.（3）ABEX={P,Q,R,S,T,U,V,W,Y,Z},素都表示命题，如下所示：

1(2)R∩R21

是A上的等价关系。、 P:A－B=AQ:AB=BR:ABS:ABT:BAU:BAV:AB=ΦW:AB=BY:A、 P:A－B=AQ:AB=BR:ABS:ABT:BAU:BAV:AB=ΦW:AB=BY:ABZ:BAR R 又令R是X上的命题等价关系,则商集X/R=({{P,S,V,Z},{R,U,W},{Q,T,Y}}) ∩，所以R R 2 1 2

是自反的；(b)设<x,y>∈R∩R，则有<x,y>∈R

和<x,y>∈R，由于R和R

是对称的，1 2 1 1 1 2 2 1 所以有<y,x>∈R1和<y,x>∈R2即<y,x>∈R∩R，可得R∩R2是对称的；(c)设<x,y>∈R∩R，且<y,z>1 2 1 1 1 2 2 1 2.(每空1分)令R和S都是人类上的关系，且 ∩R，则

和R是传递的可得<x,z>∈R，<x,z>∈R={<x,y>|xyS={<x,y>|xy的母亲}则

2 1 1

2 1 2 11 2 1 2 1 R2<x,z>∈R∩R，所以R∩R∩R是A1 2 1 2 1 SR表示(祖母和孙子 )关系；RSC表示(夫妻 )关系。 (3)R1-R2不是等价关系设A＝{1,2,3}反例如下图所示，图4为R1的关系图，图5为R2的关系图，图6为R1-R2的关系图，显然R1-R2不是A上的等价关系。3.(1<G,*>是群,其中G={a,b,c}ab2=(c),b*c=(a4.(1)A,BP(A)A|A|=3,|P(B)|=64,|P(A∪B)|=256,|B|=(6|A-B|=(2|AB|=(7)。

(4)r((A×A)-R

1)A＝{1,2,3}7为

8为R2的学班院级…………○……学姓号名………密…学班院级…………○……学姓号名………密……………○……………封……………○…………线………………Page1of3PagePagePAGE3of3得分分得分分)(按照教材格式写出推理过程)x(x)(B(x)C(x))), x(x)(C(x)D(x))),x(x)D(x)) x(x)B(x))证明：(1) x(A(x)∧D(x))P得分(2)A(a)∧D(a))ES(1)(3)A(a)T(2)I(4)D(a))T(2)I（2分）(5)x(A(x)→(B(x)→C(x)))P(6)A(a)→(B(a)→C(a))US(5)(7)B(a)→C(a))T(3)(6)I（2分）(8)x(A(x)→(C(x)∨D(x)))P(9)A(a)→(C(a)∨D(a)))US(8)（2分）(10)C(a)∨D(a)T(3)(9)I（2分）(11)C(a)T(4)(10)I(12)B(a)T(7)(11)I（2分）(13)A(a)∧B(a))(14)x(A(x)∧B(x))T(3)(12)EG(13)（2分）得分六．(15分)给定集合Ｇ＝{x|x是有理数且x≠1}，在Ｇ上定义二元运算*如下对任何a，b∈Ｇ a*b=a+b-ab求证<Ｇ，*>是个交换群。证明:1)封闭性.任取a,b∈I,a*b=a+b-2∈I,a*b∈I,所以*I上封闭.(32).a,b,c∈I,a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=(a+b-2)+c-2=(a*b)*c所以*可结合.(3分)3).证*可交换.任取a,b∈Ia*b=a+b-2=b+a-2=b*a所以*(34).a∈I,a*2=a+2-2=a2*a=2+a-2=a(35).证可逆性.任取a∈I,4-a∈I,使得a*(4-a)=a+4-a-2=2(4-a)*a=4-a+a-2=a∴a-1=4-a(3所以<I,*>是交换群得分七．.(15得分七．.(15分)设<G,>是群,a∈G,定义函数fa:GG为:任何x∈G 有1.求证fa:GG是入射的.2.F={fa:GG|a∈G},FGa定义的函数构成的集合，令“”是函数的左复合运算,求证<F,>是个群.x1≠x2，fa(x1)＝fa(x2)a*x1=a*x2由群的消去性可知x1=x2，与x1≠x2相矛盾，fa(x1)≠fa(x2)，即fa:GG（4分）2．证明：(1)fa1，fa2∈F(a1，a2∈G)由已知可知fa1=a1*x，fa2=a2*xfa1fa2(x)=a1*(a2*x)=a1*a2*x由于a1，a2∈G，，由群G的封闭性可知a1*a2∈Gfa1fa2(x)∈F（2分）fa1，fa2，fa3∈F，由运算“*”的可结合性可得fa1(fa2fa3a1*(a2*(a3*x)=(a1*a2)*(a3*x)=fa1fa2)fa3所以运算“”是可结合的。（2分）fe(x)=e*x(eG中的幺元)fefa(x)=e*(a*x)=fafe(x)=a*(e*x)=a*x＝fa(x所以fe是代数系统<F,>的幺元。（3分） fa-1a的逆元。fafa-1(x)=a*(a-1*x)=(a*a-1)*x=x=a-1*(a*x)=fa-1fa(x)=fa-1为faF（3分）综上所述，运算“所以代数系统<F,>（1分）得分八．简答题(12分)e条边，tet（3分m:(m-1)i=t-1得分支结点数i=t-1又根据树中e=v-1v是结点数.所以e=(i+t)-1=t-1+t-1=2t-22．请画出有5个结点的无向完全图K5的所有不同构的生成树。（3分）K5T4，T3可生成树，如下： （11114）(11