2022離散數(shù)學(xué)期末復(fù)習(xí)題庫及答案

2022離散數(shù)學(xué)期末復(fù)習(xí)題庫及答案

一'選擇題(每題3分)

1、下列句子中哪個(gè)不是命題？(C)

A、你通過了離散數(shù)學(xué)考試B、我倆五百年前是一家

C、我說的是真話D、淮海工學(xué)院是一座工廠

2、下列聯(lián)接詞運(yùn)算不可交換的是(C)

A、AB、vC^―D、

3、命題公式fQ不能表述為(B)

A、P或。B、非P每當(dāng)。C、非P僅當(dāng)。D、除非P,否則。

4、下列公式中為永真式的是(C)

A、PT(PAQ)B、(「八。)c、(PAQ)FQD、(PvQ)fQ

5、下列公式中為非永真式的是(B)

A、(JPA-\P)—>QB、(>Pv―F)—>QC>JPA(—\P—>Q)D、JPV(―\P—>Q)

6、設(shè)個(gè)體域A={a,〃},則謂詞公式王(尸(X)AG(X))消去量詞后，可表示為為(C)

A、(F(a)AF(Z?))v(G(a)AG(〃))B、(F(a)vF(b))A(G(〃)VG(/?))

C、(/(Q)AG(。))v(F(/?)AG(b))D、(/(a)vG(。))A(bS)vG(b))

7、設(shè)個(gè)體域4=伍力},則謂詞公式Vx力火(x,y)去掉量詞后，可表示為(D)

A、R[a,a)AR(a,b)/\R(b,a)^,R[b,b)B>R(a,a)vR(^a,b)vR(^b,a)vR(b,b)

