离散数学模拟试卷一答案
简答题（25%）：
解：R的关系矩阵表示为：
自反闭包:r(R) = {<a,a>,<b,b>,<c,c>,<d,d>, <a,b>,<b,a>, <b,c>,<c,d>}
对称闭包s(R) = {<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}
传递闭包t(R) = {<a,a>,<a,b>,<b,b>,<b,a>, <b,c>,<c,d>,<b,d>, <a,c>,<a,d>}
解：
⑴(P∨¬P)→¬Q的真值表如下所示：
P Q P∨¬P (P∨¬P)→¬Q
0 0 1 1
0 1 1 0
1 0 1 1
1 1 1 0
为可满足公式。
⑵(P→Q) (¬Q→¬P)的真值表如下所示：
P Q (P→Q) (¬Q→¬P) (P→Q) (¬Q→¬P)
0 0 1 1 1
0 1 1 1 1
1 0 0 0 1
1 1 1 1 1
为永真公式。
⑶G=(P∨Q)∧(¬P∨Q)∧(P∨¬Q)∧(¬P∨¬Q)的真值表如下所示：
P Q (P∨Q) (¬P∨Q) (P∨¬Q) (¬P∨¬Q) G
0 0 0 1 1 1 0
0 1 1 1 0 1 0
1 0 1 0 1 1 0
1 1 1 1 1 0 0
为永假公式。
⑷G=(P∧Q)∨(¬P∧Q)∨(P∧¬Q)∨(¬P∧¬Q)的真值表如下所示：
P Q (P∧Q) (¬P∧Q) (P∧¬Q) (¬P∧¬Q) G
0 0 0 0 0 1 1
0 1 0 1 0 0 1
1 0 0 0 1 0 1
1 1 1 0 0 0 1
为永真公式。
解；
不是格，∵有两个元素无下界。
是格，∵任意两个元素都有最小上界和最大下界。
是格，原因同(b)。
不是格，∵有两个元素无下界。
判断题（25%）：
1．解：
⑴ 命题为假。R∩S是反自反的，但ROS不一定是反自反的。例如R={<a,b>}，S={<b,a>}，集合A={<a,b>}，则ROS={<a,a>}不是反自反的。
⑵命题为假。R∩S是传递的，但ROS不一定是可传递的。例如：集合A={1,2,3,4,5}，R={<1,2>,<3,4>}，S={<2,3>,<4,5>}，则ROS={<1,3>,<3,5>}不是可传递的。
⑶ 命题为真。
⑷命题为假。例如：集合A={a,b,c}，R={<a,b>,<b,c>}， S={<b,b>,<c,a>}，则R与S都是反对称的，但ROS={<a,b>,<b,a>}不是反对称的。
2．解：因为对任意x，y∈R，|x-y|=|y-x|，所以x*y=y*x，故*是可交换的。而对1，2，3∈R，（1*2）*3=||1-2|-3|=2，而1*（2*3）=|1-|2-3||=0，所以（1*2）*3≠1*（2*3），故*不是可结合的。因为对每个x∈R，都不可能使对任意y∈R有x*y=y成立，所以R中不存在关于*的幺元。
3．判断下图中哪些图中有欧拉回路？
有欧拉回路
有欧拉回路
没有欧拉回路
没有欧拉回路
证明题（35%）：
证明：
∵fOg=IA是双射，∴f是内射，g是满射，
∵gOf=IB是双射，∴g是内射，f是满射，
所以g，f是双射，故g，f均可逆。
gOfOf-1=（gOf）Of-1=IBOf-1=f-1
gOfOf-1=gO(fO f-1)=gOIA=g，故g=f-1
fOgOg-1=（fOg）Og-1=IAOg-1=g-1
fOgOg-1=f O(gOg-1)=fOIB=f，故f=g-1 。
证明：
P∨Q P
¬P→Q T，①，E
Q→S P
¬P→S T，②，③，I
¬S→P T，④，E
P→R P
¬S→R T，⑤，⑥，I
SVR T，⑦，E
证明：
¬(x)Q(x) P
（x）（¬P(x)） P
（x）(¬Q(x)) T，①，E
（x）（¬P(x)）∧（x）(¬Q(x)) T，②，③，I
（x）（¬P(x)∧¬Q(x)） T，④，E
¬P(y)∧¬Q(y) US，⑤
¬P(y)∨Q(y)） T，⑥，E
（x）（P(x)∨Q(x)） P
P(y)∨Q(y) US，⑧
（P(y)∨Q(y)）∧¬（P(y)∨Q(y)） T，⑦，⑨，I
证明：
已知<G;*>是一个独异点，则存在幺元e，且*运算满足结合律，又已知对于G中的每一个元素x都有x*x=e，所以每一个元素x都有逆元为x，故<G;*>是群。
对任意a,b∈G，有(a*b)*(a*b)=e
a*(b*(a*b))=a*a
b*(a*b)=a
则b*(b*(a*b))=b*a
e*(a*b)=b*a
a*b=b*a
因此满足交换律。
所以<G;*>是一个阿贝尔群。
综合题（15%）：
解：
⑴ P→(P∧(Q→P)) P→(P∧(¬Q∨P))
¬P∨(P∧(P∨¬Q)
¬P∨P 1
∴P→(P∧(Q→P))的主合取范式为空。
主析取范式为(¬P∧Q)∨(P∧¬Q)∨(P∧Q)∨(¬P∧¬Q)
⑵ (Q→P)∧(¬P∧Q) (¬Q∨P)∧(¬P∧Q)
(¬Q∨P)∧¬(¬Q∨P) 0
∴(Q→P)∧(¬P∧Q)的主析取范式为空。
主合取范式为(¬P∨Q)∧(P∨¬Q)∧(P∨Q)∧(¬P∨¬Q)
解：下图表示比赛可能进行的各种情况，图中，标甲的表示甲胜，标乙的表示乙胜。这是一棵完全二元树。