離散數(shù)學(xué)(第29講半期考試講評(píng))

1、馮偉森馮偉森 Email： Tel:2021年年7月月4日星期日日星期日 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2 2 主要內(nèi)容主要內(nèi)容 第一大題第一大題 1、只有不怕困難，才能戰(zhàn)勝困難；、只有不怕困難，才能戰(zhàn)勝困難； 解：解： p：怕困難，：怕困難， q：戰(zhàn)勝困難：戰(zhàn)勝困難 q p or p q 完全答對(duì)：完全答對(duì)： 37人人 基本答對(duì)：基本答對(duì)： 7人人 完全答錯(cuò)：完全答錯(cuò)：0 原因分析：原因分析： 分不清楚命題和邏輯謂詞之間表示的分不清楚命題和邏輯謂詞之間表示的 區(qū)別。區(qū)別。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院3 3 2、整數(shù)、整

2、數(shù)n 是偶數(shù)當(dāng)且僅當(dāng)是偶數(shù)當(dāng)且僅當(dāng)n能被能被2整除整除.； 解：解：p:整數(shù)整數(shù)n是偶數(shù)，是偶數(shù)，q:整數(shù)整數(shù)n能被能被2整除整除 pq 完全答對(duì)：完全答對(duì)： 26人人 基本答對(duì)：基本答對(duì)： 17人人 完全答錯(cuò)：完全答錯(cuò)：1 原因分析：原因分析： 分不清楚命題和邏輯謂詞之間表示的分不清楚命題和邏輯謂詞之間表示的 區(qū)別，沒有注意到當(dāng)且僅當(dāng)是雙條件命題。區(qū)別，沒有注意到當(dāng)且僅當(dāng)是雙條件命題。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院4 4 3、發(fā)明家都是聰明的并且是勤勞的，王前進(jìn)是、發(fā)明家都是聰明的并且是勤勞的，王前進(jìn)是 發(fā)明家，所以王前進(jìn)是聰明的并且是勤勞的；發(fā)明家，所以王前進(jìn)是聰明

