《等价式和蕴涵式》PPT课件.ppt

《《等价式和蕴涵式》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《等价式和蕴涵式》PPT课件.ppt（80页珍藏版）》请在装配图网上搜索。

1、8 2 重言式 等价式和蕴涵式 8 2 1 重言式 矛盾式 从上节例 8.5中我们看到，虽然公式一般随所 含命题变元的真值变化而变化，但也有公式 无论变元真值指派是什么它的真值都是真， 也有公式无论变元真值指派是什么它的真值 都是假，它们是两类特殊的命题公式即重言 式（也叫永真式）和矛盾式（也叫永假式）， 当然更多的是命题公式的真值随变元真值的 不同有真有假，我们称它们为可满足式。 定义 8.3 对于命题公式 A，如果对 A中命题变 元的一切指派 A的真值都为真，则称命题公式 A为 重言式 （ tautology），又称 永真式； 记 作 T。 如果对 A中命题变元的一切指派 A的真值都为 假

2、，则称命题公式 A为 矛盾式 （ contradication） ， 又称 永假式 。记作 F。 如果对 A中命题变元的一切指派 A的真值有真 有假则称 A为 可满足式 （ satisfactable formula）。 那么任何一个公式肯定是永真式、永假式和 可满足式三种公式中的一个，判定一个公式 是这三类公式中的哪一个往往称为公式的判 定问题，目前我们可以借助真值表有效判定。 很显然，而当 A是永真式（永假式）时， A必为永假式（永真式）。 例 8.9 用真值表证明 (P Q) PQ 为重言 式。 证 待证公式的真值表为： 表 8.9 由表的最后一列可以看出，原式为重言式。 如果能给一组命

3、题公式中的每一变元一个真 值，使各表达式均为真，则这一组命题公式 是一致的。在给出系统规范时，必须使这些 规范一致。例如：“当且仅当系统正常操作 时，系统处于多用户状态。如果系统正常操 作，则它的核心程序正在运行。核心程序不 能正常运行，或者系统处于中断模式。如果 系统不处于多用户状态，它就处于中断模式。 系统不处在中断模式”这个系统规范就不一 致。 8 2 2 等价式 我们再来观察一下例 8.4公式 P Q的真值 表 ,它与公式 PQ 的真值表相同，也就是说， 公式 PQ 与 P Q对于 P， Q的所有真值指 派它们的真值都相同。这时我们称这两个公 式等价，即有等价式 PQ P Q。 定义

4、3.3 对于命题公式 A， B中所有变元的任何指派， A和 B的真值都相同，则称 A等价于 B，或 逻辑相等 。 记为 A B，又称它为 逻辑等价式 (logically equivalent)。 注意： （ 1）符号“ ”与“ ”的区别：“ ”表示两 个公式等价，是关系符，而“ ”是逻辑联接词， 任何两个公式都可以用它联接成一个新的公式。 （ 2）“ ”与“ ”还有密切的联系：易证 AB 当且仅当 AB是重言式。 （ 3）“ ”是公式间的一个等价关系，满足自反 性、对称性和传递性。 首先我们有以下的 基本等价式 ，它们都是以命 题定律的形式出现的，故也叫 命题定律 。其中 A， B， C表示

5、任意命题变元： 表 8 .10 除以上基本等价式外，还有一些不是运算律 的 重要等价式 ，也是在今后常用的。 E20 AB A B E21 AB BA E22 A B (AB) (BA) E23 A B (A B) (A B) E24 A BC A(BC) 说明： 这些等价式是今后作运算和推理的重要依据，它们 就象代数中 (a+b)2=a2+2ab+b2, (a+b)3=a3+3a2b+3ab2+b3那么重要。如 E21就是 我们熟悉的原命题与其逆否命题等价。基本等价式 的运算律与集合运算满足的运算律相似，它们的对 应是： 对应 ， 对应 ， 对应 （补）， T对 应 E（全集）， F对应 （

