《离散数学(大作业) (1)》由会员分享，可在线阅读，更多相关《离散数学(大作业) (1)（4页珍藏版）》请在金锄头文库上搜索。
1、2014-2015 学年第二学期期末离散数学 大作业一、简要回答下列问题：（每小题 3 分，共 30 分）1请给出集合运算的等幂率。解： AA=A;AA=A 2请给出一个集合 A，并给出 A 上既具有对称性，又具有反对称性的关系。解：A=1,2 R=(1,1),(2,2)3设 A=1，2，3，问全域关系是否具有自反性，对称性 ？解：全域关系：AAR=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)因为任意 X 属于 A，均有（x,x）属于 R，所以自反。 （1，1） ， （2，2） ， （3，3）因为任意 X,Y 属于 A，若（x,y）
2、属于 R，均有（y,x）属于 R，所以对称。（1，2）和（2，1） ， （1，3）和（3，1） ， （2，3）和（3，2）4设 A=1，2，3，4，5，6，R 是 A 上的整除关系，M=4,3，求 M 的上界，下界。解： 上界：无 下界：15关于 P，Q，R 请给出使极小项 m1，m 7为真的解释。解： 即 P=0,Q=0,R=1 或 P=1，Q=1，R=1 时 为 1(PR) (QR)6什么是图中的回路，请举一例。解：在图中，一条通路是顶点和边的交替序列，以顶点 开始，以顶点结束。其中，第一条边的终点与第二条边的始点重。第 1 条边的始点称为通路的始点，最后一条边的终点称为通路的终点。当通路
3、的终点和始点重合时，称为回路。如：简单通路：v 1 v2 v5 v6 v2 v3 v4 简单回路：v 1 v2 v3 v5 v2 v6 v1 2014-2015 学年第二学期期末离散数学 大作业7设 S 是一个非空集合，（S）是 S 的幂集， 是集合的交，并运算。求对于 的单位元，对 的单位元。8什么是群中左模 H 合同关系？9有壹环的子环是否一定是有壹环？10设 R=0，1，2，3，4，5，6，7，8，9，10，11是模 12 的整数环，问 N1=6R，N 2=2R是否为 R 的极大理想？二、 （12 分）R，S 是集合 A 上的两个关系。试证明下列等式：（1）(RS) -1= R-1S -
4、1（2）(RS) -1= R-1S -11,证明：对任意的 ，有yx,1)S(,),()R(xyxy, 11S故 11)(2,证明：对任意的 ，有Ayx,1)SR(,)S,(),(xyxy11R,故 11)S(2014-2015 学年第二学期期末离散数学 大作业三、 （20 分）对 P 和 Q 的所有值，证明 P Q 与 PQ 有同样的真值。证明（P Q）（PQ）是恒真的。证明：对公式 A 构造真值表：找出公式中所有命题变元：P 1, P2Pn 列出全部的 2n 组赋值确定过渡子公式，并加入到真值表计算各个过渡子公式的真值，并最终计算出公式 A 的真值（真值表）P Q P Q PQ （P Q）
5、（PQ）0 0 1 1 10 1 1 1 11 0 0 0 11 1 1 1 1从真值表可以看出，不管对 P 作任何指派，都使得 P Q 和 PQ 的真值相同。所以它们之间彼此等价。所以， （P Q）（PQ）恒真四、 （18 分）设 I 是如下一个解释：D=a，bP(a，a) P(a，b) P(b，a) P(b，b)1 0 0 1试确定下列公式在 I 下的真值：(1)xyP(x，y)；(2)xyP(x，y)；解：1， ),(),(bxpax原 式 ),(bpap)10(2014-2015 学年第二学期期末离散数学 大作业2， ),(),(bxpax原 式） ）（）（） ）（）（ bpa, 05
6、、 （20 分）设 G 为有向图，若 G 具有有向树定义中的 1)和 2)，并且没有有向回路。问：若 G 有限，G 是否是有向树？若 G 不是有限的，如何？解：1）G 有限，由已知有：G 中每一点恰是一条弧 e 的起点。r 不是任一条弧的起点现只需证 r 是根，即对于任意一点 v 必有一条到 r 的有向路。由于每一个点只发出一条弧，设 v 发出弧 e1 到 v，若 v不为 r，则 v必发出一条弧到达 v”（因为无回路，v”，v，v 互不相同）。假设已经找到点 v(k) ，若 v(k) =r 则得到 v 到 r的有向路，否则可以继续向前找，但因为 G 有限，有向路必然终止在某一点设为 u，若ur，则 u 必为已经找到的一点 v(i) ，因而形成回路，产生矛盾，则可知 u=r，故有从 u 到 r 的有向路，因 v 任意，则 r 为根，所以 G 是有向路。2），若 G 无限，则 G 不一定是有向树，如：
