↙️ backlink

• 极小项或极大项
  • 在含有 $n$个命题变元 $P_1,P_2,P_3,\cdots,P_n$的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，并且出现的次序与 $P_1,P_2,P_3,\cdots,P_n$一致，则称此短语或子句为关于 $P_1,P_2,P_3,\cdots,P_n$的一个极小项或极大项. （短语对应极小项，子句对应极大项）
  • 极小项性质
    • 没有两个不同的极小项是等价的
    • 每个极小项只有一组成真赋值，因此可用于给极小项编码
      • 一种极小项组合方式的编码，为使其为真的各命题变元的取值组成的二进制数字，如 $P=1,Q=0$使得极小项 $P\land\neg Q$为真（充分必要的），则该极小项的编码为 $m_\{10\}$（或转化为10进制 $m_2$）
      • 规律：命题变元与1对应，命题变元的否定与0对应
  • 极大项的性质
    • 没有两个不同的极大项是等价的
    • 每个极大项只有一组成假赋值，因此可用于给极大项编码
      • 一种极大项组合方式的编码，为使其为真的各命题变元的取值组成的二进制数字，如 $P=1,Q=0$使得极大项 $\neg P\lor Q$为假（充分必要的），则该极大项的编码为 $M_\{10\}$（或转化为10进制 $M_2$
      • 规律：命题变元与0对应，命题变元的否定与1对应
  • 极小项和极大项的性质
    • $m_i\land m_j=0;\ M_i\lor M_j=1\ (i\not=j)$
    • $m_i=\neg M_i;\ M_i=\neg m_i$
    • $\bigvee_\{i=0\}^\{2^n-1\}m_i=1;\ \bigwedge_\{i=0\}^\{2^n-1\}M_i=0$
• 主析取范式和主合取范式
  • 在给定的析取范式中，若每一个短语都是极小项，且按照编码从小到大的顺序排列，则称该范式为主析取范式（principal disjunctive normal form）
  • 在给定的合取范式中，若每一个子句都是极大项，且按照编码从小到大的顺序排列，则称该范式为主合取范式（principal conjunctive normal form）
  • 如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称该主合取范式为“空”
• 主范式求解定理
  • 求出该公式所对应的析取范式和合取范式
  • 消去重复出现的命题变元，矛盾式或重言式
  • 如果缺少命题变元 $P$，可用如下方式将 $P$补进去
    • $B_i=B_i\land1=B_i\land(\neg P\lor P)=(B_i\land\neg P)\lor(B_i\land P)$;
    • $B_i=B_i\lor0=B_i\lor(\neg P\land P)=(B_i\lor\neg P)\land(B_i\lor P)$.
  • 如果出现重复命题变元，则利用幂等律消去
  • 通过交换律排序
• 主范式求解方法二：真值表技术
• 主范式的相互转化
  • 由真值表技术可知，对于任意命题公式，主析取范式所使用的极小项的编码和主合取范式所使用的极大项编码是“互补”的关系. 从而我们可以根据公式特点先求二者之一，然后直接写出另一个.
• 主范式的应用
  • 如果主析取范式包含所有极小项，则为重言式
  • 如果主合取范式包含所有极大项，则为矛盾式
  • 两公式具有相同主范式，则等价
• 应用例题
  •