这里我们给出上面定理的证明。 首先证明存在性。设A是任一含n个命题变项的公式。由范式存在定理可知,存在与A等值的析取范式A',即A = A'。若A'的某个简单合取式Ai中既不含命题变项Pj,也不含它的否定式 ![]() Ai = Ai∧T = Ai∧(Pjmi ![]() ![]() 继续这个过程,直到所有的简单合取式都含任意命题变项或它的否定式。 若在演算过程中出现重复出现的命题变项以及极小项和矛盾式时,都应"消去":如用P代替P∧P,mi代替mi∨mi,F代替矛盾式等。最后就将A化成与之等值的主析取范式A"。 下面再证明唯一性。假设某一命题公式A存在两个与之等值的主析取范式B和C,即A = B且A = C,则B = C。由于B和C是不同的主析取范式,不妨设极小项mi只出现在B中而不出现在C中,于是,角标i的二进制表示为B的成真赋值,而为C的成假赋值,这与B = C矛盾,因而B与C必相同。后面的主合取范式的存在唯一性可类似证明。 使用真值表列写公式的方法,以及将析取范式中的合取式填满命题变项的方法,都可得到一个公式的主析取范式。 ![]() 用真值表法将P ![]() 由P, Q到P ![]() ![]() P ![]() ![]() ![]() 并简记为∨0,3。这便是P ![]() 又因为等值公式都有相同的真值表, 从而可知所有等值公式(变项均为n)的主析取范式是相同的,或说一个公式的主析取范式是唯一的。 ![]() 用填满命题变项法, 将P→Q的析取范式化成主析取范式。 P→Q = ![]() 已是P→Q的析取范式。现将这范式中的合取式 ![]() ![]() ![]() ![]() = ( ![]() ![]() ![]() Q = Q∧(P∨ ![]() = (Q∧P)∨(Q∧ ![]() 从而 P→Q = ![]() = ( ![]() ![]() ![]() ![]() = ( ![]() ![]() ![]() = m0∨m1∨m3 = ∨0,1,3 这便是P→Q的主析取范式。当然也可以用真值表法来得到此主析取范式(参见 ![]() 应用主析取范式分析和解决实际问题。 ![]() 某科研所要从3名科研骨干A,B,C中挑选1~2名出国进修。由于工作需要,选派时要满足以下条件: (1) 若A去,则C同去; (2) 若B去,则C不能去; (3) 若C不去,则A或B可以去。 问所里应如何选派他们? 解:设P:派A去 Q:派B去 R:派C去 由已知条件可得公式(P→Q)→P = ![]() ![]() ![]() (P→R)∧(Q→ ![]() ![]() 经过演算可得 (P→R)∧(Q→ ![]() ![]() = m1∨m2∨m5 由于 m1 = ![]() ![]() ![]() ![]() ![]() 可知,选派方案有三种: (a) C去,而A,B都不去; (b) B去,而A,C都不去; (c) A,C同去,而B不去。 2.极小项的性质 (1) 对一个含有n个变项的公式来说, 所有可能的极小项个数和该公式的解释个数一样多, 都是 ![]() (2) 每个极小项只在一个解释下为真。 (3) 极小项两两不等值, 而且mi∧mj = F (i ![]() (4) 任一含有n个变项的公式, 都可由k个(k≤ ![]() 恰由 ![]() ![]() 若A由k个极小项的析取组成, 那么其余的 ![]() ![]() ![]() |