离散数学大作业

1、一、简要回答下列问题：（每小题3分，共30分）1请给出集合的结合率。答：结合律(AUB)UC=AU(BUC)x(AUB)UC，即 xAUB 或 xC即 xA 或 xB 或 xC即 xA 或 xBC即 xAU(BUC)说明 (AUB)UC包含于AU(BUC)同理可证AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC)2请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。3设A=1，2，问A上共有多少个不同的对称关系？答：不同的对称关系有：8种R = R = R = R = ,R = ,R = ,R = ,R = ,4设A=1，2，3，4，5，6，R是A上的整除关系

2、，M=2,3，求M的上界，下界。R = ,M=2,3 其上界为6，下界为15关于P，Q，R请给出使极小项m0，m4为真的解释。答：m0= pqr m4 = pqr6什么是图中的简单路？请举一例。答：图的通路中，所有边e1,e2,ek互不相同，称为简单通路。7什么是交换群，请举一例。答：如果群G，*中的运算*是可以交换的，则称该群为可交换群，或称阿贝尔群。如I，+是交换群。8什么是群中右模H合同关系？答：设G是群，H是G的子群，a,bG，若有hH， 使得a =bh，则称a合同于b（右模H），记为ab（右mod H）9什么是有壹环？请举一例。答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，

3、则称e为A中关于运算的幺元。 显然，对任一x A，有 e x = x e = x环设是具有两个二元运算 和*的代数系统，如果适合: 是交换群(阿贝尔群)； 是半群； 运算对运算是可分配的，即： a (b c) = (a b) (a c) (b c) a = (b a) (c a) 则称是环。含幺环：如果是独异点(或含幺半群)，则称是含幺环。设 V=是半群，如果V中有幺元存在，则称V为含幺半群，也称为独异点。设V=是代数系统，是非空集合A上的二元运算，如果是可结合的，即对任意的x,y,zA,有 (xy)z = x(yz)则称V为半群。10什么是极大理想？请举一例。答：一个环R的一个不等于的理想I

4、叫做一个最大理想，假如除了R同I自己外没有包含A的理想。二、（12分）R，S是集合A上的两个关系。试证明下列等式：（1）(RS)-1= S-1R-1证明：先证(RS)-1 S-1R-1，对任意(x，y) (RS)-1，则(y，x) (RS)，则存在aA，满足(y，a) R且(a，x) S，那么(x，a) S-1且(a，y) R-1，所以(x，y) S-1R-1，因此(RS)-1 S-1R-1；再证S-1R-1 (RS)-1，对任意(x，y) S-1R-1，则存在aA，满足(x，a) S-1且(a，y) R-1，所以(y，a) R且(a，x) S，所以(y，x) (RS)，所以(x，y) (RS

5、)-1，因此S-1R-1 (RS)-1。（2）(R-1)-1= R证明：先证(R-1)-1 R，对任意(x，y) (R-1)-1，则(y，x) R-1，则(x，y) R，所以(R-1)-1 R；再证R (R-1)-1，对任意(x，y) R，则(y，x) R-1，则(x，y) (R-1)-1，所以R (R-1)-1。故(R-1)-1= R得证。三、（20分）指出下列公式哪些是恒真的哪些是恒假的：(1)P（P Q）Q(2)（P Q）（PQ）(3)（P Q） （QR）（P R ）(4)（P Q）（P QP Q）解：(1)P（P Q）Q是恒真的Q），(2)（P Q）（P是恒真的，(3)（P Q） （Q

6、R）（P R ）是恒真的，(4)（P Q）（P QP Q）是可满足的。四、（18分）指出下列表达式中的自由变量和约束变量，并指明量词的作用域：（1）(xP(x)$xQ(x)(xP(x)Q(y)（2）$xy(P(x)Q(y)zR(z)（3）A(z)(xyB(x，y，a)（4）x A(x)yB(x，y)（5）($xF(x)yG(x，y，z)$zH(x，y，z)答：（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(

7、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公司所关心的是计算两城市间的最便宜路线的表格。请准备一张这样的表格。C1C2C3C4C5C6C035C1C6 C245C1C5 C3或C1C6 C4C3或C1C5 C4C335C1C5 C4或C1C6 C425C1C5 10C1C6 C235C2C6 C1015C2 C320C2C4 30C2C4 C525C2C6C345C3C4 C6 C1或C3C5 C1或C3C4 C5C115C3C2 010C3C4 20C3C4 C5或C3C535C3C4 C6C435C4C5 C1或C4C6 C125C4C2 10C4C3 010C4C525C4C6 C525C5 C130C5C4 C220C5C4 C