離散數(shù)學復習資料和試題

集合論

1. 集合與集合之間的關系, 元素與集合之間的關系

1．判別下列各題是否正確：

（1）{1，2}í{1，2，3，{1，2，3}} 正確

（2）{p，q，r}í{ p，q，r ，{ p，q，r }} 正確

2．設有集合Ａ＝｛a,b,c｝，?為空集，則｛a｝íＡ

3．設S1=?，S2={?}，S3=ρ({?})，S3=ρ(?)，則：S2 ∈S4為假命題

2. 冪集：ρ（A）就是集合A中子集所組成的集合

求下列集合的冪集：

（1）{a，{a}}={?，{a}，{{a}}，{a，{a}}}

（2）{?，a，{a}}={?，{?}，{a}，{{a}}，{?，a}，{?，{a}}，{a，{a}}，{?，a，{a}}}

3. 集合的運算：10組集合恒等式：

1） 交換率：A∪B=B∪A；A∩B=B∩A

2） 結合律：A∪（B∪C）=（A∪B）∪C；A∩（B∩C）=（A∩B）∩C

3） 分配律：A∪（B∩C）=（A∪B）∩（A∪C）；A∩（B∪C）=（A∩B）∪（A∩C）

4） 同一律：A∪?=A；A∩E=A

5） 零一律：A∩?=?；A∪E=E

6） 互補率：A∪~A=E；A∩~A=?；~E=?；~?=E

7） 雙重否定率：~~A=A

8） 冪等率：A∪A=A；A∩A=A

9） 吸收率：A∪（A∩B）=A；A∩（A∪B）=A

10） 德摩根率：~（A∪B）=~A∩~B；~（A∩B）=~A∪~B

交：A∩B；并：A∪B；差運算：A—B（屬于A不屬于B）；補運算：~A；

對稱差運算：A?B；笛卡兒乘積：A×B={<a，b>|a∈A，b∈B}

設A={a，b，c}，B={b，d，e}則A—B={a，c}，A?B={a，c，d，e}

4. 集合的計數(shù)問題：|A|=2 n (n是集合A的元素的個數(shù))

| A∪B |=|A|+|B|—| A∩B |；|A∪B∪C|=|A|+|B|+|C|—| A∩B |—| A∩C |—|B∩C|+| A∩B∩C |

5. 關系的性質:①由圖寫出性質

②有性質畫圖

③由關系集合寫性質

（自反性，反自反性，對稱性，反對稱性，傳遞性：）P34 ##2.6

用圖表示出來的在集合X={1，2，3}上的關系的6個圖形，從圖中可以清楚的看出：

（1） R1 是自反的、對稱的、又是傳遞的（它是一個全關系）；

（2） R2是反自反的、反對稱的

（3） R3不是反自反的、反對稱的

（4） R4是自反的、反對稱的

（5） R5是反自反的、對稱的、反對稱的、傳遞的（它是一個空關系）

6. 映射與關系

6．設集合A={a1，a2，a3，a4}，B={ b1，b2，b3}，σ={〈a1，b2〉，〈a2，b2〉，〈a3，b1〉，〈a4，b3〉}則σ是滿射但不是單射

7. 關系的閉包：r(R)=R∪IA┎ ；s(R)=R∪~R；t(R)=R∪R 1∪R 2∪R 3……∪R n

1．設A={a，b，c}，R1、R2是A上的二元關系：

R1={〈a，a〉，〈b，b〉，〈b，c〉，〈d，d〉}

R2={〈a，a〉，〈b，b〉，〈b，c〉，〈c，b〉，〈d，d〉}試證明R1是R2的何種閉包

解：R1∪~R1 ={〈a，a〉，〈b，b〉，〈b，c〉，〈d，d }，〈c，b〉}

即有R1∪~R1= R2 根據(jù)對成閉包的定義及求解方法只R2是R1 的對稱閉包

2.設集合A={a，b，c，d}，定義R={〈a，b〉，〈b，a〉，〈b，c〉，〈c，d〉}求r(R)，s(R)，t(R)

解：r(R)= {〈a，a〉，〈b，b〉，〈c，c〉，〈d，d〉，〈a，b〉，〈b，a〉，〈b，c〉，〈c，d〉}

s(R)={ 〈a，b〉，〈b，a〉，〈b，c〉，〈c，b〉，〈c，d〉，〈d，c〉}