C、(R(a,a)/\R(a,8))\z(H(8,a"H(b,b))D,(7?(a,a)vR(a,Z?))A(R(b,a)vR(h,/?))

8、設(shè)。：全總個(gè)體域，H(x)：x是人，P(x)：x犯錯(cuò)誤，

則命題“沒有不犯錯(cuò)誤的人”的邏輯符號(hào)化為(D)

A、士(//(*)△P(x))B、玉(H(x)-P(x))C、Vx(//(x)/\P(x))D,Vx(H(x)—>P(x))

9、設(shè)￡)：全總個(gè)體域，F(xiàn)(x)：x是花，M(x)：尤是人，H(x,y)：x喜歡y,

則命題“有的人喜歡所有的花”的邏輯符號(hào)化為(D)

A、Vx(M(x)A3XF(y)H(x,y))B、Vx(M(x)AVy(E(y)-”(x,y))

C、五(M(X)A寺(F(y)->"(x,y))D、玉(V(x)AVy(F(y)->"(x,y))

10、設(shè)。為空集，則下列為假命題的是(A)

A、0e0B、0c0C、0e{0}D、0c{0}

Ik設(shè)。力各不相同，則下述等式為真的是(D)

A.[a,b}={{a},}B,{a,b}={{a,b}}

C.{{a}\J}={a,b]D、{⑷U{。}}={"}}

12、設(shè)集合A={O,0},。為空集,p(A)為A的募集,則下列為假命題的是(B)

A、0ep(A)B、Oep(A)C、{0}ep(A)D、{0}ep(A)

13、設(shè)集合A={0,0},。為空集,p(A)為A的暴集,則下列為假命題的是(B)

A、0cp(A)B、{0}GQ(A)C、{0}“(4)D、{{0}}"A)

14、非空集合X上的空關(guān)系。不具備的性質(zhì)是(A)

A、自反性B、反自反性C、對稱性D、傳遞性

10、設(shè)4={1,2,3}上的關(guān)系/?的關(guān)系圖如下，則R不具備的性質(zhì)為(A)

A、自反性B、反自反性C、反對稱性D、傳遞性

15、4={1,2,3,4}上0^^={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}只^§(C)

A、反自反性B、反對稱性C、對稱性D、傳遞性

16、設(shè)/?為4={1,2,3}上的關(guān)系，其關(guān)系圖如下，則下列為真命題的是(C)

A、/?對稱，但不反對稱B、/?反對稱，但不對稱

C、R對稱，又反對稱D、R不對稱，也不反對稱

17、設(shè)/?為人={1,2,3,4}上的關(guān)系，其關(guān)系圖如下，則下列為假命題的是(C)

A、R不自反，也不反自反B、R不對稱，也不反對稱

C、R傳遞D、/?不傳遞

18、設(shè)A={1,2,3},則A上不同等價(jià)關(guān)系的個(gè)數(shù)為(C)

A、3B、4C、5D、6

19、設(shè)4={1,2,3,4),則A上不同等價(jià)關(guān)系的個(gè)數(shù)為(C)

A、13B、14C、15D、16

20、設(shè)R、Z分別為實(shí)數(shù)集、整數(shù)集，則下列函數(shù)為滿射而非單射的是(C)

A、f:R—R,/(x)=x+6B、/:/?->??,/(x)=(x+6)2

C、/:/?—>Z,/(%)=[x]D、f:RTR,f(x)=x6+6x

21、設(shè)H、及Z*分別為實(shí)數(shù)集、非負(fù)實(shí)數(shù)集、正整數(shù)集，下列函數(shù)為單射而非滿射的是(B)

A、f:RfR,f(x)=-x2+7x-iB、f:Z*fR,/(x)=Inx：

C、f:R—>R,f(x)=|x|D、f:RTR,f(x)-7x+l

22、設(shè)|X|=3，M=4,則從X到y(tǒng)可以生成不同的單射個(gè)數(shù)為(B).

A、12B、24C、64D、81

23、設(shè)|X|=3，M=2,則從X到y(tǒng)可以生成不同的滿射個(gè)數(shù)為(B).

A、6B、8C、9D、64

24、設(shè)集合A的幕集為夕(A),n、U、—、x為集合的交、并、差、笛卡爾乘積運(yùn)算，則下列

系統(tǒng)中是代數(shù)系統(tǒng)的為(D)

A、〈/7(A),①B、(p(A),U)C、(Q(A),-〉D、(p(A),x)

25、在自然數(shù)集上定義的下列四種運(yùn)算，其中滿足結(jié)合律的是(C)

A、a^h=a—hB、a^h=\a-h\C、=max{a,Z?}D、a*h=a+2h

26、設(shè)N?為前422個(gè)自然數(shù)集，+*表示模%加法，對代數(shù)系統(tǒng)A=〈N*,+J,有(A)

A、0是么元，無零元B、1是么元，無零元C、無么元，0是零元D、無么元，無么元

27、設(shè)N*為前422個(gè)自然數(shù)集，x*表示模左乘法，對代數(shù)系統(tǒng)A=(N?,xJ,有(B)

A、1是么元，無零元B、1是么元，0是零元C、無么元，0是零元D、無零元，無么元

28、設(shè)非空有限集S的嘉集為夕(S),對代數(shù)系統(tǒng)A=(2(S),n〉，有(B)

A、①是么元，S是零元B、①是零元，S是么元C、唯一等幕元D、無等幕元

29、設(shè)非空有限集S的累集為P(S),對代數(shù)系統(tǒng)A=(夕(S)，U)，有(A)

A、①是么元，S是零元B、①是零元，S是么元C、唯一等幕元D、無等哥元

30、設(shè)Z是由所有整數(shù)組成的集合，對于下歹U*運(yùn)算，代數(shù)系統(tǒng)<Z,*>為獨(dú)異點(diǎn)的是(B)

A、a*b-cihB、a*b-aC、a*b-a+abD^a*b-ma\(a,b)

31、任意具有多個(gè)等基元的半群，它(A)

A、不能構(gòu)成群B、不一定能構(gòu)成群C、能構(gòu)成群D、能構(gòu)成阿貝爾群

32、下列命題正確的是（B）

A、簡單回路必為基本回路B、基本回路必為簡單回路

C、簡單回路必不是基本回路D、基本回路必不是簡單回路

33、歐拉回路是（B）

A、路徑B、簡單回路C、既是基本回路也是簡單回路D、既非基本回路也非簡單回路

34、哈密爾頓回路是（C）

A、路徑B、簡單回路C、既是基本回路也是簡單回路D、既非基本回路也非簡單回路

35、在任何有向圖中，下列命題正確的是（C）

A、任意頂點(diǎn)的入度與出度都相等B、任意頂點(diǎn)的入度與出度都不相等

C、所有頂點(diǎn)的入度之和與出度之和都相等D、所有頂點(diǎn)的入度之和與出度之和都不相等

36、設(shè)有向線圖G的頂點(diǎn)集丫={匕,嗎,…小.}，鄰接矩陣A=（%）“x“，則deg-（匕）=（D）

A、%B、Z%C、Z%D、工％

i=\j=ij=\

37、設(shè)有向線圖G的頂點(diǎn)集丫={匕,嶺,…，匕J，鄰接矩陣A=（陽）…，則deg*（匕）=（C）

A、djjB、Z%C、Z%D、2a

i=\j=\>1

38、在有n個(gè)結(jié)點(diǎn)的簡單無向圖中，其邊數(shù)（C）

A、最多有n-1條B、至少有n-1條C、最多有"（"一）條D、至少有迎二2條

22

39、在有n個(gè)結(jié)點(diǎn)的簡單有向圖中，其邊數(shù)（C）

A、最多有n-1條B、至少有n-1條C、最多有〃（〃—1）條D、至少有〃（〃—1）條

40、在有n個(gè)結(jié)點(diǎn)的連通圖中，其邊數(shù)（B）

A、最多有n-1條B、至少有n-1條C、最多有n條D、至少有n條

41、設(shè)4={0,{1},{1,3},{1,2,3}},則A上包含關(guān)系'七”的哈斯圖為（C）

42、集合A={1,2,3,4}上的偏序關(guān)系圖為

則它的哈斯圖為（A）

[D]

A、無簡單回路的連通圖B、有n個(gè)頂點(diǎn)n-1條邊的連通圖

C、每對頂點(diǎn)間都有通路的圖D、連通但刪去一條邊便不連通的圖

44、設(shè)G是有5個(gè)結(jié)點(diǎn)的無向完全圖，則從G中刪去（C）條邊可以得到樹

A、4B、5C、6D、10

二、填充題(每題4分)

1、當(dāng)賦予極小項(xiàng)足標(biāo)相同的指派時(shí)，該極小項(xiàng)的真值為1，當(dāng)賦予極大項(xiàng)足標(biāo)相同的指派

時(shí)，該極大項(xiàng)的真值為。.

2、任意兩個(gè)不同極小項(xiàng)的合取式的真值為。，而全體極小項(xiàng)的析取式的真值為L

3、任意兩個(gè)不同極大項(xiàng)的析取式的真值為1，而全體極大項(xiàng)的合取式的真值為Q.

4、n個(gè)命題變元可構(gòu)造包括F的不同的主析取范式類別為二.

5、〃個(gè)命題變元可構(gòu)造包括T的不同的主合取范式類別為2二.

6、若己證為真，則可假設(shè)某一確定的個(gè)體y使A(?為真，此推理規(guī)則被稱為空.

7、令「是公理與前提的合取，F(xiàn)中無x的自由出現(xiàn)，若從「可推出A(x),則從「麗雅

出VxA(x),此推理規(guī)則被稱為變.

8、p(0)={0},p(p(0))={0；{0}},p(p({(D}))={0,{0},{{0}},{0,{0}}}.

9、夕(0)-萬={0},0(2(0))一2(0)={{0}}.

10>設(shè)A={a},則夕(A)xp(A)={<0,0>,<0,a>,<A,0>,<A,A>].

11、設(shè)集合A,B分別含有m,n個(gè)不同元素，則AxB的基數(shù)為〃,p(AxB)的基數(shù)為2'"",

12、Axp(B)的基數(shù)為二竺，p(A)xB的基數(shù)為〃2"',Q(A)XQ(B)的基數(shù)為2""".

13、設(shè)4={1,2,3,4,6,證24為A上整底森，則偏序集<A,<>的極小元為[

最小元為L極大元為絲、最大元為四.

14、設(shè)A[{2,3,4,6,互2},“W”元4上整除關(guān)系，則偏序集<A,☆的極小元為2,3,

最小元為無，極大元為8,12,最大元為無，既非極小元也非極大元的是4,6.

15、設(shè)|X|=m，M=〃，則從X到F有丈種不同的二元關(guān)系，有豆二種不同的函數(shù).

16、在一個(gè)有〃個(gè)元素的集合上，可以有2)種不同的二元關(guān)系，有或種不同的函數(shù)，

有里種不同的雙射.

17、設(shè)人={2,4,6},A上*為：a*b=max{a,b},則在代數(shù)系統(tǒng)<A,*>中，么元是2，零元為

18、設(shè)A={3,6,9},A上*為：a*b=min{a,b},則在代數(shù)系統(tǒng)<A,*>中，么元是9,零元為3_.

19、設(shè)〈G*〉是一個(gè)群，則

(1)若a,b,xGG,a*x=b,則x=a'*b；(2)若a,b,xWG,a*x=a*b,貝！|x=b.

20、群<G*>的等事元是么元,有L個(gè)，零元有9個(gè).

21、設(shè)。是12階群的生成元，則/是6階元素，/是生階元素.

22、設(shè)。是10階群的生成元，則是士階元素，是由階元素.

23、在一個(gè)群〈G*〉中，若G中的元素a的階是k,則的階是

24、n階無向完全圖Kn的邊數(shù)是她二。，每個(gè)結(jié)點(diǎn)的度數(shù)是〃一1.

2——

’0101、

1011

25、設(shè)有向圖G=<V,E>,丫={匕,匕，匕,匕}的鄰接矩陣A=]]0°，

J000,

則匕的入度deg-(u)=3,外的出度deg+(匕)=1.

26、設(shè)無向圖G有18條邊且每個(gè)頂點(diǎn)的度數(shù)都是3,則圖G有受_個(gè)頂點(diǎn).

27、一棵無向樹的頂點(diǎn)數(shù)為n,則其邊數(shù)為比1,其結(jié)點(diǎn)度數(shù)之和是2n-2.

28、設(shè)1=<V,E)是一棵樹，若|V|>1,則T中至少存在爰片樹葉.

三'問答題(每題6分)

1、若個(gè)體域。={-1,3,6},5(x)：x>3,Q(x)：x=5,a：3,P：5>3,

則謂詞公式Hx(S(x)-Q(a))AP為真嗎？為什么？

答：為真；

Hx(S(x)f2(?))八P=((5(-1)fQ(a))v(S⑶fQ(a))v(S(6)fQ(a)))A1

=((0-0)v(0-O)v(l-0))/d=(lvlv0)/dol.

2、謂詞公式VxpP(x,y)->于VxP(x,y)為真嗎？為什么？

答：不為真；設(shè)個(gè)體域。：實(shí)數(shù)域，P(x,y)：x+y=O,

貝ijV燈yP(x,y)T3y^xP(x,y)=1-0o0.

3、設(shè)4={1,2,3},問A上存在一個(gè)既不是自反又不是反自反的關(guān)系嗎？為什么？

答：存在；如/?={<1,1>,<1,2>}.

4、設(shè)4={1,2,3},問A上存在一個(gè)既不是對稱又不是反對稱的關(guān)系嗎？為什么？

答：存在；如/?={<1,2>,<1,3>,<2,1>}.

5、設(shè)4={1,2,3},問A上存在一個(gè)既是對稱又是反對稱的關(guān)系嗎？為什么？

答：存在；如R={<1,1>,<2,2>,<3,3>}.

6、設(shè)4={2,3,4},§={2,4,7,10,12},從4到B的關(guān)系

R={<a,b>\aeA,beB,^.a^b},試給出R的關(guān)系圖和關(guān)系矩陣，并說明此

關(guān)系R及其逆關(guān)系R"是否為函數(shù)？為什么？

解：/?={<2,2>,<2,4>,<2,10>,<2,12>,<3,12>,<4,4>,<4,12>},

則R的關(guān)系圖為：

R的關(guān)系矩陣為

■1101T

MR=00001

01001

關(guān)系R不是A到3的函數(shù)，

因?yàn)樵?,4的象不唯一

逆關(guān)系R'也不是8到A的函數(shù)

因?yàn)樵?的象不存在.

7、設(shè)Z為整數(shù)集，函數(shù)/：ZxZ-Z,且/(x,y)=x+y,問/是單射還是滿射？

為什么？并求f(x,x),f(x,-x).

解：VxeZ,m<0,x>eZxZ,總有/(0,x)=x,則/是滿射；

對于<1,2>,<2,1>GZXZ,,有/(1,2)=3=/(2,1),而<1,2>。<2,1>,則/非單射;

f(x,x)=2x,f(x,-x)=Q.

8、設(shè)Z為整數(shù)集合，“*”定義為：a*b=ah,問其在Z上封閉嗎？可交換嗎？可結(jié)合嗎？

答：①取。=2,h=-\,a*b=2-'^Z,其在Z上不封閉；

②取a=2,6=1時(shí)，“切=*=2,b*a=lf=l,a*b^b*a,其在Z上不可交換；

③取。=2,b=\,c-2,(a*b)*c=4,a*(b*c)-2,(a砌*c#a*(2*c),其在Z上不可結(jié)合.

9、設(shè)Z為整數(shù)集合，“*”定義為：。切=2h，問其在Z上封閉嗎？可交換嗎？可結(jié)合嗎？

答：①整數(shù)乘法運(yùn)算在Z上封閉，

②V“,beZ,a*b-2ab=2ba=b*a,其在Z上可交換；

@y/a,b,ceZ,(”*3*G2(2a〃)*c=4a6c=2aX2bc=2a(b*c)=a*(6*c),其在Z上可結(jié)合.

10、設(shè)無向圖6=(匕婷有12條邊，已知有6個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于3,

問G中至少有多少個(gè)頂點(diǎn)？

答：設(shè)G中度數(shù)小于3的頂點(diǎn)有％個(gè)，則由歐拉定理Zdeg(v)=24知，

度數(shù)小于3的頂點(diǎn)度數(shù)之和為6,故當(dāng)其余的頂點(diǎn)度數(shù)都為2時(shí)，G的頂點(diǎn)最少,

即G中至少有9個(gè)頂點(diǎn).

11、〃取怎樣的值，無向完全圖K,有一條歐拉回路？

答："為奇數(shù)，VvSV,deg(n)=〃T為偶數(shù)，

所以，當(dāng)”是大于或等于3的奇數(shù)時(shí)，K“有歐拉回路.

12、判斷下列無向圖是否存在歐拉路徑？是否為歐拉圖？說明理由.

EF

答：d(A)=2,d(B)=d(C)=d(D)=4d(E)=d(F)=3

只有兩個(gè)奇數(shù)度的結(jié)點(diǎn)，有歐拉路徑，如EDBEFCABCDF；

由于每個(gè)結(jié)點(diǎn)的次數(shù)不均為偶數(shù)，所以不是歐拉圖.

13、判斷下列圖是否為歐拉圖？說明理由，是否存在哈密爾頓回路？

答：一個(gè)無向圖D是歐拉圖OD是連通的，且所有頂點(diǎn)的度等于偶數(shù),

所以是歐拉圖，但無哈密爾頓回路.

14、判斷下列圖是否存在歐拉路徑？是否為歐拉圖？說明理由.

答：一個(gè)有向圖D是歐拉圖OD是連通的，且所有頂點(diǎn)的入度等于出度,

所以是歐拉圖，存在歐拉路徑.

四、填表計(jì)算題(每題10分)

1、對命題公式A=Tp-9)A(PV4),要求

(1)用0或1填補(bǔ)其真值表的空格處；(2)求該命題公式的主析取范式與主合取范式.

解：

pyq

PqpiqA

001000

011010

100111

111010

主析取范式A0^(2)；主合取范式Ao口(0,1,3).

2、對命題公式A=(pfq)cr,要求

(1)用0或1填補(bǔ)其真值表的空格處；(2)求該命題公式的主析取范式與主合取范式.

解：

pqrpiqA

00010

00111

0i010

0i111

10001

10100

1i010

1i111

主析取范式A=Z(1，3,4,7)；主合取范式Ao口(0,2,5,6).

3、設(shè)代數(shù)系統(tǒng)其中AMa力,*是A上的二元運(yùn)算，由下列表給出，試列表分別

討論交換性、暴等性、么元和逆元.

*abc

aabc

bbca

ccab

解:

交換律哥等律么元逆元

有無aa~}=a,b~]=c,c~]=b

4、設(shè)代數(shù)系統(tǒng)。,*>,其中Ago力,*是A上的二元運(yùn)算，由下列表給出，試列表分別

討論交換性、暴等性、么元和逆元.

*ahc

aabc

habc

cabc

解:

交換律哥等律么元逆元

有無aa~l=a,b7=b

五、計(jì)算問答題（每題10分）

1、集合A={1,2,3,4}上的關(guān)系

7?={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>}，

寫出關(guān)系矩陣MR,畫出關(guān)系圖并討論R的五種性質(zhì).

’1010、

0100

解：R的關(guān)系矩陣為MR=,R的關(guān)系圖為

R1011

、0011,

因MR對角元皆為1,故R是自反的，不是反自反的；因MR為對稱矩陣，故R是對稱的;

因<1,3>,<3,1>CR,故H不是反對稱的；

又因<1,3>,<3,4>WR,但故7?無傳遞性.

2、設(shè)R是集合A={1,2,3,4}上的二元關(guān)系，

7?={<1,1>,<1,2>,<1,3>,<3,1>,<3,2>,<3,3>,<4,1>,<4,2>,<4,3>},

寫出關(guān)系矩陣MR,畫出關(guān)系圖并討論R的五種性質(zhì).

110、

0000

解：R的關(guān)系矩陣為MR=]]]0,R的關(guān)系圖為

110,

因MR對角元不全為1,也不全為0,故R不是自反的，也不是反自反的:

因MR為非對稱矩陣，故R是反對稱的，不是對稱的；因/?2=R,故R是傳遞的.

3、有向圖G如圖9.27所示,

⑴求G的鄰接矩陣；

⑵根據(jù)鄰接矩陣求各結(jié)點(diǎn)的出度和入度；

⑶求G中長度為3的路的總數(shù)，其中有多少條回路;

（4）求G的可達(dá)性矩陣.

'0110、

1000

0101

圖9.27

\,00007八4x4

(2)deg*(vi)=2,deg-(vi)=Ldeg4(V2)=l,deg"(V2)=2,

deg(V3)=2,deg-(V3)=l,deg'(V4)=0,deg-(V4)=l;

‘1101、’1110、

01101101

⑶A2=，A3=

10000110

X0000/,4x4、0000,4x4

長度為3的路有8條，其中回路3條；

’3321、'1111、

23111111

(4)C3=A°+A'+A2+A3=p=

12211111

0001>4x40001,

4、有向圖O=＜V,E＞,其中結(jié)點(diǎn)集丫={匕,彩,匕,匕},有向邊集E可表示為:

E={＜vpv2＞,＜v2,v3＞，＜匕，匕＞,＜V3,V2＞,＜%，!＞，＜%，"＞，＜匕，%＞}

(1)求。的鄰接矩陣A；(2)求。的可達(dá)性矩陣P；

(3)說明匕到％長度為4的路徑有幾條？(4)匕到其它各頂點(diǎn)長度為3的路徑有幾條？

0100一

0010

解：⑴A=]

101:

1100

101111011r1210-

,1101,12101221

(2)*=,4=,4d=

111213422

011011112311_

242111111

35421111

R=A+A2+A3+A4=p

469541111；

46321111

(3)v2到匕長度為4的路徑有2條；

(4)打到其它各頂點(diǎn)長度為3的路徑有2條.

5、有向圖O=＜V,E＞,其中結(jié)點(diǎn)集丫={匕,為，匕，匕},

有向邊集七={＜匕,彩＞,＜匕，不＞，＜%，!＞，＜%，％＞，＜匕，丫2＞，＜丫4,丫3＞}

(1)求。的鄰接矩陣A；(2)求。的可達(dá)性矩陣P；

(3)說明。中經(jīng)過匕長度為3的回路有幾條？

(4)說明。中用到匕長度為4的路徑有幾條?

(5)說明。中匕到匕所有的路徑有幾條？

'0111

1000

解：(1)A=

0000

0110

-111o-'ii?r-1221

011111101111

(2)A2=,A3=,A4=

000000000000

1000011111I0

-3553-

33321111

%=A+A2+A3+A4=,P=

400000000

23311111

(3)。中經(jīng)過匕長度為3的回路有1條;(4)。中匕到匕長度為4的路徑有2條;

(5)。中片到匕所有的路徑有5條.

四、證明計(jì)算題(每題10分)

1、設(shè)A={1,2,3,4},在4*71上定義火:<<。力>,<。,〃>>￡/?0a+d=b+c,

“十”為普通加法，證明：/?是AxA上的等價(jià)關(guān)系，并求出[<2,4>k，AxA/R.

證明：(1)X/<a,b>eAxAa+b=b+aa,b>,<a,b?eR,即R自反；

(2)V?a,b>.<c,d?eR,則a+d=b+c,.\c+b=d+a,

則vvc,d>,<a,b?eR,即R對稱；

(3)V?a,b>,<c,d?eR,?c,d>.<e.f?GR,

貝！Ja+d=h+c,c+f=d+e.\a+d+c+f=b+c+d+e

有a+f=b+e,:,《a,b》,〈e,于?GR,即R傳遞;

綜上得出，R是AxA上的等價(jià)關(guān)系，

且[<2,4〉5={<a,b>\<a,b>E,AxA,。=/?-2}={vl,3>,v2,4>},

AxA/H={[vL-R,[<2,—,3>]R,—,[<1,4>卜,—}.

2、設(shè)4={1,2,3,4},在24乂4上定義7?:?々,〃>,<。,"》￡??=a?d=,

為普通乘法，證明：R是AxA上的等價(jià)關(guān)系，并求出[<2,4>k，AxA/R.

證明：(1)V<a,h>^AxA,vv〈。力》￡R,即H自反；

(2)\/?a,b>,<c,d?￡R,則a?d=b?c,1.c?b=d?a,

則vvc,d>,vR,即R對稱;

(3)V?a,h>,<c,d?e7?,?c,d>,<e,f?GR,

貝lja?d=b?c,of=d?e：?a,d*:?于=〃?(?]吆，

有a?于=b^e,.*.?a,h>,<e,于》eR,即R傳遞;

綜上得出，R是AxA上的等價(jià)關(guān)系，

且[<2,4〉]寵={<a,h>|<a,b>^AxA,勿=〃}={<1,2>,v2,4>},

AXA/R={[<U>]R,[<1,2>],,,[<2,1>]K[<1,3>]R,[<3,1>]^,[<1,4>]K,[<4,1>]J

3、設(shè)R是實(shí)數(shù)集，H上的二元運(yùn)算*定義為：a*b=a+b+ab,

證明：</?,*>是獨(dú)異點(diǎn)，并寫出其么元和零元.

證明：⑴由于實(shí)數(shù)經(jīng)加法和乘法運(yùn)算后，其運(yùn)算結(jié)果仍為實(shí)數(shù)，所以運(yùn)算*對于R是封閉的;

由于a*/?=a+Z?+a〃=a(6+l)+(6+l)T=3+1)(b+l)-l

從而有(〃*b)*c=((〃+1)S+1)T)*c=(((a+1)3+l)-l)+l)(c+1)-1=(a+1)3+l)(c+1)-1

〃*S*c)=a*(S+1)(c+1)T)=(〃+1)((3+l)(c+1)T)+1)T=(〃+1)3+l)(c+l)-l

于是(〃*Z?)*c=4*S*c),所以*是可結(jié)合運(yùn)算；

在</?,*>中,對于任何實(shí)數(shù)a,者[，有O*a=4*O=O+a+O&=〃

故0是<凡*>中的么元，<凡*>是獨(dú)異點(diǎn)；

對</?,*>中任何實(shí)數(shù)小都有(T)*a=a*(-l)=(T)+a+(T)也二T,-1是<凡*>中的零元.

4、某無向連通圖G中有10條邊，二個(gè)2度頂點(diǎn)，二個(gè)3度頂點(diǎn)，一個(gè)4度頂點(diǎn)，其余頂點(diǎn)

的度數(shù)都是1,求G的頂點(diǎn)個(gè)數(shù)，并證明G為樹.

解：設(shè)G中度數(shù)為1的頂點(diǎn)個(gè)數(shù)為x

由握手定理知x+2x2+2x3+4=2x10

解得x=6

于是G中的頂點(diǎn)個(gè)數(shù)為％+2+2+1=11

因G為連通圖，且G中的邊數(shù)比其頂點(diǎn)個(gè)數(shù)少1-故G為樹.

五、證明題(每題10分)

1、用邏輯推理規(guī)則證明：Tpf4)fT/vs),(q-p)v-)r,r=p3q.

