离散数学复习材料.docx

离散数学复习材料
1．（10分）求SKIPIF1<0的主析取范式与主合取范式。
解SKIPIF1<0
SKIPIF1<0
（1分，这里等价式的变换用其他方法也正确）
SKIPIF1<0（1分）
SKIPIF1<0（1分）
SKIPIF1<0（1分）
SKIPIF1<0（1分）
SKIPIF1<0（2分）
SKIPIF1<0（1分）
SKIPIF1<0（2分）
（说明：若用真值表做，真值表正确共6分，结果每个2分，共4分；中间一步因为笔误出错，方法思路正确的扣2分）
2．（15分）在谓词逻辑中构造下面推理的证明：“前提：每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，有的人不喜欢骑自行车。结论：有的人不喜欢步行。”
解：论域：所有人的集合。SKIPIF1<0(SKIPIF1<0)：SKIPIF1<0喜欢步行；SKIPIF1<0(SKIPIF1<0)：SKIPIF1<0喜欢坐汽车；SKIPIF1<0(SKIPIF1<0)：SKIPIF1<0喜欢骑自行车；则推理化形式为：（每个题设正确得1分）
SKIPIF1<0SKIPIF1<0(SKIPIF1<0(SKIPIF1<0)SKIPIF1<0(SKIPIF1<0))，SKIPIF1<0SKIPIF1<0(SKIPIF1<0(SKIPIF1<0)∨SKIPIF1<0(SKIPIF1<0))，SKIPIF1<0SKIPIF1<0SKIPIF1<0(SKIPIF1<0)SKIPIF1<0SKIPIF1<0SKIPIF1<0SKIPIF1<0(SKIPIF1<0) （2分）
下面给出证明：（下面每步1分，共10分）
(1)SKIPIF1<0SKIPIF1<0SKIPIF1<0(SKIPIF1<0)P
(2)SKIPIF1<0SKIPIF1<0SKIPIF1<0(SKIPIF1<0) T(1)，E
(3)SKIPIF1<0(SKIPIF1<0) T(2)，ES
(4)SKIPIF1<0SKIPIF1<0(SKIPIF1<0(SKIPIF1<0)∨SKIPIF1<0(SKIPIF1<0)) P
(5)SKIPIF1<0(SKIPIF1<0)∨SKIPIF1<0(SKIPIF1<0) T(4)，US
(6)SKIPIF1<0(SKIPIF1<0) T(3)(5)，I
(7)SKIPIF1<0SKIPIF1<0(SKIPIF1<0(SKIPIF1<0)SKIPIF1<0(SKIPIF1<0)) P
(8)SKIPIF1<0(SKIPIF1<0)SKIPIF1<0(SKIPIF1<0) T(7)，US
(9)SKIPIF1<0(SKIPIF1<0) T(6)(8)，I
(10)SKIPIF1<0SKIPIF1<0SKIPIF1<0(SKIPIF1<0) T(9)，EG
3．（15分）设正整数的序偶集合A，在A上定义的一个二元关系R如下：
SKIPIF1<0当且仅当SKIPIF1<0。
(1)证明R是一个等价关系。(10分)
(2)若A={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,4>,<2,6>,<4,1>,<4,2>}，试写出R所决定的A上的划分。(5分)
证明：(1)SKIPIF1<0
a.自反性 （3分）
SKIPIF1<0,SKIPIF1<0
b.对称性 （3分）
SKIPIF1<0
c.传递性 （4分）
若SKIPIF1<0且SKIPIF1<0，则
SKIPIF1<0且SKIPIF1<0，显然，SKIPIF1<0，即SKIPIF1<0
(2){{<1,1>,<2,2>},{<1,2>,<2,4>},{<1,3>,<2,6>},{<2,1>,<4,2>},{<4,1>}}
（5个分块各1分，共5分）
4．（15分）设函数f：R×RR×R，f定义为：f(<x，y>)