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

习题一 1.利用逻辑联结词把下列命题翻译成符号逻辑形式：利用逻辑联结词把下列命题翻译成符号逻辑形式：（1）他既是本片的编剧，又是导演。）他既是本片的编剧，又是导演。令令P:编剧编剧;Q:导演导演;译为译为P Q（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）小张身体单薄，但是极少生病，并且头脑好使。）小张身体单薄，但是极少生病，并且头脑好使。令令P:身体单薄身体单薄;Q:少生病少生病;R:头脑好使头脑好使;译为译为P Q 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 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)矛盾式矛盾式.习题一 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，能否断定，能否断定P R？解：解：1)P Q R Q时，不能断定时，不能断定P R.因为当因为当Q T时时,P和和R可以取不同的值可以取不同的值.2)P Q R Q时，不能断定时，不能断定P R.(由由Q F推推)3)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)P Q RR (Q P)P(R (Q P)0 0 0010 0 1110 1 0010 1 1011 0 0001 0 1111 1 0001 1 111.习题一 12(3)解法二解法二(等价变换法等价变换法)P(R (Q P)P (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)(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 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 QP Q.习题一 21(2)一个有钱人死前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻一个有钱人死前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：找珍宝的线索如下：（1）如果藏宝房靠近池塘，那么珍宝不会藏在东厢房）如果藏宝房靠近池塘，那么珍宝不会藏在东厢房；（2）如果房子的前院载有大柏树，那么珍宝就藏在东厢房；）如果房子的前院载有大柏树，那么珍宝就藏在东厢房；（3）藏宝房子靠近池塘；）藏宝房子靠近池塘；（4）要么前院载有大柏树，那么珍宝埋在花园正中地下；）要么前院载有大柏树，那么珍宝埋在花园正中地下；（5）如果后院载有香樟树，珍宝就藏在附近。）如果后院载有香樟树，珍宝就藏在附近。请利用蕴含关系找出藏宝处。请利用蕴含关系找出藏宝处。解解:令令P:靠近池塘靠近池塘;Q:藏在东厢房藏在东厢房;R:有大柏树有大柏树;S:花园正中地下花园正中地下;U:有香樟树有香樟树;V:在附近在附近;翻译为翻译为:P Q,R Q,P,R S,U V可推出结果为可推出结果为S,过程如下过程如下:QR QRR SS PP Q.习题一 20(4)演绎证明下列蕴含式：(P Q)(R S),(Q E)(S B),(E B),P R P证明证明:(直接法直接法)步骤步骤公式公式规则规则 (1)(P Q)(R S)P(2)(P R)(Q S)TI(1)(3)(Q E)(S B)P(4)(Q S)(E B)TI(3)(5)(P R)(E B)TI(2)(4)(6)(E B)P(7)(P R)TI(5)(6)(8)P RTE(7)(即即R P)(9)P RP(10)PTI(8)(9).习题一 20(5)演绎证明下列蕴含式：P(Q R),Q(R S)P(Q S)证明证明:(CP法法)步骤步骤公式公式规则规则 (1)PP(附加附加)(2)P(Q R)P(3)Q RTI(1)(2)(4)Q(R S)P(5)R(Q S)TE(4)(6)Q(Q S)TI(3)(5)(7)Q STE(6)(8)P(Q S)CP(1)(7).习题一 21(2)某单位发生一起盗窃案，经仔细侦查，掌握了如下一些事实：某单位发生一起盗窃案，经仔细侦查，掌握了如下一些事实：被盗现场没留下任何痕迹；被盗现场没留下任何痕迹；失窃时，小花或者小英正在卡拉失窃时，小花或者小英正在卡拉OK厅；厅；如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去；如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去；如果失窃时小花正在卡拉如果失窃时小花正在卡拉OK厅唱歌，那么金刚是最大的嫌疑者；厅唱歌，那么金刚是最大的嫌疑者；如果失窃时小胖不在附近，那么他的女友小英会和他一起外出郊游；如果失窃时小胖不在附近，那么他的女友小英会和他一起外出郊游；如果失窃时小英正在卡拉如果失窃时小英正在卡拉OK厅唱歌，那么瘦子是最大的嫌疑者；厅唱歌，那么瘦子是最大的嫌疑者；根据以上事实，请通过演绎推理找出偷窃者。根据以上事实，请通过演绎推理找出偷窃者。解解:令令P1:未留痕迹未留痕迹;P2:小花在小花在OK厅厅;P3:小英在小英在OK厅厅;P4:小胖在附近小胖在附近;J:金刚是嫌犯金刚是嫌犯;S:瘦子是嫌犯瘦子是嫌犯;翻译为翻译为:P1,P2 P3,P4 P1,P2 J,P4 P3,P3 S可推出结果为可推出结果为”金刚是嫌犯金刚是嫌犯”,过程如下过程如下:P1P4 P1P4P2 P3P3P2P2 JP4 P3J.习题一 23(3)利用消解法证明蕴含式：P(Q R),Q(R S)P(Q S)证明证明:首先把结论否定加入前提得公式集首先把结论否定加入前提得公式集:P(Q R),Q(R S),(P(Q S)构造子句集构造子句集:P Q R,Q R S,P,Q,S消解过程如下消解过程如下:(1)P 引入子句引入子句(2)P Q R引入子句引入子句(3)Q R由由(1)(2)消解消解(4)Q引入子句引入子句(5)R由由(3)(4)消解消解(6)Q R S引入子句引入子句(7)Q S由由(5)(6)消解消解(8)S 引入子句引入子句(9)Q 由由(7)(8)消解消解(10)由由(9)(4)消解消解(11).