證明：(1)rP

(2)(qTp)vfP

(3)qfpT(l),(2)(析取三段論)

(4)r7sT(l)(加法式)

(5)->(〃-4)->T，vs)P

(6)piqT(4),(5)(拒取式)

⑺(pfq)A(q-?p)T(3),(6)(合取式)

(8)pcqT(7)(等值表達(dá)式).

2、用邏輯推理規(guī)則證明：(pvq)f(FAS),(rvs)ff=>p.

證明：(1)pP(附加前提)

(2)p\/qT(l)(加法式)

(3)(pvq)f(r/\s)P

z\

(4

\7rf\sT⑵,(3)(假言推理)

/\

(51

\7T(4)(簡化式)

/\

(6

\77(5)(加法式)

z\

(7)

\z

z\

(8

\7T(6),(7)(假言推理)

/\

{9

\7PfCP.

3、用邏輯推理規(guī)則證明：Vx(E(x)vG(x)),Vx(G(x)TT?(x)),VxR(x)=>VxF(x).

證明：⑴VxR(x)P

⑵R(c)r(i)(US)

(3)Vx(G(x)-[R(x))p

⑷G(c)->「R(c)773)(US)

(拒取式)

⑸-1G(c)T(2),⑷

(6)Vx(F(x)vG(%))P

⑺F(c)vG(c)T⑹(US)

(8)F(c)T(5),(7)(析取三段論)

(9)VxF(x)T(8)(UG).

4、用邏輯推理規(guī)則證明：HxF(x)Vy(F(y)vG(y)->/?(y)),3xF(x)=>BxR(x).

證明：⑴王戶(x)P

⑵尸(c)T⑴(￡5)

⑶士Dy(F(y)vG(y)-R(y))P

⑷Vy(尸(y)vG(y)-R(y))T⑴，⑶(假言推理)

⑸F(c)vG(c)->R(c)T(4)(US)

(6)F(c)vG(c)T⑵(加法式)

⑺R(c)T⑸，⑹(假言推理)

⑻士大(x)T⑺(EG).

5、用邏輯推理規(guī)則證明：Vx(P(x)TQ(x))=玉尸(x)->3xQ(x).

證明：⑴玉尸(x)P(附加前提)

⑵P(a)T(D(ES)

⑶Vx(P(x)f。(切P

(4)P(a)—>Q(a)T(3)(US)

⑸。⑷T⑵,⑷(假言推理)

⑹HxQ(x)T⑸(EG)

⑺大尸(x)—玉Q(x)CP.

6、設(shè)R為集合A上的二元關(guān)系，如果R是反自反的和可傳遞的，則R一定是反對稱的.

證明：假設(shè)R不是反對稱的，貝ijm<x,y>eR,<y,x>^R,x^y

由R的傳遞性知，<x,x>eR,此與R反自反矛盾，故R反對稱.

7、設(shè)R是A上的對稱和傳遞關(guān)系，

證明：若VaeAm匕則R是A上的等價(jià)關(guān)系.

證明：A,BbeA,6<a,b>eR,因R是對稱的，有<O,a〉eR,

又因R是傳遞的，所以<a,a>eR,則R在A上自反，故R是A上的等價(jià)關(guān)系.

8、設(shè)R,S是A上的偏序關(guān)系，證明：RDS是A上的偏序關(guān)系.

證明：(1)VxeA,因R,S在A上的自反性，則<x,x>e/?ns,有/?C|S在A上自反;

(2)設(shè)<x,y>eRDS,而XHy,則<x,y>eR,<x,y>eS,因H,S在A上的反對稱性,

有<y,x>^R,<y,x>wS,則<y,x〉wRnS,于是，RDS在A上是反對稱的；

(3)設(shè)<%,丁>eRnS,<y,z>eRnS,

則<x,y>eR,<y,z>eH;<x,y>eS,<y,z>eS,因R,S在A上的傳遞性,

有<x,z>eR,<x,z>eS,則<x,z>eRflS,于是，RDS在A上是傳遞的；

綜上所述，可證RflS是A上的偏序關(guān)系.

9、設(shè)R是S上的等價(jià)關(guān)系，證明：Ri是S上的等價(jià)關(guān)系.

證明：(1)因R在s上的自反性，有八三R，則，s=/；uRT，有RT在S上自反；

(2)因R在S上的