2012年离散数学形成性考核全部答案

离散数学形成性考核作业（一）

参考答案

第1章 集合及其运算

1．用列举法表示 “大于2而小于等于9的整数” 集合． {3,4,5,6,7,8,9}。

2．用描述法表示 “小于5的非负整数集合” 集合． {x∣x∈Z∧0≤x≤5}。

3．写出集合B={1, {2, 3 }}的全部子集． { }，{1}，{{2, 3 }}，{1, {2, 3 }}。

4．求集合A={?,{?}}的幂集． Φ，{Φ}，{{Φ}}，{Φ，{Φ}}。

5．设集合A={{a }, a }，命题：{a }?P(A) 是否正确，说明理由．

错误。 P(A)中无元素a。 6．设A?{1,2,3},B?{1,3,5},C?{2,4,6},求

(1)A?B (2)A?B?C (3)C - A (4)A?B

（1）{3}；（2）{1，2，3，4，5，6}；（3）{4，6}；（4）{2，5}。

7．化简集合表示式：((A?B )?B) - A?B．

((A∪B )∩ B) - A∪B =（ B- A）∪B = （B∩～ A）∪B = B。

1

8．设A, B, C是三个任意集合，试证： A - (B?C ) = (A - B ) - C．

A-(B∪C) = A∩～(B∪C) = A∩～B∩～C = (A - B)–C。 9．填写集合{4, 9 }?{9, 10, 4}之间的关系．

10．设集合A = {2, a, {3}, 4}，那么下列命题中错误的是（ A ）． A．{a}?A B．{ a, 4, {3}}?A C．{a}?A D．??

A

11．设B = { {a}, 3, 4, 2}，那么下列命题中错误的是（ B ）． A．{a}?B B．{2, {a}, 3, 4}?B C．{a}?B D．{?}?B

第2章 关系与函数

1．设集合A = {a, b}，B = {1, 2, 3}，C = {3, 4}，求 A?(B?C)，(A?B)?(A?C ) ，并验证A?(B?C ) = (A?B)?(A?C )． A×(B∩C ) = {a, b}×{3} = {,}；

（A×B）∩（A×C）= {,,,,,}∩

{,,}={,

,3>}

验证了A×(B∩C ) =（A×B）∩（A×C）。

2

2．对任意三个集合A, B和C，若A?B?A?C，是否一定有B?C？为什么？

当A是空集时，不一定有B?C。 当A不是空集时，一定有B?C。

x∈A，y∈B，∈A×B， ∈A×C， y∈C。即B?C。 3．对任意三个集合A, B和C，试证 若A?B = A?C，且A?则B = C．

x∈A，y∈B，∈A×B， ∈A×C， y∈C。即B?C； 同理：C?B，B = C 。

4．写出从集合A = {a，b，c }到集合B = {1}的所有二元关系． Φ，{}，{}，{}，{,}，{,},

{,}{,,}。

5．设集合A = {1，2，3，4，5，6 }，R是A上的二元关系，R ={?a ,

?，

b??a , b?A , 且a +b = 6}写出R的集合表示式．

{<1,5>,<5,1>,<2,4>,<4,2>,<3,3>}。

6．设R从集合A = {a，b，c，d }到B = {1，2，3}的二元关系，写出关系

R ={?a , 1?，?a , 3?，?b , 2?，?c , 2?，?c , 3?}的关系矩

阵，并画出关系图．

?1?0 MR = ??0??0

01101??0?1??0?

3

7．设集合A={a , b , c , d}，A上的二元关系

R ={?a , b?，?b , d?，?c , c?，?c , d?}， S ={?a , c?，?b , d?，?d , b?，?d , d?}．

求R?S，R?S，R-S，~（R?S），R?S ．

R∪S = {，，，，，，}；

R∩S = {}；

R - S = {，，， }；

～(R∪S) = {，，，，，，，

，}；

