四川大学离散数学教材书后面的模拟试卷II IV 参考答案

模拟试卷II

四、 1、解：

R1?R2?{?a,a?,?a,b?,?b,b?,?c,c?}R1?R2?{?a,a?,?a,b?,?a,c?,?b,a?,?b,c?,?b,b?,?c,c?}?1R1?{?a,a?,?b,a?,?b,b?,?c,a?,?c,b?,?c,c?}r(R1)?R1 t(R1)?R1s(R1)?{?a,a?,?a,b?,?a,c?,?c,a?,?b,a?,?b,c?,?c,b??b,b?,?c,c?}

2、

解 (1)求G的邻接矩阵为：

?0??0A??0??0??0??0P??0??0?101??011??101?

100?? (2) 可达矩阵为

111??111?111??。

111???0??0?0??0?111??0

??

111??1

∧?111?1???111???1

000??1

??

111??0

＝?111?0???111???0

000?

?

111?

， ?111?

111??

TP?P?(3)因为

所以{v1}，{v2，v3，v4}构成G的强分图。

[键入文字]

[键入文字]

3、

解：此问题的最优设计方案即要求该图的最小生成树， 由破圈法或避圈法得最小生成树为： 其权数为1+1+3+4 = 9 。

4、

解：极大元：e 极小元：b,d 最大元：e 最小元：无 最小上界：e 最大下界：a

五、

1、?x(P(x)∨Q(x))，?x?P(x)??x Q(x)

证明：

(1)?x?P(x) P

(2)?P(c) T(1)，US (3)?x(P(x)∨Q(x)) P

(4)P(c)∨Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?x Q(x) T(5)，EG

cbafedg2、设是一个代数系统，*是R上二元运算，

?a,b?R

[键入文字]

a*b?a?b?a?b，则0是幺元且是含幺半群。

[键入文字]

证明： [幺]

?a?R ，0*a?0?a?0?a?a,a*0?a?0?a?0

即 0*a?a*0?a?0为幺元 [闭] ?a,b?R，由于+，·在R封闭。所以

a*b?a?b?a?b?R 即*在R上封闭。

[结] ?a,b,c?R

(a*b)*c?(a?b?a?b)*c?a?b?a?b?c?(a?b?a?b)?c?a?b?c?a?b?a?c?b?c?a?b?ca*(b*c)?a?b?c?a?b?a?c?b?c?a?b?c所以(a*b)*c?a*(b*c)因此 ， 〈R，*〉是含幺半群。

[键入文字]

[键入文字]

模拟试卷IV

四、

1、

P?(Q?R)?P?(Q?R(P??P))?P?(P?Q?R)?(?P?Q?R)?(P?(Q??Q)?(R??R))?(P?Q?R)?(?P?Q?R)?(P?Q?R)?(P?Q??R)? (P??Q?R)? (P??Q??R)?(?P?Q?R)

2、

r（R）={<1，1>，<1，2>，<2，3>，<2，2>，<3，3>} s（R）={<1，1>，<1，2>，<2，3>，<2，1>，<3，2>} t（R）={<1，1>，<1，2>，<2，3>，<1，3>}

3、设一度结点的个数为L，总的结点数为n，树的边数为m，

由握手定理：6×2+5×3+4×6+L=2m 由树的基本性质：m=n-1 ? 51+L=2(n-1) ① 由题意 15+L=n ② 由①②解得 n=38 4、

[键入文字]

[键入文字]

单位元：e?x 1逆元：x?x x?x x?x x?x ?1?1?1?111243342

生成元：x ，x24

五、

1、证明：（1）R 附加前提

（2）?R∨P P

（3）P T(1)(2)，I （4）P?(Q?S) P

（5）Q?S T(3)(4)，I （6）Q P

（7）S T(5)(6)，I （8）R?S CP

2、证明：1）?x∈I，因为（x-x）/m=0，所以x?x(mod m)，即xRx。

2）?x，y∈I，若xRy，则x?y(mod m)，即（x-y）/m=k∈I，所以（y - x）/m=-k∈I，所以y?x(mod m)，即yRx。

3）?x，y，z∈I，若xRy，yRz，则（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v ∈I，因此xRz。

[键入文字]