溪黄草的功效与作用-数学应用题

离散数学作业
一、选择题
1、下列语句中哪个是真命题（
C
）。
A．我正在说谎。
B．如果1+2=3，那么雪是黑色的。
C．如果1+2=5，那么雪是白色的。
D．严禁吸烟！
2、设命题公式
Gp(p(qr))
，则G是（
C
）。
A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式
3、谓词公式
F(x,y,z)xyG(x,y,z)
中的变 元
x
（
C
）。
A．是自由变元但不是约束变元
B．既不是自由变元又不是约束变元
C．既是自由变元又是约束变元
D．是约束变元但不是自由变元
4、设A={1，2，3}，则下列关系R不是等价关系的是（
C
）
A．R={<1，1>，<2，2>，<3，3>}
B．R={<1，1>，<2，2>，<3，3>，<2，3>，<3，2>}
C．R={<1，1>，<2，2>，<3，3>，<1，4>}
D．R={<1，1>，< 2，2>，<3，3>，<1，2>，<1，3>，<2，3>，<2，1>，
<3，1>，<3，2>}
5、设R为实数集，映射=RR，（x）= -x
2
+2x-1，则是（
D
）。
A．单射而非满射 B．满射而非单射 C．双射 D．既不是单射，也不是满射
6、下列二元运算在所给的集合上不封闭的是（
D
）
A. S={2x-1|x

Z
+
}，S关于普通的乘法运算
B. S={0，1}，S关于普通的乘法运算
C. 整数集合Z和普通的减法运算
D. S={x | x=2
n
，n

Z
+
}，S关于普通的加法运算
7、*运算如下表所示，哪个能使（{a,b}，*）成为含幺元半群（
D
）
abababab
aabaaaaaaaab
bab

bbb

baa

bba

A B C D
8、下列图中是欧拉图的是（
A
）。

A B C D
9、下列各组数中,能构成无向图的度数列是（
D
）
A．1,1,1,2,4 B．1,2,3,4,5
C．0,1,0,2,4 D．1,2,3,3,5
10、一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树中树叶的个
数是（
B
）
A .8 B.9 C. 10 D. 11
11、“所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。”则该
句话（
B
）
A．不是命题 B．是真命题 C．是假命题 D．是悖论
12、一个公式在等价意义下，下面哪个写法是唯一的（
C
）。
A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不对
13、设论域E={a, b}，且P(a,a)=1 P(a,b)=0 P(b,a)=1 P(b,b)=0 则在
下列公式中真值为1的是（
D
）
A.$$x
14、设集合A={1, 2, 3 }，A上的关系R={<1, 1 >,<2, 2 > }，则R不具有
（
A
）性质。
A.自反性 B.对称性 C.传递性 D. 反对称性
15、设集合A={a,b,c,d},B={1,2,3,4} ,则从A到B的函数
f={,,,}是（
D
）。
A. 双射函数 B. 单射函数
C. 满射函数 D. 即不是满射又是不是单射函数
16、下面给出的一阶逻辑等值式中，（
B
）是错的。
A.
x(A(x)B(x))xA(x)xB(x);

B.
x(A(x)B(x))xA(x)xB(x);

C.
xA(x)x(A(x));

D.
AxB(x)x(AB(x)).

17、下列各代数系统中，不含零元素的是 （
C
）
A．
M
n
(R),
，
M
n
(R)
是全体n阶实矩阵集合，

是矩阵乘法运算。
B．
p(S),
，
p(S)
是集合S的幂集合，
< br>是集合的并运算。
C．
R,
，
R
是有理数集，

是数的加法运算。
D．
I,
，
I
是整数集，< br>
是数的乘法运算。

18、 设图G是有6个顶点的连通图，总度数为20，则从G中删去（
B
）边
后使之变成树。
A .10 B. 5 C. 3 D. 2
19、在具有n个结点的无向连通图中，（
B
）。
A. 恰好有n条边 B. 恰好有n-1条边
C. 最多有n条边 D. 至少有n条边
20、下列图是欧拉图的是（
C
）

