离散数学课后习题答案左孝凌版) 下载本文

⑤┐B(u) →┐A(u) T②E ⑥C(u)→┐A(u) T④⑤I ⑦(?x)(C(x)→┐A(x)) UG⑥

d) (?x)(A(x)∨B(x)),( ?x)(B(x)→┐C(x)),( ?x)C(x)? (?x)A(x) ①( ?x)(B(x)→┐C(x)) P

②B(u)→┐C(u) US① ③( ?x)C(x) P

④C(u) US③ ⑤┐B(u) T②④I ⑥ (?x)(A(x)∨B(x)) P ⑦A(u)∨B(u) US

⑧A(u) T⑤⑦I ⑨(?x)A(x) UG⑧ (2) 证明:

a)①( ?x)P(x) P(附加前提) ②P(u) US① ③(?x)(P(x)→Q(x)) P ④P(u)→Q(u) US③ ⑤Q(u) T②④I ⑥(?x)Q(x) UG⑤ ⑦( ?x)P(x)→(?x)Q(x) CP b)因为(?x)P(x)∨(?x)Q(x)?┐(?x)P(x) →(?x)Q(x)

故本题就是推证(?x)(P(x)∨Q(x))?? ┐(?x)P(x) →(?x)Q(x) ①┐(?x)P(x) P(附加前提) ②( ?x)┐P(x) T①E ③┐P(c) ES② ④(?x)(P(x)∨Q(x)) P ⑤P(c)∨Q(c) ES④ ⑥Q(c) T③⑤I ⑦( ?x) Q(x) EG⑥ ⑧┐(?x)P(x) →(?x)Q(x) CP (3)

解:a)设R(x):x是实数。Q(x):x是有理数。I(x):x是整数。 本题符号化为:

(?x)(Q(x) →R(x)) ∧(?x)(Q(x) ∧I(x))?? (?x)(R(x) ∧I(x)) ①(?x)(Q(x) ∧I(x)) P ②Q(c) ∧I(c) ES① ③(?x)(Q(x) →R(x)) P

④Q(c) →R(c) US③ ⑤Q(c) T②I ⑥ R(c) T④⑤I ⑦I(c) T②I ⑧R(c)∧I(c) T⑥⑦I ⑨(?x)(R(x) ∧I(x)) EG⑧ b)设P(x):x喜欢步行。Q(x):x喜欢乘汽车。R(x):x喜欢骑自行车本题符号化为:

dintin@gmail.com

26

(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x)?? (?x) ┐P(x) ①(?x) ┐R(x) P ②┐R (c) ES① ③(?x)(Q(x) ∨R(x)) P ④Q(c) ∨R(c) US③ ⑤Q(c) T②④I ⑥ (?x)(P(x) →┐Q(x)) P ⑦P(c) →┐Q(c) US⑥ ⑧┐P (c) T⑤⑦I ⑨(?x) ┐P(x) EG⑧

c) 每个大学生不是文科学生就是理工科学生,有的大学生是优等生,小张不是理工科学生,但他是优等生,因而如果小张是大学生,他就是文科学生。 设G(x):x是大学生。L(x):x是文科学生。P(x):x是理工科学生。 S(x):x是优秀生。c:小张。 本题符号化为:

(?x)(G(x) →L(x)∨P(x)), (?x)(G(x) ∧ S(x)), ┐P (c) , S(c) ? G(c) →L(c) ①G(c) P(附加前提) ②(?x)(G(x) →L(x)∨P(x)) P ③G(c) →L(c)∨P(c) US② ④L(c)∨P(c) T①③I ⑤┐P (c) P

⑥ L(c) T④⑤I ⑦G(c) →L(c) CP

注意:本题推证过程中未用到前提(?x)(G(x) ∧ S(x))以及S(c)。主要是S(x):x是优秀生,这个条件与其他前提的联系对证明结论没有影响,因S(x)与其他前提不矛盾,故本题的推证仍是有效的。

dintin@gmail.com 27

