1、- 1 -天津理工大学离散数学第一章检测题答案一、填空题（每空 2 分，共 30 分）1 2 3， ， ， ， ， ， 。PQP c 4 ，()()()RRPQ()()RPQR5 6 7()()PQS 二、单项选择题（每小题 2 分，共 20 分） 1 2 3 4 5 6 7 8 9 10 得分D B C B C D A A C B三、简答题（每小题 6 分，共 12 分）1构造命题公式 的真值表 )(RQP()PQR0 0 0 1 10 0 1 1 10 1 0 0 00 1 1 1 11 0 0 1 11 0 1 1 11 1 0 0 11 1 1 1 12求命题公式 的主析取范式和主合取
2、范式。 ()PQR ()()1()1()(PQRPR分 分)() ()()PRQP分分- 2 -()()()()()PQRPQRRPQR24567013 1()()mmM这 是 主 析 取 范 式 分这 是 主 合 取 范 式 分3判断命题公式 与 是否等价。 (PQR()PQR解： ()()A()()B 等价四证明题（共 32 分） （10 分）用 CP 规则证明 ；SQPSRQP),(),(1. P 6. T(4,5) I （2 分）P2. P 7. T(3,4) I（2 分） ()QR3. T(1, 2) I （2 分） 8. T(6,7) I（2 分）S4. P(附加前提) 9. CP
3、 （2 分）)(Q5. P )(SRQ （10 分）用归谬法证明 ,(),ABCSA证: 1 （1 分） 2 附 加 前 提 BP 3 （2 分） 4 1,BTIC5 （2 分） 6 3,4C S 7 （2 分） 8 （26I 5,7TI分）由 8 得出了矛盾，根据归谬法说明原推理正确（1 分）3 （12 分）公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：- 3 -（1）营业员 或 盗窃了钻石项链AB（2）若 作案，则作案时间不在营业时间（3）若 提供的证词正确，则货柜未上锁（4）若 提供的证词不正确，则作案发生在营业时间（5）货柜上了锁试问：作案者是谁？要求写出推理过程。解：令
4、 表示“ 营业员 盗窃了钻石项链 ”； 表示 “营业员 盗窃了钻石项链”；AB表示“作案时间在营业时间” ； 表示“ 提供的证词正确”； 表示“ 货柜PQAR上了锁”。则侦察结果如下：， ， ， ， 由此可推出作案者是 （4 分）ABRPRA推理过程如下：(1) (6) RBP(2) (7) (5)，(6) （2 分）QTI(3) (1)，(2) （2 分） (8) TIA(4) (9) (7)，(8) （2 分）PTI(5) (3)， (4) （2 分）TI天津理工大学离散数学第二章检测题答案一、填空题（每空 3 分，共 30 分）1 ()()()xGFxxG或 yy2 ()()(,)(,)
5、(,)xzwPxRwQzRxw3 Pabcabc4 5)()()()()( P- 4 -(),)(,Pxyx6 （ ； ） 7 8, (,)PyR()()xFGx二、单项选择题（每小题 2 分，共 20 分） 1 2 3 4 5 6 7 8 9 10 得分A A B D C A C C B D三、 简答题（每小题 6 分，共 12 分）1求謂词公式 的前束析取范式),()(),()( zyQPyxQPx ,)( zy),()(),)()(, ,)()()( zyQuPyxPzuxQz2证明： x证： ()()()()()xxPQxx左 式四证明题（共 38 分） 1 （12 分）用谓词演算的推
6、理规则证明:， ，)(xQPx)()(xSRxaP)(RaS（1） （2） （2 分）)(a)1(U（3） PRP（4） I （2 分）)(Q)3(T（5） )(xSx- 5 -（6） （2 分）)()(aSRaQ)5(US（7） I （2 分）3T（8） I （2 分）)( )7(4（9） I （2 分）aS 862(10 分) 指出下面推理证明过程中的错误，并给出正确的证明用谓词演算的推理规则证明： )()()( xZRxZxQRxQ证:：(1) P (6) T(4) Ia(2) US(1) (7) T(2),(5) I)(a)(3) P (8) T(6),(7) IxZQx ZR(4)
7、ES(3) (9) EG(8)( )(xx(5) T(4) Ia该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2 分）正确的证明是：（4 分）(1) P (6) T(2) I （1 分）)(xZQx )(aZ(2) ES (1) （2 分） (7) T(4),(5) I （1 分）)aR(3) P (8) T(6),(7) I （1 分）)(xRx)(4) US (3) （2 分） (9) EG(8) （1 分）)QxZx(5) T(2) I )(a3 （16 分）符号化下列命题并推证其结论任何人如果他喜欢音乐,他就不喜欢体育每个人或者
8、喜欢体育，或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐 （设 M(x)：x 喜欢音乐，S(x)：x 喜欢体育，(x)：喜欢美术 ）该推理符号化为：或()()()()()MSxAxxMx- 6 -前提： ()(),(),()xMSxAx结论： （4 分）证：（1） P （2） ES（1） （2 分）()xA()a（3） P （4） US（3） （2 分）SxSA（5） T（2） （4）I（2 分） （6） P()a ()()xMx（7） US（6） （2 分） （8） T（7）E （1 分）()Ma（9） T（5） （8）I（2 分） （10） EG（9） （1 分）()a ()x天津理工大
9、学离散数学第三、四章检测题答案一、填空题（每空 2 分，共 40 分）1 3 2n,abc4反对称，传递。 5 ； 6 ， 或单位矩阵1RiAI107 4,6 ， 2,3 ， 无 ， 无 ， 12 ， 1 。8 , 。1f,012f,1,09单射，满射；既是单射又是满射； ； BIA二、单项选择题（每小题 2 分，共 20 分） 1 2 3 4 5 6 7 8 9 10 得分(1) (2) (1) (3) （2） （2） (1) (3) (3) (1)三、简答题（共 30 分）1 （6 分）设 =1,2,3,5,6,10,15,30 ， “” 为集合 上的整除关系。 ，是否为AAA偏序集? 若
10、是，画出其哈斯图；- 7 -解： ，是偏序集。其哈斯图为：A2 （12 分）对下图所给的偏序集 ，求下表所列集合的上（下）界，上（下）确界，,A并将结果填入表中。子 集 上 界 下 界 上 确 界 下 确 界,abcadadde,c无 c无A无 无3 （6 分）设 =1,2,3,4,5,6，集合 上的关系A=1,3,1,5,2,5,4,4,4,5,5,4,6,3,6,6。R（1）画出 的关系图，并求它的关系矩阵；（2）求 及 。(),rS()tR解：（1） 的关系图为的关系矩阵为R（2 分）10010RM（2） ， （1 分）()1,2,35,r（1 分）6SR- 8 -（2 分）()1,42
11、,5tR4设 Z 是整数集， 是 Z 上的模 3 同余关系，即 ，,(mod3)RxyZxy试根据等价关系 决定 Z 的一个划分 。答案：由 决定的 Z 的划分为： ， 其中：R2,10R,8521,4721963, R四证明题（共 10 分） 设 定义 为 ，证明： 是双射，并求,ba1,0,:baf abxf)(f出其逆映射。证：1）先证明 是入射（2 分）f对任意的 则有 ，从而有 ，),(, 2121 xffbax若 abx21 21x故 是入射。f2) 再证明 是满射（2 分）对任意的 从而 是满射。,)(,)(,10 yxfbaybxy 使 得都 存 在 f综合（1） 、 （2）知
12、 是双射。f为 ，对任意 。 （1 分）,0:baf axb)()1 ,0x天津理工大学离散数学第五章检测题答案一、填空题（每空 2 分，共 30 分）1. 2 3 4 ；1 5 关于 运算不封闭 1ba,SaS6 2， 7 循环群，生成元 842- 9 -12 9 关于 封闭B二、单项选择题（每小题 2 分，共 20 分） 1 2 3 4 5 6 7 8 9 10 得分B C A A B D D C B D三、简答题（共 30 分）1设 是实数集 上的二元运算，其定义如下： R2abab（1）求 2 3， 3 (-5)和 7 1/2 。 （2） 是半群吗？ 可交换吗？,（3）求 中关于 的单
13、位元。 （4） 中哪些元素有逆元素，其逆元素是什么？R答案：（1）17，-32，14.5 。 2） 是半群， 可交换。 （3）0。 ,R（4）当 时， 有逆元素， 。,1/aa1/(2)a2设 ， 是交换群， 是 的单位元。 的运算表如下：,AbcdA,A bcd cd12ax 4356x 求 ，并说明道理。123456,xx答案： 。因为有限群的运算表中的每行、每列23456,dcbxdcxb都是群中元素的一个置换。3设集合 ， 是定义在 上的模 11 乘法（即任意 a,bG，有1,59GGa*b=(ab)(mod11)， 是普通乘法） ，问 是循环群吗？若是，试找出它的生,成元。答： 的运
14、算表如下表所示。,1 3 4 5 9- 10 -13459 1 3 4 5 93 9 1 4 54 1 5 9 35 4 9 3 19 5 3 1 4从运算表可知， 在 上封闭、有幺元 1，且 ，再G51432,59由 是可结合的得 是循环群，3，4，5 和 9 均为其生成元。,四证明题（共 20 分） （4 分）设 是独异点， 为其幺元，且对 ，有 ，证明,GeaGae是一个交换群。,证明： 对 ，由于 ，则 ， 即 中的每一个元素 都有逆元aae1a a素,故 是一个群。,G又对 ，有b，11()abba所以 是一个 Abel 群。,G （6 分）设 是一个群， ， ， ，有G:fxG1()xa试证明 是 一个自同构f,证：首先证明 是入射。 （3 分） 111212 212,(), .xGfxfaxxaaff对 若 则 有该 式 两 边 同 时 左 乘 及 右 乘 得 故 为 入 射其次证明 是满射。f对 1, ,(),yxyGyfxf都 存 在 使 得 因 此 是 满 射 .
