3.主合取范式 由n个命题变项P1, …,Pn所组成的公式(基本和) Q1∨Q2∨…∨Qn 其中Qi = Pi或 ![]() 极大项必须含有Q1, …, Qn全部n个文字。 由两个命题变项P1, …, Pn可构成四个极大项: ![]() ![]() ![]() ![]() n个命题变项P1, …, Pn可组成 个极大项。每个极大项也可以Mi来表示, 。每个极大项中Q1, …, Qn全部出现。 ![]() ![]() 同样使用真值表列写公式的方法,以及将合取范式中的析取式填满命题变项的方法都可得到一个公式的唯一的主合取范式。 ![]() 用真值表法将P ![]() 依由P、Q到P ![]() ![]() P ![]() ![]() ![]() = M1∧M2 并简记为∧1,2。这便是P ![]() ![]() 用填满命题变项法, 将已为合取范式的P∧Q化为主合取范式。 P∧Q = (P∨(Q∧ ![]() ![]() = (P∨Q)∧(P∨ ![]() ![]() = ( ![]() ![]() = M1∧M2∧M3 = ∧1;2;3 重言式与矛盾式的主合取范式。 矛盾式无成真赋值,因而矛盾式的主合取范式含2n(n为公式中变项个数)个极大项。而重言式无成假赋值,因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式,它的主合取范式中极大项的个数一定小于2n。 4.极大项的性质 (1) 对一个含有n个变项的公式来说, 所有可能的极大项个数和该公式的解释个数一样多, 都是 。 (2) 每个极大项只在一个解释下为假。 (3) 极大项两两不等值, 而且Mi∨Mj = T (i≠j) 。 (4) 任一含有n个变项的公式, 都可由k个(k≤2n)极大项的合取来表示。或说可将所有的极大项建立一"坐标系"。 恰由2n个极大项的合取构成的公式,必为矛盾式。即 ![]() 若A由k个极大项的合取组成, 那么其余的2n-k 个极大项的合取必是公式 ![]() 5.主析取范式与主合取范式间的转换 以三个变项的情形为例加以说明。 若已知A的主析取范式, 如 A = ∨0,1,4,5,7 = ∧ ![]() = ∧ ![]() ∧5,4,1。 (求补是对 而言的, 如2的补为5, 因为2 + 5 = 7) 若已知A的主合取范式, 如 A = ∧1,4,5 = ∨ ![]() = ∨ ![]() = ∨0,1,4,5,7 从真值表列写公式的主析取范式, 主合取范式时, 除分别从T和F列写外, 在填写合取式和析取式时是取变项还是变项的否定是有区别的, 这就是主合取范式、主析取范式的转换过程要求补的原因。 我们可以问这样的问题,含n个命题变项的所有无穷多的合式公式中,与它们等值的主析取范式(主合取范式)共有多少种不同的情况。n个命题变项共可产生2n个极小项(极大项),因而共可产生 ![]() 种不同的主析取范式(主合取范式),由存在唯一性定理可知,含n个命题变项的所有公式的主析取范式(主合取范式)最多有 ![]() A = B当且仅当A与B有相同的主析取范式(主合取范式)。因而可以这样说,真值表与主析取范式(主合取范式)是描述命题公式标准形式的两种不同的等价形式。 命题等值式就介绍这些, 下面讨论推理式。 |