东北农业大学(2014版)离散数学网上作业题及答案(5)

<,>?R?

xu= yvxx=，所以<,>?R。即R是自反的。 yy(1)对任意的?A，因为

(2)设任意的?A，?A，若 <,>?R?

xuux=?=?<,>?R。即R是对称的。 yvvy(3)设任意的?A，?A，?A,若 <,>?R∧<,>?R?(

uwxu=)∧(=)

vsyv ?

xw=?<,>?R。 ys即R是传递的。 因此R为A上的等价关系。

五、给出偏序集上偏序关系R的关系图（如下图所示）。

a c b d （1）求偏序集的哈斯图。

e （2）指出A的最大、最小元（如果有的话），极大、极小元。 答：解：（1）偏序集的哈斯图为：

a b c （2）A的最大元素为a，A的最小元素不存在；极大元为a，极小元为d，e。

六、设为群。若在G上定义二元运算о,使得对任何元素x，y?G，有

21

d e

xоy = y?x。

证明也是群 答：证：

（1）由于为群，故xоy=y*x?G。因此，о运算在G 中封闭。又对任意 x,y,z?G ，由于*运算可结合，从而(xоy)оz=(y*x)оz=z*(y*x)=(z*y)*x=xо(z*y)=xо(yоz) 即о运算可结合。因此为一半群。

（2）为群, G对*运算有幺元e 。从而对任意x?G，x*e=e*x=x，进而 xоe=e*x=x ，eоx=x*e=x即e也为G对о运算的幺元。

（3）对任意x?G，由于为群，x关于*运算有逆元x，于是x* x x*x=e，从而xоx= x*x=e xоx=x* x=e 。即x关于о运算也有逆元x。 综上（1），（2），（3），为群。

七、设为群,a为G中给定元素。定义函数f：G→G，使得对每一x?G有f(x)=a?x?a证明：f是到的自同构。 答：证明：

f显然为 G?G的一个函数。

对任意x1,x2?G ，若f(x1)=f(x2) ，则a*x1*a=a*x2*a，

于是x1=x2 。故f为单射。 对任意y?G 取x=a*y*a?G，那么

f(x)=f(a*y*a)=a*(a*y*a)?a=y

故f为满射，从而f为双射。 又对任意x1,x2?G

f(x1*x2)=a*( x1*x2)* a f(x1)*f(x2)=( a*x1*a

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1=

-1

-1

-1

)*(a*x2*a

-1

)= a*( x1*x2)* a

-1

故f(x1*x2)=f(x1)*f(x2)，即f保运算。 因此f为到的自同构映射。

复习题七

一、证明

1、对任意两个集合A和B，证明 ?A?B???A?B??A

答：证明：?A?B???A?B??A?B??A?B??A?B?B?A?E?A

2、构造下面命题推理的证明

如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，

22

????

因此我热衷与玩游戏机。

答：符号化为：P?Q,?R?P,?Q?R 证明：(1)?Q P

(2)P?Q P (3)?P T(1)(2)I

(4)?R?P P

(5) R T(3)(4)I

二 、计算

1、 画一个有一条欧拉回路和一条汉密顿回路的图。

答：

?1，2、设P?x,y?为x整除y，Q?x?为x?2，个体域为2?，求公式：

??x???y??P?x,y??Q?x??的真值。

??x???y??P?x,y??Q?x?????x???P?x,1??Q?x????P?x,2??Q?x??????P?1,1??Q?1????P?1,2??Q?1??????P?2,1??Q?2????P?2,2??Q?2???答：

???T?T???T?T?????F?F???T?F????T?T???T?F??T?T?T3一棵树有n2个结点度数为2 ，n3个结点度数为3，? ，nk个结点度数为k ，问它有几个度数为1的结点。

答：设它有n1个度数为1的结点，则：

