, (}},贝i]P(A) nP(B)= 。14. 给定个体域为整数域，若F(x):表示x是偶数，G(x):表示x是奇数；那么
(3X)F(X)A(3X)G(X)：^一个 语句；而Qx) (F(X)AG(X))是一个
______ 语句O
15. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度结点， 该图有 个顶点。
16. 设T是一棵完全二元树，有15个结点，其中8个树叶结点，则T分枝结点 数是 , T的所有结点度数之和是 o
二、作图题(本大题共8分，共1小题，每小题8分) 求下图所示带权图的最小生成树：
三、简答题（本大题共4分，共1小题，每小题4分） 判断下图是否欧拉图，若是，找出一个欧拉回路。
四、分析题（本大题共10分，共2小题，每小题5分）
1.设I是整数集，〈，＞,=,-'-f。是I上的二元关系，分别表示小 于、大于、等于、小于等于、大于等于，不等于。那么这些关系会满足什么性 质？试填写下表： 3 V 自反。 反自反。 对称3 反对称- 传递。 3 2 3 2 2 2 3 3 3 3 =3 a 3 2 2 ° 2 3 3 2.设集合A={1,2,3,4,5}上的二元关系R如下图，请判断R是否是A上的等价关系, 若是，
请说明理由并写出各元素的等价类，若不是，请说明理由。
五、证明题(本大题共30分，共5小题，每小题6分) 1. 设G为群，证明e为G中的唯一幕等元。
2. 在命题逻辑中构造下面推理的证明。前提：p-s, q-r, ］〕r, pVq结 论：s
3. 案件涉及甲、乙、丙、丁四个，根据已有的线索，已知：i.若甲、乙均未 作案，则丙、丁也未作案ii.若丙、丁未作案，则甲、乙也未作案iii.若甲 与乙同时作案，则丙与丁有一人且只有一人作案iv.若乙与丙同时作案，则甲 与丁同时作案或同时未作
案。办案人员由此的出结论：甲是作案者。这个结论 是否正确，为什么
4. 设fl, f2都是从代数系统〈&★＞到代数系统〈B,*〉的同态。设g是从A到B 的一个映射，使得对任意aGA,都有g(a)= fl (a)* f2 (a)。证明：如果是 一个可交换半群，那麽g是一个由代数系统〈A, ★〉到代数系统〈B, *〉的同态。
5. 设R是集合A上的自反、传递的二元关系，又设T也是A上的二元关系，且 满足：＜x, y＞《TU＞〈x, y〉GR ' ■ ＜y, x＞GR,求证：T是A上的等价关系。
答案:
一、填空题(48分，共16题，每小题3分)
1.
参： 永真式 解题方案：
答案正确得满分，错误不得分
2.
参： G是连通m_n+l 解题方案： 评分标准：
3.
参：
、每条边；每个顶点 解题方案： 评分标准：
4.
参：
(1) PAQ (2) P—]Q (3)P-»]Q 解题方案：
评分标准：
5.
参：
8
解题方案： 评分标准：
6.
参：
可满足式 永假式(或矛盾式) 解题方案： 评分标准：
答案正确得满分，错误不得分
7.
参：
1
解题方案:
8.
参：
(1)
4 (2) 4
解题方案： 评分标准：
9.
参：
_24, 36_ 1 无 1
解题方案： 评分标准：
10.
参： IPA(QVR) 解题方案： 评分标准：
11.
参：
8
解题方案： 评分标准：
12.
参：
{<2, 12>, <3,8>, <3, 12>, <0, 14>}
解题方案： 评分标准：
13.
参： 解题方案： 评分标准：
14.
参： 永真；永假 解题方案： 评分标准：
15.
参：
4
解题方案： 评分标准：
16.
参：
7, 28
解题方案： 评分标准：
二、作图题（8分，共1题，每小题8分）
0.
参：
解题方案: 评分标准:
三、简答题（4分，共1题，每小题4分）
0.
参：
是；欧拉回路为：
v 1 rvO —>v5—>vl TV4
解题方案： 评分标准：
TV2TV3TV4 TV2 —>vl
四、分析题（IO分，共2题，每小题5分）
1.
参: 自反。 反自反3 对称2 反对称G 传递。 V £ •山 山 =2 也 X'' V ° £ V a •\\L 解题方案:
评分标准：
2.
参：
R是A上的等价关系。（因为同时满足自反性、对称性、传递性）
[1]K=[2]R=[3]R=[1]R={1,2,3}
解题方案：
R是A上的等价关系。（因为同时满足自反性、对称性、传递性）
[1]R=[2]R=[3]R=[1]R={1, 2, 3}
评分标准：
5
5
五、证明题（30分，共5题，每小题6分）
1.
参：
设e（）6G也是幕等元，则e0=eo=e0e,由消去率可知e0=eo
解题方案： 评分标准:
2
2.
参：
证明：(1)匚I P。
(2) Tr P・ (3) 〕q (4) pVq
T(l)(2> P。
(5) p T(3)(4)『 (6) p—s P*J (7) s T(5)(6)。
解题方案： 评分标准：
3.
参：
对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 则办案人员的推理可形式化如下：
前提(1 ) ( 1 pl 人 1 p2)—( 1 p3 A p4)
(2) ( ] p3 △] p4)—( ] pl △] p2)
(3) (pl A p2)—(p3 A! p4) V ( 1 p3 A p4) (4) (p2 A p3)—(pl A p4) v ( 1 pl A! p4) 结论：pl
由于：((]pl 人]p2)—( 1 p3 A p4) ) A ( ( ] p3 △] p4)—( ] pl △] p2)) A ( (pl A p2)一'(p3 △] p4) v ( 1 p3 A p4) ) A ((p2 A p3)—>(pl A p4) v ( ] pl △] p4) ) —pl
上金不是永真式，如取pl=0,p2=l,p3=0,p4=l时，上式的真值为假。 故pl不是前提(1)( 2 ) ( 3 ) ( 4 )的有效结论。
即甲是作案者的结论是不正确的。
解题方案：
对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 则办案人员的推理可形式化如下：
前提(1 ) ( 1 pl 人1 p2)—( 1 p3 A p4)
(2) ( ] p3 △] p4)—( ] pl △] p2)
(3) (pl A p2)—(p3 △] p4) v ( 1 p3 A p4) (4) (p2 A p3)—(pl A p4) v ( 1 pl A! p4) 结论：pl
由于：((]pl 人 1 p2)—( 1 p3 A p4) ) A ( ( ] p3 △] p4)—( ] pl △] P2))
A ( (pl A p2)—>(p3 A! p4) v ( 1 p3 A p4) ) A
((p2 A p3)—(pl A p4) v ( 1 pl A! p4) ) —pl
上式不是永真式，如取pl=0,p2=l,p3=0,p4=l时，上式的真值为假。 故pl不是前提(1)( 2 ) ( 3 ) ( 4 )的有效结论。
即甲是作案者的结论是不正确的。 评分标准：
111112 111 4.
参：
因为对于任意的 a, bGA,都有 g(a^b)= fl(a*b)* f2 (a^b) = fl (a)* fl (b)
* f2 (a) * f2 (b) =g(a) *g(b)所以，g 是由到的同态。
解题方案： 评分标准：
5.
参： 证明：(1)自反性。
由于R是A上的自反关系，则对于A集合上的所有元素X,有丘R,因为： c R A £ R 有：UT,故T是 A上的自反关系。“(2) 对称性“
对于A上的元素％x，若eT,则有：〈豪勺盗〉WR, “ 由于：FRA 丘R。£RA eRo eT” 所以T是A上的对称关系。\"(3) 传递性“
对于A上的元素耘以，若GT,并且勺藻〉丘匚有一 w R △ 丘 R 并且 u R △ 丘 因为R是A上的传递关系，有冬y>eRA勺思〉eRn〈旧〉eR“并且 e RA U R^* 仁 2 v^^FvW* 由 RA R^> vwvw-因此由eT,并且eT=>£T,故T是A上传递关系。。 综上所述，T满足自反、对称、传递性，故T是等价关系° “解题方案： 评分标准:
