离散数学期末考试题(附答案和含解析1)

一、填空

2．A ，B ，C

4．公式(P ∧R ) ∨(S ∧R ) ∨⌝P 的主合取范式为(⌝P ∨S ∨R ) ∧(⌝P ∨⌝S ∨R ) 。 5．若解释I 的论域D 仅包含一个元素，则 ∃xP (x ) →∀xP (x ) 在I 下真值为。 6．设A={1，2，3，4}，A 上关系图如下，则。

⎛1 0= 0 0⎝

010010000⎫⎪ 1⎪0⎪⎪0⎪⎭

//备注：

⎛0

1R =

0 0⎝

10000100

0⎫ ⎪0⎪1⎪⎪0⎪⎭

R 2

7．设A={a，b ，c ，d}，其上偏序关系R 的哈斯图如下，则R=。

//备注：偏序满足自反性，反对称性，传递性

8．图

的补图为 。

//补图:给定一个图G, 又G 中所有结点和所有能使G 成为完全图的添加边组成的图, 成为补图. 自补图:一个图如果同构于它的补图, 则是自补图 9．设A={a，b ，c ，d} ，A 上二元运算如下：

那么代数系统的是，有的元素为，它们的逆元分别为。 //备注：二元运算为x*y=max{x,y}，x,y ∈A 。 10．下图所示的偏序集中，是格的为。

//（注：什么是格？即任意两个元素有最小上界 和最大

下界的偏序）

二、选择题

1、下列是真命题的有（ C 、D ）

A ． {a }⊆{{a }}； B ．{{Φ}}∈{Φ, {Φ}}； C ．

Φ∈{{Φ},Φ}； D ．{Φ}∈{{Φ}}。

2、下列集合中相等的有（ B 、C ）

A ．{4，3}⋃Φ；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ C ）个。 A ． 23 ； B ． 32 ； C ．

2⨯2

23⨯3； D ． 3。

//备注：A 的二元关系个数为：

2

n 2

个。

4、设R ，S 是集合A 上的关系，则下列说法正确的是（ A ） A ．若R ，S 是自反的， 则R S 是自反的； B ．若R ，S 是反自反的， 则R S 是反自反的； X C ．若R ，S 是对称的， 则R S 是对称的； X D ．若R ，S 是传递的， 则R S 是传递的。 X //备注：设R={,},S={}, 则S

R

={} ,

R S

={}

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下

R ={|s , t ∈p (A ) ∧(|s |

=|t |}，则P （A ）/ R=（ D ）

A ．A ； B ．P(A) ； C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}

6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的为（ C ）

//例题：画出下列各关系的哈斯图 1）

P={1,2,3,4},

的哈斯图。

2）A={2,3,6,12,24,36},的哈斯图。 3）A={1,2,3,5,6,10,15,30},的哈斯图

A ．f : I

7 A ） //双射既是单射又是满射

→E , f (x) = 2x ； B ．f : N→N ⨯N, f (n) = ； C ．f : R→I , f (x) = [x] ；//x的象 D ．f :I→N, f (x) = | x | 。

（注：I —整数集，E —偶数集， N —自然数集，R —实数集） 8、图 中 从v1到v3长度为3 的通路有（ D ）条。

//备注：分别是v1->v1->v1->v3，v1->v4->v1->v3，v1->v3->v1->v3

A ．0；

B ．1； C ．2； D ．3。

9、下图中既不是（欧拉）图，也不是（哈密顿）图的图是（ B ）

10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ A ）个4度结点。 A ．1；

B ．2；

C ．3；

D ．4 。

//备注：树的顶点数=边数+1 7+3×3+4n=2（7+3+n-1） 解得n=1 三、证明题

1、R 是集合X 上的一个自反关系，求证：R 是对称和传递的，当且仅当和在R 中有在R 中。 证： ⇒∀a , b , c ∈X , ∈ R , ∈ R ∈ R ∈ R ∈ R ∈ R a , b ∈X ∈ R ∈ R

⇐∴ ∈ R 所以R 是对称的

若

∈ R ， ∈ R 则 ∈ R ∧∈R ∴ ∈ R 即R 是传递的

2、f 和g 都是群到的同态映射。

证明是的一个子群。其中C=

证：

{x |x ∈G 1且f (x ) =g (x )}

-1

∀a , b ∈C ，有 f (a ) =g (a ), f (b ) =g (b ) ，又f (b ) =f

