等价式和蕴涵式精选PPT.ppt

《等价式和蕴涵式精选PPT.ppt》由会员分享，可在线阅读，更多相关《等价式和蕴涵式精选PPT.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、B，C表示任意命题变元：第9页，此课件共80页哦v 表8.10 第10页，此课件共80页哦v除以上基本等价式外，还有一些不是运算律的重要等价式重要等价式，也是在今后常用的。vE20 ABABvE21 ABBAvE22 A B(AB)(BA)vE23 A B(AB)(AB)vE24 ABCA(BC)第11页，此课件共80页哦v说明：v这些等价式是今后作运算和推理的重要依据，它们就象代数中(a+b)2=a2+2ab+b2,(a+b)3=a3+3a2b+3ab2+b3那么重要。如E21就是我们熟悉的原命题与其逆否命题等价。基本等价式的运算律与集合运算满足的运算律相似，它们的对应是：对应，对应，对应（

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

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

8、，且CD。若将A中出现子公式C的某处（未必全部）替换为D后得到的公式记为B，那么AB。v这是明显的。由于C和D等值，因而用D替换C不会改变A的真值，因此B与A等值。v在逻辑运算中用置换规则和在代数中运用那些恒等式是相似的。第16页，此课件共80页哦例8.11求证：Q（PQ）P）是一个重言式。证：原式 Q（PQ）P）Q（PQ）P）Q（PP）（PQ）Q（T（PQ）Q（PQ）（QQ）P TP T所以，Q（PQ）P）是一个重言式。第17页，此课件共80页哦例8.12试证对任意公式A，B，C，(AB)C(AC)(BC)证：(AB)C(AB)C (AB)C(AC)(BC)(AC)(BC)(AC)(BC)故

9、等价公式成立。第18页，此课件共80页哦例例8.13 化简命题公式：（P QR）（P QR）解：原式（QR）P）（QR）P）（QR）（PP）（QR）T（QR）第19页，此课件共80页哦v从例中可看出，一个命题公式的表示形式并不是唯一的，可以有多种不同的表达式，通过等值演算可以寻求出最简单的逻辑表达式。这在数字电路中，当电路的功能明确后，如何寻求简单而又可靠的电子线路，提供了有力的手段。这一点我们在下一节中会看到。第20页，此课件共80页哦823 蕴涵式蕴涵式第21页，此课件共80页哦v我们知道两个公式A，B等价，即A B 当且仅当AB是重言式。而A B(AB)(BA)，从而 AB与BA 都为重

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

11、）前真推后真法：v即由前件A为真若能推得后件也为B真，则A B。因为A真B也一定为真的话，则AB不存在A真B假的情况，从而AB永真。vB）后假推前假法：v即由后件B为假若能推得前件A也为假，则A B。因为B假A也一定为假的话，则AB不存在A真B假的情况，从而AB永真。第25页，此课件共80页哦v例8.14证明：(AB)B Av 证：（用前真推后真法）v假设前件(AB)B为真，则AB为真，B也为真，于是B为假，又AB为真，从而A为假，故A为真，所以(AB)B A。第26页，此课件共80页哦v例8.15对任意公式A，B，C，证明：v ABA(CB)v证：v法一：用后假推前假法v假设后件A(CB)为

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

13、(AB)(AB)v（2）A(BC)B(AC)v（3）A(BC)(AB)(AC)v（4）(AB)(AB)A v3、证明下列逻辑蕴涵式：v （1）AB ABv （2）(AB)A A v （3）AB(AB)A)Bv（4）(AB)C A(BC)v（5）(AB)(AC)(BC)Cv（6）(AB)A(BC)v 4、化简下列各式：v （1）(AB)(AB)(AB)v （2）B(AB)A)v （3）(PQ)(QP)v （4）(QP)(PQ)v （5）(Q(PQ)P)(QP)第29页，此课件共80页哦8 3 命题公式的范式命题公式的范式第30页，此课件共80页哦v在第一节我们介绍了五个联接词，强调它们是基本的重

