资源描述：
《离散数学A答案盛艳秀》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、20061学期计算机2005级《离散数学（A卷）》参考答案及评分标准一、将下列命题符号化（每小题3分，共18分）1、P：我有时间，Q：我去音乐会。P→Q……………………………………………[3分]2、P：这门课很难，Q：这门课很有意思。P∧Q……………………………………[3分]3、P：你去，Q：我去。(P∧ØQ)∨(ØP∧Q)或Ø(P⇄Q)……………………………[3分]4、P：天下雨，Q：我开车，R：我乘公共汽车。(P⇄Q)∧(ØP⇄R)………………[3分]5、S(x)：x是学生，L(x,y)：x比y聪明。$x(P(x)∧"y(
2、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∧(P→Q))→Q⇔(P∧(ØP∨Q))→Q⇔(P∧Q)→Q⇔Ø(P∧Q)∨Q⇔(ØP∨ØQ)∨Q⇔ØP∨(ØQ∨Q)=ØP∨T=T真值表PQP→QP∧(P→Q)公式FFTFTFTTFTTF
3、FFTTTTTT故该命题公式为重演式…………………………………………………………[6分]2、等值演算(ØP→Q)→(Q→ØP)⇔(P∨Q)→(ØQ∨ØP)⇔Ø(P∨Q)∨(ØQ∨ØP)⇔(ØP∧ØQ)∨(ØQ∨ØP)⇔ØQ∨ØP真值表PQØP→QQ→ØP公式FFFTTFTTTTTFTTTTTTFF故该命题公式为可满足式………………………………………………………[6分]三、用推理规则，构造如下问题的证明（每小题5分，共15分）1、P∨(Q→R)，Q∨R，R→PÞP(1)ØPP(附加前提)(2)R→PP(3)ØRT(1)(2)I(
4、4)P∨(Q→R)P(5)Q→RT(1)(4)I(6)Q∨RP(7)QT(3)(6)I(8)RT(5)(7)I(9)ØR∧RT(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)→Ø
5、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)→"
6、xG(x)CP或其他正确的证明方法………………………………………………………………[5分]一、可以使用等值演算或真值表真值表PQRP↑QP∧ØR公式FFFTFFFFTTFFFTFTFFFTTTFFTFFTTTTFTTFFTTFFTTTTTFFT故(P↑Q)→(P∧ØR)的主析取范式为(P∧ØQ∧ØR)∨(P∧Q∧ØR)∨(P∧Q∧R)………[3分]成假指派为(F,F,F),(F,F,T),(F,T,F),(F,T,T),(T,F,T)……………………………[2分]二、设A、B、C是任意集合，判断下列命题是否为真，如果对于真命题
7、，证明之。对于假命题说明原因。（每小题4分，共8分）1、假命题。……………………………………………………………………………[2分]设A={1,2,3}，B={1}，C={2}，则BÍA，CÍA且A∪B=A∪C，但B≠C…………[2分]1、真命题。……………………………………………………………………………[2分]证明任取x∈B，则分为两种情况：1）若x∈A，则x∈A∩B，那么xÏAÅB，因为AÅB=AÅC，所以xÏAÅC。因为x∈A，故x∈A∩C，即x∈C2）若xÏA，则x∈A∪B且xÏA∩B，那么x∈AÅB，因为AÅB=AÅC
8、，所以x∈AÅC。因为xÏA，故xÏA∩C，而x∈(A∪C)-(A∩C)，即x∈A∪C，故x∈C。综上所述，BÍC。同理可证CÍB.即可证得B=C。………………………………[2分]一、设A={a,b,c}，按下列要求给出A的二元关系：（每小题4分，共12分）1、R={
