离散数学（大作业）-吉林大学

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

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

1．请给出集合运算的等幂率。 答：等幂律 A?A=A，A?A=A

2．请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。 答：设A={1,2,3}, R={（1，1），（2，2），（3，3）} 既对称又反对称。

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

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

5．关于P，Q，R请给出使极小项m1，m7为真的解释。

答：P=0,Q=0,R=1, ?P∧?Q∧R，记为m1 取1值，为真； P=1,Q=1,R=1，P∧Q∧R 记为m7 取1值，为真。

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

设G=(P,L)是图，(v0 ,v1, …, vn)是G中从v0 到vn的路，称此路为简单路，如果 （1） v0 , …, vn-1互不相同 （2） v1 , …, vn互不相同

显然，一条简单路(v0 ,v1, …, vn)，除v0与 vn可以相同外，其他任意两点都不相同。

B C

A F E D

上图中，路(A，B，C，D)，（A，E，D，A）是简单路，而路（A，B，F，C，B）不是简单路。

设G=(P，L)是图，G中从点v到自身的长度不小于3的简单路，称为回路。 上图中，路（A，E，D，A），（A，D，C，F，B，A）是回路。

当简单路的起点和终点重合时，并且从起点再到自身的长度大于等于3时，即为回路。

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

答：对于?的单位元是S，对于?的单位元是空集?。

8．什么是群中左模H合同关系？ 答：包含a的左陪集，就是以H的所有元素乘以a所得的集合Ha，定义a合同于b(左模H)，a≡b（左mod H）

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

9．有壹环的子环是否一定是有壹环？ 答：不一定，可能有，也可能没有

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

N1=6R={0，6}，不是R的极大理想，是R的主理想。 N2=2R={0，2，4，6，8，10}，是R的极大理想。

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

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

-1-1-1

（2）(R∩S)= R∩S 答： 证明：

-1

(1)任取(x,y)∈(R∪S)，即(y,x) ∈(R∪S)，也就是(y,x) ∈R或者(y,x) ∈S，于是(x,y) -1-1-1-1-1-1-1∈R或者(x,y) ∈S，故(x,y) ∈R∪S，，即证得(R∪S)= R∪S 证明：

-1

(2)任取(x,y) ∈(R∩S)，即(y,x) ∈(R∩S)，也就是(y,x) ∈R并且(y,x) ∈S，于是(x,y) -1-1-1-1-1-1-1∈R并且(x,y) ∈S，故(x,y) ∈R∩S，即证得(R∩S)=R∩S

-1

-1

-1

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

答：

证明：对公式构造真值表

n

找出公式中出现的所有原子，显然，有n个不同原子的公式，共有2 组赋值。 真值表如下图 P 0 0 1 1 Q 0 1 0 1 P? Q 1 1 0 1 ?P?Q 1 1 0 1 （P? Q）?（?P?Q） 1 1 1 1 四、（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)；

答：

(1) T1(?x?yP(x，y))

=T1(?yP(a，y) ∧?yP(b，y))

=T1((P(a,a)∨P(a,b)) ∧(P(b,a) ∨P(b,b)))

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

=(1∨0) ∧(0∨1) =1

(2) T1(?x?yP(x，y))

=T1(?yP(a，y) ∧?yP(b，y))

=T1((P(a，a) ∧P(a,b)) ∧(P(b,a) ∧P(b,b))) =(1∧0) ∧(0∧1) =0

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

答：

1）G有限，由已知得到：

(1) G中每一点恰是一条弧e的起点。 (2) r不是任一条弧的起点

现只需证明r一定是根，即对于任意一点v必有一条到r的有向路。由于每一个点只发出一条弧，设v发出弧e1到v’，若v’不为r，则v’必发出一条弧到达v”（因为无

(k)(k)

回路，v”，v’，v互不相同）。假设已经找到点v，若v=r则得到v到r的有向路，否则可以继续向前找，但因为G有限，有向路必然终止在某一点设为u，若u≠r，则u

(i)

必为已经找到的一点v，因而形成回路，产生矛盾，则可知u=r，故有从u到r的有向路，也就是v=r，则有从v到r的有向路，因v任意，则r是根，所以G是有向路。 2)若G无限，则G不一定是有向树。如：

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