离散数学

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

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

1．请给出集合运算的等幂率。

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

3．设A={1，2，3}，问全域关系是否具有自反性，对称性？

4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={4,3}，求M的上界，下界。5．关于P，Q，R请给出使极小项m1，m7为真的解释。

6．什么是图中的回路，请举一例。

7．设S是一个非空集合，ρ（S）是S的幂集，⋂，⋃是集合的交，并运算。求对于⋂的单位元，对⋃的单位元。

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

9．有壹环的子环是否一定是有壹环？

10．设R={0，1，2，3，4，5，6，7，8，9，10，11}是模12的整数环，问N1=6R，N2=2R是否为R的极大理想？

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

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

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

三、（20分）对P和Q的所有值，证明P→Q与⌝P∨Q有同样的真值。证明（P→Q）↔（⌝P∨Q）是恒真的。

四、（18分）设I是如下一个解释：

D={a，b}

P(a，a) P(a，b) P(b，a) P(b，b)

1 0 0 1

试确定下列公式在I下的真值：

(1)∀x∃yP(x，y)；

(2)∀x∀yP(x，y)；

五、（20分）设G为有向图，若G具有有向树定义中的1)和2)，并且没有有向回路。问：若G有限，G是否是有向树？若G不是有限的，如何？