离散数学（大作业）

本文格式为Word版，下载可任意编辑——离散数学（大作业）2023-2023学年其次学期期末《离散数学》大作业

一、简要回复以下问题：（每题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可以一致外，其他任意两点都不一致。

BC

AFED

上图中，路(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（左modH）

2023-2023学年其次学期期末《离散数学》大作业

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组赋值。真值表如下图P0011Q0101P?Q1101?P?Q1101（P?Q）?（?P?Q）1111四、（18分）设I是如下一个解释：

D={a，b}

P(a，a)P(a，b)P(b，a)P(b，b)1001试确定以下公式在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)))

2023-2023学年其次学期期末《离散数学》大作业

=(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