3、的并且是勤勞的； 解：解： F(x)：x是發(fā)明家，是發(fā)明家，G(x)：x是聰明的，是聰明的，H(x) ：x是勤勞的，是勤勞的，a：王前進(jìn)：王前進(jìn) ( x(F(x)(G(x)H(x) F(a)G(a)H(a) 完全答對(duì)：完全答對(duì)： 7人人 基本答對(duì)：基本答對(duì)： 31人人 完全答錯(cuò)：完全答錯(cuò)：5 原因分析：原因分析： 邏輯謂詞的全稱量詞沒有寫，或者邏輯謂詞的全稱量詞沒有寫，或者 邏輯混淆。邏輯混淆。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院5 5 4、若、若x與與y都是實(shí)數(shù)，且都是實(shí)數(shù)，且 xy，則，則 x+2y+2； 解：解： F(x)：x是實(shí)數(shù)，是實(shí)數(shù)，H(x，y)：xy x y(

4、F(x)F(y)H(x,y)H(x+2，x+2) 完全答對(duì)：完全答對(duì)： 20人人 基本答對(duì)：基本答對(duì)： 22人人 完全答錯(cuò)：完全答錯(cuò)：2 原因分析：原因分析： 邏輯謂詞的全稱量詞沒有寫。邏輯謂詞的全稱量詞沒有寫。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院6 6 5、不存在最大的自然數(shù)。、不存在最大的自然數(shù)。 解：解： F(x)：x是實(shí)數(shù)，是實(shí)數(shù)，H(x，y)： xy x (F(x) y(F(y)H(x,y) 或或 x(F(x) y(F(y) H(x,y) 完全答對(duì)：完全答對(duì)： 5人人 基本答對(duì)：基本答對(duì)： 24人人 完全答錯(cuò)：完全答錯(cuò)：15 原因分析：原因分析： 邏輯謂詞的存在量詞

5、和全稱量詞沒邏輯謂詞的存在量詞和全稱量詞沒 有寫，對(duì)這句話理解很多人不是很清楚。有寫，對(duì)這句話理解很多人不是很清楚。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院7 7 第二大題第二大題 1、用等價(jià)變換法求下列公式的主析取范式和主、用等價(jià)變換法求下列公式的主析取范式和主 合取范式合取范式 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院8 8 )pq()qp()qp( 主合取式 主析取式 )pq()pq()qp( )pp(q()qp( )qp( q)qp( )q)pq()pq(q( )pq(q )pq()qp()qp( 完全答對(duì)：完全答對(duì)： 27人人 基本答對(duì)：基本答對(duì)： 5人人

6、完全答錯(cuò)：完全答錯(cuò)：12 原因分析：原因分析：對(duì)命題公式不熟悉，計(jì)算錯(cuò)誤。對(duì)命題公式不熟悉，計(jì)算錯(cuò)誤。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院9 9 2、求、求2A，其中，其中A=，a，b； 解：解：2A= ，,a,b,a，,b,a，b,A 完全答對(duì)：完全答對(duì)： 35人人 基本答對(duì)：基本答對(duì)： 0人人 完全答錯(cuò)：完全答錯(cuò)：9 原因分析：原因分析：典型錯(cuò)誤是少寫一個(gè)典型錯(cuò)誤是少寫一個(gè)，或，或。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1010 3、假設(shè)、假設(shè)R的關(guān)系圖如圖所示，試給出的關(guān)系圖如圖所示，試給出r（R）、）、s （R）、）、t（R）的關(guān)系矩陣）的關(guān)系矩陣M（

7、r（R）、）、M （s（R）、）、M（t（R）。）。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1111 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 R 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1212 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 )R(r(M 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 )R(s(M 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1

8、 1 0 )R(t(M 完全答對(duì)：完全答對(duì)： 14人人 基本答對(duì)：基本答對(duì)： 26人人 完全答錯(cuò)：完全答錯(cuò)：4 原因分析：原因分析：沒有根據(jù)圖寫出關(guān)系或關(guān)系矩陣沒有根據(jù)圖寫出關(guān)系或關(guān)系矩陣R， 對(duì)對(duì)r（R）和）和s（R）錯(cuò)誤較少，）錯(cuò)誤較少，t（R）錯(cuò)誤較）錯(cuò)誤較 多，可能是對(duì)多，可能是對(duì)warshall算法不了解或不熟悉。算法不了解或不熟悉。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1313 4、如圖是偏序集、如圖是偏序集 的哈斯圖，求的哈斯圖，求X和和的集的集 合表達(dá)式，合表達(dá)式， 并指出該偏序集的極大元、極小并指出該偏序集的極大元、極小 元、最大元、最小元。元、最大元、最小元

9、。 解：解：X=a,b,c,d,e,f =a,b, a,c, a,d, a,e, a,f, b,e, c,e, c,f, d,fIX 極大元極大元e,f；極小元；極小元a；最大元不存在，最小元；最大元不存在，最小元a； 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1414 ,X 完全答對(duì)：完全答對(duì)： 6人人 基本答對(duì)：基本答對(duì)： 33人人 完全答錯(cuò)：完全答錯(cuò)：5 原因分析：原因分析：偏序關(guān)系寫對(duì)的人很少，大部分寫偏序關(guān)系寫對(duì)的人很少，大部分寫 的是的是 =a,b, a,c, a,d, a,e, a,f, b,e, c,e, c,f, d,f缺少缺少Ix 2021-7-42021-7-4

10、計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1515 5、設(shè)、設(shè) 求求 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1616 2 ,3 :,( ), :, ( )2 2,3 xx RRxRRxx x , 3 x, 0 3x, 2x )x( 1 x, 2 1x,)2x( )x( 2 2 完全答對(duì)：完全答對(duì)： 32人人 基本答對(duì)：基本答對(duì)： 5人人 完全答錯(cuò)：完全答錯(cuò)：7 原因分析：原因分析：如果按函數(shù)的算對(duì)的比較多，按關(guān)如果按函數(shù)的算對(duì)的比較多，按關(guān) 系的有一個(gè)，其他的錯(cuò)誤是按函數(shù)算，但定義系的有一個(gè)，其他的錯(cuò)誤是按函數(shù)算，但定義 域沒寫對(duì)。域沒寫對(duì)。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院171

11、7 第三大題第三大題 1、用、用CP規(guī)則證明下面推理規(guī)則證明下面推理 前提前提: 結(jié)論結(jié)論: 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1818 () ,pqrspq rs P )rq(p)6 T4)E )rq()5 Morgan) De )qr()4 I2T1 qr)3 P q)2 P r)1 （ ） （附加前提） 完全答對(duì)：完全答對(duì)： 27人人 基本答對(duì)：基本答對(duì)： 11人人 完全答錯(cuò)：完全答錯(cuò)：6 原因分析：原因分析：采用采用CP規(guī)則推理時(shí)，沒有嚴(yán)格的按規(guī)則推理時(shí)，沒有嚴(yán)格的按 邏輯推理，有些關(guān)鍵步驟被省略，對(duì)推理中使邏輯推理，有些關(guān)鍵步驟被省略，對(duì)推理中使 用的規(guī)則使用不當(dāng)。

12、有些不了解規(guī)則。用的規(guī)則使用不當(dāng)。有些不了解規(guī)則。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院1919 規(guī)則 拒取式） 基本等價(jià)式、拒取式） CP sr)10 I(8T7 s)9 P ps )8 T5)6)I( p)7 2、用反證法證明下面推理、用反證法證明下面推理 前提前提: 結(jié)論結(jié)論: 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2020 (),pqrpq rs （假言推理） （簡(jiǎn)化法則） ） （附加前提） I5T4 rq)6 P )rq(p)5 IT3 p)4 P qp)3 ET1 sr)2 P )sr()1 完全答對(duì)：完全答對(duì)： 22人人 基本答對(duì)：基本答對(duì)： 20人

