0 1 1 （5） 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 A B C B?C A?B A?C A?(B?C) （A?B)?(A?C) 0 0 0 0 1 1 1 1

5. 只使用命题变元p和q能构造多少不同的命题公式真值表？ 解 能构造出16（2的4次方）种不同的命题公式真值表。

6. 用等价演算法证明下面的等价式 （1）p?(p?q)?(p??q)

（2）(p??q)?(?p?q)?(p?q)??(p?q) （3）p?(q?p)??p?(p??q) （4）?(p?q)?(p?q)??(p?q) （5）(p?q)?(p?r)?p?(q?r) （6）(p?r)?(q?r)?(p?q)?r （7）p?(q?r)?(p?q)?r （8）p?(q?r)?q?(p?r)

解 （1）右边?(p?q)?(p??q)?p?(q??q)?p?1?p=左边 （2）

左边＝(p??q)?(?p?q) 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 ?(p??p)?(p?q)?(?q??p)?(?q?q) ?1?(p?q)?(?q??p)?1

?(p?q)?(?q??p)

?(p?q)??(p?q)

=右边

（3）

左边＝p?(q?p)＝?p?(?q?p)=1 右边??p?(p??q)?p?(?p??q)=1

所以 （4）

左边＝右边 左边＝?(p?q)

＝?((p?q)?(q?p)) ??(?p?q)??(?q?p) ?(p??q)?(q??p)

?(p?q)?(p??p)?(?q?q)?(?q??p) ?(p?q)??(p?q)=右边

（5）

左边＝(p?q)?(p?r)

＝(?p?q)?(?p?r) ??p?(q?r) ?p?(q?r)=右边

（6）

左边＝(p?r)?(q?r)

＝(?p?r)?(?q?r) ＝(?p??q)?r

＝?(p?q)?r

?(p?q)?r=右边

（7）

左边＝p?(q?r)＝?p?(?q?r)

右边?(p?q)?r??(p?q)?r??p??q?r

所以 （8）

左边＝右边

左边＝p?(q?r)＝?p?(?q?r) 右边?q?(p?r)??q?(?p?r)

所以

左边＝右边

下面4道题是智力游戏题，解题时可以先把语句翻译成命题公式，再利用其成真赋值进行

求解。

7. 边远村庄的每个人要么总说真话，要么总说谎话。对旅游者的问题，村民要么回答“是”，

要么回答“不”。假定你在这一地区旅游，走到了一个岔路口，一条岔路通向你想去的遗址，另一岔路通向丛林深处。此时恰有一村民站在岔路口，问村民什么样的一个问题就能决定走那条路？

解 问“如果我问你右边的路是否通向遗址，你会说‘是’，对吗？”，如果回答“是”，则右边的路通向遗址，否则左边的路通向遗址，具体分析如下：

（1）被问者总说真话且回答“对”。则右边的路通向遗址。 （2）被问者总说真话且回答“不对”。则左边的路通向遗址。

（3）被问者总说谎话且回答“对”。因为是说谎者，所以实际上他会回答“不是”；又因

为是说谎者，他回答‘不是’，表明右边的路通向遗址。

（4）被问者总说谎话且回答“不对”。因为是说谎者，所以实际上他会回答“是”；又因现在假设用p表示被问的人总说真话， q表示被问的人回答“对”，r表示如果我问右边的路是否通向遗址，回答‘是’，s表示右边的路通向遗址，则根据以上分析我们有如下表所示的真值表。

为是说谎者，他回答‘是’，表明右边的路不通向遗址。

p q r s 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 这里，r和s都不是独立的命题变元，可以看成命题p，q的逻辑表达式，即

r?p?q， s?p?(p?q)

8. 一个探险者被几个吃人者抓住了。有两种吃人者：总是说谎的和永不说谎的。除非

探险者能判断出一位指定的吃人者是说谎者还是说真话者，否则就要被吃人者烤了吃。探险者只被允许问这位吃人者一个问题。

（1）解释为什么问：“你说谎吗？”是不行的。

（2）找一个问题，使探险者可以用来判断该吃人者是说谎者还是说真话者。 解 （1） 略

（2）问“如果我问你是否是说谎者，你会说‘是’，对吗？”，如果回答“是”，则是说谎者，否则不是说谎者。

9. 侦探调查了罪案的四位证人。从证人的话侦探得出的结论是：如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁不可能都说真话；园丁和杂役不可能都在说谎；如果杂役说真话，那么厨师在说谎。侦探能判定这四位证人分别是在说谎还是在说真话吗？解释你的理由。

解 设p：男管家说的是真话；q：厨师说的是真话；r：园丁说的是真话；s：杂役说的是真话。

则有p?q?1，q?r?0，r?s?1，s??q?1。

若p?1，根据p?q?1得q?1，再根据q?r?0得r?0，再根据r?s?1得

s?1，与s??q?1矛盾。 若p?0，根据p?q?1得q?1或q?0。

若p?0，q?1，根据q?r?0得r?0，再根据r?s?1得s?1，与s??q?1矛盾。

若p?0，q?0，根据q?r?0得r?1或r?0。

若p?0，q?0，r?1，根据r?s?1得s?1或s?0，都s??q?1相容。 若p?0，q?0，r?0，根据r?s?1得s?1，与s??q?1相容。

从以上分析可以可以判定男管家和厨师说谎，但不能判断究竟是园丁还是杂役说真话。

10. 四个朋友被认定为非法进入某计算机系统的嫌疑人。他们已对调查员作了陈述.。爱丽丝说“卡诺斯干的”，约翰说“我没干”，卡诺斯说“黛安娜干的”，黛安娜说“卡诺斯说是我干的，他说谎”。

（1）如果调查员知道四个嫌疑人中恰有一人说真话，那么谁非法进入了计算机系统？

说明理由。

（2）如果调查员知道四个嫌疑人中恰有一人说慌，那么谁非法进入了计算机系统？说