離散數學複習資料和試題

離散數學複習資料和試題

集合論

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. 集合的計數問題：|A|=2 n (n是集合A的元素的個數)

| 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 根據對成閉包的定義及求解方法只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

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},{b},{c},{a,b},{b,c},{a,c},{ a,b,c } }上的「Í」是偏序關係，則（1）B={{a,b},{b,c},{b},{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種元素

最大元

最小元

極大元

極小元

上界

下界

上確界

下確界

12,24,36

2,3,6

無

2,3

6,12,24,36

無

24,36

無

2,3,6,12

無

2,3

12,24,36

無

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

解

最大元

無

最小元

無

極大元

a,b

d,e

極小元

a,b

上界

c,d,e,f,g,h

下界

無

a,b,c

上確界

下確界

無

代數系統

1. 代數系統單位元逆元素零元素

1.在實數集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

（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.在代數系統<N，+>中的單位元是：0

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

2. 找子群證明交換群

1.試證階為偶數的循環群中周期為2的元素個數一定是奇數

證明：設（G，*）是階為n的循環群，即|G|=n（n是偶數）。任取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的階數大於2時，a與它的逆元素總是成對出現的

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

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. 證明兩代數系統同構

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

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

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

2.證明兩個代數系統之間的同構關係就是等價關係

證：設<X , > <Y, *>和<Z ,+>為任意的三個代數系統

首先，<X ,

>≌<X ,

>，所以滿足自反性

其次，如果<X ,

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

有g(x1

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

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

x2= g—1(y1)

g—1(y2)；

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) Þ<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)

建立一個一一對應的函數 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 Þ x*a≠x*b （x∈G）一一映射下的函數就是一一對應函數

④Φ(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

根據數學歸納法得出（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，根據群的第二定義

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

圖論

1. 數量積

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

①通路

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

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

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

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

真子圖：則V＇ÍV且E＇ÌE

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

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

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

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點出發執行曬水任務，城市街道圖形如圖所示，試問是否存在一條曬水路線，是曬水車從A點出發通過所有街道且不重複最後回到車庫B15

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

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

命題邏輯

1. 判斷何為命題

判斷命題真假 ①

②公式真值表

邏輯演算

3. 命題符號化

4. 公式的真值指派

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

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

0 0 1

0 1 0

1 0 0

1 0 1

1 1 0

1 1 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）

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

0 0 1

0 1 0

1 0 0

1 0 1

1 1 0

1 1 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) ——含有三個簡單合取式的析取範式 (式子②)

根據式子②先求主析取範式 (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)

根據式子①先求合取取範式（(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. 在自然推理系統中構造下面的證明：若a為實數，則它不是有理數就是無理數，。若a不是能表示成分數，則它不是有理數。a是實數且他不能表示成分數，則他不是無理數。

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

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

結論：r

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

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

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

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

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

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

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

結論： r

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

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

⑤r ③④拒取式

4. 如果今天是星期天，我們就要到頤和園或圓明園去玩。如果頤和園人遊人太多，我們就不去頤和園玩。今天星期天。頤和園有人太多。所以我們去圓明園玩

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

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

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

結論：r

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

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

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

⑦r ③⑥析取三段論

《離散數學》試題及答案

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

1. 命題公式為 ( )

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

2．設P表示「天下大雨」， Q表示「他在室內運動」，則命題「除非天下大雨，否則他不在室內運動」符號化為（）。

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

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

(A) 1ÎA (B) {1,2, 3}Í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. 在「同學，老鄉，親戚，朋友」四個關係中_______是等價關係.

9. 寫出一個不含「」的邏輯聯結詞的完備集 .

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)∧QÞR®S

13.（10分）證明

與

，

與

等勢。

四、解答題(共35分)

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

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

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分)

7.{<6,3>,<8,4> } 8. 老鄉

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.

填對每個格得1分。

15.

P Q

PÙQ

ØP

ØQ

ØPÚØQ

(PÙQ)Ù(ØPÚØQ)

0 0

0 1

1 0

1 1

表中最後一列的數中，每對1個數得2分.

16. (2分)

(4分)

(6分)

(10分)

17. 解設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據題意應有：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分