参考答案及评分细则
西南科技大学2006——2007学年第2学期
《 离散数学J 》期中考试试卷
课程代码 1 4 3 1 4 0 3 2 0 命题单位 计算机学院 1．将下列命题将其符号化。（共4分） 解. ①符号化为：┐(┐p)∧┐q。(2分)
②符号化为：(q→p)→┐q。(2分) 2．在一阶逻辑中将下列命题符号化。（共9分） 解:
①.符号化为： ?x(I(x)?Q(x))???x(Q(x)?I(x))??x(Q(x)??I(x))
(3分)
②. 符号化为：
或者：
③.原句可表示为
?x(M(x)∧K(x)→L(x))∧?x(┐H(x,x)→N(x))； (3分)
3. 试证明 ：(┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R)) = R (共10分)
证明：(┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R)) =((┐P∧┐Q)∧R∨((Q∨P)∧R) =(┐(P∨Q)∧R)∨((Q∨P)∧R) =(┐(P∨Q)∨(Q∨P)∧R
=T∧R =R
第 1 页 共 4 页
；(3分)
4. 求公式G＝(P→Q)∧R的主析取范式和主合取范式。(共12分)
解：G＝(P→Q)∧R＝(┐P∨Q)∧R
＝(┐P∨Q∨(R∧┐R))∧((┐P∧P)∨(┐Q∧Q)∨R)
＝(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)∧(┐P∨Q∨R)∧
(P∨┐Q∨R)∧(P∨Q∨R)
＝(P∨Q∨R)∧(P∨┐Q∨R)∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)
主合取范式 （6分）
G＝(P→Q)∧R ＝(┐P∨Q)∧R ＝(┐P∧R)∨(Q∧R)
＝(┐P∧(┐Q∨Q)∧R)∨((┐P∨P)∧Q∧R)
＝(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(┐P∧Q∧R)∨(P∧Q∧R) ＝(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧Q∧R)
主析取范式 （6分）5.先将些列论断符号化，再证明
论断的正确性。（共15分）
解： 前提：(?x)(P(x)→Q(x)), ┐( ?x)(P(x)→R(x))
结论：(?x)(Q(x)∧┐R(x)) （4分）
P T,1),E
1) ┐( ?x)(P(x)→R(x)) 2)( ?x)┐(┐P(x)∨R(x)) 3) ┐(┐P(c)∨R(c)) 4)(P(c)∧┐R(c)) 5)P(c)
ES,2) T,3),E
T,4),I
T,4),I
P
6) ┐R(c)
7)( ?x)(P(x)→Q(x)) 8)P(c)→Q(c) 9)Q(c)
US,7)
T,5),8),I
第 2 页 共 4 页
10)Q(c)∧┐R(c) T,6),9),I
EG,10) （11分）
11)( ?x)(Q(x)∧┐R(x))
6.设A表示会排球的人的集合，B表示会篮球的人的集合，C表示会足球的人的集合。(共12分)
解:由题意有，|A∪B∪C|=50，由容斥原理得，
|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C| 由于|A|=40，|B|=35，|C|=10，|A∩B∩C|=5
所以有|A∩B|+|A∩C|+|B∩C|=-50+40+35+10+5=40 (5分) 会两门以上语言的人数为： |(A∩B)∪|(A∩C)∪(B∩C)|=
|(A∩B)|+|(A∩C)|+|(B∩C)|-2|A∩B∩C|=40-2*5=30 (4分)
只会两门语言的人数为会两门以上语言的人数减去会三门的人数，由此可得会两门的人数为30-5=25人。(3分)
7. 设R,S分别是从集合A到集合B，集合B到集合C的二元关系，试证明：
(RoS)-1＝S-1oR-1 (共12分)
证：任取
则至少存一个b∈B,使得：
由集合的定义知：(RoS) -1＝S-1oR-1。 （3分）
第 3 页 共 4 页
8. 设集合A＝{2,4}，B＝{2, 3，8}，设R={<2,3>,<3,8>}是集合B上的二元关
系. (共26分) 1) A×B (4分)
A×B ={<2,2>,<2,3>,<2,8>,<4,2>,<4,3>,<4,8>} 2) r(R)，s(R)，t(R))，st(R) 和ts(R) （每个2分） r(R)={<2,3>,<3,8>,<2,2>,<3,3>,<8,8>} s(R) )={<2,3>,<3,8>,<3,2>,<8,3>} t(R)) )={<2,3>,<3,8>,<2,8>}
st(R) )={<2,3>,<3,8>,<2,8>,<3,2>,<8,3>,<8,2>}
ts(R) )={<2,3>,<3,8>,<2,2>,<2,8>,<3,2>,<3,3>,<8,2><8,3>}
3) 画出集合B的幂集P(B)上定义的“包含于”关系的哈斯图，并指出集合
{{3},{2,3},{3,8}}的最小元、最大元、极小元、极大元、上界、最小上界、下界和最大下界。（哈斯图4分，其余每个1分） 最小元:{3} 最大元:无 极小元: {3} 极大元:{2,3},{3,8} 上界:{2,3,8} 最小上界: {2,3,8} 下界: {3}和空集 最大下界：{3}
第 4 页 共 4 页
