离散数学模拟试题讲解.doc

(完整word版)离散数学模拟试题讲解
离散数学模拟试题Ⅰ
一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分
1．设，下面哪个命题为假（ A ）。
A、； B、；
C、； D、。
2．设，则B－A是（ C ）。
A、； B、； C、； D、。
3．右图描述的偏序集中，子集的上界为 （ B ）。
A、b，c； B、a，b； C、b； D、a，b，c。
4．设和都是X上的双射函数，则为（ C ）。
A、； B、； C、； D、。
5．下面集合（ B ）关于减法运算是封闭的。
A、N ； B、； C、； D、。
6．具有如下定义的代数系统，（ D ）不构成群。
A、G={1，10}，*是模11乘 ； B、G={1，3，4，5，9}，*是模11乘 ；
C、G=Q（有理数集），*是普通加法； D、G=Q（有理数集），*是普通乘法。
7．设，*为普通乘法。则代数系统的幺元为（ B）。
A、不存在 ； B、； C、； D、。
8．下面集合（ C ）关于整除关系构成格。
A、{2，3，6，12，24，36} ； B、{1，2，3，4，6，8，12} ；
C、{1，2，3，5，6，15，30} ； D、{3，6，9，12}。
9．设，
，则有向图
是（C ）。
A、强连通的 ； B、单向连通的 ； C、弱连通的 ； D、不连通的。
10．下面那一个图是欧拉图（ A ）。

11．在任何图中必定有偶数个（ C）。
A、度数为偶数的结点 ； B、入度为奇数的结点 ；
C、度数为奇数的结点 ； D、出度为奇数的结点 。
12．含有3个命题变元的具有不同真值的命题公式的个数为（ C ）。
A、； B、； C、； D、。
13．下列集合中哪个是最小联结词集（ A ）。
A、； B、； C、； D、。
14．下面哪个命题公式是重言式（ B ）。
A、； B、；
C、； D、。
15．在谓词演算中，下列各式哪个是正确的（ A ）。
A、； B、；
C、； D、。
二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。
3
1
2
1、设A＝{1,2,3}，则右图所示A上的关系具有（ 2）4)5) ）。
1).自反性 2).反自反性 3).对称性
4).反对称性 5).传递性
2、下列语句是命题的有（ 1）3) ）。
1). 明年中秋节的晚上是晴天； 2).；
3). 当且仅当x和y都大于0； 4).我正在说谎。
3、A，B为二合式公式，且，则（ 1）2)3)4)5) ）。
1).为重言式； 2).；3).；
4).； 5).为重言式。
4、右图所示的图一定不是（ 1）2)3)5) ）。
1).平面图 2).二部图 3).欧拉图
4).哈密而顿图 5).树
5、设R和S是集合A上的任意关系，下列命题不成立（ 2）3)4) ）。
1).若R和S是自反的，则RS也是自反的。
2).若R和S是反自反的，则RS也是反自反的。
3).若R和S是对称的，则RS也是对称的。
4).若R和S是传递的，则RS也是传递的
三、填空题（本大题共5小题，每题2分，共10分）
1、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为（1）
～P→Q或～Q→P ；“虽然你努力了，但还是失败了”的翻译为（2）
P∧Q 。
2、设A={2，3，4，5，6}上的二元关系，则
R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>, <4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}
（枚举法）。
R的关系矩阵MR=

*
a b c
a
b
c
a b c
b b c
c c b
3、设代数系统<A，*>，其中A={a，b，c},
则幺元是 （1）a ；是否有幂等性
（2）F 。

4、设A={1，2，3}，则A上既不是对称的又不是反对称的关系
R= {<1,2>,<1,3>,<2,1>} ；A上既是对称的又是反对称的关系
R= {<1,1>,<2,2>,<3,3>} 。
5、n个结点的无向完全图Kn的边数为
（1）n(n－1)/2 ，欧拉图的充要条件是
图中无奇度结点且连通 。
四、演算题（本大题共5小题，每题7分，共35分 ）
1、设A={1，2}，A上所有函数的集合记为AA, 是函数的复合运算，试给出AA上运算的运算表，并指出AA中是否有幺元，哪些元素有逆元。
解：

幺元为，、有逆元
2、设是布尔代数上的一个布尔表达式，试写出其主析取范式和主合取范式。
解：函数表为：