R?S = {，， ，，，}； 8．设集合A={1 , 2 }，B = { a , b , c}，C ={? , ?}，R是从A到B的二元关系，S是从B到C的二元关系，且R = {<1 , a>，<1 , b>，<2 , c>}， S= {，}， 用关系矩阵求出复合关系R·S． M R·S = MR·MS = ??1?010?00????01???01???01????00??1??； 0? R·S = {<1，β>}

9．设集合A={1 , 2 , 3 , 4}上的二元关系

R = {?1 , 1?，?1 , 3?，?2 , 2?，?3 , 1?，?3 , 3?，?3 , 4?，

?4 , 3?，?4 , 4?}，

4

判断R具有哪几种性质？ 自反性、对称性、传递性。

10．设集合A={a , b , c , d }上的二元关系

R = {?a , a?，?a , b?，?b , b?，?c , d?}，

求r (R)，s (R)，t (R)．

r（R）= {〈a，a〉，〈a，b〉，〈b，b〉〈c，c〉，〈c，d〉，〈d，d〉}；

s（R）= {〈a，a〉，〈a，b〉，〈b，a〉〈b，b〉，〈c，d〉，〈d，c〉}； t（R）= {〈a，a〉，〈a，b〉，〈b，b〉〈c，d〉 }。

11．设集合A = {a, b, c, d}，R，S是A上的二元关系，且 R = { , , , , ,

d> , , }

S = { , , , , ,

b> , , , }

试画出R和S的关系图，并判断它们是否为等价关系，若是等价关系，则求出A中各元素的等价类及商集．

R是等价关系，A/R = {[a]，[c]}。S不是等价关系。 12．图1.1所示两个偏序集?A，R ?的哈斯图，试分别写出集合

A和偏序关系R的集合表达式．

d b a (1)

图1.1 题12哈斯图

e f c g

b c f d a (2)

e g 5

A = {a，b，c，d，e，f，g}。

R = {，，，，，，

，，，}∪IA。

S = {，，，，，，}∪IA。

13．画出各偏序集?A，?1?的哈斯图，并指出集合A的最大元、最小元、极大元和极小元．其中：A={a , b , c , d , e }，

?1 = {?a , b?，?a , c?，?a , d?，?a , e?，?b , e?,?c , e?，

?d , e?}?IA；

集合A的最大元e、最小元a、极大元e和极小元a。 14．下列函数中，哪些是满射的？那些是单射的？那些是双射的？

(1) f1 ：R ?R，f (a) = a3 + 1；

?0, (2) f4 ：N ?{0 , 1}，f (a) = ??1,a为奇数a为偶数 ．

（1）双射； （2）满射。

15．设集合A= {1, 2 }，B = {a, b, c}，则B ?A= {，，，

，，} ．

16．设集合A = {1，2，3，4}，A上的二元关系

6

R ={?1 , 2?，?1 , 4?，?2 , 4?，?3 , 3?}， S ={?1 , 4?，?2 , 3?，?2 , 4?，?3 , 2?}，

则关系（ B ）= {?1 , 4?，?2 , 4?}．

A．R?S B．R?S C．R - S D．S - R

17．设集合A={1 , 2 , 3 , 4}上的二元关系R = {?1 , 1?，?2 ,

a 3?，?2 , 4?，?3 , 4?}，则R具有（ ）． A．自反性 B．传递性 C．对称性 D．反自反性

b c e d 图1.2 题18哈斯图

18．设集合A={ a , b , c , d , e }上的偏序关系的哈斯 图如图1.2所示．则A的极大元为 a ，极小元为c、d．

19．设R为实数集，函数f：R?R，f (a) = -a2 +2a - 1，则f 是（ D ）．

A．单射而非满射 B．满射而非单射 C．双射 D．既不是单射也不是满射

作业2 三、四章无答案

第3章 图的基本概念与性质

