离散数学习题答案_2015

1、.离散数学习题答案习题一1、利用逻辑联结词把以下命题翻译成符号逻辑形式（1） 他既是本片的编剧，又是导演 - P Q（2） 银行利率一降低，股价随之上扬- P Q（3） 尽管银行利率降低，股价却没有上扬- P Q（4） 占据空间的、有质量而且不断变化的对象称为物质 - M ßà(SPT)（5） 他今天不是乘火车去，就是随旅行团去了九寨沟- P Q（6） 小X身体薄弱，但是极少生病，并且头脑好使- P Q R（7） 不识庐山真面目，只缘身在此山中- P Q解释：因为身在此山中，所以不识庐山真面目（8） 两个三角形相似，当且仅当他们的对应角相等或者对应边成比例- S ß

2、;à(ET)（9） 如果一个整数能被6整除，那么它就能被2和3整除。如果一个整数能被3整除，那么它的各位数字之和也能被3整除解：设 P 一个整数能被6整除Q 一个整数能被2整除R 一个整数能被3整除S 一个整数各位数字之和能被3整除翻译为：P Q R R S2、判别下面各语句是否命题，如果是命题，说出它的真值1BASIC语言是最完美的程序设计语言- Y，T/F2这件事大概是小王干的- N3x2 = 64- N4可导的实函数都是连续函数- Y，T/F5我们要发扬连续作战的作风，再接再厉，争取更大的胜利- N6客观规律是不以人们意志为转移的- Y，T7到2021年，中国的国民生产总值将赶

3、上和超过美国- Y，N/A8凡事都有例外- Y，F3、构造以下公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式1P P Q Q解：PQP QP P QP P Q Q可满足式0000101111100101101124表略：2可满足式、3永真式 、4可满足式4、利用真值表方法验证以下各式为永真式18略5、证明以下各等价式3PQ Ró P QP R证明：左式óPQ Ró PQP Ró PQP Ró P QP Ró 右式4P QR QR Pó P QR QR P证明：左式ó(PR QR Pó (PRR

4、) ) (PRP) ) QRQPó P QR QR Pó 右式6、如果P Q ó QR,能否断定 P ó R . 如果P Q ó QR，能否断定 P ó R.如果P ó R，能否断定 P ó R.解：1如果P Q ó QR，不能判断P ó R，因为如果 Q = P R, 那么P Qó PP R ó QR，但P可以不等价于R. 2如果P Q ó QR，不能判断P ó R，因为如果 Q = P R, 那么P Qó PP R ó QR，但P可

5、以不等价于R.3如果P ó R，那么有P ó R，因为P ó R，那么P <-> R为永真式，及有P <-> R为永真式，所以P ó R.8、把以下各式用等价表示出来1(PQ) P解：原式 ó (PQ) (PQ) (PP)ó (PQ) (PQ) (PQ) (PQ) (PP) (PP)9、证明： 是最小功能完备集合证明:因为, 是最小功能完备集合,所以,如果 能表示出,那么其是功能完备集合。由于 P Q ó (P) Q ,所以 是功能完备集合。因为 不能相互表示，所以 是最小功能完备集合；同理可证：非，