0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0

主析取范式：

主合取范式：

3、如右图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。
解： 用克鲁斯克尔（Kruskal）算法求产生的最优树。算法为：

结果如图：

树权C(T)=23+1+4+9+3+17=57（万元）即为总造价。
4、已知有如右图的偏序关系，求出其子集A={b,c,d,e}的
极大元、极小元、最大元、最小元、最小上界和最大下界。
解：极大元：e
极小元：b,d
最大元：e
最小元：无
最小上界：e
最大下界：a
5、设，A上的关系 ，求出
。
解：
，
，
，

五、证明题（本大题共3小题，每题10分，共30分 ）
1、证明：(P®(Q®S))∧(Ø R∨P)∧QÞR®S
证：（1）R 附加前提
（2）ØR∨P P
（3）P T(1)(2)，I
（4）P®(Q®S) P
（5）Q®S T(3)(4)，I
（6）Q P
（7）S T(5)(6)，I
（8）R®S CP
2、如果集合A上的关系R和S是自反的、对称的和传递的，
证明：是A上的等价关系。
证明：（1）
自反。
（2），若，则由R ，S对称，所以，，所以 对称。
（3），若则
由R ，S传递性知，从而
所以，传递。
综上所述，是A上的等价关系。

3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。
证：由题设，在无向图G中只有两个奇数度结点，
因此，在这两个奇数度结点之间作一条边，则在该图中所有的结点的度数都是偶数，由欧拉图的充要条件，在图中必然存在一条欧拉回路，将此边从欧拉回路中删除，在这两个奇数度结点间还存在一条欧拉道路，所以，这两个结点一定连通。

离散数学模拟试题Ⅱ
一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1、设，则 有（ D ）个元素。
A. 3； B． 6； C． 7； D． 8 。
2、设，定义上的等价关系
则由R产生的上一个划分共有（ B ）个分块。
A．4； B．5； C．6； D．9 。
解释：
=
=，=，=
=
3、设，S上关系R的关系图如右图所示，则R具有（ D ）性质。
A．自反性、对称性、传递性； B．反自反性、反对称性；
C．反自反性、反对称性、传递性； D．自反性 。
4、设 为普通加法和乘法，则（ A ）是域。
A． B．
C． D．= N 。
5、下面偏序集（ B ）能构成格。

6、在如图所示的有向图中，从V1到V4长度为3 的道路有
（ B ）条。
A．1； B．2； C．3； D．4 。
7、在如下各图中（ B ）是欧拉图。

8、“人总是要死的”谓词公式表示为（ C ）。（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。
A. ； B.
C.； D.
9、公式的解释I为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A的真值为（ A ）。
A. 1； B. 0； C. 可满足式； D. 无法判定。
10、下列等价关系正确的是（ B ）。
A.；
B.；
C.；
D. 。
11、下列推理步骤错在（ B ）。
① P
② US①
③ P
④ ES③
⑤ T②④I
⑥ EG⑤
A. ②； B. ④； C. ⑤； D. ⑥
12、下列命题公式为重言式的是（ A ）。
A．p→ (p∨q) B．(p∨┐p)→q C．q∧┐q D．p→┐q
13、下列语句中是真命题的是（　C　）。
A．我正在说谎 B．严禁吸烟
C．如果1+2=5，那么雪是黑的 D． 如果1+2=3，那么雪是黑的
14、设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（ D）。
A．┐p∧q B．┐p→q C．┐p→┐q D．p→┐q
15、设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（ D ） 。
A．自反关系； B．反自反关系； C．对称关系； D．传递关系；
二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。
1、下面在集合论和逻辑学中正确的公式有( 1)2）4） )。
1) P∧～PÞR∧Q； 2) R®QÞPÚ～P； 3) ；
4) A⊕B=A⊕CÞB=C；
2、设有如下命题
A)如果地上有水，则天上下雨
B)如果天上下雨，则地上有水
C)如果地上没有水，则天上不下雨
D)如果天上不下雨，则地上没有水
哪些命题等价的（ 2）4） ）。
1）. A)与B)等价 ； 2）. A)与D)等价； 3). A)与C)等价 ；
4）. B)与C)等价
3、G={0,1,2,…,n}，n∈N，定义为模n加法，即xy=(x+y) mod n，则代数系统(G，)( 1)2） )。
1). 是循环群 2). 是交换群 3). 是半群但不是群 4). 是无限群
4、设G是一个35阶群，a∈G，则a的周期不可能是（ 1）2）3）4） ）。
1).1 2).2 3).3 4).4 5).5
5、下列哈斯图中，是格的有（ 3）4） ）。
1). 2). 3). 4). 5).