6、空集），读者可以对应记 忆。 当然它们都可以用真值表来验证。 上面所有等价式中的 A， B， C是任意的公式也可以， 因为对任意的命题变元成立的等价式与变元取值无 关，因此把变元换成任意公式也成立。 如：（ P Q） （ P Q） T； （ AB ） （ AB ） F （ AB） C （ A B） C 因此我们今后要灵活运用这些等价式。 前面已述，我们可以用真值表来判定一个公 式是永真式、永假式还是可满足式，也可以 用真值表来判断两个公式是否等价。但真值 表对公式含有少量变元是可行的，当变元数 目增长时，就不可行了。 例如，对于含 20个变元的公式，它的真值指 派组合有 220=1048576

7、组，显然此时需要用 一台计算机帮你做这个工作。可当变元有 1000个时，一台计算机要检查 21000种真值 组合的真值在几亿年内都不能完成，而迄今 为止尚没有其他已知的计算过程能使计算机 在合理可接受的时间内完成，这涉及到算法 复杂性问题，也是计算机解决问题最重要最 根本的问题。 那么我们还可以用什么方法判定一个公式是 哪一种公式，还能用什么方法讨论两个公式 等价呢？那就是现在的等价公式。依据等价 公式作运算，还有一个重要的置换规则。 定理 8.1 置换原理 （ rule of replacement）设 A为一命题公式， C为 A的子公式，且 CD。 若将 A中出现子公式 C的某处（未必全部

8、）替 换为 D后得到的公式记为 B，那么 AB。 这是明显的。由于 C和 D等值，因而用 D替换 C不会改变 A的真值，因此 B与 A等值。 在逻辑运算中用置换规则和在代数中运用那 些恒等式是相似的。 例 8.11求证： Q （ P Q） P）是一个重言式。 证：原式 Q （ （ P Q） P） Q （ P Q） P） Q （ P P） （ P Q） Q （ T （ P Q） Q （ P Q） （ Q Q） P T P T 所以， Q （ P Q） P）是一个重言式。 例 8.12试证对任意公式 A， B， C， (A B)C (AC) (BC) 证： (A B)C (A B) C (A B)

9、 C (A C) (B C) (AC) (B C) (AC) (BC) 故等价公式成立。 例 8.13 化简命题公式：（ P Q R） （ P Q R） 解：原式 （ Q R ） P） （ Q R） P） （ Q R ） （ P P） （ Q R ） T （ Q R ） 从例中可看出，一个命题公式的表示形式并 不是唯一的，可以有多种不同的表达式，通 过等值演算可以寻求出最简单的逻辑表达式。 这在数字电路中，当电路的功能明确后，如 何寻求简单而又可靠的电子线路，提供了有 力的手段。这一点我们在下一节中会看到。 8 2 3 蕴涵式 我们知道两个公式 A， B等价，即 A B 当且 仅当 AB是重言

10、式。而 A B (AB) (BA) ，从而 AB 与 BA 都为重言 式。如果现在只要求 AB 一个是重言式，则 就是我们下边要研究的另一种公式间的关系 - -蕴涵。 定义 8.5 当命题公式 AB 为永真式时，称 A 逻辑蕴涵 B，记为 A B，又称它为 逻辑蕴涵 式 (logically implication)。 与符号“ ”与“ ”的区别类似，同样要 注意符号 “ ” 与“ ”的区别。 考虑“ ”还是公式间的一个等价关系吗？ 我们可以很容易得出下面十分重要的逻辑蕴 涵式： 表 8.11 由定义，要证 A B，只要证 AB 为永真式， 进而用真值表或依据置换规则的等价变形都 可以。但对蕴

11、涵我们还有两个特殊的方法： A）前真推后真法： 即由前件 A为真若能推得后件也为 B真，则 A B。因为 A真 B也一定为真的话，则 AB 不存在 A真 B假的情况，从而 AB 永真。 B）后假推前假法： 即由后件 B为假若能推得前件 A也为假，则 A B。因为 B假 A也一定为假的话，则 AB 不存在 A真 B假的情况，从而 AB 永真。 例 8.14证明： (AB) B A 证：（用前真推后真法） 假设前件 (AB) B为真，则 AB 为真， B也为真，于是 B为假，又 AB 为真，从而 A为假，故 A为真，所以 (AB) B A。 例 8.15对任意公式 A， B， C，证明： A BA

