离散数学习题答案-2015(34页).doc

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

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

2、成比例- S (ET)（9） 如果一个整数能被6整除，那么它就能被2和3整除。如果一个整数能被3整除，那么它的各位数字之和也能被3整除解：设 P 一个整数能被6整除Q 一个整数能被2整除R 一个整数能被3整除S 一个整数各位数字之和能被3整除翻译为：（P （Q R） （R S）2、判别下面各语句是否命题，如果是命题，说出它的真值（1）BASIC语言是最完美的程序设计语言- Y，T/F（2）这件事大概是小王干的- N（3）x2 = 64- N（4）可导的实函数都是连续函数- Y，T/F（5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利- N（6）客观规律是不以人们意志为转移的- Y，T（7

3、）到2020年，中国的国民生产总值将赶上和超过美国- Y，N/A（8）凡事都有例外- Y，F3、构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式（1）（P （P Q） Q解：PQP QP （P Q）（P （P Q） Q可满足式00001011111001011011（2）（4）表略：（2）可满足式、（3）永真式 、（4）可满足式4、利用真值表方法验证下列各式为永真式（1）（8）略5、证明下列各等价式（3）P（Q R） （P Q）（P R）证明：左式PQ R PQP R （PQ）（P R） （P Q）（P R） 右式（4）（P Q）（R Q）（R P） （P Q）（R Q）（R

4、 P）证明：左式(（PR） Q）（R P） (（PR）R) ) (（PR）P) ) （QR）（QP） （P Q）（R Q）（R 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可以不等价于R.（3）如果P R，那么有P R，因为P R，则P R为永真式，及有P R为永真式，所以P R.8、把下列各式用等价