-1

(b ) , g (b -1) =g -1(b )

∴f (b -1) =f -1(b ) =g -1(b ) =g (b -1) ∴f (a b -1) =f (a ) *f -1(b ) =g (a ) *g (b -1) =g (a b -1)

∴a b -1∈C ∴

3、G= (|V| = v，|E|=e ) 是每一个面至少由k （k ≥3）条边围成的连通平面图，则 森图（Peterson ）图是非平面图。（11分） 证：

e ≤

k (v -2)

k -2， 由此证明①设G 有r 个面，则（8分）

2e =∑d (F i ) ≥rk

i =1

r

r ≤

，即

2e 2e k (v -2)

2=v -e +r ≤v -e +e ≤

k 即得 k 。k -2。而 v -e +r =2故

k =5, e =15, v =10，这样e ≤

②彼得森图为

k (v

-2)

k -2不成立，

四、逻辑推演

1、用证明下题

∀x (P (x ) →Q (x )) ⇒∀xP (x ) →∀xQ (x )

∀xP (x ) ①

② ③ ④ ⑤

P （附加前提）

P (c )

US ①

∀x (P (x ) →Q (x )) P P (c ) →Q (c )

US ③

Q (c ) T ②

④I

∀xQ (x ) ⑥ UG ⑤

⑦

∀xP (x ) →∀xQ (x ) CP

五、计算题

1、设集合A={a，b ，c ，d}上的关系R={ , , , }用求出R 解：

⎛0

1M R =

0 0⎝

100001000⎫⎪0⎪1⎪⎪0⎪⎭

M R 2

⎛1

=M R M R =

0 0⎝

01001000

⎛010⎫ ⎪

101⎪

M R 3=M R 2 M R =

000⎪ ⎪ 0⎪⎝00⎭0

100

1⎫⎪0⎪0⎪⎪0⎪⎭

M R 4=M R 3

⎛1

M R =

0 0⎝

01001000

⎛110⎫

⎪

1⎪ 11

M t (R ) =M R +M R 2+M R 3+M R 4=

000⎪

⎪ 000⎪⎝⎭，

1

100

1⎫⎪1⎪1⎪⎪0⎪⎭

t (R)={ , , , , , , , , }

一、填空

2．A ，B ，C

4．公式(P ∧R ) ∨(S ∧R ) ∨⌝P 的主合取范式为(⌝P ∨S ∨R ) ∧(⌝P ∨⌝S ∨R ) 。 5．若解释I 的论域D 仅包含一个元素，则 ∃xP (x ) →∀xP (x ) 在I 下真值为。 6．设A={1，2，3，4}，A 上关系图如下，则。

⎛1 0= 0 0⎝

010010000⎫⎪ 1⎪0⎪⎪0⎪⎭

//备注：

⎛0

1R =

0 0⎝

10000100

0⎫ ⎪0⎪1⎪⎪0⎪⎭

R 2

7．设A={a，b ，c ，d}，其上偏序关系R 的哈斯图如下，则R=。

//备注：偏序满足自反性，反对称性，传递性

8．图

的补图为 。

//补图:给定一个图G, 又G 中所有结点和所有能使G 成为完全图的添加边组成的图, 成为补图. 自补图:一个图如果同构于它的补图, 则是自补图 9．设A={a，b ，c ，d} ，A 上二元运算如下：

那么代数系统的是，有的元素为，它们的逆元分别为。 //备注：二元运算为x*y=max{x,y}，x,y ∈A 。 10．下图所示的偏序集中，是格的为。

//（注：什么是格？即任意两个元素有最小上界 和最大

下界的偏序）

二、选择题

1、下列是真命题的有（ C 、D ）

A ． {a }⊆{{a }}； B ．{{Φ}}∈{Φ, {Φ}}； C ．

Φ∈{{Φ},Φ}； D ．{Φ}∈{{Φ}}。

2、下列集合中相等的有（ B 、C ）

A ．{4，3}⋃Φ；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ C ）个。 A ． 23 ； B ． 32 ； C ．

2⨯2

23⨯3； D ． 3。

//备注：A 的二元关系个数为：

2

n 2

个。

4、设R ，S 是集合A 上的关系，则下列说法正确的是（ A ） A ．若R ，S 是自反的， 则R S 是自反的； B ．若R ，S 是反自反的， 则R S 是反自反的； X C ．若R ，S 是对称的， 则R S 是对称的； X D ．若R ，S 是传递的， 则R S 是传递的。 X //备注：设R={,},S={}, 则S