{0 m2 w; R1 w

1．计算出下图2.1的结点数与边数，并说明其满足握手定理．5

7

H }5 X% J* b; t4 Z9 |; }

9 {- A: { Z5 V; J

图2.1 习题1的图

解：共有6个结点，6条边，图中从左上至右下的结点的度数分别为3、2、0、2、3、2，显然度数之和为12，即为边数的两倍，满足握

手定理．

7 m% y8 ?& _( m3 e' [5 e4 A# X

2．试分别画出下列图2.2(a)、(b)、(c)的补图．7 U: P8 w. C& R# c/ a: k( |7 [6 x / N( N- k9 @+ j7 u

图2.2

习题2的图0 C1 I) k\ 解： 2.2(a)、(b)、(c)的补图如下： 4 H5 `# C' E; @. D5 d% w; u! D, H 3．找出下图2.3中的路、通路与圈．

4 ]8 x5 E3 b1 q7 F

图2.3 习题3的图

解：对图2.3中的结点作标记如下：\

其中路有aca、acdc、bedc等，通路ac、acd、bedc等，圈有bedcb、

8

edcbe等．1 \ 4．有n个结点的无向完全图的边数为1 @3 |% a2 Q9 b0 r, n

．

5．图中度数为奇数的结点为 数个．

6．已知图G的邻接矩阵为, ? s; c* Z/ \

，

则G有（ ）． A．5点，8边

B．6点，7边) U8 T( _0 T2 o2 ]3 l

C．5点，7边3 m) i! Z [) @* n7 g8 D% i/ `7 N7 S

D．6点，8边 k: j: t8 J$ r! \

第4章 几种特殊图

1．如图2.8是否为欧拉图？试说明理由．

$ A( K$ e' l; L/ Y+ D4 I: J

图2.8

判断是否为欧拉图' P/ E! h2 a+ e! _3 L' K: m7 I 解：图[font=?&

5;]2.8不是欧拉图，因为结点[font=?&5;]2、v3、v4、v6的度数均不为偶数．9 ?4 p; ^7 m8 e* G

+ l/ u' m, S9 V v* Y5 P

9

5;]v[font=?&

2．如图2.9是否为汉密尔顿图？试说明理由．

& M- V, T7 I3 l- r4 l

图2.9

判断是否为汉密尔顿图. l5 k( \ 解：图2.9是汉密尔顿图，因为图中存在汉密尔顿回路

v1v3v5v6v8v4v7v2v1．$ k ~* s6 d0 \

3．试分别说明图4.3（a）、（b）与（c）是否为平面图．: y) ~: C\n3 T, U) |% K

图2.105 e9 }; I( \

判断是否为平面图 解：4.3（a）为平面图，可画为 # l5 ^1 n! ?) r. @/ h$ W, ]: o

（b）为平面图，可画为) g+ c' u9 v! y9 o- d# J( b( O

（c）为平面图，可画为5 ?9 r% o3 y. w7 r7 k- r+ r

4．若G是一个汉密尔顿图，则G一定是( c )．

A．欧拉图 B．平面图 C．连通图

10

5．设G是有n个结点m条边的连通平面图，且有k个面，则k等于( b )．; i6 @1 ]* w% [7 ^4 Y: s3 p; G6 A

A．m-n+2\

B．n-m-24 J: u% j/ h* Q4 }$ B C．n+m-2$ F6 g! @1 X! R, M1 u, e

D．m+n+2

: O7 r+ S. ~/ m1 j/ h, Z |) _

6．现有一个具有个奇数度结点的图，若要使图中有一条欧拉回路，

最少要向图中添加____ k/2___条边．

第5章树及其应用

1．试指出图2.13中那些是树，那些是森林，并说明理由．

* M% N\

图2.13

习题1的图\

解：图中（a）、（c）是树，因（a）与（c）均为无回路的连通图． （b）是森林，因其包含两棵子树． （c）不是树也不是森林，因其包含回路．

2．试画出图2.14中的一个生成树，并说明其中的树枝、弦，以及对