21. 半群、群及独异点的关系是………………………………………………
（
D
）
（A）{群}

{独异点}

{半群} （B）{独异点}

{半群}

{群}
（C）{独异点}

{群}

{半群} （D）{半群}

{独异点}

{群}
22. 设集合A={1, 2, 3 }，A上的关系R={<1, 1 >,<2, 2 >,<3,3>}，则R不具
有下列性质中的……………………………………………………………… （
D
）
(A) 自反性 (B) 对称性 (C) 传递性 (D) 反自反性
23. 以下图中哪个是欧拉图…………………………………………… （
D
）

24．*运算如下表所示，哪个能使<{
a,b
}，*>成为含幺元半群…………（
D
）
abababab
aabaaaaaaaab
bab

bbb

baa

bba

(A) (B) (C) (D)
25. 设
P
：张三可以做这件事，
Q
：李四可以做这件事 。命题“张三或李四可以
做这件事”符号化为…………………………………………………（
A< br>）
(A)
PQ
(B)
P~Q
(C)
PQ
(D)
~(~P~Q)

26.
27.
G
是连通的平面图 ，有5个顶点，6个面，则
G
的边数为……………（
C
）
(A) 6 (B) 5 (C) 9 (D) 11
28. 下列句子中是命题的有 …………………………………………… （
D
）
(A) 上课时请不要说话! (B) 我在说谎.（C）你吃饭了吗？（D）上海是中国
的首都.
29. 以下命题公式中，为永假式的是(
C
)
(A) p→(p∨q∨r) (B) (p→┐p)→┐p
（C）┐(q→q)∧p （D）┐(q∨┐p)→(p∧┐p)
30. 图 的生成子图为……………………………（
C
）






(A) (B) (C) (D)
31.如下图所示的有界格中，元素b的补元是(
D
)
（A）a
（B）0
（C）c
（D）d
32. 设A={a,b,c}，则下列是集合A的划分的是(
D
)
（A） {{b,c},{c}} （B）{{a,b},{a,c}} （C）{{a,b},c} （D）{{a},{b,c}}
33. 整数集合Z上“＜”关系的自反闭包是关系 （
D
）
(A) = (B)≠ (C)＞ (D) ≤
34. 下列式子正确的是 (
B
)
(A)

∈

(B)



(C){

}


(D){

}∈


35. 设i是虚数，·是复数乘法运算，则G =<{1,-1,i,-i},·>是群，下列是G的

子群是(
A
)
（A）<{1},·> （B）〈{-1},·〉 （C）〈{i},·〉 （D）〈{-i},·〉
36.集合A={1，2}的幂集P(A)的基数是…………………………………………
（
D
）
（A） 0 （B） 1 （C） 2 （D） 4
37. 下列哪个联结词运算不可交换？………………………………………（
A
）
(A) → (B)

(C) ∨ (D) ∧
38. 设集合A={1，2，3，…，10},下列定义的哪种运算关于集合A是不封闭的 (
D
)
(A) x*y=max{x,y} (B) x*y=(x,y) 即x,y的最大公约数

(C) x*y=min{x,y} (D) x*y=[x,y] 即x,y的最小公倍数
39.设R为实数集，函数f：R→R，f(x)=2x，则f是（
B
）
A．满射函数 B．单射函数 C．双射函数 D．非单射非满射

40. 若<
A
,*>是一个代数系统,且满足结合律,则<
A
,* >必为…………………（
A
）
(A) 半群 (B) 独异点 (C) 群 (D) 交换群
41. 设R是A上的等价关系,即R是……………………………………………（
D
）
（A）反自反的,对称的，传递的 （B）自反的,反对称的, 传递的
（C）反自反的,反对称的,传递的 （D） 自反的,对称的,传递的
42．下列哪一组命题公式是等价的……………………………………………（
B
）
(A)
~P~Q
，
PQ
(B)
A(BA)
，
~A(A~B)

(C)
Q(PQ)
，
~Q(PQ)
(D)
~A(AB)
，
B

