H=
=P
Q)
( P
Q))
H ((
P
Q)
(
=
= =M2
(m2)
((m0 m1 m3))
= P为H的主合取式。
Q
一般地,若公式A中含n个命题原子,且A的主析取式中含有k个极小项:mi,...,mi,则
1kA的主析取式中必含有其余
12n?k的2n-k个极小项,不妨设为:mj,...,mjA=mj因此,
A=
A
1,即
?...?mjn2?k。
= (mj1?...?mjn12?k)
2?k =?mj =Mj1?...??mjn2?k
?...?Mjn。
由此可知,从一公式A的主析取式求其主合取式的步骤如下: (1)求出A的主析取式中没有包含的所有极小项。 (2)求出与(1)中极小项下标相同的极大项。
(3)将(2)求出的所有极大项合取起来,即得A的主合取式。
类似地,从一公式A的主合取式求其主析取式的步骤为: (1)求出A的主合取式中没有包含的所有极大项。 (2)求出与(1)中极大项下标相同的极小项。
(3)将(2)求出的所有极小项析取起来,即得A的主析取式。
3. 求主合取式和主析取式的方法
方法一. 真值表法。主析取式恰好是使得公式为真的解释所对应的极小项的析取组成,主合取式恰好是使得公式为假的解释所对应的极大项的合取组成。
方法二. 公式推导法。设命题公式G中所有不同原子为P1,…,Pn,则G的主析取式的求法如下: (a) 将公式G化为析取式。
(b) 删去析取式中所有恒假的短语。
(c) 用等幂律将短语中重复出现的同一文字化简为一次出现,如,PP=P。
(d) 对于所有不是关于P1,…,Pn的极小项的短语使用同一律,补进短语中未出现的所有命题原子,并使用分配律展开,即,如果短语Gi’不是关于P1,…,Pn的极小项,则Gi’中必然缺少原子,不妨设为P j1,…,Pjk,于是
Gi’= Gi’Pjk)
=mi1(Pj1 Pj1)…( Pjk
?...?mik
2这样,就将非极小项Gi’化成了一些极小项之析取。将相同的短语的多次出现化为一次出现,就得到了给定公式的主析取式。
主合取式的求法类似,留给读者作为练习。
由上面讨论可知,只要求出一种式,可立即得到另外一种式。
例2.2.8 求公式G= P→(Q→R)的主析取式与主合取式。 解:(1)使用真值表法。见表2.2.5。 P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 P→(Q→R) 1 1 1 1 1 1 0 1 表2.2.5
根据真值表中使得公式为真的解释,所对应的极小项的析取即为其主析取式:
G= (
P
QP
(
P
Q
R) (P
(P
= m0
R) Q QQ m1
(R)
P R) R) m2
m3
m4
m5
m7
(P
Q
R)
Q
R)
(
根据真值表中使得公式为假的解释,所对应的极大项的合取即为其主合取式:
G=
P
Q
(2)公式推导法
G= P→(Q→R) =
=(
P
Q
R Q) P)
(R
R))
R))
R= M6
P(Q((R
Q(P P Q
(P Q
P)(Q
(R
Q)) P
Q
R)
(
= (P
Q
(
R) (
R) P
R) (P QR) (PQR)