离散数学(上)

二、主范式

　　一个公式的范式不是唯一的, 因此使用范式判别几个公式是否相等就比较困难了。另外，人们也期望范式具有唯一性。为此引入主（优）范式的概念。
　　1. 主析取范式
　　对n个命题变项P₁,…,P_n来说, 所组成的公式(基本积)
　　　Q₁∧Q₂∧…∧Q_n
　　其中 Q_i = P_i 或

P_i (i = 1, …, n), 则称Q₁∧…∧Q_n为极小项, 并以m_i表示。
　　极小项必须含有Q₁,…,Q_n全部n个文字。
　　由两个命题变项P₁, P₂可构成四个极小项：

P₁∧

P₂,

P₁∧P₂, P₁∧

P₂和P₁∧P₂。若将P_i与1对应, 而

P_i与0对应, 进而将极小项
　　

P₁∧P₂与00对应, 简记为m₀。
　　

P₁∧P₂与01对应，简记为m₁。
　　P₁∧

P₁与10对应, 简记为m₂。
　　P₁∧P₂与11对应, 简记为m₃。
　　n个命题变项P₁,…,P_n可组成个极小项。每个极小项也可以m_i表示，

。每个极小项中Q₁,…,Q_m全部出现。
　　定义：仅由极小项构成的析取式为主析取范式。
　　定理：任一含有n个命题变项的公式，都有唯一的一个与之等值的恰仅含这n个命题变项的主析取范式。

　　例3: 用真值表法将P

Q化成主析取范式。
　　例4: 用填满命题变项法, 将P→Q的析取范式化成主析取范式。

　　应用主析取范式分析和解决实际问题。
　　例：某科研所要从3名科研骨干A，B，C中挑选1～2名出国进修。由于工作需要，选派时要满足以下条件：
　　（1）若A去，则C同去；
　　（2）若B去，则C不能去；
　　（3）若C不去，则A或B可以去。
　　问所里应如何选派他们？

　　2. 极小项的性质
　　3. 主合取范式
　　定义：仅由极大项构成的合取式为主合取范式。
　　定理：任一含有n个命题变项的公式，都有唯一的一个与之等值的恰仅含这n个命题变项的主合取范式。
　　同样使用真值表列写公式的方法，以及将合取范式中的析取式填满命题变项的方法都可得到一个公式的唯一的主合取范式。

　　例5: 用真值表法将P

Q化成主合取范式。
　　例6: 用填满命题变项法, 将已为合取范式的P∧Q化为主合取范式。

　　4. 极大项的性质
　　5. 主析取范式与主合取范式间的转换