离散数学第一章第四节

第1-4讲范式1.对偶式2.对偶原理3.合取范式和析取范式4.主析取范式5.主合取范式6.真值表法求主析(合)取范式7.用等价公式求主析(合)取范式8.主析、合取范式互求9.范式的应用10.作业1、对偶式定义１设命题公式Ａ中仅含有联结词

、∨、∧，将Ａ中∨、∧、Ｔ、Ｆ分别换成∧、∨、Ｆ、Ｔ所得的命题公式A*叫Ａ的对偶式。从根本恒等式中不难发现，多数公式是成对出现，因而互为对偶式。

例１求P↑Q和P↓Q的对偶式解：因为P↑Q

(P∧Q)，故P↑Q的对偶式为

(P∨Q)，即P↓Q。那麽P↑Q和P↓Q互为对偶式。定理１设Ａ(P1,P2，…,Pn)与A*(P1,P2，…,Pn)是对偶式，那么

(1)Ａ(P1,P2，…,Pn)A*(P1,P2，…,Pn)

(2)Ａ(P1,P2，…,Pn)A*(P1,P2，…,Pn)证：由于Ａ仅含连接词、∧、∨,对Ａ取否认，由德．摩根律可知，Ａ中的∨、∧、Ｔ、Ｆ将分别转化为∧、∨、Ｆ、Ｔ，且每一变元都将带上号。所以Ａ(P1,P2，…,Pn)A*(P1,P2，…,Pn)Ａ(P1,P2，…,Pn)A*(P1,P2，…,Pn)例１设A*〔P,Q,R〕是P∧(Q∨R)，证明

A*(P,Q,R)A(P,Q,R)证：因A*〔P,Q,R〕P∧(Q∨R)，代入可得A*(P,Q,R)P∧(Q∨R)。而按对偶式的定义，由A*〔P,Q,R〕可写出Ａ(P,Q,R)P∨(Q∧R)故Ａ(P,Q,R)〔P∨(Q∧R)〕P∧(Q∧R)〔德．摩根律〕P∧(Q∨R)〔德．摩根律〕A*(P,Q,R)

2.对偶原理证：设Ａ(P1,P2，…,Pn)

Ｂ(P1,P2，…,Pn)，按等价定义可知Ａ(P1,P2，…,Pn)

Ｂ(P1,P2，…,Pn)是永真式。那么Ａ(

P1,

P2，…,

Pn)

Ｂ(

P1,

P2，…,

Pn)亦为永真式。所以

Ａ(

P1,

P2，…,

Pn)

Ｂ(

P1,

P2，…,

Pn)。根据定理１中(2)式：Ａ(

P1,

P2，…,

Pn)

A*(P1,P2，…,Pn)，B(

P1,

P2，…,

Pn)

B*(P1,P2，…,Pn)。所以,

A*(P1,P2，…,Pn)

B*(P1,P2，…,Pn)。故A*

B*。定理2(对偶原理)设A*、B*分别是命题公式Ａ、Ｂ的对偶式。如果ＡＢ，那么A*B*。问题１：很多命题公式的外表形式虽不同，但它们是等价的。形式不同的所有等价命题公式是否可以化为唯一的标准形式呢？问题2：如果一个命题公式的成真和成假赋值,能否求出该命题公式?定义1一个命题公式称为合取范式，当且仅当它具有形式：A1∧A2∧…∧An(n≥1)，其中A1、A2、...An都是由命题变元或其否认构成的析取式。3、合取范式和析取范式例如，(P∨

Q∨R)∧(

P∨Q)∧

Q是合取范式。这里，A1是P∨

Q∨R，A2是

P∨Q，A3是

Q。

求析取范式或合取范式的步骤：⑴将命题公式中的联结词全部化为

、∧、∨；⑵利用德．摩根律，将

直接移到各命题变元之前；⑶利用分配律、结合律将命题公式化为析取范式或合取范式。定义2一个命题公式称为析取范式，当且仅当它具有形式：A1∨A2∨...∨An(n≥1)，其中A1、A2、...An都是由命题变元或其否认构成的合取式。

例如，P∨(P∧Q)∨(P∧Q∧R)是析取范式。例４求以下命题的析取范式和合取范式：

