離散題A計算機上

1、湖南科技大學考試試題紙( A 卷)(2007 -200 8 學年第 1 學期 )離散數(shù)學 課程 數(shù)學與計算科學學院 院(系) 計算機，網(wǎng)絡 班級 考試時量 100 分鐘 學生人數(shù)命題教師 李世群 系主任交題時間： 07 年 12 月 24 日 考試時間： 年 月 日 一、 判斷題( 每小題 2分，共 16 分)正確的打“”，否則打“”1、 xA(x) xB(x) x(A(x) B(x)2、|A B| |A| |A B| 3、實數(shù)集上數(shù)的大小關系是全序關系。4 、集合上的二元關系若是對稱的，則必不是反對稱的。5、 A B A B6. p q 的對偶式是 p q7、 x(A(x) p(x,y) x

2、B(x) 可以改名為y(A(y) p( y, y) xB(x)8、A=1,2,3 ，4, A 上的關系 R=, , ，, 是函數(shù)。二、填空題 (每小題 3 分，共 30分)1、設 A有 2 個元，則 A上的不同的二元關系共有 個2、A=1,2,3 ，集合 A 上的全域關系將 A 分成類3、A=1,2,3 ，4, R是 A上的關系，且 R=, , ，, ，則 R的對稱閉包 S(R)= 4.設 解 釋 I 為 ： D a,b,p(a,a): 1 P(a,b): 0 p(b,a): 0 p(b.b): 1 ， 公 式 x yp( x,y)在以上解釋 I 下的真值為 _5、a,b _6、自然數(shù)集 N

3、上的整除關系 R x,y |x整除 y 是關系(填偏序或等價)7、設 A 1,2, ，其冪集 (A) _ 。8、 A 1,2, ，則 A A _ 。9.設 A, B是含命題變項 p,q,r的命題公式 ,已知 :A的成真賦值為 000, 011, 110, 111; B的成真賦值為 000, 101, 110;則 A B的成真賦值為 10設 A=1,2,3 ，4, A 上的置換(1,2), (2,3) ，則 _三、計算題( 每小題 8 分，共 24分)1. 求公式 p ( q r) 的主合取范式。( 8 分)2. 求合式公式xG(x) xH(x) 的前束范式。 (8 分)1 / 113（ 1）將

4、 命題“每個人都要吃飯” 在一階邏輯中符號化。 （4 分）（2）將命題“每個實數(shù)都存在相反數(shù)”在一階邏輯中符號化。 （4 分）四.（20分） 設集合 A=1,2,3,4,5,6 ，R x,y | x整除y為A上的關系，（1）用列舉法列出 R的全部元素；（ 5 分）（2）畫出 R的哈斯圖；（ 5 分）（3）求 R 的關系矩陣。（ 5 分）（4）求子集 B=2，3，6 的最大元，最小元，極大元，極小元，上界，上確界。 （5 分）五、證明題（ 每小題 5 分，共 10分）1. 在一階邏輯中，構造下面推理的證明。前提： x（F（x） G（x）,x F（X） ；結(jié)論： xG（x） 。2. 設 A是集合，

5、證明 A （A B） A共 頁， 第 頁，注：請打印或用炭素墨水書寫、字跡要求工整、并抄寫在方框線內(nèi)2 / 11湖南科技大學瀟湘學院考試試題紙(A 卷)(200 -200 學年第 學期 )離散數(shù)學 課程 計算機，網(wǎng)絡工程，專業(yè)班級考試時量 100 分鐘 學生人數(shù) 命題教師 李世群 系主任交題時間： 07 年 12 月 24 日 考試時間： 年 月 日一 判斷題( 每小題 2分，共 16 分)正確的打“”，否則打“”1、 xA(x) xB(x) x(A(x) B(x)2、|A B| |A| |A B|3、實數(shù)集上數(shù)的大小關系是全序關系。4 、集合上的二元關系若是對稱的，則必不是反對稱的。5、 A

6、 B A B6. p q 的對偶式是 p q7、 x(A(x) p(x,y) xB(x) 可以改名為y(A(y) p( y, y)xB(x)8、A=1,2,3 ，4, A 上的關系 R=, , ，, 是函數(shù)。二、填空題 (每小題 3 分，共 30 分)1、設 A 有 2 個元，則 A 上的不同的二元關系共有 個2、A=1,2,3 ，集合 A 上的全域關系將 A 分成類3、A=1,2,3 ，4, A 上的關系 R=, , ，, ，則 R的對稱閉包 S(R)= 4. 解釋 I 為： D a,b, p(a,a): 1 P(a,b): 0 p(b,a): 0 p(b.b): 1，公式x yp( x,y

7、)在以上解釋 I 下的真值為 _5、a,b _6、自然數(shù)集 N 上的整除關系 R x,y |x整除 y 是關系(填偏序或等價)7、設 A 1,2, ，其冪集 p(A) _8、 A 1,2, ，則 A A _9.設 A, B 是含命題變項 p,q,r 的命題公式 ,已知:A 的成真賦值為 000, 011, 110, 111; B 的成真賦值為 000, 101, 110; 則 A B 的成真賦值為 10設 A=1,2,3 ，4, A 上的置換 (1,2), (2,3) ，則 _3 / 11三、計算題( 每小題 10 分，共 30 分 )1. 求公式 p ( q r) 的主合取范式。2. 求合式

8、公式 xG(x) xH(x) 的前束范式。3將 命題“每個人都要吃飯”在一階邏輯中符號化。四. (15分)設集合 A=1,2,3,4,5,6 ，R為 A 上的整除關系，(1)列舉法列出 R的全部元素；( 5 分)(2)畫出 R的哈斯圖；( 5 分)(3)求 R 的關系矩陣。( 5 分)五、證明題(5 分 +4 分，共 9 分 )1. 在一階邏輯中，構造下面推理的證明。 前提： x(F(x) G(x), x F(X) ； 結(jié)論： xG(x) 。2. 設 A是集合，證明 A (A B) A共 頁， 第 頁，注：請用炭素墨水書寫、字跡要求工整、并抄寫在方框線內(nèi)4 / 11湖南科技大學考試試題參考答案

9、及評分細則( 200 -200 學年第 學期)課程( A 卷)院(系) 班級應試學生人數(shù) 實際考試學生人數(shù) 考試時量 100 分鐘 命題教師 審核人： 考試時間： 年 月 日 一.判斷題( 每小題 2 分，共 16分)正確的打“” ，否則打“”1. 2. 3. 4. 5. 6. 7. 8. 二. 填空題 (每小題 3 分，共 30分)4(1). 24 個;(2).1 (3). 1,1 , 2,1 , 1,2 , 4,2 , 2,4 (4).1 (5). a (6). 偏序 (7). ,1, 2, 1,2(8). A A 1,1 , 1,2 , 2,1 , 2,2 (9). 000，011， 1

10、10， 111， 101;(10). ( 1，3，2).三.(24 分, 每小題 8 分)1. 解：p ( q r)(p q)(p r) 2 分(p q( r r) (p ( q q) r)4 分(p q r) (p qr) (p qr)M0 M1M28 分2. ，求合式公式 xG(x) xH(x) 的前束范式。解： xG(x) xH(x)x G(x) xH(x)4 分x( G(x) H(x)8 分3將命題“每個人都要吃飯”在一階邏輯中符號化。m(x) : x是人解：設 2 分D( x)： x要吃飯“每個人都要吃飯”在一階邏輯中符號化為：x(M( x) D( x)4 分5 / 11命題“每個實

11、數(shù)都存在相反數(shù)”在一階邏輯中符號化為：x(R(x) y(R(y) P(x,y) 4 分四.(20分) R 是集合 A=1,2,3,4,5,6 上的關系， R為 A上的整除關系，(1) . 用列舉法列出 R的全部元素；( 5 分)(2) . 畫出 R的哈斯圖；( 4 分)(3) 求 R 的關系矩陣。( 4 分)(4) . 求子集 B=2，3，6 的最大元，最小元，極大元，極小元，上界，上確界。 ( 7 分)解：(1) R 1,1 1,2 , 1,3 ,1,4 , 1,5. , 1,6 , 2,2,3,3 , 4,4 , 5,5 , 6,6 , 2,4 , 2,6 , 3,6 1111101010

12、(3) M (R)0010000010000012)R的哈斯圖：000005 分 9 分111 13 分001(4) B的最大元為 6；極大元 6； B 的最小元無， 極小元為 2，3；上界和上確界為 6； 20 分 五、證明題( 每小題 5 分，共 10 分)1. 在一階邏輯中，構造下面推理的證明前提： x(F(x) G(x), x F(X) ； 結(jié)論： xG(x) 。證明：(1) x F(X)P6 / 112)F(a)T（1）EI(3) x(F(x) G(x) P ；(4) F(a) G(a) T(3)UI ； 2 分(5) G(a)T(2)(4)I ； 4 分(6) xG(x)T(5)E

13、G 。 5 分2. 設 A是集合，證明 A (A B) A證明： x A (A B) x A (x A x B) 3 分x A 5 分注：請用炭素墨水書寫、字跡要求工整、并抄寫在方框線內(nèi) 共 頁， 第 頁，7 / 11湖南科技大學瀟湘學院考試試題參考答案及評分細則（ 200 -200 學年第 學期） 離散數(shù)學 課程（A/B 卷）計算機，網(wǎng)絡工程 專業(yè) 班 級應試學生人數(shù) 實際考試學生人數(shù) 考試時量 100 分 鐘命題教師 李世群 審核人： 考試時間： 年 月 日8 / 11.判斷題（16分,每小題 2分）, 正確的打“” ，否則打“(1). (2). (3). (4). 二、填空題 (每小題

14、3 分，共 30分)4(1). 24 ;(2). 1;(4).1;(5). a;(7). ,1,2,1,2 ;(9). 000，011， 110， 111， 101;(5). (6). (7). (8). (3). 1,1 , 2,1 , 1,2 , 4,2 , 2,4 ; (6).偏序 ;(8). 1,1 , 1,2 , 2,1 , 2,2 _ (10). ( 1，3， 2)三、計算題（ 每小題 10 分，共 30 分 ）1. 求公式 p ( q r) 的主合取范式。解： p ( q r)(p q) (p r) 2 分(p q( r r) (p ( q q) r)5 分(p q r) (p

15、qr) (p qr)M1 M0M210 分2. ，求合式公式 xG(x) xH(x) 的前束范式。解： xG(x) xH(x)x G(x) xH(x)5 分x( G(x) H(x)10 分3將命題“每個人都要吃飯”在一階邏輯中符號化。解：設 m（x） : x是人; D（ x）： x要吃飯5 分每個人都要吃飯”在一階邏輯中符號化為：x(M (x) D(x)-10 分四.(15 分)R 1,1 1,2 , 1,3 ,1,4 , 1,5. , 1,6 , 2,2, 解： (1)3,3 , 4,4 , 5,5 , 6,6 , 2,4 , 2,6 , 3,6 5 分( 2) R的哈斯圖： 10 分9 / 11111111(3)010101M (R)00100100010000001000000115五、證明題（ 5分+4分，共 9 分）1. 在一階邏輯中，構造下面推理的證明前提： x(F(x) G(x), x F(X