14、要的，因为它们是自然语言中最常用的。实际上，只有这五个是不够用的，我们还会涉及其它的联接词。第31页，此课件共80页哦831 联结词的扩充与最小联接词集联结词的扩充与最小联接词集v首先我们回过头来分析一下五个基本联接词，我们发现其中的析取“”所表示的“或者”允许两个都为真，即是可兼的，且当A，B都为真时，AB为真。而比如一快餐馆中写到：一套快餐包括“主菜一个，汤或沙拉一份”，此句中的“或”不是可兼的。再来区分一下：“明天上午我或者在教室或者在图书馆”，“明天上午十点我或者在教室或者在图书馆”，前一语句中的“或”是可兼的，可用“”来表示，而后一语句中的“或”是不可兼的，不能用“”来表示。本节我们

15、要引进逻辑电路中涉及的“异或（不可兼或）门”、“与非门”、“或非门”等四个扩充联接词。当然我们只作最少的介绍。第32页，此课件共80页哦v“异或（不可兼或）异或（不可兼或）”，用符号（或）表示，其含义可由下列等价式决定：vPQ(PQ)(PQ)(P Q)(PQ)(PQ)v也就是说当P，Q都为真时PQ为假。v“与非（与非（NAND）词）词”，用记号表示，也称为悉非尔悉非尔（Sheffer）竖，其含义可由下列等价式决定：PQ(PQ)v这说明当P，Q都为真时PQ为假。第33页，此课件共80页哦v“或非（或非（NOR）”，用记号表示，也称为皮尔斯皮尔斯（Peirce）箭头，其含义可由下列等价式决定：v

16、PQ(PQ)v 这说明当P，Q都为假时PQ为真。v“蕴涵否定词蕴涵否定词”，用记号 表示，其含义可由下列等价式决定：v PQ(PQ)第34页，此课件共80页哦v那么到现在为止，我们共介绍了九个联接词，可以证明这九个联接词就够用了，即满足完备性。但从我们本节引进的四个扩充联接词看，它们都能用前边五个基本联接词表示，而由等价式知道，和又能用，来等价表示，同时由德摩根律PQ(PQ)，PQ(PQ)又能将与互相转换，因而，和，都是完备联接词集完备联接词集（complete group of connectives）。我们容易说明与，与是相互独立的，我们称既具有完备性又具有独立性的联接词集为最小最小联接词

17、集。联接词集。第35页，此课件共80页哦v常见的最小联接词集有，。，在研究逻辑系统的演绎和推理时很重要，在程序系统的研究中也经常用，如ifthenelse;，在大规模集成电路中有广泛应用。v注意，等都不是最小联接词集。但，是完备集，等价表示一公式也较简单，因此是常用的联接词集。如布尔代数系统以及下面要介绍的范式，就只用，三个联接词。第36页，此课件共80页哦8.3.2 析取范式和合取范式析取范式和合取范式第37页，此课件共80页哦v我们已经知道，对众多的命题公式，可以依据它们之间的逻辑等价关系进行分类，使相互逻辑等价的公式为一类。那我们想，是否可以在各类公式中分别选出一个公式作为各类的“代表”

18、，而且使它们具有统一的规范形式呢？这就是我们现在要讲的公式的范式或标准形式。第38页，此课件共80页哦v定义定义8.5 命题公式A称为析取范式析取范式（disjunctive normal form），当且仅当它具有型式：A1A2An（n1）v其中A1,A2,An为由命题常元、变元及它们的否定组成的合取式。v如PQ，P(QP)Q都是析取范式。第39页，此课件共80页哦v定义定义8.6 命题公式A称为合取范式合取范式（conjunctive normal form），当且仅当它具有型式：A1 A1A2An（n1）v其中A1,A2,An为由命题常元、变元及它们的否定组成的析取式。v如PQ，P（PQ

