《離散數(shù)學(xué)復(fù)習(xí)》由會(huì)員分享,可在線閱讀,更多相關(guān)《離散數(shù)學(xué)復(fù)習(xí)(3頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、離散數(shù)學(xué)復(fù)習(xí)題B
一. 有兩個(gè)小題
1.分別說(shuō)明聯(lián)結(jié)詞、∧、∨、→和在自然語(yǔ)言中表示什么含義。
解:“”表示“…不成立”,“不…”。
“∧”表示“并且”、“不但…而且...”、“既…又 ...”等。
“∨”表示“或者”, 是可兼取的或。
“”表示 如果… ,則 …;只要… ,就 …; 只有… , 才…; 僅當(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)說(shuō)明它為什么不是永真式。
解:(4). (P∨Q)→P 不是永真式。
因?yàn)槿绻凹∨Q為真,后件P不一定為真。所以(P∨Q)→P 不是永真式。
三.用謂詞邏輯推理的方法證明下面推理的有效性。要求按照推理的格式書寫推理過(guò)程。
"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ì)算過(guò)程,不能直接寫出計(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>}