離散數(shù)學(xué)復(fù)習(xí)資料和試題

集合論

1. 集合與集合之間的關(guān)系, 元素與集合之間的關(guān)系

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

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

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

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

3．設(shè)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. 集合的運(yùn)算：10組集合恒等式：

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

2） 結(jié)合律：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） 互補(bǔ)率：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；差運(yùn)算：A—B（屬于A不屬于B）；補(bǔ)運(yùn)算：~A；

對(duì)稱(chēng)差運(yùn)算：A?B；笛卡兒乘積：A×B={<a，b>|a∈A，b∈B}

設(shè)A={a，b，c}，B={b，d，e}則A—B={a，c}，A?B={a，c，d，e}

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

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

5. 關(guān)系的性質(zhì):①由圖寫(xiě)出性質(zhì)

②有性質(zhì)畫(huà)圖

③由關(guān)系集合寫(xiě)性質(zhì)

（自反性，反自反性，對(duì)稱(chēng)性，反對(duì)稱(chēng)性，傳遞性：）P34 ##2.6

用圖表示出來(lái)的在集合X={1，2，3}上的關(guān)系的6個(gè)圖形，從圖中可以清楚的看出：

（1） R1 是自反的、對(duì)稱(chēng)的、又是傳遞的（它是一個(gè)全關(guān)系）；

（2） R2是反自反的、反對(duì)稱(chēng)的

（3） R3不是反自反的、反對(duì)稱(chēng)的

（4） R4是自反的、反對(duì)稱(chēng)的

（5） R5是反自反的、對(duì)稱(chēng)的、反對(duì)稱(chēng)的、傳遞的（它是一個(gè)空關(guān)系）

6. 映射與關(guān)系

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

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

1．設(shè)A={a，b，c}，R1、R2是A上的二元關(guān)系：

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ù)對(duì)成閉包的定義及求解方法只R2是R1 的對(duì)稱(chēng)閉包

2.設(shè)集合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.由關(guān)系集合寫(xiě)性質(zhì)

設(shè)A={a，b，c}，R={〈a，a〉，〈b，b〉}，具有反對(duì)稱(chēng)性

8. 關(guān)系的運(yùn)算(復(fù)合運(yùn)算) R1

R2

1.設(shè)X={0，1，2，3}，X上有兩個(gè)關(guān)系：R1={〈i，j〉|j=i+1或j=i/2}；R2={〈i，j〉|i=j+2}

求復(fù)合關(guān)系：R1R2

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

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

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

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

9. 特殊關(guān)系 等價(jià)關(guān)系:

1.A={0,1,2,4,5,8,9},R為A上模為4的同余關(guān)系，求(1)R的所有等價(jià)類(lèi)

(2)畫(huà)出R的關(guān)系圖

解：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的等價(jià)關(guān)系R={〈a，a〉，〈b，b〉，〈c，c〉，〈d，d〉，〈a，b〉，〈b，a〉，〈8，4〉，〈c，d〉，〈d，c〉} 求（1）圖 （2）A的等價(jià)類(lèi) （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)寫(xiě)出R (2)畫(huà)圖 (3)證明R是等價(jià)關(guān)系

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

(2)

(3)(定義法)若證明R為等價(jià)關(guān)系，只需證明R具有自反性，對(duì)稱(chēng)性，傳遞性

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

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

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

③傳遞性： 如果<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為等價(jià)關(guān)系

偏序關(guān)系

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

2.集合A={2，3，6，12，24，36}上的整除關(guān)系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〉}

求特殊關(guān)系

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

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

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

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

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

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

1） 畫(huà)出一般的關(guān)系圖和哈斯圖 2）設(shè)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

無(wú)

無(wú)

2,3

2,3

6,12,24,36

無(wú)

6

無(wú)

B3

無(wú)

無(wú)

24,36

24,36

無(wú)

2,3,6,12

無(wú)

12

B4

12

無(wú)

12

2,3

12,24,36

無(wú)

12

無(wú)

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

解

B1

B2

最大元

無(wú)

無(wú)

最小元

無(wú)

c

極大元

a,b

d,e

極小元

a,b

c

上界

c,d,e,f,g,h

h

下界

無(wú)

a,b,c

上確界

c

h

下確界

無(wú)

c

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

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

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

（1）x*y是否滿(mǎn)足結(jié)合律、交換率？是否有單位元及逆元？

（2）xy是否滿(mǎn)足結(jié)合律、交換率？是否有單位元及逆元？

解：因?yàn)椋?）（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滿(mǎn)足結(jié)合率

x*y= x+y—xy；y*x= y+x—xy滿(mǎn)足交換率

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）

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

（2）因?yàn)椋▁y）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 所以不滿(mǎn)足結(jié)合律

又因?yàn)閤y=1/2（x+y），yx=1/2（x+y）所以滿(mǎn)足交換率；不存在單位元素和逆元素

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

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

2. 找子群 證明交換群

1.試證階為偶數(shù)的循環(huán)群中周期為2的元素個(gè)數(shù)一定是奇數(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，由群的性質(zhì)，知a —1 的階也是m，則必定有 a≠a —1

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

又因?yàn)槿褐形ㄒ坏膯挝辉豦的階為1，此時(shí)階大于2的元素個(gè)數(shù)是偶數(shù)，加上單位元e，個(gè)數(shù)為奇數(shù)了，剩下的那些階為2的元素個(gè)數(shù)必須是奇數(shù)，才能滿(mǎn)足所給條件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.設(shè)群中每個(gè)元素的逆元素是其自身的，則G是一個(gè)交換群