19、）（PQQ）都是合取范式。v注：P，P都可以看成特殊的析取范式和合取范式，PQ是析取范式，也可以看成是含有一个析取式的合取范式。第40页，此课件共80页哦v例8.16求P(PQ)的析取范式及合取范式。v 解：P(PQ)P(PQ)vP(PQ)(P)析取范式v(PP)(PQ)vP(PQ)(P)合取范式第41页，此课件共80页哦v 例8.17求(PQ)(PQ)的析取范式和合取范式。v解：(PQ)(PQ)v（(PQ)(PQ)）(PQ)(PQ)v（PQ)(P）(PQ)（PQ)v(PQ)（PQ)合取范式v(PP)（PQ）（PQ)（QQ)v（PQ）（PQ)析取范式第42页，此课件共80页哦v我们看到：任一命

20、题公式都可化为与其等价的析取范式和合取范式。其等价推演的方法步骤是：v第一步，消去公式中的联结词和：v把公式中的PQ化为PQ；v把公式中的PQ化为(PQ)(QP)或(PQ)(PQ)；v第二步，将否定联结词 向内深入，使之只作用于命题变元或命题变元的否定，然后将P化为P；v第三步，利用分配律，将公式进一步化为所需要的范式。第43页，此课件共80页哦v我们已经发现，一公式的析取范式和合取范式可能不是唯一的，例如v另一方面，一公式的合取范式与析取范式又可能是同一的。例如，P既是P(PQ)的合取范式，又是它的析取范式。又如PQ既可称为PQ的析取范式，又可称为它的合取范式。v上述两点不能不说是析取范式和

21、合取范式的缺点，因此，我们需要更加规范公式的范式，这就是下面的主范式。第44页，此课件共80页哦8.3.3 主析取范式与主合取范式主析取范式与主合取范式第45页，此课件共80页哦主析取范式主析取范式v主析取范式与析取范式的区别就在于对析取范式中的合取式有更严格的要求，即要达到都是小项。那么什么是小项，小项又有什么性质呢？第46页，此课件共80页哦v定义定义8.7 在含n个变元的合取式中，若每个变元与其否定二者必出现且仅出现一个，则称此合取式为含n个变元的小项小项。v 如：两个变元P，Q能够组成的小项有：4=22 个v PQ，PQ，PQ，PQv三个变元P，Q，R能够组成的小项有：8=23 个vP

22、QR，PQR，PQR，PQR，PQR，PQR，PQR，PQRv因此，n个变元能够组成的小项有2N个.第47页，此课件共80页哦v我们知道2N随n的增长速率很快，下面讨论一下对小项编码问题。v由于含有n个变元的每个小项都是n项的合取，而每一项或者是变元出现或者是变元否定出现。v我们约定：当变元出现时相应位置记为“1”；当变元否定出现时相应位置记为“0”。这样每个小项就对应一个n位二进制数。那么这个小项的编码就用m带上这个n位二进制数为右下标组成。如PQ的编码为m01，PQR的编码为m101，因此小项与编码是一一对应的，编码为m010的小项为PQR。v再来看看小项的性质，我们从它们的真值表去分析：

23、（表8.12和表8.13分别是两个变元的小项与三个变元的小项真值表）第48页，此课件共80页哦第49页，此课件共80页哦v由上两个小项真值表不难看出，小项具有如下性质：v任两小项均不等价；v每个小项有且仅有一组指派使其真值为真，且恰当指派与小项编码一致时。即其它任何指派都使此小项为假。如小项m101只在指派101时为真，其它指派都是假。v有了对小项的充分讨论，下面我们研究主析取范式的概念、性质与求法。第50页，此课件共80页哦v定义定义8.8 对一析取范式，若其每一个合取式均为小项时，即是主析取范式主析取范式（majordisjunctive normal form）。第51页，此课件共80页

