《離散數(shù)學(xué)復(fù)習(xí)》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)復(fù)習(xí)（3頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、離散數(shù)學(xué)復(fù)習(xí)題B
一. 有兩個(gè)小題
1．分別說明聯(lián)結(jié)詞、∧、∨、→和在自然語言中表示什么含義。
解：“”表示“…不成立”，“不…”。
“∧”表示“并且”、“不但…而且...”、“既…又 ...”等。
“∨”表示“或者”， 是可兼取的或。
“”表示 如果… ，則 …；只要… ，就 …； 只有… , 才…； 僅當(dāng) … 。
“”表示“當(dāng)且僅當(dāng)”、“充分且必要”。
2．分別列出PQ、 PQ、PQ 、PQ的真值表(填下表)。
P
Q
PQ
PQ
PQ
PQ
解：
P
2、
Q
PQ
PQ
PQ
PQ
F
F
T
F
T
F
F
T
F
T
T
F
T
F
F
T
F
F
T
T
T
T
T
T
二. 1.指出下面的命題公式中哪些是永真式(只寫題號(hào)即可)。
(1). (P∧(P→Q))→Q (2). P→(P∨Q)
(3). (P∧Q)→Q (4). (P∨Q)→P
解:(1),(2),(3)為永真式。
2.然后對(duì)上面的永真式任選其中一個(gè)給予證明(方法不限)。
證明 (3). (P∧Q)→Q
設(shè)前件(P∧
3、Q)為真，則得Q為真。所以(P∧Q)→Q是永真式。
3.上面哪個(gè)不是永真式（找出一個(gè)即可），請(qǐng)說明它為什么不是永真式。
解：(4). (P∨Q)→P 不是永真式。
因?yàn)槿绻凹∨Q為真，后件P不一定為真。所以(P∨Q)→P 不是永真式。
三.用謂詞邏輯推理的方法證明下面推理的有效性。要求按照推理的格式書寫推理過程。
"x(B(x)C(x)), $xA(x), "x(A(x)C(x)) $xB(x)
解：⑴ $xA(x) P
⑵ A(a) ES ⑴
4、
⑶ "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
⑼ $xB((x) EG ⑻
四．令全集E={1,2},A={1}, P(A)表示集合A的冪集。
5、
（注意：要求有計(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,2}}
3．計(jì)算～AE
解：因?yàn)椤獳＝E－A={1,2}-{1}={2}
～AE＝{2} {1,2}＝({2}{1,2})－({2
6、}{1,2})＝{1,2}－{2}＝{1}
五.給定集合A={1,2,3},定義A上的關(guān)系如下：
R= AA(完全關(guān)系（全域關(guān)系）)
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
。
。
。
1
3
2
。
。
。
1
3
2
M
。
7、
。
1
3
2
R
。
。
。
。
1
3
2
S
2. 判斷各個(gè)關(guān)系性質(zhì)。用“√”表示“是”，用“”表示“否”，填下表：
自反的
反自反的
對(duì)稱的
反對(duì)稱的
傳遞的
R
S
T
M
解：
自反的
反自反的
對(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},{3}} A/R={{1,2,3}}
4.求復(fù)合關(guān)系SoT
解：SoT＝{<1,1>,<1,2>,<2,3>,<3,1>,<3,2>}
離散數(shù)學(xué)復(fù)習(xí)