12、(CB) 证： 法一：用后假推前假法 假设后件 A(CB) 为假，则 A为真， CB 为假， 于是 A为假， C为真， B为假，从而 A B为假，故 A BA(CB) 。 法二：依据等价式和置换规则作等价变形（以后简 称等价变形法） 因为 A BA(CB) （ A B） A (C B) A B A C BT 故 A BA(CB) 。 读者还可以用真值表尝试一下。 很明显：逻辑等价式与逻辑蕴涵式有如下关系： 定理 8.2 AB当且仅当 A B且 B A 即说明等价是双向的，蕴涵是单向的。 练习 8 2 1、试判定下列各式是三类公式的那 一类： （ 1） (PQ)(QP) （ 2） P(PQ) （

13、 3） Q (PQ) （ 4） P Q(P Q) 2、证明下列逻辑等价式： （ 1） AB (A B) (A B) （ 2） A(BC) B(AC) （ 3） A(BC) (AB)(AC) （ 4） (A B) (A B) A 3、证明下列逻辑蕴涵式： （ 1） A B AB （ 2） (AB)A A （ 3） AB (AB)A)B （ 4） (A B) C A (B C) （ 5） (A B) (AC) (BC) C （ 6） (A B) A (B C) 4、化简下列各式： （ 1） (A B) (A B) (A B) （ 2） B (A B) A) （ 3） (PQ) (QP) （ 4）

14、(QP) (PQ) （ 5） (Q (PQ)P) (QP) 8 3 命题公式的范式 在第一节我们介绍了五个联接词，强调它们 是基本的重要的，因为它们是自然语言中最 常用的。实际上，只有这五个是不够用的， 我们还会涉及其它的联接词。 8 3 1 联结词的扩充与最小联接词集 首先我们回过头来分析一下五个基本联接词，我们 发现其中的析取“ ”所表示的“或者”允许两个 都为真，即是可兼的，且当 A， B都为真时， A B 为真。而比如一快餐馆中写到：一套快餐包括“主 菜一个，汤或沙拉一份”，此句中的“或”不是可 兼的。再来区分一下：“明天上午我或者在教室或 者在图书馆”，“明天上午十点我或者在教室或者

15、 在图书馆”，前一语句中的“或”是可兼的，可用 “ ”来表示，而后一语句中的“或”是不可兼的， 不能用“ ”来表示。本节我们要引进逻辑电路中 涉及的 “异或（不可兼或）门”、 “与非门”、 “或非门”等四个扩充联接词。当然我们只作最少 的介绍。 “异或（不可兼或） ” ， 用符号（或 ）表示， 其含义可由下列等价式决定： PQ (P Q) (P Q) (P Q) (P Q) (P Q) 也就是说当 P， Q都为真时 PQ为假。 “ 与非（ NAND）词 ”，用记号 表示，也称 为 悉非尔 （ Sheffer）竖，其含义可由下列等 价式决定： PQ(P Q) 这说明当 P， Q都为真时 PQ为假

16、。 “或非（ NOR） ”，用记号 表示，也称为 皮 尔斯 （ Peirce）箭头，其含义可由下列等价 式决定： PQ(P Q) 这说明当 P， Q都为假时 PQ为真。 “蕴涵否定词” ，用记号 表示，其含义可 由下列等价式决定： PQ(PQ) 那么到现在为止，我们共介绍了九个联接词， 可以证明这九个联接词就够用了，即满足完备 性。但从我们本节引进的四个扩充联接词看， 它们都能用前边五个基本联接词表示，而由等 价式知道， 和 又能用 ， ， 来等价表 示，同时由德摩根律 P Q(P Q)， P Q(P Q)又能将 与 互相转换， 因而 ， 和 ， 都是 完备联接词集 （ complete gr

17、oup of connectives）。我们容 易说明 与 ， 与 是相互独立的，我们称 既具有完备性又具有独立性的联接词集为 最小 联接词集。 常见的最小联接词集有 ， ， ， ， ， ， ， 。 ， 在研究逻辑系统 的演绎和推理时很重要，在程序系统的研究 中也经常用，如 ifthenelse; ， 在 大规模集成电路中有广泛应用。 注意， ， ， ， ， ， ， 等都 不是最小联接词集。但 ， ， 是完备集， 等价表示一公式也较简单，因此是常用的联 接词集。如布尔代数系统以及下面要介绍的 范式，就只用 ， ， 三个联接词。 8.3.2 析取范式和合取范式 我们已经知道，对众多的命题公式，可

