|
Chapter 11 标准析取模式的简化 1. 消除多余的析取肢 如果标准析取模式的某个析取肢蕴含该标准析取模式的其他部分【这一点可通过一举检验法加以识别】，则该析取肢可以消去。设标准析取模式为P可以分成两部分Q和R（每一部分都是由原模式P的若干析取肢复合而成的标准析取模式）。由第九章关于蕴含的几个定理的第二个定理，R与P和Q的析取等价，当且仅当Q蕴含R；而P和Q的析取等价于P（通过对等价模式“p∨q”和“p”进行同步替换，可以分别得到P和Q的析取和P），所以R与P等价，当且仅当Q蕴含R。 2. 消除某个析取肢中多余的单字 如果某个析取肢去除某个单字后，仍能蕴含整个模式【这也可以通过一举检验法加以识别】，那么这个单字是可以消除的。设标准析取模式P可以分成两部分Q和R，其中Q是P的某个单一的析取肢，Q除去单字S后的剩余部分是T。如果T蕴含P，那么P与P和T的析取等价，即与Q和R和T的析取等价。而Q和T的析取等价于T（通过对等价模式“p∨q”和“p”进行同步替换，可以分别得到Q和T的析取和T），所以P与T和R的析取等价。 3. 更进一步的简化 如果若干单字的合取蕴含某个标准析取模式，那么这个合取称为该标准析取模式的蕴含肢；如果某个蕴含肢除去任何一个单字后得到的合取不再蕴含该标准析取模式，则这个蕴含肢被称为真蕴含肢（prime implicant）。显然，经过以上两种简化而得到的标准析取模式中的每一个析取肢都是真蕴含肢。但也许除此之外仍存在着其他的真蕴含肢。对于任何包含相否定单字的析取肢，将这两个析取肢中除去这两个相否定的单字之外的单字进行合取，所得结果将是原模式的真蕴含肢。可以证明，用此法可以找出所有不在模式中的真蕴含肢。所有真蕴含肢既然都在手，我们可以形成所有可能与原模式等价但不更长的模式。其中通过等价检验的最短的模式就是最理想的简化模式（可能不至一个）。遗憾的是，随着模式中的字母数的增加，这种简化的工作量也越来越大。目前尚未发现更加简单的、不需要借助于对真蕴含肢的搜集和组合的系统的简化方法。 Exercises 1. Check the equivalence of “ps1∨p1q1∨s1q∨r1ps” and “p1q1∨s1q∨r1ps”. 【答案】 p1s1∨p1q1∨s1q∨r1ps·↔·p1q1∨s1q∨r1ps T1s1∨T1q1∨s1q∨r1Ts·↔·T1q1∨s1q∨r1Ts s1q∨r1s·↔·s1q∨r1s p1s1∨p1q1∨s1q∨r1ps·↔·p1q1∨s1q∨r1ps F1s1∨F1q1∨s1q∨r1Fs·↔·F1q1∨s1q∨r1Fs s1∨q1∨s1q·↔·q1∨s1q
T1∨q1∨T1q·↔·q1∨T1q
q1↔q1 2. Similar for ‘pq1∨p1q∨qr1∨q1r’ and ‘pq1∨qr1∨p1r’ 【答案】 pq1∨p1q∨qr1∨q1r·↔·pq1∨qr1∨p1r Tq1∨T1q∨qr1∨q1r·↔·Tq1∨qr1∨T1r q1∨qr1∨q1r·↔·q1∨qr1
T1∨Tr1∨T1r·↔·T1∨Tr1 Fq1∨F1q∨qr1∨q1r·↔·Fq1∨qr1∨F1r q∨qr1∨q1r·↔·qr1∨r
T∨Tr1∨T1r·↔·Tr1∨r
3. Investigate these schemata for redundant clauses and redundant literals: pq1r1∨p1q∨pr∨qr, pq∨pq1r∨p1q∨r1 【答案】 pq1r1∨p1q∨pr∨qr p1q∨pr∨qr T1F∨TF∨FF F…这说明“pq1r1”不多余。 pq1r1∨pr∨qr FT1r1∨Fr∨Tr r…这说明“p1q”不多余。 pq1r1∨p1q∨qr Tq1T1∨T1q∨qT q…这说明“pr”不多余。 pq1r1∨p1q∨pr pT1T1∨p1T∨pT p1∨p…这说明“qr”多余。 因此原式等价于“pq1r1∨p1q∨pr” pq1r1∨p1q∨pr pF1F1∨p1F∨pF p…这说明“pq1r1”中的“p”不多余。 pq1r1∨p1q∨pr Tq1F1∨T1q∨TF q1…这说明“pq1r1”中的“q1”不多余。 pq1r1∨p1q∨pr r1∨T1F∨Tr r1∨r…这说明“pq1r1”中的“r1”多余。 因此原式等价于“pq1∨p1q∨pr” pq1∨p1q∨pr Fq1∨q∨Fr q…这说明“p1q”中的“p1”不多余。 pq1∨p1q∨pr pT1∨p1∨pr p1∨pr T1∨Tr r…这说明“p1q”中的“q”不多余。 pq1∨p1q∨pr Tq1∨T1q∨r q1∨r…这说明“pr”中的“p”不多余。 pq1∨p1q∨pr pq1∨p1q∨p p∨p1q…这说明“pr”中的“r”不多余。
因此，简化形式为“pq1∨p1q∨pr”。 pq∨pq1r∨p1q1r1 pq1r∨p1q1r1 TT1r∨T1T1r1 F…这说明“pq”不多余。 pq∨p1q1r1 TF∨T1F1T1 F…这说明“pq1r”不多余。 pq∨pq1r FF∨FF1F F…这说明“p1q1r1”不多余。 pq∨pq1r∨p1q1r1 q∨Tq1r∨T1q1r1 q∨q1r…这说明“pq”中的“p”不多余。 pq∨pq1r∨p1q1r1 p∨pT1r∨p1T1r1 p…这说明“pq”中的“q”不多余。 pq∨pq1r∨p1q1r1 Tq∨q1r∨T1q1r1 q∨q1r…这说明“pq1r”中的“p”不多余。 pq∨pq1r∨p1q1r1 pF∨pr∨p1F1r1 pr∨p1r1 Fr∨F1r1 r1…这说明“pq1r”中的“q1”不多余。 pq∨pq1r∨p1q1r1 pq∨pq1∨p1q1T1 pq∨pq1…这说明“pq1r”中的“r”不多余。 pq∨pq1r∨p1q1r1 Fq∨Fq1r∨q1r1 q1r1…这说明“p1q1r1”中的“p1”不多余。 pq∨pq1r∨p1q1r1 pF∨pF1r∨p1r1 pr∨p1r1…这说明“p1q1r1”中的“q1”不多余。 pq∨pq1r∨p1q1r1 pq∨pq1F∨p1q1 pq∨p1q1…这说明“p1q1r1”中的“r1”不多余。 综上，原模式不包含多余的析取肢或单字。 4. Do the same for the six alternational normal schemata obtained in Exercise 1 of Chapter 10. 【答案】 在那里得到的6个标准析取模式是： p1q q∨q1 pp1 pqr∨p1q1r1 pqr∨p1q1r∨pq1r1∨p1qr1 pqr∨p1r1∨q1r1 其中前4个一望而知已经是最简形式了。所以我们只检验最后两个。 pqr∨p1q1r∨pq1r1∨p1qr1 T1T1T∨TT1T1∨T1TT1 F…这表明“pqr”不多余。 pqr∨pq1r1∨p1qr1 FFT∨FF1T1∨F1FT1 F…这表明“p1q1r”不多余。 另外两个析取肢也不多余，因为它们与“p1q1r”在模式中处于对称的地位。 pqr∨p1q1r∨pq1r1∨p1qr1 qr∨T1q1r∨Tq1r1∨T1qr1 qr∨q1r1…这表明“pqr”中的“p”不是多余的。 同样地“pqr”中的“q”和“r”也不是多余的。 pqr∨p1q1r∨pq1r1∨p1qr1 Fqr∨q1r∨Fq1r1∨F1qr1 q1r∨qr1…这表明“p1q1r”中的“p1”不是多余的。 同样地，原模式中所有字母的否定都不是多余的。 pqr∨p1q1r∨pq1r1∨p1qr1 pqT∨p1q1∨pq1T1∨p1qT1 pq∨p1q1…这表明“p1q1r”中的“r”不是多余的。 同样地，原模式中所有字母的肯定式也不是多余的。 综上，这样模式中既没有多余的析取肢，也没有多余的单字。 pqr∨p1r1∨q1r1 用一举检验法可知每一个析取肢都不多余。一举检验法表明“pqr”中的每一个字母都不是多余的（只需要检验一个字母即可）。一举检验法还表明“p1”和“q1”也不是多余的（只需检验其中一个单字即可）。一举检验法也表明“r1”的两次出现也不是多余的（只需检验其中的一次出现即可）。 5. Find shorter equivalents of ‘pq1∨p1q∨qr1∨q1r’ . 【答案】 先找出除去已知的4个真蕴含肢以外的所有真蕴含肢。 “pq1”和“p1q”：存在组相互否定的单字 “pq1”和“qr1”：pr1 “pq1”和“q1r”：不存在相否定的单字 “p1q”和“qr1”：不存在相否定的单字 “p1q”和“q1r”：p1r “qr1”和“q1r”：存在组相互否定的单字。 显然，原式等价于“pq1∨p1q∨qr1∨q1r∨pr1∨p1r” 最短的等价式的析取肢必定产生于原来的四个真蕴含肢和新发现的两个真蕴含肢。 我们看前面的析取肢能否被删除。先看“pq1”能否被删除，方法是看它是否蕴含剩下的5个析取肢。因为“pq1”只在“p”真“q”假的情况下为真，所以只要做一次真值分析就可得出结论。 p1q∨qr1∨q1r∨pr1∨p1r T1F∨Fr1∨F1r∨Tr1∨T1r r∨r1 结论是肯定的。因此原式等价于： p1q∨qr1∨q1r∨pr1∨p1r 再看“p1q”能否被进一步删除。 qr1∨q1r∨pr1∨p1r Tr1∨T1r∨Fr1∨F1r r1∨r 结论是肯定的。因此原式等价于： qr1∨q1r∨pr1∨p1r 再看“qr1”能否被进一步删除。 q1r∨pr1∨p1r T1F∨pF1∨p1F p 结论是否定的。再看“q1r”能否被进一步删除。 qr1∨pr1∨p1r FT1∨pT1∨p1T p1 结论也是否定的。再看“pr1”能否被进一步删除。 qr1∨q1r∨p1r qF1∨q1F∨T1F q 结论也是否定的。再看“p1r”能否被进一步删除。 qr1∨q1r∨pr1 qT1∨q1T∨FT1 q1 结论也是否定的。因此原式等价于“qr1∨q1r∨pr1∨p1r”。这和原式一样长。 现在让我们先考虑能否删除“qr1”。 pq1∨p1q∨q1r∨pr1∨p1r pT1∨p1T∨q1F∨pF1∨p1F p1∨p 结论是肯定的。因此原式等价于： pq1∨p1q∨q1r∨pr1∨p1r 再来看“pq1”能否被进一步删除。 p1q∨q1r∨pr1∨p1r T1F∨F1r∨Tr1∨T1r r∨r1 结论是肯定的。再来看“p1q”能否被进一步删除。 q1r∨pr1∨p1r T1r∨Fr1∨F1r r 结论是否定的。再来看“q1r”能否被进一步删除。 p1q∨pr1∨p1r p1F∨pT1∨p1T p1 结论是否定的。再来看“pr1”能否被进一步删除。 p1q∨q1r∨p1r T1q∨q1F∨T1F F 结论是否定的。再来看“p1r”能否被进一步删除。 p1q∨qr1∨q1r∨pr1∨p1r p1q∨q1r∨pr1 F1q∨q1T∨FT1 q∨q1 结论是肯定的。因此原模式等价于“p1q∨q1r∨pr1”。这个模式中的每个析取肢都无法被删除。 现在让我们先考虑“q1r”能否被删除。 pq1∨p1q∨qr1∨pr1∨p1r pF1∨p1F∨FT1∨pT1∨p1T p∨p1 结论是肯定的。因此原模式等价于： pq1∨p1q∨qr1∨pr1∨p1r 再来看“pq1”能否被进一步删除。 p1q∨qr1∨pr1∨p1r T1F∨Fr1∨Tr1∨T1r r1 结论是否定的。再看“p1q”能否被进一步删除。 pq1∨qr1∨pr1∨p1r FT1∨Tr1∨Fr1∨F1r r1∨r 结论是肯定的。再看“qr1”能否被进一步删除。 pq1∨pr1∨p1r pT1∨pF1∨p1F p 结论是否定的。再看“pr1”能否被进一步删除。 pq1∨qr1∨p1r Tq1∨qF1∨T1F q1∨q 结论是肯定的。再看“p1r”能否被进一步删除。结论是否定的。因此原式等价于“pq1∨qr1∨p1r”，而这个式子中的三个析取肢都不能被删除。 最后结论：比原式更短的模式有两个： p1q∨q1r∨pr1 pq1∨qr1∨p1r 6. Find all implicants of each of the six alternational normal schemata obtained in Exercise 1 of Chapter 10. 【答案】 p1q q∨q1 pp1 pqr∨p1q1r1 pqr∨p1q1r∨pq1r1∨p1qr1 pqr∨p1r1∨q1r1 “p1q”的惟一的真蕴含肢是它本身。“q∨q1”没有真蕴含肢。“pp1”也没有真蕴含肢。其他三个的真蕴含肢就是它们的析取肢，因为任何两个析取肢之间都不正好有一组相否定的单字。 7. Find a shortest alternational normal equivalent of each of the six. 【答案】它们本身就是最短的形式了。第一，它们本身没有多余的析取肢或单字。第二，它们除了本身的析取肢外没有另外的真蕴含肢。 |
|
|
