主析取范式的求法和其应用.docVIP

主析取范式的求法及其应用 杨菲 （天津市河西区职工大学，天津市300203） 摘要：本文综述了求主析取范式的三种主要方法，即推演法、真值表法、构造树法，并从经典例题入手分析了三种方法的应用技巧。 关键词：主析取范式 推演法 真值表法 构造树法 命题公式的主析取范式在数理逻辑学中具有十分重要的意义，其求解的主要目的在于使命题公式规范化，从而有利于判断两个命题公式是否等值，并且还可以判断一个公式是重言式（永真式）还是矛盾式（永假式）。鉴于主析取范式求解的重要意义，本文综述了求主析取范式的方法及各种方法的应用技巧。 1 相关概念 1.1 极小项 为了阐明主析取范式的概念，首先介绍一下极小项的相关理论内容。 定义：个命题变元组成的合取式，该式中要包含所有这个变元或它的否定，则称这个合取式为关于这个命题变元的极小项。 性质：（1）对于个原子而言，其所有的极小项共有个。 (2) 每个小项当其真值指派与编码相同时，其真值为T，在其余种指派情况下均为F。 1.2 主析取范式 定义：对于一个给定的命题公式，若有一个由小项的析取组成的命题公式与其等价，则称该等价式为给定命题公式的主析取范式。 定理1. 对于任何一个命题公式，其主析取范式存在且唯一。（证明略） 2 主析取范式的求法解析 2.1 推演法 对于给定命题公式的主析取范式可由推演法求出，其主要步骤归纳为： (1) 首先将公式化为析取范式。 (2) 除去析取范式中永假的析取项，并将析取式中重复出现的合取项和相同变元合并。 (3) 对于不是小项的合取式，补入没有出现的命题变元，即通过合取添加式，然后应用分配律展开公式。 例1. 求的主析取范式 解 特点：初步将命题公式化为一般析取范式后，各合式公式中缺少一到两个命题变元即该形式已经接近主析取范式时，可以用该法较快得解。但是，如果命题公式中的命题变元较多且关系复杂时，化为析取范式的难度已经很大，或者化为一般析取范式后，各合式公式中缺少的命题变元较多，使用该法会大大增加计算难度，层次较多容易出现错误，因此，此类命题公式不宜用该法求解主析取范式。 2.2 真值表法 对于任意给定的命题公式，均可用真值表法求出其主析取范式： (1)?? 根据数理逻辑运算法则列出给定命题公式的真值表。（注意：运算时要特别注意括号的嵌套，层层运算，避免出现逻辑错误） (2)?? 将列出的真值表中最后一列（即命题公式的真值）为1的对应的极小项写出。 (3)?? 将这些极小项用析取符号连接起来。 例2. 求命题公式的主析取范式和主合取范式。 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 因此所求的主析取范式是 主合取范式是 特点：真值表法求解命题公式的主析取范式具有普遍性，无论多么复杂的命题公式都可以利用该法求其主析取范式，该法易于理解，简单方便，而且可一次求出其主析取范式和主合取范式。但是，如果命题公式的层次较多，尤其是涉及到的命题变元较多时，真值表就会非常的大，计算量也会相应增大，容易出现运算错误。 2.3 构造树法 此法的特点就是所给出的公式容易化成合取范式。如果命题公式含有较多的命题变元，且化简后得到合取范式，其中的每一个析取式中又含有较少的命题变元，这时用推演法或者真值表法，过程就会比较复杂和混乱，容易出现错误，构造树法可以大大简化这种类型的计算。这种构造树方法的核心思想就是利用析取对合取的分配律。下面以一个例题来阐述一下利用构造树法求解主析取范式。 例3．某单位要从张、王、马、牛、杨五名同志中选派一部分人外出培训，但是由于部门工作需要，必须满足以下条件： （1）若张去，王也去。 （2）牛、杨两同志中必有一人去。 （3）王、马两同志中去且仅去一人。 （4）马、牛两同志同去或同不去。 （5）若杨去，则张王同去。 通过数理逻辑中的相关理论，分析该单位如何选派他们出国。 解：令 则五个条件化为命题公式分别为，选派方案即是求的主析取范式。 从构造树上看，黑色代表非中止叶子节点，从其他中止叶子节点到根节点1的路径分别写出：和，化简得原式的主析取范式为。因此有两种方案：张、王、杨去，马、牛不去；马、牛同去，而张、王、杨不去。 特点：运用构造树的方法能非常方便地应用到此类型的实际问题中，不仅能将实际问题符号化便于计算，同时又大大简化了计算过程，克服了容易出错的缺点，使此类型的实际问题游刃而解。 3 结语 本文总结了三种求主析取范式的方法，并给出了三种方法应用的特点，在将来的计算中可以根据实际