应生成树的补．1 R% i; U8 v L- f7 @ 6 a/ {) E e0 b; i& f9 W. T6 d

11

图2.14

习题2的图

解：图中的一个生成树如下：

其中的边为生成树的树枝． 对应生成树的补如下

其中的边为上生成树的弦．\

4 |, y4 q( B; a: H* n % ?* b% z( _: x2 p! p' w7 n: f4 g

3．给定一组权值为1，2，2，3，6，7，9，12，是求出相应的一个

最优树．

解：相应的一个最优树如下：

作业3

一、单项选择题

1．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}?A B．{ a }?A C．{2}?A D．??A 正确答案：B

2．若集合A={a，b，{ 1，2 }}，B={ 1，2}，则（ ）． A．B ? A，且B?A B．B? A，但B?A

12

C．B ? A，但B?A D．B? A，且B?A 正确答案：B

3．设集合A = {1, a }，则P(A) = ( )．

A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 正确答案：C

注意：若A是n元集，则幂集P(A )有2 n个元素．

4．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b??a ,

b?A , 且a +b = 8}，则R具有的性质为（ ）．

A．自反的 B．对称的

C．对称和传递的 D．反自反和传递的 正确答案：B

因为写出二元关系R的集合表达式为

R = {?2 , 6?，?6 , 2?，?3 , 5?，?5 , 3?，?4 , 4?}

显然，R是对称的，不是自反的、反自反的、传递的． 要求大家能熟练地写出二元关系R的集合表达式． 5．设集合A={1 , 2 , 3 , 4}上的二元关系

R = {?1 , 1?，?2 , 2?，?2 , 3?，?4 , 4?}，

S = {?1 , 1?，?2 , 2?，?2 , 3?，?3 , 2?，?4 , 4?}，

则S是R的（ ）闭包．

A．自反 B．传递 C．对称 D．以上都不对

13

正确答案：C

想一想：R的自反闭包是什么？

如果集合A={1, 2, 3}，A上的二元关系R={|x?A，y?A，

x+y=8}，那么R的自反闭包是什么？请写出．

1 6．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系的哈斯图如右图所示，若A的子集B = {3 , 4 , 5}， 4 2 3 5

则元素3为B的（ ）．

A．下界 B．最大下界 C．最小上界 D．以上答案都不对 正确答案：C ?

二、填空题

1．设集合A有n个元素，那么A的幂集合P(A)的元素个数为 ． 应该填写：2n

如果n=5, n=8，那么A的幂集合P(A)的元素个数分别是多少？

2．设集合A = {1，2，3，4，5 }，B = {1，2，3}，R从A到B的二元关系，

R ={?a , b??a?A，b?B且2?a + b?4}

则R的集合表示式为 ．

应该填写：R = {?1 , 1?，?1 , 2?，?1 , 3?，?2 , 1?，?2 , 2?，

?3 , 1?}

14

3．设集合A={0, 1, 2}，B={0, 2, 4},R是A到B的二元关系，

R?{?x,y?x?A且y?B且x,y?A?B}

则R的关系矩阵MR＝

．

?10应该填写：????11010??0?0??

因为R ={<0,0>, <0,2>, <2,0>, <2,2>}，由此可以写出R的关系矩阵．

4．设集合A={a,b,c}，A上的二元关系

R={,}，S={,,}

则(R?S)－1= ． 应该填写：{, }

因为 R?S={, }，所以(R?S)－1={, }．

5．设集合A=｛a,b,c,d｝，A上的二元关系R={, , , }，则二元关系R具有的性质是 ． 应该填写：反自反的

6．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是 ．

应该填写：{<1, a >, <2, b >}，{<1, b >, <2, a >}

想一想：集合A到B的不同函数的个数有几个？

三、判断说明题（判断下列各题，并说明理由．）

15

1．设A、B、C为任意的三个集合，如果A∪B=A∪C，判断结论

