離散數(shù)學(xué)復(fù)習(xí)

1、離散數(shù)學(xué)復(fù)習(xí)題B一. 有兩個(gè)小題1分別說明聯(lián)結(jié)詞Ø、和«在自然語言中表示什么含義。解：“Ø”表示“不成立”，“不”?！啊北硎尽安⑶摇薄ⅰ安坏?”、“既又 .”等?！啊北硎尽盎蛘摺保?是可兼取的或。“®”表示 如果 ，則 ；只要 ，就 ； 只有 , 才； 僅當(dāng) ?！?#171;”表示“當(dāng)且僅當(dāng)”、“充分且必要”。2分別列出P«Q、 PÚQ、P®Q 、PÙQ的真值表(填下表)。PQP«Q PÚQP®QPÙQ解：PQP«Q PÚQP®QPÙ

2、;QFFTFTFFTFTTFTFFTFFTTTTTT二. 1.指出下面的命題公式中哪些是永真式(只寫題號(hào)即可)。 (1). (P(PQ)Q (2). P(PQ) (3). (PQ)Q (4). (PQ)P解:(1),(2),(3)為永真式。2.然后對(duì)上面的永真式任選其中一個(gè)給予證明(方法不限)。證明 (3). (PQ)Q 設(shè)前件(PQ)為真，則得Q為真。所以(PQ)Q是永真式。 3.上面哪個(gè)不是永真式（找出一個(gè)即可），請(qǐng)說明它為什么不是永真式。解：(4). (PQ)P 不是永真式。因?yàn)槿绻凹Q為真，后件P不一定為真。所以(PQ)P 不是永真式。三.用謂詞邏輯推理的方法證明下面推理的有效性。

3、要求按照推理的格式書寫推理過程。 "x(B(x)®ØC(x), $xA(x), "x(ØA(x)ÚC(x) Þ $xØB(x)解： $xA(x) P A(a) ES "x(ØA(x)Ú C(x) P ØA(a)ÚC(a) US C(a) T I " x(B(x)®ØC(x) P B(a)®ØC(a) US ØB(a) T I $xØB(x) EG 四令全集E=1,2,A=1, P(A)表示集合A的

4、冪集。（注意：要求有計(jì)算過程，不能直接寫出計(jì)算結(jié)果！）1. 指出 P(E)和P(A)各有多少個(gè)元素。即求|P(E)|和|P(A)|。解：因?yàn)镻(E),1,2, 1,2 所以P(E)有4個(gè)元素。即|P(E)|4。P(A),1 所以P(A)有2個(gè)元素。即|P(A)|2。 2. 計(jì)算 P(E)P(A)解： P(E)P(A),1,2,1,2,1 2, 1,23計(jì)算AÅE解：因?yàn)锳EA=1,2-1=2 AÅE2 Å1,2(2È1,2)(2Ç1,2)1,221五.給定集合A=1,2,3,定義A上的關(guān)系如下： R= A×A(完全關(guān)系（全域關(guān)系）)

5、S=<1,2>,<2,3>,<3,1> T=<1,1>,<1,2>,<2,1>,<2,2>,<3,3> M=<1,1>,<1,2>,<1,3>,<2,2>,<3,3> 1.寫出關(guān)系S的矩陣；再畫出上述各個(gè)關(guān)系的有向圖。解：關(guān)系S的矩陣如下：下面是幾個(gè)關(guān)系的有向圖：T。132。132M。132R。132S2. 判斷各個(gè)關(guān)系性質(zhì)。用“”表示“是”，用“×”表示“否”，填下表：自反的反自反的對(duì)稱的反對(duì)稱的傳遞的RSTM解：自反的反自反的對(duì)稱的反對(duì)稱的傳遞的R××S×××T××M××3.上述四個(gè)關(guān)系中，哪些是等價(jià)關(guān)系？哪些是偏序關(guān)系？對(duì)等價(jià)關(guān)系，寫出此等價(jià)關(guān)系的各個(gè)等價(jià)類。解：T和R是等價(jià)關(guān)系。 M是偏序關(guān)系。 A/T=1,2