43.设S={0,1},则S…………… ………………………………………………（
A
）
（A）在普通乘法下封闭，在普通加法下不封闭; （B）在普通加法和乘法下都封
闭；
（C）在普通加法下封闭，在普通乘法下不封闭； （D）在普通加法和乘法下都
不封闭；
44. 下面谓词公式是前束范式的是 （
A
）
A.
xyz(B(x,y)A(z))
B.
xy(B(x,y)

C.
xyz(B(x,y)A(z))
D.
x(B(x,y)yB(y))

45. 整数集合Z上“＜”关系的自反闭包是关系（
D
）
(A)= (B)≠ (C)＞ (D)≤
11.下列图既是欧拉图,又是哈密顿图的是………………………………（
C
）




(A)
(B) (C) (D)

46. 设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系 R的对
称闭包S(R)是(
C
)
(A) R∪IA (B) R (C) R∪{〈c,a〉} (D) R∩IA
47. 下列式子正确的是(
B
)
(A)

∈

(B)



(C) {

}


(D) {

}∈


48. 下列句子是命题的是(
C
)
(A) 水开了吗? (B) 这朵花多好看呀！ (C) 2是常数。 (D)我正在说谎
49. 函数
f:AB
可逆的充要条件是 （
D
）
(A) A=B (B)A与B有相同的基数 (C)
f
为满射 (D)
f
为双射
二、填空题
1、公式(P∧Q)→(R∨S)真值表中共有
16
种真值指派。
2、设A(x):x是运动员,B(x):x是强壮的.命题“没有一个运动员不是强壮的”
可符号化为 。
3、 是公式
xF(y,x)yG(y)
的前束范式。
4、设集合A={1,2,3 }上两个二元关系为R
1
={＜1,3＞，＜2,1＞，＜3,2＞} 和
R
2
={＜1,2＞，＜2,3＞，＜3,1＞}，则
R
1

R
2
= ,
t(R
1
)
。
5、 集合Z
m
={[0],[1],[2]，…，[m-1]}，在Z
m
上定义运算+
m
为：对任意的[i]，
[j]∈Z
m
有： [i]+
m
[j]=[（i+j）（modm）]，则m
，+
m
>的幺元是
[0]
，

[i]∈Z
m
的逆元是
[m-i]
。
6、无向图G如图1所示，则G的点连通度为
1
。

图1 图2

7、有向图
D
如图2所示，则有向图
D
的邻接矩阵A= ，
D
中长度为2的回路有
2
条。
8、设p：1+1=5，q：明天是阴天。则命题“只要1+1=5，那么明天是阴天”可符
号化为________ _，其真值为________
1
_。
9、设
F(x):x
是兔子，G

y

:y
是乌龟，
H(x,y):x
比< br>y
跑得快，则“并不是所有
的兔子都比乌龟跑得快。”可符号化为

1

0
10、 设有向图D的邻接矩阵A(D)=

0


0
210

010


,则长度为2的通路有
10

001


010

条.
11、设
Z
4
{0,1,2,3},xy{
xyxy4
，则
(Z< br>4
,)
的生成元
xy4xy4
是 1 或 3 。
12、具有16个结点的完全无向图其边数一定为
120
条。
13、设集合
A{2,3,4,6,8,12,24}
，R为A上的整除关系，集合 A中的极大元是
24
；极小元
2，3
；
14、整数加群的幺元是_

0___。
15若
A
={1,2,3 },
x,yA,xymin{x,y}
,则*的运算表为
16.设
A
={a,{a}},
A
的幂集
P
(
A
)是 。
17.设
G
是
n
阶无向完全图,则该图的边数为 。
18.在一棵根树中，仅有一个结点的入度为
0
_，称为树根，其余结点的入度

均为
1
。
19.设
A
、
B
是两个集合，其中
A
={
a,b,c
}，
B
={ 1，2}，则
A
×
B
= .
20. 设个体域
A
={
a
,
b
},公式xP(x)xS(x)
在
A
中消去量词后应是

21. 设M(x):x是人，D(x):x是要死的，则命题“所有的人都是要死的”可符号
化为__ ____,其中量词的辖域是___ __
22. 画出完全图
K
5

23. 设A={a,b,c},则A×A中的元素有
9
个。
24. 设集合
A
={1,2,3 ,4},
R
为
A
上的一个二元关系，
R
={<1,1>,<1,2>,
<2,1>,<3,3>}则R的关系矩阵为 .
25. 设G是m阶有向完全图,则该图的边数为
m(m-1)

26. 设P(x)：x 非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明
和能干”的为谓词表达式为___ ____。
27. 设A，B是两个集合，A={1, 2, 3, 4}，B={2, 3, 5}，则A

B=
{1.4.5}
.
28. 公式A→(

x)B(x)的前束范式为____________________。
29. 一个简单连通无向图有n个节点，它的边数至少有
n-1
条。
30. 画出完全图
K
3,3

三、计算题
1、求公式
(pq)r
的主析取范式和主合取范式。
解：方法一（等值演算法）
(pq)r

((pq)r)(r(pq))

((pq)r)((pq)r)

((pq)r)(pqr)

(pqr)(pr)(qr)

(pq r)(pqr)(pqr)(pqr)
m
1
m
3
m
4
m
7

方法二（真值表法）
公式
(pq)r
真值表如下：
p
0
0
0
0
1
1
1
1
q
0
0
1
1
0
0
1
1
r
0
1
0
1
0
1
0
1
pq

(pq)r

r(pq)

(pq)r

1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
0
1
0
1
1
0
0
1
根据真值表可以得到主析取范式为：
m
1m
3
m
4
m
7

2、列出命题公式（
(pq)p)p
的真值表。
解：
p

q


(pq)p)
(pq)p)
pq
1
1
0
1

