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

82 重言式 等价式和蕴涵式,821 重言式 矛盾式,从上节例8.5中我们看到，虽然公式一般随所含命题变元的真值变化而变化，但也有公式无论变元真值指派是什么它的真值都是真，也有公式无论变元真值指派是什么它的真值都是假，它们是两类特殊的命题公式即重言式（也叫永真式）和矛盾式（也叫永假式），当然更多的是命题公式的真值随变元真值的不同有真有假，我们称它们为可满足式。,定义8.3 对于命题公式A，如果对A中命题变元的一切指派A的真值都为真，则称命题公式A为重言式（tautology），又称永真式；记作T。 如果对A中命题变元的一切指派A的真值都为假，则称命题公式A为矛盾式（contradication），又称永假式。记作F。 如果对A中命题变元的一切指派A的真值有真有假则称A为可满足式（satisfactable formula）。,那么任何一个公式肯定是永真式、永假式和可满足式三种公式中的一个，判定一个公式是这三类公式中的哪一个往往称为公式的判定问题，目前我们可以借助真值表有效判定。 很显然，而当A是永真式（永假式）时， A必为永假式（永真式）。,例8.9 用真值表证明(PQ)PQ为重言式。 证 待证公式的真值表为： 表8.9 由表的最后一列可以看出，原式为重言式。,如果能给一组命题公式中的每一变元一个真值，使各表达式均为真，则这一组命题公式是一致的。在给出系统规范时，必须使这些规范一致。例如：“当且仅当系统正常操作时，系统处于多用户状态。如果系统正常操作，则它的核心程序正在运行。核心程序不能正常运行，或者系统处于中断模式。如果系统不处于多用户状态，它就处于中断模式。系统不处在中断模式”这个系统规范就不一致。,822 等价式,我们再来观察一下例 8.4公式PQ的真值表,它与公式PQ的真值表相同，也就是说，公式PQ与PQ对于P，Q的所有真值指派它们的真值都相同。这时我们称这两个公式等价，即有等价式PQPQ。,定义3.3 对于命题公式A，B中所有变元的任何指派，A和B的真值都相同，则称A等价于B，或逻辑相等。记为A B，又称它为逻辑等价式(logically equivalent)。 注意： （1）符号“”与“”的区别：“”表示两个公式等价，是关系符，而“”是逻辑联接词，任何两个公式都可以用它联接成一个新的公式。 （2）“”与“”还有密切的联系：易证AB当且仅当AB是重言式。 （3）“”是公式间的一个等价关系，满足自反性、对称性和传递性。 首先我们有以下的基本等价式，它们都是以命题定律的形式出现的，故也叫命题定律。其中A，B，C表示任意命题变元：,表8 .10,除以上基本等价式外，还有一些不是运算律的重要等价式，也是在今后常用的。 E20 ABAB E21 ABBA E22 A B (AB)(BA) E23 A B (AB)(AB) E24 ABCA(BC),说明： 这些等价式是今后作运算和推理的重要依据，它们就象代数中(a+b)2=a2+2ab+b2, (a+b)3=a3+3a2b+3ab2+b3那么重要。如E21就是我们熟悉的原命题与其逆否命题等价。基本等价式的运算律与集合运算满足的运算律相似，它们的对应是：对应，对应， 对应（补），T对应E（全集）， F对应（空集），读者可以对应记忆。 当然它们都可以用真值表来验证。 上面所有等价式中的A，B，C是任意的公式也可以，因为对任意的命题变元成立的等价式与变元取值无关，因此把变元换成任意公式也成立。,如：（PQ）（PQ）T； （AB）（AB）F （AB）C （AB）C 因此我们今后要灵活运用这些等价式。 前面已述，我们可以用真值表来判定一个公式是永真式、永假式还是可满足式，也可以用真值表来判断两个公式是否等价。但真值表对公式含有少量变元是可行的，当变元数目增长时，就不可行了。,例如，对于含20个变元的公式，它的真值指派组合有220=1048576组，显然此时需要用一台计算机帮你做这个工作。可当变元有1000个时，一台计算机要检查21000种真值组合的真值在几亿年内都不能完成，而迄今为止尚没有其他已知的计算过程能使计算机在合理可接受的时间内完成，这涉及到算法复杂性问题，也是计算机解决问题最重要最根本的问题。,那么我们还可以用什么方法判定一个公式是哪一种公式，还能用什么方法讨论两个公式等价呢？那就是现在的等价公式。依据等价公式作运算，还有一个重要的置换规则。,定理8.1 置换原理（rule of replacement）设A为一命题公式，C为A的子公式，且CD。若将A中出现子公式C的某处（未必全部）替换为D后得到的公式记为B，那么AB。 这是明显的。由于C和D等值，因而用D替换C不会改变A的真值，因此B与A等值。 在逻辑运算中用置换规则和在代数中运用那些恒等式是相似的。,例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）是一个重言式。,例8.12试证对任意公式A，B，C， (AB)C (AC)(BC) 证： (AB)C(AB)C (AB)C (AC)(BC) (AC) (BC) (AC) (BC) 故等价公式成立。,例8.13 化简命题公式：（P QR）（P QR） 解：原式 （QR ）P）（QR） P） （QR ）（PP） （QR ）T （QR ）,从例中可看出，一个命题公式的表示形式并不是唯一的，可以有多种不同的表达式，通过等值演算可以寻求出最简单的逻辑表达式。这在数字电路中，当电路的功能明确后，如何寻求简单而又可靠的电子线路，提供了有力的手段。这一点我们在下一节中会看到。,823 蕴涵式,我们知道两个公式A，B等价，即A B 当且仅当AB是重言式。而A B (AB)(BA)，从而 AB与BA 都为重言式。如果现在只要求AB一个是重言式，则就是我们下边要研究的另一种公式间的关系-蕴涵。,定义8.5 当命题公式AB为永真式时，称A逻辑蕴涵B，记为A B，又称它为逻辑蕴涵式(logically implication)。 与符号“”与“”的区别类似，同样要注意符号 “” 与“”的区别。 考虑“”还是公式间的一个等价关系吗？ 我们可以很容易得出下面十分重要的逻辑蕴涵式：,表8.11,由定义，要证A B，只要证AB为永真式，进而用真值表或依据置换规则的等价变形都可以。但对蕴涵我们还有两个特殊的方法： 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，证明： ABA(CB) 证： 法一：用后假推前假法 假设后件A(CB)为假，则A为真，CB为假，于是A为假，C为真，B为假，从而AB为假，故ABA(CB)。 法二：依据等价式和置换规则作等价变形（以后简称等价变形法） 因为ABA(CB) （AB）A(CB) ABACBT 故ABA(CB)。 读者还可以用真值表尝试一下。,很明显：逻辑等价式与逻辑蕴涵式有如下关系： 定理8.2 AB当且仅当A B且B A 即说明等价是双向的，蕴涵是单向的。,练习82,1、试判定下列各式是三类公式的那一类： （1）(PQ)(QP) （2）P(PQ) （3）Q(PQ) （4）PQ(PQ) 2、证明下列逻辑等价式： （1）AB (AB)(AB) （2）A(BC) B(AC) （3）A(BC) (AB)(AC) （4）(AB)(AB) A,3、证明下列逻辑蕴涵式： （1）AB AB （2）(AB)A A （3）AB (AB)A)B （4）(AB)C A(BC) （5）(AB)(AC)(BC) C （6）(AB) A(BC) 4、化简下列各式： （1）(AB)(AB)(AB) （2）B(AB)A) （3）(PQ) (QP) （4）(QP) (PQ) （5）(Q(PQ)P)(QP),8 3 命题公式的范式,在第一节我们介绍了五个联接词，强调它们是基本的重要的，因为它们是自然语言中最常用的。实际上，只有这五个是不够用的，我们还会涉及其它的联接词。,831 联结词的扩充与最小联接词集,首先我们回过头来分析一下五个基本联接词，我们发现其中的析取“”所表示的“或者”允许两个都为真，即是可兼的，且当A，B都为真时，AB为真。而比如一快餐馆中写到：一套快餐包括“主菜一个，汤或沙拉一份”，此句中的“或”不是可兼的。再来区分一下：“明天上午我或者在教室或者在图书馆”，“明天上午十点我或者在教室或者在图书馆”，前一语句中的“或”是可兼的，可用“”来表示，而后一语句中的“或”是不可兼的，不能用“”来表示。本节我们要引进逻辑电路中涉及的 “异或（不可兼或）门”、 “与非门”、“或非门”等四个扩充联接词。当然我们只作最少的介绍。,“异或（不可兼或）”，用符号（或 ）表示，其含义可由下列等价式决定： PQ (PQ)(PQ) (P Q) (PQ) (PQ) 也就是说当P，Q都为真时PQ为假。 “与非（NAND）词”，用记号表示，也称为悉非尔（Sheffer）竖，其含义可由下列等价式决定：PQ(PQ) 这说明当P，Q都为真时PQ为假。,“或非（NOR）”，用记号表示，也称为皮尔斯（Peirce）箭头，其含义可由下列等价式决定： PQ(PQ) 这说明当P，Q都为假时PQ为真。 “蕴涵否定词”，用记号 表示，其含义可由下列等价式决定： PQ(PQ),那么到现在为止，我们共介绍了九个联接词，可以证明这九个联接词就够用了，即满足完备性。但从我们本节引进的四个扩充联接词看，它们都能用前边五个基本联接词表示，而由等价式知道，和又能用，来等价表示，同时由德摩根律PQ(PQ)，PQ(PQ)又能将与互相转换，因而，和，都是完备联接词集（complete group of connectives）。我们容易说明与，与是相互独立的，我们称既具有完备性又具有独立性的联接词集为最小联接词集。,常见的最小联接词集有，。，在研究逻辑系统的演绎和推理时很重要，在程序系统的研究中也经常用，如ifthenelse;，在大规模集成电路中有广泛应用。 注意，等都不是最小联接词集。但，是完备集，等价表示一公式也较简单，因此是常用的联接词集。如布尔代数系统以及下面要介绍的范式，就只用，三个联接词。,8.3.2 析取范式和合取范式,我们已经知道，对众多的命题公式，可以依据它们之间的逻辑等价关系进行分类，使相互逻辑等价的公式为一类。那我们想，是否可以在各类公式中分别选出一个公式作为各类的“代表”，而且使它们具有统一的规范形式呢？这就是我们现在要讲的公式的范式或标准形式。,定义8.5 命题公式A称为析取范式（disjunctive normal form），当且仅当它具有型式：A1A2An （n1） 其中A1,A2,An为由命题常元、变元及它们的否定组成的合取式。 如PQ，P(QP)Q都是析取范式。,定义8.6 命题公式A称为合取范式（conjunctive normal form），当且仅当它具有型式：A1 A1A2An （n1） 其中A1,A2,An为由命题常元、变元及它们的否定组成的析取式。 如PQ，P（PQ）（PQQ）都是合取范式。 注：P，P都可以看成特殊的析取范式和合取范式，PQ是析取范式，也可以看成是含有一个析取式的合取范式。,例8.16求P(PQ)的析取范式及合取范式。 解：P(PQ) P(PQ) P(PQ)( P)析取范式 (PP)(PQ) P(P Q)( P)合取范式,例8.17求 (PQ) (PQ)的析取范式和合取范式。 解：(PQ) (PQ) （(PQ) (PQ)）( (PQ)(PQ) （PQ) (P）( (PQ)（PQ) (PQ)（PQ) 合取范式 (PP)（PQ）（PQ) （QQ) （PQ）（PQ) 析取范式,我们看到：任一命题公式都可化为与其等价的析取范式和合取范式。其等价推演的方法步骤是： 第一步，消去公式中的联结词和： 把公式中的PQ化为PQ； 把公式中的PQ化为(PQ)(QP)或(PQ) (PQ)； 第二步，将否定联结词 向内深入，使之只作用于命题变元或命题变元的否定，然后将P化为P； 第三步，利用分配律，将公式进一步化为所需要的范式。,我们已经发现，一公式的析取范式和合取范式可能不是唯一的，例如 另一方面，一公式的合取范式与析取范式又可能是同一的。例如，P既是P(PQ)的合取范式，又是它的析取范式。又如PQ既可称为PQ的析取范式，又可称为它的合取范式。 上述两点不能不说是析取范式和合取范式的缺点，因此，我们需要更加规范公式的范式，这就是下面的主范式。,8.3.3 主析取范式与主合取范式,主析取范式,主析取范式与析取范式的区别就在于对析取范式中的合取式有更严格的要求，即要达到都是小项。那么什么是小项，小项又有什么性质呢？,定义8.7 在含n个变元的合取式中，若每个变元与其否定二者必出现且仅出现一个，则称此合取式为含n个变元的小项。 如：两个变元P，Q能够组成的小项有：4 = 22 个 PQ， PQ，PQ，PQ 三个变元P，Q，R能够组成的小项有：8 = 23 个 PQR，PQR， PQR，PQR，PQR，PQR， PQR，PQR 因此，n个变元能够组成的小项有2N个.,我们知道2N随n的增长速率很快，下面讨论一下对小项编码问题。 由于含有n个变元的每个小项都是n项的合取，而每一项或者是变元出现或者是变元否定出现。 我们约定：当变元出现时相应位置记为“1”；当变元否定出现时相应位置记为“0”。这样每个小项就对应一个n位二进制数。那么这个小项的编码就用m带上这个n位二进制数为右下标组成。如PQ的编码为m01，PQR的编码为m101，因此小项与编码是一一对应的，编码为m010的小项为PQR。 再来看看小项的性质，我们从它们的真值表去分析：（表8 .12 和表8 .13分别是两个变元的小项与三个变元的小项真值表）,由上两个小项真值表不难看出，小项具有如下性质： 任两小项均不等价； 每个小项有且仅有一组指派使其真值为真，且恰当指派与小项编码一致时。即其它任何指派都使此小项为假。如小项m101只在指派101时为真，其它指派都是假。 有了对小项的充分讨论，下面我们研究主析取范式的概念、性质与求法。,定义8.8 对一析取范式，若其每一个合取式均为小项时，即是主析取范式（majordisjunctive normal form）。,我们可以有两种方法求主析取范式： 方法1：真值表法 真值表中使公式A为真的指派所对应的小项组成的析取式即为A的主析取范式。其道理不难从小项的性质得出这样的主析取范式与A等价，因而可作为A的主析取范式。,例8.18 用真值表求 P Q的主析取范式 解：P Q的真值表为： 表8.14 因此P Q的主析取范式为m00 m01 m11 （PQ）（PQ）（PQ） 由此我们知道，一个公式的主析取范式是惟一的。,方法2：等价变形法 例8.19 用等价变形法求 P Q的主析取范式 解：P Q PQ（这是析取范式。现将这范式中的合取式P添加变元Q, 合取式Q添加P, 即填满变元P、Q, 以构成小项） （P（QQ）（Q（PP） （PQ）（PQ）（PQ）,由此得出利用等价变形法求公式的主析取范式的方法步骤： 第一步：求出该公式的析取范式； 第二步：除去范式中所有恒假的合取式，即化掉含有互补对的合取式；同时，将合取式中同一变元的多个出现合并为一个； 第三步：对并非每一变元都出现的析取范式中的合取式，利用PPTP(QQ)把未出现的变元（Q）补进来，并用分配律将其展开，最后得到给定公式的主析取范式。,下面我们对应地介绍主合取范式。 主合取范式 主合取范式与合取范式的区别就在于对合取范式中的析取式有更严格的要求，即要达到都是大项。那么什么是大项，大项又有什么性质呢？,定义8.9 在含n个变元的析取式中，若每个变元与其否定二者必出现且仅出现一个，则称此析取式为含n个变元的大项。 如：两个变元P，Q能够组成的大项有：4 = 22 个 PQ， PQ，PQ，PQ 三个变元P，Q，R能够组成的大项有：8 = 23 个 PQR，PQR， PQR，PQR，PQR，PQR， PQR，PQR 因此，n个变元能够组成的大项有2N个. 同样，下面讨论一下对大项编码问题。 由于含有n个变元的每个大项都是n项的析取，而每一项或者是变元出现或者是变元否定出现。,我们约定：当变元出现时相应位置记为“0”；当变元否定出现时相应位置记为“1”。这样每个大项就对应一个n位二进制数。那么这个大项的编码就用M带上这个n位二进制数为右下标组成。如PQ的编码为M10，PQR的编码为M010，因此大项与编码是一一对应的，编码为M101的小项为PQR。 再来看看大项的性质，我们也从它们的真值表去分析：（表8 .15和表8 .16分别是两个变元的大项与三个变元的大项真值表）,由上两个大项真值表不难看出，大项具有如下性质： 任两大项均不等价； 每个大项有且仅有一组指派使其真值为假，且恰当指派与大项编码一致时。即其它任何指派都使此大项为真。如大项M101只在指派101时为假，其它指派都是真。 有了对大项的充分讨论，下面我们研究主合取范式的概念、性质与求法。,定义8.10 对一合取范式，若其每一个合取式均为大项时，即是主合取范式（conjunctive normal form）。 我们也可以有两种方法求主合取范式： 方法1：真值表法 真值表中使公式A为假的指派所对应的大项组成的合取式即为A的主合取范式。其道理不难从大项的性质得出这样的主合取范式与A等价，因而可作为A的主合取范式。,例8.20 用真值表求 P Q的主合取范式 解：由表8.14知， P Q的主合取范式为 M10 （PQ） 由此我们知道，一个公式的主合取范式也是惟一的。,方法2：等价变形法 例8.21 求公式(PQ)R的主合取范式。 解： (PQ)R (PR)(QR) (P(QQ)R)(PP)QR) (pQR)(PQR) (PQR)(PQR) (PQR)(PQR)(PQR),由此得出利用等价变形法求公式的主合取范式的方法步骤： 第一步：求出该公式的合取范式； 第二步：除去范式中所有恒真的析取式，即化掉含有互补对的析取式；同时，将析取式中同一变元的多个出现合并为一个； 第三步：对并非每一变元都出现的析取范式中的析取式，利用PPFP (QQ)把未出现的变元（Q）补进来，并用分配律将其展开，最后得到给定公式的主合取范式。 应用主析取范式分析和解决实际问题。,例8.22 某科研所要从3名科研骨干A，B，C中挑选12名出国进修。由于工作需要，选派时要满足以下条件： （1） 若A去，则C同去； （2） 若B去，则C不能去； （3） 若C不去，则A或B可以去。 问所里应如何选派他们？ 解：设P：派A去 Q：派B去 R：派C去 那么需要满足的条件是 (PR)(Q R)(R( PQ) 经过变形可得 (PR)(QR)(R( PQ) m001m010m101 （PQR）（PQR ）（PQR 因此，选派方案有三种： （a） C去，而A，B都不去； （b） B去，而A，C都不去； （c） A，C同去，而B不去。,练习8.3,*1、把公式(pq) ( qp)变换为与之等价的、只含联结词 ，的公式。 2、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析（合）取范式直接确定使该公式为真和为假的指派： （1）(PQ)(PQ) （2）Q(PQ) （3）P(P(Q(QR) （4）P(P(QR) （5）(PQ)PQ （6）(PQ) (PQ)(PQ) *（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四人做竞赛游戏，其中三人报告情况如下： A：C第一，B第二； B：C第二，D第三； C：A第二，D第四。 后经核实发现每个人的报告都是至少有一个为真，问实际名次究竟如何？,*84命题逻辑在逻辑电路与语句逻辑中的应用,1 简单开关电路的化简 例8.23 化简如图8.1所示的开关电路。,解：该电路结构的公式： f=(uv) （x(uy) X(uw) (yz) Zu） 将其等价变形化简之： f u（x(uy) X(uw) (yz) Zu）v（x(uy) X(uw) (yz) Zu） u（v（(xy)（Xw)）,与最简式相对应的开关电路图（图8.2）：,图8.2所示的电路与图8.1所示的电路具有相同的功能，但较前大大简化了。这在实际生产过程中，在自动控制和电路设计中，有着很重要的意义。,2 开关电路分析,开关电路分析的任务是：确定电路接通或断开的条件，即确定相应的逻辑公式之值为1或0的条件。 很显然，我们可以得到如下的方法： 电路工作的条件： 写出给定的开关电路相对应的逻辑命题公式； 将该表达式化为析取标准式； 令其某一项取值为1即可。,例8.24 试决定下图（图8.3）所示的电路工作的条件。,解：该电路的表达式为 f=（Xyz）（uvx） 此为析取范式。令Xyz=1，得 x=0，y=1且z=1 ； 或令uvx=1，得 u=1，v=1且x=1。 以上结果表明使电路工作时，各开关x、y、z、u、v所应取的开或闭的状态。,（2）电路不工作的条件：, 写出给定的开关电路相对应的布尔表达式； 将该表达式化为合取范式； 令其某一项取值为0即可。 对于塔型开关电路，可化为1值小项范式（即主析取范式）或0值大项范式（即主合取范式），以分别确定其工作或不工作的条件。,3 逻辑电路设计,例8.25 一家航空公司，为了保证安全可靠，用计算机复核飞行计划。每台计算机能给出飞行计划正确或者有误的回答。由于计算机也有可能发生故障，因此采用3台计算机同时复核。由所给信息，根据“少数服从多数”的原则作出判断。试将结果用命题公式表示，并加以简化，设计出相应的电路图。,4 指令变换,例8.26 一位观测者看着在自己面前缓缓移动的纸带上的数字，他必须按照指令把某些数字消除掉。这指令内容如下： “把能被3除尽，末尾是0，各数字之和大于31的数消除；把不能被3除尽，末尾是0，各数字之和小于31的数消除；把能被3除尽，末尾是0，各数字之和小于31的数消除；再把不能被3除尽，末尾是0，各数字之和大于31的数消除；把能被3除尽，末尾不是0，各数字之和大于31的数消除。”,解：设A表示能被3除尽； B表示末尾是0； C表示各数之和大于31的数。 则