B=C 是否成立？并说明理由．

解：结论不成立．

设A={1, 2}，B={1}，C={2}，则A∪B=A∪C，但B?C．

2．如果R1和R2是A上的自反关系，判断结论：“R-11、R1∪R2、R1?R2是自反的” 是否成立？并说明理由． 解：结论成立．

因为R1和R2是A上的自反关系，即IA?R1，IA?R2． 由逆关系定义和IA?R1，得IA? R1-1； 由IA?R1，IA?R2，得IA? R1∪R2，IA? R1?R2．

所以，R1-1、R1∪R2、R1?R2是自反的．

3．判断“若偏序集??，R?的哈斯图如右图所示，则集合A的极大元为a，f；最大元不存在．”是否正确，并说明理由．

a

解：正确

按照极大元定义：“若对任意a?B，且b?a，都有

f b d c e a = b，则称b为B的极大元”，可知a，f是A的极大元，

且最大元不存在．

想一想：“若偏序集??，R?的哈斯图如右图所示，则集合

A的最大元为a；最小元不存在．” 是否正确？

再给出一个判断说明题，大家要重视的。

想一想：“设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，

16

则f是单射．”是否成立？并说明理由．

四、计算题

1．设集合A＝{a, b, c}，B={b, d, e}，求

（1）B?A； （2）A?B； （3）A－B； （4）B?A． 解：（1）B?A={a, b, c}?{b, d, e}={ b } （2）A?B={a, b, c}?{b, d, e}={a, b, c, d, e } （3）A－B={a, b, c}－{b, d, e}={a, c}

（4）B?A= A?B－B?A={a, b, c, d, e }－{ b }={a, c, d, e }

2．设集合A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是

A上的整除关系，B={2, 4, 6}．

（1）写出关系R的表示式； （2）画出关系R的哈斯图； （3）求出集合B的最大元、最小元．

解：（1）R=IA?{<1,2>, <1,3>, ?, <1,12>, <2,4>, <2,6>, <2,8>,

12 <2,10>, <2,12>, <3,6>, <3,9>, <3,12>, <4,8>, <4,12>, <5,10>, 8 <6,12>}

10 5 4 2 6 3 9 7 11

（2）

1 关系R的哈斯图

17

（3）集合B没有最大元，最小元是：2

3．设集合A＝{a, b, c, d}上的二元关系R的 a d 关系图如右图所示．

b c （1）写出R的表达式； （2）写出R的关系矩阵； （3）求出R2．

解：（1）R＝{, , , } ?1010??（2） M??0010?R??0000?

??0001??（3）R2 = {, , , }?{, , }

={, , }

五、证明题

1．试证明集合等式：A? (B?C)=(A?B) ? (A?C)．

证：若x∈A? (B?C)，则x∈A或x∈B?C， 即 x∈A或x∈B 且 x∈A或x∈C． 即x∈A?B 且 x∈A?C ， 即 x∈(A?B) ? (A?C)，

18

>, c所以A? (B?C)? (A?B) ? (A?C)．

反之，若x∈(A?B) ? (A?C)，则x∈A?B 且 x∈A?C， 即x∈A或x∈B 且 x∈A或x∈C，

即x∈A或x∈B?C， 即x∈A? (B?C)，

所以 (A?B) ? (A?C)? A? (B?C)． 因此 A? (B?C)=(A?B) ? (A?C)．

想一想：等式A? (B?C)=(A?B) ? (A?C)如何证明？

2．设R是集合A上的对称关系和传递关系，试证明：若对任意

a?A，存在b?A，使得?R，则R是等价关系．

证明：已知R是对称关系和传递关系，只需证明R是自反关系． 任意a?A，存在b?A，使得?R，因为R是对称的，故?R；

又R是传递的，即当?R，?R，可以得到?R；

由元素a的任意性，知R是自反的． 所以，R是等价关系．

3．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．

