计算机本科离散数学形成性考核作业参考答案
作业一
一、 填空题
1、集合的
示
有两种: 列举 法和 描述 法。请把“大于3而小于或等于7的整 数集合”用任一种集合的表示方法表示出来A={ 4,5,6,7 }。 2、“不超过29的全体素数组成的集合”表示为 。
3、写出A={1,{1},2,{2}}的全部子集 。* E: ^- E& L0 |" D( B,
s ~4、集合运算的基本定律:A&639;A=A,满足 幂等 律;A&639;~A=&~B,满足 摩根 律。
?B)=~A?510;,满足 补余 律;~(A
(A)={{ 5},{ 2,5},{??(B)?
5、设A,B是两个集合,A={1,2,3,4},B={2,3,5},则B-A={ 5 } , (B)的元素 个数为 3 。?3,5},{ 2,3,5}} ,1 ~) @% d3 S: v" I( N- l) h- Y C= ??B)?
6、全集E={a,b,c,d,e},A={a,d},B={a,b,e},C={b,d}, 求(A ,{ a}} 。 ?(B)= { ??(A)? { a,c,e} ,) Q Z. J/ [$ |" J3 C 7、 A和B是任意两个集合,若序偶的第一个元素是A的一个元素,第二个元素是B
的一个元素,则所有这样的序偶集合称为集合A和B的 ,/ t7 \. ~) _8
u/ c8 s
B的子集R称为A,B上的 ?B= 。A?B,即A?
记作A 。
8、 ,则从A到B的所有映射是
。
9、 R是集合A上的二元关系,如果关系R同时具有 自反 性、 对称 性和 传 递 性,则称R是等价关系。, c, w- n( A0 N5 [
10、 设集合A={1,2,3},σ与τ都是A上的映射,σ={(1,2),(2,1), (3,3)},τ={(1,3),(2,2),(3,2)},
则 ,
。5 z0 p3 {8 F0 P/ _& Y' _8 J
11、 设R1,R2是集合A={a,b,c,d}上的二元关系,其中R1={(a,a),(a,b), (b,d)},R2={(a,d),(b,c),(b,d),(c,b)},则R1 R2 = , R12= 。?! l# w; U/ G7 g9 S* k 二、 单项选择题
1. 由集合运算定义,下列各式正确的有( A )。; Y4 K4 u. R& Z, V5 p% c6 I7 {! T+
f2 }
Y ?X?Y B.X?X?A( X Y?X?Y D.Y?X? C.X 2、 下列命题正确的是( )。0 g- } Y- R j, Y {a,b,c} ? C({a}?}=?{?? B(?}=?{??A( {a,b,c}?? D(- I( j7 ^% s& p6 V1
u, n* ~5 k
3、设集合 ,则 ( )。
y2 J$ c+ e/ V) M2 Q6 v1 h
4、 下列式子中正确的有( )。
5、 集合A={a,b,c},A上的关系R={(a,b),(a,c),(b,a),(b,c),
(c,a),(c,b),(c,c)},则R具有关系的( C )性质。' E$ B2 S2 I* R9 I7 y2 p9 R A(自反 B(对称 C(传递 D(反对称, U, g" W9 @: } t9 g 6、设集合 A={1,2,3},A上的关系R={(1,1), (1,2), (2,2), (3,3), (3,2)}, 则R不具备( A )。
A 自反性 B 传递性 C 对称性 D 反对称性* t. a0 Z7 |% @# `" B* d8 q; V" ^, U
7、设R1,R2是集合A={a,b,c,d}上的两个关系,其中R1={(a,a),(b,b),(b, c),(d,d)},R2={(a,a),(b,b),(b,c),(c,b),(d,d)},则R2是
R1的( B )闭包。
A(自反 B(对称 C(传递 D(以上都不是8 F+ d& y, l$ M' t" y
)是半序集,则A( )。?8、设(A," n% ~1 n- b1 l
A 必有最大元和极大元 B不一定有最大元,肯定有极大元
C不一定有极大元,肯定有最大元 D不一定有最大元,也不一定有极大元3 w6 {) U6 L/ a0 H# h, R
是( D )。?(x)= -x2+2x-1,则?R,?=R?9、设R为实数集,映射
A(单射而非满射 B(满射而非单射 C(双射 D(既不是单射,也不是满射) X& x4 `% B; i* ~5 [
10、集合 ,半序关系R的哈斯图如下图所示,若A的子集 ,则元素c为B的( C )。# Y4 h- Y+ ^1
[ p, u
A. 下界; B. 最大下界; C. 最小上界; D. 以上答案都不对。% V, j" R( D( T7 n
a) ^1 l1 Z9 {7 O1 Z9 m+ [: @+ e
b c [0 h" b* L& ]
d e5 d6 G: Z7 f/ J$ s: x! ^
三、 计算题# G& ~. i4 J+ \; V/ M! y
1. 化简下式:
C)?B?(A?C)?B?(A?C)?B)?((A?C)?B?(A& U: N7 X, A7 p. h0 Y C)?B?(A?C)?B?(A?C)?B)?((A?C)?B?解:(A
C)?B? A?~C) ?B?(A?C) ?~B?(A?~C) ?~B?=(A ((?C)) ?(~C?~B)?=(( A C))?(~C?B)?A
E) E为全集?B)?(( A?E) ?~B)?=(( A
B)?( A?~B) ?=( A
B)?(~B ?= A0 r$ B/ g9 H: @" ]. ^7 q- S E?= A5 m. q+ z0 d; h8 b3 f8 `
=A/ o. o" J$ e; l" X, H( ]
2. 一个年级170人中,120名学生学英语,80名学生学德语,60名学生学日语,
50名学生既学英语又学德语,25名学生既学英语又学日语,30名学生既学德语又学日语, 还有10名学生同时学习三种语言。试问:有多少名学生这三种语言都没有学习,(提示: 考虑试用文氏图来求出结果。) : w5 b( D, v3 Q( a% \# W6 V
解:设学习英语、德语、日语的学生集合分别为A,B,C。
C)。?B?那么“三种语言都没有学习的学生”的集合为~(A; h1 U9 g% o' j- p 根据题意画出文氏图如下:
利用定理1.2.2的推广结论,得:# {2 }2 s R1 w$ C& K4 S) f6 v C)|?B ?C)|=170-|(A ?B ? |~(A
C|)?B?C|+|A?C|-|B?B|-|A? =170-(|A|+|B|+|C|-|A
=170-(120+80+60-50-25-30+10)
=5
所以三种语言都没有学习的学生有5名。8 r* Z* @! x/ ? c! Y% Y% C 3、 设集合 ,A上的二元关系 ,求R的关系图与关系矩阵。,,' \1 w9 Q+ S6 T. S+ g
解:因为R=,(x,y)|x,y?A,且x?y,
=,(1,1),(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(3,3),(4,3),(4,4),. g; G" s2 e+ d! M$ f& M!
D
所以,R的关系图如下:
关系矩阵为MR=
7 L; t& z! o2 t5 a ~3 O ^; D/ }2 t
题3R的关系图 J( x: P5 r, H9 u
4、 A={a,b,c,d},R1,R2是A上的关系,其中R1={(a,a),(a,b),(b, a),(b,b),(c,c),(c,d),(d,c),(d,d)},R2={(a,b),(b,a),
(a,c),(c,a),(b,c),(c,b),(a,a),(b,b),(c,c)}。
(1) 画出R1和R2的关系图;
(2) 判断它们是否为等价关系,是等价关系的求A中各元素的等价类。 解: 关系图如右图所示(5 F+ C5 g. C# Q/ B% {
R1是等价关系(等价类有两个:) k! i# C! J3 }) Y% y [a] = ={a , b},[c] = [d] ={c , d}(+ F N) C# [8 E* v8 `2 ]3 u% [ 商集为 ={{a , b},{c , d}}(; Q- h. s% k+ `3 x/ M
R2 不是等价关系( C% J# j; H3 F' ^2 k3 X& {
5、 集合 ,R是集合A上的关系, ,求 ,并分别画出它们的关系图。,,,4 m) }& e( f" Z7 L+ x, {
6、 设集合 ,R为A上的整除关系,(1)画出半序集(A, R)的哈斯图;(2) 写出集合A中的最大元、最小元、极大元、极小元;(3)写出A的子集 的上界、下界、最 小上界、最大下界。5 ]2 ^) `# J! K4 b, _8 x, J 解:(1)因为R=
,(2,2),(2,4),(2,8,),(2,12),(2,24),(3,3),(3,4),(3,6),(3,12),(3,24),(4,4),(4,8),
(4,12),(4,24),, J. K+ L1 N K# G% v
(6,6),(6,12),(6,24),(8,8),(8,24),(12,12),(12,24),(24,24),
所以,序集(R,A)的哈斯图如下:
(2)由哈斯图可以看出,集合A中的最大 元是24,无最小元;极大元也是24, 极小元是2与3。
(3)由定义2.5.6知,集合B的上界是12与24,无下界,最小上界是12,无最小下界。
题6序集(R,A)的哈斯图
四、
题
C)。?(B?C)?C=(A?B)?1、 设A,B,C为三个任意集合,试证明:(A 2利用 与吸收律及其它运算律,证明 。 # c; r; f3 \9 R1 v# l4 G 证明:((A?B?C)?(A?B)),((,?(,,,))?,)0 M, H4 [8 h6 o! c
,(A?B),,2 K2 `& a1 n& Z4 t
,(A?B)?,,
,(,?,,)?(,?,,)4 ]/ \2 q; n7 {" `' \6 i
,,?(,,?,)
,,,?,
1。(定理,。,。,)? S?1 ?1 = R?S)?3、 设R和S是二元关系,证明:(R- N2 g m! h5 K* `4 W
4、设R是集合A上的二元关系,证明:R是传递的,当且仅当t(R)=R。 离散数学形成性考核作业(二)
图论部分
6 r& L* [. D( b2 x* q
本课程形成性考核作业共4次,内容由中央电大确定、统一布置。本次形考作业是第二次作 业,大家要认真及时地完成图论部分的形考作业,字迹工整,抄写题目,解答题有解答过程。
第3章 图的基本概念与性质
8 D/ s4 ]9 S4 n8 o2 t# z5 y
1(计算出下图2.1的结点数与边数,并
其满足握手定理( x2 @4 S0 t3 R) {' ?4 s
. T2 O1 y! I* F" u7 h* H, y, d
图2.1
习题1的图( S. l% X% Z4 H
解:共有6个结点,6条边,图中从左上至右下的结点的度数分别为3、2、0、2、 3、2,显然度数之和为12,即为边数的两倍,满足握手定理(
2(试分别画出下列图2.2(a)、(b)、(c)的补图(+ V2 B) B% h" w' a' ~. S8 J " @$ O( A8 o. D5 D/ A
图2.2, k2 l" A( h8 o
习题2的图
解: 2.2(a)、(b)、(c)的补图如下:, J, z: v4 K2 F& h, L" G + H) K) D+ U# z: F
3(找出下图2.3中的路、通路与圈(
图2.3$ Z7 c3 b- g4 ~8 C' W6 V
习题3的图4 m' z( @/ p4 K" o A8 T
解:对图2.3中的结点作标记如下:2 {* k6 F. x2 l
6 \- n# [! P; w; H. |
其中路有aca、acdc、bedc等,通路ac、acd、bedc等,圈有bedcb、edcbe等( 4(有n个结点的无向完全图的边数为
(# w- y: h |5 ?1 o. O# e
5(图中度数为奇数的结点为 数个(
6 ~) B& |: K: g! C' S; w; |9 } 6(已知图G的邻接矩阵为
,+ O+ s& m/ u2 ~5 H% u 则G有( )( . h" I z* h) S4 N( u: r% [ A(5点,8边
B(6点,7边 5 z- x$ W- v! Q _4 J C(5点,7边* }5 ?# q* t9 z5 B" B D(6点,8边# k, D" n$ y8 W( I& N 第4章 几种特殊图
1(如图2.8是否为欧拉图,试说明理由(
图2.8
判断是否为欧拉图) S2 ` `- R* F* u
解:图2.8不是欧拉图,因为结点2、v3、v4、v6的度数均不为偶数(
2(如图2.9是否为汉密尔顿图,试说明理由(
图2.9
判断是否为汉密尔顿图* h( Y. v3 C. r% z 解:图2.9是汉密尔顿图,因为图中存在汉密尔顿回路v1v3v5v6v8v4v7v2v1( 3(试分别说明图4.3(a)、(b)与(c)是否为平面图(
图2.10
判断是否为平面图" V/ ]& F& |4 i" l8 ?, Y 解:4.3(a)为平面图,可画为3 Y) R/ }# s& k0 G
(b)为平面图,可画为% F. Q/ z2 l2 ?2 V0 a' h/ ~
(c)为平面图,可画为
4(若G是一个汉密尔顿图,则G一定是( c )(
A(欧拉图6 s- Z- V8 Q3 T1 C* Y3 W B(平面图7 A A. [ m+ {1 J4 Q
C(连通图
5(设G是有n个结点m条边的连通平面图,且有k个面,则k等于( b )( A(m-n+2* ^& U' y7 N8 R3 j" X" W B(n-m-2% P" |0 h0 Z, O, C7 A C(n+m-2+ Q8 D2 x8 w" U1 H( I$ O D(m+n+2' M1 F0 B+ K( F' o# e) l0 ~. e% _+ \
6(现有一个具有 个奇数度结点的图,若要使图中有一条欧拉回路,最少要向图中添加____
k/2___条边(
第5章 树及其应用
r- e* Z. T7 W
1(试指出图2.13中那些是树,那些是森林,并说明理由(
图2.13
习题1的图
解:图中(a)、(c)是树,因(a)与(c)均为无回路的连通图(
(b)是森林,因其包含两棵子树(
(c)不是树也不是森林,因其包含回路(
2(试画出图2.14中的一个生成树,并说明其中的树枝、弦,以及对应生成树的补(3 O, v- m6
M& T# d- x/ D
图2.14, q9 V/ n z# K8 D; \9 d! |
习题2的图; c/ X$ n8 M' {* m/ @: P
解:图中的一个生成树如下:
其中的边为生成树的树枝(
对应生成树的补如下
其中的边为上生成树的弦(& Z. o& `, G' S+ N0 G( o+ s 0 ?" m; j N ` O
N* `$ |( a5 d h; a x6 J
3(给定一组权值为1,2,2,3,6,7,9,12,是求出相应的一个最优树(
解:相应的一个最优树如下:
离散数学形成性考核作业(三)
集合论与图论综合练习
本课程形成性考核作业共4次,内容由中央电大确定、统一布置。本次形考作业 是第三次作业,大家要认真及时地完成图论部分的形考作业,字迹工整,抄写题 目,解答题有解答过程。
一、单项选择题
1(若集合A,{2,a,{ a },4},则下列表述正确的是( , )(
A({a,{ a }}?A8 o4 p2 y! j' E1 } d$ k B({ a }?A
% I1 N- d5 V& _8 X( z
C({2}?A
3 h# q0 D2 U2 V1 Q. @
D( ?A
6 H& V$ A9 Q6 R4 K5 A) R5 \* P6 {5 Y
2(若集合A={a,b,{1,2 }},B={1,2},则( , )(
A(B; _5 e# C* R+ w7 m. I" P$ M ? A,且B?A- h( k# O' k9 i8 G; g B(B? A,但B?A
C(B ? A,但B?A! F7 x' H& h! C" t2 {6 _3 v1 W
D(B? A,且B?A
1 O$ b* q) l' j1 h% J: d# q0 B% Z& W
3(设集合A = {1,2,3,4,5 },B = {1,2,3},R从A到B的二元关系,
R ={ a , b ?a A,b B且 }
则R具有的性质为( , )(
* T* {( B4 K% }( M5 W3 d( ~ A(自反的
B(对称的
C(传递的
D(反自反的
& Q7 V* v" @7 a: ^8 e/ a1 S 4(设集合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(以上都不对
( G5 I' `9 B5 ^, ?6 h/ u 5(设图G的邻接矩阵为
则G的边数为(
)(
A(5
B(6 2 Y: r2 o {% Q3 _
C(3
D(4
6(给定无向图G如右图所示,下面给出的结点
集子集中,不是点割集的为( )
A({b, d}8 i' B' I5 W! x W: U6 L% e
B({d}
C({a, c}# ^$ f# P8 ]; h9 ?
D({g, e}
7(设G是有n个结点,m条边的连通图,必须删去G的( , )条边,才能确定 G的一棵生成树(
% T! {2 U, L% \7 r1 k6 U
A( " V0 I& }7 o, N5 |: j
B(
C( ! T$ R/ G% m0 O9 }- H0 j
D(
三、判断说明题 _4 o" o* n! A4 b% M# k 1(设A、B、C为任意的三个集合,如果A?B=A?C,判断结论B=C 是否成立, 并说明理由(
2(如果R1和R2是A上的自反关系,判断结论:“R-11、R1?R2、R1?R2是自 反的” 是否成立,并说明理由(
3(判断下图的树是否同构,说明理由(# E. O- c3 F" D, o) z
四、计算题
1(设 ,求:
(1)(A?B)?~C; (2)P(A),P(C); (3)A?B(
解:(1)因为A?B=,1,4,?,1,2,5,=,1,,
~C=,1,2,3,4,5,-,2,4,=,1,3,5,
所以 (A?B )1 J: v4 W$ [; Z' |
?~C=,1,?,1,3,5,=,1,3,5,
; t H) B _* ]/ Y; R( Y' ~
(2)因为P(A)=,?,,1,, ,4,, ,1,4,,
P(C)=,?,,2,,,4,,,2,4,,
所以 P(A)-P(C)={
?,{ 1},{ 4},{ 1,4}}-{?,{ 2},{ 4},{2,4 }}
(3) 因为 A?B={ 1,2,4,5},. a! `* M6 [5 X A?B={ 1}
所以 A?B=A?B-A?B={1,2,4,5}-{1}={2,4,5} 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的最大元、最小元(
7 _# A) @, t$ T. N- C0 I
3(设集合A,{a, b, c, d}上的二元关系R的
关系图如右图所示(
(1)写出R的表达式;
(2)写出R的关系矩阵;/ ]& w3 {$ w# H. f7 I/ N (3)求出R2(
4(设图G=
,V={ v1,v2,v3,v4,v5},E={ (v1,v2),(v1,v3),(v2,v3), (v2,v4),(v3,v4),(v3,v5),(v4,v5) }(
(1)试给出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数
(4)画出图G的补图的图形(
解: (1)图中G有5个结点,分别用结点画出,根据边集E
连接相关结点,则G图的图形表示如图4.1:
(2)图G有5个结点,则G的邻接矩阵为5X5矩阵,
按结点序号排序,根据结点间的邻接关系确定邻
接矩阵中的对应值,则G图的邻接矩阵为:
' o e1 M1 W! i1 l
(3)根据每个结点所关联的边数计算出结点的度数分别为:
deg(V1)=2
l) b9 A# c. b
deg(V2)=3
8 p; c: ?7 `. L% O" g7 j9 l% H deg(V3)=4
4 _6 A3 b: T% t. a; S
deg(V4)=3
deg(V5)=2
(4)补图的结点集与原图相等,补图的边集是那些由结点集确定的完全图中去掉 原图中的边所留下的边组成的,图G的补图如图4.4:
图4.1
图4.4
5(图G=,其中V={a, b, c, d, e, f },E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c,
e), (d, e), (d, f), (e, f) },对应边的权值依次为5,2,1,2,6,1,9,3及8( (1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值(. R7 } l( N/ U- U, @ 解:图G的图形与邻接矩阵如下图:) u8 p- ^9 t( G3 P! F6 w& t: Y
邻接矩阵# I4 b7 }+ ~$ s1 H" C
* s2 Z0 m' a7 a# u5 b7 k" r
G的图形上
G权最小的生成树+ R$ o9 ] d) \0 r5 a3 l
最小生成树如右上图,权为15。
五、证明题
1(试证明集合等式:A? (B?C)=(A?B) ? (A?C)(, v# @) z# y* V% O, W! X0 }2 _% f
2(设连通图G有k个奇数度的结点,证明在图G中至少要添加 条边才能使其 成为欧拉图(
离散数学形成性考核作业(四)$ n" B- w+ w+ x9 a5 k" R$ h' Q; q 数理逻辑部分
本课程形成性考核作业共4次,内容由中央电大确定、统一布置。本次形考作业是第四次作 业,大家要认真及时地完成数理逻辑部分的形考作业,字迹工整,抄写题目,解答题有解答 过程。& R$ P8 P8 B$ w" J6 w/ y8 m1 t; F 第6章 命题逻辑
1(判断下列语句是否为命题,若是命题请指出是简单命题还是复合命题( (1)8能被4整除(
(2)今天温度高吗,5 G* a# Y$ u; r* g$ H' {; b3 t/ p; F (3)今天天气真好呀~
(4)6是整数当且仅当四边形有4条边(# z( ?0 n" T" O$ X, s6 @ (5)地球是行星(- T( t, p! n6 v8 v+ w
(6)小王是学生,但小李是工人(# h! T+ ^7 l8 i* @" z+ C9 t (7)除非下雨,否则他不会去(
(8)如果他不来,那么会议就不能准时开始(
解:(1)(5)是简单命题,(4)(6)(7)(8)是复合命题(
2(成命题公式( E$ k3 v x! ?; y* N' W (1)他不会做此事(# e5 p8 r% _ m1 ]; T2 X2 o (2)他去旅游,仅当他有时间(
(3)小王或小李都会解这个题(
(4)如果你来,他就不回去(* D3 ~) G9 C' F! m7 i (5)没有人去看展览(* H) \9 x+ o( C1 v+ w. p9 ~ (6)他们都是学生(5 s1 V) Z1 L: r/ L6 u: c (7)他没有去看电影,而是去观看了体育比赛(
(8)如果下雨,那么他就会带伞() T8 m& O* z% O' [ Y 解: (1)设P:他会做此事,公式为 P(, [ _: j6 }1 s$ \ (2)设P:他去旅游,Q:他有时间,公式为P Q(- H1 f$ P' D8 u6 r9 w* G: S
(3)设P:小王会解这个题,Q:小李会解这个题,公式为P Q(
(4)设P:你来,Q:他回去,公式为P Q(
(5)设P:有人去看展览,公式为 P(
(6)设P:他们都是学生,公式为P(
(7)设P:他去看电影Q:他去观看了体育比赛,公式为 P Q(
(8)设P:下雨,Q:他就会带伞,公式为P Q(
3(设P,Q的真值为1;R,S的真值为0,求命题公式(P?Q)?R?S?Q的真值( 解: (P?Q)?R?S?Q+ R' p! X0 N1 G: C i (1?1)?0?0?13 @! |/ K9 H# R* Z3 z' B 1?0?0?1
0?0& U) G% I7 v' h x7 w5 J
0
4(试证明如下逻辑公式4 q. Q* o' s* P
(1) ?(A??B)?(?B?C)??C ==> ?(A?C)
证明:
1)?(A??B) P
2)?A?B T 1)E
3)?B?C P
4)?C P
5)?B T 3) 4)I
6)?A T 2) 5)I6 G# \2 s; @: h7 _ 7)?A??C T 5) 6)I& `1 w: i/ d) t c* N. G) f. D
8)?(A?C) T 7)E
(2) (P?Q)?(Q?R)??R ==> P
证明:
1)P?Q P
2)Q?R P
3)?R P
4)?Q T 2) 3)I8 h+ {) U- V" j, Y- s 5)?P T 1) 4)I9 d& m/ R- y- d2 V8 p 5(试求下列命题公式的主析取范式,主合取范式(7 M; T& M# b. z (1) (P?(Q?R))?(P?Q)
解: (P?(Q?R))?(P?Q)
?(P?(Q?R))?(P?Q)
(?P?(?Q??R))?(P?Q)
(?P??Q)?(?P??R)?(P?Q)
(?P??Q)?(R??R)?(?P??R)?(Q??Q)?(P?Q) ?(R??R)) D2 Q# i0 U7
A1 r4 e' v& W
(?P??Q?R)?(?P??Q??R)?(?P??R?Q)?(?P??R??Q)?(P?Q?R) ?(P?Q??R)* }! Q! {5 _& A& O* a) H" b2 x B (?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(P?Q??R)?(P?Q?R) 0,1,2,6,7
3,4,5
(2) ?(P?Q)?Q+ K3 _ p; s1 ~
解: ?(P?Q)?Q$ L# r" Z" {7 e; @
?(?P?Q)?Q
P??Q?Q
F+ D& k0 l* O3 s7 {, {1 R4 U- w& b 0,1,2,3,4,5,6,7 X% k0 x2 o, h& C! N; }+ { 6(利用求公式的范式的方法,判断下列公式是否永真或永假(
(2)(P?Q)?R t) I4 \* x! d
解:(P?Q)?R
?(P?Q)?R2 F! H A3 t, x F3 W
(?P??Q)?R5 e Q8 L' n: g; }9 _
(?P??Q)?R为析取范式,析取的两个合取式不会永真或永假,所以此公式不是永真或 永假式(
对其他一些公式也可以通过求主范式进行类似地判断(
7(试证明C?D,( C?D)??H,?H?(A??B),(A??B)?(R?S)}蕴含R?S(! t' r' \3 y0
v9 C5 a7 j) c' b
证明:' q8 U1 u a8 _1 E3 V
1)C?D P
2)( C?D)??H P# m& O* _- J4 X: R; p 3)?H T 1) 2)I! A- A4 l/ f3 @9 @1 h% B7 | 4)?H?(A??B) P% V7 o+ A9 B$ l% q' k$ N8 |. g& Q6 e
5)A??B T 3) 4)I
6)(A??B)?(R?S) P
7)R?S T 5) 6)I
8(设P:昨天天晴,Q:前天下雨,则命题"昨天天晴,但前天下雨"可符号化为( A )(6 D9 u5
c8 L( e0 [5 R
A(P?Q B(P ?Q C(P?Q D(Q ? P 9(可以确定下述推理的步骤( 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
(2) P T(1)I: ~! q( A- H( _9 t0 G( D D((1) P?Q P) V. `. ]' g# [8 H* Y
(2) P T(1)I
第7章谓词逻辑$ e/ G, U# I& h# T
,(将下列命题翻译成谓词公式9 l6 e6 G; w2 d2 d: h, Q (1) 有人能做这件事,但不是所有人都能做。
(2) 每个人都不会来。
(3) 没有人能做这件事。 j* L! C/ ^! F+ c+ i
(4) 所有的整数都是实数。. X3 K' H6 x6 O8 v
(5) 有些人能去,但不是所有人都能去。4 T% ~! j/ X) Q) F; u (6) 如果每人都这样做,那么就没有什么事做不了。! I5 p& i$ h4 l- E" Z$ ]( R
(7) 没有什么非做不可的事。" G- p1 L' V h& X
(8) 不是每个人都愿意做这件事。
(9) 所有人都需要不断地努力学习,争取进步。" a3 q* j: d" I4 G
(10) 如果x大于y,那么x+4大于y+1。
解:(1)设P(x):x是人,Q(x):x能做这件事,
公式为( x)(P(x)?Q(x))??( x)(P(x)?Q(x))(# c F. D2 S+ D# P+ I' I+ P, Y3
|
(2) 设P(x):x是人,Q(x):x会来,
公式为( x)(P(x)??Q(x))(
(3) 设P(x):x是人,Q(x):x能做这件事,% i. k# G: C- V+ ~& v7 o. J$ ? 公式为 ?( x)(P(x)?Q(x))(
(4) 设P(x):x是整数,Q(x):x是实数,
公式为( x)(P(x)?Q(x))(/ m7 `9 i z1 k
(5) 设P(x):x是人,Q(x):x能去,
公式为( x)(P(x)?Q(x))??( x)(P(x)?Q(x))(" @+ c, q! m: s8 D% P9 A3 _!
|$ ?. F
(6) 设P(x):x是人,Q(x):x这样做,R(x):x是事,S(x,y):x能做y事, 公式为( x)(P(x)?Q(x))? ( y)( x)(R(y)?P(x)??S(x,y))( (7) 设P(x):x是事,Q(x):x被做,
公式为( x)(P(x)??Q(x))(, r7 g7 E6 l5 `- d7 o2 w) ~ (8) 设P(x):x是人,Q(x):x愿意做这件事,9 D. F, ^- ~" p" \$ N 公式为?( x)(P(x)?Q(x))(
(9) 设P(x):x是人,Q(x):x需要不断地努力学习,争取进步,9 L* f1 R/ S1 V7 P. f; G( V
公式为( x)(P(x)?Q(x))(" x. V/ Z+ T# w. S1 t6 g; T (10) 设P(x,y):x大于y,Q((x,y):x+4大于y+1,: A( v2 H' C' e* K' U6 T9 c 公式为( x)(P(x)?Q(x))(
2(设谓词A(x):x是偶数,B(x):x是奇数,x的取值为1至10之间的正整数,试求出下 列谓词公式的值(8 \+ }. Y$ g1 a! H. H4 l
(1)( x)A(x)?( x)B(x)(
解:( x)A(x)?( x)B(x)% [4 A3 K+ r/ ]/ c3 q% ^" J ( 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))$ q8 [) s8 g- i( }5 R2 U
(0?1?0?1?0?1?0?1?0?1)?(1?0?1?0?1?0?1?0?1?0)
(1)?(1)
1(3 a; T1 {/ L- E M) `
(2) ( x)(A(x) B(x))(+ I T+ U* f/ N- e x0 ` 类似可求
3(试证明下列公式
(1)( x) A(x)==>( x)A(x)(( t7 ]: c; q1 ?/ e 证明:* S0 l" Q5 s3 G1 s$ L
1)( x) A(x) P& W: F. S+ U1 C# {8 O7 q* J 2)A(a) T 1)US
3)( x)A(x) T 2)EG9 g4 G* z6 k4 u$ Z (2)( x)(P(x)?R(x))==> ( x)P(x)?( x)R(x)(
证明:
1)( x)(P(x)?R(x)) P
2)P(a)?R(a) T 1)ES6 \- ~1 R" p% \4 r' l4 l! e: Y 3)P(a) T 2)I. @8 u6 Q( u" ^+ S
4)( x)P(x) T 3)EG/ k/ i' C0 a5 V0 U0 n6 G& {3 T 5)R(a) T 2)I. B$ q w& H6 z6 ?
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)(/ ]4 F- Z4 c! @4 C! J 证明:
1)?( x)A(x)?B P
2)( x)?A(x)?B T 1)E
3)( x)(?A(x)?B) T 2)E
4)( x)(A(x) B) T 3)E
4(试证明( x)( P(x)?R(x)),( x) R(x)可逻辑推出( x)P(x)(9 R3 P7 Q- X6 k8 j+ ]5 g9 p
证明:
1)( x)(?P(x) R(x)) P
2)( x)?R(x) P
3)?R(a) T 2)US/ ^- l1 P% K/ {- L6 Y0 w# {- O 4)?P(x) R(x) T 1)US( |" k* V7 c$ h1 p, W 5)P(a) T 3) 4)I. u2 ~# M- T/ S& f 6)( x)P(x) T 5)EG
5(设A(x):x是人,B(x):x犯错误,则命题"没有不犯错误的人"可符号化为( D )(
A(( x)(A(x)?B(x)) B(?( x)(A(x) ? ?B(x))
C(?( x)(A(x)?B(x)) D(?( x)(A(x)??B(x))
6(可以确定下述谓词推理的步骤( A )是正确的(4 J( A7 C, Q4 Y A( (1) ( x)P(x) P
(2) P(a) US(1)9 ~ C4 @3 `4 `, H+ I$ N/ T% k
(3) ( x)P(x) ES(2)) Q# B& ? O$ Z4 A% T" j: ^ B( (1) ( x)P(x) P) p1 \( F" O3 Y2 W2 [( x
(2) P(a) ES(1)4 o4 E: g/ T {; g" C/ {" T: e
(3) ( x)P(x) US(2)
C( (1) P(a) P3 ]5 {; \/ ^5 M
(2) ( x)P(x) US(1)& ]3 @! I! y3 j2 H3 b& X4 j9 M" d D( (1) P(a) P
(2) ( a)P(a) US(1)