《离散数学-冯栾石陈编-习题答案.doc》由会员分享，可在线阅读，更多相关《离散数学-冯栾石陈编-习题答案.doc（50页珍藏版）》请在金锄头文库上搜索。
1、仅供个人参考For personal use only in study and research; not for commercial use习题一1、 利用逻辑联结词把下列命题翻译成符号逻辑形式（1） 他既是本片的编剧，又是导演 - P Q（2） 银行利率一降低，股价随之上扬- P Q（3） 尽管银行利率降低，股价却没有上扬- P Q（4） 占据空间的、有质量而且不断变化的对象称为物质 - M ?(SPT)（5） 他今天不是乘火车去北京，就是随旅行团去了九寨沟- P Q（6） 小张身体单薄，但是极少生病，并且头脑好使- P Q R（7） 不识庐山真面目，只缘身在此山中- P Q（解释：因
2、为身在此山中，所以不识庐山真面目）（8） 两个三角形相似，当且仅当他们的对应角相等或者对应边成比例- 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）我们要发扬
3、连续作战的作风，再接再厉，争取更大的胜利- N（6）客观规律是不以人们意志为转移的- Y，T（7）到2020年，中国的国民生产总值将赶上和超过美国- Y，N/A（8）凡事都有例外- Y，F3、 构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式（1）（P （P Q） Q解：PQP QP （P Q）（P （P Q） Q可满足式00001011111001011011（2）（4）略4、 利用真值表方法验证下列各式为永真式（1）（8）略5、 证明下列各等价式（1）（P Q）（P Q）（P Q）? P证明：左式 ? （P Q）（P Q）（P Q）? P （P Q）（P Q） T （P
4、Q）? P ? 右式（2）（P Q）（R Q）?（P R）Q证明：左式 ?（PQ）（RQ） （P R）Q （P R）Q （P R）Q ? 右式（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 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
5、? 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.7、 检查和是否满足结合率解： 用真值表方式检查PQRPQQR(PQ) RP(Q R)00011110011101010111101110011001110101110011001101110011由上表可知，不满住
6、结合率PQRPQQR(PQ) RP(Q R)00011000011001010001101100011000110101000011000101110000由上表可知，不满住结合率8、 把下列各式用等价表示出来（1）(PQ) P解：原式 ? (PQ) (PQ) (PP)? (PQ) (PQ) (PQ) (PQ) (PP) (PP)（2）P（P Q）解：原式 ? PPQ? Q? (QQ) (QQ)（3）（P（Q R） P解：原式 ? （ PQ R） P? P（Q P）（R P）? (PP) （(QQ) (PP)）（R(PP)）? (PP) （(QQ) (PP)）（(QQ) (PP)）（R(PP)
7、）（R(PP)）设：(PP) = N（(QQ) (PP)）（(QQ) (PP)）= L（R(PP)）（R(PP)） = M则上式? (NN) (LL) (NN) (LL) (MM)（4） PQ（R P）解：原式 ? PQ（RP）? (PP) (QQ) （(PP) (RR)）? (（(PP) (QQ)）（(PP) (QQ)）) （(PP) (RR)）设：(（(PP) (QQ)）（(PP) (QQ)）) = N（(PP) (RR)） = M则上式? (NM) (NM)9、 证明： 是最小功能完备集合证明:因为, 是最小功能完备集合,所以,如果 能表示出,则其是功能完备集合。由于 P Q ? (P)
8、 Q ,所以 是功能完备集合。因为 不能相互表示，所以 是最小功能完备集合；同理可证：非，条件非也能将或表示出来：P Q ? (P ! Q)10、 证明: ， 不是功能完备集证明： PQ没有办法通过，的公式表达出来，因为PQPQPP(PP)PQ000010011011101011111010所以，通过，不能表达出真值为三个1或1个1的情况，因此，不能表达出PQ，所以不是功能完备集。11、 用和把公式 PQR和（PQ）R表示出来解：（PQ）R ? (（PQ）（PQ）) R? (（PQ）（PQ）) R) (（PQ）（PQ）) R)? (（PQ）（PQ）R) （PQ）（PQ）R）? （(（PQ）（P
9、Q）R)）（PQ）（PQ）R）（PQ）R?（ (（PQ）（PQ）R)12、 分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:(1) P(RQ) S)解：真值表法PQRSRQ(RQ) SP(RQ) S)0000011000101100100110011011010001101010110110101011111110000111001011101001110110111100011110101111101001111111所以：主合取范式为 = PQRS = M14主析取范式为 = m1m2m3m4m5m6m7m 8m9m10m11m12m13m14m16等价变换法（略）(2)（
10、PQ）（PQ）解：真值表法PQPQPQ（PQ）（PQ）00100011111011111001所以：主合取范式为 = PQ = M0主析取范式为 = (PQ)(PQ)(PQ) = m1m2m3等价变换法（略） (3) P(R(QP)解：真值表法PQRQPR(QP)P(R(QP)000101001111010001011001100100101111110100111111所以：主合取范式为 = (PQR) (PQR) = M4M6主析取范式为 = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7等价变换法（略）(4) (P(QR) (P(QR)解：真值表法PQRQRQRP(QR)P(QR)(P(QR) (P(QR)00001111001001000