5、表示出来（1）(PQ) P解：原式 (PQ) (PQ) (PP) (PQ) (PQ) (PQ) (PQ) (PP) (PP)9、证明： 是最小功能完备集合证明:因为, 是最小功能完备集合,所以,如果 能表示出,则其是功能完备集合。由于 P Q (P) Q ,所以 是功能完备集合。因为 不能相互表示，所以 是最小功能完备集合；同理可证：非，条件非也能将或表示出来：P Q (P ! Q)8、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:(3) P(R(QP)解：真值表法PQRQPR(QP)P(R(QP)000101001111010001011001100100101111110

6、100111111所以：主合取范式为 = (PQR) (PQR) = M4M6主析取范式为 = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7等价变换法（略）(4) (P(QR) (P(QR)解：真值表法PQRQRQRP(QR)P(QR)(P(QR) (P(QR)0000111100100100010001000111010010001010101000101100001011110111所以：主合取范式为 = (PQR) ( PQR) ( PQR) (PQR) ( PQR) ( PQR) = M1M2M3M4M5M6主析取范式为 = (PQR)(P

7、QR) = m0m7等价变换法（略）14、从A,B,C,D 4个人中派2人出差，要求满足下列条件：如果A去，则必须在C或D中选一人同去；B和C不能同时去；C和D不能同时去。用构造范式的方法决定选派方案。解：由题设 A：A去，B：B去，C：C去，D：D去则满足条件的选派应满足如下范式：（A（CD）（BC）（CD）构造和以上范式等价的主析取范式（A（CD）（BC）（CD）（AB C D ）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求： （ABCD），（ABCD），（ABCD）即有三种方案：A

8、和C去或者A和D去或者B和D去。15、证明下列蕴含试：（1）PQ=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)所以，这是个等价式，因此也是个蕴含式（3）PPR=S证明：PPR F = S (F可蕴含任何命题公式)（4）P=QRR证明：P=T QRR （任何公式可蕴含永真式）18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：（1） 如果藏宝的房子靠近池

9、塘，那么珍宝不会藏在东厢房。（2） 如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。（3） 藏宝房子靠近池塘。（4） 要么前院栽有大柏树，要么珍宝埋在花园正中地下。（5） 如果后院栽有香樟树，珍宝藏在附近。请利用蕴含关系找出藏宝处解：根据给定的条件有下述命题：P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下T：后院栽有香樟树M：珍宝藏在附近根据题意，得出：（QP）（RP）Q（RS）（TM） ？（QP）（RP）Q（RS）（TM） P（RP）（RS）（TM） R（RS）（TM） S（TM）S 即珍宝藏在花园正中地下20、演绎证明下面各蕴含式：（4）(RQ)

10、(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 E（5）P(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）某公司发生了一起盗窃案，经仔细侦察，掌握了如下一

11、些事实：l 被盗现场没有留下任何痕迹l 失盗时，小花或则小英正在卡拉ok厅l 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去l 如果失盗时小花正在卡拉ok厅唱歌，那么金刚是最大的嫌疑者l 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游l 如果失盗时小英正在卡拉ok厅唱歌，那么瘦子是最大的嫌疑者根据以上事实，请通过演绎推理找出偷窃者解：根据给定的条件有下述命题：P：现场无任何痕迹Q：失窃时，小花在OK厅R：失窃时，小英在OK厅S：失窃时，小胖在附近T：金刚是偷窃者M：瘦子是偷窃者则根据案情有如下命题公式：P，QR，S P，Q T， S R，R M P P SP P

12、S TI SR P R TI QR P Q TI QT P T TI即 金刚是偷窃者23、利用消解法证明下列各蕴含式：（3）P(QR),Q(RS) P(QS)证明：P(QR) PQRQ(RS) QRS（P(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

13、(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平行G（x,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，)）B（）（4）任何正整数不是合数就是质数解：A(x)-是正整数(x)-是合数(x)-是质数翻译如下：(x)（A(x)(x)(x)）（6） 凡是存钱的人都想有利息，如果

14、没有利息，人们就不会存钱解：A(x)-是存钱的人F(x，y)-想有P-存钱没有利息Q:-人们不存钱a:-利息翻译如下：(x)（A(x)F(x，a)）（PQ）2、设论域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解：设论域在任意数域集合，运

15、用常规的数学符号，翻译如下(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

16、)，解释 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 )（2）2A 2B = 2 A B 证明：X 2A 2B X 2A X 2B X A X B X A B X 2 A B附加题

17、：证明等式(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用序偶的集合表示出来（1）xRy x|y解: R = (1,0) ,(1,1),(1,4) ,(

18、1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12)（2）xRy xy(mod 3)解: R =(1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4)（3）xRy y/x (y-x)/2解: R =(3,9), (3,12) , (4,9) , (4,12)2、用关系图和关系矩阵表示第1题中的各个关系解：略6、设在整数集Z上定义如下二元关系，试填写下表： 解：填表如下R自反性反自反性对称性反对称性传递性x|yxy(mod m)xy0xy0

19、x=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,所以传递性成立(4) 因为xx0,所以自反性成立；因此，

20、反自反性不成立；因为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倍，那么a 一定不是c的2倍8、设R和S都是集合A上的二元

21、关系，它们经过关系运算后得到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,a）R,S，所以（a,a）RS，因此自反性在RS上保持因为（a,a）R，所以（a,a）不属于-

22、R,所以-R不具有自反性因为（a,a）R，所以（a,a）R-1，因此R-1具有自反性（2） 反自反性的保持情况说明：因为R,S都具有反自反性，等价于 IAR = , IAS = 因为IARS =，IA（RS）=，所以RS，RS都是反自反的因为IAR-S =，所以 R-S也是自反的对于RS，假设（a,b）R,（b,a）S, 那么（a,a）RS, 所以反自反在RS上不一定保持因为（a,a）不属于R，所以（a,a）一定属于-R，所以-R一定是自反的，一定不是反自反的因为（a,a）不属于R，所以（a,a）也不属于R-1，因此R-1一定是反自反的（3） 对称性的保持情况说明：因为R,S是对称的，所以R=

23、 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的补是对

24、称的因为 R逆的逆就是R，既等于R的逆，所以R的逆是对称的（4） 反对称性的保持情况说明：因为R,S是反对称的，所以R R-1 IA S S-1 IA因为（RS）（RS）-1 = （RR-1）（SS-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）,变为对称的，所以反对称性，在复合运算下不一定

25、保持因为如果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)-1,所以R-1是反对称的（5） 传递性的保持情况说明：因为R,S是传递的，所以R2R, S2S因为（RS）2 = （RS）（RS） R2S2(RS)(SR) RS，所以传递性保持如果R = (a,b), S=(b,c),都是传递关系，但RS = (a,b),(b,c)不再是传递关系，所以传递性在RS上不一定保持如果R=(a,b),(b,c),(a,c)

26、,S=(a,c),分别是两个传递关系，但R-S = (a,b),(b,c)不再是传递关系，所以传递性在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-1）2R-1，所以传递性在逆运算下保持10、设R是集合A上的一个二元关系，证明（1）R是自反的 IAR证明: R是自反的 = IAR因为，R是自反的，所以对任意的A中元素a，有（a,a）R，即IA中任意元素都属于R，所以IARIAR = R是自反的因为，对任意的A中元素a，有（a,a）IA，又IAR，所以（a,a）R，所以R是自反的综上所述，R是自反的 IAR（2）R是反自反的 IAR = 证明：R是反自反的 = IAR = 因为，IA中的任意元素(a,a)，都不属于R，所以IAR = IAR = = R是反自反的因为IAR = ，所以IA中的任意元素(a,a)，都不属于R，即对任意的A中元素a，有（a,a）IA，都不属于R，所以R是反自反的综上所述，R是反自反