18、以依 据它们之间的逻辑等价关系进行分类，使相 互逻辑等价的公式为一类。那我们想，是否 可以在各类公式中分别选出一个公式作为各 类的“代表”，而且使它们具有统一的规范 形式呢？这就是我们现在要讲的公式的范式 或标准形式。 定义 8.5 命题公式 A称为 析取范式 （ disjunctive normal form），当且仅当它具 有型式： A1 A2 An （ n1） 其中 A1,A2,An 为由命题常元、变元及它们 的否定组成的合取式。 如 P Q， P (Q P) Q都是析取范 式。 定义 8.6 命题公式 A称为 合取范式 （ conjunctive normal form），当且仅当它具

19、 有型式： A1 A1 A2 An （ n1） 其中 A1,A2,An 为由命题常元、变元及它们 的否定组成的析取式。 如 P Q， P （ P Q） （ P Q Q）都 是合取范式。 注： P， P都可以看成特殊的析取范式和合 取范式， P Q是析取范式，也可以看成是 含有一个析取式的合取范式。 例 8.16求 P(PQ) 的析取范式及合取范 式。 解： P(PQ) P (P Q) P (P Q)( P)析取范式 (P P) (P Q) P (P Q)( P)合取范式 例 8.17求 (P Q) (P Q)的析取范式和合取范 式。 解： (P Q) (P Q) （ (P Q) (P Q)）

20、( (P Q) (P Q) （ P Q) (P） ( (P Q) （ P Q) (P Q) （ P Q) 合取范式 (P P) （ P Q） （ P Q) （ Q Q) （ P Q） （ P Q) 析取范式 我们看到：任一命题公式都可化为与其等价的析取 范式和合取范式。其等价推演的方法步骤是： 第一步，消去公式中的联结词 和 ： 把公式中的 PQ 化为 P Q； 把公式中的 PQ化为 (P Q) (Q P)或 (P Q) (P Q)； 第二步，将否定联结词 向内深入，使之只作用于 命题变元或命题变元的否定，然后将 P化为 P； 第三步，利用分配律，将公式进一步化为所需要的 范式。 我们已经发现

21、，一公式的析取范式和合取范 式可能不是唯一的，例如 另一方面，一公式的合取范式与析取范式又 可能是同一的。例如， P既是 P(PQ) 的 合取范式，又是它的析取范式。又如 P Q 既可称为 PQ 的析取范式，又可称为它的合 取范式。 上述两点不能不说是析取范式和合取范式的 缺点，因此，我们需要更加规范公式的范式， 这就是下面的主范式。 8.3.3 主析取范式与主合取范式 主析取范式 主析取范式与析取范式的区别就在于对析取 范式中的合取式有更严格的要求，即要达到 都是小项。那么什么是小项，小项又有什么 性质呢？ 定义 8.7 在含 n个变元的合取式中，若每个变元与其 否定二者必出现且仅出现一个，

22、则称此合取式为含 n个变元的 小项 。 如：两个变元 P， Q能够组成的小项有： 4 = 22 个 P Q， P Q， P Q， P Q 三个变元 P， Q， R能够组成的小项有： 8 = 23 个 P Q R， P Q R， P Q R， P Q R， P Q R， P Q R， P Q R， P Q R 因此， n个变元能够组成的小项有 2N个 . 我们知道 2N随 n的增长速率很快，下面讨论一下对 小项编码问题。 由于含有 n个变元的每个小项都是 n项的合取，而每 一项或者是变元出现或者是变元否定出现。 我们约定：当变元出现时相应位置记为“ 1”；当变 元否定出现时相应位置记为“ 0”。

23、这样每个小项就 对应一个 n位二进制数。那么这个小项的编码就用 m 带上这个 n位二进制数为右下标组成。如 P Q的 编码为 m01， P Q R的编码为 m101，因此小项 与编码是一一对应的，编码为 m010的小项为 P Q R。 再来看看小项的性质，我们从它们的真值表去分析： （表 8 .12 和表 8 .13分别是两个变元的小项与 三个变元的小项真值表） 由上两个小项真值表不难看出，小项具有如 下性质： 任两小项均不等价； 每个小项有且仅有一组指派使其真值为真， 且恰当指派与小项编码一致时。即其它任何 指派都使此小项为假。如小项 m101只在指派 101时为真，其它指派都是假。 有了对

