离散数学大作业答案

2014-2015学年第一学期期末《离散数学》大作业

一、简要回答下列问题：（每小题3分，共30分）

1．请给出集合的结合率。

答：结合律(AUB)UC=AU(BUC)x∈(AUB)UC，即 x∈AUB 或 x∈C即 x∈A 或 x∈B 或 x∈C即 x∈A 或 x∈B∪C即 x∈AU(BUC)说明 (AUB)UC包含于AU(BUC)同理可证AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC)

2．请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。

3．设A={1，2}，问A上共有多少个不同的对称关系？ 答：不同的对称关系有：8种 R = Φ R = {<1,1>} R = {<2,2>}

R = {<1,1>,<2,2>} R = {<1,2>,<2,1>}

R = {<1,1>,<1,2>,<2,1>} R = {<1,2>,<2,1>,<2,2>}

R = {<1,1>,<1,2>,<2,1>,<2,2>}

4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={2,3}，求M的上界，下界。

5．关于P，Q，R请给出使极小项m0，m4为真的解释。 答：m0= ┐p∧┐q∧┐r m4 = p∧┐q∧┐r

6．什么是图中的简单路？请举一例。

答：图的通路中，所有边e1,e2,…,ek互不相同，称为简单通路。

7．什么是交换群，请举一例。

答：如果群〈G，*〉中的运算*是可以交换的，则称该群为可交换群，或称阿贝尔群。 如〈I，+〉是交换群。

8．什么是群中右模H合同关系？

答：设G是群，H是G的子群，a,b∈G，若有h∈H， 使得a =bh，则称a合同于b（右模H），记为a≡b（右mod H）。

9．什么是有壹环？请举一例。

答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，则称e为A中关于运算☆的幺元。

显然，对任一x ∈ A，有 e ☆ x = x ☆ e = x 环

设是具有两个二元运算△ 和*的代数系统，如果适合: ① 是交换群(阿贝尔群)； ② 是半群；

③运算☆对运算△是可分配的，即：

2014-2015学年第一学期期末《离散数学》大作业

a ☆ (b △ c) = (a ☆ b) △ (a ☆ c) (b △ c) ☆ a = (b ☆ a) △ (c ☆ a) 则称是环。

含幺环：

如果是独异点(或含幺半群)，则称是含幺环。

设 V=是半群，如果V中有幺元存在，则称V为含幺半群，也称为独异点。

设V=是代数系统，☆是非空集合A上的二元运算，如果☆是可结合的，即对任意的x,y,z∈A,有

(x☆y)☆z = x☆(y☆z) 则称V为半群。

10．什么是极大理想？请举一例。 答：一个环R的一个不等于的理想I叫做一个最大理想，假如除了R同I自己外没有包含A的理想。

二、（12分）R，S是集合A上的两个关系。试证明下列等式：

（1）(R?S)-1= S-1?R-1

-1-1-1-1

证明：先证(R?S)? S?R，对任意(x，y) ?(R?S)，则(y，x) ?(R?S)，则存在a?A，满足

-1-1-1-1-1-1

(y，a) ?R且(a，x) ?S，那么(x，a) ?S且(a，y) ?R，所以(x，y) ? S?R，因此(R?S)? S-1-1-1-1-1-1-1

?R；再证S?R ?(R?S)，对任意(x，y) ? S?R，则存在a?A，满足(x，a) ?S且(a，y) -1-1-1-1?R，所以(y，a) ?R且(a，x) ?S，所以(y，x) ?(R?S)，所以(x，y) ?(R?S)，因此S?R ?(R-1

?S)。

（2）(R-1)-1= R

-1-1-1-1-1-1-1

证明：先证(R)? R，对任意(x，y) ?(R)，则(y，x) ? R，则(x，y) ? R，所以(R)? R；

-1-1-1-1-1-1-1-1-1

再证R ?(R)，对任意(x，y) ? R，则(y，x) ? R，则(x，y) ?(R)，所以R ?(R)。故(R)= R得证。

三、（20分）指出下列公式哪些是恒真的哪些是恒假的：

解：(1)P?（P? Q）?Q是恒真的?Q）， (2)（P? Q）?（?P是恒真的，

(3)（P? Q）? （Q?R）?（P? R ）是恒真的， (4)（P? Q）?（P? Q??P?? Q）是可满足的。

四、（18分）指出下列表达式中的自由变量和约束变量，并指明量词的作用域：

（1）(?xP(x)??xQ(x))?(?xP(x)?Q(y)) （2）?x?y((P(x)?Q(y))??zR(z)) （3）A(z)?(??x?yB(x，y，a)) （4）?x A(x)??yB(x，y)

（5）(?xF(x)??yG(x，y，z))??zH(x，y，z)

2014-2015学年第一学期期末《离散数学》大作业

答：（1）(?xP(x)∧?xQ(x))∨(?xP(x)→Q(y))3个x都是约束变量，y为自由变量第一个?x的作用域是第一个P(x)第2个?x的作用域是第2个P(x)?x的作用域是Q(x) （2）x,y,z都是约束变量

（3）x,y是约束变量，z为自由变量

（4）A(x)中的x是约束变量，B(x,y)中的x是自由变量，y是约束变量

（5）F(x)中的x是约束变量 G(x,y,z)中的y是约束变量，x,z是自由变量 H(x,y,z)中的z是约束变量，x,y是自由变量。

五、（20分）一公司在六个城市c1，c2，…，c6中的每一个都有分公司。从ci到cj的班机

旅费由下列矩阵中的第i行第j列元素给出(?表示没有直接班机)： 0 50 ? 40 25 10 50 0 15 20 ? 25 ? 15 0 10 20 ? 40 20 10 0 10 25

25 ? 20 10 0 55 10 25 ? 25 55 0

公司所关心的是计算两城市间的最便宜路线的表格。请准备一张这样的表格。

C C1 0 C2 35 C1?C6 ?C2 C3 45 C1?C5 ?C3或 C1?C6 ?C4?C3或C1?C5 ?C4?C3 C2 35 C2?C6 ?C1 C3 45 C3?C4 ?C6 ?C1或 C3?C5 ?C1或C3?C4 ?C5?C1 C4 35 C4?C5 ?C1或 C4?C6 ?C1 25 C4?C2 10 C4?C3 0 10 C4?C5 25 C4?C6 15 C3?C2 0 15 C2? C3 0 20 C2?C4 10 C3?C4 30 C2?C4 ?C5 20 C3?C4 ?C5或C3?C5 25 C2?C6 35 C3?C4 ?C6 C4 35 C1?C5 ?C4或 C1?C6 ?C4 C5 25 C1?C5 C6 10 C1?C6 2014-2015学年第一学期期末《离散数学》大作业

C5 25 C5 ?C1 30 C5?C4 ?C2 20 C5?C4 ?C3或C5?C3 35 C6?C4 ?C3 10 C5 ?C4 0 35 C5?C4 ?C6或 C6 10 C6?C1 25 C6?C2 25 C6?C4 35 C6?C4 ?C5或 C6?C1 ?C5 C5?C1 ?C6 0

本文来源：https://www.bwwdw.com/article/79zt.html