2020-2021大學《離散數(shù)學》期末課程考試試卷A1（含答案）

10.下列各圖是歐拉圖的是（)

2020-2021《離散數(shù)學》期末課程試卷A1

專業(yè)：考試日期：時間:總分：分閉卷

二大題：填空題（共10空，每空2分，共20分）

一大題：選擇題（共10小題，每小題2分，共20分）1.“如果雪是黑的，太陽從西邊出”是命題。

2.集合A={1,2,3}上的二元關(guān)系R具有對稱性，反對稱性，自反性，則

I.下列是兩個命題變元P，Q的小項是()

R二o

A.PA-iPAQB.-IPVQC.-|PAQD.-|PVPVQ

3.設(shè)R是實數(shù)集，在R上定義二元運算*為a*b=a+b+a-b,其中+和-是數(shù)的加法和乘法,

2.令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為

則代數(shù)系統(tǒng)＜R,*〉的幺元是，3的逆元是o

()A.P-1QB.PV-|Q

4.對稱關(guān)系具有性和性。

C.PAQD.PA-iQ

5.無向圖G具有一條歐拉回路，當且僅當G是,并且所有結(jié)點的度數(shù)都是。

3.下列等值式不正確的是()

6.在下圖中，度數(shù)為3的結(jié)點有個，出度為2的結(jié)點有個。

A.-|(Vx)A<=>(3x)-|A

B.(Vx)(B-*A(x))(Vx)A(x)

C.(3x)(A(x)AB(x))<=>(3x)A(x)A(3x)B(x)

D.(Vx)(Vy)(A(x)-*B(y))?(3x)A(x)-(Vy)B(y)

4.設(shè)R為實數(shù)集，函數(shù)f：RfR,f(x)=2x,則f是(）

A.滿射函數(shù)B.入射函數(shù)C.雙射函數(shù)D.非入射非滿射

三大題：計算證明題（共8小題，共60分）

5.設(shè)A={a,b,c,d},A上的等價關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}UIA,則對應(yīng)于R的A

1.（8分）如果論域是集合{a,b,c},試消去給定公式中的量詞：（閂y）（Wx）（x+y=0）.

的劃分是（）

2.（10分）設(shè)人二{21）3},P（A）是A的鼎集，十是集合對稱差運算。已知＜P（A）,十》

A.{{a},{b,c},zoi9hhf}B.{{a,b}?{c}?{d)}C.{{a},>{c},(d)}D.{{a,b

是群。在群＜P（A）,十〉中，①找出其幺元。②找出任一元素的逆元。③求元素x使?jié)M足

},{c,d}}

（a）?x={b）

6.設(shè)X,Y,Z是集合，“-”是集合相對補運算，下列等式不正確的是（）

A.(x-Y)-z=x-(Ynz)B.(X-Y)-Z=(X-Z)-Y3.（8分）求公式r（P-Q）c（P--1Q）的主合取范式。

C.(X-Y)-Z=(X-Z)-(Y-Z)D.(X-Y)-Z=X-(YUZ)4.（8分）在偏序集＜Z,W＞中，其中Z={1,2,3,4,6,8,12,14},W是Z中的整除關(guān)系，求

7.設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，則（）Z的極大元，極小元，最大元，最小元，并求集合口={2,3,4,6}的最小上界和最大下界。

A.對所有x屬于A,有x*Z=Z*x=Z

B.Z屬于A,且對所有x屬于A,有x*Z=Z*x=Z

C.Z屬于A,且對所有x屬于A,有x*Z二Z*x二x

D.Z屬于A,且存在x屬于A,有x*Z二Z*x二Z

8.在自然數(shù)集N上，下列定義的運算中不可結(jié)合的只有（）

A.a*b=min（a,b）B.a*b=a+b

5.（8分）證明（（QAS）-R）A（S-（PVR））O（SA（P-Q））-R

C.a*b二abD.a*b二a/b

6.（8分）證明：下列兩個圖同構(gòu)。

9.下列說法正確的是（）

A.整環(huán)必為域B.交換環(huán)必為整環(huán)C.整環(huán)必為交換環(huán)D.交換環(huán)必

為含幺環(huán)

7.（10分）在謂詞邏輯中構(gòu)造下面推理的證明：每個人在學校讀書的就能獲得知識。所以

如果沒有人獲得知識就沒有人在學校讀書。（個體域：所有人的集合）

8.在自然數(shù)集N上，下列定義的運算中不可結(jié)合的只有(D)

《離散數(shù)學》期末課程試卷答案A.a*b-min(a,b)

2020-2021AlB.a*b=a+b

C.a*b=a-b

郛專業(yè)：考試日期：時間：總分：分閉卷D.a*b=a/b

9.下列說法正確的是(C)

一大題：選擇題(共10小題，每小題2分，共20分)

A.整環(huán)必為域B.交換環(huán)必為整環(huán)

1.下列是兩個命題變元P，Q的小項是(C)

C.整環(huán)必為交換環(huán)D.交換環(huán)必為含幺環(huán)

A.PA-iPAQB.-]PVQ