Q∧〔(P∨Q)→R〕解：求析取范式：Q∧〔(P∨Q)→R〕Q∧〔(P∨Q)∨R〕〔①消去→〕Q∧〔(P∧Q)∨R〕〔②内移〕〔Q∧(P∧Q)〕∨(Q∧R)〔③用∧对∨的分配律〕(P∧Q)∨(Q∧R)〔④析取范式〕求合取范式〔①,②两个步骤相同〕：Q∧〔(P∨Q)→R〕Q∧〔(P∧Q)∨R〕Q∧〔(P∨R)∧(Q∨R)〕Q∧(P∨R)∧(Q∨R〕任一命题公式都有一个与之等值的析取范式和合取范式。4、主析取范式〔小项〕定义3在ｎ个变元的合取式中，假设每一个变元与其否认不同时存在，但二者之一必须出现且仅出现一次,同时按某种顺序第ｉ个命题变元或其否认出现在左起第ｉ个位置上，那么这种合取式叫小项。例如，三个命题变元Ｐ、Ｑ、Ｒ可形成８个小项：4、主析取范式〔小项的性质〕小项有如下几个性质：⑴每一个小项当其真值指派与编码相同时，其真值为Ｔ，而在其余2n-1种指派下均为Ｆ。⑵任意两个不同小项的合取式永假：ｍi∧ｍj

Ｆ(i≠j)⑶全体小项的析取式永真，记为：定义4给定命题公式Ａ，如果Ａ与命题公式Ｂ等价,且Ｂ仅由小项的析取组成，那么Ｂ称为Ａ的主析取范式。4、主析取范式〔小项性质1、2举例〕对

性质1和

性质2举例如下：

ｍ0：(

P∧

Q∧

R)和ｍ4

：(P∧

Q∧

R)：5、主合取范式(大项)定义3在ｎ个变元的析取式中，假设每一个变元与其否认不同时存在，但二者之一必须出现且仅出现一次,同时按某种顺序第ｉ个命题变元或其否认出现在左起第ｉ个位置上，那么这种析取式叫大项。例如，三个命题变元Ｐ、Ｑ、Ｒ可形成８个大项：5、主合取范式〔大项的性质〕大项有如下几个性质：⑴每一个大项当其真值指派与编码相同时，其真值为F，而在其余2n-1种指派下均为T。⑵任意两个不同大项的析取式永真：Mi∨Mj

T(i≠j)⑶全体大项的合取式永假，记为：定义５给定命题公式Ａ，如果Ａ与命题公式Ｂ等价,且Ｂ仅由大项的合取组成，那么Ｂ称为Ａ的主合取范式。6、真值表法求主析(合)取范式定理３一个命题公式的真值表中，真值为Ｔ〔Ｆ〕的指派所对应的小项〔大项〕的析取〔合取〕即为此公式的主析取范式〔主合取范式〕。证：设给定的命题公式为Ａ，为表达方便，可设使A的真值为T和F的指派所对应的小项分别为m1，m2，...，mk和mK+1，mK+2，...，m2n-1。令Ｂm1∨m2∨...∨mk，下面证明ＡＢ。设A在某一指派下为T，该指派所对应的小项mi必在Ｂ中，因为mi为Ｔ(小项性质)，从而B为T。设A在某一指派下为F，该指派所对应的小项mj必不在Ｂ中，在该指派下m1，m2，...，mk均为Ｆ，故Ｂ为Ｆ。以上说明，A、B在任何指派下同真同假，因此ＡＢ任一命题公式的主析〔合〕取范式一定存在且唯一。6、用真值表法求主析(合)取范式〔例〕例５求Q∧〔(P∨Q)→R〕的主析取范式和主合取范式。解：给定命题公式的真值表为：所以Q∧〔(P∨Q)→R〕的主析取范式为:(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∑2,3,7；主合取范式:(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∏0,1,4,5,67、用等价公式求主析(合)取范式例6求Q∧〔(P∨Q)→R〕的主析取范式。解：Q∧〔(P∨Q)→R〕(P∧Q)∨(Q∧R)(先化为析取范式)(P∧Q∧(R∨R))∨((P∨P)∧Q∧R)(补入未出现的变元)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(展开)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(合并相同的小项)m2∨m3∨m7∑2,3,77、用等价公式求主析(合)取范式〔续〕例7求Q∧〔(P∨Q)→R〕的主合取范式。解：Q∧〔(P∨Q)→R〕Q∧(P∨R)∧(Q∨R)(化为合取范式)((P∧P)∨Q∨(R∧R))∧(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(补入未出现的变元)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)(展开)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)(合并相同的小项)M0∧M1∧M4∧M5∧M6∏0,1,4,5,68、主析、合取范式互求

设命题公式Ａ中含有ｎ个命题变元，且Ａ的主析取范式中含ｋ个极小项ｍi1，ｍi2．．．ｍik，即

A

ｍi1∨ｍi2∨

．．．∨ｍik

那么，

Ａ的主析取范式中必含2n-k个极小项。设它们是ｍj1，ｍj2．．．Ｍj(2n-k)，即

Ａ

ｍj1∨ｍj2∨．．．∨ｍj(2n-k)

注意到

ｍi

Mi，

Mi

mi，所以

A

A

(ｍj1∨ｍj2∨．．．∨ｍj(2n-k))

ｍj1∧

ｍj2∧．．．∧

ｍj(2n-k)，

Mj1∧Mj2∧．．．∧Mj(2n-k)9、范式的应用㈠．判定二命题公式是否等值。ＡＢ当且仅当Ａ与Ｂ有相同的主析〔合〕取范式。㈡．判定命题公式的类型。设Ａ是含有ｎ个变元的命题公式：①Ａ为重言式，当且仅当Ａ的主析取范式中含有2n个小项。此时，主合取范式中不含任何大项，可令主合取范式为T。②Ａ为永假式，当且仅当Ａ的主合取范式中含有2n个大项。此时主析取范式中不含任何小项，可令主析取范式为F。㈢．求命题公式的成真和成假赋值。10、范式的应用〔例〕例７判断以下命题公式的类型及成真赋值和成假赋值：⑴(P→Q)∧Q；⑵(P→Q)∧P→Q；⑶(P→Q)∧Q。解：⑴(P→Q)∧Q(P∨Q)∧QP∧Q∧Q(F)(P∨(Q∧Q))∧(Q∨(P∧P))∧(Q∨(P∧P))(P∨Q)∧(P∨Q)∧(P