0
0
1
1
0
1
0
1
0
0
1
1
p
1
1
1
1

1,2,3

，
R
为A上的二元关系，R={＜1,2＞＜3,1＞,＜2,3＞} ，求3、设集合A=

R ，
r(R)
，
s(R)
，
t(R)
的集合表达式。
解：因为R={<1,2>,<2,3>,<3,1>},所以
R
2
={<1,3>,<2,1>,<3,2>}
r(R)={<1,1>,<2,2>,<3,3>,<1,2>,<2,3>,<3,1>}
s(R)={<1,2>,<2,1>,<2,3>,<3,2>,<3,1>,<1,3>}
t(R)=E
A

4、在偏序集中，其中A={1,2,3,4, 6,8,12,14}，≤是A中的整除关系，
2

求集合D={2,3,4,6 }的极大元，极小元，最大元，最小元，上界，下界,最小上
界和最大下界。
解：



极大元：4，6；极小元：2，3；
最大元：无；最小元：无；
上界：12；下界1：
最小上界：12;最大下界:1
5、求带权为1, 3, 6, 7,8,11的最优二叉树,编一个最佳2元前缀码，并求其权
数.
解：最优二叉树如下图所示：
编码： 1：0000 ；3：0001 ；6：001； 7：10； 8：11； 11：01
最小生成树的权数为其权W(T)=(1+3)*4+6*3+(11+7+8)*12=86

36



15

21
7
8

10
11
7

4
6


1
3


6、用Kruskal算法求下列权图的最小生成树,并求最小生成树的权数,要求写出解的过程.

B


3
7
1
D

2
4

E

A

9

2
7
C


4

5

E


解: 取数的由小到大的排列为1＜2＜3＜4＜5＜7＜9

B 2
D

F
3

1
4

2
A


E

C

最小生成树如图所示：
最小生成树的权数为其权W(T)=12
7、设A={a,b,c,d},R={ ,,,}。试用关系图表示R及R的
传递闭包。
8、设G=＜a＞是10阶循环群，求出G的所有子群。
解：因为10的正因子是1,2,5，10
所以 G的子群有4个，
分别是
10
>={e}
5
>={e, a
5
}
2
>={e, a
2
, a
4
, a
6
，a
8
}
=G
9、（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，
应该有几片树叶？ （2）画出两棵非同构的满足（1）中顶点度数的无向树T1和
T2。
解：（1）设树有n个顶点，则有n-6片树叶
根据握手定理可知
2243(n6)2(n1)