三、填空题（本大题共5小题，每题2分，共10分）
1．设，，请在下列每对集合中填入适当的符号：∈ , (2) Í。
2．设，N为自然数集，
若，则是双 射的；若，则是 （2） 满 射的。
3．设图G = < V ，E >中有7个结点，各结点的次数分别为2，4，4，6，5，5，
2，则G中有（1） 14 条边，根据 （2） 。
4．两个重言式的析取是 （1）重言式，一个重言式和一个矛盾式的合是 （2）矛盾式 。
5．设个体域为自然数集，命题“不存在最大自然数”符号化为
。
四、演算题（本大题共5小题，每题7分，共35分 ）
1、设集合A＝{a，b，c}，A上的关系
＝{<a，a>，<a，b>，<a，c>，<b，b>，<b，c>，<c，c>}，
＝{<a，a>，<a，b>，<b，a>，<b，b>， <c，c>}。
计算
解：
2、有向图G如右图所示，试求：
(1)求G的邻接矩阵A。
(2)求出可达矩阵P。
(3)所有强分图。
解 (1)求G的邻接矩阵为：

(2) 可达矩阵为
。
(3)因为∧＝，
所以{}，{，，}构成G的强分图。

3、右图给出的赋权图表示五个城市及对应两城镇间公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。
解：此问题的最优设计方案即要求该图的最小生成树，
由破圈法或避圈法得最小生成树为：
其权数为1+1+3+4 = 9 。

4、已知有如图的偏序关系，并求出其子集A={b,c,d,e}的极大元、极小元、最大元、最小元、最小上界和最大下界。
解：极大元：e
极小元：b,d
最大元：e
最小元：无
最小上界：e
最大下界：a

5、已知，为模7乘法。试说明是否构成群？是否为循环群？若是，生成元是什么？
解：因为G对于是封闭的，同时满足结合律，1是幺元，3和5，2和4，6和6互为逆元，所以构成群。
是循环群，生成元是（3）。
五、证明题（本大题共3小题，每题10分，共30分 ）
1、"x(P(x)∨Q(x))，"xØP(x)Þ$x Q(x)
证明：
(1)"xØP(x) P
(2)ØP(c) T(1)，US
(3)"x(P(x)∨Q(x)) P
(4)P(c)∨Q(c) T(3)，US
(5)Q(c) T(2)(4)，I
(6)$x Q(x) T(5)，EG
2、p={A1，A2，…，An}是集合A的一个划分，定义R={<a，b>|a、b∈Ai，i=1，2，…，n}，则R是A上的等价关系。
证明见教材
3、

证明：
[幺] ，
即
[闭] ，由于+，·在R封闭。所以
即*在R上封闭。
[结]

因此 ， 〈R，*〉是含幺半群。