1*n1＋2*n2＋3*n3＋? ＋k*nk=2*（n1+n2+n3+?+nk-1） 得：n1=n3＋2*n4＋? ＋(k-2)*nk+2

4设集合A??a,b,c,d?,A上的关系 R?a,b,b,a,b,c,c,d，求出它的自反闭包，对称闭包和传递闭包。

答：r(R)?a,b,b,a,b,c,c,d,a,a,b,b,c,c,d,d

????s(R)??a,b,b,a,b,c,c,d,c,b,d,c?

23

t(R)??a,b,b,a,b,c,c,d,a,c,a,ab,b,b,d,a,d?

R是否为A上的偏序关系？若是，三、设A??3,5,9,15?上的整除关系R?a1,a2a1,a2?A,a1整除a2，

则：

1、画出R的哈斯图；2、求A的极大值和A的极小值。 答：R是A上的偏序关系。 1、R的哈斯图：

??

2、A的极大值为9，15；极小值为3，5。

四、用推导法求公式??P?Q??R?的主析取范式和主合取范式。

??P?Q??R??????P?Q??R????P??Q??R????P?R????Q?R?????P??Q??Q??R????P??P???Q?R??答：

???P?Q?R???P??Q?R????P??Q?R?????P?Q?R???P??Q?R???P??Q??R????P?Q?R????P??Q?R??五、设自然数集N上的关系R定义为：R?n1,n2n1,n2?N,n1/n2?2m,m?I，

证明：R是N上的等价关系。

答：证明：?x?N有x/x?1?20所以x,x?R

因此R是自反的

???x,y?R有x,y?N且x/y?2m,m?I,得y/x?2?m,?m?I,所以y,x?R 因此R是对称的

?x,y,y,z?R有x,y,z?N且x/y?2m1,y/z?2m2,m1,m2?I得x/z?2

m1?m2,m1?m2?I,所以x,z?R

因此R是传递的。综上：R是N上的等价关系。

六、设R和R分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数f:R?R?为

?f(r)?10r，证明f是从(R,?)到(R?,?) 的同构映射。

答：证明：?x,y?R,且x?y,有10x?10y,所以f是入射

?z?R?,?r?R使10r?z,即r?lgz,所以f是满射

因此f是双射。

24

?x,y?R,有f?x?y??10x?y?10x?10y?f?x??f?y?，所以f是从(R,?)到(R?,?) 的同构映射。

七、设I是整数集合，＋是普通加法，试证明?I,??是一个群。?I,??是否循环群？ 答：证明：?x,y?I,有x?y?I，因此，运算是封闭的

?x,y,z?I,有(x?y)?z?x?(y?z)，因此，运算是可结合的 ?x?I,有x?0?0?x?x，因此，0是幺元

综上：?I,＋?是一个群。

因为：?i?I,有i?(1)i，因此，1是生成元，?I,＋?是循环群。

复习题八

一、 求公式(┐p∨┐q)→(p?┐q)的析取范式、合取范式及主析取范式、主合取范式。 答：解：(┐p∨┐q)→(p?┐q)?┐(┐p∨┐q)∨((┐p∨┐q)∧(p∨q))

? (p∧q)∨(┐p∧q)∨(p∧┐q) （主析取范式） ?q∨(p∧┐q) （析取范式） ?p∨q （合取范式、主合取范式）

二、用推理规则证明：

前提 (?x)P(x)→(?x)((P(x)∨Q(x))→R(x))，(?x)P(x)，(?x)Q(x) 结论 (?x)(?y)(R(x)∧R(y)) 答：证明：

(1) (?x)P(x)→(?x)((P(x)∨Q(x))→R(x)) P (2) (?x)P(x) P

(3) (?x)((P(x)∨Q(x))→R(x)) T(1)(2)I (4) P(c) ES(2) (5) (P(c)∨Q(c))→R(c) US(3) (6) P(c)∨Q(c) T(4)I (7) R(c) T(5)(6)I

25