第二章析取范式与合取范式讲解学习

第二章析取范式与合取范式范式的定义由有限个简单合取式构成的析取式称为析取范式。由有限个简单析取式构成的合取式称为合取范式。析取范式与合取范式统称为范式。设Ai(i=1,2,…,s)为简单合取式,则析取范式的形式:A=A1∨A2∨…∨As

例如A=(p∧┐q)∨(┐q∧┐r)∨p设Ai(i=1,2,…,s)为简单析取式,则合取范式的形式:A=A1∧A2∧…∧As

例如A=(p∨q∨r)∧(┐p∨┐q)∧r

思考：┐p∧q∧r与p∨┐q∨r属于什么范式？定理2.2一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。定理2.3（范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。研究范式的目的是将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。思考：怎样将公式转化为范式？例2.7求下面公式的析取范式与合取范式：

(p→q)

r

先求合取范式

(p→q)

r

(┐p∨q)

r

（消去→）

((┐p∨q)→r)∧(r→(┐p∨q))

（消去

）

(┐(┐p∨q)∨r)∧(┐r∨┐p∨q)

（消去→）

((p∧┐q)∨r)∧(┐p∨q∨┐r)

（否定号内移）

(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)（∨对∧分配律）

将公式转化为范式的步骤消除联结词

，

A→B

┐A∨B

A

B(A

B)∧(B

A)