t(R)={ 〈a，a〉，〈b，b〉，〈a，b〉，〈a，c〉，〈a，d〉，〈b，a〉，〈b，c〉，〈b，d〉，〈c，d〉}

3.由關系集合寫性質

設A={a，b，c}，R={〈a，a〉，〈b，b〉}，具有反對稱性

8. 關系的運算(復合運算) R1

R2

1.設X={0，1，2，3}，X上有兩個關系：R1={〈i，j〉|j=i+1或j=i/2}；R2={〈i，j〉|i=j+2}

求復合關系：R1R2

R1={ 〈0，1〉，〈1，2〉，〈2，3〉，〈0，0〉，〈2，1〉}，R2= {〈2，0〉，〈3，1〉}則有：

R1R2= {〈1，0〉，〈2，1〉}

2.設R1，R2是集合A={1，2，3，4}上的二元關系，其中R1={〈1，1〉，〈1，2〉，〈2，4〉}，R2={〈1，4〉，〈2，3〉，〈2，4〉，〈3，2〉}，試求：R1R2

解：R1R2=〈1，4〉，〈1，3〉}

9. 特殊關系 等價關系:

1.A={0,1,2,4,5,8,9},R為A上模為4的同余關系，求(1)R的所有等價類

(2)畫出R的關系圖

解：R={ 〈0，0〉，〈1，1〉，〈2，2〉，……，〈9，9〉，〈0，4〉，〈4，0〉，〈1，5〉，〈5，1〉，〈4，8〉，〈8，4〉，〈5，9〉，〈9，5〉，〈0，8〉，〈8，0〉，〈1，9〉，〈9，1〉}

(1)[0]R={0,4,8}=[4]R=[8]R; [1]R={1,5,9}=[5]R = [9]R ; [2]R ={2}

(2)

2. A={a,b,c,d} A的等價關系R={〈a，a〉，〈b，b〉，〈c，c〉，〈d，d〉，〈a，b〉，〈b，a〉，〈8，4〉，〈c，d〉，〈d，c〉} 求（1）圖 （2）A的等價類 （3）A/R (商集)

解：（1）

（2）[a]R=[b]R={a,b} [c]R=[d]R={c,d} (3)A/R={{a,b},{c,d}}

3.A={,1,2,4,……,24}上定義R={<x,y>|x，y∈A，且（x—y）能被12整除}

(1)寫出R (2)畫圖 (3)證明R是等價關系

解：(1)R={<1，1>,<2，2>,……<24，24>,<1，13>,<2，14>,……<12，24>,<24，12>}

(2)

(3)(定義法)若證明R為等價關系，只需證明R具有自反性，對稱性，傳遞性

①自反性： "x∈A，則<x，x>∈R 所以R具有自反性

②對稱性： 若<x，y>∈R，則12|(x—y)，y—x=(—x+y)

所以12|(y—x)，故<y,x>∈R，所以R具有對稱性

③傳遞性： 如果<x，y>∈R，且<y，z>∈R，則12|(x—y)且12|(y—z)

則x—z=(x—y)+(y—z)能被12整除，故12|(x—z)，<x，z>∈R

所以R具有傳遞性

綜上所述，R為等價關系

偏序關系

1.集合X={2,3,6,8},上的整除關系R={〈2，2〉，〈3，3〉，〈6，6〉，〈8，8〉，〈2，6〉，〈2，8〉，〈3，6〉}是偏序的，求其哈斯圖

2.集合A={2，3，6，12，24，36}上的整除關系R是偏序的，它可用哈斯圖表示

R={〈2，2〉，〈3，3〉，〈6，6〉，〈12，12〉，〈24，24〉，〈36，36〉，

〈2，6〉，〈3，6〉，〈6，12〉，〈12，24〉，

〈2，12〉，〈3，12〉，〈6，24〉，〈12，36〉

〈2，24〉，〈3，24〉，〈6，36〉，

〈2，36〉，〈3，36〉}

求特殊關系

1.設A={a,b,c}的冪集ρ(A)={ ?,{a},,{c},{a,b},{b,c},{a,c},{ a,b,c } }上的“í”是偏序關系，則（1）B={{a,b},{b,c},,{c},?} (2)B={{a}，{c}}，求8種特殊關系

解：（1）不$y∈B,"y’ íy，故無罪最大元，最小元是?；

極大元為{a,b},{b,c}；極小元為?；上界和上確界均{ a,b,c }；下界下確界均為?

