上海開放大學期末考試

離散數學模擬試題（半開卷）

題號二三四五六總分

分數

得分評卷入

一、單項選擇題（每題3分，共15分）

1.設集合A中有4個元素，那么集合4的鼎集"川中有（）個元素。

A.4B.8

C.16D.32

2.設圖G=<匕￡>,小匕那么以下結論成立的是（）.

A.deg（v）=21E|B.deg（v）=|E\

C.^deg(v)=|￡|D.^deg(v)=2|E|

VGVveV

3.如圖一所示，以下說法正確的選項是（).

A.（e,c）是割邊B.(de)是割邊

C.（〃,“）是割邊D.(b,c)是割邊

b°

圖一

4.命題公式PV。的合取范式是（）.

A.PB.PAQ

C.P\/PD.P7Q

5.以下公式中（）為永真式.

A?-U4A-IB?IA八一\B

C.一IAA―\BD.-U4A-\B<>—I(/4A5)

得分評卷入

二、填空題（每題3分，共15分）

1.命題公式Pv「尸的真值為.

2.設集合4={2,3,4},左{1,2,3,4},2是A到〉的二元關系,

R={<x,y>tA且），GBJELx<y]

那么R的有序對集合為.

3.設集合A={1,2}上的關系2>},那么在R中僅需加一個元素，就可使新

得到的關系為對稱的.

4.設G是具有〃個結點機條邊左個面的連通平面圖，那么〃?等于.

5.假設無向樹7有5個結點，那么7的邊數為.

得分評卷人

三、邏輯公式翻譯題（每題6分，共18分）

1.將語句“今天上班”翻譯成命題公式.

2.將語句“他去操場鍛煉，僅當他有時間"翻譯成命題公式.

3.將語句“所有的人都要呼吸"翻譯成謂詞公式.

得分評卷入

四、判斷說明題（每題5分，共10分）

1.如果圖G是無向圖，且其結點度數均為偶數，那么圖G是歐拉圖.

2.函數/N—N,次r）=2i■，其中N為自然數集，那么/是雙射的。

2.畫一棵帶權為1,2,2,3,4的最優二叉利計算它們的權.

3.求(PVQ)f(RVQ)的合取范式.

得分評卷人

六、證明題（此題6分）

試證明：假設R與S是集合A上的對稱關系，那么也是集合A上的對稱關系.

離散數學模擬試題答案

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

1.C2.D3.B4.D5.B

二、填空題(每題3分，共15分)

1.1或真2.{<2,2>,<2,3>,<2,4>,<3,3>},<3,4>,<4,4>}

3.<2,1>4.n+k-25.4

三、邏輯公式翻譯題(每題6分，共18分)

1.設P：今天上班,

那么命題公式為：P.

2.設P：他去操場鍛煉，Q：他有時間，

那么命題公式為：PTQ.

3.設。(x)：x是人,Q5)：x要呼吸，

那么謂詞公式為：Vx(P(x)-Q(x))

四、判斷說明題(每題5分，共10分)

1.錯誤.

當圖G不連通時圖G不為歐拉圖.

2.錯誤.

/是單射的，但不是滿射的,因為ranr<zN,因為ran/'不含有奇數.

五、計算題[每題12分，共36分)

解：

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

(2)AQB=[\]

(3)<{1},{!,2}>,<1,<2,

2.

12

12

權為1x3+2x3+2x2+3x2+4x2=27

3.（PVQ）-*1RVQ）

（?VQ）V（RVQ）

o-Q）V（RVQ）

o（「PVRVQ）八（「QVRVQ）

o（WRVQ）Al

o（「PVRVQ）（合取范式）

六、證明題（此題6分）

證明：設Vx,yeA,因為R對稱，所以假設那么<