證明：對(duì)于任意的a，b∈G由a*b∈G,因?yàn)橐粋€(gè)元素的逆元素就是其自己，于是

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

3. 計(jì)算置換

設(shè)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)同構(gòu)

1.證明<R+ , ×>和<R ,+>同構(gòu)

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

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

2.證明兩個(gè)代數(shù)系統(tǒng)之間的同構(gòu)關(guān)系就是等價(jià)關(guān)系

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

首先，<X ,

>≌<X ,

>， 所以滿(mǎn)足自反性

其次，如果<X ,

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

有g(shù)(x1

x2)= g(x1) * g(x2) 由g為一一對(duì)應(yīng)的函數(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(shù)(x1

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

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

建立一個(gè)一一對(duì)應(yīng)的函數(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)

綜上所述同構(gòu)關(guān)系就是等價(jià)關(guān)系

3.任何一個(gè)群與一個(gè)變換群同構(gòu)

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

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

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

①a=b，τa=τb 說(shuō)明是映射

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

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

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

所以是同構(gòu)

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

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

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

(xy)(y—1x—1)=e 得x x—1=e 滿(mǎn)足結(jié)合律

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

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ù)學(xué)歸納法得出 （a*b）n= an * bn

6.設(shè)Ｇ為群，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

又因?yàn)镠為G的子群，則a b—1∈H，且在H中有唯一解，

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

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

圖論

1. 數(shù)量積

基本通路:：（n，m）圖,基本通路的長(zhǎng)度——≤n—1

①通路

基本回路：（n，m）圖，基本回路的長(zhǎng)度——≤n

②（n，m）的完全圖Kn，m和n的關(guān)系

2.

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

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

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

3. 應(yīng)用：歐拉圖　歐拉通路

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

解：由于圖中每個(gè)結(jié)點(diǎn)的次數(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. 曬水車(chē)從A點(diǎn)出發(fā)執(zhí)行曬水任務(wù)，城市街道圖形如圖所示，試問(wèn)是否存在一條曬水路線，是曬水車(chē)從A點(diǎn)出發(fā)通過(guò)所有街道且不重復(fù)最后回到車(chē)庫(kù)B15

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

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

命題邏輯

1. 判斷何為命題

2.

判斷命題真假 ①

②公式 真值表

邏輯演算

3. 命題符號(hào)化

4. 公式的真值指派

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

2. 設(shè)命題公式G=P∧ (┐Q∨R),則使G得真值指派為T(mén)的是：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. 化簡(jiǎn)公式：

化簡(jiǎn)下列公式（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.設(shè)命題公式G=P∧ (┐Q∨R),則使G得真值指派為T(mén)的是：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) ——含有三個(gè)簡(jiǎn)單析取式的合取范式 (式子①)

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

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

根據(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. 在自然推理中構(gòu)造下列證明：

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

結(jié)論：p→s

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

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

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

⑦p→s ②⑥假言三段論

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

解： 設(shè)p：a為實(shí)數(shù)；q：a為有理數(shù)；r：a為無(wú)理數(shù)；s：a能表示成分?jǐn)?shù)

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

結(jié)論：r

證明： ①p∧┐s 前提引入 ②p ①化簡(jiǎn)

③┐s ①化簡(jiǎn) ④p→（q∨r）前提引入

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

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

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

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

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

結(jié)論： r

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

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

⑤r ③④拒取式

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

解：設(shè)p：今天是星期天 q：到頤和園玩

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

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

結(jié)論：r

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

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

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

⑦r ③⑥析取三段論

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

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

1. 命題公式為 ( )

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

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

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

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

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

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

4. 設(shè)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. 設(shè)G如右圖：那么G不是( ).

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

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

二、填空題：本大題共5小題，每小題4分，共20分。把答案填在對(duì)應(yīng)題號(hào)后的橫線上。

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

7. 設(shè)集合A={1,2,3,4 }, B={6,8,12}, A到B的關(guān)系R＝,

那么R－1＝

8. 在“同學(xué)，老鄉(xiāng)，親戚，朋友”四個(gè)關(guān)系中_______是等價(jià)關(guān)系.

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

10.設(shè)X＝{a,b,c}，R是X上的二元關(guān)系，其關(guān)系矩陣為

MR＝，那么R的關(guān)系圖為

三、證明題（共30分）

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

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

13.（10分）證明

與

，

與

等勢(shì)。

四、解答題(共35分)

14.（7分）構(gòu)造三階幻方（以1為首項(xiàng)的9個(gè)連續(xù)自然數(shù)正好布滿(mǎn)一個(gè)

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

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

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

求R1·R2的集合表達(dá)式.

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

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

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

一、單項(xiàng)選擇題(每小題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. 見(jiàn)第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) 設(shè)，作如下： 2分

5分

b) 設(shè)，作如下： 7分

10分

14.

4

9

2

3

5

7

8

1

6

填對(duì)每個(gè)格得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ù)中，每對(duì)1個(gè)數(shù)得2分.

16. (2分)

(4分)

(6分)

(10分)

17. 解 設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時(shí)成立。 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分