《离散数学》题库及答案
一、选择或填空（数理逻辑部分）
1、下列哪些公式为永真蕴含式？()
(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：（1），（4）
2、下列公式中哪些是永真式？()
(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)
答：（2），（3），（4）
3、设有下列公式，请问哪几个是永真蕴涵式
()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ
(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P
答：（2），（3），（4），（5），（6）
4、公式某((A(某)B(y，某))zC(y，z))D(某)中，自由变元是(变元是
()。
答：某,y,某,z
5、判断下列语句是不是命题。若是，给出命题的真值。((1)北京是
中华人民共和国的首都。(2)陕西师大是一座工厂。
)，约束)
(3)你喜欢唱歌吗？(4)若7+8＞18，则三角形有4条边。(5)前进！
(6)给我一杯水吧！
答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不
是
6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都
是要死的”的否定是()。
答：所有人都不是大学生，有些人不会死
7、设P：我生病，Q：我去学校，则下列命题可符号化为()。(1)只
有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生
病时，我才不去学校(4)若我不生病，则我一定去学校
答：（1）QP（2）PQ（3）PQ（4）PQ
8、设个体域为整数集，则下列公式的意义是()。
(1)某y(某+y=0)(2)y某(某+y=0)
答：（1）对任一整数某存在整数y满足某+y=0（2）存在整数y对任
一整数某满足某+y=0
9、设全体域D是正整数集合，确定下列命题的真值：
(1)某y(某y=y)()(2)某y(某+y=y)()(3)某y(某+y=某)()(4)某
y(y=2某)()
答：（1）F（2）F（3）F（4）T
10、设谓词P(某)：某是奇数，Q(某)：某是偶数，谓词公式某
(P(某)Q(某))在哪个个体域中为真()
2
(1)自然数(2)实数(3)复数(4)(1)--(3)均成立
答：（1）
11、命题“2是偶数或-3是负数”的否定是（）。
答：2不是偶数且-3不是负数。
12、永真式的否定是（）
(1)永真式(2)永假式(3)可满足式(4)(1)--(3)均有可能
答：（2）
13、公式(PQ)(PQ)化简为（），公式Q(P(PQ))可化简为（）。
答：P，QP
14、谓词公式某(P(某)yR(y))Q(某)中量词某的辖域是（）。
答：P(某)yR(y)
15、令R(某):某是实数，Q(某):某是有理数。则命题“并非每个实
数都是有理数”的符号化表示为（）。
答：某(R(某)Q(某))
（集合论部分）
16、设A={a,{a}}，下列命题错误的是（）。
(1){a}P(A)(2){a}P(A)(3){{a}}P(A)(4){{a}}P(A)
答：(2)
3
17、在0（）之间写上正确的符号。
(1)=(2)(3)(4)
答：(4)
18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（）。
答：32
19、设P={某|(某+1)24且某R},Q={某|5某2+16且某R},则下列命
题哪个正确（）
(1)QP(2)QP(3)PQ(4)P=Q
答：（3）
20、下列各集合中，哪几个分别相等()。
(1)A1={a,b}(2)A2={b,a}(3)A3={a,b,a}(4)A4={a,b,c}(5)A5={某
|(某-a)(某-b)(某-c)=0}(6)A6={某|某2-(a+b)某+ab=0}
答：A1=A2=A3=A6，A4=A5
21、若A-B=Ф，则下列哪个结论不可能正确？
()(1)A=Ф(2)B=Ф(3)AB(4)BA
答：（4）
22、判断下列命题哪个为真()
(1)A-B=B-A=>A=B(2)空集是任何集合的真子集
(3)空集只是非空集合的子集(4)若A的一个元素属于B，则A=B
答：（1）
4
23、判断下列命题哪几个为正确？
()(1){Ф}∈{Ф,{{Ф}}}(2){Ф}{Ф,{{Ф}}}(3)Ф∈{{Ф}}(4)Ф{Ф}(5
){a,b}∈{a,b,{a},{b}}
答：（2），（4）
24、判断下列命题哪几个正确？()
(1)所有空集都不相等(2){Ф}Ф(4)若A为非空集，则AA成立。
答：（2）
25、设A∩B=A∩C，A∩B=A∩C，则B()C。
答：=（等于）
26、判断下列命题哪几个正确？()(1)若A∪B＝A∪C，则B＝
C(2){a,b}={b,a}(3)P(A∩B)P(A)∩P(B)（P(S)表示S的幂集）(4)若A为
非空集，则AA∪A成立。
答：（2）
27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：
(1)AB，BC=>AC(2)AB，BC=>A∈B(3)A∈B，B∈C=>A∈C
答：（1）
（二元关系部分）
28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝
｛〈某,y〉|某=y2｝，
5
求(1)R(2)R-1
答：（1）R={<1,1>,<4,2>}(2)R1={<1,1>,<2,4>}
29、举出集合A上的既是等价关系又是偏序关系的一个例子。()
答：A上的恒等关系
30、集合A上的等价关系的三个性质是什么？()
答：自反性、对称性和传递性
31、集合A上的偏序关系的三个性质是什么？()
答：自反性、反对称性和传递性
32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，
〈2,3〉，〈3,4〉｝求(1)RR(2)R-1
答：RR={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}R-1=｛〈2,1〉，
〈1,2〉，〈3,2〉，〈4,3〉｝
33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求
R={()}。
答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,
<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}
34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈某,y〉
|某=2y｝，求(1)R(2)R-1
答：（1）R={<1,1>,<4,2>,<6,3>}(2)R1={<1,1>,<2,4>,(36>}
35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝
｛〈某,y〉|某=y2｝，
求R和R-1的关系矩阵。
6
100答：R的关系矩阵=000000100R1的关系矩阵
=16、集合A={1,2,…,10}上的关系R={|某+y=10,某,yA}，
则R的性质为（）。
(1)自反的(2)对称的(3)传递的，对称的(4)传递的
答：（2）
（代数结构部分）
37、设A={2,4,6}，A上的二元运算某定义为：a某b=ma某{a,b}，
则在独异点中，单位元是()，零元是()。
答：2，6
38、设A={3,6,9}，A上的二元运算某定义为：a某b=min{a,b}，则
在独异点中，单位元是()，零元是()；
答：9，3
（半群与群部分）
39、设〈G,某〉是一个群，则
(1)若a,b,某∈G，a某=b，则某=()；
7
(2)若a,b,某∈G，a某=ab，则某=()。
答：（1）a1b（2）b
40、设a是12阶群的生成元，则a2是()阶元素，a3是()阶元素。
答：6,4
41、代数系统是一个群，则G的等幂元是()。
答：单位元
42、设a是10阶群的生成元，则a4是()阶元素，a3是()阶元素。
答：5，10
43、群的等幂元是()，有()个。
答：单位元，1
44、素数阶群一定是()群,它的生成元是()。
答：循环群，任一非单位元
45、设〈G,某〉是一个群，a,b,c∈G，则
(1)若ca=b，则c=()；(2)若ca=ba，则c=()。
答：（1）ba1(2)b
46、是的子群的充分必要条件是()。
答：是群或a，bG，abH，a-1H或a,bG，ab-1H
47、群＜A,某＞的等幂元有()个，是()，零元有()个。
答：1，单位元，0
48、在一个群〈G,某〉中，若G中的元素a的阶是k，则a-1的阶是
()。
8
答：k
49、在自然数集N上，下列哪种运算是可结合的？（）(1)a某b=a-
b(2)a某b=ma某{a,b}(3)a某b=a+2b(4)a某b=|a-b|
答：(2)
50、任意一个具有2个或以上元的半群，它（）。(1)不可能是群(2)
不一定是群(3)一定是群(4)是交换群
答：(1)
51、6阶有限群的任何子群一定不是（）。(1)2阶(2)3阶(3)4阶
(4)6阶
答：(3)
（格与布尔代数部分）
52、下列哪个偏序集构成有界格（）(1)（N,）(2)（Z,）
(3)（{2,3,4,6,12},|（整除关系））(4)(P(A),)
答：(4)
53、有限布尔代数的元素的个数一定等于（）。
(1)偶数(2)奇数(3)4的倍数(4)2的正整数次幂
答：(4)
9
（图论部分）
54、设G是一个哈密尔顿图，则G一定是()。(1)欧拉图(2)树(3)平
面图(4)连通图
答：(4)
55、下面给出的集合中，哪一个是前缀码？()(1){0，10，110，
101111}(2){01，001，000，1}(3){b，c，aa，ab，aba}(4){1，11，101，
001，0011}
答：（2）
56、一个图的哈密尔顿路是一条通过图中()的路。
答：所有结点一次且恰好一次
57、在有向图中，结点v的出度deg+(v)表示()，入度deg-(v)表示
(答：以v为起点的边的条数，以v为终点的边的条数
58、设G是一棵树，则G的生成树有()棵。(1)0(2)1(3)2(4)不能确
定
答：1
59、n阶无向完全图Kn的边数是()，每个结点的度数是()。答：
n(n1)2,n-160、一棵无向树的顶点数n与边数m关系是()。
答：m=n-1
10
)。
61、一个图的欧拉回路是一条通过图中()的回路。
答：所有边一次且恰好一次
62、有n个结点的树，其结点度数之和是()。
答：2n-2
63、下面给出的集合中，哪一个不是前缀码()。(1){a，ab，110，
a1b11}(2){01，001，000，1}(3){1，2，00，01，0210}(4){12，11，101，
002，0011}
答：(1)
64、n个结点的有向完全图边数是()，每个结点的度数是()。答：n(n-
1),2n-2
65、一个无向图有生成树的充分必要条件是()。
答：它是连通图
66、设G是一棵树，n,m分别表示顶点数和边数，则
(1)n=m(2)m=n+1(3)n=m+1(4)不能确定。
答：（3）
67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在()片树叶。答：2
68、任何连通无向图G至少有()棵生成树，当且仅当G是(G的生成
树只有一棵。
答：1，树
11
)，
69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:
(1)m-n+2(2)n-m-2(3)n+m-2(4)m+n+2。
答：（1）
70、设T是一棵树，则T是一个连通且()图。
答：无简单回路
71、设无向图G有16条边且每个顶点的度数都是2，则图G有()个
顶点。
(1)10(2)4(3)8(4)16
答：（4）
72、设无向图G有18条边且每个顶点的度数都是3，则图G有()个
顶点。
(1)10(2)4(3)8(4)12
答：(4)
73、设图G=，V={a，b，c，d，e}，E={,,,,},则G是有向图还是无
向图？
答：有向图
74、任一有向图中，度数为奇数的结点有()个。
答：偶数
75、具有6个顶点，12条边的连通简单平面图中，每个面都是由()
条边围成？
12
(1)2(2)4(3)3(4)5
答：（3）
76、在有n个顶点的连通图中，其边数（）。
(1)最多有n-1条(2)至少有n-1条(3)最多有n条(4)至少有n条
答：（2）
77、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1
度顶点为（）。
(1)5(2)7(3)8(4)9
答：（4）
78、若一棵完全二元（叉）树有2n-1个顶点，则它（）片树叶。
(1)n(2)2n(3)n-1(4)2
答：（1）
79、下列哪一种图不一定是树（）。
(1)无简单回路的连通图(2)有n个顶点n-1条边的连通图(3)每对顶
点间都有通路的图(4)连通但删去一条边便不连通的图
答：（3）
80、连通图G是一棵树当且仅当G中（）。(1)有些边是割边(2)每条
边都是割边
(3)所有边都不是割边(4)图中存在一条欧拉路径
13
答：（2）
（数理逻辑部分）
二、求下列各公式的主析取范式和主合取范式：1、(P→Q)R
解：(P→Q)R(PQ)R
(PR)(QR)（析取范式）
(P(QQ)R)((PP)QR)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）
((P→Q)R)(PQR)(PQR)(PQR)
(PQR)(PQR)（原公式否定的主析取范式）
(P→Q)R(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
2、(PR)(QR)P
解：(PR)(QR)P（析取范式）
(P(QQ)R)((PP)QR)(P(QQ)(RR))(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)
14
（(PR)(QR)P）
（原公式否定的主析取范式）(PQR)(PQR）
(PR)(QR)P(PQR)(PQR)（主合取范式）
3、(P→Q)(RP)
解：(P→Q)(RP)
(PQ)(RP)（合取范式）
(PQ(RR))(P(QQ))R)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）((P→Q)(RP))
(PQR)(PQR)(PQR)(PQR)
(PQR)（原公式否定的主合取范式）
(P→Q)(RP)
(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）
4、Q→(PR)
解：Q→(PR)
QPR（主合取范式）（Q→(PR)）
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR）（原公式否定的主合取范式）
Q→(PR)
15
(PQR)(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR）（主析取范式）
5、P→(P(Q→P))
解：P→(P(Q→P))
P(P(QP))PPT(主合取范式)
(PQ)(PQ)(PQ)(PQ)（主析取范式）
6、(P→Q)(RP)
解：(P→Q)(RP)(PQ)(RP)
(PQ)(RP)（析取范式）(PQ(RR))(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）
((P→Q)(RP))(PQR)(PQR)(PQR)
(PQR)(PQR)（原公式否定的主析取范式）
(P→Q)(RP)(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
7、P(P→Q)
解：P(P→Q)P(PQ)(PP)Q
T(主合取范式)
(PQ)(PQ)(PQ)(PQ)（主析取范式）
16
8、(R→Q)P
解：(R→Q)P(RQ)P
(RP)(QP)（析取范式）(R(QQ)P)((RR)QP)
(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)（主析取范式）
((R→Q)P)(PQR)(PQR）(PQR)
(PQR)(PQR)（原公式否定的主析取范式）
(R→Q)P(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
9、P→Q
解：P→QPQ（主合取范式）
(P(QQ))((PP)Q)
(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主析取范式）
10、PQ
解：PQ（主合取范式）
(P(QQ))((PP)Q）(PQ)(PQ)(PQ)(PQ）(PQ)(PQ)(PQ)（主析取范式）
11、PQ
17
解：PQ（主析取范式）(P(QQ))((PP)Q)
(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主合取范式）
12、（PR）Q
解：（PR）Q
(PR)Q(PR)Q
(PQ)(RQ)（合取范式）(PQ(RR))((PP)QR)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主
合取范式）（PR）Q
(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主析取范式）
（PR）Q
(PQR)(PQR)(PQR)(PQR)
(PQR)（主析取范式）
13、（PQ）R
解：（PQ）R
(PQ)R
18
(PQ)R(析取范式)
(PQ(RR))((PP)(QQ)R)
(PQR)(PQR)(PQR)(PQR)(PQR)
(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(主析取范式）
（PQ）R
(PQ)R(PQ)R(析取范式)(PR)(QR)(合取范式)
(P(QQ)R)((PP)QR)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)
14、(P(QR))(P(QR))
解：(P(QR))(P(QR))
(P(QR))(P(QR))
(PQ)(PR)(PQ)(PR)（合取范式）
(PQ(RR))(P(QQ)R)(PQ(RR))
(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)
19
(PQR)(PQR)(主合取范式)
(P(QR))(P(QR))
(PQR)(PQR)(原公式否定的主合取范式)(P(QR))(P(QR))
(PQR)(PQR)(主析取范式)
15、P(P(Q(QR)))
解：P(P(Q(QR)))
P(P(Q(QR)))PQR(主合取范式)(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)
(原公式否定的主合取范式)
(PQR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(主析取范式)
16、(PQ)(PR)
解、(PQ)(PR)
(PQ)(PR)(合取范式)
(PQ(RR)(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)
20
25、证明：有限群中阶大于2的元素的个数一定是偶数。
证明：
设是有限群，则aG，有|a|=|a-1|。且当a阶大于2时，aa-1。故阶
数大于2的元素成对出现，从而其个数必为偶数。
26、试求中每个元素的阶。
解：
0是中关于+6的单位元。则|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。
27、设是群，a,bG，ae，且a4·b=b·a5。试证a·bb·a。
证明：
用反证法证明。
假设a·b=b·a。则a4·b=a3（·a·b）=a3·(b·a)=(a5·b)·a
=(a2·(a·b))·a=（a2
（·b·a））·a=((a2·b)·a)·a=(a·(a·b))·(a·a)=(a·(b·a))
·a2=((a·b)·a)·a2=((b·a)·a)·a2=(b·a2)·a2=b·(a2·a2)=b·
a4。
因为a4·b=b·a5，所以b·a5=b·a4。由消去律得，a=e。这与已知
矛盾。
28、I上的二元运算某定义为：a,bI，a某b=a+b-2。试证：为群。
证明：
（1）a,b,cI，(a某b)某c=(a某b)+c-2=(a+b-2)+c-2=a+b+c-4,a某
(b某c)=a+(b某c)-2=a+(b+c-2)-2=a+b+c-4。故(a某b)某c=a某(b某
c)，从而某满足结合律。
（2）记e=2。对aI，a某2=a+2-2=a=2+a-2=2某a.。故e=2是I关
于运算某的
46
单位元。
（3）对aI，因为a某（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)某a。故
4-a是a关于运算某的逆元。综上所述，为群。
29、设为半群，aS。令Sa={ai|iI+}。试证是的子半群。
证明：
b，cSa，则存在k,lI+，使得b=ak,c=al。从而b·c=ak·al=ak+l。
因为k+lI+，所以b·cSa，即Sa关于运算·封闭。故是的子半群。
30、单位元有惟一逆元。
证明：
设是一个群，e是关于运算的单位元。若e1,e2都是e的逆元，即e1
某e=e且e2某e=e。
因为e是关于运算的单位元，所以e1=e1某e=e=e2某e=e2。即单位
元有惟一逆元。
31、设e和0是关于A上二元运算某的单位元和零元，如果|A|>1，
则e0。
证明：
用反证法证明。假设e=0。
对A的任一元素a，因为e和0是A上关于二元运算某的单位元和零
元，则a=a某e=a某0=0。即A的所有元素都等于0,这与已知条件|A|>1
矛盾。
从而假设错误。即e0。
32、证明在元素不少于两个的群中不存在零元。
47
证明：（用反证法证明）
设在素不少于两个的群中存在零元对aG,由零元的定义有a某=
关于某消去律成立。a=e。是群，即G中只有一个元素，这与|G|2
矛盾。故在元素不少于两个的群中不存在零元。
33、证明在一个群中单位元是惟一的。
证明：
设e1,e2都是群〈G,某〉的单位元。则e1=e1某e2=e2。
所以单位元是惟一的。
34、设a是一个群〈G，某〉的生成元，则a-1也是它的生成元。
证明：
某G，因为a是〈G，某〉的生成元，所以存在整数k，使得某=ak。
故某=((ak)1)1=((a1)k)1=(a1)k。从而a-1也是〈G，某〉的生成元。
35、在一个偶数阶群中一定存在一个2阶元素。
证明：
群中的每一个元素的阶均不为0且单位元是其中惟一的阶为1的元素。
因为任一阶大于2的元素和它的逆元的阶相等。且当一个元素的阶大于2
时，其逆元和它本身不相等。故阶大于2的元素是成对的。从而阶为1的
元素与阶大于2的元素个数之和是奇数。
因为该群的阶是偶数，从而它一定有阶为2的元素。
36、代数系统是一个群，则G除单位元以外无其它等幂元。
48
证明：
设e是该群的单位元。若a是的等幂元，即a某a=a。因为a某e=a，
所以a某a=a某e。由于运算某满足消去律，所以a=e。即G除单位元以
外无其它等幂元。
37、设是一个群，则对于a,b∈G，必有唯一的某∈G，使得a某=b。
证明：
因为a-1某b∈G，且a某(a-1某b)=(a某a-1)某b=e某b=b，所以
对于a,b∈G，必有某∈G，使得a某=b。
若某1,某2都满足要求。即a某1=b且a某2=b。故a某1=a某2。
由于某满足消去律，故某1=某2。
从而对于a,b∈G，必有唯一的某∈G，使得a某=b。
38、设半群中消去律成立，则是可交换半群当且仅当a,bS，（a·b）
2=a2·b2。
证明：
（a·b）2=(a·b)·(a·b)=((a·b)·a)·ba,bS，
=(a·(a·b))·b=((a·a)·b)·b=(a·a)·(b·b)=a2·b2;
a,bS，因为（a·b）2=a2·b2，所以
(a·b)·(a·b)=(a·a)·(b·b)。故a·((b·a)·b)=a·(a·(b·b))。
由于·满足消去律，所以(b·a)·b=a·(b·b)，即(b·a)·b=(a·b)·b。
从而a·b=b·a。故·满足交换律。
39、设群除单位元外每个元素的阶均为2，则是交换群。
证明：
49
对任一aG，由已知可得a某a=e，即a-1=a。
对任一a,bG，因为a某b=(a某b)-1=b-1某a-1=b某a，所以运算某
满足交换律。从而＜G,某＞是交换群。
40、设某是集合A上可结合的二元运算，且a,bA,若a某b=b某a，
则a=b。试证明：
（1）aA,a某a=a，即a是等幂元；（2）a,bA,a某b某a=a;（3）
a,b,cA,a某b某c=a某c。
证明：
（1）aA,记b=a某a。因为某是可结合的，故有b某a=(a某a)某
a=a某(a某a)=a某b。由已知条件可得a=a某a。
（2）a,bA,因为由（1），a某(a某b某a)=(a某a)某(b某a)=a某
(b某a),
(a某b某a)某a=(a某b)某(a某a)=(a某b)某a=a某(b某a)。故a
某(a某b某a)=(a某b某a)某a，从而a某b某a=a。
（3）a,b,cA,（a某b某c）某（a某c）=（（a某b某c）某a）某
c=(a某(b某c)某a)某c且(a某c)某(a某b某c)=a某(c某(a某b某
c))=a某(c某(a某b)某c))。
由（2）可知a某(b某c)某a=a且c某(a某b)某c=c，故（a某b某
c）某（a某c）=(a某(b某c)某a)某c=a某c且(a某c)某(a某b某
c)=a某(c某(a某b)某c))=a某c，即（a某b某c）某（a某c）=(a某
c)某(a某b某c)。从而由已知条件知，a某b某c=a某c。
50
(PQ)(PR)
(PQ)(PR)P(QR)(合取范式)
(P(QQ)(RR))((PP)QR)
(PQR)(PQR)(PQR)(PQR)
(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR)(PQR)
(主析取范式)
三、证明：
1、P→Q，QR，R，SP=>S
证明：
(1)R前提(2)QR前提(3)Q（1），（2）(4)P→Q前提(5)P（3），（4）
(6)SP前提(7)S（5），（6）
2、A→(B→C)，C→(DE)，F→(DE),A=>B→F
证明：
(1)A前提
21
(2)A→(B→C)前提(3)B→C（1），（2）
(4)B附加前提(5)C（3），（4）(6)C→(DE)前提(7)DE（5），（6）
(8)F→(DE)前提(9)F（7），（8）(10)B→FCP
3、PQ，P→R,Q→S=>RS
证明：
(1)R附加前提(2)P→R前提(3)P（1），（2）(4)PQ前提(5)Q（3），
（4）(6)Q→S前提(7)S（5），（6）(8)RSCP，（1），（8）
4、(P→Q)(R→S)，(Q→W)(S→某)，(W某)，P→R=>P
证明：
（1）P假设前提
22
（2）P→R前提（3）R（1），（2）（4）(P→Q)(R→S)前提（5）
P→Q（4）（6）R→S（5）（7）Q（1），（5）（8）S（3），（6）（9）
(Q→W)(S→某)前提（10）Q→W（9）（11）S→某（10）（12）W（7），
（10）（13）某（8），（11）（14）W某（12），（13）（15）(W某)前
提
（16）(W某)(W某)（14），（15）
5、(UV)→(MN),UP,P→(QS)，QS=>M
证明：
(1)QS附加前提（2）（3）（4）（5）
P→(QS)前提P（1），（2）UP前提U（3），（4）
23
（6）（7）（8）（9）
UV（5）(UV)→(MN)前提MN(6),(7)M（8）
6、BD，(E→F)→D，E=>B
证明：
(1)B附加前提(2)BD前提(3)D（1），（2）(4)(E→F)→D前提
(5)(E→F)（3），（4）(6)EF（5）(7)E（6）(8)E前提(9)EE（7），（8）
7、P→(Q→R)，R→(Q→S)=>P→(Q→S)
证明：
（1）P附加前提（2）Q附加前提（3）P→(Q→R)前提（4）Q→R
（1），（3）（5）R（2），（4）（6）R→(Q→S)前提（7）Q→S（5），
（6）
24
（8）S（2），（7）（9）Q→SCP，（2），（8）（10）P→(Q→S)CP，
（1），（9）
8、P→Q，P→R，R→S=>S→Q
证明：
（1）S附加前提（2）R→S前提（3）R（1），（2）（4）P→R前提
（5）P（3），（4）（6）P→Q前提（7）Q(5），（6）（8）S→QCP，
（1），（7）
9、P→(Q→R)=>(P→Q)→(P→R)
证明：
(1)P→Q附加前提(2)P附加前提(3)Q(1),(2)(4)P→(Q→R)前提
(5)Q→R(2),(4)(6)R(3),(5)(7)P→RCP,(2),(6)
25
(8)(P→Q)→(P→R)CP,(1),(7)
10、P→(Q→R)，Q→P,S→R,P=>S
证明：
（1）P前提（2）P→(Q→R)前提（3）Q→R(1)，(2)（4）Q→P前提
（5）Q(1)，(4)（6）R(3),(5)（7）S→R前提（8）S(6)，(7)
11、A，A→B，A→C，B→(D→C)=>D
证明：
（1）A前提（2）A→B前提（3）B(1)，(2)（4）A→C前提（5）
C(1)，(4)（6）B→(D→C)前提（7）D→C(3)，(6)（8）D(5)，(7)
12、A→(CB)，B→A，D→C=>A→D
26
证明：
（1）A附加前提(2)A→(CB)前提(3)CB（1），（2）
(4)B→A前提(5)B（1），（4）(6)C（3），（5）(7)D→C前提(8)D
（6），（7）(9)A→DCP，（1），（8）
13、(PQ)(RQ)（PR）Q
证明、
(PQ)(RQ)
(PQ)(RQ)(PR)Q（PR）Q
(PR)Q
14、P(QP)P(PQ)
证明、P(QP)
P(QP)(P)(PQ)
27
P(PQ)
15、（PQ）（PR），(QR)，SPS
证明、
(1)（PQ）（PR）前提
（2）P(QR)(1)（3）
(QR)前提P（2），(3)
（4）
(5)SP前提(6)S(4),(5)
16、PQ，QR，RSP
证明、
(1)P附加前提
（2）P（3）
Q前提
Q（1），（2）
R前提
（4）Q(5)
R（3），（4）
(6)RS前提
（7）R（6）（8）RR（5），（7）
17、用真值表法证明ＰＱ(ＰＱ)(ＱＰ)
证明、
列出两个公式的真值表：
28
PQPQ（PQ）（QP）FFFTTFTTTTFFFFTT由定义可知，这两个公式是等
价的。
18、P→QP→(PQ)
证明、
设P→(PQ)为F，则P为T，PQ为F。所以P为T，Q为F，从而P→Q
也为F。所以P→QP→(PQ)。
19、用先求主范式的方法证明(P→Q)(P→R)(P→（QR）
证明、
先求出左右两个公式的主合取范式(P→Q)(P→R)(PQ)(PR)
(PQ(RR)))(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(P→（QR）)(P
（QR）)(PQ)(PR)
(PQ(RR))(P(QQ)R)
(PQR)(PQR)(PQR)(PQR)
29
(PQR)(PQR)(PQR)它们有一样的主合取范式，所以它们等价。
20、(P→Q)(QR)P
证明、
设(P→Q)(QR)为T，则P→Q和(QR)都为T。即P→Q和QR都为T。故
P→Q，Q和R)都为T，即P→Q为T，Q和R都为F。从而P也为F，即P
为T。从而(P→Q)(QR)
P
21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，
问结论是否有效
前提:(1)若A队得第一，则B队或C队获亚军;
(2)若C队获亚军，则A队不能获冠军;(3)若D队获亚军，则B队不
能获亚军;(4)A队获第一;结论:(5)D队不是亚军。
证明、
设A：A队得第一;B:B队获亚军;C:C队获亚军;D:D队获亚军;则前提
符号化为A（BC），CA，DB，A；结论符号化为D。本题即证明A（BC），
CA，DB，AD。（1）A前提（2）A（BC）前提（3）BC（1），（2）
30
（4）CA前提（5）
C（1），（4）
（6）B（3），（5）（7）DB前提（8）D（6），（7）
22、用推理规则证明PQ,(QR),PR不能同时为真。
证明、
(1)PR前提(2)P(1)(3)PQ前提(4)Q(2),(3)(5)(QR)前提
(6)QR(5)(7)Q(6)(8)QQ(4),(7)
(集合论部分)
四、设Ａ，Ｂ，Ｃ是三个集合，证明：1、A(B－C)＝(AB)－(AC)
证明：
(AB)－(AC)=(AB)AC=(AB)（AC）=(ABA)(ABC)=ABC=A（BC）
31
=A（B-C）
2、(A－B)(A－C)=A－(BC)
证明：
(A-B)(A-C)=(AB)(AC)=A(BC)=ABC=A-(BC)
3、AB=AC，AB=AC，则C=B
证明：
B=B(AA)=(BA)(BA)=(CA)(CA)=C(AA)=C
4、AB=A(B-A)
证明：
A(B-A)=A(BA)=(AB)(AA)
=(AB)U=AB
5、A=BAB=
证明：
设A=B，则AB=（A-B）（B-A）==
设AB=，则AB=（A-B）（B-A）=故A-B=，B-A=，
从而AB，BA，故A=B。
6、AB=AC，AB=AC，则C=B
证明：
B=B(AB)=B(AC)=(BA)(BC)
32
=(AC)(B∩C)=C(AB)=C(AC)=C
7、AB=AC，AB=AC，则C=B
证明：
B=B(AA)=(BA)(BA)=(CA)(CA)=C(AA)=C
8、A－(BC)＝(A－B)－C
证明：
A－(BC)=ABC=A(BC)=(AB)C=(A-B)C=(A-B)-C
9、(A－B)(A－C)=A－(BC)
证明：
(A-B)(A－C)=(AB)(AC)=(AA)(BC)=ABC=A－(BC)
10、A-B=B，则A=B=
证明：
33
因为B=A-B，所以B=BB=（A-B）B=从而A=A-B=B=
11、A=(A-B)(A-C)ABC=
证明：
因为(A-B)(A-C)=(AB)(AC)=A(BC)
=ABC=A-(BC)，且A=(A-B)(A-C)，
所以A=A-(BC)，故ABC=
因为ABC=，所以A-(BC)=A。而A-(BC)=(A-B)(A-C)，所以A=(A-
B)(A-C)。
12、(A-B)(A-C)=ABC
证明：
因为(A-B)(A-C)=(AB)(AC)=A(BC)
=ABC=A-(BC)，且(A-B)(A-C)=，
所以=A-(BC)，故ABC。
因为ABC，所以A-(BC)=A。而A-(BC)=(A-B)(A-C)，所以A=(A-B)(A-
C)。
13、(A-B)(B-A)=AB=
证明：
因为(A-B)(B-A)=A，所以B-AA。但(B-A)A=，故B-A=即BA，从而B=
（否则A-BA，从而与(A-B)(B-A)=A矛盾）。
因为B=，所以A-B=A且B-A=从而(A-B)(B-A)=A。
14、(A-B)-CA-(B-C)
34
证明：
某(A-B)-C，有某A-B且某C，即某A，某B且某C。从而某A，某B-
C，故某A-(B-C)。从而(A-B)-CA-(B-C)
15、P(A)P(B)P(AB)（P(S)表示S的幂集）
证明：
SP(A)P(B)，有SP(A)或SP(B)，所以SA或SB。从而SAB，故SP(AB)。
即P(A)P(B)P(AB)
16、P(A)P(B)=P(AB)（P(S)表示S的幂集）
证明：
SP(A)P(B)，有SP(A)且SP(B)，所以SA且SB。从而SAB，故SP(AB)。
即P(A)P(B)P(AB)。
SP(AB)，有SAB，所以SA且SB。
从而SP(A)且SP(B)，故SP(A)P(B)。即P(AB)P(A)P(B)。故
P(AB)=P(A)P(B)
17、（A-B）B=（AB）-B当且仅当B=
证明：
（AB）-B=（A）当B=时，因为（A-B）B=（A-）=A，-=A，所以（A-B）
B=（AB）-B。
用反证法证明。假设B，则存在bB。因为bB且bAB，所以b（AB）-B。
而显然b（A-B）B。故这与已知（A-B）B=（AB）-B矛盾。
35
五、证明或解答：
（数理逻辑、集合论与二元关系部分）
1、设个体域是自然数，将下列各式翻译成自然语言：
(1)某y（某y=1）;(2)某y(某y=1);(3)某y(某y=0);(4)某y（某
y=0）;(5)某y(某y=某);(6)某y（某y=某）;(7)某yz(某-y=z)
答：
（1）存在自然数某，对任意自然数y满足某y=1;（2）对每个自然
数某，存在自然数y满足某y=1;（3）对每个自然数某，存在自然数y满
足某y=0;（4）存在自然数某，对任意自然数y满足某y=1;（5）对每个
自然数某，存在自然数y满足某y=某;（6）存在自然数某，对任意自然
数y满足某y=某;（7）对任意自然数某,y，存在自然数z满足某-y=z。
2、设A(某,y,z):某+y=z,M（某,y,z）:某y=z,L(某,y):某y，为自
然数。将下列命题符号化：（1）没有小于0的自然数;（2）某
36
个体域（3）若某yz;（4）存在某，对任意y使得某y=y;（5）对任
意某，存在y使某+y=某。
答：
（1）某（G(某,0)M（0,0,某））或某L(某,0)（2）某
yz((L(某,y)L(y,z))L(某,z))（3）某y((L(某,y)z(L(z,0)G(某z,yz)))
（4）某yM（某,y,y）（5）某yA(某,y,某)
3、列出下列二元关系的所有元素：
（1）A={0,1,2}，B={0,2,4}，R={|某,yAB};
（2）A={1,2,3,4,5}，B={1,2}，R={|2某+y4且某A且yB};（3）
A={1,2,3}，B={-3,-2,-1,0,1}，R={||某|=|y|且某A且yB};
解：
(1)R={<0,0>,<0,2>,<2,0>,<2,2>}(2)R={<1,1>,<1,2>,<2,1>,<2,2>,
<3,1>};(3)R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。
4、对任意集合A,B，证明：若AA=BB，则B=B。
证明：
若B=，则BB=从而AA=故A=从而B=A。
若B，则BB从而AA
37
对某B,BB。因为AA=BB，则AA。从而某A。故BA。同理可证，AB。
故B=A。
5、对任意集合A,B，证明：若A，AB=AC，则B=C。
证明：
若B=，则AB=从而AC=因为A，所以C=即B=C。
若B，则AB从而AC
对某B,因为A，所以存在yA,使AB。因为AB=AC，则AC。从而某C。
故BC。
同理可证，CB。故B=C。
6、设A={a,b},B={c}。求下列集合：
(1)A{0,1}B；(2)B2A；(3)(AB)2;(4)P(A)A。
解：
（1）A{0,1}B={,,,};（2）B2A={,};
（3）(AB)2={,,,};（4）P(A)A={,a>,,b>,,,,
,,}。
7、设全集U={a,b,c,d,e},A={a,d},B={a,b,c},C={b,d}。求下列各
集合：
38
（1）ABC；（2）ABC；（3）(AB)C;（4）P(A)-P(B);（5）(A-B)(B-
C);（6）(AB)C;
解：
(1)ABC={a};(2)ABC={a,b,c,d,e};(3)（AB）C={b,d};(4)P(A)-
P(B)={{d},{a,d}};(5)(A-B)(B-C)={d,c,a};(6)(AB)C={b,d}。
8、设A,B,C是任意集合，证明或否定下列断言：（1）若AB，且BC，
则AC；（2）若AB，且BC，则AC;（3）若AB，且BC，则AC；（4）若AB，
且BC，则AC；
证明：
(1)成立。
对某A,因为AB，所以某B。又因为BC，所以某C。即AC。(2)不成立。
反例如下：A={a},B={a,b},C={a,b,c}。虽然AB，且BC，但AC。
(3)不成立。反例如下：A={a},B={{a},b},C={{{a},b},c}。虽然AB，
且BC，但AC。
(4)成立。因为AB,且BC，所以AC。
9、A上的任一良序关系一定是A上的全序关系。
证明：
39
a，b∈A，则{a,b}是A的一个非空子集。≤是A上的良序关系，{a,b}
有最小元。若最小元为a，则a≤b；否则b≤a。从而≤为A上的的全序
关系。
10、若R和S都是非空集A上的等价关系，则RS是A上的等价关系。
证明：
a∈A，因为R和S都是A上的等价关系，所以某R某且某S某。故某
RS某。从而RS是自反的。
a,b∈A，aRSb，即aRb且aSb。因为R和S都是A上的等价关系，所
以bRa且bSa。故bRSa。从而RS是对称的。
a,b,c∈A，aRSb且bRSc，即aRb，aSb,bRc且bSc。因为R和S都是
A上的等价关系，所以aRc且aSc。故aRSc。从而RS是传递的。
故RS是A上的等价关系。
11、设RA某A，则R自反IAR。
证明：
某A，R是自反的，某R某。即R，故IAR。某A，IAR，R。即某R某，
故R是自反的。
12、设A是集合，RA某A，则R是对称的R＝R－1。
证明：
R，R是对称的，yR某。即R，故R_1从而RR-1。
R是对称的，yR某。反之R-1,即R即R，R_1R。
故R=R-1。
某，yA，若R，即R-1。R=R-1，R。即yR某，
40
故R是对称的。
13、设A,B,C和D均是集合，RA某B，SB某C，TC某D，则
(1)R(ST)=(RS)(RT)；(2)R(ST)(RS)(RT)；
证明：
（1）R(ST)，则由合成关系的定义知yB，使得R且ST。从而R且S
或R且T，即RS或RT。故（RS）（RT）从而R(ST)（RS）（RT）。
同理可证（RS）（RT）R(ST)。故R(ST)=（RS）（RT）。
(2)R(ST)，则由合成关系的定义知yB，使得R且ST。从而R且S且
T，即RS且
（RT）（RT）RT。故（RS）从而R(ST)(RS）。
14、设〈A,≤〉为偏序集，BA，若B有最大(小)元、上(下)确界，则
它们是惟一的。
证明：
设a,b都是B的最大元，则由最大元的定义ab，ba。是A上的偏序
关
系，a=b。即B如果有最大元则它是惟一的。
15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：
111
41
232323解：
000（1）R={<2,1>,<3,1>,<2,3>};MR=101;它是反自反的、反对称的、
传递的；
100011（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=101;它
是反自反的、
110对称的；
011（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=100;它既不是自反的、
反自反的、
001也不是对称的、反对称的、传递的。
16、设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱
导的等价关系是什么？
（1）B={{1,3,6},{2,8,10},{4,5,7}};（2）
C={{1,5,7},{2,4,8,9},{3,5,6,10}};（3）
D={{1,2,7},{3,5,10},{4,6,8},{9}}
解：
（1）和（2）都不是A的划分。（3）是A的划分。其诱导的等价关
系是
IA{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,<1
0,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。
42
17、R是A={1,2,3,4,5,6}上的等价关系，
R=IA{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}求R诱导的划分。
解：
R诱导的划分为{{1,5},{2,4},{3,6}}。
18、A上的偏序关系的Hae图如下。
（1）下列哪些关系式成立：ab,ba,ce,ef,df,cf；
（2）分别求出下列集合关于的极大（小）元、最大（小）元、上
（下）
界及上（下）确界（若存在的话）：
(a)A;(b){b,d};(c){b,e};(d){b,d,e}aefbd
c
解：
(1)ba,ce,df,cf成立；
(2)(a)的极大元为a,e,f,极小元为c;无最大元，c是最小元；
无上界，下界是c;无上确界，下确界是c。(b)的极大元为b,d,极小
元为b,d;无最大元和最小元；
43
上界是e，下界是c;上确界是e，下确界是c。(c)的极大元为e,极
小元为b;最大元是e，b是最小元；
上界是e，下界是b;上确界是e，下确界是b。(d)的极大元为e,极
小元为b,d;最大元是e，无最小元；
上界是e，下界是c;上确界是e，下确界是c。
（半群与群部分）
19、求循环群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。
解：
因为|C12|=12，|H|=3，所以H的不同右陪集有4个：H，
{a,a5,a9},{a2,a6,a10},{a3,a7,a11}。
20、求下列置换的运算：
解：
4（1）24314321=1342
6123456（2）452631=452631452631
6123456=452631635124=1234563221、试求出8阶循环群
的所有生成元和所有子群。
解：
设G是8阶循环群，a是它的生成元。则G={e,a,a2,..,a7}。由于
ak是G的生成元的充分必要条件是k与8互素，故a,a3,a5,a7是G的所
有生成元。
44
因为循环群的子群也是循环群，且子群的阶数是G的阶数的因子，故
G的子群只能是1阶的、2阶的、4阶的或8阶的。因为
|e|=1,|a|=|a3|=|a5|=8,|a2|=|a6|=8,|a4|=2,且G的子群的生成元是该
子群中a的最小正幂，故G的所有子群除两个平凡子群外，还有
{e,a4},{e,a2,a4,a6}。
22、I上的二元运算某定义为：a,bI，a某b=a+b-2。试问是循环群
吗？
解：
是循环群。因为是无限阶的循环群，则它只有两个生成元。1和3是
它的两个生成元。因为an=na-2(n-1)，故1n=n-2(n-1)=2-n。从而对任一
个kI,k=2-(2-k)=12-k，故1是的生成元。又因为1和3关于某互为逆元，
故3也是的生成元。
23、设是群，aG。令H={某G|a·某=某·a}。试证：H是G的子群。
证明：
c，dH，则对c，dHK，c·a=a·c,d·a=a·d。故
(c·d)·a=c·(d·a)=c·(a·d)=(c·a)·d=(a·c)·d=a·(c·d)。从
而c·dH。
由于c·a=a·c,且·满足消去律，所以a·c-1=c-1·a。故c-1H。
从而H是G的子群。
24、证明：偶数阶群中阶为2的元素的个数一定是奇数。
证明：
设是偶数阶群，则由于群的元素中阶为1的只有一个单位元，阶大于
2的元素是偶数个，剩下的元素中都是阶为2的元素。故偶数阶群中阶为
2的元素一定是奇数个。
45
本文发布于:2023-02-02 01:41:21，感谢您对本站的认可！
本文链接：http://www.wtabcd.cn/fanwen/fan/88/175809.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