离散数学模拟试题Ⅲ
一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分
1． 下列命题公式是永真式的是（ B ）。
A．（P∧～P）↔Q B．（～（P→Q）∧Q）→Q
C．（P→Q）∨Q D．（P∨P）∧（P→～P）
2． 命题公式A不存在主合取范式，则A是 （C ）
A．矛盾式 B．可满足式 C ．永真式 D．都不对
3． 谓词公式（"x）P（X）→（$x）P（X） 是（D ）
A．可满足式 B．矛盾式 C．无法判别 D．永真式
4． 公式（"x）（$y）（P（x,y）∧Q（z））→R（x） 中的x （C ）
A．仅是约束变元 B．仅是自由变元
C．既是约束变元又是自由变元 D．既不是约束变元也不是自由变元
5． 设A、B、C是集合，下列四个命题中，( D )在任何情况下都是正确的。
A.若AB且B∈C，则A∈C B. 若AB且B∈C，则AC
C.若A∈B且BC，则AC D.若A∈B且BC，则A∈C
6． 下面的表达哪个不正确 （ A ）
A．{a}Í{{a}} B．{a}∈{{a}} C．{a}Í{a，{a}} D．{a}∈{a，{a}}
7． 若集合A中共有n个元素，那么A上不同二元关系的个数为 （ B ）
A． B． C． D．都不对
8． 下列判断正确的是 （ C ）
A．若R，S是自反的，则R-S是自反的
B．若R，S是对称的，则R○S是对称的
C．若R，S是传递的，则R∩ S是传递的
D．若R，S是传递的，则R ∪S是传递的
9． 设R，S是非空集合上的等价关系，则R∪S是（ C ）
A．一定具有自反性，但不一定保持对称性
B．一定具有对称性，但不一定保持自反性
C．一定具有自反性和对称性
D．是等价关系
10． 在5个元素的集合上可以定义的单射数目为 （ D ）
A．5 B．10 C．60 D．120
11． 设函数f：X→Y；X，Y 是有限集合， f是单射，那么下列关系一定不成立的是 （ B ）
A．|X|=|Y| B．|X|﹥|Y| C．|X|﹤|Y| D．X∈Y
12． 平面非连通图G，n-m+f 的值为 （ C ）
A．2 B．ω（G） C．ω（G）+1 D．3
13． 若一棵树G（n，n-1） 只有两个叶节点，则 （ B ）不正确
A．不包含点度大于等于3的枝点 B．节点总度数大于等于4
C．最少包含2个节点 D．节点总度数=2+2（n-2）
14． 设10阶简单连通图有32条边，则最少要去掉 （ D ）条边才能使其成为
平面图
A．10 B．12 C．32 D．8
15.下列代数系统<，*>中，哪个是群？（ D ）
A. ，*是模7加法 B. （有理数集合），*是一般乘法
C. （整数集合），*是一般减法 D. ，*是模11乘法
二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。
3
1
2
1. 设A＝{1,2,3}，则右图所示A上的关系具有（BDE ）。
1).自反性 2).反自反性 3).对称性
4).反对称性 5).传递性
2. 设A＝{a}，B＝{a，{a}}，则（ABD）。
1).A∈B 2).AB 3).{A}∈B
4).{A}B 5).{A}{B}
3. 下列命题公式中，（ CD ）在解释{～P，Q，～R }下为真。
1).(P∧Q)→R 2).(P∨Q)→R 3).(RQ)→P
4).P→(Q→R) 5). ～(P∧Q)→R
4. 树是（ CDE ）。
1). 欧拉图 2). 哈密顿图 3). 二部图
4). 平面图 5). 连通图
5. 在一个环（R，+，.）中，以下命题不一定成立的有（DE）。
1) a.0=0 2) a.(-b)=-(a.b) 3) -a.(-b)=a.b
4) a.b=0 ，则a=0或b=0 5) a.b=a.c ，则b=c
三、填空题（本大题共5小题，每题2分，共10分）
1．设，，请在下列每对集合中填入适当的符号：（1） ∈ , (2) Í 。
2．设，N为自然数集，
若，则是(1) 双 射的，
若，则是(2) 满 射的。
3．设图G = < V ，E >中有7个结点，各结点的度数分别为2，4，4，6，5，5，2，
则G中有 （1） 14 条边，根据 （2） 握手定理 。
4．两个重言式的析取是（1） 重言式 ，一个重言式和一个矛盾式的合取是 （2）矛盾式 。
5．设个体域为自然数集，命题“不存在最大自然数”符号化为
（1）"x$y(y＞x) 。
四、演算题（本大题共5小题，每题7分，共35分 ）
1．写出（P∧～R）∨（S∧P）的主析取范式。
解：（P∧～R）∨（S∧P）
= （P∧～R∧S）∨（P∧～R∧～S）∨（P∧R∧S）
2．把下面的命题符号化成逻辑公式：
每个旅客要么坐硬座要么坐软座，每个旅客当且仅当富裕时坐软座，并非每个旅客都富裕。因此，有些旅客坐硬座。
解： 设 P（x）：x为旅客；Q（x）：坐硬座；R（x）：坐软座；S（x）：旅客富有
（"x）（P（x）→（Q（x）∨R（x）））∧（"x）（P（x）→（S（x）↔Q（x）））∧（$x）（P（x）∧～S（x））=>（$x）（P（x）∧R（x））
V1
V2
V3
V4

3．利用矩阵方法求如图所示的所有强分图：(写出运算过程)。
解：三个强分图顶点集合为：{V1} {V4} {V2，V3}