3-5.1 列出所有从X={a,b,c}到Y={s}的关系。 解:Z1={} Z2={} Z3={} Z4={,} Z5={,} Z6={,} Z7={,,} 3-5.2 在一个有n个元素的集合上,可以有多少种不同的关系。 解 因为在X中的任何二元关系都是X×X的子集,而X×X=X2中共有n2个元素,取0个到n2个元素,共可组成2n2个子集,即|?(X?X)|?2n2。 3-5.3 设A={6:00,6:30,7:30,…, 9:30,10:30}表示在晚上每隔半小时的九个时刻的集合,设B={3,12,15,17}表示本地四个电视频道的集合,设R1和R2是从A到B的两个二元关系,对于二无关系R1,R2,R1∪R2,R1∩R2,R1?R2和R1-R2可分别得出怎样的解释。 解:A×B表示在晚上九个时刻和四个电视频道所组成的电视节目表。 R1和R2分别是A×B的两个子集,例如R1表示音乐节目播出的时间表,R2是戏曲节日的播出时间表,则R1∪R2表示音乐或戏曲节目的播出时间表,R1∩R2表示音乐和戏曲一起播出的时间表,R1?R2表示音乐节目表以及戏曲节目表,但不是音乐和戏曲一起的节日表,R1-R2表示不是戏曲时间的音乐节目时间麦。 3-5.4 设L表示关系“小于或等于”,D表示‘整除”关系,L和D刀均定义于{1,2,3,6},分别写出L和D的所有元素并求出L∩D. dintin@gmail.com

解:L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>, <3,6>,<1,1>,<2,2>,<3,3>,<6,6>} D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} L∩D= {<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} 3-5.5对下列每一式,给出A上的二元关系,试给出关系图: a){|0≤x∧y≤3},这里A={1,2,3,4}; b){|2≤x,y≤7且x除尽y,这里A={n|n∈N∧n≤10} c) {|0≤x-y<3},这里A={0,1,2,3,4}; d){|x,y是互质的},这里A={2,3,4,5,6} 解: a) R={<0,0>,<0,1>,<0,2>,<0,3>, <1,0>,<1,1>,<1,2>,<1,3>, <2,0>,<2,1>,<2,2>,<2,3>, <3,0>,<3,1>,<3,2>,<3,3>,} 其关系图 b) R={<2,0>,<2,2>,<2,4>,<2,6>, <3,0>,<3,3>,<3,6>, <4,0>,<4,4>, <5,0>,<5,5>, <6,0>,<6,6>, <7,0>,<7,7>} 28

3-6.1 分析集合A={1,2,3}上的下述五个关系: (1)R={<1,1>,<1,2>,<1,3>,<3,3>}; (2)S={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}; (3)T={<1,1>,<1,2>,<2,2>,<2,3>}; (4)?=空关系; (5)A×A=全域关系。 判断A中的上述关系是否为a)自反的,b)对称的,c)可传递的,d)反对称的。 解(1)R是可传递和反对称的。 (2)S是自反,对称和可传递的。 (3)T是反对称的。 (4)空关系是对称,可传递和反对称的。 (5)全域关系是自反,对称和可传递的。 3-6.2给定A={1,2,3,4},考虑a上的关系R,若R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} a) 在A?A的坐标图上标出R,并绘出它的关系图; b) R是ⅰ)自反的ⅱ)对称的ⅲ)可传递的,iv) 反对称的吗? 解 a) 1 2 4 3 dintin@gmail.com

