《离散数学：1-5 对偶与范式》由会员分享，可在线阅读，更多相关《离散数学：1-5 对偶与范式（39页珍藏版）》请在金锄头文库上搜索。
1、1.5对偶与范式对偶与范式 对偶式与对偶原理对偶式与对偶原理 析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式 1对偶式和对偶式和对偶原理对偶原理定义定义在仅含有联结词在仅含有联结词 ,的命题公式的命题公式A中，将中，将换成换成,换成换成，若，若A中含有中含有0或或1，就将，就将0换成换成1，1换成换成0，所得命题公式称为，所得命题公式称为A的的对偶式对偶式，记为，记为A*.从定义不难看出，从定义不难看出，(A*)*还原成还原成A定理定理设设A和和A*互为对偶式，互为对偶式，p1,p2,pn是出现在是出现在A和和A*中的全部命题变项，将中的全部命题变项，将A和
2、和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*. .2析取范式与合取范式析取范式与合取范式 文字文字: :命题变项及其否定的总称命题变项及其否定的总称简单析取式简单析取式: :有限个文字构成的析取式有限个文字构成的析取式如如p, q,pq,p q r,简单合取式简单合取式: :有限个文字构成的合取式有限个文字构成的合取式如如p, q,pq,p q r,析取范式析取范式: :
3、由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式A1 A2Ar,其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式: :由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式A1 A2Ar ,其中其中A1,A2,Ar是是简单析取式简单析取式3析取范式与合取范式析取范式析取范式: :由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2Ar, 其中其中A1,A2,Ar是是简单合取式简单合取式例如例如: (pq) (p q r)合取范式合取范式: :由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A1 A2Ar , 其中其中A1,A2
4、,Ar是是简单析取式简单析取式例如例如: (pq) (p q r)4析取范式与合取范式析取范式与合取范式( (续续) )范式范式: :析取范式与合取范式的总称析取范式与合取范式的总称公式公式A的析取范式的析取范式:与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式:与与A等值的合取范式等值的合取范式说明：说明：单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式pq r, p qr既是析取范式，又是合取范式既是析取范式，又是合取范式(为什么为什么?) 5命题公式的范式命题公式的范式 定理定理任何命题公式都存在着与之等值的析取范式任何命题公式都存在着与之等值
5、的析取范式与合取范式与合取范式. .求公求公式式A的范式的步骤：的范式的步骤：(1)消去消去A中的中的,（若存在）（若存在）(2)否定联结词否定联结词 的内移或消去的内移或消去(3)使用分配律使用分配律 对对 分配（析取范式）分配（析取范式） 对对 分配（合取范式）分配（合取范式）公式的范式存在，但不惟一公式的范式存在，但不惟一6范式存在定理定定理理任任何何命命题题公公式式都都存存在在着着与与之之等等值值的的析析取范式与合取范式取范式与合取范式. .证证 求公求公式式A的范式的步骤：的范式的步骤：(1) 消去消去A中的中的, ABA B AB (AB) (BA) ( A B) (AB)7范式存
6、在定理(2) 否定联结词否定联结词 的内移或消去的内移或消去 (A B)AB (A B)AB A A(3) 使用分配律使用分配律 A (B C)(A B) (A C) 求求合合取取范范式式 A (B C)(A B) (A C) 求求析析取取范范式式8范式存在定理(续)例例1 1 求求 (pq)r 的析取范式与合取范式的析取范式与合取范式9范式存在定理(续)例例1 1 求求 (pq)r 的析取范式与合取范式的析取范式与合取范式解解 (pq)r ( p q)r (蕴涵等涵等值式式) (pq)r (德模根律德模根律) (pq)r (双双重重否否定定律律) 析取范式析取范式10范式存在定理(续)注意注
7、意: 公式的析取范式与合取范式不惟一公式的析取范式与合取范式不惟一. (pq)r (pq)r (pq) ( r 1) (同一律同一律)(pq) ( r (pp) (排中律排中律) (pq) ( r p) ( rp) (分分配配律律)11极小项与极大项极小项与极大项 定义定义在含有在含有n个命题变项的简单合取式个命题变项的简单合取式( (简单析取式简单析取式) )中，中，若每个命题变项均以若每个命题变项均以文字文字的形式在其中出现且仅出现一的形式在其中出现且仅出现一次次，而而且且第第i（1 i n）个个文文字字出出现现在在左左起起第第i位位上上，称称这这样样的简单合取式（简单析取式）为的简单合取
8、式（简单析取式）为极小项极小项（极大项极大项）.说明：说明：n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的十是该极小项成真赋值的十进制表示进制表示.用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成假是该极大项成假赋值的十进制表示赋值的十进制表示,mi( (Mi) )称为极小项称为极小项( (极大项极大项) )的名称的名称. mi与与Mi的关系的关系: : mi Mi , Mi mi12极小项与极大项极小项与极大项( (
9、续续) )由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 公式公式 成真赋值成真赋值名称名称 公式公式 成假赋值成假赋值名称名称 p q p q p q p q00011011m0m1m2m3 p qp q p q p q 00011011 M0M1M2M3 极小项极小项 极大项极大项 13 由由p,q,r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 极小项极小项 极大项极大项 公式公式 成真成真赋值赋值名称名称 公式公式 成假成假赋值赋值名称名称 p qr p q r p qr p q rp q rp q rp qrp q r000001010
10、011100101110111m0m1m2m3m4m5m6m7p q r p qr p q r p qr p q r p qr p q r p qr 000001010011100101110111M0M1M2M3M4M5M6M7 14主析取范式与主合取范式主析取范式与主合取范式 主析取范式主析取范式: : 由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式: : 由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，( pq r) ( p q r)m1 m3是是主析取范式主析取范式(p qr) ( p qr)M1 M5是是主合取范
11、主合取范式式 A的主析取范式的主析取范式:与与A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式: : 与与A等值的主合取范式等值的主合取范式.15主析取范式与主合取范式主析取范式与主合取范式( (续续) )定理定理任何命题公式都存在着与之等值的主析取范任何命题公式都存在着与之等值的主析取范式和主合取范式式和主合取范式,并且是惟一的并且是惟一的. .用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个
12、极小项的析单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等. (3)极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，并表示，并按角标从小到大顺序排序按角标从小到大顺序排序. 16求主析取范式的步骤设公式设公式A含命题变项含命题变项p1,p2,pn(1) 求求A的析取范式的析取范式A =B1 B2 Bs, 其中其中Bj是简单是简单合取式合取式 j=1,2, ,s (2) 若某个若某个Bj既不含既不含pi, 又不含又不含 pi, 则将
13、则将Bj展开成展开成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重复这个过程重复这个过程, 直到所有简单合取式都是长度为直到所有简单合取式都是长度为n的极的极 小项为止小项为止(3) 消去重复出现的极小项消去重复出现的极小项, 即用即用mi代替代替mi mi(4) 将极小项按下标从小到大排列将极小项按下标从小到大排列17求主合取范式的步骤设公式设公式A含命题变项含命题变项p1,p2,pn(1) 求求A的合取范式的合取范式A =B1 B2 Bs, 其中其中Bj是简单是简单析析 取式取式 j=1,2, ,s (2) 若某个若某个Bj既不含既不含pi, 又不含又不含 pi, 则将则
14、将Bj展开成展开成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重复这个过程重复这个过程, 直到所有简单析取式都是长度为直到所有简单析取式都是长度为n的极的极大项为止大项为止(3) 消去重复出现的极大项消去重复出现的极大项, 即用即用Mi代替代替Mi Mi(4) 将极大项按下标从小到大排列将极大项按下标从小到大排列18实例例例1(1(续续) ) 求求 (pq)r 的的主主析析取取范范式式与与主主合取范式合取范式解解 (1) (1) (pq)r (pq)r 19 例例1(1(续续) ) 求求 (pq)r 的主析取范式与主合取范式的主析取范式与主合取范式解解 (1) (1) (pq
15、)r (pq)r pq (pq) 1 同一律同一律 (pq) ( r r) 排中律排中律 (pq r) (pq r) 分配律分配律 m4 m5 r ( p p) ( q q)r 同同一一律律, 排排中律中律 ( pq r) ( p q r) (pq r) (p q r) m0 m2 m4 m6 分配律分配律得得 (pq)r m0 m2 m4 m5 m6可记作可记作 (0,2,4,5,6)20实例(续)(2) (pq)r (pr) ( qr) pr p 0r 同一律同一律 p (qq)r 矛盾律矛盾律 (p qr) (p qr) 分配律分配律 M1 M3 qr (pp) ( qr) 同一律同一律
16、, 矛矛盾律盾律 (pqr) ( pqr) 分配律分配律 M3 M7得得 (pq)r M1 M3 M7可记作可记作 (1,3,7)21快速求法设公式含有设公式含有n个命题变项个命题变项, 则则长度为长度为k的简单析取式可展开成的简单析取式可展开成2n k个极大项的合取个极大项的合取例如例如 pr (p qr) (p qr) M1 M3长度为长度为k的简单合取式可展开成的简单合取式可展开成2n k个极小项的析取个极小项的析取例如例如 公式含公式含p,q,r q ( p q r) ( p q r) (p q r) (p q r) M5 M4 M1 M022实例例例2 (1) 求求 A ( p q)
17、 ( pq r) r 的主析取范式的主析取范式解解 用快速求法用快速求法23实例例例2 (1) 求求 A ( p q) ( pq r) r 的主析取范式的主析取范式解解 用快速求法用快速求法(1) p q ( p q r) ( p q r) m2 m3 pq r m1 r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7得得 A m1 m2 m3 m5 m7 (1,2,3,5,7)24实例(续)(2) 求求 Bp (p qr)的主合取范式的主合取范式解解25实例(续)(2) 求求 Bp (p qr)的主合取范式的主合取范式解解 p ( p q r) ( p
18、 qr) ( p q r) ( p qr) M4 M5 M6 M7 p qr M1得得 B M1 M4 M5 M6 M7 (1,4,5,6,7)26主合取范式由主析取范式求主合取范式由主析取范式求主合取范式设设没有出现的极小项是没有出现的极小项是其中其中t=2n s, 于是于是27主合取范式(续)例例6 求求A=( pq r) ( p q r) (p q r)的主的主合取范式合取范式解解 A m1 m3 m7 (1,3,7) (0,2,4,5,6) M0 M2 M4 M5 M6矛盾式的主合取范式含全部矛盾式的主合取范式含全部2n个极大项个极大项重言式的主合取范式不含任何极大项重言式的主合取范式
19、不含任何极大项, 记作记作128实例例例5 某单位要从某单位要从A,B,C三人选派若干人出国考察三人选派若干人出国考察, 需满足需满足下述条件下述条件:(1) 若若A去去, 则则C必须去必须去;(2) 若若B去去, 则则C不能去不能去;(3) 若若C不去不去,则则A或或B可以去可以去.问有几种可能的选派方案问有几种可能的选派方案?解解 记记p:派派A去去, q:派派B去去, r:派派C去去(1) pr, (2) qr, (3) r(p q)求下式的成真赋值求下式的成真赋值 A=(pr) (qr) ( r(p q)29实例(续)求求A的主析取范式的主析取范式 A=(pr) (qr) ( r(p
20、q) ( p r) ( qr) (r p q) (蕴涵等值式蕴涵等值式,双重双重否定律否定律) ( p q r) ( p q r) (矛盾律矛盾律,分配律分配律) (pqr) ( pqr) (矛盾律矛盾律,分配律分配律) (p q r) (交换律交换律) M4 M6 M3 M7 M0 (0,3,4,6,7) (1,2,5)成真赋值成真赋值:001,010,101结论结论: 方案方案1 派派C去去,A和和B不去不去; 方案方案2 派派B去去, A和和C不去不去; 方案方案3 派派A和和C去去, B不去不去.30主范式的用途主范式的用途与真值表相同与真值表相同 (1)求公式的成真赋值和成假赋值求公
21、式的成真赋值和成假赋值例如例如(pq)rm1 m3 m5 m6 m7， 其成真赋值为其成真赋值为001,011,101,110,111， 其余的赋值其余的赋值 000,010,100为为成假赋值成假赋值.类似地，由主合取范式也可立即求出成类似地，由主合取范式也可立即求出成 假赋值和成真赋值假赋值和成真赋值.31主范式的用途主范式的用途( (续续) )(2)判断公式的类型判断公式的类型设设A含含n个命题变项，则个命题变项，则A为重言式为重言式A的主析取范式含的主析取范式含2n个极小项个极小项A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式A的主析取范式为的主析取范式为0A的主合取范式含的主合
22、取范式含2n个极大项个极大项A为非重言式的可满足式为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项的主合取范式中至少含一个且不含全部极大项 32主范式的用途主范式的用途( (续续) )例例用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值： p(qr)与与(p q)r p(qr)与与(pq)r解解 p(qr)=m0 m1 m2 m3 m4 m5 m7(p q)r =m0 m1 m2 m3 m4 m5 m7(pq)r =m1 m3 m4 m5 m7故故中的两公式等值，而中的两公
23、式等值，而的不等值的不等值. (3)判断两个公式是否等值判断两个公式是否等值说明：说明： 由公式由公式A的主析取范式确定它的主合取范式，反之亦然的主析取范式确定它的主合取范式，反之亦然. 用公式用公式A的真值表求的真值表求A的主范式的主范式.33主范式的用途主范式的用途( (续续) ) 例例某公司要从赵、钱、孙、李、周五名新毕某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习业的大学生中选派一些人出国学习.选派必须选派必须满足以下条件：满足以下条件： (1)(1)若赵去，钱也去；若赵去，钱也去； (2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去； (3)(3)钱、
24、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人； (4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去； (5)(5)若周去，则赵、钱也去若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出试用主析取范式法分析该公司如何选派他们出国？国？34例例(续续)解此类问题的步骤为：解此类问题的步骤为：将简单命题符号化将简单命题符号化写出各复合命题写出各复合命题写出由写出由中复合命题组成的合取式中复合命题组成的合取式 求求中所得公式的主析取范式中所得公式的主析取范式 35例例(续续)解解设设p：派赵去，派赵去，q：派钱去，派钱去，r：派孙去，派孙去， s：派李去，派李去，u：
25、派周去派周去. .(1)(pq)(2)(s u)(3)(qr) ( q r)(4)(r s) ( rs)(5)(u(p q)(1)(5)构成的合取式为构成的合取式为A=(pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)36例例(续续)A ( pq r su) (p qrs u)结论：由结论：由可知，可知，A的成真赋值为的成真赋值为00110与与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）周去（孙、李不去）. . A的演算过程如下的演算过程如下: :A( p q) (qr) ( q r)
26、(s u) ( u (p q) (r s) ( rs)（交换律交换律) )B1=( p q) (qr) ( q r)( p qr) ( pq r) (qr)（分分配配律）律）37例例(续续)B2=(s u) ( u (p q)(su) (p q s) (p q u)（分配律）分配律）B1 B2( p qr su) ( pq r su) (qr su) (p qr s) (p qr u)再令再令B3=(r s) ( rs)得得 AB1 B2 B3( pq r su) (p qrs u)注意：在以上演算中多次用矛盾律注意：在以上演算中多次用矛盾律要求：自己演算一遍要求：自己演算一遍 38作业：P34-35:T1.12(2)T1.13(1)自由练习：自由练习：T1.12(2) (3)T1.13(2)T1.1539