（2）無最大最小元；極大元和極小元均為{a}，{c}；

上界為,{a,c},{ a,b,c }；上確界為{ a,c }；下界和下確界均為?；

2.集合A={2，3，6，12，24，36},其中“≤”為A上的整除關系R

1） 畫出一般的關系圖和哈斯圖 2）設B1={6,12} B2={2,3} B3={24,36} B4={2,3,6,12}為A的子集試求出B1 B2 B3 B4 8種元素

最大元

最小元

極大元

極小元

上界

下界

上確界

下確界

B1

12

6

12

6

12,24,36

2,3,6

12

6

B2

無

無

2,3

2,3

6,12,24,36

無

6

無

B3

無

無

24,36

24,36

無

2,3,6,12

無

12

B4

12

無

12

2,3

12,24,36

無

12

無

3.A={a,b,c,d,e,f,g,h}，對應的哈斯圖如下；令B1={a,b}，B2={c,d,e}，求B1 B2 8種元素

解

B1

B2

最大元

無

無

最小元

無

c

極大元

a,b

d,e

極小元

a,b

c

上界

c,d,e,f,g,h

h

下界

無

a,b,c

上確界

c

h

下確界

無

c

代數(shù)系統(tǒng)

1. 代數(shù)系統(tǒng) 單位元 逆元素 零元素

1.在實數(shù)集R上定義二元關系“*”：“”如下：x*y=x+y—xy，xy=1/2（x+y）

（1）x*y是否滿足結合律、交換率？是否有單位元及逆元？

（2）xy是否滿足結合律、交換率？是否有單位元及逆元？

解：因為（1）（x*y）*z=（x+y—xy）*z=x+y—xy+z—xz—yz+xyz

x*（y*z）= x*（y+z—yz）=x+y—xy+z—xz—yz+xyz滿足結合率

x*y= x+y—xy；y*x= y+x—xy滿足交換率

x*0= x+0—x 0= 0+x—0 x=x所以單位元是 0

x*x —1=x+ x —1—x x —1 =0所以x —1 = —x /（1—x） （x≠1）

所以對于R—{1}的所有x均有逆元素—x /（1—x）

（2）因為（xy）z=1/2（x+y）z=1/2（1/2（x+y）+z）=1/4 x+1/4 y+1/2 z

x

（y

z）= x

1/2（y+z）=1/4 y+1/4 z+1/2 x 所以不滿足結合律

又因為xy=1/2（x+y），yx=1/2（x+y）所以滿足交換率；不存在單位元素和逆元素

2.在代數(shù)系統(tǒng)<N，+>中的單位元是：0

3.設A是非空集合<ρ(A)，∪，∩> 中, ρ(A)對運算∪的單位元是?，ρ(A)對運算∩的單位元是Ａ

2. 找子群 證明交換群

1.試證階為偶數(shù)的循環(huán)群中周期為2的元素個數(shù)一定是奇數(shù)

證明：設（G，*）是階為n的循環(huán)群，即|G|=n（n是偶數(shù)）。任取a∈G，an=e（m>2）,a的階為m,a的逆元素a —1∈G，故（a —1）m=（a m）—1=e—1=e，由群的性質，知a —1 的階也是m，則必定有 a≠a —1

反證法，若a≠a —1，則a2 =e，所以a的階不大于2，這與m>2矛盾，所以a≠a —1，即當a的階數(shù)大于2時，a與它的逆元素總是成對出現(xiàn)的

又因為群中唯一的單位元素e的階為1，此時階大于2的元素個數(shù)是偶數(shù)，加上單位元e，個數(shù)為奇數(shù)了，剩下的那些階為2的元素個數(shù)必須是奇數(shù)，才能滿足所給條件n是偶數(shù)，得證

2.找出（Z12 , ?12）的所有子群

解：(1)1階子群（[0], ?12）

(2)2階子群（{[0],[6]} ?12）

(3)3階子群（{[0],[4],[8]}, ?12）

(4)4階子群（{[0],[3],[6],[9]}, ?12）

(5)6階子群（{[0],[2],[4],[6],[8],[10],} ?12）

(6)12階子群（Z1.2 , ?1.2）

3.設群中每個元素的逆元素是其自身的，則G是一個交換群

證明：對于任意的a，b∈G由a*b∈G,因為一個元素的逆元素就是其自己，于是