于是n=12
因此有6片树叶。
(2)两棵非同构的树为
T
1
T
2








10、A、B、C、D四个人中要派两个人出差，需满足如下条件：
（1）若A去，则C和D中要去一人；
（2）B和C不能都去；
（3）C去则D要留下。
问有几种派法？如何派？
解：用A、B、C、D分别表示A去，B去，C去，D去出差，则命题符号化如下：

（1）A→（C⊙D）（⊙表示异或，可用其它符号）
（2）（B∧┐C）∨（┐B∧C）
（3）C→┐D
出差的派法要同时满足上述三个条件，故
G= （A→（C⊙D）∧（（B∧┐C）∨（┐B∧C））∧（C→┐D）
列该公式的真值表如下：（可以去掉所有不满足条件的，只剩6种情况如下：）
A
0
0
0
1
1
B
0
1
1
0
0
C
1
0
1
0
1
D
1
1
0
1
0
（1）
1
1
1
0
1
（2）
1
1
0
1
1
（3）
0
1
1
1
1
G
0
1
0
0
1
1 1 0 0 0 1 1 0
由真值表知有两种派法A，C去或B，D去。
11、设A={1,2,3,6,12},对于整除关系构成偏序集R
(1)作出偏序关系R的哈斯图
(2)令B={2,3,6}，求B的最大，最小元，极大、 极小元，上界，最小上界，下
界，最大下界。
12、一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。
解：设树的叶子数为x,于是T中有x+2+3个顶点,有(x+2+3)-1条边，

d(v
i
)
由握手定理知T中所有顶点的度数之和
i1
=2[(x+2+3)-1]
2*4+3*3+x*1=2*[(2+3+x)-1]
X=9
13、求带权为2, 3, 5, 7,8,9的最优二叉树,并编一个最佳2元前缀码.
解：最优二叉树如下图所示：
编码： 2：0000； 3：0001 5：001 7：10 8：11 9：01


34
19
10
5
2
3

14、带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。
5
15
7
9
7
8
xy

a

20
b

15
1
4
23
g

36
9
f

c

16
28
8
3
e 17
d


解：取数的由小到大的排列为1＜3＜4＜8＜9＜15＜16<17<20<23<28<36

a

23
f

1
8
e
g

4
b

9
3
c


d

最小生成树如图所示：
最小生成树的权数为其权W(T)=48
15、 求┐(P→Q)

(P→┐Q)的主合取范式并给出所有使命题为真的赋值。
解：原式

(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)
命题为真的赋值是P=1,Q=0和P=1,Q=1
16、某班有学生60人，其中有38人选修Visual C++课程，有l6人选修Visual
Basic课程。有21人选修Java课程；有3人这三门课程都选修，有2人这三门
课程都 不选修，问仅选修两门课程的学生人数是多少？
解 设选修Visual C++课程的学生为集合A；选修Visual Basic课程的学生为
集合B；选修Java课程的学生为集合C。
由题意可知：
|A|＝38 |B|＝16 |C|＝21
|A∩B∩C|＝3 60-|A∪B∪C|＝2
因为|A∪B∪C|＝|A|+|B|+| C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

所以有：|A∩B|+|A∩C|+|B∩C|=20。
所以仅选修两门课程的学生数是
|A∩B|+|A∩C|+|B∩C|-3|A∩B∩C|=11。

17、设〈A,R〉为一个偏序集，其中A={1，2，3，4，6，9，24，54} ，R是A上的整除关系。（1）画出〈A,R〉的哈斯图；（2）求R关于A的极大元；（3）求
B={4, 6,9}的最小上界和最大下界。

