吉林大学离散数学课后习题答案

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)

联系客服:779662525#qq.com(#替换为@)