离散数学第一章命题逻辑习题答案.ppt

1、习题一 1.,利用逻辑联结词把下列命题翻译成符号逻辑形式： （1）他既是本片的编剧，又是导演。 令P:编剧; Q:导演; 译为PQ （2）银行利率一降低，股价随之上扬。 令P:利率降低; Q:股价上扬; 译为P Q （3）尽管银行利率降低，股价却没有上扬。 译为P Q 或 (P Q),习题一 1.,利用逻辑联结词把下列命题翻译成符号逻辑形式： （4）占据空间的、有质量而且不断变化的对象称为物质。 令P:占据空间; Q:有质量; R:变化; S:物质;译为(P Q R) S （5）他今天不是乘火车去了北京，就是随旅游团去了九寨沟。 令P:去北京; Q:去九寨沟;译为P Q （6）小张身体单薄，但

2、是极少生病，并且头脑好使。 令P:身体单薄; Q:少生病; R:头脑好使; 译为PQ R,习题一 1.,利用逻辑联结词把下列命题翻译成符号逻辑形式： （7）不识庐山真面目，只缘生在此山中。 令P:身在此山中; Q:识庐山真面目;译为P Q （8）两个三角形相似当且仅当它们对应角相等或者对应边成比例。 令P:两个三角形相似; Q:对应角相等; R:对应边成比例;译为P (Q R) （9）如果一个整数能被6整除，那么它就能被2和3整除。如果一个整数能被3整除，那么它的各位数字之和也能被3整除。 令P:被6整除; Q:被2整除; R:被3整除; S:各位数字之和被3整除。译为(P (Q R) (R

3、S),习题一 2.,判别下面各语句是否是命题，如果是命题，说出其真值。 （1）BASIC语言是最完美的程序设计语言。Y(0) （2）这件事大概是小王干的。Y(待定) （3）x2=64. N （4）可导的一元实函数都是连续函数。Y(1) （5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利。N （6）客观规律是不依人们意志为转移的。Y(1) （7）到2020年，中国的国民生产总值将赶上和超过美国。Y(待定) （8）凡事都有例外。悖论,习题一 3.,构造下列公式的真值表，判断哪些是永真式、矛盾式或可满足式： 解：构造真值表略. (1)可满足式 (2)可满足式 (3)永真式, 可满足式 (4)矛

4、盾式,习题一 5.证明下列各等价式,(3) P (Q R) (P Q) (P R) 证明 : P (Q R) P Q R ( P Q) ( P R) (P Q) (P R),习题一 5.证明下列各等价式,(4)(P Q) (Q R) (R P) (P Q) (Q R) (R P) 证明 : (P Q) (Q R) (R P) (Q (P R) ) (R P) (分配律) (Q (R P) ) (P R (R P) ) (Q R) (P Q) (R P) (分配律、吸收律、交换律),习题一 6.,如果P Q R Q，能否断定P R？ 如果P Q R Q，能否断定P R？ 如果 P R ，能否断定

5、P R？ 解： P Q R Q时，不能断定P R. 因为当Q T时, P和R可以取不同的值. P Q R Q时，不能断定P R. (由Q F推) P R时, 两端同时取“非”, 即P R.,习题一 13 (3)分别用真值表法和等价变换法求公式 P (R (Q P)的主合取范式和主析取范式,解法一 (真值表法) 由对应于公式取值为0的全部解释得主合取范式： (P Q R) (P Q R) 由对应于公式取值为1的全部解释得主析取范式： (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R),习题一 12(3),解法二 (等价变换法) P (R (Q P) P

6、 (R ( Q P) P R P R (Q Q ) (P Q R) (P Q R) (主合) 由 P R ( P (Q Q) (R R) (P P) (Q Q) R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (主析),习题一 12(4) 分别用真值表法和等价变换法求公式 (P (Q R) (P (Q R)的主合取范式和主析取范式,真值表法略. (P (Q R) (P (Q R) (P (Q R) ( P (Q R) (P Q) (P R ) (P Q) (P R ) (P Q (R R) (P (Q Q) R ) (P Q (R R) )

7、 (P (Q Q) R ) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (主合) (P Q R) (P Q R) (主析),习题一 14.,从A、B、C、D4人中派2人出差，要求满足下述条件：如果A去，则必须在C或D中选一人同去；B和C不能同时去；C和D不能同去。用构造范式的方法决定出选派方案。 若X表示“X去出差”, 可得公式 (A (C D) (B C) (C D) (A (C D) (C D) ) (B C ) (C D ) (A B C D) (A B C D) (A B C D) (A B C D) (A B C D) (A B C

8、 D) (A B C D) (A B C D) 可得派法: B, D A, C A, D,习题一 15(2) 证明蕴含式：(P Q) Q P Q,证明：(P Q) Q ( P Q) Q (P Q) Q (P Q) ( Q Q) P Q P Q,习题一 21(2),一个有钱人死前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下： （1）如果藏宝房靠近池塘，那么珍宝不会藏在东厢房 ； （2）如果房子的前院载有大柏树，那么珍宝就藏在东厢房； （3）藏宝房子靠近池塘； （4）要么前院载有大柏树，那么珍宝埋在花园正中地下； （5）如果后院载有香樟树，珍宝就藏在附近。 请利用蕴含关系

9、找出藏宝处。 解:令P:靠近池塘; Q:藏在东厢房; R:有大柏树; S:花园正中地下; U:有香樟树; V:在附近; 翻译为: P Q, R Q, P, R S, U V 可推出结果为S, 过程如下:, Q,R Q,R,R S,S,P P Q,习题一 20(4) 演绎证明下列蕴含式：,(P Q) (R S) , (Q E) (S B), (EB), P R P 证明:(直接法) 步骤公式规则 (P Q) (R S) P (PR) (QS)TI(1) (Q E) (S B)P (QS) (EB)TI(3) (PR) (EB)TI(2)(4) (EB)P (PR)TI(5)(6) P RTE(7

10、) (即R P ) P RP PTI(8)(9),习题一 20(5) 演绎证明下列蕴含式：,P (Q R), Q (R S) P (Q S) 证明:(CP法) 步骤公式规则 PP(附加) P (Q R)P Q RTI(1)(2) Q (R S)P R (Q S) TE(4) Q (Q S)TI(3)(5) Q STE(6) P (Q S)CP(1)(7),习题一 21(2),某单位发生一起盗窃案，经仔细侦查，掌握了如下一些事实： 被盗现场没留下任何痕迹； 失窃时，小花或者小英正在卡拉OK厅； 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去； 如果失窃时小花正在卡拉OK厅唱歌，

11、那么金刚是最大的嫌疑者； 如果失窃时小胖不在附近，那么他的女友小英会和他一起外出郊游； 如果失窃时小英正在卡拉OK厅唱歌，那么瘦子是最大的嫌疑者； 根据以上事实，请通过演绎推理找出偷窃者。 解:令P1:未留痕迹; P2:小花在OK厅; P3:小英在OK厅; P4:小胖在附近; J:金刚是嫌犯; S:瘦子是嫌犯; 翻译为: P1, P2 P3, P4 P1, P2 J, P4 P3, P3 S 可推出结果为”金刚是嫌犯”, 过程如下:,P1,P4 P1,P4,P2 P3,P3,P2,P2 J,P4 P3,J,习题一 23(3) 利用消解法证明蕴含式：,P (Q R), Q (R S) P (Q S) 证明: 首先把结论