18、设G=＜a＞是12阶循环群，求出G的所有子群。
解：因为12的正因子是1,2,5，10
所以 G的子群有4个， 分别是
10
>={e}
5
>={e, a
5
}
2
>={e, a
2
, a
4
, a
6
，a
8
}
=G
四、证明题
1
1、设R
1
，R
2
为A上的关系 ，证明：
(R
1
R
2
)
1
R
11
R
2
。
证明：对任意的
x,yA
，有
x,y(R
1
R
2
)
1

y,xR
1
R
2

(y,xR
1
)(y,xR
2
)

(x,yR
1
)(x,yR
2
)

x,yR
1
R
2

1
故
(R
1
R
2
)
1
R
1
1
R
2

1
2、设R
1
，R
2
为A上的关系 ，证明：
(R
1
R
2
)
1
R
11
R
2
。
11
11
证明：对任意的
x,yA
，有
x,y(R
1
R
2
)
1

y,xR
1
R
2

(y,xR
1
)(y,xR
2
)

(x,yR
1
)(x,yR
2
)

x,yR
1
R
2

1
故
(R
1
R
2
)
1
R
1
1
R
2

11
11

3、在自然推理系统P中，构造下面推理的证明：
只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过
受害者房间。如果 A在11点以前离开，看门人会看见他。看门人没有看见他，
所以A犯了谋杀罪。
证明： 命题符号化：
p：A曾到过受害者房间
q：A11点以前离开
r ：A犯了谋杀罪
s：看门人会看见他
前提：（p∧┐q）→r，p，q→s，┐s
结论：r
证明：① ┐s
② q→s
③ ┐q
④p
⑤（p∧┐q）
⑥ （p∧┐q）→r
⑦ r
4、设C*={a+bi | a,b为实数，且a≠0}。其中i 是虚数单位。在C*上定义：
R={| a+bi∈C*∧c+di∈C*∧ac＞0}
（1）证明：R是C*上的等价关系；
（2）给出R产生的等价类。
证明：（1）对任意的a+bi∈C
*
，
a≠0Ûaa＞0Û（a+bi）R（a+bi）
所以R是自反的。
（2）对任意的a+bi，c+di∈C
*
，
（a+bi）R（c+di）Ûac＞0 Û ca＞0 Û（c+di）R（a+bi）
所以R是对称的。
（3）对任意的a+bi，c+di， e+fi∈C
*
，
（a+bi）R（c+di），（c+di）R（e+fi）Û ac＞0，ce＞0Ûae＞0
Û（a+bi）R（e+fi）
所以R是传递的。
综上R是一个等价关系。
R有两个不同的等价类。设为K
1
，K
2

K
1
={（a+bi）∧a＞0}，K
2
={（a+bi）∧a＜0}
5、证明：6阶群中必含3阶元。
证明：设G是6阶群，由L—定理的推论1知G中元素的阶只可能是1，2，
3，6。
若G中含有6阶元，设该元素为a，则a
2
为3阶元。
若G中不含有6阶元 ，下面证明G中必含有3阶元。若不然G中只含有1
阶和2阶元，即对任意a∈G，有a
2=e，则G是Abel群，取G中两个不同的2 阶
元a,b，令H={e,a,b,ab}，则H 是G的子群，但|H|=4，|G|=6，4不整除6，矛
盾。故G中必含有3阶元。
6、构造下面推理的证明:
前提:
x(F(x)H(x)),x(G(x)H(x)).

结论:
x(G(x)F(x)).

证明:
(1)
x(F(x)H(x))
前提引入
(2)
x(F(x)H(x))
(1)置换
(3)
x(H(x)F(x))
(2)置换
(4)
H(y)F(y))
(3)UI
(5)
x(G(x)H(x))
前提引入
(6)
G(y)H(y))
(5)UI
(7)
G(y)F(y))
(6)(4)假言三段论
(8)
x(G(x)F(x)).
(7)UG
7、、构造下列推理的证明.
前提:
pq,pr,st,sr,t

结论:
q

证明：
(1)
st
前提引入
(2)
t
前提引入
(3)
s
(1)(2)拒取式
(4)
sr
前提引入
(5)
r
(3)(4)假言推理
(6)
pr
前提引入
(7)
p
(5)(6)拒取式
(8)
pq
前提引入
(9)
q
(7)(8)析取三段论