证明：① 任意x?A, ?R, ?S ? ?R?S ，所以R?S有自反性；

② 对任意x, y?A，因为R，S是反对称的，由

?R?S 且 ?R?S

? (?R且? S)且(?R且? S) ? (?R且?R)且(? S且? S)

19

? x= y且y= x，

即x= y．所以，R?S有反对称性．

③对任意x, y, z ?A，因为R，S是传递的，由 ?R?S 且 ?R?S ? ?R且? S且?R且? S

? ?R且?R且? S且? S ? ?R且? S ? ?R?S

所以，R?S有传递性．

总之，R?S是偏序关系. 4 5 6题无答案 作业4

第6章 命题逻辑

1．判断下列语句是否为命题，若是命题请指出是简单命题还是复

合命题． （1）8能被4整除．

（2）今天温度高吗？! O2 d8 r' @6 o4 E2 O( ]

（3）今天天气真好呀！

（4）6是整数当且仅当四边形有4条边．\ （5）小王是学生，但小李是工人．6 d/ {, U. Y$ J2 u1 O8 ~

（6）除非下雨，否则他不会去．

解：（1）是简单命题，（4）（5）（6）是复合命题．

2．翻译成命题公式

（1）他不会做此事．5 [( h0 C/ ]' e; F( _

（2）他去旅游，仅当他有时间．\ （3）小王或小李都会解这个题．! T e* b& B! j1 V0 H5 t

20

（4）如果你来，他就不回去． （5）没有人去看展览．/ I4 b0 C. T& [ （6）他没有去看电影，而是去观看了体育比赛．

解： （1）设P：他会做此事，公式为 P．- n6 M5 X. {/ ~3 Y9 g0 I( E

（2）设P：他去旅游，Q：他有时间，公式为P Q．6 k7 j1 x( C5 z8 e

（3）设P：小王会解这个题，Q：小李会解这个题，公式为P Q． （4）设P：你来，Q：他回去，公式为P Q．2 C5 P' e3 I6 P- B& K; S/ X

（5）设P：有人去看展览，公式为 P．

（6）设P：他去看电影Q：他去观看了体育比赛，公式为 P Q．1 L; f\ k- k' ], Z H9 p

3．设P，Q的真值为1；R，S的真值为0，求命题公式(P∨Q)∧R

∨S∧Q的真值．- T; D# p, n) \

解： (P∨Q)∧R∨S∧Q

(1∨1)∧0∨0∧1( p+ ], {3 ?& W, f9 a 1∧0∨0∧17 `. Y0 l v) R+ {

0∨0

0\ J/ T( N' c/ b 4．试证明如下逻辑公式

（1） ┐（A∧┐B）∧（┐B∨C）∧┐C ==> ┐（A∨C）

21

证明： A* P$ {0 b ^

1）┐（A∧┐B） P# ~9 y! u: u' S8 \E+ y9 P7 D

2）┐A∨B T 1）E$ i6 N. r k( k% ?1 `( m

3）┐B∨C P

4）┐C P\ 5）┐B T 3） 4）I* O5 R* a q( q# ?0 P

6）┐A T 2） 5）I 7）┐A∧┐C T 5） 6）I 8）┐（A∨C） T 7）E

（2） (P→Q)∧(Q→R)∧┐R ==> P( ?% p! _/ L' H P2 f: s( R\\

证明：/ a; |, v! Y# m/ z# P

1）P→Q P2 w9 s% \ 2）Q→R P) V J! Y) D# q4 S: ^ 3）┐R P9 |' t7 m/ F2 [( Z

4）┐Q T 2） 3）I 5）┐P T 1） 4）I 5．试求下列命题公式的主析取范式，主合取范式． （1） （P∨(Q∧R)）→(P∧Q)0 m z; _2 z) r, b- E& c) a

22

解： （P∨(Q∧R)）→(P∧Q)

┐（P∨(Q∧R)）∨(P∧Q)9 J+ `3 J' U. F3 D* C p* ~ （┐P∧（┐Q∨┐R））∨(P∧Q)6 \

（┐P∧┐Q）∨（┐P∧┐R）∨(P∧Q)+ b, D+ L\ （┐P∧┐Q）∧（R∨┐R）∨（┐P∧┐R）∧（Q∨┐Q）∨(P∧Q)

∧（R∨┐R）

（┐P∧┐Q∧R）∨（┐P∧┐Q∧┐R）∨（┐P∧┐R∧Q）∨（┐P∧┐R∧┐Q）∨(P∧Q∧R）∨(P∧Q∧┐R）. @! b7 u$ i0 k1 o) i （┐P∧┐Q∧┐R）∨（┐P∧┐Q∧R）∨（┐P∧Q∧┐R）∨(P∧Q

∧┐R）∨(P∧Q∧R）4 x7 s6 j, b K, _

0，1，2，6，7 3，4，5

（2） ┐(P→Q)∧Q6 }6 s2 P7 D4 z2 K* D; G; `

解： ┐(P→Q)∧Q ┐(┐P∨Q)∧Q P∧┐Q∧Q

F# l% h8 ~7 ?3 S8 Q+ ^) d3 | 0，1，2，3，4，5，6，7

6．利用求公式的范式的方法，判断下列公式是否永真或永假．7 n. L1 H6 |8 g3 S% [7 u

（2）（P∨Q）→R* \ 解：（P∨Q）→R. S1 R( ?) X1 S4 B8 r7 I

23

┐（P∨Q）∨R

（┐P∧┐Q）∨R6 v* u+ [) y* g1 r8 x

（┐P∧┐Q）∨R为析取范式，析取的两个合取式不会永真或永假，

所以此公式不是永真或永假式．

对其他一些公式也可以通过求主范式进行类似地判断．9 i( Q8 H% i. o8 ?) b

7．设P：昨天天晴，Q：前天下雨，则命题\昨天天晴，但前天下

雨\可符号化为（ A ）．

A．P∧Q B．P →

Q C．P∨Q D．Q → P

8．可以确定下述推理的步骤（ D ）是正确的． A．（1） ┐P∧Q P

（2） P T（1）I

B．（1） P →Q P

（2） Q T（1）I C．（1） P∨Q P( z\ X& T （2） P T（1）I H! p; ^+ o. M, q- a

D．（1） P∧Q P

（2） P T（1）I( S+ V7 e& C }8 I# X( ? 第7章谓词逻辑

24

１．将下列命题翻译成谓词公式

(1) 每个人都不会来。

(2) 没有人能做这件事。9 v; _5 P( v! d. D) [& e

(3) 有些人能去，但不是所有人都能去。

(4) 如果每人都这样做，那么就没有什么事做不了。\^$ `\A\f* B8 w+ t

(5) 不是每个人都愿意做这件事。3 C& o+ [; v5 T+ F4 H (6) 所有人都需要不断地努力学习，争取进步。+ v

解：(1) 设P（x）：x是人，Q（x）：x会来，2 M1 c7 X: Y) v) m% b8 y# x) W\

公式为（ x）（P（x）→┐Q（x））． (2) 设P（x）：x是人，Q（x）：x能做这件事，

公式为 ┐（ x）（P（x）∧Q（x））．+ t0 Z B5 S5 S m2 p, d

(3) 设P（x）：x是人，Q（x）：x能去，

公式为（ x）（P（x）∧Q（x））∧┐（ x）（P（x）→Q（x））． q; R+ l. A( ^. b

(4) 设P（x）：x是人，Q（x）：x这样做，R（x）：x是事，S（x,y）：x能做y事，# B. A+ z) z: x8 g- C1 d; s7 U 公式为（ x）（P（x）→Q（x））→ （ y）（ x）（R（y）→P（x）∧┐S（x,y））．4 d9 t, m) \(5) 设P（x）：x

是人，Q（x）：x愿意做这件事，

25

公式为┐（ x）（P（x）→Q（x））．

(6) 设P（x）：x是人，Q（x）：x需要不断地努力学习，争取进

步，* {! E2 P# ]2 u9 @' `

公式为（ x）（P（x）→Q（x））． B0 X- L4 P) i3 _/ |+ S2 \

2．设谓词A(x)：x是偶数，B(x)：x是奇数，x的取值为1至10

之间的正整数，试求出下列谓词公式的值． （1）（ #x）A（x）∧（ #x）B（x）．

解：（ x）A（x）∧（ x）B（x）$ E+ q% Q5 b2 w7 H, b7 u6 l （ A（1）∨A（2）∨A（3）∨A（4）∨A（5）∨A（6）∨A（7）∨A（8）∨A（9）∨A（10））∧（ B（1）∨B（2）∨B（3）∨B（4）∨B（5）∨B（6）∨B（7）∨B（8）∨B（9）∨B（10）） （0∨1∨0∨1∨0∨1∨0∨1∨0∨1）∧（1∨0∨1∨0∨1∨0∨1∨0

∨1∨0）

（1）∧（1）$ L3 E0 h5 a\

1．

（2） （ x）（A（x） B（x））．* ~' [8 I2 H) |) i) M! h1 z: s6 U 类似可求

3．试证明下列公式# P% n: W( J7 p3 [8 G% b* T1 `% P （2）（ x）（P（x）∧R（x））==> （ x）P（x）∧（ x）R（x）．

证明：; H7 \

26

1）（ x）（P（x）∧R（x）） P 2）P（a）∧R（a） T 1）ES 3）P（a） T 2）I 4）（ x）P（x） T 3）EG 5）R（a） T 2）I 6）（ x）R（x） T 5）EG

7）（ x）P（x）∧（ x）R（x） T 5） 6）I

（3） （ x）A（x）∨B==>（ x）（A（x）→B）．! e% b3 W* w5 r3 o 证明：

1）┐（ x）A（x）∨B P; E- y# Q$ y# ?$ w 2）（ x）┐A（x）∨B T 1）E0 k7 m$ T: W\[( ^8 m( O

3）（ x）(┐A（x）∨B) T 2）E8 V* |/ E8 P5 R( ~+ l\

4）（ x）（A（x） B） T 3）E5 ~& g7 }6 V; `5 A& G

4．试证明（ x）（ P（x）→R（x））,（ x） R（x）可逻辑推出

（ x）P（x）．; e# c3 ]! R& o\

证明：8 O/ v# [$ B; ?5 V7 s+ \ 1）（ x）（┐P（x） R（x）） P 2）（ x）┐R（x） P

27

3）┐R（a） T 2）US! D, R( d% t! N' z. s6 V

4）┐P（x） R（x） T 1）US 5）P（a） T 3） 4）I 6）（ x）P（x） T 5）EG* }% ]9 q4 u. c7 v5 @

5．设A（x）：x是人，B（x）：x犯错误，则命题\没有不犯错误

的人\可符号化为（ D ）．/ ^2 e0 ]' @: T$ p: h I A．( x)(A(x)∧B(x)) B．┐

( x)(A(x) → ┐B(x))( V4 u' s% K) \

C．┐( x)(A(x)∧B(x)) D．┐

( x)(A(x）∧┐B(x））

6．可以确定下述谓词推理的步骤（ A ）是正确的．( \M3 t; Z) n8 ~. `1 b2 d2 ?: g

A． （1） （ x）P（x） P

（2） P（a） US

（1）

（3） （ x）P（x） ES（2） B． （1） （ x）P（x） P

（2） P（a） ES（1）

（3） （ x）P（x） US（2） C． （1） P（a） P

28

（2） （ x）P（x） US（1） D． （1） P（a） P （2） （ a）P（a） US（1）

29