离散数学课件18范式

1-6.范式范式就是命题公式形式的规范形式。分为析取范式与合取范式一.定义:1.析取范式公式A如果写成如下形式：

A1∨A2∨...∨An(n≥1)其中每个Ai(i=1,2..n)是合取式，称之为A的析取范式

2.合取范式公式A如果写成如下形式：

A1∧A2∧...∧An(n≥1)

其中每个Ai(i=1,2..n)是析取式，称之为A的合取范式可以看出:在析取范式与合取范式中只含有联结词

,∧,∨,并且

在命题变元之前

例如，PQ

的析取范式与合取范式：

PQ(P∧Q)∨(

P∧

Q)----析取范式

PQ(P∨Q)∧(P∨

Q)----合取范式注:∵P∨P

PP∧P

P∴P是合(析)取式.4.析取范式与合取范式的写法⑴先用相应的公式去掉和。公式E16P

Q

P∨Q

公式E21PQ(P∧Q)∨(

P∧

Q)

公式E20PQ(P

Q)∧(Q

P)

再用E16PQ(P∨Q)∧(P∨

Q)⑵用公式的否定公式或摩根定律将

后移到命题变元之前。

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)

德-摩根定律

(P∨Q)

P∧

Q

(P∧Q)

P∨

Q⑶用分配律、幂等律等公式进行整理，使之成为所要求的形式。

例如求(P

Q)

R的析取范式与合取范式

(P

Q)

R((P∨Q)∧(P∨Q))∨R(P∧Q)∨(P∧Q)∨R------析取范式

(P

Q)

R((P∧Q)∨(P∧Q))∨R((P∨Q)∧(P∨Q))∨R(P∨Q∨R)∧(P∨Q∨R)---合取范式请同学阅读一下17页的例1.14二.主析取范式与主合取范式一个公式的析取范式与合取范式的形式是不唯一的。下面定义形式唯一的主析取范式与主合取范式。㈠主析取范式

1.小项⑴定义：是n个命题变元的合取式，其中每个变元必出现且仅出现一次，称这个合取式为小项。例如，有两个变元的小项：

P∧Q、P∧Q、P∧Q、P∧Q

小项可编码:用1表变元本身,0表变元的否定形式,则m00

P∧Qm01

P∧Q

m10

P∧Qm11

P∧Q(2)小项的性质

m11m10m01

m00PQP∧QP∧QP∧QP∧Q00FFFFFT01FTFFTF10TFFTFF11TTTFFFa).有n个变元，则有2n个小项。

b).每个小项当且仅当其真值指派与编码相同时,其真值为T;其余2n-1组真值指派均使该小项的

真值为F。c).全体小项的析取式为永真式,记为:

∑mi=m0

∨m1∨…∨m2n-1⇔T2.主析取范式定义若一个命题公式的析取范式为A1∨A2∨...∨An,,其中每个Ai(i=1,2..n)都是小项，则称之为该命题公式的主析取范式。3.主析取范式的写法方法Ⅰ：列真值表⑴列出给定公式的真值表。⑵找出真值表中该公式的每个为“T”行的真值指派所对应的小项。⑶用“∨”联结上述小项，即可。i=02n-1例如求PQ和P

Q的主析取范式

PQPQP

QFFTTFTTFTFFFTTTTPQm00∨m01∨m11

(P∧Q)∨(P∧Q)∨(P∧Q)P

Q

m00∨m11(P∧Q)∨(P∧Q)思考题:永真式的主析取范式是什么样？方法Ⅱ：用公式的等价变换⑴先写出给定公式的析取范式A1∨A2∨...∨An

。⑵为使每个Ai都变成小项，对缺少变元的Ai补全变元，比如缺变元R，就用∧联结永真式(R∨

R)形式补R。⑶用分配律等公式加以整理。

PQP∨Q(P∧(Q∨

Q))∨((P∨

P)∧Q)(P∧Q)∨(P∧

Q)∨(P∧Q)∨(

P∧Q)(P∧Q)∨(P∧

Q)∨(P∧Q)㈡主合取范式1.大项⑴定义:是n个命题变元的析取式，其中每个变元必出现且仅出现一次,称之为大项例如，有两个变元的大项及其真值表：

M00M01M10M11PQP∨QP∨QP∨QP∨Q00FF

FTTT01FTT

FTT10TFTTFT11TTTTT

F可看出大项的编码正好与小项相反:

用0表变元本身,1表变元的否定形式M00P∨QM01P∨Q

M10

P∨QM11P∨Q⑵大项的性质

a).有n个变元，则有2n个大项。

b).每个大项当且仅当其真值指派与编码相同时,其真值为F;其余2n-1组真值指派均使该大项的真值为T。

c).全体大项的合取式必为永假式

∑Mi

=M0∧M1∧…∧M2n-1

⇔Fi=02n-12.主合取范式定义

若一个命题公式的合取范式为A1∧A2∧...∧An,,其中每个Ai(i=1,2..n)都是大项，则称之为该命题公式的主合取范式。3.主合取范式的写法方法Ⅰ：列真值表

⑴列出给定公式的真值表。

⑵找出真值表中该公式的每个为“F”行的真值指派所对应的大项。

⑶用“∧”联结上述大项，即可。课堂练习：1.已知A(P,Q,R)的真值表如图：求它的主析取和主合取范式。2.已知A(P,Q,R)的主析取范式中含有下面小项m1,m3,m5,m7求它的主合取范式.PQRA(P,Q,R)FFFTFFTFFTFFFTTTTFFTTFTFTTFTTTTT练习答案：1.A(P,Q,R)的主析取范式:A(P,Q,R)

m000∨m011∨m100∨m110∨m111

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧

R)∨(P∧Q∧R)A(P,Q,R)的主合取范式：A(P,Q,R)

M001∧M010∧M101(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)2.A(P,Q,R)

M0∧M2∧M4∧M6

M000∧M010∧M100∧M110(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

∧(P∨Q∨R)方法Ⅱ：用公式的等价变换⑴先写出给定公式的合取范式

A1∧A2∧...∧An

。⑵为使每个Ai变成大项，对缺少变元的析取式Ai补全变元，比如缺变元R，就用∨联结永假式(R∧

R)形式补R。⑶用分配律等公式加以整理。例如，求(PQ)R的主合取范式(PQ)R(P∨Q)∨R(P∧

Q)∨R(P∨R)∧(

Q∨R)(P∨(Q∧Q)∨R)∧((P∧P)∨

Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧

(P∨

Q∨R)∧(P∨

Q∨R)例1.安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。令L1、L2、L3分别表示语言课排在第一、第二、第三节。

M1、M2、M3分别表示数学课排在第一、第二、第三节。

P1、P2、P3分别表示原理课排在第一、第二、第三节。三位教师都满意的条件是：(L1∨L3)∧(M2∨M3)∧(P1∨P2)为真。将上式写成析取范式(用分配律)得：((L1∧M2)∨(L1∧M3)∨(L3∧M2)∨(L