24、小项的充分讨论，下面我们研究主析 取范式的概念、性质与求法。 定义 8.8 对一析取范式，若其每一个合取式 均为小项时，即是 主析取范式 （ majordisjunctive normal form）。 我们可以有两种方法求主析取范式： 方法 1：真值表法 真值表中使公式 A为真的指派所对应的小项组 成的析取式即为 A的主析取范式。其道理不难 从小项的性质得出这样的主析取范式与 A等价， 因而可作为 A的主析取范式。 例 8.18 用真值表求 P Q 的主析取范式 解： P Q 的真值表为： 表 8.14 因此 P Q 的主析取范式为 m00 m01 m11 （ P Q） （ P Q） （ P

25、 Q） 由此我们知道，一个公式的主析取范式是惟一的。 方法 2：等价变形法 例 8.19 用等价变形法求 P Q 的主析取范式 解： P Q P Q（这是析取范式。现将这 范式中的合取式 P添加变元 Q, 合取式 Q添加 P, 即 填满变元 P、 Q, 以构成小项） （ P （ Q Q） （ Q （ P P） （ P Q） （ P Q） （ P Q） 由此得出利用等价变形法求公式的主析取范式的方 法步骤： 第一步：求出该公式的析取范式； 第二步：除去范式中所有恒假的合取式，即化掉含 有互补对的合取式；同时，将合取式中同一变元的 多个出现合并为一个； 第三步：对并非每一变元都出现的析取范式中的合

26、 取式，利用 PP TP (Q Q)把未出现的变 元（ Q）补进来，并用分配律将其展开，最后得到 给定公式的主析取范式。 下面我们对应地介绍主合取范式。 主合取范式 主合取范式与合取范式的区别就在于对合取 范式中的析取式有更严格的要求，即要达到 都是大项。那么什么是大项，大项又有什么 性质呢？ 定义 8.9 在含 n个变元的析取式中，若每个变元与其 否定二者必出现且仅出现一个，则称此析取式为含 n个变元的 大项 。 如：两个变元 P， Q能够组成的大项有： 4 = 22 个 P Q， P Q， P Q， P Q 三个变元 P， Q， R能够组成的大项有： 8 = 23 个 P Q R， P Q

27、 R， P Q R， P Q R， P Q R， P Q R， P Q R， P Q R 因此， n个变元能够组成的大项有 2N个 . 同样，下面讨论一下对大项编码问题。 由于含有 n个变元的每个大项都是 n项的析取，而每 一项或者是变元出现或者是变元否定出现。 我们约定：当变元出现时相应位置记为“ 0”； 当变元否定出现时相应位置记为“ 1”。这样 每个大项就对应一个 n位二进制数。那么这个 大项的编码就用 M带上这个 n位二进制数为右 下标组成。如 P Q的编码为 M10， P Q R的编码为 M010，因此大项与编码 是一一对应的，编码为 M101的小项为 P Q R。 再来看看大项的性

28、质，我们也从它们的真值 表去分析：（表 8 .15和表 8 .16分别是两个变 元的大项与三个变元的大项真值表） 由上两个大项真值表不难看出，大项具有如 下性质： 任两大项均不等价； 每个大项有且仅有一组指派使其真值为假， 且恰当指派与大项编码一致时。即其它任何 指派都使此大项为真。如大项 M101只在指派 101时为假，其它指派都是真。 有了对大项的充分讨论，下面我们研究主合 取范式的概念、性质与求法。 定义 8.10 对一合取范式，若其每一个合取式 均为大项时，即是 主合取范式 （ conjunctive normal form）。 我们也可以有两种方法求主合取范式： 方法 1：真值表法

