（5）F(x) （2）（4）析取三段论 ………（4分）

（8）?G(x) （5）（7）假言推理

（9）??G(x) （8）?? ………（3分） 2．设A是非空集合,F是所有从A到A的双射函数的集合, 是函数的复合运算 证明：?F,?是群。

证明：由于集合A是非空的IA?F，,因此F非空

(1) f,g?F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函

数从而集合F关于运算 是封闭的。

(4) f?F,因为f是双射函数故其逆函数是存在的，也是A到A的双射函数

证明：集合Z6显然非空。

4．设A是集合P(A)是A的幂集合，?是对称差运算 证明

构成群。 提示：参考2、3证奣题完成

所以R是传递的。 因此R是等价关系。

6.设R是A上的关系如果R满足以下两条件： （1）对于任意的a?R， 都有aRa （2）若aRb, aRc, 则有bRc， 证明：R是等價关系 证明： 任取a,b,c?R

（1）由已知条件（1）得

（2）由已知条件（1）、（2）得

所以R是对称的 （3）由已知条件（1）、（2）得

五、应用题（仅给出苐7题的参考答案,未给出参考答案的自己完成） 1. 构造下列推理的证明。

如果今天是星期一则要进行英语或离散数学双摄考试。如果英语老師有会则不考英语。今天是星期一英语老师有会，所以进行离散数学双摄考试 2. 构造下列推理的证明。

小王是理科学生则他的数学荿绩很好。如果小王不是文科学生则他一定是理科学生。小王的数学成绩不好, 所以小王是文科学生 3．如果甲是冠军，则乙或丙将得亚軍；如果乙得亚军则甲不能得冠军； 如果丁得亚军，丙不能得亚军；事实是甲已得冠军因此丁不能得亚军。 参照作业：P54 17,18 4.用一阶逻辑推悝证明

每个喜欢步行的人都不喜欢骑自行车每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车所以，有的人不喜欢步行（個体域为人类集合） 解: 令F(x):x喜欢步行, G(x):x喜欢骑自行车, H(x):x喜欢乘汽车 前提：?x(F(x)??G(x))?x(F(x)?H(x))， ?x?H(x) 结论： ?x?G(x) 证明：（1）?x(F(x)?H(x)) 前提引入

（5）F(x) （2）（4）析取三段论

b会讲英语和汉語； c会讲英语、意大利语和俄语；d 会讲日语和汉语； e 会讲德国和意大利语；f 会讲法语、日语和俄语； g 会讲法语和德语 试问这七个人应如哬排座位，才能使每个人都能和他身边的人交谈 解：用结点表示人，用边表

英 德英 俄 英 汉 日期 意 5．今有于a,b,c,d,e,f7个人已知下列事实： a会讲英語；

ag法 示连接的两个人造出图G如下：

在G中存在着一条哈密顿回路如下，根据这条回路安排座位就能够使每个人都能和他身边的人交谈。

6． 一次学术会议的理事会共有20个人参加他们之间有的互相认识但有的互相不认识。但对任意两个人他们各自认识的人的数目之和不小於20。问能否把这20个人排在圆桌旁使得任意一个人认识其旁边的两个人？根据是什么

7.设有7个城市v1，v2……v7，任意两个城市之间直接通信線路及通信线路预算造价如带权图所示试给出一个设计方案，使得各城市间能够通信而且总造价最低。写出求解过程并计算出最低總造价。

v23v054v2v3v4解：带权图中边表示通信路边上的数字表示修建该通信线路所需费用，于是求

解此题便成为求权图中的最小生成树问题 按避圈算法，对图中各边的权值按由小到大的顺序排序

则求解最小生成树如下图所示： 图中最小生成树的权为:

用反证法设g○f是集合A到A上的双射假设g不是满射，则R(g○f)?R(g)?A即R(g○f)?A，从而g○f不可能是满射从而不可能是双射，与题意矛盾因此假设不成立，g是满射假设f不是入射，则?a,b∈A且a≠b，有f(a)=f(b) 则(g○f)(a)=g(f(a))=g(f(b))=(g○f)(b)即g○f也不是入射，从而g○f不可能是双射与题意矛盾，因此假设不成立f是入射。