24、哦v我们可以有两种方法求主析取范式：v方法1：真值表法v真值表中使公式A为真的指派所对应的小项组成的析取式即为A的主析取范式。其道理不难从小项的性质得出这样的主析取范式与A等价，因而可作为A的主析取范式。第52页，此课件共80页哦v例例8.18 用真值表求 P Q的主析取范式v解：P Q的真值表为：v 表8.14v因此P Q的主析取范式为m00 m01 m11 （PQ）（PQ）（PQ）v由此我们知道，一个公式的主析取范式是惟一的。第53页，此课件共80页哦v方法2：等价变形法v例例8.19 用等价变形法求 P Q的主析取范式v解：P Q PQ（这是析取范式。现将这范式中的合取式P添加变元Q,合

25、取式Q添加P,即填满变元P、Q,以构成小项）v（P（QQ）（Q（PP）v（PQ）（PQ）（PQ）第54页，此课件共80页哦v由此得出利用等价变形法求公式的主析取范式的方法步骤：v第一步：求出该公式的析取范式；v第二步：除去范式中所有恒假的合取式，即化掉含有互补对的合取式；同时，将合取式中同一变元的多个出现合并为一个；v第三步：对并非每一变元都出现的析取范式中的合取式，利用PPTP(QQ)把未出现的变元（Q）补进来，并用分配律将其展开，最后得到给定公式的主析取范式。第55页，此课件共80页哦v下面我们对应地介绍主合取范式。v主合取范式主合取范式v 主合取范式与合取范式的区别就在于对合取范式中的析

26、取式有更严格的要求，即要达到都是大项。那么什么是大项，大项又有什么性质呢？第56页，此课件共80页哦v定义定义8.9 在含n个变元的析取式中，若每个变元与其否定二者必出现且仅出现一个，则称此析取式为含n个变元的大项大项。v如：两个变元P，Q能够组成的大项有：4=22 个vPQ，PQ，PQ，PQv三个变元P，Q，R能够组成的大项有：8=23 个vPQR，PQR，PQR，PQR，PQR，PQR，PQR，PQRv因此，n个变元能够组成的大项有2N个.v同样，下面讨论一下对大项编码问题。v由于含有n个变元的每个大项都是n项的析取，而每一项或者是变元出现或者是变元否定出现。第57页，此课件共80页哦v我

27、们约定：当变元出现时相应位置记为“0”；当变元否定出现时相应位置记为“1”。这样每个大项就对应一个n位二进制数。那么这个大项的编码就用M带上这个n位二进制数为右下标组成。如PQ的编码为M10，PQR的编码为M010，因此大项与编码是一一对应的，编码为M101的小项为PQR。v再来看看大项的性质，我们也从它们的真值表去分析：（表8.15和表8.16分别是两个变元的大项与三个变元的大项真值表）第58页，此课件共80页哦第59页，此课件共80页哦v由上两个大项真值表不难看出，大项具有如下性质：v任两大项均不等价；v每个大项有且仅有一组指派使其真值为假，且恰当指派与大项编码一致时。即其它任何指派都使此

28、大项为真。如大项M101只在指派101时为假，其它指派都是真。v有了对大项的充分讨论，下面我们研究主合取范式的概念、性质与求法。第60页，此课件共80页哦v定义定义8.10 对一合取范式，若其每一个合取式均为大项时，即是主合取范式主合取范式（conjunctive normal form）。v我们也可以有两种方法求主合取范式：v方法1：真值表法v真值表中使公式A为假的指派所对应的大项组成的合取式即为A的主合取范式。其道理不难从大项的性质得出这样的主合取范式与A等价，因而可作为A的主合取范式。第61页，此课件共80页哦v例例8.20 用真值表求 P Q的主合取范式v解：由表8.14知，P Q的主