(┐A∨B)∧(A∨┐B缩小┐的作用范围┐┐A

A

┐(A∧B)

┐A∨┐B

┐(A∨B)

┐A∧┐B利用分配率，转化为析取（合取）范式

A∧(B∨C)

(A∧B)∨(A∧C)

A∨(B∧C)

(A∨B)∧(A∨C)例2.7求下面公式的析取范式与合取范式：

(p→q)

r

求析取范式

(p→q)

r

(┐p∨q)

r

（消去→）

((┐p∨q)→r)∧(r→(┐p∨q))

（消去

）

(┐(┐p∨q)∨r)∧(┐r∨┐p∨q)

（消去→）

((p∧┐q)∨r)∧(┐p∨q∨┐r)

（否定号内移）

(p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r）∨(r∧┐p)∨(r∧q)∨(r∧┐r)

（∨对∧分配律）

极小项与极大项的定义极小项：在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式为极小项。例：p∧r∧q;p∧┐p∧r;p∧┐q∧p;p∧q∧r;p∧┐q∧r;┐p∧┐q∧┐r思考:(1)n个命题变项共可产生多少个不同的极小项?(2)每个极小项有多少个成真赋值?2n一个规定:成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi极小项与极大项的定义极大项：在含有n个命题变项的简单析取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单析取式为极大项。例：p∨r∨q;p∨┐p∨r;p∨┐q∨p;p∨q∨r;p∨┐q∨r;┐p∨┐q∨┐r思考:(1)n个命题变项共可产生多少个不同的极大项?(2)每个极大项有多少个成假赋值?2n一个规定:成假赋值所对应的二进制数转换为十进制数i，就将所对应极大项记作Mi极小项解释记法极大项解释记法

p

q

r000m0p

q

r000M0

p

q

r001m1p

q

r001M1

p

q

r010m2p

q

r010M2

p

q

r011m3p

q

r011M3p

q

r100m4

p

q

r100M4p

q

r101m5

p

q

r101M5p

q

r110m6

p

q

r110M6p

q

r111m7

p

q

r111M7p,q,r形成的极小项与极大项定理2.4设mi与Mi是命题变项p1,p2,……,pn形成的极小项和极大项，则┐mi

Mi，┐Mi

mi

主析取范式(主合取范式)设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。设由n个命题变项构成的合取范式中所有的简单析取式都是极大项，则称该合取范式主合取范式。例如：(p→q)

r例如：(p→q)

r定理2.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的。如何求主析取范式（主合取范式）？首先求等价的析取范式（合取范式）然后对非极小项（或者非极大项）进行扩展。AA∨(P∧┐P)（A∨P）∧（A∨┐P）AA∧(P∨┐P)（A∧P）∨（A∧┐P）最后，求出某公式的主析取范式（主合取范式）后，将极小项（极大项）都用名称写出，并且按极小项（极大项）名称的角标由小到大顺序排列。求A=(r

p)

(q

(p

r))的主析取范式例1：解：AA∧(P∨┐P)（A∧P）∨（A∧┐P）结论:公式的所有成真赋值对应主析取范式的所有极小项.结论:公式的所有成假赋值对应主合取范式的所有极大项.例2：求A=(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)m4∨m1∨m3∨m7求A=(p→q)

r的主合取范式(p→q)

r(p∨q∨r)∧(p∨┐q∨r)∧(┐p∨┐q∨r)∧(┐p∨q∨┐r)M0M2M6M5如何求一个公式的主析取范式？（1）利用等值转化法（2）利用真值表（3）通过主合取范式求逆例3：求命题公式p→q的主析取范式和主合取范式。方法1：真值表法pqp→q001011100111p→qm0

m1

m4(p

q)(p

q)(p

q)方法2：公式法p→qp

q[

p

(q

q)]

[q

(p

p)](

p

q)

(

p

q)

(p

q)M2

p

qm0

m1

m4练习:求(

p→q)(qr)的主析取范式公式法：(

p→q)(qr)(pq)(qr)(pqr)(qr)(pqr)(qrp)(qrp)(pqr)(pqr)m3m7练习:求(

p→q)(qr)的主析取范式真值表法：pqr

p

p→qqr(

p→q)(qr)00010000011000010110001111111000100101010011001001110111(

p→q)(qr)m3m7练习:求(

p→q)(qr)的主析取范式求合取范式：因此主析取范式为：m3m7历史遗留问题:我只给村里所有那些不给自己理发的人理发只要别人有困难,他就帮忙,除非困难解决.a:别人有困难,b:他帮忙ab作业Ｐ385题（1、3）注意总结规律6题（2)作业问题:

整体较好,都交了.个别书写不认真,应付私事。注意“”的书写P1414题(10)除非天下大雨，否则他不乘车上班。p:天下大雨q:他乘车上班

q→

p2和4是素数，这是不对的。p:2是素数q:4是素数

(p

q)P384题(4)(pq)(pq)(pq)(pq)(pq)(pq)[(pq)p][(pq)q](pp)(qp)(pq)(qq)(qp)(pq)(pq)(pq)主析取范式的用途

求公式的成真与成假赋值

判断公式的类型

判断两个命题公式是否等值

应用主析取范式分析和解决实际问题例1:求(

p→q)→(

q∨p)的成真赋值Am1∨m2∨…∨ms(

p→q)→(

q

p)

(p

q)

(

q

p)(p

q)

(

q

p)(p

q)(p

q)(p

q)m0

m2

m3即成真赋值为：00,10，11pq

p

p→q

q

q

p(

p→q)→(

q

p)0010111011100010011111101011Am1∨m2∨…∨ms(1)A为重言式当且仅当其主析取范式包含2n个极小项(2)A为矛盾式当且仅当其主析取范式包不含极小项(3)A为可满足式当且仅当其主析取范式包至少含一个极小项例2：判断下列公式的类型p→(p

q)

p

(p

q)(

p

q)

(

p

q)

(p

q)

(p

q)

(p

q)

(

p

q)m1

m0

m3

m2重言式(2)(p

q)→r(

p

q)r

(

p

qr)

(

p

qr)

(p

qr)

(

p

qr)(p

qr)

(

p

qr)m1

m0

m7

m3

m5pqrp

q(p

q)→r0000100101010100111110010101111101011111若公式A、B含有相同的命题变项，A与B等值的充要条件是它们有相同的主析取范式。例：问(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)m5

m4

m7

m3

m1p→(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)m3

m1

m2

m0

m5

m4

m7M6例:某科研所要从3名科研骨干A、B、C中挑选1~2名出国进修，由于工作需要，选派时要满足以下条件：（1）若A去，则B同去；（2）若B去，则C不能去；（3）若C不去，则A或B可以去。问所里有哪些选派方案？解：设p:A去;q:B去;r:C去则选派方案应满足：(p→r)(q→

r)(r→(p

q))(p→r)(q→

r)(r→(p

q))(p

r)(q

r)(r

p

q)(pqr)(pqr)(pqr)(pqr)(p

qr)M4M6M3M7M0m1m2m5因此,选派方案为（001，010，110）§2.3联结词的完备集

n元真值函数的定义

自变量：n个命题变项定义域：由0，1组成的长度为n的符号串全体。（2n）值域：{0，1}思考：n个命题变项可构成多少个不同的真值函数？（22n）每个真值函数对应唯一一个主析取范式（主合取范式）每个真值函数对应无穷多个与之等值的命题公式每个命题公式对应唯一一个真值函数联结词完备设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理2.6S={┐,∧,∨}是联结词完备集证：因为任何n(n≥1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词┐,∧,∨，所以S={┐,∧,∨}是联结词完备集。

推论以下联结词集都是完备集：

(1)S1={┐,∧,∨,→}

(2)S2={┐,∧,∨,→,

}

(3)S3={┐,∧}

(4)S4={┐,∨}

(5)S5={┐,→}

p∨q┐┐(p∨q)┐(┐p∧┐q)

与非联结词根据需要，人们还可构造形式上更为简单的联结词完备集。例如，在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集。设p、q为两个命题，复合命题“p与q的否定式”称作p,q的与非式记作p↑q。即p↑q┐(p∧q）,符号↑称作与非联结词。p↓q表示或非式，即p↓q┐(p∨q）定理2.7{↑}，{↓}都是联结词完备集小结主要内容：等值式基本的等值式主析取范式与主合取范式联结词完备要求熟练掌握等值演算熟练掌握公式主析取范式（主合取范式）的求法会用主析取范式解决一些问题会将公式化为联结词完备集中的公式一、下列说法正确的是:

AB当且仅当A

B是可满足式AB当且仅当A和B有相同的主析取范式若A为重言式,则A的主析取范式含有个2n极小项若A为矛盾式,则A的主析取范式为1若A为矛盾式,则A的主合取范式为1任何公式A都能等值的化为联结词{∧,∨}中的公式任何公式A都能等值的化为联结词集合{→,┐,∧}中的公式二、用等值演算法来判断下列公式的类型

(p→q)∧r∧q(p∧

q)∧r∧qp∧0∧r0所有,该公式为矛盾式三、用主析取范式法来判断下列公式的类型,并求其成真赋值(p→q)→(

p→

q)(

p

q)(p

q)(pq)p

q(pq)(pq)(pq)(pq)(

p