離散數(shù)學(xué)期末考試試卷(A卷)

1、精選離散數(shù)學(xué)期末考試試卷(A卷)一、判斷題：(每題2分，共10分)(1)心-)(2)對任意的命題公式4星。，若Knee丹AC ,則MOB(0)(3)設(shè)或是集合金上的等價關(guān)系,上是由 % 誘導(dǎo)的/上的等價關(guān)系，則R二匚。 (4)任意一個命題公式都與某一個只含合取和析取兩種聯(lián)結(jié)詞的命題公式等價。(0)(5)設(shè)尺是/上的關(guān)系，耳空，武蜀分別表示R的對稱和傳遞閉包，則漢出)E(聞(0)二、填空題：(每題2分，共10分)(1 )空集的募集的募集為()。(2)寫出(尸V0八(尸一氏)的對偶式()。(3)設(shè)/是我校本科生全體構(gòu)成的集合，兩位同學(xué)等價當(dāng)且僅當(dāng)他們在同一個班，則等價類的個數(shù)為()，同學(xué)小王所在的

2、等價類為()。(4)設(shè)/ = tW津是幺上的關(guān)系，則正滿足下列性質(zhì)的 哪幾條：自反的，對稱的，傳遞的，反自反的，反對稱的。( )(5)寫出命題公式的兩種等價公式()。三、用命題公式符號化下列命題(1 )(2) (3),用謂詞公式符號化下列命題(4) (5) (6)。(12 分)(1 ) ( 1 )僅當(dāng)今晚有時間，我去看電影。(2)(2)假如上午不下雨，我去看電影，否則就在家里讀書。(3)你能通你能通過考試，除非你不復(fù)習(xí)。(4) (4)并非發(fā)光的都是金子。(5) (5)有些男同志，既是教練員，又是國家選手。(6) (6)有一個數(shù)比任何數(shù)都大。四、設(shè)他濟(jì)。，給定上的兩個關(guān)系或和上分別是R=(%與0

3、 G 3 如上=M內(nèi)S*,£向3M 處（1） （1）寫出況和£的關(guān)系矩陣。（2）求直口£及,休口上）（12分）五、求（尸-也八國）八（？（-2八）的主析取范式和主合取范式。（1 0 分）六、設(shè)丁是片到F的關(guān)系，區(qū)是F到Z的關(guān)系，證明：（&#' = £'口r（8 分）七、設(shè)起是一個等價關(guān)系，設(shè)區(qū)=：偈小工對某一個匕，有%"工圾且證明：£也是一個等價關(guān)系。（10分）八、（10分）用命題推理理論來論證下述推證是否有效？甲、乙、丙、丁四人參加比賽，如果甲獲勝，則乙失敗；如果內(nèi)獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。

4、所以，如果丙獲勝，則丁不失敗。九、（10分）用謂詞推理理論來論證下述推證。任何人如果他喜歡步行，他就不喜歡乘汽車，每一個人或喜歡乘汽車，或喜歡騎 自行車（可能這兩種都喜歡）。有的人不愛騎自行車，因而有的人不愛步行 （論 域是人）。十、（8分）利用命題公式求解下列問題。甲、乙、丙、丁四人參加考試后，有人問他們，誰的成績最好，甲說：“不是我，”乙說：“是丁，”內(nèi)說：“是乙，”丁說：“不是我。” 四人的回答只有一人符合實際，問若只有一人成績最好，是誰？離散數(shù)學(xué)期末考試試卷答案（A卷）一、判斷題：（每題2分，共10分）（1） x x x（）（2）對任意的命題公式A，B，C,若A C B C,則A B

5、（）（3）設(shè)R是集合A上的等價關(guān)系，L是由AR誘導(dǎo)的A上的等價關(guān)系，則R L。（）（4）任意一個命題公式都與某一個只含合取和析取兩種聯(lián)結(jié)詞的命題公式等價。（）（5）設(shè)R是A上的關(guān)系，s（R），t（R）分別表示R的對稱和傳遞閉包，則ts（R） st（R）（）二、填空題：（每題2分，共10分）(1)空集的募集的募集為( ，)0(2)寫出(P Q) (PR)的對偶式(P Q) ( P R)。(3)設(shè)A是我校本科生全體構(gòu)成的集合，兩位同學(xué)等價當(dāng)且僅當(dāng)他們在同一個班，則等價類的個數(shù)為(我校本科生的班級數(shù)) ，同學(xué)小王所在的等價類為(小王所在的班的集合) 。(4)設(shè)A 1,2,3，R 1,2，1,3 是人

6、上的關(guān)系，則R滿足下列性質(zhì)的哪 幾條：自反的，對稱的，傳遞的，反自反的，反對稱的。( 傳遞的，反自反的，反對稱的 )(5) 寫 出 命 題 公 式 P Q 的 兩 種 等 價 公 式 ( (P Q) (Q P) ( P Q) ( Q P)。三、用命題公式符號化下列命題(1 )(2) (3),用謂詞公式符號化下列命題(4) (5) (6)。(12 分)(3) ( 1 )僅當(dāng)今晚有時間，我去看電影。解： P: 今晚我有時間 . Q: 我去看電影QP(4) (2)假如上午不下雨，我去看電影，否則就在家里讀書。解 P: 上午下雨 , Q: 我去看電影 R: 我在家里讀書。( P Q) (P R)( 3

7、)你能通你能通過考試，除非你不復(fù)習(xí)。解 P 你能通過考試， Q: 你復(fù)習(xí) . QP(7) (4)并非發(fā)光的都是金子。解 A(x):x是發(fā)光的，B(x)：x是金子( x)(A(x)B(x)(8) (5)有些男同志，既是教練員，又是國家選手。解A(x):x是男同志，B(x)：x是教練員，C(x)：x是國家選手( x)(A(x) B(x) C(x)(9) (6)有一個數(shù)比任何數(shù)都大。解 A(x ) : x 是數(shù)， B(x, y) : x 比 y 大，( x)(A(x) ( y)(A(y)B(x,y)四、設(shè)A a，b，c，d,給定A上的兩個關(guān)系R和L分別是R (a,b),(b,c),(c,a), L

8、(a,d),(b,b), (c,a),(c,c),(d,a),(d,c).可編輯(2)解（1 ）寫出R和L的關(guān)系矩陣。（2）求R L及t（R L）（12分）010000010010ML01001000101000001010010010101010M (R L)201010001000000000000010110101010M401010000(R L)000000000000MRLMRM (R L)31111M t( R L)五、求(P(P ( ( (P(P(QPPPQP111100010000(Q R)R) (Q Q) QR)R)(PR) (PR)R)(PP(P R) PQ P(PQR）

9、的主析取范式和主合取范式。（1R)R)Q)R) (R) (PR) (R) (P(PPRPQR)Q R) (Q)QR)(PR)Q R)Q)0分)1,2,3,4,5,60,7是 X 到 Y 的關(guān)系，證明：S是Y到Z的關(guān)系，證明:(TS)cSc六、cT （8 分）z, x (T S)c x,z T S( y)(y Y x,y T y,z S)( y)(y Y y,x Tc z,ySc)z,xScT c七 、 設(shè) R 是 一 個 等 價 關(guān) 系 ， 設(shè) S a,b : 對 某 一 個 c , 有 a，cR，且c，b R，證明：S也是一個等價關(guān)系。(10分)證明： (1) 對任一 x A, 因為 R 在

10、 A 上是自反的，所以x，x R.由S的定義，<x,x> S,所以S是自反的。(3)(2)對任意x，y A，若 x，yS，則對于某個c使得 x,c R c,y R,因為R對稱的，故有：y,c R c,x R,由S 的定義可知： y, x S, 所以 S 是對稱的。(3)對任意 x，y，z A，若x，yS及y,zS,則必存在某個ci ,使得x，ci Rci，y R，由R傳遞性，可知x，y R ,同理存在c2使得y，c2Rc2，zR，由R傳遞性，可知 y，z Ro再由S的定義，得 x，z S，故s是傳遞的。綜上可知， S 是 A 上的等價關(guān)系。八、(10分)用命題推理理論來論證下述推證

11、是否有效？甲、乙、丙、丁四人參加比賽，如果甲獲勝，則乙失??；如果丙獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。所以，如果丙獲勝，則丁不失敗。解：設(shè)A:甲獲勝。B:乙獲勝。C:丙獲勝。D: 丁獲勝。前提為：AB ，C B， A D結(jié)論為：CD(1) A BP(2) B A(1)T，E(3) A DP(4) BD(2)(3)T，I(5) CBP(6) CD(5)(4)T，I九、(10分)用謂詞推理理論來論證下述推證。任何人如果他喜歡步行， 他就不喜歡乘汽車， 每一個人或喜歡乘汽車， 或喜歡騎自行車(可能這兩種都喜歡) 。有的人不愛騎自行車，因而有的人不愛步行(論域是人 )。解：設(shè)P(x):x喜歡不

12、行。Q(x)喜歡乘汽車。R(x):x 喜歡騎自行車。本題符號化為： ( X)(P(X)Q(x),( X)(Q(x) R(x),( x) R(x) ( x) P(x)(1) ( x) R(x)P(2) R(c)(1)ES(3) ( X)(Q(x) R(x)P(4) Q(c) R(c)(3) US(5) Q(c)(2)(4)T,I(6) ( X)(P(X)Q(x)P(7) P(c) Q(c)(6)US(8) P(c)(5)(7)T,I(9) ( x) P(x)(8)EG 十、 (8 分) 利用命題公式求解下列問題。甲、乙、丙、丁四人參加考試后，有人問他們，誰的成績最好，甲說： “不是我， ”乙說： “是丁， ”丙說： “是乙， ”丁說： “不是我?！?四人的回答只有一人符合實際，問若只有一人成績最好，是誰？ 解：設(shè)A:甲的成績最好，B:乙的成績最好,C：內(nèi)的成績最好，D: 丁的成績最好 因為