4．将置换 表示成循环之积，并求其逆置换。
解：л=（1 5 2）（3 6 4）
л°л-1 =（1）
л-1 =（1 2 5）（3 4 6）

5．无向图G有21条边，12个3度顶点，其余顶点的度数均为2，求G的阶数n（写出求解过程）。
解： ∵ 2m = ∑d（v）
2x21 = 12x3 + （n-12）x 2
∴ n = 15

五、证明题（本大题共3小题，每题10分，共30分 ）
1．证明〈{a+b| a，b∈I}，+，×〉为环（+，×为普通加法和乘法）。
证明：（1）<M，+>为交换群
a）封闭性
b）0为幺元
c）a+b√2 与 –a-b√2互为逆元
d）+ 可交换
（2）<M，x>为半群
（3）分配律成立

2．证明：简单连通无向图G的任何一条边都是G的某一棵生成树的边。
证明：反证法，假设$e ∈G（n，m），不是任何一棵生成树的边，那么，任选一棵生成数T（n，n-1），增加边e，可以在T+{e}中形成一个圈，然后，删掉T+{e}中圈的任一条非e的边，使的删边子图成为一棵树，并且，包含e。与假设矛盾。原命题结论成立。

3．证明P→（Q→S）是{P→（Q→R），R→（Q→S）}的逻辑结果。

离散数学模拟试题Ⅳ
一、单项选择题（本大题共15小题，每题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分
1、结点数为奇数且所有结点的度数也为奇数的连通图必定是（ D ）。
A．欧拉图 B．汉密尔顿图 C．非平面图 D．不存在的
2、平面图(如下)的三个面的次数分别是（ A ）。

A．11，3，4 B．11，3，5 C．12，3，6 D．10，4，3 。
3、下列式子中( D )是永真的。
A.(PÚQ)®(P∧Q)； B.(P®Q)∧(PÚQ)；
C.(P®Q)®(P«Q)； D.(P«Q)®(P®Q)
4、设R是A上的二元关系，且R°R=R，则可以肯定R应是( B )。
A.自反关系； B.传递关系； C.反对称关系； D.等价关系
5、永真命题公式( A )。
A.只存在主析取范式； B.只存在主合取范式；
C.既存在主析取范式也存在主合取范式； D.都不对
6、设集合A={1，2，3，4}，下列A上的关系构成A到A的映射的是（ D ）。
A. f1={(2,1),(2,4),(3,4),(4,1)}
B. f2={(4,4),(3,1),(1,2),(4,2)}
C. f3={(1,1),(2,1),(1,2),(3,4)}
D. f4={(1,4),(2,1),(3,4),(4,1)}
7、设R是A上的二元关系,，且R°RUR=R，则( C )。
A. r(R)=R； B.S( R )=R； C . t( R )=R； D . R=IA 。
8、下面关于集合基数正确的说法是( D )。
A.一个集合不可能和它的真子集等势； B.实数集合的基数最大；
C.没有最小的基数； D.素数集合与有理数集合等势
9、在自然数集上，下列哪种运算是可结合的？（ B ）
A. B.
C. D.
10、 下列代数系统<，*>中，哪个是群？（ D ）
A. ，*是模7加法 B. （有理数集合），*是一般乘法
C. （整数集合），*是一般减法 D. ，*是模11乘法
11、 下面哪个集合关于指定的运算构成环？（ C ）
A. ，关于数的加法和乘法；
B.阶实数矩阵，关于矩阵的加法和乘法；
C. ，关于数的加法和乘法；
D. ，关于矩阵的加法和乘法；
12、 在代数系统中，整环和域的关系为（ A ）。
A. 域一定是整环 B.域不一定是整环
C. 整环一定是域 D. 域一定不是整环
13、 是自然数集，是小于等于关系，则是（ C ）。
A. 有界格 ； B.有补格； C. 分配格； D. 有补分配格
a
b
c
d
e
f
g
14、右图给出的哈斯图表示的格中哪个元素无补元？（ B ）
A. ； B. ； C. ； D.
15、 给定下列序列，可构成无向简单图的结点度数序列的是（ D ）。
A.（1，1，2，2，3） B.（1，3，4，4，5）
C.（0，1，3，3，3） D.（1，1，2，2，2）
二、多项选择题（本大题共5小题，每题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。
1.设A＝{1,2,3}，则右图所示A上的关系具有（ BDE ）。
3
1
2
1).自反性 2).反自反性 3).对称性
4).反对称性 5).传递性
2.设A＝{a}，B＝{a，{a}}，则（ABD）。
1).A∈B 2).AB 3).{A}∈B
4).{A}B 5).{A}{B}
3.下列命题公式中，（ ACD）在解释{～P，Q，～R }下为真。
1).(P∧Q)→R 2).(P∨Q)→R 3).(RQ)→P
4).P→(Q→R) 5). ～(P∧Q)→R
4.树是（ CDE ）。
1). 欧拉图 2). 哈密顿图 3). 二部图
4). 平面图 5). 连通图
5.在一个环（R，+，.）中，以下命题不一定成立的有（DE）。
1) a.0=0 2) a.(-b)=-(a.b) 3) -a.(-b)=a.b
4) a.b=0 ，则a=0或b=0 5) a.b=a.c ，则b=c
三、填空题（本大题共5小题，每空1分，共10分）
1．设S为非空有限集，代数系统中幺元为（1）Æ ，零元为（2） S 。
2．设P、Q为两个命题，其De-Morden律可表示为 （1） 。
3．当时，群只能有 （1）2,4 阶非平凡子群，不能有（2）3，5，7 阶子群，平凡子群为（3） 。
4．设，定义A上的二元运算为普通乘法、除法和加法，则代数系统<A,*>中运算*关于（1） 乘法 运算具有封闭性。
5．设集合S={α，β，γ，δ，ζ}，S上的运算*定义为
*
α
β
γ
δ
ζ
α
α
β
γ
δ
ζ
β
β
δ
α
γ
δ
γ
γ
α
β
α
β
δ
δ
α
γ
δ
γ
ζ
ζ
δ
α
γ
ζ

