论命题逻辑中主范式的求法

韦 宁 

（河北能源职业技术学院， 河北 唐山  063004）

http://s11/middle/43e11075ga3634634beea&690

On logic assign topic analysis of seeking main disjunctive normal form

(Base Department of Hebei Energy Institute of Vocation and Technology Tangshan  Hebei , 063004 , China )

wei ning   wang en-liang

Abstract: seeking the main disjunctive normal form mainly includes the following four methods, the truth table method, the deductive method, the main disjunctive normal form using the truth table method to seek the G, the main conjunctive normal form using the deductive method to seek the G. To support the truth table method, the properties of the minimal form are cited. Besides, it proves the theorem of the main disjunctive normal form of seeking G with the definition of formula equality.

Key words: minimal form; main disjunctive normal form; truth table; deductive method

 

 

摘  要：求主析取范式包括真值表法、推演法以及用真值表法求 G的主析取范式、用推演法求G的主合取范式等四种方法。用极小项的性质给出了真值表求法的证明，用公式相等的定义证明了求 G的主析取范式的定理。

关键词：极小项； 主析取范式；真值表；推演法

  

求命题逻辑的公式的主析取范式具有重要的意义，其主要目的在于讨论公式的标准形式。由公式的主析取范式，不仅可判断两个公式是否相等，而且还可以判断一个公式是否为恒真式或恒假式。我们将求主析取范式的方法分成直接方法和间接方法两类，并独立给出它们分别用真值表法求解时两个定理的证明，从整体上对求主析取范式的方法进行了系统归纳和理论解析。

一、主析取范式概念

1.极小项

为了准确分析主析取范式的求法，这里先简要介绍极小项的概念及性质。

定义：设P₁,P₂,……，Pn是n个原子，一个短语如果恰包含所有这n个原子或其否定，且排列顺序与P₁,P₂,……，Pn的顺序一致，则称此短语为关于P₁,P₂,,……，Pn的一个极小项。

性质：(1)对于n个原子P₁,P₂,……，Pn而言，其所有的极小项共有2ⁿ个。

(2)对于P₁,P₂,……，Pn的任一个极小项m，有且只有一个解释使其取l值。例如对P、Q、R而言极小项 P∧Q∧ R给出解释Ⅰ：( P，Q， R)，视为010=m₂，使其取1值，其他解释都使其取0值。

 2.主析取范式

定义：设公式G中所有不同原子为P₁,P₂,……，Pn，如果G的析取范式G′中的每个短语，都是关于P₁,P₂,……，Pn的一个极小项，则称G′为G的主析取范式。

说明：(1)同理可定义极大项求主合取范式。

      (2)因主析取范式与主合取范式可以根据对偶原则本文定理2,定理5等方法相互求出，所以，只探讨主析取范式的求法。

3．定理1. 对于任何一个公式，其主析取范式皆存在且唯一。

限于篇幅，本文略去其证明。

二、主析取范式的四种求法解析

求一个公式的主析取范式可分为直接求法和间接求法，下面各给出它们中的各两种求法，并进行理论解析。

直接求法类

1.     真值表法

定理2. 对于任意的公式G，可按下述方法求出其主析取范式：

(1)   列出公式的真值表。

(2)   将真值表最后一列G的真值1的左侧的二进制数对应的极小项写出。

(3)   将这些极小项析取起来。

证明:  设按定理2的步骤得出的极小项的析取范式为G′，下面证G= G′即可。不妨设G中包含n个原子P₁,P₂,……，Pn，且由上述方法（2）共得出k个极小项m₀,m₁,……，m_k-1 。(k-1≤n)。又设使这些极小项取值为1的解释，其对应的二进制数转化为十进制数之后为i_0,i_1, ……，i_k-1。依P₁,P₂,……，Pn的顺序取公式G的任一个解释Ⅰ，并将其对应的二进制数转化为十进制数后记为M，则M∈Z₀=｛0，1，……，2ⁿ-1｝=Z₁∪Z₂。其中Z₁=｛i_0,i_1, ……，i_k-1｝，Z₂=Z₀-Z₁  。若M∈Z₀，则其对应的极小项必为m₀,m₁,……，m_k-1中之一。此时由极小项的性质，显见T_I（G）=T_I（G′）=1。

若M∈Z₁ ，则其对应的极小项必不在m₀,m₁,……，m_k-1中，此时由极小项性质，易得T_I（G）=T_I（G′）=0。

于是G= G′，且G′必为G唯一的主析取范式。

特点：利用定理2求公式的主析取范式方法简单，易于理解和掌握，而且可一次既求出其主析取范式，又可求出其主合取范式。但若已知公式层次较多时，增大计算量, 给列真值表带来麻烦。

2.     推演法