R是可传递的的和反对称的;但不是自反的和对称的。 3-6.3 举出A={1,2,3}上关系R的例子,使其具有下述性质: a)既是对称的,又是反对称的; b)R既不是对称的,又不是反对称的; c)R是可传递的。 解 a)R={<1,1>,<2,2>,<3,3>} b)R={<1,2>,<2,1>,<2,3>} c) R={<1,2>,<2,1>,<1,1>,<2,2>,<3,3>} 3-6.4 如果关系R和S是自反的,对称的和可传递的,证明R∩S也是自反,对称和可传递的。 证明 设R和S是X上的自反的,对称的和可传递的关系。 1)对任意x∈X,有<x,x>∈R和<x,x>∈S,所以<x,x>∈R∩S,即R∩S在X上是自反的。 2)对任意的<x,y>∈R∩S,有<x,y>∈R∧<x,y>∈S,因为R和S是对称的,故必有<y,x>∈R∧<y,x>∈S。即<y,x>∈R∩S,所以R∩S在X上是对称的。 3)对任意的<x,y>∈R∩S∧<y,z>∈R∩S,则有 <x,y>∈R∧<x,y>∈S∧<y,z>∈R∧<y,z>∈S 因为R和S是传递的,故得<x,z>∈R∧<x,z>∈S,即<x,z>∈R∩S,所以R∩S在X上是传递的。 3-6.5给定S={1,2,3,4}和S上关系:R={<1,2>,<4,3>,<2,2>,<2,1>,<3,1>} 说明R是不可传递的,找出关系R1?R,使得R1是可传递的,还能找出另一个29

3-7.1设R1和R2是A上的任意关系,说明以下命题的真假并予以证明。 a)若R1和R2是自反的,则R1○R2也是自反的; b)若R1和R2是反自反的,则R1○R2也是反自反的; c)若R1和R2是对称的,则R1○R2也是对称的; d)若R1和R2是传递的,则R1○R2也是传递的。 证明 a)对任意a∈A,设R1和R2是自反的,则<a,a>∈R1,<a,a>∈R2 所以,<a,a>∈R1○R2,即R1○R2也是自反的。 b)假。例如:设A={a,b},有R1={<a,b>}与R2={<b,a>} R1和R2是反自反的。但R1○R2={<a,a>},所以R1○R2在A上不是反自反的。 c)假。例如:设A={a,b,c},有 R1={<a,b>,<b,a>,<c,c>},R2={<b,c>,<c,b>} R1和R2是对称的,但R 1○R2={<a,c>,<c,b>} 所以,R1○R2不是对称的。 d)假。例如:设A={a,b,c},有 R1={<a,b>,<b,c>,<a,c>},R2={<b,c>,<c,a>,<b,a>} 则R1,R2都是传递的。但R 1○R2={<a,c>,<a,a>,<b,a>} 所以,R1○R2不是传递的。 3-7.2 证明 若S为集合X上的二元关系: a)S是传递的,当且仅当(S○S)?S; b)S是自反的,当且仅当IX?S; c)证明定理3-7.3(b)(即S是反对称的,当且仅当S∩Sc?IX)。 证明 a)设S为传递的,若<x,z>∈S○S,则存在某个y∈X,使得<x,ydintin@gmail.com

>∈S,且<y,z>∈S。 若S是传递的,<x,z>∈S,所以(S○S)?S。 反之,设(S○S)?S ,假定<x,y>∈S且<y,z>∈S,则<x,z>∈S○S。因为(S○S)?S,故<x,z>∈S,得到S是传递的。 b)设S是自反的,令<x,y>∈IX,则x=y。但<x,x>∈S,因此<x,y>=<x,x>∈S,得IX?S。 反之,令IX?S,设任意x∈X,<x,x>∈IX,故<x,x>∈S,因此S是自反的。 c)设S是反对称的。假定<x,y>∈S∩Sc,则 <x,y>∈S∧<x,y>∈Sc?<x,y>∈S∧<y,x>∈S 因为S是反对称的,故x=y, 所以<x,y>=<x,x>∈IX,即S∩Sc?IX。 反之,若S∩Sc?IX,设<x,y>∈S且<y,x>∈S,则 <x,y>∈S∧<x,y>∈Sc ?<x,y>∈S∩Sc ?<x,y>∈IX 故x=y,即S是反对称的。 3-7.3 设S为X上的关系,证明若S是自反和传递的,则S○S=S,其逆为真吗 ? 证明 若S是X上传递关系,由习题3-7.2a)可知(S○S)?S, 令<x,y>∈S,根据自反性,必有<x,x>∈S,因此有<x,y>∈S○S,即S?S○S。得到 S=S○S. 这个定理的逆不真。例如X={1,2,3},S={<1,2>,<2,2>,<1,1>},30