下载文档原格式
一、简要回答下列问题：（每小题3分，共30分）
1．请给出集合运算的等幂率。
解：A∪A=A;A∩A=A
2．请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。
解：A={1,2} R={(1,1),(2,2)}
3．设A={1，2，3}，问全域关系是否具有自反性，对称性？
解：全域关系：A×A
R={(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）属于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的上界，下界。
解：上界：无下界：1
5．关于P，Q，R请给出使极小项m1，m7为真的解释。
解：即P=0,Q=0,R=1 或 P=1，Q=1，R=1时为1
(P∨R) ∧(Q∨R)
6．什么是图中的回路，请举一例。
解：在图中，一条通路是顶点和边的交替序列，以顶点开始，以顶点结束。其中，第一条边的终点与第二条边的始点重。
第一条边的始点称为通路的始点，最后一条边的终点称为通路的终点。当通路的终点和始点重合时，称为回路。
如：简单通路：v1v2v5v6v2v3v4
简单回路：v1v2v3v5v2v6v1
7．设S 是一个非空集合，ρ（S ）是S 的幂集，⋂，⋃是集合的交，并运算。求对于⋂的单位元，对⋃的单位元。
8．什么是群中左模H 合同关系？
9．有壹环的子环是否一定是有壹环？
10．设R={0，1，2，3，4，5，6，7，8，9，10，11}是模12的整数环，问N 1=6R ，N 2=2R 是否为R 的极大理想？
二、（12分）R ，S 是集合A 上的两个关系。试证明下列等式：
（1）(R ∪S)-1
= R -1
∪S -1
（2）(R ∩S)-1= R -1∩S
-1
1,证明：对任意的A y x ∈,，有
1)S R (,-⋃>∈ S R ,⋃>∈⇔ )S ,()R ,(⋂>∈<∨>∈<⇔x y x y )S ,()R ,(11--⋂>∈<∨>∈<⇔y x y x 11S R ,--∨>∈⇔ 故111S R )S R (---⋃=⋃ 2,证明：对任意的A y x ∈,，有 1)S R (,-⋂>∈ S R ,⋂>∈⇔ )S ,()R ,(⋂>∈<∧>∈<⇔x y x y )S ,()R ,(11--⋂>∈<∧>∈<⇔y x y x 11S R ,--⋂>∈⇔ 故111S R )S R (---⋂=⋂ 三、（20分）对P 和Q 的所有值，证明P → Q 与⌝P ∨Q 有同样的真值。证明（P → Q ）↔（⌝P ∨Q ）是恒真的。 证明：对公式A 构造真值表： 找出公式中所有命题变元：P 1, P 2…Pn 列出全部的2 n 组赋值 确定过渡子公式，并加入到真值表 计算各个过渡子公式的真值，并最终计算出公式 A 的真值 （真值表） P Q P → Q ⌝P ∨Q （P → Q ）↔（⌝P ∨Q ） 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 从真值表可以看出，不管对P 作任何指派，都使得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)； 解： 1， )),(),((b x p a x p x ∨∀⇔原式 )),(),(()),(),((b b p a b p b a p a a p ∨∧∨⇔ )10()01(∨∧∨⇔ 1⇔ 2，)),(),((b x p a x p x ∧∀⇔原式 a a p a b ）） , ∧ ⇔ ∧ ,∧ , p p, （ ）） （ ） b （ （ ） p a b （b （ ⇔ 五、（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，若u≠r，则u必为已经找到的一点v(i) ，因而形成回路，产生矛盾，则可知u=r，故有从u到r 的有向路，因v任意，则r为根，所以G是有向路。 2），若G无限，则G不一定是有向树，如：