定理3.  对于任意公式G，其主析取范式可由下面的推演法求出。设P₁,P₂,……，Pn为公式G的n个原子。

(1)   将公式G 化为任一析取范式G′。

(2)   检查G′中每个短语是否为极小项。如果是，则保留；如果某短语G_i不是关于P₁,P₂,……，Pn的极小项，则G_i中必然缺少某些原子P_i1，……，P_ik，

则G_i=G_i∧1

         = G_i∧（P_i1∨ P_i1）∧……∧（P_ik ∨ P_ik）

                            =m_i1∨……∨m_iS

在上式推演中，反复使用分配律、交换律、结合律、等幂律、互补律、零一律、同一律等算律，如P∧P=P，P∧ P=0，m_i ∨m_i= m_i，最终将短语G_i化成了若干个极小项之析取。

(3)   对于G′中其他非极小项的短语，重复（2）的方法，将其化为若干个极小项的析取式。最后将公式G′运用某些运算律，整理为标准的主析取范式。

特点：当将公式G初步化为析取范式G′后，各短语所缺原子较少，已比较接近主析取范式时，用此法可事半而功倍。若公式中原子较多，各原子关系复杂且包含→、 ，不易化为析取范式；或者化为析取范式后，所缺原子较多，使用推演法将导致困难，并容易产生运算错误;则可不用此法。

间接求法类

3．用真值表法求﹃G的主析取范式

定理4.  已知公式G含有n个原子P₁,P₂,……，Pn，公式G′是按定理2的方法，将G化为了k个极小项之析取得到的G的主析取范式；则将公式G′中未出现的关于P₁,P₂,,……，Pn的极小项全析取起来为公式G〞，那么，G〞即为 G的主析取范式。

证明：即证﹃G= G〞，不妨设m₀,m₁,……，m_k-1为公式G的k个极小项G= G′= m₀∨m₁∨……∨m_k-1，而m_k，……，m₂ⁿ-1是关于原子P₁,P₂,……，Pn的另2ⁿ-k个极小项。又设I为公式G的任一解释，则I亦为公式﹃G的任一解释（因﹃G中同样包含P₁,P₂,……，Pn这n个原子）。

若T_I（G）=1，则解释I必使m₀,m₁,……，m_k-1 某极小项真值为1；同时有T_I（﹃G）=0。由极小项的性质（2）知，此解释I必弄假其他所有极小项，故T_I（G〞）=0。所以T_I（﹃G）= T_I（G〞）

若T_I（G）=0，则解释I不满足m₀,m₁,……，m_k-1中任一者；于是有T_I（﹃G）=1，由极小项性质，I必满足m_k，……，m₂ⁿ-1中某个极小项，故T_I（G〞）=1，所以T_I（﹃G）= T_I（G〞）

综上知，﹃G= G〞。

特点：如若公式﹃G比公式G的形式更为简捷，则先求出﹃G，然后列出﹃G的真值表，将最右列公式﹃G真值中0对应的极小项析取出来，即可得到G的主析取范式。（同时也可得到﹃G的主析取范式。）如若已知﹃G的主析取范式，则可由此定理直接写出G的主析取范式。

定理4^﹟ 若公式G的主合取范式为G﹡，将G﹡中未出现的极大项合取出来即得﹃G的主合取范式。

4．用推演法求G和主合取范式G﹡

定理5.  对于任意公式G，可由下述方法求得其主析取范式：

(1)   用推演法求出公式G的主合取范式G﹡。

(2)   由G﹡，用定理4^﹟求出﹃G的主合取范式G﹡﹡。

(3)   求G的主析取范式G′（使用德·摩根律）G′=﹃（﹃G）=﹃G﹡﹡

此定理道理简明，过程清晰，略去证明。

特点：(1)如若公式G的主合取范式，运用推演法易于求得，则使用定理5，可非常方

便地求出公式G的主析取范式，而且二者可兼得。

          (2)由该定理易见，对于任一公式的主析取范式和主合取范式可相互转换。我们可根据实际问题灵活选择方法，甚至只掌握其一即可。

     

 

参考文献：

1．《离散数学》[M]，耿素云等编著，北京：清华大学出版社，1999年第1版；

2．《离散数学》[M]，刘叙华等编，北京：中央广播电视大学出版社，1998年10月出版；

3．《离散数学导论》[M]，徐洁磐编，北京：高等教育出版社，2004年3版。

 

作者简介：，韦宁，1961年生，男，山东济宁人，河北能源职业技术学院基础部副教授，长期从事数学教学与研究工作。

 

联系电话：韦宁；（ 宅）0315-2326655；（手 ）13131599437；（办 ）3049327

         E—mail :weiningwei@sina.com

 

                         2005-01-12

b本文发表在《河北理工大学学报》2006年4期