命题逻辑公式的范式和主范式.pdf

计算机科学MOOC课程群

离离散散数数学学基基础础

本单元内容比较多，视频分割成三个部分：范式的概念、主范式及其应
用和主范式的编码

PART1范式的概念

•范式的一些基本定义
−文字：原子命题及其否定式统称为文字（形）。
»例：对变量表{p,q}，p,¬p,q,¬q都是文字。
»例：把F称为空文字，记作NIL。
−基本积：由有限个文字的合取构成。(简单合取式)
»例：对变量表{p,q,r}，基本积有p,¬p,q∧¬p,¬q∧¬p∧r等等。
−基本和：由有限个文字的析取构成。(简单析取式)
»例：对变量表{p,q,r}，基本和有p,¬p,q∨¬p,¬q∨¬p∨r等等。

•定理6
−一个基本和是永真的当且仅当其中含有某个原子的互补对；
»由排中律和零律：α∨p∨¬p⇔α∨1⇔1
−一个基本积是矛盾的当且仅当其中含有某个原子的互补对。
»由矛盾律和零律：α∧p∧¬p⇔α∧0⇔0

•定义：析取范式

−一个命题公式称为是一个析取范式当且仅当其具有形式A1∨A2∨…∨An
(1≤n<∞)，其中Ai是基本积(1≤i≤n)。
−例1：¬p∨(q∧¬r)∨s，(n=3)
−例2：¬p，(n=1)
−例3：¬p∧q∧¬r，(n=1)
−例4：¬p∨q∨¬r，(n=3)

•定义：合取范式

−一个命题公式称为是一个合取范式当且仅当其具有形式A1∧A2∧…∧An
(1≤n<∞)，其中Ai是基本和(1≤i≤n)。
−例1：(¬p∨q∨s)∧(¬p∨¬r∨s)，(n=2)
−例2：¬p，(n=1)
−例3：¬p∧q∧¬r，(n=3)
−例4：¬p∨q∨¬r，(n=1)

•定理7
(1)一个合取范式是永真的当且仅当其中含有的基本和都是永真的；
(2)一个析取范式是矛盾的当且仅当其中含有的基本积都是矛盾的。
−证明：留作思考。

•定理8（范式存在基本定理）
−任一命题公式都有与之等值的析取范式和合取范式。
−构造性证明
−以求合取范式为例，重复施行如下的等值变形：
①联结词化归：应用联结词消去等值式，消去→和↔；
②否定词深入：应用德‐摩根律，使否定词直接作用于原子命题变量；
③重复利用∧和∨之间的分配律求得析取范式或合取范式。

−例：(p∧(q→r))→s
⇔¬(p∧(¬q∨r))∨s联结词化归
⇔¬p∨¬(¬q∨r)∨s德‐摩根律
⇔¬p∨(q∧¬r)∨s德‐摩根律
⇔(¬p∨q∨s)∧(¬p∨¬r∨s)分配律
⇔(¬p∨q∨s)∧(¬p∨¬r∨s)∧(¬p∨¬r∨s)幂等律
•讨论：一个命题公式的合取（析取）范式不是唯一的。

PART2主范式及其应用

•定义：极小项

−设命题公式A(p1,p2,…,pn)，又设Ak∈{pk,¬pk},k=1..n,则称A1∧A2∧…∧An为公
式A的一个极小项。
−极小项也称布尔积。
n
(1)关于A(p1,p2,…,pn)或原子变量集合{p1,p2,…,pn}的极小项有2个。
»例：对{p,q}，可以构造22=4个极小项¬p∧¬q，¬p∧q，p∧¬q，p∧q。
(2)对变量表的任一解释有且仅有一个极小项的值为1，其余的值为0，称该极
小项为该解释所对应的极小项。
»例：对{p,q}的一个解释t(p)=1,t(q)=0，有且仅有p∧¬q=1,对其他的三个
极小项，每个极小项中至少有一个文字的值是0，所以这三个极小项的值都
是0。
(3)任何一对不同极小项的合取为0。所有极小项的析取为1。
»由(2),对变量表的任一解释，任何一对极小项中最多有一个极小项取值为
1，另外的取值为0，所以合取为0；所有极小项中恰有一个极小项取值为1，
所以析取为1。

•定义：极大项

−设命题公式A(p1,p2,…,pn)，又设Ak∈{pk,¬pk},k=1..n,则称A1∨A2∨…∨An为公
式A的一个极大项。
−极大项也称布尔和。
n
(1)关于A(p1,p2,…,pn)或原子变量集合{p1,p2,…,pn}的极大项有2个。
»例：对{p,q}，可以构造极大项¬p∨¬q，¬p∨q，p∨¬q，p∨q。
(2)对任一解释有且仅有一个极大项的值为0，其余的值为1，称该极大项为该解
释所对应的极大项。
(3)任何一对不同极大项的析取为1。所有极大项的合取为0。

•定义：主析取范式

−一个命题公式B(p1,p2,…,pn)称为是一个主析取范式(形的)，当且仅当其具有
形式
n
B1∨B2∨…∨Bm(1≤m≤2)，
其中Bi(1≤i≤m)为公式B的一个极小项，且Bi≠Bj(对i≠j)。

•定义：主合取范式

−一个命题公式B(p1,p2,…,pn)称为是一个主合取范式(形的)，当且仅当其具有
形式
n
B1∧B2∧…∧Bm(1≤m≤2)，
其中Bi(1≤i≤m)为公式B的一个极大项，且Bi≠Bj(