離散數(shù)學(xué)A答案盛艷秀.doc

20061學(xué)期計(jì)算機(jī)2005級(jí)離散數(shù)學(xué)（A卷）參考答案及評(píng)分標(biāo)準(zhǔn)一、 將下列命題符號(hào)化（每小題3分，共18分）1、 P：我有時(shí)間，Q：我去音樂(lè)會(huì)。PQ 3分2、 P：這門(mén)課很難，Q：這門(mén)課很有意思。PQ3分3、 P：你去，Q：我去。(PQ)(PQ)或(PQ)3分4、 P：天下雨，Q：我開(kāi)車(chē)，R：我乘公共汽車(chē)。(PQ)(PR) 3分5、 S(x)：x是學(xué)生，L(x,y)：x比y聰明。$x(P(x)y(P(y)L(x,y) 3分6、 P(x)：x是鳥(niǎo)，Q(x)：x有翅膀。x(P(x)Q(x)x(Q(x)P(x)或者x(P(x)Q(x)$x(Q(x)P(x) 3分二、 判斷下列命題公式的類(lèi)型。要求寫(xiě)出過(guò)程，使用等值演算或真值表均可。（每小題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故該命題公式為可滿(mǎn)足式6分三、 用推理規(guī)則，構(gòu)造如下問(wèn)題的證明（每小題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、符號(hào)化命題： 設(shè)F(x)：x是無(wú)理數(shù)，G(x)：x是有理數(shù)，H(x)：x能表示成分?jǐn)?shù)。 $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規(guī)則) (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分五、 設(shè)A、B、C是任意集合，判斷下列命題是否為真，如果對(duì)于真命題，證明之。對(duì)于假命題說(shuō)明原因。（每小題4分，共8分）1、 假命題。2分設(shè)A=1,2,3，B=1，C=2，則BA，CA且AB=AC，但BC2分2、 真命題。2分證明 任取xB，則分為兩種情況：1） 若xA，則xAB，那么xAB，因?yàn)锳B=AC，所以xAC。因?yàn)閤A，故xAC，即xC2） 若xA，則xAB且x AB，那么xAB，因?yàn)锳B=AC，所以xAC。因?yàn)閤A，故xAC，而x(AC)-(AC)，即xAC，故xC。綜上所述，BC。同理可證CB.即可證得B=C。2分六、 設(shè)A=a,b,c，按下列要求給出A的二元關(guān)系：（每小題4分，共12分）1、 R=,或A上其他的等價(jià)關(guān)系1分 或其他等價(jià)關(guān)系對(duì)應(yīng)的等價(jià)矩陣1分A/R=a,b,c或其他等價(jià)關(guān)系對(duì)應(yīng)的商集1分abc或其他等價(jià)關(guān)系對(duì)應(yīng)的關(guān)系圖1分2、 R=,或A上其他的偏序關(guān)系2分 abc或其他偏序關(guān)系對(duì)應(yīng)的哈斯圖2分3、 A上共有233=512個(gè)二元關(guān)系。2分有5個(gè)等價(jià)關(guān)系。2分七、 證明 充分性 因?yàn)镽Rc=IA，所以xA，IA，即RRc，從而有R，故R具有自反性。2分RR，則Rc，有RRc，也即IA，故有x=y成立。即R具有反對(duì)稱(chēng)性。2分因?yàn)閠r(R)具有傳遞性，由R=tr(R)可知R必具有傳遞性。.1分綜上所述R是偏序關(guān)系。必要性由于R是偏序關(guān)系，所以R必是自反的、反對(duì)稱(chēng)的和傳遞的。則對(duì)xA，R，Rc，RRc，IA RRc。對(duì)x,yA，若 RRc，即R且Rc，Rc，R，R是反對(duì)稱(chēng)的，由R且R可知x=y，RRc IA。故RRc= IA。R是自反的，R=r(R)，R是傳遞的，R=t(R)，R=tr(R)5分八、 解 構(gòu)造雙射函數(shù)法設(shè)集合A=0,1/2,1/3,1/n,定義f：0，1（0，1）使得或其