10.下列各圖是歐拉圖的是(D)

C.nPAQD.-IPVPVQ

2.令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為

(D)A.P-*-|QB.PV-|Q

C.PAQD.PA-iQ

3.下列等值式不正確的是(C)

A.-|(Vx)A。(mx)iA二大題：填空題(共10空，每空2分，共20分)

B.(Vx)(B~*A(x))(Vx)A(x)i.“如果雪是黑的，太陽從西邊出”是_a_命題。

C.(3x)(A(x)AB(x))?(3X)A(X)A(3X)B(X)2.集合A={1,2,3}上的二元關(guān)系R具有對稱性，反對稱性，自反性，則

D.(Vx)(Vy)(A(x)-B(y))<=>(3x)A(x)-*(Vy)B(y)R=(<1,1>,<2,2>,<3,3?。

4.設(shè)R為實數(shù)集，函數(shù)f：R-R,f(x)=2x,貝Ijf是(C)3.設(shè)R是實數(shù)集，在R上定義二元運算*為a*b=a+b+a-b,其中+和?是數(shù)的加法和乘法，

A.滿射函數(shù)B.入射函數(shù)C.雙射函數(shù)D.非入射非滿射則代數(shù)系統(tǒng)<R,*>的幺元是3,3的逆元是-3/4°

5.設(shè)A={a,b,c,d},A上的等價關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c?UIA,則對應(yīng)于R的A4.對稱關(guān)系具有自反性和對■稱性。

的劃分是(D)5.無向圖G具有一條歐拉回路，當且僅當G是連通圖，并且所有結(jié)點的度數(shù)都是偶

A.{{a},{b,c},00tkt9k}B.{{a,b),{c},n5ao60y}數(shù).

C.{{a},,{c},{d)}D.{{a,b},{c,d}}6.在下圖中，度數(shù)為3的結(jié)點有2個,出度為2的結(jié)點有」個。

6.設(shè)X,Y,Z是集合，“-”是集合相對補運算，下列等式不正確的是(A)

A.(X-Y)-z=x-(ynz)

B.(X-Y)-Z=(X-Z)-Y

C.(X-Y)-Z=(X-Z)-(Y-Z)

D.(X-Y)-Z=X-(YUZ)三大題：計算證明題(共8小題，共60分)

7.設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，則(B)1.(8分)如果論域是集合{a,b,c},試消去給定公式中的量詞：(三丫)(Vx)(x+y=0)。

A.對所有x屬于A,有x*Z=Z*x=Z

解:原公式o(3y)(a+y=0八b+y=0八c+y=0)(2分)

B.Z屬于A,且對所有x屬于A,有x*Z=Z*x=Z<=>(a+a=0Ab+a=0AC+a=0)v(a+b=0Ab+b=0AC4-b=0)

C.Z屬于A,且對所有x屬于A,有x*Z=Z*x=xv(a+c=0Ab+c=0AC+c=0)(2分)

D.Z屬于A,且存在x屬于A,有x*Z二Z*x二Z

2.(10分)設(shè)慶=伍,1)人),P(A)是A的幕集，十是集合對稱差運算。己知<P(A),十)

343

是群。在群<P(A),十》中，①找出其幺元。②找出任一元素的逆元。③求元素x使?jié)M足

{a}十x=

解：①因為0wP(A),且對任意BwP(A),0^B=B,所以0為幺元.(3分)

②對任意BcP(A),因為B十B=0,所以B"=B.(3分)4

③因為{a}十{a,b}=,所以產(chǎn){a,b}.并且由題可知x的取法唯一.所以x有唯一解:證明：圖中結(jié)點如上標示.建立映射:f：iTi1(3分)易見f為雙射.(1分)又因左圖的邊為

x={a,b}.(4分)(1,2),(2,3),(2,4)(3,5).(4,5),(5,6).一一對應(yīng)于右圖的

3.(8分)求公式1(P-Q)—(P--|Q)的主合取范式。邊：⑴，2'),(2',3')，(2',5')(3',4'),(4',5'),(4',6').所以兩個圖等價.(2分)

o(PA—>Q)c(―iPv—iQ)(l分)7.(10分)在謂詞邏輯中構(gòu)造下面推理的證明：每個人在學校讀書的就能獲得知識。所以

O((PA-iQ)A(-|PV-1Q))V(—>(PA-?Q)A-?(-iPv-?Q))(1分)如果沒有人獲得知識就沒有人在學校讀書。(個體域：所有人的集合)

<=>(PA」Q)V((「PVQ)A(PA「Q))(l分)譯:P(x):x在學校讀書;Q(x):x能獲得知識.

A「分)

=PQ(1(Vx)(P(x)->Q(x))=Tmx)Q(x)fT")P(x)(3分)

=(Pv(QA->Q))AHQV(PA「P)(l分)

證明:⑴"X)(P(X)TQ(X)P

0(PvQ)A(Pv「Q)A(「Pv->Q)。分)

(2)P(a)fQ(a)US(I)

4.(8分)在偏序集<乙<>中，