29、真值表中使公式 A为假的指派所对应的大项组 成的合取式即为 A的主合取范式。其道理不难 从大项的性质得出这样的主合取范式与 A等价， 因而可作为 A的主合取范式。 例 8.20 用真值表求 P Q 的主合取范式 解：由表 8.14知， P Q 的主合取范式为 M10 （ P Q） 由此我们知道，一个公式的主合取范式也是 惟一的。 方法 2：等价变形法 例 8.21 求公式 (P Q) R的主合取范式。 解： (P Q) R (P R) (Q R) (P (Q Q) R) (P P) Q R) (p Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P

30、Q R) 由此得出利用等价变形法求公式的主合取范式的方 法步骤： 第一步：求出该公式的合取范式； 第二步：除去范式中所有恒真的析取式，即化掉含 有互补对的析取式；同时，将析取式中同一变元的 多个出现合并为一个； 第三步：对并非每一变元都出现的析取范式中的析 取式，利用 PP FP (Q Q)把未出现的变 元（ Q）补进来，并用分配律将其展开，最后得到 给定公式的主合取范式。 应用主析取范式分析和解决实际问题。 例 8.22 某科研所要从 3名科研骨干 A， B， C中挑选 1 2 名出国进修。由于工作需要，选派时要满足以下条件： （ 1） 若 A去，则 C同去； （ 2） 若 B去，则 C不能