6、条件非也能将或表示出来：P Q ó (P ! Q)8、分别利用真值表法和等价变换法求以下公式的主合取X式及主析取X式:(3) P(R(QP)解：真值表法PQRQPR(QP)P(R(QP)000101001111010001011001100100101111110100111111所以：主合取X式为 = (PQR) (PQR) = M4M6主析取X式为 = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7等价变换法略(4) (P(QR) (P(QR)解：真值表法PQRQRQRP(QR)P(QR)(P(QR) (P(QR)00001111001

7、00100010001000111010010001010101000101100001011110111所以：主合取X式为 = (PQR) ( PQR) ( PQR) (PQR) ( PQR) ( PQR) = M1M2M3M4M5M6主析取X式为 = (PQR)(PQR) = m0m7等价变换法略14、从A,B,C,D 4个人中派2人出差，要求满足以下条件：如果A去，那么必须在C或D中选一人同去；B和C不能同时去；C和D不能同时去。用构造X式的方法决定选派方案。解：由题设 A：A去，B：B去，C：C去，D：D去那么满足条件的选派应满足如下X式：ACÑDBCCD构造和以上X式等价的

8、主析取X式ACÑDBCCDÛAB C D ABCDABCDABCDABCDABCDABCDABCD共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求： ABCD，ABCD，ABCD即有三种方案：A和C去或者A和D去或者B和D去。15、证明以下蕴含试：1PQ=>P (PQ)证明：PQ Û P Q Û T(P Q) Û (PP) (P Q) Û P (PQ)Û P (PQ)所以，这是个等价式，因此也是个蕴含式2(PQ) Q=> (PQ)证明：(PQ) Q Û (PQ) Q Û (

9、PQ) Q Û (PQ) (QQ) Û (PQ) T Û (PQ)所以，这是个等价式，因此也是个蕴含式3PPR=>S证明：PPR Û F => S (F可蕴含任何命题公式)4P=>QRR证明：P=>T Û QRR 任何公式可蕴含永真式18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：（1） 如果藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。（2） 如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。（3） 藏宝房子靠近池塘。（4） 要么前院栽有大柏树，要么珍宝埋在花园正中地下。（5）

10、如果后院栽有香樟树，珍宝藏在附近。请利用蕴含关系找出藏宝处解：根据给定的条件有下述命题：P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下T：后院栽有香樟树M：珍宝藏在附近根据题意，得出：QPRPQRSTM Þ.QPRPQRSTM ÞPRPRSTM ÞRRSTM ÞSTMÞS 即珍宝藏在花园正中地下20、演绎证明下面各蕴含式：4(RQ) (RS),(QE) (SB), (EB),(PR) Þ P证明：运用反证方法，将结论的非纳入前提，证明步骤如下1Pp(附加前提)2PRp3RT 1,2 I4(RQ

11、) (RS)p5QST 3,4 I6(QE) (SB)p7EBT 5,6 I8(EB)p9F(矛盾式)T 7,8 E5P(QR),Q(RS) Þ P(QS)证明：运用cp法，将结论条件式的前件作为前提，证明步骤如下1Pp(附加前提)2P(QR)p3QRT 1,2 I4Q(RS)p5R(QS)T 4 E6QST 3,5 I7P(QS)CP 1,621、把以下句子演绎成逻辑形式，并给出证明2某公司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实：l 被盗现场没有留下任何痕迹l 失盗时，小花或那么小英正在卡拉ok厅l 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去l 如果

12、失盗时小花正在卡拉ok厅唱歌，那么金刚是最大的嫌疑者l 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游l 如果失盗时小英正在卡拉ok厅唱歌，那么瘦子是最大的嫌疑者根据以上事实，请通过演绎推理找出偷窃者解：根据给定的条件有下述命题：P：现场无任何痕迹Q：失窃时，小花在OK厅R：失窃时，小英在OK厅S：失窃时，小胖在附近T：金刚是偷窃者M：瘦子是偷窃者那么根据案情有如下命题公式：P，QR，SP，QT，SR，RM P P SP P S TI SR P R TI QR P Q TI QT P T TI即 金刚是偷窃者23、利用消解法证明以下各蕴含式：3P(QR),Q(RS)Þ P

13、(QS)证明：P(QR) Û PQRQ(RS) Û QRSP(QS)Û PQS因此子句集合 = PQR，QRS，P，Q，S 消解过程如下：1PQRp2Pp3QR由1，2归结4Qp5R由3，4归结6QRSp7Sp8QR由6，7归结9R由4，8归结10FLASE 由5，9归结导出空子句习题二1、把以下谓词翻译成谓词公式1每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数解： R(x)-x是实数Ra(x)-x是有利数翻译如下："(x)( Ra(x) R(x) "(x)( R(x) Ra(x)$(x)( R(x) Ra(x)2直线a和b平

14、行当切仅当a和b不相交解：A(x)-x是直线 F(x，y)-x与y平行Gx,y)-与相交 翻译如下："()"()A()A() (F(，)«G,)3除非所有的会员都参加，这个活动才有意义解：A(x)-是会员B(x)-x有意义-这个活动F(x，y)-参加翻译如下：B"(x)A(x)F(x，) 或"(x)A(x)F(x，)B4任何正整数不是合数就是质数解：A(x)-是正整数(x)-是合数(x)-是质数翻译如下："(x)A(x)(x)Ñ(x)（6） 但凡存钱的人都想有利息，如果没有利息，人们就不会存钱解：A(x)-是存钱的人F(x，

15、y)-想有P-存钱没有利息Q:-人们不存钱a:-利息翻译如下："(x)A(x)F(x，a)PQ2、设论域D = 0, 1, 2，把以下公式用不含量词的公式表示出来3"(x) P(x)$(x)Q(x)解：上式 Û P(0) P(1) P(2) Q(0) Q(1) Q(2)3、指出以下公式中的约束变元和自由变元，并确定公式的辖域解：略5、把以下语句符号化，并确定相应谓词公式是永真式、可满足式、还是矛盾式1如果两个数的积等于0，那么至少其中一个数为0，数x-1不等于0，所以数x-1和x+1的积也不等于0解：设论域在任意数域集合，运用常规的数学符号，翻译如下"(

16、x)"(y)( xy = 0 (x=0 y=0) (x-1 0) (x-1)(x+1) 0)这是一个可满足式，但不是永真式，因为存在x=-1时，谓词公式不成立，但其它情况均成立，如果论域中不包含-1，为真，包含就不成立2老实的人都讲实话。小林不是老实的，因而小林不讲实话解：H(x)-x老实T(x)-x讲真话a-小林翻译如下："(x)(H(x) T(x) H(a) T(a)这是一个可满足式，因为否认条件命题前件，不一定后件命题一定为假。及小林虽然不老实，但也可能讲实话6、对于题目给定的解释，求以下各公式相应的真值1 A = "(x) P(x) Q(x) R(a)，解

17、释 D =1,2,3，P(x): x2+x=2; Q(x): x是素数；R(x): x<3; a = 1解： 根据解释，A变为 P(1) Q(1)P(2) Q(2)P(3) Q(2)R(1)，根据P(x), Q(x), R(x)的定义，显然P(1) Q(1) = 1，P(2) Q(2) = 1，P(3) Q(2) = 1，R(1) =1，所以整个公式解释为真2 A=P(a, f(b) P(b,f(a), B="(x)$(y)P(y,x), C = $(y)"(x)P(y,x), E = "(x)"(y)P(x,y) P(f(x),f(y)，解释：D

18、=2,3, a = 3, b = 2, f(2)=3, f(3) =2，P(2,2)=0, P(2,3)=0, P(3,2)=P(3,3) = 1解： 根据解释，A变为 P( 3, 3 ) P( 2, 2 ) = 1 0 = 0 ，真值为假B变为 (P(2,2) P(2,3) (P(3,2) P(3,3) = 0011= 0，真值为假C变为 (P(2,2) P(2,3) (P(3,2) P(3,3) = 0011= 1，真值为真E变为 (P(2,2) P(3,3) (P(2,3) P(3,2) (P(3,2) P(2,3) (P(3,3) P(2,2) = 01011010= 0，真值为假7、

19、设论域为整数集合Z，试判定下面各公式是否是永真式，矛盾式或可满足式1"(x)x>-10x20答：为假命题2$(x)2x>8x2-6x+50答：为真命题，当4，5使满足谓词公式3"(x)$(y)x+y=1024答：为真命题，对任意整数x，y取值为1024-x及可4$(y)"(x)xy<10x+y2答：为真命题，y=0及成立9、证明以下各式成立：1"(x)"(y)P(x) Q(y) ó$(x)P(x)"(y)Q(y)证明：右式 ó"(x)"(y) P(x) Q(y) ó&

20、quot;(x) P(x) "(y)Q(y)ó$(x)P(x)"(y)Q(y)10、判别$(x)P(x) Q(x)ó$(x)P(x)$(x)Q(x)是否成立，如果成立，请给出证明；如果不成立，找一个解释予以说明解：$(x)P(x) Q(x) ó$(x) P(x) Q(x) ó$(x) P(x)$(x)Q(x) ó"(x)P(x)$(x)Q(x) 显然和$(x)P(x)$(x)Q(x)不等价，现构造如下解释设论域为D=a,b，P(a) = 0, P(b) = 1, Q(a) = 0, Q(b) = 0, 那么$(x)

21、P(x) Q(x)解释为真，而$(x)P(x)$(x)Q(x)解释为假，所以不等价11、把以下公式化为等价的前束X式，再求出对应的SKolemX式4"(x) P(x,0)($(y)P(y,f(x)"(z)Q(x,z)解：原式 ó"(x) P(x,0)($(y)P(y,f(x) "(z)Q(x,z) ó"(x) $(y) "(z) P(x,0)(P(y,f(x) Q(x,z)其SKolemX式为："(x) "(z) P(x,0)(P(g(x),f(x) Q(x,z)13、证明以下各式成立1$(x)

22、$(y)P(x) Q(y)Þ$(x)P(x)证明：左式 ó$(x)P(x) $(y)Q(y) Þ$(x)P(x)2($(x)P(x) Q(a) Þ$(x)P(x) Q(a)证明：左式 ó $(x)P(x) Q(a) ó$(x)P(x) Q(a)15、下面给出了对"(x) P(x) Q(x)Þ"(x) P(x) "(x)Q(x)的证明：原证明过程略试判断这个证明是否正确。你能给出一个证明吗.答：这个证明不正确，因为：如果 P Þ Q 那么QÞ P 而 P Þ Q不一定

23、成立，因此在这个证明过程中，第二步到第三步的蕴含不成立17、判别下面各个推理是否正确，如果不正确，指出错在什么地方题目不再重复1答：不正确，全称指定应该变为其他非x的变元，可修改为：P(y) Q(x)2答：正确3答：不正确，全称指定应该使用一样的个体常量，可修改为：P(a) Q(a)4答：题目不正确，存在量词的指导变元应该是另外的变元符号5答：不正确，存在量词的辖域应该包含全部的谓词，可修改为：$(x)P(x) Q(x) 6答：不正确，对不同的个体常元应该用不同的变元进展存在指定，可修改为：$(x)P(x) Q(b) 7答：不正确，推理过程中，应该先使用存在指定，然后使用全称指定习题三4、仔细

24、区分集合中的关系符号 和Í，并判断以下各蕴含关系的真假题目内容，见课本1真，根据子集的定义，任何属于B集合的元素也属于C集合2假，例如：A = 1,2 B = 1,2, 2, 3 C=B，1属于A，但并不是C集的元素3假，例如：A=1,2 B=1,2,3 C=1,2,3，A不是C的元素4假，例如：A=1,2 B=1,2,3 C=1,2,3，A不是C的子集5假，例如：A=1 B=1,2,3 C=1,2,3，A不是C的元素6真，子集关系具有传递性9、证明以下各式1A(B-C) = (AB)-(AC) 证明：左式 = A(BC) = (ABC) (ABA) = (AB) (CA) = (A

25、B) (AC) = (AB)-(AC) = 右式2A - (BC) = (A-B) (A-C)证明：右式 = (AB)(AC) = ABC = A(BC) = A - (BC) = 左式3(A-B)-C = A-(BC)=(A-C)-B证明：(A-B)-C = ABC = A(BC) = A-(BC) = ACB = (A-C)-B4A(BC)=(AB) C ó CÍA证明：充分性 A(BC)=(AB) C ó (AB) (AC) = (AB) C假设C不是A的子集，那么C中必存在元素c在C中而不在A中，那么c一定不在等式的左端集合中，而一定在右端集合中，矛盾 C

26、ÍA必要性 CÍA ， AC = C ，等式两端同时并上另一个集合，等式成立(AB) (AC) = (AB) C óA(BC)=(AB) C5A(BC) = (AB) (AC)证明：左式 = AB C-BC= A(B C) (BC)= A(B C) (BC)=ABC + ACB右式 = (AB) (AC)- (AB) (AC)= A(BC)ABC= A(BC) (ABC) = ABC + ACB 所以，左式 = 右式10、下面三式中，哪个可得出B=C的结论1AB=AC答：不能得出此结论，因为如果 B C,但B,C都是A的子集，AB=AC成立2AB=AC答：不能得出

27、此结论，因为B C，但A是CB子集，AB=AC成立（2） AB=AC答：能，因为AA = ,A = A=A,同时，ABC = ABC所以，等式两端 AAB= AAC óB =C ó B=C16、求A=Æ, a, b的幂集解：2A = Æ, Æ , a , b , Æ,a , Æ,b , a, b , Æ, a, b17、设A,B是任意两集合，证明12AÈ 2BÍ2 AÈ B，给出等号成立的条件证明：X Î2AÈ 2BÛ X Î2AÚ X

28、 Î 2BÛ X Í A Ú X Í B=> X Í A È BÛ X Î2 AÈ B等号成立的条件: A Í B或B Í A(因为假设A和B没有子集关系, 必有a ÎA B和 b ÎB A，使a, b Î2 AÈ B，但a, b Ï2AÈ 2B )22AÇ 2B = 2 AÇ B证明：X Î2AÇ 2BÛ X Î2AÙ X Î 2

29、BÛ X Í A Ù X Í BÛ X Í A Ç BÛ X Î2 AÇ B附加题：证明等式(AB) C = A(BC)证明：A(BC) = A(B-C)(C-B) = (A - (B-C)(C-B) (B-C)(C-B)- A)= ABC + ABC + ABC + ABC(AB) C = C(AB)那么按上式的划简方式，就是把C替换为A, 把A替换为B,将B替换为C,所以C(AB) = CAB + CAB + CAB + CAB = ABC + ABC + ABC + ABC习题四1、设A=

30、1,2,3,4,B=0,1,4,9,12.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来1xRy Ûx|y解: R = (1,0) ,(1,1),(1,4) ,(1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12)2xRy Û xºy(mod 3)解: R =(1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4)3xRy Û y/x £(y-x)/2解: R =(3,9)

31、, (3,12) , (4,9) , (4,12)2、用关系图和关系矩阵表示第1题中的各个关系解：略6、设在整数集Z上定义如下二元关系，试填写下表： 解：填表如下R自反性反自反性对称性反对称性传递性x|y×××xy(mod m)××xy>0×××xy0×××x=y或|x-y|=1×××x2> y2××(1) 因为x|x成立，所以自反性成立；所以反自反性不成立；因为x0时，x|0成立，但0|x不成立，所以对称性不成立，因为 1

32、|-1，和-1|1成立，所以反对称性不成立；但x|y,y|z成立，就一定有x|z成立，所以传递性成立(2) 因为模m相等是整数集合上的等价关系，所以具有自反、对称、传递性(3) 因为00 = 0，所以自反性不成立；因为x 0时必有 *>0,所以反自反性不成立；因为xy >0 必有yx>0,所以对称性成立；因此反对称性不成立；因为xy>0,yz>0,能得到x,y,z同号且不为0，所以，xz>0,所以传递性成立(4) 因为*0,所以自反性成立；因此，反自反性不成立；因为xy0,所以yx0，因此对称性成立；因此，反对称性不成立；因为-1*0 0，0*10，但-1*

33、1 < 0,所以传递性不成立(5) 因为 x=x，所以自反性成立；因此反自反性不成立；因为|x-y|=1，所以| y-x |=1，因此对称性成立；所以反对称性不成立；因为|1-2|=1，|2-3|=1，但|1-3|=2，所以传递性不成立因为 * = *，所以自反性不成立；反自反性成立；因为x2> y2 成立，那么y2> x2就不成立，所以对称性不成立，反对称性成立；传递性成立7、设R是集合A上的一个二元关系，合于xRy yRz => xRz,称R是A上的一个反传递关系。试举一个实际的反传递关系的例子解：例如在人群集合上，建立父子关系，那么就是一个反传递关系，因为如果 甲

34、是乙的父亲，乙是丙的父亲，那么甲和丙就一定不存在父子关系；另外，在正整数域上建立的倍数关系，也是一个反传递关系，因为如果 a 是 b的2倍，b是c的2倍，那么a 一定不是c的2倍8、设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。试判别当R和S同时具有下表左列某种指定性质时，经过指定的运算后所得到新关系也仍保持这种性质，把所得结论以，×的形式填在下表中相应的位置上RSRSR-SRS-RR-1自反性××反自反性××对称性×反对称性×××传递性×××

35、15;（1） 自反性的保持情况说明：因为R,S都具有自反性，所以IAÍR, IAÍS，因此IAÍRS, IAÍRS,所以自反性在RS，RS上保持因为IAÍS，所以IA不是S补集的子集，因此也不是R-S的子集，所以自反性在R-S上不保持因为R,S是自反的，所以对任意的a A，a,aR,S，所以a,aRS，因此自反性在RS上保持因为a,aR，所以a,a不属于-R,所以-R不具有自反性因为a,aR，所以a,aR-1，因此R-1具有自反性（2） 反自反性的保持情况说明：因为R,S都具有反自反性，等价于 IAR = , IAS = 因为IARS =，IA

36、RS=，所以RS，RS都是反自反的因为IAR-S =，所以 R-S也是自反的对于RS，假设a,bR,b,aS, 那么a,aRS, 所以反自反在RS上不一定保持因为a,a不属于R，所以a,a一定属于-R，所以-R一定是自反的，一定不是反自反的因为a,a不属于R，所以a,a也不属于R-1，因此R-1一定是反自反的（3） 对称性的保持情况说明：因为R,S是对称的，所以R= R-1,S= S-1，-R = (-R)-1= -R-1, -S = (-S)-1= -S-1因为RS-1= R-1 S-1= RS, 所以RS具有对称性因为RS-1= R-1 S-1= RS, 所以RS具有对称性因为R-S-1=

37、 R-S-1=R-1 -S-1= R-1 -S-1 = R-S，所以R-S具有对称性因为(RS)-1 = S-1 R-1 = SR ,但SR通常情况下与RS不一样，所以对称性不一定保持，例如：R = (a,b),(b,a), S = (b,c),(c,b),那么RS = a,c,并不对称因为-R-1 = -R-1 = -R，所以R的补是对称的因为 R逆的逆就是R，既等于R的逆，所以R的逆是对称的（4） 反对称性的保持情况说明：因为R,S是反对称的，所以R R-1Í IAS S-1Í IA因为RSRS-1 = RR-1SS-1Í IA ，所以RS具有反对称性因为如果

38、R = (a,b) S = (b,a),都是反对称的，但 RS = (a,b),(b,a)是对称的，所以RS不一定再保持对称性因为R是反对称的，而R-S在R的根底上减少集合元素，因此也一定是反对称的因为如果 R = (a,b),(c,a), S = (b,c),(a,a), 那么RS = a,c，c,a,变为对称的，所以反对称性，在复合运算下不一定保持因为如果R = a,b,(c,c)是反对称的，但-R = a,a,(b,b),(b,a),(a,c,),(c,a),(b,c),(c,b),不是反对称的，所以反对称性在补集运算上不保持因为R R-1Í IA，有因为 R = (R-1)-

39、1,所以R-1是反对称的（5） 传递性的保持情况说明：因为R,S是传递的，所以R2ÍR, S2ÍS因为RS2 = RSRSÍ R2S2(RS)(SR)Í RS，所以传递性保持如果R = (a,b), S=(b,c),都是传递关系，但RS = (a,b),(b,c)不再是传递关系，所以传递性在RS上不一定保持如果R=(a,b),(b,c),(a,c),S=(a,c),分别是两个传递关系，但R-S = (a,b),(b,c)不再是传递关系，所以传递性在R-S上不一定保持如果R=(a,b),(c,d),S=(b,c),(d,e), 分别是两个传递关系，但RS

40、= (a,c),(c,e)不再是传递关系，所以传递性在RS上不一定保持如果A = a,b,c, R = (a,b), 那么 R = A ×A R,显然不是传递的，所以传递性在-R上不一定保持因为R2ÍR，所以 R2-1ÍR-1 ，即R-12ÍR-1，所以传递性在逆运算下保持10、设R是集合A上的一个二元关系，证明1R是自反的 Û IAÍR证明: R是自反的 => IAÍR因为，R是自反的，所以对任意的A中元素a，有a,aR，即IA中任意元素都属于R，所以IAÍRIAÍR => R是自反的因为，

41、对任意的A中元素a，有a,aIA，又IAÍR，所以a,aR，所以R是自反的综上所述，R是自反的 Û IAÍR2R是反自反的 Û IAR = 证明：R是反自反的 => IAR = 因为，IA中的任意元素(a,a)，都不属于R，所以IAR = IAR = => R是反自反的因为IAR = ，所以IA中的任意元素(a,a)，都不属于R，即对任意的A中元素a，有a,aIA，都不属于R，所以R是反自反的综上所述，R是反自反的 Û IAR = 3R是对称的 Û R = R-1证明：R是对称的 => R = R-1因为对R中的任意

42、元素a,b,因为R是对称的，所以b,aR，那么a,bR-1,所以RÍ R-1因为对R-1中的任意元素a,b,那么b,aR，因为R是对称的，那么a,bR,所以R-1Í R所以 R = R-1R = R-1 => R是对称的对R中的任意元素a,b，因为R = R-1 ,所以a,b也属于R-1，所以b,aR，因此R是对称的综上所述，R是对称的 Û R = R-14R是反对称的 Û RR-1ÍIA证明:R是反对称的 => RR-1ÍIA因为对任意(a,b) RR-1 ,那么其就同时属于R和R-1 ，那么b,a也属于R，根据反对称的

43、定义，a = b，所以a,bIA ,所以RR-1ÍIARR-1ÍIA => R是反对称的假设R不是反对称的，那么必定存在 a b(a,b) R (b,a) R，那么a,bRR-1 ,但a,b不属于IA，矛盾；因此R必是反对称的综上所述，R是反对称的 Û RR-1ÍIA（1） R是传递的 Û R2ÍR证明：R是传递的 => R2ÍR因为对任意a,bR2 ,必存在c，使得a,c,(c,b)属于R，因为R是传递的，所以(a,b)属于R，因此R2ÍRR2ÍR => R是传递的因为对任意的R中的元

44、素a,b，(b,c)，那么(a,c)必定属于R2,也就属于R，所以R是传递的综上所述，R是传递的 Û R2ÍR11、设A=1,2,3,4,定义A上的关系 R = (a,b)|a=b+2,S = (x,y)|y=x+1x=2y 求：R。S,R。S-1。R,R2,(S-1)2解：根据题意，R=(3,1),(4,2)，S=(4,2),(1,2),(2，3)，3，4所以：R。S = 3，2，4，3 S-1 = 2，4，2，1，3，2，4，3所以：R。S-1 = (4,4),(4,1) R。S-1。R = (4,2) R2 = Æ (S-1)2 = (2,3),(3,4),

45、(3,1),(4,2)12、设A=a,b,c,d,e,f,g,h，A上的二元关系R对应的关系图4-5所示，求使Rm=Rn的最小整数m和n(m < n)答：R = R16；简要说明如下：本关系图分为两个局部，R = R1 R2,因为 R1。R2 = R2。R1 = Æ, 所以R2 = R12 R22 ,同理Rn = R1n R2n ,又因为 I1 = R13,I2=R25 ；3，5的最小公倍数为15，所以I = R15 ,所以R = I º R15 = R º R15 = R1613、设R是集合A上的二元关系，证明：1IAn = IA证明：因为单位关系的关系矩

46、阵为单位矩阵，而复合运算就是矩阵的乘法，根据单位矩阵的性质，IAn = IA2IAº R=R ºIA =R证明：同上，因为单位矩阵左乘、右乘一个矩阵，结果不变；所以IAº R=R ºIA =R3(RIA)n=IARR2R3Rn证明：根据书中并集关系复合的定理4.2，展开，并利用上述1，2的结论，及可得证严格可用归纳法15、写出第12题中关系图对应的关系矩阵，并利用warshall算法求这个关系的传递闭包解：习题五1、设 A = (a,b)| a,b Î N，定义A上的一个二元关系 R = (a,b),(c,d) | ad = bc 证明：R 是

47、 A 上的等价关系证明：自反性因为 对任意a,bÎ A, 都有：ab = ba, 既(a,b,(a,b) Î R，所以R是自反的对称性如果a,b,(c,d)Î R ,那么ad = bc, 所以 cb = ad,既c,d,(a,b)ÎR, 所以R是对称的传递性如果a,b,(c,d)Î R, (c,d),(e,f) Î R, 那么 ad = bc ,cf = ed ,因此，adcf = bced (注：如果 0 N 中)， 那么af = eb, 所以a,b,(e,f)Î R,R具有传递性综上所证，R是A上的等价关系3、集合 A

48、= 1，2，3，4的一个分化为 S0=1,2,4,3,求由S0导出的A上的一个等价关系R解：等价关系R = 1，2，4×1，2，43×3 = 1，1，2，2，4，4，1，2，1，4，2，1，2，4，4，1,(4,2),(3,3)4、试确定在4个元素的集合上可以定义的等价关系数目解：在此集合上可以确定的4分划个数为：1在此集合上可以确定的3分划个数为：c(4,2) = 6在此集合上可以确定的2分划个数为：c(4,1) + c(4,2) /2 = 7在此集合上可以确定的1分划个数为：c(4,4) = 1所以共可定义15个等价关系6、设R是非空集合A上的一个二元关系，具有对称性和

49、传递性。证明：如果对每一个xÎA，存在yÎA使xRy，那么，R是A上的等价关系证明：因为对每一个xÎA，存在yÎA使xRy，由于R是对称的，所以yRx；又因为R是传递的，当xRy 并且 yRx，那么xRx。所以R是自反的。综上所述，R是自反的，对称的和传递的，因此R是A上的等价关系8、设A是由54的正因子构成的集合，“|表示整除。画出偏序集<A,|>对应的Hasse图解：先求出偏序集，然后求处相应的cover，然后画出Hasse图A=1，2，3，6，9，18，27，54COVER(|)=(1,2), (1,3), (2,6), (3,6),

50、(3,9),(6,18), (9,18), (9,27), (18,54), (27,54)最大元：54最小元：1有4个包含元素最多的全序子集:L1=54,27,9,3,1L1=54,18,9,3,1L1=54,18,6,3,1L1=54,18,6,2,1182639541279、设A=a,b,c,画出偏序集合对应的Hasse图。试比拟此题与上题Hasse图的异同解：a,b,ca,ba,cb,cabcÆ两图的一样点 ： 都有最大小元 不同点：最大线序一个为5，一个为411、设R是集合A上的一个等价关系。现在在等价类之间定义一个新关系S使得R的任何等价类a和b满足aSbóaR

51、b，判别S是一个什么关系解:根据题目信息，猜想是等价关系，说明如下：（1） 因为对任意的aÎA，aRa成立R是A上的等价关系，是自反的，所以a S a,S是自反的（2） 假设a S b成立，那么aRb；因为R是对称的，所以bRa,因此b S a成立，所以S是对称的（3） 假设aSb,bSc成立，那么aRb,bRc，因为R是传递的，所以aRc成立，因此aSc成立，所以S是传递的综上所述，S是等价类集合上的等价关系习题六1、设A=1，2，3，4，B=A×A,确定下述集合是否为A到B的全函数或局部函数11，2，3，2，2，2，3，1，3，4，4，3答：根据本书全函数的定义，这是从A到B的全函数21，1，2，1，2，3，3，2，4答：根据本书函数的定义，每个原像只能有一个像，所以此定义不是A到B的函数31，3，3，2，3，3，3，2，1，4，4，1答：根据本书全函数的定义，这是从A到B的全函数2、判别以下关系中哪些是全函数1n1,n2|n1,n2