13、人 完全答錯(cuò)：完全答錯(cuò)：2 原因分析原因分析：沒有嚴(yán)格的按邏輯推理，有些關(guān)鍵：沒有嚴(yán)格的按邏輯推理，有些關(guān)鍵 步驟被省略。步驟被省略。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2121 （矛盾式） （簡(jiǎn)化法則） （假言推理） （簡(jiǎn)化法則） F)10 IT2 r)9 I7T6 r )8 IT3 q)7 3、構(gòu)造下面推理的證明、構(gòu)造下面推理的證明 前提前提: x(F(x) y(G(y)H(x) ， xF(x) 結(jié)論結(jié)論: x(F(x)G(x)H(x) 解：解：1） xF(x) 前提引入前提引入 2) F(c) 1）EI 3) x(F(x) y(G(y)H(x) 前提引入前提引入 4)

14、x y (F(x) (G(y)H(x) 3）轄域擴(kuò)張）轄域擴(kuò)張 5) y (F(c) (G(y)H(c) 4）UI 6) F(c) (G(c)H(c) 5）UI 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2222 7) G(c)H(c) 2）6）假言推理）假言推理 8) F(c)G(c)H(c) 2）7）合取）合取 9) x(F(x)G(x)H(x) 8）EG 完全答對(duì)：完全答對(duì)： 13人人 基本答對(duì)：基本答對(duì)： 10人人 完全答錯(cuò)：完全答錯(cuò)：21 原因分析：原因分析：對(duì)含有謂詞公式的推理，錯(cuò)的人比對(duì)含有謂詞公式的推理，錯(cuò)的人比 較多，主要是對(duì)規(guī)則的不熟悉，規(guī)則使用時(shí)應(yīng)較多，主要是對(duì)

15、規(guī)則的不熟悉，規(guī)則使用時(shí)應(yīng) 該注意的條件沒有注意。該注意的條件沒有注意。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2323 4、設(shè)、設(shè)R是是A 上的自反和傳遞關(guān)系，如下定義上的自反和傳遞關(guān)系，如下定義A 上的關(guān)系上的關(guān)系T，使得，使得 x,yA TRR 證明證明T是是A上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。 證明：證明：1）R是自反的是自反的 ， R ，即，即 T，T是自反的是自反的 2） 顯然，顯然，T是對(duì)稱的是對(duì)稱的 3） 設(shè)設(shè)T，T,由由T的定義有的定義有 RR 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2424 RR，由，由R的傳遞性，有的傳遞性，有 RR 即即T，T是傳遞

16、的是傳遞的 故故T是是A上的等價(jià)關(guān)系上的等價(jià)關(guān)系 完全答對(duì)：完全答對(duì)： 24人人 基本答對(duì)：基本答對(duì)： 9人人 完全答錯(cuò)：完全答錯(cuò)：11 原因分析：原因分析：這道題的正確率比較高，錯(cuò)的人主要這道題的正確率比較高，錯(cuò)的人主要 是傳遞性證明出錯(cuò)，對(duì)傳遞性的定義不了解。是傳遞性證明出錯(cuò)，對(duì)傳遞性的定義不了解。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2525 5、設(shè)、設(shè)f:A B 為單射函數(shù)，為單射函數(shù)， 為為X 在在f 下的像。證明下的像。證明 G也是單射的。也是單射的。 解：假設(shè)解：假設(shè) A1，A2 2A ，A1 A2， 不妨設(shè)存在不妨設(shè)存在x使得使得x A1x A2， 所以所以 f

17、(x) f(A1) 且且f(x) f(A2) 于是于是 f（A1） f(A2) 故故 G(A1) G(A2) 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2626 完全答對(duì)：完全答對(duì)： 6人人 基本答對(duì)：基本答對(duì)： 15人人 完全答錯(cuò)：完全答錯(cuò)：23 原因分析：這道題錯(cuò)誤率比較高，對(duì)原因分析：這道題錯(cuò)誤率比較高，對(duì)G（X） 為為X在在f下的像理解不清楚，沒有注意到，下的像理解不清楚，沒有注意到， f(x) f(A1) 且且f(x) f(A2)。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2727 第四大題第四大題 在一個(gè)道路網(wǎng)絡(luò)上連接有在一個(gè)道路網(wǎng)絡(luò)上連接有8個(gè)城市，分別標(biāo)記

18、為個(gè)城市，分別標(biāo)記為 a,b,c,d,e,f,g,h；城市之間的直接連接的道路有；城市之間的直接連接的道路有 ab,ac,bg,gb,cf,fe,bd,df。對(duì)每。對(duì)每 個(gè)城市求出從它出發(fā)能夠到達(dá)的所有其它城市個(gè)城市求出從它出發(fā)能夠到達(dá)的所有其它城市 。 解：令解：令 S=a,b,c,d,e,f,g,h 定義定義S上的關(guān)系上的關(guān)系R 如如 下下:x,y R 從從a到到b有一條直接的道路有一條直接的道路 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2828 R=a,b,a,c, b,g, g,b, c,f, f,e, b,d, d,f, 求出求出R的傳遞閉包的傳遞閉包t(R) 即可獲得問題的解。即可獲得問題的解。 2021-7-42021-7-4計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2929 0 0 0 000 010 000 010 000 000 0 0 1 0 1 1 0 0 0 0 0 0 0000 0000 1000 0110 MR 1 0 0 111 010 000 010 000 000 0 0 1 1 1 1 1 1 1 1 1 1 0000 0000 1010 1110 M )R( t (t(R)-IS)a=b，c，d，e，f，g