离散数学习题答案_2015.doc

《离散数学习题答案_2015.doc》由会员分享，可在线阅读，更多相关《离散数学习题答案_2015.doc（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 (ET)（9） 如果一个整数能

2、被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年，中国的国民生产总值将赶上和超过美国- Y，N/A8凡事都有例外-

3、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) ) (PRP) ) QRQP P QR QR P 右式6、如果P Q QR,能否断定 P R ？ 如果P Q QR，能否断定 P R？如果P R，能

4、否断定 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可以不等价于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

5、(P) Q ,所以 是功能完备集合。因为 不能相互表示，所以 是最小功能完备集合；同理可证：非，条件非也能将或表示出来：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)解：真值表法

6、PQRQRQRP(QR)P(QR)(P(QR) (P(QR)0000111100100100010001000111010010001010101000101100001011110111所以：主合取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

7、去那么满足条件的选派应满足如下X式：ACDBCCD构造和以上X式等价的主析取X式ACDBCCDAB 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 (PQ) Q (PQ) (QQ) (PQ) T (PQ)所以，这是个

8、等价式，因此也是个蕴含式3PPR=S证明：PPR F = S (F可蕴含任何命题公式)4P=QRR证明：P=T QRR 任何公式可蕴含永真式18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：（1） 如果藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。（2） 如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。（3） 藏宝房子靠近池塘。（4） 要么前院栽有大柏树，要么珍宝埋在花园正中地下。（5） 如果后院栽有香樟树，珍宝藏在附近。请利用蕴含关系找出藏宝处解：根据给定的条件有下述命题：P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园

9、正中地下T：后院栽有香樟树M：珍宝藏在附近根据题意，得出：QPRPQRSTM ？QPRPQRSTM PRPRSTM RRSTM STMS 即珍宝藏在花园正中地下20、演绎证明下面各蕴含式：4(RQ) (RS),(QE) (SB), (EB),(PR) P证明：运用反证方法，将结论的非纳入前提，证明步骤如下1Pp(附加前提)2PRp3RT 1,2 I4(RQ) (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)p

10、3QRT 1,2 I4Q(RS)p5R(QS)T 4 E6QST 3,5 I7P(QS)CP 1,621、把以下句子演绎成逻辑形式，并给出证明2某公司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实：l 被盗现场没有留下任何痕迹l 失盗时，小花或那么小英正在卡拉ok厅l 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去l 如果失盗时小花正在卡拉ok厅唱歌，那么金刚是最大的嫌疑者l 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游l 如果失盗时小英正在卡拉ok厅唱歌，那么瘦子是最大的嫌疑者根据以上事实，请通过演绎推理找出偷窃者解：根据给定的条件有下述命题：P：现场无任何

11、痕迹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(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归结导出空

12、子句习题二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平行当切仅当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任何正整数不是合数就

13、是质数解：A(x)-是正整数(x)-是合数(x)-是质数翻译如下：(x)A(x)(x)(x)（6） 但凡存钱的人都想有利息，如果没有利息，人们就不会存钱解：A(x)-是存钱的人F(x，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

14、，那么至少其中一个数为0，数x-1不等于0，所以数x-1和x+1的积也不等于0解：设论域在任意数域集合，运用常规的数学符号，翻译如下(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)这是一个可满足式，因为否认条件命题前件，不一定后件命题一定为假。及小林虽然不老实，但也可能讲实话

15、6、对于题目给定的解释，求以下各公式相应的真值1 A = (x) P(x) Q(x) R(a)，解释 D =1,2,3，P(x): x2+x=2; Q(x): x是素数；R(x): x-10x20答：为假命题2$(x)2x8x2-6x+50答：为真命题，当4，5使满足谓词公式3(x)$(y)x+y=1024答：为真命题，对任意整数x，y取值为1024-x及可4$(y)(x)xy 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

16、 X 2A X 2B 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=1,2,3,4,B=0,1,4,9,12.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来1xR

17、y 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 xy(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), (3,12) , (4,9) , (4,12)2、用关系图和关系矩阵表示第1题中的各个关系解：略6、设在整数集Z上定义如下二元关系，试填写下表： 解：填表如下R自反性反自反

18、性对称性反对称性传递性x|yxy(mod m)xy0xy0x=y或|x-y|=1x2 y2(1) 因为x|x成立，所以自反性成立；所以反自反性不成立；因为x0时，x|0成立，但0|x不成立，所以对称性不成立，因为 1|-1，和-1|1成立，所以反对称性不成立；但x|y,y|z成立，就一定有x|z成立，所以传递性成立(2) 因为模m相等是整数集合上的等价关系，所以具有自反、对称、传递性(3) 因为00 = 0，所以自反性不成立；因为x 0时必有 xx0,所以反自反性不成立；因为xy 0 必有yx0,所以对称性成立；因此反对称性不成立；因为xy0,yz0,能得到x,y,z同号且不为0，所以，xz0

19、,所以传递性成立(4) 因为xx0,所以自反性成立；因此，反自反性不成立；因为xy0,所以yx0，因此对称性成立；因此，反对称性不成立；因为-1*0 0，0*10，但-1*1 y2 成立，那么y2 x2就不成立，所以对称性不成立，反对称性成立；传递性成立7、设R是集合A上的一个二元关系，合于xRy yRz = xRz,称R是A上的一个反传递关系。试举一个实际的反传递关系的例子解：例如在人群集合上，建立父子关系，那么就是一个反传递关系，因为如果 甲是乙的父亲，乙是丙的父亲，那么甲和丙就一定不存在父子关系；另外，在正整数域上建立的倍数关系，也是一个反传递关系，因为如果 a 是 b的2倍，b是c的2

20、倍，那么a 一定不是c的2倍8、设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。试判别当R和S同时具有下表左列某种指定性质时，经过指定的运算后所得到新关系也仍保持这种性质，把所得结论以，的形式填在下表中相应的位置上RSRSR-SRS-RR-1自反性反自反性对称性反对称性传递性（1） 自反性的保持情况说明：因为R,S都具有自反性，所以IAR, IAS，因此IARS, IARS,所以自反性在RS，RS上保持因为IAS，所以IA不是S补集的子集，因此也不是R-S的子集，所以自反性在R-S上不保持因为R,S是自反的，所以对任意的a A，a,aR,S，所以a,aRS，因此自反性在

21、RS上保持因为a,aR，所以a,a不属于-R,所以-R不具有自反性因为a,aR，所以a,aR-1，因此R-1具有自反性（2） 反自反性的保持情况说明：因为R,S都具有反自反性，等价于 IAR = , IAS = 因为IARS =，IARS=，所以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

22、= 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= 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，

23、既等于R的逆，所以R的逆是对称的（4） 反对称性的保持情况说明：因为R,S是反对称的，所以R R-1 IAS S-1 IA因为RSRS-1 = RR-1SS-1 IA ，所以RS具有反对称性因为如果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)是反对称的，但

24、-R = a,a,(b,b),(b,a),(a,c,),(c,a),(b,c),(c,b),不是反对称的，所以反对称性在补集运算上不保持因为R R-1 IA，有因为 R = (R-1)-1,所以R-1是反对称的（5） 传递性的保持情况说明：因为R,S是传递的，所以R2R, S2S因为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

25、)不再是传递关系，所以传递性在R-S上不一定保持如果R=(a,b),(c,d),S=(b,c),(d,e), 分别是两个传递关系，但RS = (a,c),(c,e)不再是传递关系，所以传递性在RS上不一定保持如果A = a,b,c, R = (a,b), 那么 R = A A R,显然不是传递的，所以传递性在-R上不一定保持因为R2R，所以 R2-1R-1 ，即R-12R-1，所以传递性在逆运算下保持10、设R是集合A上的一个二元关系，证明1R是自反的 IAR证明: R是自反的 = IAR因为，R是自反的，所以对任意的A中元素a，有a,aR，即IA中任意元素都属于R，所以IARIAR = R是自反的因为，对任意的A中元素a，有a,aIA，又IAR，所以a,aR，所以R是自反的综上所述，R是自反的 IAR2R是反自反的 IAR = 证明：R是反自反的 = IAR = 因为，IA中的任意元素(a,a)，都不属于R，所以IAR = IAR = = R是反自反的因为IAR = ，所以IA中的任意元素(a,a)，都不属于R，即对任意的A中元素a，有a,aIA，都不属于R，所以R是反自反的综上所述，R是反自反的