离散数学考试试题（b卷及答案）
一、（10分）求命题公式(p∧q)(pr)的主合取范式。
解：(p∧q)(pr)（(p∧q)(pr)）∧pr)(p∧q)）
(p∧q)∨(p∧r)）∧p∨r)∨(p∨q)）
p∧q)∨(p∧r)
p∨r)∧（q∨p）∧（q∨r）
p∨q∨r)∧(p∨q∨r)∧（p∨q∨r）∧（p∨q∨r）
m1∧m3∧m4∧m5
二、（8分）叙述并证明苏格拉底三段论。
解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
符号化：f（x）：x是一个人。g（x）：x要死的。a：苏格拉底。
命题符号化为"x（f（x）g（x）），f（a）g（a）
证明：1）"x(f(x)g(x)) p
2）f(a)g(a) t(1),us
3）f(a) p
4）g(a) t(2)(3),i
三、（8分）已知a、b、c是三个集合，证明a∩(b∪c)=(a∩b)∪(a∩c)
证明：∵x a∩（b∪c） x a∧x（b∪c）
x a∧（xb∨xc）
x a∧xb）∨（x a∧xc）
x（a∩b）∨x a∩c
x（a∩b）∪（a∩c）
a∩（b∪c）=（a∩b）∪（a∩c）
四、（10分）已知r和s是非空集合a上的等价关系，试证：1）r∩s是a上的等价关系；2）对a∈a，[a]r∩s=[a]r∩[a]s。
解："x∈a，因为r和s是自反关系，所以∈r、∈s，因而∈r∩s，故r∩s是自反的。
x、y∈a，若∈r∩s，则∈r、∈s，因为r和s是对称关系，所以因∈r、∈s，因而∈r∩s，故r∩s是对称的。
x、y、z∈a，若∈r∩s且∈r∩s，则∈r、∈s且∈r、∈s，因为r和s是传递的，所以因∈r、∈s，因而∈r∩s，故r∩s是传递的。
总之r∩s是等价关系。
2）因为x∈[a]r∩s∈r∩s
r∧∈s x∈[a]r∧x∈[a]s x∈[a]r∩[a]s
所以[a]r∩s=[a]r∩[a]s。
五、(10分) 设a＝，r是a上的二元关系，且r＝，求r(r)、s(r)和t(r)。
解 r(r)＝r∪ia＝
s(r)＝r∪r-1＝
r2＝r3＝
r4＝＝r2
t(r)＝＝
六、(15分) 设a、b、c、d是集合，f是a到b的双射，g是c到d的双射，令h：a×cb×d且"∈a×c，h()＝证明h是双射。
证明：1）先证h是满射。
∈b×d，则b∈b，d∈d，因为f是a到b的双射，g是c到d的双射，所以存在a∈a，c∈c，使得f(a)=b，f(c)=d，亦即存在∈a×c，使得h()＝所以h是满射。
2）再证h是单射。
、∈a×c，若h()＝h()，则＝ ，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是a到b的双射，g是c到d的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。
综合1）和2），h是双射。
七、(12分)设是群，h是g的非空子集，证明是的子群的充要条件是若a，bh，则有a*b-1h。
证明： "a,b∈h有b-1∈h，所以a*b-1∈h。
a∈h，则e=a*a-1∈h
a-1=e*a-1∈h
a,b∈h及b-1∈h，∴a*b=a*（b-1）-1∈h
hg且h≠f,∴*在h上满足结合律。
是的子群。八、（10分）设g=是简单的无向平面图，证明g至少有一个结点的度数小于等于5。
解：设g的每个结点的度数都大于等于6，则2|e|=sd(v)≥6|v|，即|e|≥3|v|，与简单无向平面图的|e|≤3|v|-6矛盾，所以g至少有一个结点的度数小于等于5。
九。g=,a=,*的运算表为：(写过程，7分)
1）g是否为阿贝尔群？
2）找出g的单位元；（3）找出g的幂等元（4）求b的逆元和c的逆元。
解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)
a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)
b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)
所以g是阿贝尔群。
2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以g的单位元是a
3）因为a*a=a 所以g的幂等元是a
4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b
十、(10分)求叶的权分别为的最优二叉树及其权。
解：最优二叉树为。
权＝148
离散数学考试试题a
一。8分 求与公式 x2 or not x1 x3 逻辑等值的主合取范式和主析取范式。二。8分 判断下列各公式是 1.永真式 2.永假式 3.其它。1 p q r q p r 2 not p or q p and p and q 3 not p or q and not q or not r and...
离散数学考试试题
天水师范学院 2012 2013学年第1学期。数统学院数应专业 10级 离散数学 考试试题。注 可参考笔记与课本。一 20分 一个排队线路，输入a,b,c,输出fa,fb,fc.本线路在同一时间只能有一个信号通过，若同时。有两个或两个以上信号申请输出时，则按a,b,c的顺序输出，写出fa,fb,fc...
离散数学考试试题
迅腾国际离散数学试题。一 选择题 20 3分 1.下面那个描述不是命题 a.今天是五一国际劳动节b.的小数点后第八万位是5 c 全体立正d.1 10 110 2.设p 今天下雨，q 明天下雨，这p q表示 a.今天和明天都下雨b.今天没有下雨。c 今天和明天都不会下雨 d.今天或明天下雨。3.下面那...