《离散数学》课程PPT教学课件（讲稿）第1章 命题逻辑（1.5）对偶与范式

15对偶与范式 ■对偶式与对偶原理 ■析取范式与合取范式 主析取范式与主合取范式

1 1.5 对偶与范式 ▪对偶式与对偶原理 ▪析取范式与合取范式 ▪主析取范式与主合取范式

对偶式和对偶原理 定义在仅含有联结词→,∧,∨的命题公式4中,将 换成∧,∧换成∨,若A中含有0或1,就将0换成 1,1换成0,所得命题公式称为A的对偶式,记为A 从定义不难看出,(4)还原成A 定理设A和A4互为对偶式,P12D2…1是出现在A和 A中的全部命题变项,将A和A*写成n元函数形式, 则(1)-A(D12D2…)分A"(-p1-p2…,-pn (2)A(P1,p2,…,=P A"(p12…n 定理(对偶原理)设A,B为两个命题公式, 若A分B,则A兮B

2 对偶式和对偶原理 定义 在仅含有联结词, ∧,∨的命题公式A中，将 ∨换成∧, ∧换成∨，若A中含有0或1，就将0换成 1，1换成0，所得命题公式称为A的对偶式，记为A* . 从定义不难看出，(A* ) *还原成A 定理 设A和A*互为对偶式，p1 ,p2 ,…,pn是出现在A和 A*中的全部命题变项，将A和A*写成n元函数形式， 则 (1)  A(p1 ,p2 ,…,pn )  A* ( p1 ,  p2 ,…,  pn ) (2) A( p1 ,  p2 ,…,  pn )   A* (p1 ,p2 ,…,pn ) 定理（对偶原理）设A，B为两个命题公式， 若A  B，则A*  B*

析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 P9-4,pV-4,qV, 简单合取式:有限个文字构成的合取式 如 P,-q,p-4,p∧q∧r, 析取范式:由有限个简单合取式组成的析取式 AV42…A,其中A142,…,4,是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1~42^…,A,其中A1,42,,4是简单析取式

3 析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 p, q, pq, pqr, … 简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr, … 析取范式:由有限个简单合取式组成的析取式 A1A2Ar , 其中A1 ,A2 ,,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1A2Ar , 其中A1 ,A2 ,,Ar是简单析取式

析取范式与合取范式(续) 范式:析取范式与合取范式的总称 公式A的析取范式:与A等值的析取范式 公式4的合取范式:与A等值的合取范式 说明 单个文字既是简单析取式,又是简单合取式 形如p∧-q∧r,mqr的公式既是析取范式, 又是合取范式(为什么?

4 析取范式与合取范式(续) 范式:析取范式与合取范式的总称 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 形如 pqr, pqr 的公式既是析取范式， 又是合取范式 (为什么?)

命题公式的范式 定理任何命题公式都存在着与之等值的析取范式 与合取范式 求公式4的范式的步骤: (1)消去A中的→,4(若存在) (2)否定联结词一的内移或消去 (3)使用分配律 ∧对√分配(析取范式) v对入分配(合取范式) 公式的范式存在,但不惟一,这是它的局限性

5 命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式 与合取范式. 求公式A的范式的步骤： (1) 消去A中的→, （若存在） (2) 否定联结词的内移或消去 (3) 使用分配律 对分配（析取范式） 对分配（合取范式） 公式的范式存在，但不惟一，这是它的局限性

求公式的范式举例 例求下列公式的析取范式与合取范式 (1)4=(p→>-q)v 解(p->qvr 分(yV-qyr(消去→) 兮一VqV(结合律) 这既是A的析取范式(由3个简单合取式组成的析 取式),又是A的合取范式(由一个简单析取式 组成的合取式)

6 求公式的范式举例 例 求下列公式的析取范式与合取范式 (1) A=(p→q)r 解 (p→q)r  (pq)r （消去→）  pqr （结合律） 这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式）

求公式的范式举例(续) (2)B=D→>-q)->r 解(p→-q)-r 兮(yV-q)-r(消去第一个→) 兮-(yV-qyr(消去第二个→) 分(∧qvr (否定号内移—德摩根律) 这一步已为析取范式(两个简单合取式构成) 继续:(p∧qr 台(pVr)∧(qr)(v对入分配律) 这一步得到合取范式(由两个简单析取式构成)

7 求公式的范式举例(续) (2) B=(p→q)→r 解 (p→q)→r  (pq)→r （消去第一个→）  (pq)r （消去第二个→）  (pq)r （否定号内移——德摩根律） 这一步已为析取范式（两个简单合取式构成） 继续： (pq)r  (pr)(qr) （对分配律） 这一步得到合取范式（由两个简单析取式构成）

极小项与极大项 定义在含有n个命题变项的简单合取式(简单析取式)中, 若每个命题变项均以文字的形式在其中出现且仅出现一 次,而且第(I≤还n)个文字出现在左起第谊上,称这样 的简单合取式(简单析取式)为极小项(极大项) 说明:n个命题变项产生2n个极小项和2n个极大项 2n个极小项(极大项)均互不等值 用m表示第i个极小项,其中i该极小项成真赋值的十 进制表示用M表示第个极大项,其中误该极大项成假 赋值的十进制表示,m2(M)称为极小项(极大项)的名称 m1与M的关系:-m1分M,_M分m1

8 极小项与极大项 定义 在含有n个命题变项的简单合取式(简单析取式)中， 若每个命题变项均以文字的形式在其中出现且仅出现一 次，而且第i（1in）个文字出现在左起第i位上，称这样 的简单合取式（简单析取式）为极小项（极大项）. 说明：n个命题变项产生2 n个极小项和2 n个极大项 2 n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十 进制表示. 用Mi表示第i个极大项，其中i是该极大项成假 赋值的十进制表示, mi (Mi )称为极小项(极大项)的名称. mi与Mi的关系: mi Mi , Mi mi

极小项与极大项(续) 由,q两个命题变项形成的极小项与极大项 极小项 极大项 公式成真赋值名称公式成假赋值名称 y∧-q 00 00M y入q pv-nq01 MI 12一yq 10M P∧q 11

9 极小项与极大项(续) 由p, q两个命题变项形成的极小项与极大项 公式 成真赋值 名称 公式 成假赋值 名称 p  q p  q p  q p  q 0 0 0 1 1 0 1 1 m0 m1 m2 m3 p  q p  q p  q p  q 0 0 0 1 1 0 1 1 M0 M1 M2 M3 极小项 极大项

由,q,r三个命题变项形成的极小项与极大项 极小项 极大项 公式 成真名称公式成假名称 赋值 赋值 PA-qAP000 pvgvr000 ∧-q∧r001m 112 pvqv-r 001 一∧q∧r010 pv-qvr010 MMMM 011 Pv9V-r011 P∧一q∧_r100 一vqr100 P∧-q∧r101 opVgV-r101 0123456 P∧q∧-r 110 一V-qVr110 P∧r111m-Vy=qy111M 10

10 由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 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 m1 m2 m3 m4 m5 m6 m7 p  q  r p  q r p  q  r p  q r p  q  r p  q r p  q  r p  q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M0 M1 M2 M3 M4 M5 M6 M7