2023年離散數(shù)學形成性考核作業(yè)離散數(shù)學綜合練習書面作業(yè)

離散數(shù)學形成性考核作業(yè)4

姓名：

號.

學

得分：____________

離散數(shù)學綜合練習書面作業(yè)

規(guī)定：學生提交作業(yè)有如下三種方式可供選擇：

1.可將本次作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有

解答過程，完畢作業(yè)后交給輔導教師批閱.

2.在線提交word文檔.

3.自備答題紙張，將答題過程手工書寫，并拍照上傳.

一、公式翻譯題

1.請將語句“小王去上課，小李也去上課."翻譯成命題公式.

設(shè)P：小王去上課

Q:小李去上課

則：命題公式PAQ

2.請將語句“他去旅游，僅當他有時間.”翻譯成命題公式.

設(shè)P：他去旅游

Q：他有時間

則命題公式為P-Q

3.請將語句“有人不去工作”翻譯成謂詞公式.

設(shè)A(x):x是人

B(x)：去工作

則謂詞公式為3x(A(x)A-B(x))

4.請將語句“所有人都努力學習.”翻譯成謂詞公式.

設(shè)A(x):x是人

B(x):努力學習

則謂詞公式為Vx(A(x)AB(x))

二、計算題

1.設(shè)4={{1},{2},1,2},5={1,2,{1,2}),試計算

(1)(A-B)；(2)(AA5)；(3)AxB.

解:

(I)(A-B)={{1},{2})

(2)(APB)={1,2}

(3)AxB=

{<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1,

2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>}

2.設(shè)4={1,2,3,4,5},R={<x,y>\x&A,yeA且x+yV4},S={<x,y>\x&A,

yeA且x+y<0},試求R,S,R?S,S?R,Ri,S-i,r(S),s(R).

解：

R={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}

S=空集

R?S=空集

S?R=空集

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

空集

r(5)={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}

s(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}

3.設(shè)A={1,2,3,4,5,6,7,8},R是A上日勺整除關(guān)系，B=[2,4,6).

(1)寫出關(guān)系R日勺表達式；(2)畫出關(guān)系R日勺哈斯圖;

(3)求出集合5日勺最大元、最小元.

答：(1)R=|<1,1><1,2x1,3x1,4x1,5x1,6x1,7x1,8>

<2,2x2,4x2,6x2,8x3,3x3,6x4.4?<4,8x5,5x6,6x7,7><8,8>}

(2次的哈斯圖為

{3)集合B沒有最大元，最小元是2

4.設(shè)G=<V,E>,V=[V],v2,v3,v4,v5},E={(vpv3),(v2,v3),(v2,v4),(v3,v4),

(v3,v5),(v4,v5)},試

(1)給出G日勺圖形表達；(2)寫出其鄰接矩陣；

(3)求出每個結(jié)點日勺度數(shù)；(4)畫出其補圖日勺圖形.

答：⑴

(2)

-00100-

00110

.4(D)=11011

01101

00110

(3)

deg(vl)=l,deg(v2)=2,deg(v3)=4,deg(v4)=3,deg(v5)=2

(4)

VL

5.圖G=<V,E>,其中V={a,b,c,d,e},E={(a,b\(a,c),(a,e),(b,d),(b,e),

(c,e),(c,d),(d,e)},對應(yīng)邊日勺權(quán)值依次為2、1、2、3、6、1、4及5,試

(1)畫出G日勺圖形;(2)寫出G日勺鄰接矩陣;

(3)求出G權(quán)最小日勺生成樹及其權(quán)值.

解:

(1)

(2)

011o1

1001

A(D)=10011

01101

11110

(3)

其中權(quán)值是：7

6.設(shè)有一組權(quán)為2,3,5,7,17,31,試畫出對應(yīng)日勺最優(yōu)二叉樹，計算該最優(yōu)

二叉樹日勺權(quán).

解:

48

31

權(quán)值：65

7.求PfQvR日勺析取范式，合取范式、主析取范式，主合取范式.

解:

PTQVKCrPvQvR（析取超式）

oJPvQvR）（合取范式）

真值表；

pQR-Ip原式極小項及大項

00011-IPA—IPA—?P

00111-,PA->QAR

01011-IPAQA-IR

0111I—IPAQAR

10000PvQvR

10101PA-?QAR

11001PAQA-iR

11101PAQAR

主析菽應(yīng):if(->PA-,PA-,P)v(-,PA-,QAR)V(-,PAQA-.R)V

(-.PAQAR)v(PA-,QAR)V(PAQA->R)V(PAQAR)

主合取范式JPvQvR)

8.設(shè)謂詞公式(土)(尸0,丁)—(以)。(丫,羽名))人(?)氏0,2).

(1)試寫出量詞日勺轄域；

(2)指出該公式日勺自由變元和約束變元.

答：(1)的轄域為P(x.y)T\/zQ(x,y,z)

Vz的轄域為Q(x,y,z)

Vy的轄域為R(y,z)

(2)約束變元為

P<x,y)->VzQ(x,y.z)中的x

Q(x,y,z)中的z

R(y,z)中的y

自由委無為

P(x,y)->DzQ(x,y,z)中的y

R(y,z)中的z

9.設(shè)個體域為。={%,%}，求謂詞公式(Vy)0x)P(x,y)消去量詞后日勺等值式;

捽：謂詞公式消去用詞后的等值式為

(R(a.a)AR(a,b))v(R(b,a)AR(b,b))

三、證明題

1.對任意三個集合A,B和C,試證明：<Ax5=AxC,且Aw0,則B=C.

證明：設(shè)x￡A,yFB,JH1]<x,y>FAxB

由于AxB=AxC,故vx,y>￡AxC,則有y^C

因此BcC

設(shè)xGA,z@C,則<x,z>GAxC

由于AxB=AxC,故<x,z>CAxB,則有z@B

因此CcB

故得A=B

2.試證明：若R與S是集合A上口勺自反關(guān)系，則ACS也是集合A上日勺自

反關(guān)系.

證明：

R和S是自反口勺，VxGA,<x,x>GR,<x,x>cS

則<x,x>eRnS

因此RcS是自反日勺

3.設(shè)連通圖G有左個奇數(shù)度日勺結(jié)點，證明在圖G中至少要添加：條邊才能

使其成為歐拉圖.

證明：由定理推論知：在任何圖中，度數(shù)為奇數(shù)的結(jié)點必是偈數(shù)個，則k是

偎數(shù)，又由歐拉圖的充要條件是圖G