8、设
Z
为整数集合,在
Z
上定义二元运算*,
x,yZ
有
xyxy1

证明: (
Z
, *)是群.
证明: (1) 封闭性：
(2) 可结合性：
(3)幺元为1 ：
(4)x的逆元为
X2x

9、试证：任一棵非平凡树G至少有两片树叶。
证明：设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条
边，由握手定理知T中所有顶点的度数之和

=2(x+y-1)。
又树叶的度为1，任一分支点的度大于等于2于是
xy


d(v
i
)
≥x·1+2y
d(v
i
)
i1
xy
1
i1
从而2(x+y-1)≥x+2y
x≥2
证毕。
10、设
Q
为有理数集合,在
Q-{1}
上定义二元运算*,
x,yQ
-{1}有
xyxyxy

证明：是群。
证明:
(1) 封闭性：
(2) 可结合性：
(3)幺元为0 ：
x
(4)x的逆元为
x
1


x1
11、有代数系统V1 =,V2=<
R

,·>,其中＋,·为普通加法和乘法,令
j :R→
R

j (x)=
e
x
, 试证j映射为同构映射。
xy
xy
e
ee
证明：(1)∈R,j(x＋y)= = ·=j(x)·j(y),所以, j 是V1
到V2的同态.
xy
(2) ∈R， x

y 则有
e

e
，即j(x)

j(y)，所以, j 是V1到
V2的单射

（3）∈
R
，有x=lny∈R , 所以, j 是V1到V2的满射
综上三点，所以j 是V1到V2的同构映射
12、在自然推理系统F中，构造下面推理的证明：
任何人如果喜欢音乐就不喜欢体育。每 个人或者喜欢体育或者喜欢美术。有
的人不喜欢美术，因而有的人不喜欢音乐。（个体域为人类集合）
命题符号化：
F(x)
：
x
喜欢音乐
G(x)
：
x
喜欢体育
H(x)
：
x
喜欢美术
前提：
x(F( x)G(x))
，
x(G(x)H(x))

结论：
xH(x)xF(x)

证明：附加前提证明法
①
xH(x)
附加前提引入
②
H(c)
EI规则
③
x(G(x)H(x))
前提引入
④
G(c)H(c)
UI规则
⑤
G(c)
②④析取三段论
⑥
x(F(x)G(x))
前提引入
⑦
F(c)G(c)
UI规则
⑧
F(c)
⑤⑦拒取
⑨
xF(x)
EG规则
13、设R是A上的自反的和传递的，如下定义A上的关系T，使得
x,yA
，
x,yTx,yRy,xR

证明：T是A上的等价关系。
证明：因为R具有自反性,所以对任意的
xA
，
x,xR
故
x,xRx,xRx,xT

所以T具有自反性。
对任意的
x,yT
，有
x,yT

x,yRy,xR

y,xRx,yR

y,xT

所以T具有对称性；
利用R具有传递性，若
x,y,y,zT
，则
x,yTy,zT

(x,yRy,xR)(y ,zRz,yR)
(x,yRy,zR)(z,yRy,x R)

x,zRz,xR

x,zT


所以T具有传递性；
因为T具有自反性、对称性和传递性，所以R是一个等价关系。

14、设Z为 整数集合，在Z上定义二元运算

如下：
x,yZ,xyxy2

证明：Z关于

运算构成群。
证明：
因为对任意的
x, yZ
，有
xy2Z
，所以整数集合Z关于运算

封闭。
对
x,y,zZ
有
(xy)z(xy2)zxyz4

x(yz)x(yz2)xyz4

故
(xy)z(xy)z
，即运算

满足结合律。 2Z
，且对任意的
xZ
有
x22xx
，所以2是< br>Z,
的单位元。
对任意的
xZ
有
4xZ
，且
x(4x)(4x)x2
，即
x
1
4x< br>
综合上述可知Z关于

运算构成群。