31、去； （ 3） 若 C不去，则 A或 B可以去。 问所里应如何选派他们？ 解：设 P：派 A去 Q：派 B去 R：派 C去 那么需要满足的条件是 (PR) (Q R) (R( P Q) 经过变形可得 (PR) (QR) (R( P Q) m001 m010 m101 （ P Q R） （ P Q R ） （ P Q R 因此，选派方案有三种： （ a） C去，而 A， B都不去； （ b） B去，而 A， C都不去； （ c） A， C同去，而 B不去。 练习 8.3 *1、把公式 (pq) ( qp) 变换为与之等价的、只含联结词 ， 的公式。 2、求下列公式的析取范式、合 取范式及主析取范

32、式、主合取范 式，并据主析（合）取范式直接 确定使该公式为真和为假的指派： （ 1） (P Q)(P Q) （ 2） Q (P Q) （ 3） P (P(Q (QR) （ 4） P(P (QR) （ 5） (PQ) PQ （ 6） (PQ) (P Q) (P Q) *（ 7） (PQ) （ PQ） *（ 8） (PQ) （ PQ） 3、某单位要在 A、 B、 C、 D四个 人中派两个人出差，按下述三个 条件有几种派法：？如何派？ （ 1）若 A去，则 C和 D中要去一 人； （ 2） 若 B和 C不能都去； （ 3） 若 C去，则 D要留下。 4、 A、 B、 C、 D四人做竞赛 游戏，其中三

33、人报告情况如下： A： C第一， B第二； B： C第二， D第三； C： A第二， D第四。 后经核实发现每个人的报告都 是至少有一个为真，问实际名次 究竟如何？ * 8 4命题逻辑在逻辑电路与语 句逻辑中的应用 1 简单开关电路的化简 例 8.23 化简如图 8.1所示的开关电路。 解：该电路结构的公式： f=(u v) （ x (u y) X (u w) (y z) Z u） 将其等价变形化简之： f u （ x (u y) X (u w) (y z) Z u） v （ x (u y) X (u w) (y z) Z u） u （ v （ (x y) （ X w)） 与最简式相对应的开关

34、电路图（图 8.2）： 图 8.2所示的电路与图 8.1所示的电路具有相 同的功能，但较前大 大简化了。这在实际 生产过程中，在自动 控制和电路设计中， 有着很重要的意义。 2 开关电路分析 开关电路分析的任务是：确定电路接通或断开的条 件，即确定相应的逻辑公式之值为 1或 0的条件。 很显然，我们可以得到如下的方法： 电路工作的条件： 写出给定的开关电路相对应的逻辑命题公式； 将该表达式化为析取标准式； 令其某一项取值为 1即可。 例 8.24 试决定下图（图 8.3）所示的 电路工作的条件。 解：该电路的表达式为 f=（ X y z） （ u v x） 此为析取范式。令 X y z=1，得

35、 x=0， y=1且 z=1 ； 或令 u v x=1，得 u=1， v=1且 x=1。 以上结果表明使电路工作时， 各开关 x、 y、 z、 u、 v所应取 的开或闭的状态。 （ 2）电路不工作的条件： 写出给定的开关电路相对应的布尔表达式； 将该表达式化为合取范式； 令其某一项取值为 0即可。 对于塔型开关电路，可化为 1值小项范式（即主析 取范式）或 0值大项范式（即主合取范式），以分 别确定其工作或不工作的条件。 3 逻辑电路设计 例 8.25 一家航空公司，为了保证安全可靠， 用计算机复核飞行计划。每台计算机能给出 飞行计划正确或者有误的回答。由于计算机 也有可能发生故障，因此采用

36、3台计算机同时 复核。由所给信息，根据“少数服从多数” 的原则作出判断。试将结果用命题公式表示， 并加以简化，设计出相应的电路图。 4 指令变换 例 8.26 一位观测者看着在自己面前缓缓移动的纸带 上的数字，他必须按照指令把某些数字消除掉。这 指令内容如下： “把能被 3除尽，末尾是 0，各数字之和大于 31的数 消除；把不能被 3除尽，末尾是 0，各数字之和小于 31的数消除；把能被 3除尽，末尾是 0，各数字之和 小于 31的数消除；再把不能被 3除尽，末尾是 0，各 数字之和大于 31的数消除；把能被 3除尽，末尾不 是 0，各数字之和大于 31的数消除。” 解：设 A表示能被 3除尽

37、； B表示末尾是 0； C表示各数之和大于 31的数。 则 f（ A B C） （ A B C） （ A B C） （ A B C） （ A B C） （ A B） （ C C） （ A B C） （ A B C） （ A B C） （ A B） （ A B） （ A B C） B （ B A C） B （ A C） 故得如下指令：“把末尾是 0，或者能被 3除尽并且 各数字之和大于 31的数消除掉。”这样，命题演算 能把给出的指令变换成非常简单的易于理解的指令。 这是命题演算使电子计算机工作者最感兴趣的地方。 5 语句逻辑问题 例 8.27（ 著名的逻辑学家的故事）有一逻辑学家误 入某部落，

38、被拘于牢狱，酋长意欲放行，他对逻辑 学家说：“今有两门，一为自由，一为死亡，你可 任意开启一门，为协助你逃脱，今加派两名战士负 责解答你所提出的问题。惟可虑者，此两战士中一 名天性诚实，一名说谎成性，今后生死由你自己选 择。”逻辑学家沉思片刻，即向一战士发问，然后 开门从容离去。该逻辑学家应如何发问？ 解：逻辑学家手指一门问身旁的一名战士说：“这扇门是死 亡门，他（指另一名战士）将回答是，对吗？ 当被问战士回答“对”，则逻辑学家开启所指的门从容离 去。当被问战士回答“否”，则逻辑学家将开启另一扇门从 容离去。 因为，如果被问战士是诚实战士，他回答“对”，则另一 名战士是说谎战士，他回答“是”，

39、那么，这扇门不是死亡 门。如果被问战士是诚实战士，他回答“否”，则另一名战 士是说谎战士，他回答“不是”，那么，这扇门是死亡门。 如果被问战士是说谎战士，可以类似分析。 设 P：被问战士是诚实战士， Q：被问战士回答是“对”， R：另一名战士回答是“是”， S：这扇门是死亡门 练习 8.4 1牛牛想用两个事实来判断三位工作伙伴的相对 薪水。首先他知道如果小影的薪水不是三人中最高 的，那么大山的最高。其次他知道如果大山的薪水 不是三人中最低的，那么中元的最高。从以上牛牛 知道的事实，有可能决定小影、大山和中元的相对 薪水吗？如果能，谁的最高，谁的最低？试解释你 的推理。 2五个朋友都能进入谈话室。如果知道下面的信 息，能决定谁在谈话吗？张元或王津或他们两个都 在谈话。袁莫或刘仪在谈话，但没有同时谈话。如 果吴天在谈话，那么袁莫也在谈话。刘仪和张元或 者两人都在谈话，或者都不谈话。如果王津在谈话， 那么吴天和张元也在谈话。解释你的推理。 3四个朋友被认定为非法进入计算机系统的嫌疑 犯。他们已对审讯员作了陈述。 A说“ B干的。” C 说“我没干。” B说“ D干的。” D说“ B说是我干 的，他说谎。” （ 1）如果审讯员知道四个嫌疑犯中恰有一人说真 话，那么谁干的？解释你的 推理。 （ 2）如果审讯员知道四个嫌疑犯中恰有一人说谎， 那么谁干的？解释你的 推理。