29、合取范式为M10 （PQ）v由此我们知道，一个公式的主合取范式也是惟一的。第62页，此课件共80页哦v方法2：等价变形法v例例8.21 求公式(PQ)R的主合取范式。v 解：(PQ)Rv(PR)(QR)v(P(QQ)R)(PP)QR)v(pQR)(PQR)v(PQR)(PQR)v(PQR)(PQR)(PQR)第63页，此课件共80页哦v由此得出利用等价变形法求公式的主合取范式的方法步骤：v第一步：求出该公式的合取范式；v第二步：除去范式中所有恒真的析取式，即化掉含有互补对的析取式；同时，将析取式中同一变元的多个出现合并为一个；v第三步：对并非每一变元都出现的析取范式中的析取式，利用PPFP(Q

30、Q)把未出现的变元（Q）补进来，并用分配律将其展开，最后得到给定公式的主合取范式。v应用主析取范式分析和解决实际问题。第64页，此课件共80页哦v例例8.22某科研所要从3名科研骨干A，B，C中挑选12名出国进修。由于工作需要，选派时要满足以下条件：v（1）若A去，则C同去；v（2）若B去，则C不能去；v（3）若C不去，则A或B可以去。v问所里应如何选派他们？v解：设P：派A去Q：派B去R：派C去v那么需要满足的条件是v(PR)(Q R)(R(PQ)经过变形可得v(PR)(QR)(R(PQ)m001m010m101v（PQR）（PQR）（PQRv因此，选派方案有三种：（a）C去，而A，B都不去

31、；v（b）B去，而A，C都不去；v（c）A，C同去，而B不去。第65页，此课件共80页哦练习练习8.3v*1、把公式(pq)(qp)变换为与之等价的、只含联结词，的公式。v2、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析（合）取范式直接确定使该公式为真和为假的指派：v（1）(PQ)(PQ)v（2）Q(PQ)v（3）P(P(Q(QR)v（4）P(P(QR)v（5）(PQ)PQv（6）(PQ)(PQ)(PQ)v*（7）(PQ)（PQ）v*（8）(PQ)（PQ）v3、某单位要在A、B、C、D四个人中派两个人出差，按下述三个条件有几种派法：？如何派？v（1）若A去，则C和D中要去一

32、人；v（2）若B和C不能都去；v（3）若C去，则D要留下。v 4、A、B、C、D四人做竞赛游戏，其中三人报告情况如下：v A：C第一，B第二；v B：C第二，D第三；v C：A第二，D第四。v 后经核实发现每个人的报告都是至少有一个为真，问实际名次究竟如何？第66页，此课件共80页哦*84命题逻辑在逻辑电路与语命题逻辑在逻辑电路与语句逻辑中的应用句逻辑中的应用第67页，此课件共80页哦 1 简单开关电路的化简简单开关电路的化简例例8.23 化简如图8.1所示的开关电路。v解：该电路结构的公式：v f=(uv)（x(uy)X(uw)(yz)Zu）v 将其等价变形化简之：v fvu（x(uy)X(

33、uw)(yz)Zu）v（x(uy)X(uw)(yz)Zu）vu（v（(xy)（Xw)）第68页，此课件共80页哦 与最简式相对应的开关电路图（图8.2）：v图8.2所示的电路与图8.1所示的电路具有相同的功能，但较前大大简化了。这在实际生产过程中，在自动控制和电路设计中，有着很重要的意义。第69页，此课件共80页哦2 开关电路分析开关电路分析v开关电路分析的任务是：确定电路接通或断开的条件，即确定相应的逻辑公式之值为1或0的条件。v很显然，我们可以得到如下的方法：v电路工作的条件：v 写出给定的开关电路相对应的逻辑命题公式；v 将该表达式化为析取标准式；v 令其某一项取值为1即可。第70页，此

34、课件共80页哦 例例8.24 试决定下图（图8.3）所示的电路工作的条件。v解：该电路的表达式为v f=（Xyz）（uvx）v此为析取范式。令Xyz=1，得v x=0，y=1且z=1；v或令uvx=1，得vu=1，v=1且x=1。v以上结果表明使电路工作时，各开关x、y、z、u、v所应取的开或闭的状态。第71页，此课件共80页哦（2）电路不工作的条件：v 写出给定的开关电路相对应的布尔表达式；v 将该表达式化为合取范式；v 令其某一项取值为0即可。v对于塔型开关电路，可化为1值小项范式（即主析取范式）或0值大项范式（即主合取范式），以分别确定其工作或不工作的条件。第72页，此课件共80页哦3

35、逻辑电路设计逻辑电路设计v例例8.25 一家航空公司，为了保证安全可靠，用计算机复核飞行计划。每台计算机能给出飞行计划正确或者有误的回答。由于计算机也有可能发生故障，因此采用3台计算机同时复核。由所给信息，根据“少数服从多数”的原则作出判断。试将结果用命题公式表示，并加以简化，设计出相应的电路图。第73页，此课件共80页哦第74页，此课件共80页哦4 指令变换指令变换v例例8.26 一位观测者看着在自己面前缓缓移动的纸带上的数字，他必须按照指令把某些数字消除掉。这指令内容如下：v“把能被3除尽，末尾是0，各数字之和大于31的数消除；把不能被3除尽，末尾是0，各数字之和小于31的数消除；把能被3

36、除尽，末尾是0，各数字之和小于31的数消除；再把不能被3除尽，末尾是0，各数字之和大于31的数消除；把能被3除尽，末尾不是0，各数字之和大于31的数消除。”第75页，此课件共80页哦v解：设A表示能被3除尽；v B表示末尾是0；v C表示各数之和大于31的数。v则 f（ABC）（ABC）（ABC）（ABC）（ABC）v （AB）（CC）（ABC）（ABC）（ABC）v （AB）（AB）（ABC）v B（BAC）v B（AC）v故得如下指令：“把末尾是0，或者能被3除尽并且各数字之和大于31的数消除掉。”这样，命题演算能把给出的指令变换成非常简单的易于理解的指令。这是命题演算使电子计算机工作者最

37、感兴趣的地方。第76页，此课件共80页哦5 语句逻辑问题语句逻辑问题v例例8.27（著名的逻辑学家的故事）有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门，为协助你逃脱，今加派两名战士负责解答你所提出的问题。惟可虑者，此两战士中一名天性诚实，一名说谎成性，今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？第77页，此课件共80页哦v解：逻辑学家手指一门问身旁的一名战士说：“这扇门是死亡门，他（指另一名战士）将回答是，对吗？v 当被问战士回答“对”，则逻辑学家开启所指的门从容离去。当

38、被问战士回答“否”，则逻辑学家将开启另一扇门从容离去。v 因为，如果被问战士是诚实战士，他回答“对”，则另一名战士是说谎战士，他回答“是”，那么，这扇门不是死亡门。如果被问战士是诚实战士，他回答“否”，则另一名战士是说谎战士，他回答“不是”，那么，这扇门是死亡门。如果被问战士是说谎战士，可以类似分析。v 设P：被问战士是诚实战士，v Q：被问战士回答是“对”，v R：另一名战士回答是“是”，v S：这扇门是死亡门第78页，此课件共80页哦v练习练习8.4v1牛牛想用两个事实来判断三位工作伙伴的相对薪水。首先他知道如果小影的薪水不是三人中最高的，那么大山的最高。其次他知道如果大山的薪水不是三人中

39、最低的，那么中元的最高。从以上牛牛知道的事实，有可能决定小影、大山和中元的相对薪水吗？如果能，谁的最高，谁的最低？试解释你的推理。第79页，此课件共80页哦v2五个朋友都能进入谈话室。如果知道下面的信息，能决定谁在谈话吗？张元或王津或他们两个都在谈话。袁莫或刘仪在谈话，但没有同时谈话。如果吴天在谈话，那么袁莫也在谈话。刘仪和张元或者两人都在谈话，或者都不谈话。如果王津在谈话，那么吴天和张元也在谈话。解释你的推理。v3四个朋友被认定为非法进入计算机系统的嫌疑犯。他们已对审讯员作了陈述。A说“B干的。”C说“我没干。”B说“D干的。”D说“B说是我干的，他说谎。”v（1）如果审讯员知道四个嫌疑犯中恰有一人说真话，那么谁干的？解释你的 推理。v（2）如果审讯员知道四个嫌疑犯中恰有一人说谎，那么谁干的？解释你的 推理。第80页，此课件共80页哦