a*b=（a*b）—1 = b—1 *a—1=b*a，所以G是交換群

3. 計算置換

設M={1,2,3}，σ與Τ是M的置換：σ= 1 2 3 ，Τ= 1 2 3

2 3 1 3 2 1

求σ—1，σΤ，Τσ，Τ—1

σ—1= 1 2 3 σΤ= 1 2 3 1 2 3 = 1 2 3

3 1 2 2 3 1 3 2 1 2 1 3

Τσ= 1 2 3 1 2 3 = 1 2 3

3 2 1 2 3 1 1 3 2

Τ—1= 1 2 3

3 2 1

4. 證明兩代數(shù)系統(tǒng)同構

1.證明<R+ , ×>和<R ,+>同構

證：設g：R+ →R，g(x)=ln x 顯然g(x)=ln x為一一對應的函數(shù)ln (x1 x2)= ln x1+ ln x2

得 g(x1 x2)= g(x1)+ g(x2) (x1， x2∈x) 所以證明<R+ , ×>和<R ,+>同構

2.證明兩個代數(shù)系統(tǒng)之間的同構關系就是等價關系

證：設<X , > <Y, *>和<Z ,+>為任意的三個代數(shù)系統(tǒng)

首先，<X ,

>≌<X ,

>， 所以滿足自反性

其次，如果<X ,

>≌ <Y, *>，即存在g：X→Y，使得," x1 ， x2∈X，

有g(x1

x2)= g(x1) * g(x2) 由g為一一對應的函數(shù)，所以存在g—1：Y→X，

"y1 y2∈Y1 g—1(y1) =x1 g—1(y2)=x2 x1

x2= g—1(y1)

g—1(y2)；

x1

x2= g—1(g(x1

x2))= g—1(g(x1) * g(x2))= g—1(y1 * y2)

所以 g—1(y1 * y2) = g—1(y1)

g—1(y2) T<X ,

>≌ <Y, *>

最后，如果<X ,

>≌ <Y, *>，<Y, *>≌ <Z ,+> 只需要證<X ,

>≌<Z ,+>

即存在g：X→Y，使得" x1 ， x2∈X，均有g(x1

x2)= g(x1) * g(x2)

存在h：Y→Z，使得 " y1 ， y2∈Y，均有 h(y1* y2)= h(y1) + h(y2)

建立一個一一對應的函數(shù) f：h

g：X→Z

" x1 ， x2∈X f(x1 x2)= hg(x1 x2)= h (g(x1) * g(x2)) = h g(x1) +h g(x2) = f(x1)*f( x2)

綜上所述同構關系就是等價關系

3.任何一個群與一個變換群同構

證明：設群為<G，*>, " a ∈G,可定義變換τa（x） →x*a,做集合G＇

下面證明<G＇，>≌<G，*>

即找出Φ：Ｇ →G＇使得" a，ｂ∈G有Φ(a*b)=Φ(a) Φ(b)

①a=b，τa=τb 說明是映射

②"τa∈G＇$ a∈G,使得τa(x)=x*a 說明是漫射

③" a，ｂ∈G，且a≠b T x*a≠x*b （x∈G） 一一映射下的函數(shù)就是一一對應函數(shù)

④Φ(a*b)= τ(a*b)=x*(a*b)=(x*a)*b=τb(τa(x))=( τa*τb)(x)= Φ(a) Φ(b)

所以是同構

/*這里額外說明一下：設f：A→B，g：B→C fg：A→C （fg)(x)=g[f(x)] */

4.設G為群，若"x∈G，又x2=e 證G為交換群

證明：由"x∈G，有x2=e，所以x=x—1 ， 存在逆元素

(xy)(y—1x—1)=e 得x x—1=e 滿足結合律

"x，y∈G，xy=(xy）—1=y—1x—1=yx 滿足交換律

5.若<G，*>為可交換半群，則"a，b∈G，必有（a*b）n= an * bn

證明：（a*b）2= a2 * b2 "a，b∈G，

（a*b）2 =（a* b）*（a* b）= a* （b*a）* b= a*（a * b）* b= (a*a )*( b* b) = a2 * b2

根據(jù)數(shù)學歸納法得出 （a*b）n= an * bn

6.設Ｇ為群，H，K為G的子群，證H∩K也為G的子群

1）首先證明G是非空的，

由于H, K均為G的子集，e∈H∩K，所以H∩K非空

2）"a，b∈H∩K，

