离散数学习题集(十五套)

离散数学习历年真题

离散数学试题与答案试卷一

一、填空 20% （每小题2分）

1．设 A {x|(x N)且(x 5)},B {x|x E且x 7}（N：自然数集，E+ 正偶数） 则

A B 。

2．A，B，C表示三个集合，文图中阴影部分的集合表达式为 。

3．设P，Q 的真值为0，R，S的真值为1，则

(P (Q (R P))) (R S)的真值= 。

4．公式(P R) (S R) P的主合取范式为 。

5．若解释I的论域D仅包含一个元素，则 xP(x) xP(x) 在I下真值为 。

6．设A={1，2，3，4}，A上关系图为

则 R2 = 。

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

则 R= 。

8．图的补图为 。

9．设A={a，b，c，d} ，A上二元运算如下：

离散数学习历年真题

那么代数系统<A，*>的幺元是 ，它们的逆元分别为 。

10．下图所示的偏序集中，是格的为 。

二、选择 20% （每小题 2分）

1、下列是真命题的有（ ） A． {a} {{a}}；

B．{{ }} { ,{ }}；

C． {{ }, }； D． { } {{ }}。 2、下列集合中相等的有（ ）

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

3 3

； D． 32 2

。

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

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

R { s,t |s,t p(A) (|s| |t|}则

P（A）/ R=（ ）

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上包含关系“ ”的哈斯图为（

）

离散数学习历年真题

7、下列函数是双射的为（ ）

A．f : I E , f (x) = 2x ； B．f : N N N, f (n) = <n , n+1> ； C．f : R I , f (x) = [x] ； D．f :I N, f (x) = | x | 。 （注：I—整数集，E—偶数集， N—自然数集，R—实数集） 8、图 中 从v1到v3长度为3 的通路有（ ）条。

A． 0； B． 1；

C． 2；

D． 3。

9、下图中既不是Eular图，也不是Hamilton图的图是（ ）

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

三、证明 26%

１、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当

< a, b> 和<a , c>在R中有<.b , c>在R中。（8分）

２、f和g都是群<G1 ,★>到< G2, *>的同态映射，证明<C , ★>是<G1, ★>的一个子群。其中

C={x|x G1且f(x) g(x)} (8分)

３、G=<V, E> (|V| = v，|E|=e ) 是每一个面至少由k（k 3）条边围成的连通平面图，则

此证明彼得森图（Peterson）图是非平面图。（11分）

e

k(v 2)

k 2， 由

离散数学习历年真题

四、逻辑推演 16%

用CP规则证明下题（每小题 8分） 1、A B C D,D E F A F 2、 x(P(x) Q(x)) xP(x) xQ(x)

五、计算 18%

1、设集合A={a，b，c，d}上的关系R={<a , b > ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 （9分）

2、如下图所示的赋权图表示某七个城市v1,v2, ,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分）

试卷一答案：

一、填空 20% （每小题2分）

1、{0，1，2，3，4，6}； 2、(B C) A；3、1； 4、( P S R) ( P S R)； 5、1；6、{<1,1>,

<1,3>, <2,2>, <2,4> }；7、{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>} IA ；8、

9、a ；a , b , c ,d ；a , d , c , d ；10、

c; 二、选择 20% （每小题 2分）

三、证明 26%

1、 证：

“ ” a,b,c X 若<a,b>,<a,c> R由R对称性知<b,a>,<c,a R，由R传递性得

<b,c> R

离散数学习历年真题

“ ” 若<a,b> R，<a,c> R有 <b,c> R 任意 a,b X，因<a,a> R若

<a,b> R <b,a> R 所以R是对称的。

<a,c> R 即R是传递的。 若<a,b> R，<b,c> R 则 <b,a> R b,c R

2、 证

a,b C

，有

f(a) g(a),f(b) g(b)

，又

f(b 1) 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 < C , ★> 是 < G1 , ★>的子群。

3、 证：

r

①设G有r个面，则

2e d(Fi) rk

i 1

，即

r

2e2e

2 v e r v e

k。而 v e r 2故k即

得

e

k(v 2)

k 2。（8分）

②彼得森图为k 5,e 15,v 10，这样

e

k(v 2)

k 2不成立，

所以彼得森图非平面图。（3分）

二、 逻辑推演 16% 1、 证明：

①A ②A B

③A B C D ④C D ⑤D ⑥D E ⑦D E F ⑧F ⑨A F 2、证明

P（附加前提） T①I P T②③I T④I T⑤I P T⑥⑦I CP

离散数学习历年真题

① 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

三、 计算 18% 1、 解：

0100 1

0 M 1010 1001 R

0001 M 01

R2 MR MR

00

000

0

00 ，

000

0

0

1

01 M010 R3 MR M 1

2

R

0000 0000

1010 M101 1R4 MR3

M 0

R

000 Mt(R) MR MR2 M 1R3 MR4 0

0000 0

0 t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > ,

< b , d > , < c , d > }

2、 解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：

树权C(T)=23+1+4+9+3+17=57即为总造价。

试卷二试题与答案

一、填空 20% （每小题2分）

1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为

；“虽然你努力了，但还是失败了”的翻译为

11

1 111 001 00

0 ，

离散数学习历年真题

。 2、论域D={1，2}，指定谓词P

则公式 x 真值为 。 2、 设S={a1 ，a2 ， ，a8}，Bi是S的子集，则由B31所表达的子集是 。

}，则R= 3、 设A={2，3，4，5，6}上的二元关系R { x,y |x y x是质数

（列举法）。

R的关系矩阵MR=

。

5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R= ；A上既是对称的

又是反对称的关系R= 。

6、设代数系统<A，*>，其中A={a，b，c},

则幺元是 ；是否有幂等 性 ；是否有对称性 。

7、4阶群必是 群或

群。 8、下面偏序格是分配格的是 。

9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 10、公式(P ( P Q)) (( P Q) R的根树表示为

。

离散数学习历年真题

二、选择 20% （每小题2分）

1、在下述公式中是重言式为（ ）

A．(P Q) (P Q)；B．(P Q) ((P Q) (Q P))； C． (P Q) Q； D．P (P Q)。

2、命题公式 ( P Q) ( Q P) 中极小项的个数为（ ），成真赋值的个数为（ ）。

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

S

3、设S { ,{1},{1,2}}，则 2 有（ ）个元素。

A．3； B．6； C．7； D．8 。 4、 设S { 1, 2, 3 }，定义S S上的等价关系

R { a,b , c,d | a,b S S, c,d S S,a d b c}则由 R产 生的S S上一个划分共

有（ ）个分块。

A．4； B．5； C．6； D．9 。 5、设S { 1, 2, 3 }，S上关系R的关系图为

则R具有（ ）性质。

A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。 6、设 , 为普通加法和乘法，则（ ） S, , 是域。 A．S {x|x a b3,C．S {x|x 2n 1,

a,b Q} B．S {x|x 2n,a,b Z}

n Z} D．S {x|x Z x 0}= N 。

7、下面偏序集（ ）能构成格。

8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。

离散数学习历年真题

A．1； B．2； C．3； D．4 。 9、在如下各图中（ ）欧拉图。

10、设R是实数集合，“ ”

为普通乘法，则代数系统<R ，×> 是（ ）。

A．群； B．独异点； C．半群 。

三、证明 46%

1、 设R是A上一个二元关系，

S { a,b |(a,b A) (对于某一个c A,有 a,c R且 c,b R)}试证明若R是A上一个等价关

系，则S也是A上的一个等价关系。（9分）

2、 用逻辑推理证明：

所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）

3、 若f:A B是从

A

到

B

的函数，定义一个函数g:B 2

A

对任意b B有

g(b) {x|(x A) (f(x) b)}，证明：若f是A到B的满射，则g是从B到 2A 的单射。（10分）

4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）

5、 设G是具有n个结点的无向简单图，其边数

m

1

(n 1)(n 2) 22，则G是Hamilton图（8分）

四、计算 14%

1、 设<Z6,+6>是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出<Z6,+6>的所有子

群及其相应左陪集。（7分）

2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）

试卷二答案：

离散数学习历年真题

一、 填空 20%（每小题2分）

1、 P Q；P Q2、T 3、B31 B00011111 {a4,a5,a6,a7,a8}4、

R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；

1 1 0 1 0

1111

1111 0011

1111 0000 5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein四元

1

n(n 1)2群；循环群 8、 B 9、；图中无奇度结点且连通 10 、

二、

三、 证明 46%

1、（9分）

（1） S自反的

a A，由R自反， ( a,a R) ( a,a R)， a,a S

（2） S对称的

a,b A

a,b S ( a,c R) ( c,b R)

( a,c R) ( c,b R) b,a S

（3） S传递的

S定义 R对称 R传递

a,b,c A

a,b S b,c S

( a,d R) ( d,b R) ( b,e R) ( e,c R) ( a,b R) ( b,c R) a,c S

R传递 S定义

由（1）、（2）、（3）得；S是等价关系。 2、11分

证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华 上述句子符号化为：

前提： x(P(x) Q(x))、S(a) P(a) 结论： x(S(x) Q(x)) 3分

①S(a) P(a) ② x(P(x) Q(x)) ③P(a) Q(a) ④P(a)

P P US② T①I

离散数学习历年真题

⑤Q(a). ⑥S(a) ⑦S(a) Q(a) ⑧ x(S(x) Q(x) ３、１0分

T③④I T①I T⑤⑥I EG⑦

11分

证明 ： b1,b2 B,(b1 b2) f满射 a1,a2 A

使f(a1) b1,f(a2) b2,且f(a1) f(a2),由于f是函数, a1 a2 又g(b1) {x|(x A) (f(x) b1)},g(b2) {x|(x A) (f(x) b2)} a1 g(b1),a2 g(b2)但a1 g(b2),a2 g(b1) g(b1) g(b2)由b1,b2任意性知,g为单射。

4、8分

证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。

5、8分

证明： 证G中任何两结点之和不小于n。

反证法：若存在两结点u，v 不相邻且d(u) d(v) n 1,令V1 {u,v}，则G-V1是具有n-2个结点的简单图，它的边数

为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。

所以G为Hamilton图.

计算 14%

1、 7分

解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6> {[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]} {[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]} {[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]} Z6的左陪集：Z6 。

2、 7分

m'

11(n 1)(n 2) 2 (n 1)m' (n 2)(n 3) 122,可得，这与G1=G-V1为n-2个结点

四、

试卷三试题与答案

离散数学习历年真题

一、 填空 20% （每空 2分）

1、 设 f，g是自然数集N上的函数 x N,

f(x) x 1,g(x) 2x，

则f g(x) 。

2、 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,

则s（R）= 。

}，则用列举法 3、 A={1，2，3，4，5，6}，A上二元关系T { x,y |x y是素数

T= ； T的关系图为

； T具有 性质。

4、 集合A {{ ,2},{2}}的幂集2= 。

A

5、 P，Q真值为0 ；R，S真值为1。则wff(P (R S)) ((P Q) (R S))的真值

为 。

6、 wff ((P Q) R) R的主合取范式为 。

7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词

wff

x(P(x) y(O(y) N(y,x)))的自然语言是

。 8、 谓词wff x y( z(P(x,z) P(y,z)) uQ(x,y,u))的前束范式为

。

二、 选择 20% （每小题 2分）

1、 下述命题公式中，是重言式的为（ ）。

A、(p q) (p q)； B、(p q) ((p q)) (q p))； C、 (p q) q； D、(p p) q。 2、 wff

(p q) r的主析取范式中含极小项的个数为（ ）。

A 、2； B、 3； C、5； D、0； E、 8 。 3、 给定推理

① x(F(x) G(x)) ②F(y) G(y) ③ xF(x) ④F(y) ⑤G(y)

P US① P ES③ T②④I

离散数学习历年真题

⑥ xG(x)

UG⑤

x(F(x) G(x)) xG(x)

推理过程中错在（ ）。

A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥

4、 设S1={1，2， ，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，

S5={3，5}，在条件X S1且X S3下X与（ ）集合相等。 A、 X=S2或S5 ； B、X=S4或S5；

C、X=S1，S2或S4； D、X与S1， ，S5中任何集合都不等。

}，5、 设R和S是P上的关系，P是所有人的集合，R { x,y |x,y P x是y的父亲

S { x,y |x,y P x是y的母亲}则S 1 R表示关系 （ ）。 }； A、{ x,y |x,y P x是y的丈夫

}； B、{ x,y |x,y P x是y的孙子或孙女

}。 C、 ； D、{ x,y |x,y P x是y的祖父或祖母

6、 下面函数（ ）是单射而非满射。

A、f:R R,B、f:Z R,C、f:R Z,D、f:R R,

f(x) x2 2x 1；

f(x) lnx；

f(x) [x],[x]表示不大于x的最大整数；

f(x) 2x 1。

其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。 7、 设S={1，2，3}，R为S上的关系，其关系图为

则R具有（ ）的性质。

A、 自反、对称、传递； B、什么性质也没有；

C、反自反、反对称、传递； D、自反、对称、反对称、传递。 8、 设S { ,{1},{1,2}}，则有（ ） S。

A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。 9、 设A={1 ,2 ,3 }，则A上有（ ）个二元关系。

A、23 ； B、32 ； C、2； D、2。 10、全体小项合取式为（ ）。

A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。

23

32

离散数学习历年真题

三、 用CP规则证明 16% （每小题 8分）

1、A B C D,D E F

A F

2、 x(P(x) Q(x)) xP(x) xQ(x)

四、（14%）

集合X={<1,2>, <3,4>, <5,6>, }，R={<<x1,y1>,<x2,y2>>|x1+y2 = x2+y1} 。 1、 证明R是X上的等价关系。 （10分） 2、 求出X关于R的商集。（4分）

五、（10%）

设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算求出R的传递闭包。（6分）

六、（20%）

1、（10分）设f和g是函数，证明f g也是函数。 2、（10分）设函数g:S T答案：

五、 填空 20%（每空2分） 1

、

2(x+1)

；

2

、

f:T S，证明 f:T S有一左逆函数当且仅当f是入射函数。

{ a ,a , a ,b , a ,c , c ,c , b ,a , c ,a }

；3、

{ 2,1 , 3,1 , 5,1 , 4,2 , 6,2 , 6,3 ；

4、

反对称性、反自反性；4、{ ,{{ ,2}},{{2}},{{ ,2},{2}}}；5、1；

6、(P Q R) ( P Q R) (P Q R)；7、任意x，如果x是素数则存在一个y，y是奇数且y整除x ；8、 x y z u( P(x,z) P(y,z) Q(x,y,u))。

六、 选择 20%（每小题 2分）

七、 证明 16%(每小题8分) 1、

离散数学习历年真题

①A ②A B

③A B C D ④C D ⑤D ⑥D E ⑦D E F ⑧F ⑨A F 2、

P（附加前提） T①I P T②③I T④I T⑤I P T⑥⑦I CP

xP(x) xQ(x) ( x)P(x) xQ(x)本题可证 x(P(x) Q(x)) ( xP(x) xQ(x)

① ( xP(x)) ② x( P(x)) ③ P(a)

④ x(P(x) Q(x)) ⑤P(a) Q(a) ⑥Q(a) ⑦ xQ(x)

⑧ ( xP(x) xQ(x) 八、 14% （1） 证明：

1、

自反性： x,y X,由于x y x y x,y , x,y R2、

P（附加前提） T①E ES② P US④ T③⑤I EG⑥ CP

R自反

对称性： x1,y1 X, x2,y2 X

当 x1,y1 , x2,y2 R时 即x1 y2 x2 y1也即x2 y1 x1 y2

故 x2,y2 , x1,y1 R R有对称性

3、

传递性： x1,y1 X, x2,y2 X

x3,y3 X

当 x1,y1 , x2,y2 R且 x2,y2 , x3,y3 R时

x1 y2 x2 y1即

x2 y3 x3 y2

(1)(2)

离散数学习历年真题

(1) (2)

x1 y2 x2 y3 x2 y1 x3 y2

即x1 y3 x3 y1

故 x1,y1 , x3,y3 R R有传递性

由（1）（2）（3）知：R是X上的先等价关系。 2、X/R={[ 1,2 ]R} 九、 10%

0

1MR

0 0 1、

1

0000100

0 0 1 0 ； 关系图

1000100100010000 1 0 0

MR2

2、

1

0

MR MR

0 0 0 1

MR

0 0 1 0

MR

0 0

10000100

MR3 MR2

1 0 0 0

0 1

MR2 0 0 MR5 MR3,MR6 MR4, 1 1 0 0

110011001 1 1 0

MR4 MR3

Mt(R) MR MR2 MR3 MR4

t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > }。

六、 20%

f g { x,y |x domf x domg y f(x) y g(x)}

{ x,y |x domf domg y f(x) g(x)}1、（1）

令h f g

domf g domh {x|x domf domg,f(x) g(x)}

（2）h { x,y |x domf domg y h(x) f(x) g(x)}

对x domh若有y1,y2使得

y1 h(x) f(x) g(x),y2 h(x) f(x) g(x)

由于f(或g)是函数,有y1 y2即

x domh有唯一y使得y h(x)

离散数学习历年真题

f g也是函数。

2、证明：

" "若f有一左逆g,则对 t T故g f是入射,所以f是入射。 " "f是入射,

g f(t) t

f:T S定义如下:

s f(T),由f入射, |t T,使f(t) s此时令g(s) t,若s f(T)令g(s) c T则对 s S,g(s)只有一个值t或c且若f(t) s则g f(t) g(s) t,故g是f的左逆元

即若f入射,必能构造函数g,使g为f左逆函数。

试卷四试题与答案

一、 填空 10% （每小题 2分）

1、 若P，Q，为二命题，P Q真值为0 当且仅当 。

2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，L(x,y):x y则命题的逻辑谓

词公式为 。

3、 谓词合式公式 xP(x) xQ(x)的前束范式为 。

4、 将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法

称为换名规则。

5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则

被称为存在量词消去规则，记为ES。

二、 选择 25% （每小题 2.5分）

1、 下列语句是命题的有（ ）。

A、 明年中秋节的晚上是晴天； B、x y 0； C、xy 0当且仅当x和y都大于0； D、我正在说谎。

2、 下列各命题中真值为真的命题有（ ）。

A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数； C、2+2≠4当且仅当3是奇数； D、2+2≠4当且仅当3不是奇数；

3、 下列符号串是合式公式的有（ ）

A、P Q；B、P P Q；C、( P Q) (P Q)；D、 (P Q)。 4、 下列等价式成立的有（ ）。

A、P Q Q P；B、P (P R) R；

离散数学习历年真题

C、 P (P Q) Q； D、P (Q R) (P Q) R。 5、 若A1,A2 An和B为wff，且A1 A2 An B则（ ）。 A、称A1 A2 An为B的前件； B、称B为A1,A2 An的有效结论

C、当且仅当A1 A2 An B F；D、当且仅当A1 A2 An B F。 6、 A，B为二合式公式，且A B，则（ ）。

A、A B为重言式； B、A* B*

；

C、A B； D、A* B*

； E、A B为重言式。

7、 “人总是要死的”谓词公式表示为（ ）。 （论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。 A、M(x) Mortal(x)； B、M(x) Mortal(x) C、 x(M(x) Mortal(x))；D、 x(M(x) Mortal(x))

8、 公式A x(P(x) Q(x))的解释I为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A的真值为（A、1； B、0； C、可满足式； D、无法判定。 9、 下列等价关系正确的是（ ）。 A、 x(P(x) Q(x)) xP(x) xQ(x)； B、 x(P(x) Q(x)) xP(x) xQ(x)； C、 x(P(x) Q) xP(x) Q； D、 x(P(x) Q) xP(x) Q。 10、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ②F(y) G(y) US① ③ xF(x) P ④F(y) ES③ ⑤G(y) T②④I ⑥ xG(x)

EG⑤

A、②；B、④；C、⑤；D、⑥

三、 逻辑判断30%

1、 用等值演算法和真值表法判断公式A ((P Q) (Q P)) (P Q)的类型。（10分） 2、 下列问题，若成立请证明，若不成立请举出反例：（10分）

（1） 已知A C B C，问A B成立吗？

。 ）

离散数学习历年真题

（2） 已知 A B，问A B成立吗？

3、 如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。问：若厂方拒绝

增加工资，面罢工刚开始，罢工是否能够停止。（10分）

四、计算10%

1、 设命题A1，A2的真值为1，A3，A4真值为0，求命题

(A1 (A2 (A3 A1))) (A2 A4)的真值。（5分）

2、 利用主析取范式，求公式 (P Q) Q R的类型。（5分）

五、谓词逻辑推理 15%

符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。

六、证明：（10%）

设论域D={a , b , c}，求证： xA(x) xB(x) x(A(x) B(x))。 答案：

十、 填空 10%（每小题2分）

1、P真值为1，Q的真值为0；2、 x(F(x) L(x,0) y(F(y) L(y,x))；3、 x( P(x) Q(x))；4、约束变元；5、 xA(x) A(y)，y为D的某些元素。

十一、 选择 25%（每小题2.5分）

十二、 逻辑判断 30% 1、（1）等值演算法

A ((P Q) (Q P)) (P Q) (P Q) (P Q) T

（2）真值表法

所以A

离散数学习历年真题

2、（1）不成立。

若取C T

则A T T

B T T有A C B C T

但A与B不一定等价，可为任意不等价的公式。 （2）成立。 证明： A B

充要条件 A B T

T ( A B) ( B A) (A B) (B A)

即： ( B A) ( A B) (A B) (B A) A B

所以A B T故 A B。

3、解：设P：厂方拒绝增加工资；Q：罢工停止；R罢工超壶过一年；R：撤换厂长 前提：P ( (R S) Q),①P ( (R S) Q) ②P

③ (R S) Q ④ R ⑤ R S ⑥ (R S) ⑦ Q

罢工不会停止是有效结论。 四、计算 10%

P, R 结论： Q

P P T①②I P T④I T⑤E T③⑥I

(1 (1 0 0))) (1 1) (1 (1 0) 1

（1） 解： (1 0) 1 1 1 1

(P Q) Q R ( P Q) (Q R)

(P Q) (Q R) P Q Q R F

（2）

它无成真赋值，所以为矛盾式。

五、谓词逻辑推理 15%

解：M(x):x是人;

F(x):x是花;G(x):x是杂草;H(x,y):x喜欢y

x(M(x) y(F(y) H(x,y))) x(M(x) y(G(y) H(x,y)))

x(F(x) G(x))

证明：

⑴ x(M(x) y(F(y) H(x,y))) ⑵M(a) y(F(y) H(a,y))

P ES⑴

离散数学习历年真题

⑶M(a)

⑷ y(F(y) H(a,y))

⑸ x(M(x) y(G(y) H(x,y))) ⑹M(a) y(G(y) H(a,y)) ⑺ y(G(y) H(a,y)) ⑻ y(H(a,y) G(y)) ⑼F(z) H(a,z) ⑽H(a,z) G(z) ⑾F(z) G(z) ⑿ x(F(x) G(x))

十三、

证明10%

T⑵I T⑵I P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾

xA(x) xB(x) (A(a) A(b) A(c) (B(a) B(b) B(c) (A(a) B(a)) (A(a) B(b)) (A(a) B(c)) (A(b) B(a)) (A(b) B(b)) (A(b) B(c)) (A(c) B(a)) (A(c) B(b)) (A(c) B(c)) (A(a) B(a)) (A(b) B(b)) (A(c) B(c) x(A(x) B(x))

试卷五试题与答案

一、填空15%（每空3分）

1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 个5度结点。 2、n阶完全图，Kn的点数X (Kn) = 。

3、有向图

中从v1到v2长度为2的通路有 条。

4、设[R，+，·]是代数系统，如果①[R，+]是交换群 ②[R，·]是半群

③ 则称[R，+，·]为环。 5、设[L, , ]是代数系统，则[L, , ]满足幂等律，即对 a L有 。

本文来源：https://www.bwwdw.com/article/q464.html