R

={} ,

R S

={}

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下

R ={|s , t ∈p (A ) ∧(|s |

=|t |}，则P （A ）/ R=（ D ）

A ．A ； B ．P(A) ； C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}

6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的为（ C ）

//例题：画出下列各关系的哈斯图 1）

P={1,2,3,4},

的哈斯图。

2）A={2,3,6,12,24,36},的哈斯图。 3）A={1,2,3,5,6,10,15,30},的哈斯图

A ．f : I

7 A ） //双射既是单射又是满射

→E , f (x) = 2x ； B ．f : N→N ⨯N, f (n) = ； C ．f : R→I , f (x) = [x] ；//x的象 D ．f :I→N, f (x) = | x | 。

（注：I —整数集，E —偶数集， N —自然数集，R —实数集） 8、图 中 从v1到v3长度为3 的通路有（ D ）条。

//备注：分别是v1->v1->v1->v3，v1->v4->v1->v3，v1->v3->v1->v3

A ．0；

B ．1； C ．2； D ．3。

9、下图中既不是（欧拉）图，也不是（哈密顿）图的图是（ B ）

10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ A ）个4度结点。 A ．1；

B ．2；

C ．3；

D ．4 。

//备注：树的顶点数=边数+1 7+3×3+4n=2（7+3+n-1） 解得n=1 三、证明题

1、R 是集合X 上的一个自反关系，求证：R 是对称和传递的，当且仅当和在R 中有在R 中。 证： ⇒∀a , b , c ∈X , ∈ R , ∈ R ∈ R ∈ R ∈ R ∈ R a , b ∈X ∈ R ∈ R

⇐∴ ∈ R 所以R 是对称的

若

∈ R ， ∈ R 则 ∈ R ∧∈R ∴ ∈ R 即R 是传递的

2、f 和g 都是群到的同态映射。

证明是的一个子群。其中C=

证：

{x |x ∈G 1且f (x ) =g (x )}

-1

∀a , b ∈C ，有 f (a ) =g (a ), f (b ) =g (b ) ，又f (b ) =f

-1

(b ) , g (b -1) =g -1(b )

∴f (b -1) =f -1(b ) =g -1(b ) =g (b -1) ∴f (a b -1) =f (a ) *f -1(b ) =g (a ) *g (b -1) =g (a b -1)

∴a b -1∈C ∴

3、G= (|V| = v，|E|=e ) 是每一个面至少由k （k ≥3）条边围成的连通平面图，则 森图（Peterson ）图是非平面图。（11分） 证：

e ≤

k (v -2)

k -2， 由此证明①设G 有r 个面，则（8分）

2e =∑d (F i ) ≥rk

i =1

r

r ≤

，即

2e 2e k (v -2)

2=v -e +r ≤v -e +e ≤

k 即得 k 。k -2。而 v -e +r =2故

k =5, e =15, v =10，这样e ≤

②彼得森图为

k (v

-2)

k -2不成立，

四、逻辑推演

1、用证明下题

∀x (P (x ) →Q (x )) ⇒∀xP (x ) →∀xQ (x )

∀xP (x ) ①

② ③ ④ ⑤

P （附加前提）

P (c )

US ①

∀x (P (x ) →Q (x )) P P (c ) →Q (c )

US ③

Q (c ) T ②

④I

∀xQ (x ) ⑥ UG ⑤

⑦

∀xP (x ) →∀xQ (x ) CP

五、计算题

1、设集合A={a，b ，c ，d}上的关系R={ , , , }用求出R 解：

⎛0

1M R =

0 0⎝

100001000⎫⎪0⎪1⎪⎪0⎪⎭

M R 2

⎛1

=M R M R =

0 0⎝

01001000

⎛010⎫ ⎪

101⎪

M R 3=M R 2 M R =

000⎪ ⎪ 0⎪⎝00⎭0

100

1⎫⎪0⎪0⎪⎪0⎪⎭

M R 4=M R 3

⎛1

M R =

0 0⎝

01001000

⎛110⎫

⎪

1⎪ 11

M t (R ) =M R +M R 2+M R 3+M R 4=

000⎪

⎪ 000⎪⎝⎭，

1

100

1⎫⎪1⎪1⎪⎪0⎪⎭

t (R)={ , , , , , , , , }