a∈H，a∈K，b∈H，b∈K

又因為H為G的子群，則a b—1∈H，且在H中有唯一解，

同理得，a b—1∈K，根據(jù)群的第二定義

綜上所述，得出，H，K為G的子群，證H∩K也為G的子群

圖論

1. 數(shù)量積

基本通路:：（n，m）圖,基本通路的長度——≤n—1

①通路

基本回路：（n，m）圖，基本回路的長度——≤n

②（n，m）的完全圖Kn，m和n的關系

2.

生成子圖：則V＇=V且E＇=E

子圖：則V＇íV且E＇íE ＜V＇，E＇＞是＜V，E＞

真子圖：則V＇íV且E＇ìE

3. 應用：歐拉圖　歐拉通路

1. 郵遞員從郵局v1出發(fā)沿由路投遞信件，其郵路圖所示，試問是否存在一條投遞路線使郵遞員從郵局出發(fā)通過所有路線而不重復且最后回到郵局

解：由于圖中每個結點的次數(shù)均為偶次數(shù)，由定理知這樣的路線一定是存在的

C（v1, v 5 v 11 v 7 v 12 v 8 v 10 v 6 v 9 v 11 v 12 v 10 v 9 v 5 v 2 v 6 v 4 v 8 v 3 v 7 v 1）

2. 曬水車從A點出發(fā)執(zhí)行曬水任務，城市街道圖形如圖所示，試問是否存在一條曬水路線，是曬水車從A點出發(fā)通過所有街道且不重復最后回到車庫B15

解：問題的變形是問AB之間是否存在歐拉通路，由于圖中每個結點除、了A、B為奇數(shù)外其余均為偶次數(shù)，由定理可知這樣一條曬水路線使存在的

P=（A,C,D,E,F,B,G,C,F,G,A,B）

命題邏輯

1. 判斷何為命題

2.

判斷命題真假 ①

②公式 真值表

邏輯演算

3. 命題符號化

4. 公式的真值指派

1. 下列命題公式 ┐（P∧(Q→┐P) ）記做G，使G的真值指派為F的P，Q的真值是：（T，F(xiàn)）

2. 設命題公式G=P∧ (┐Q∨R),則使G得真值指派為T的是：TTT,TFT,TTF

3. （┐p∧q)→┐r

p, q, r

┐p

（┐p∧q)

┐r

（┐p∧q)→┐r

0 0 0

1

0

1

1

0 0 1

1

0

0

1

0 1 0

1

1

1

1

1 0 0

1

1

0

0

1 0 1

0

0

1

1

1 1 0

0

0

0

1

1 1 0

0

0

1

1

1 1 1

0

0

0

1

4. （1）（p→┐p) ∧q→┐q 均為成真賦值 （2）┐（p→q) ∧q∧r 均為成假賦值

5. 化簡公式：

化簡下列公式（1）（┐P∧Q) ∨（┐P∧┐Q） （2）Q→（P∨（P∧Q）

解：(1)（┐P∧Q) ∨（┐P∧┐Q） (2) Q→（P∨（P∧Q）

=（Q∧┐P) ∨（┐Q∧┐P） =(┐Q∨P) ∨P

=（Q ∨┐Q）∧┐P = Q→P

=1∧┐P

=┐P

6. 求主范式

1.命題公式 ┐（(P∧(Q→┐P)）記做G，使G的真值指派為F的P，Q的真值是：（T，F(xiàn)）

2.設命題公式G=P∧ (┐Q∨R),則使G得真值指派為T的是：TTT,TFT,TFF

3.（┐p∧q)→┐r

p, q, r

┐p

（┐p∧q)

┐r

（┐p∧q)→┐r

0 0 0

1

0

1

1

0 0 1

1

0

0

1

0 1 0

1

1

1

1

1 0 0

1

1

0

0

1 0 1

0

0

1

1

1 1 0

0

0

0

1

1 1 0

0

0

1

1

1 1 1

0

0

0

1

4.（1）（p→┐p) ∧q→┐q 均為永真式 （2）┐（p→q) ∧q∧r 均為永假式

21．( p→q) r

法一： （┐p∨q) r

=（(┐p∨q) → r）∧（r →(┐p∨q)）

=（┐(┐p∨q) ∨r）∧（┐r∨ (┐p∨q)）

=（(p∨┐q) ∨r）∧（┐r∨ ┐p∨q）

