离散数学大作业答案

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∧┐rm4=p∧┐q∧┐r6．什么是图中的简单路？请举一例。答：图的通路中，所有边e1,e2,…,ek互不相同，称为简单通路。7．什么是交换群，请举一例。答：如果群〈G，*〉中的运算*是可以交换的，则称该群为可交换群，或称阿贝尔群。如〈I，+〉是交换群。8．什么是群中右模H合同关系？答：设G是群，H是G的子群，a,b∈G，若有h∈H，使得a=bh，则称a合同于b（右模H），记为a≡b（右modH）。9．什么是有壹环？请举一例。答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，则称e为A中关于运算☆的幺元。显然，对任一x∈A，有e☆x=x☆e=x环设A,△,☆是具有两个二元运算△和*的代数系统，如果适合:①A,△是交换群(阿贝尔群)；②A,☆是半群；③运算☆对运算△是可分配的，即：2014-2015学年第一学期期末《离散数学》大作业a☆(b△c)=(a☆b)△(a☆c)(b△c)☆a=(b☆a)△(c☆a)则称A,△,☆是环。含幺环：如果A,☆是独异点(或含幺半群)，则称A,△,☆是含幺环。设V=A,☆是半群，如果V中有幺元存在，则称V为含幺半群，也称为独异点。设V=A,☆是代数系统，☆是非空集合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证明：先证(R•S)-1S-1•R-1，对任意(x，y)(R•S)-1，则(y，x)(R•S)，则存在aA，满足(y，a)R且(a，x)S，那么(x，a)S-1且(a，y)R-1，所以(x，y)S-1•R-1，因此(R•S)-1S-1•R-1；再证S-1•R-1(R•S)-1，对任意(x，y)S-1•R-1，则存在aA，满足(x，a)S-1且(a，y)R-1，所以(y，a)R且(a，x)S，所以(y，x)(R•S)，所以(x，y)(R•S)-1，因此S-1•R-1(R•S)-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是恒真的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）xA(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列元素给出(表示没有直接班机)：050402510500152025150102040201001025252010055102525550公司所关心的是计算两城市间的最便宜路线的表格。请准备一张这样的表格。C1C2C3C4C5C6C035C1C6C245C1C5C3或C1C6C4C3或C1C5C4C335C1C5C4或C1C6C425C1C510C1C6C235C2C6C1015C2C320C2C430C2C4C525C2C6C345C3C4C6C1或C3C5C1或C3C4C5C115C3C2010C3C420C3C4C5或C3C535C3C4C6C435C4C5C1或C4C6C125C4C210C4C3010C4C525C4C62014-2015学年第一学期期末《离散数学》大作业C525C5C130C5C4C220C5C4C3或C5C310C5C4035C5C4C6或C5C1C6C610C6C125C6C235C6C4C325C6C435C6C4C5或C6C1C50