离散数学A答案盛艳秀.doc

20061学期计算机2005级离散数学（A卷）参考答案及评分标准一、 将下列命题符号化（每小题3分，共18分）1、 P：我有时间，Q：我去音乐会。PQ 3分2、 P：这门课很难，Q：这门课很有意思。PQ3分3、 P：你去，Q：我去。(PQ)(PQ)或(PQ)3分4、 P：天下雨，Q：我开车，R：我乘公共汽车。(PQ)(PR) 3分5、 S(x)：x是学生，L(x,y)：x比y聪明。$x(P(x)y(P(y)L(x,y) 3分6、 P(x)：x是鸟，Q(x)：x有翅膀。x(P(x)Q(x)x(Q(x)P(x)或者x(P(x)Q(x)$x(Q(x)P(x) 3分二、 判断下列命题公式的类型。要求写出过程，使用等值演算或真值表均可。（每小题4分，共12分）1、 等值演算：(P(PQ)Q(P(PQ)Q(PQ)Q(PQ)Q(PQ)QP(QQ)= PT=T真值表PQPQP(PQ)公式FFTFTFTTFTTFFFTTTTTT故该命题公式为重演式6分2、 等值演算(PQ)(QP) (PQ)(QP)(PQ)(QP)(PQ)(QP) QP真值表PQPQQP公式FFFTTFTTTTTFTTTTTTFF故该命题公式为可满足式6分三、 用推理规则，构造如下问题的证明（每小题5分，共15分）1、P(QR)，QR，RPP(1) P P(附加前提)(2) RP P(3) R T(1)(2) I(4) P(QR) P(5) QR T(1)(4) I(6) QR P(7) Q T(3)(6) I(8) R T(5)(7) I(9) RR T(3)(8) I或其他正确的证明方法5分2、符号化命题： 设F(x)：x是无理数，G(x)：x是有理数，H(x)：x能表示成分数。 $x(F(x)H(x)，x(G(x)H(x) x(G(x)F(x) 证明 (1) $x(F(x)H(x) P (2) x(F(x)H(x) T(1) E (3) F(a)H(a) US(2) (4) H(a)F(a) T(3) E (5) x(G(x)H(x) P (6) G(a)H(a) US(4) (7) G(a)F(a) T(4)(5) I (8) x(G(x)F(x) UG(6)或其他正确的证明方法5分3、x(F(x)G(x)xF(x)xG(x) 附加前提法(CP规则) (1) xF(x) P(附加前提) (2) F(a) US(1) (3) x(F(x)G(x) P (4) F(a)G(a) US(3) (5) G(a) T(2)(4) I (6) xG(x) UG(5) (7) xF(x)xG(x) CP或其他正确的证明方法5分四、 可以使用等值演算或真值表真值表PQRPQPR公式FFFTFFFFTTFFFTFTFFFTTTFFTFFTTTTFTTFFTTFFTTTTTFFT故(PQ)(PR)的主析取范式为(PQR)(PQR) (PQR)3分成假指派为(F,F,F),(F,F,T), (F,T,F), (F,T,T) ,(T,F,T)2分五、 设A、B、C是任意集合，判断下列命题是否为真，如果对于真命题，证明之。对于假命题说明原因。（每小题4分，共8分）1、 假命题。2分设A=1,2,3，B=1，C=2，则BA，CA且AB=AC，但BC2分2、 真命题。2分证明 任取xB，则分为两种情况：1） 若xA，则xAB，那么xAB，因为AB=AC，所以xAC。因为xA，故xAC，即xC2） 若xA，则xAB且x AB，那么xAB，因为AB=AC，所以xAC。因为xA，故xAC，而x(AC)-(AC)，即xAC，故xC。综上所述，BC。同理可证CB.即可证得B=C。2分六、 设A=a,b,c，按下列要求给出A的二元关系：（每小题4分，共12分）1、 R=,或A上其他的等价关系1分 或其他等价关系对应的等价矩阵1分A/R=a,b,c或其他等价关系对应的商集1分abc或其他等价关系对应的关系图1分2、 R=,或A上其他的偏序关系2分 abc或其他偏序关系对应的哈斯图2分3、 A上共有233=512个二元关系。2分有5个等价关系。2分七、 证明 充分性 因为RRc=IA，所以xA，IA，即RRc，从而有R，故R具有自反性。2分RR，则Rc，有RRc，也即IA，故有x=y成立。即R具有反对称性。2分因为tr(R)具有传递性，由R=tr(R)可知R必具有传递性。.1分综上所述R是偏序关系。必要性由于R是偏序关系，所以R必是自反的、反对称的和传递的。则对xA，R，Rc，RRc，IA RRc。对x,yA，若 RRc，即R且Rc，Rc，R，R是反对称的，由R且R可知x=y，RRc IA。故RRc= IA。R是自反的，R=r(R)，R是传递的，R=t(R)，R=tr(R)5分八、 解 构造双射函数法设集合A=0,1/2,1/3,1/n,定义f：0，1（0，1）使得或其