=（(p∨r）∧（┐q∨r ）∧(┐p∨q ∨┐r) ——含有三個簡單析取式的合取范式 (式子①)

=（(p∧┐q) ∧┐r）∨(p∧┐q∧┐p)∨(p∧┐q∧q)∨(r∧┐r)∨(r∧┐p) ∨(r∧q)

=(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) ——含有三個簡單合取式的析取范式 (式子②)

根據(jù)式子②先求主析取范式 (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r )

=(p∧┐q∧┐r)∨(┐p∧（q∨┐q）∧r)∨(r∧（p∨┐p）∧q)

=(p∧┐q∧┐r)∨(┐p∧q∧r) ∨（┐p∧┐q∧r)）∨(r∧p∧q) ∨（r∧┐p∧q）

=(p∧┐q∧┐r) ∨(┐p∧q∧r) ∨（┐p∧┐q∧r)） ∨(r∧p∧q)

1 0 0 (m4) 0 1 1(m3) 0 0 1(m1) 1 1 1(m7)

根據(jù)式子①先求合取取范式 （(p∨r）∧（┐q∨r ）∧(┐p∨q ∨┐r)

=（(p∨（q∧┐q）∨r）∧（┐q∨（p∧┐p）∨r ）∧(┐p∨q ∨┐r)

=（(p∨q∨r）∧（p∨┐q∨r）∧（┐q∨p∨r ）∧（┐q∨┐p∨r）∧(┐p∨q ∨┐r)

=（(p∨q∨r）∧（p∨┐q∨r）∧（┐q∨┐p∨r）∧(┐p∨q ∨┐r)

0 0 0(M0) 0 1 0(M2) 1 1 0(M6) 1 0 1(M5)

法二：真值表

p, q r

( p→q) r

主析取范式

=m4∨m3∨m1∨m7

主合取范式

= M0∧M2∧M6∧M5

0 0 0

1 0

0 0 1

1 1

0 1 0

1 0

0 1 1

1 1

1 0 0

0 1

1 0 1

0 0

1 1 0

1 0

1 1 1

1 1

7. 在自然推理中的證明

1. 在自然推理中構造下列證明：

前提：┐p∨q，r∨┐q，r→s；

結論：p→s

證明：①┐p∨q 前提引入 ②p→q ①置換

③r∨┐q前提引入 ④q→r ③置換

⑤r→s 前提引入 ⑥q→s ④⑤假言三段論

⑦p→s ②⑥假言三段論

2. 在自然推理系統(tǒng)中構造下面的證明：若a為實數(shù)，則它不是有理數(shù)就是無理數(shù)，。若a不是能表示成分數(shù)，則它不是有理數(shù)。a是實數(shù)且他不能表示成分數(shù)，則他不是無理數(shù)。

解： 設p：a為實數(shù)；q：a為有理數(shù)；r：a為無理數(shù)；s：a能表示成分數(shù)

前提：p→（q∨r），┐s→┐q，p∧┐s；

結論：r

證明： ①p∧┐s 前提引入 ②p ①化簡

③┐s ①化簡 ④p→（q∨r）前提引入

⑤q∨r ②④假言推理 ⑥s→┐q 前提引入

⑦┐q ③⑥假言推理 ⑧r ⑤⑦析取三段論

3. 如果“小王是理科生，則他的數(shù)學成績一定很好。如果小王不是文科生，他一定是理科生。小王的數(shù)學不好。所以他是文科生

解：p：小王是理科生 q：他的數(shù)學成績很好 r：小王是文科生

前提：p→q ┐r→p ┐q

結論： r

證明：①p→q 前提引入 ②┐q 前提引入

③┐p ①②拒取 ④┐r→p 前提引入

⑤r ③④拒取式

4. 如果今天是星期天，我們就要到頤和園或圓明園去玩。如果頤和園人游人太多，我們就不去頤和園玩。今天星期天。頤和園有人太多。所以我們?nèi)A明園玩

解：設p：今天是星期天 q：到頤和園玩

r：到圓明園玩 s：頤和園人太多

前提：p→（q∨r）， s→┐q， p，s

結論：r

證明： ①s→┐q 前提引入 ②s 前提引入

③┐q ①②假言推理 ④p→（q∨r） 前提引入

⑤p 前提引入 ⑥q∨r ④⑤假言推理

⑦r ③⑥析取三段論

《離散數(shù)學》試題及答案

一、選擇題：本題共5小題，每小題3分，共15分，在每小題給出的四個選項中，只有一項是符合題目要求的。

1. 命題公式為 ( )

(A) 矛盾式 (B) 可滿足式 (C) 重言式 (D) 合取范式

2．設P表示“天下大雨”， Q表示“他在室內(nèi)運動”，則命題“除非天下大雨，否則他不在室內(nèi)運動”符號化為（ ）。

(A)． ；　(B)．；　　(C)．；　(D)．．

3.設集合A={{1,2,3}, {4,5}, {6,7,8}}，則下式為真的是( )

(A) 1?A (B) {1,2, 3}íA

(C) {{4,5}}ìA (D) ??A

4. 設A＝{1,2},B={a,b,c},C={c,d}, 則A×(B?C)= ( )

(A) {<1,c>,<2,c>} (B) {<c,1>,<2,c>} (C) {<c,1><c,2>,} (D) {<1,c>,<c,2>}

5. 設G如右圖：那么G不是( ).

(A)哈密頓圖； (B)完全圖；

(C)歐拉圖； (D) 平面圖.

二、填空題：本大題共5小題，每小題4分，共20分。把答案填在對應題號后的橫線上。

6. 設集合A={?,{a}}，則A的冪集P(A)=

7. 設集合A={1,2,3,4 }, B={6,8,12}, A到B的關系R＝,

那么R－1＝

8. 在“同學，老鄉(xiāng)，親戚，朋友”四個關系中_______是等價關系.

9. 寫出一個不含“”的邏輯聯(lián)結詞的完備集 .

10.設X＝{a,b,c}，R是X上的二元關系，其關系矩陣為

MR＝，那么R的關系圖為

三、證明題（共30分）

11. （10分）已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C)

12. （10分）構造證明：(P?(Q?S))∧(?R∨P)∧QTR?S

13.（10分）證明

與

，

與

等勢。

四、解答題(共35分)

14.（7分）構造三階幻方（以1為首項的9個連續(xù)自然數(shù)正好布滿一個

方陣，且方陣中的每一行, 每一列及主、副對角線上的各數(shù)之和都相等.）

15.（8分） 求命題公式的真值表.

16.（10分）設R1是A1＝{1,2}到A2＝(a,b,c)的二元關系，R2是A2到A3＝{}的二元關系，R1= {<1,a>,<1,b>,<2,c>}, R2={<a,b>,<b,b>}

求R1·R2的集合表達式.

17.（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？

三個條件：(1)若A去，則C和D中要去1個人；(2)B和C不能都去；

(3)若C去，則D留下。

一、單項選擇題(每小題3分，共15分)

1.B 2.C 3. C 4.A 5.B

二、填空題(每小題4分，共20分)

6.

7.{<6,3>,<8,4> } 8. 老鄉(xiāng)

9.或 或 或

10. 見第10題答案圖.

11.證明：∵x? A∩（B∪C）? x? A∧x?（B∪C） 2分

? x? A∧（x?B∨x?C） 3分

?（ x? A∧x?B）∨（x? A∧x?C） 5分

? x?（A∩B）∨x? A∩C 7分

? x?（A∩B）∪（A∩C） 9分

∴A∩（B∪C）=（A∩B）∪（A∩C） 10分

12.證明：（1）R 附加前提

（2）?R∨P P 2分

（3）P T(1)(2)，I 3分

（4）P?(Q?S) P 4分

（5）Q?S T(3)(4)，I 5分

（6）Q P 6分

（7）S T(5)(6)，I 8分

（8）R?S CP 10分

13. 證明：a) 設，作如下： 2分

5分

b) 設，作如下： 7分

10分

14.

4

9

2

3

5

7

8

1

6

填對每個格得1分。

15.

P Q

PùQ

?P

?Q

?Pú?Q

(PùQ)ù(?Pú?Q)

0 0

0

1

1

1

0

0 1

0

1

0

1

0

1 0

0

0

1

1

0

1 1

1

0

0

0

0

表中最后一列的數(shù)中，每對1個數(shù)得2分.

16. (2分)

(4分)

(6分)

(10分)

17. 解 設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應有：A?C?D，?(B∧C)，C??D必須同時成立。 2分

因此(A?C?D)∧?(B∧C)∧(C??D)

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))

?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)

∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)

?T 8分

故有三種派法：B∧D，A∧C，A∧D。 10分