则代数系统<S，*>中幺元是 （1）a ，β左逆元是 （2）d，g ，
无左逆元的元素是 （3） z 。
四、演算题（本大题共5小题，每题7分，共35分 ）
1、用等值演算法，求P∨(Q∧R)的主析取范式。

2、设A={1，2，3}，给定A上二元关系R={<1，1>，<1，2>，<2，3>}，
求r(R)，s(R)和t(R)。
解：r（R）={<1，1>，<1，2>，<2，3>，<2，2>，<3，3>}
s（R）={<1，1>，<1，2>，<2，3>，<2，1>，<3，2>}
t（R）={<1，1>，<1，2>，<2，3>，<1，3>}

3、设树G中有6个结点度数为2，5个结点度数为3，4个结点度数为6，
其余结点度数均为1，试求G中的总结点数目。
解：设一度结点的个数为L，总的结点数为n，树的边数为m，
由握手定理：6×2+5×3+4×6+L=2m
由树的基本性质：m=n-1
Þ 51+L=2(n-1) ①
由题意 15+L=n ②
由①②解得 n=38

4、群<S,*>的运算如下表所示，试求<S,*>的单位元、每个元素的逆元，如果
存在生成元，请计算所有的生成元。
*
x1
x2
x3
x4
x1
x1
x2
x3
x4
x2
x2
x3
x4
x1
x3
x3
x4
x1
x2
x4
x4
x1
x2
x3

解：单位元为x1 ，x2和x4互为逆元，x3和自身互为逆元，
生成元为x2和x4
5、右图为一个有向图，用邻接矩阵计算该图中长度为3的所有道路和回路总数。
解：
长度为3的道路总数为20条；
其中长度为3的回路总数为4条。

五、证明题（本大题共3小题，每题10分，共30分 ）
1．(P®(Q®S))∧(ØR∨P)∧QÞR®S。
证明：（1）R 附加前提
（2）ØR∨P P
（3）P T(1)(2)，I
（4）P®(Q®S) P
（5）Q®S T(3)(4)，I
（6）Q P
（7）S T(5)(6)，I
（8）R®S CP

2．证明整数集I上的模m同余关系R={<x，y>|xºy(mod m)}是等价关系。其中，xºy(mod m)的含义是x-y可以被m整除。
3．若有n个人，每个人都恰有三个朋友，则n必为偶数。
证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图
。因为每个人恰有三个朋友，所以，，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是偶数。

37