离散数学(对偶和范式).ppt

1.5 对偶与范式对偶与范式对偶式与对偶原理对偶式与对偶原理析取范式与合取范式析取范式与合取范式主析取范式与主合取范式主析取范式与主合取范式1.对偶式和对偶原理对偶式和对偶原理定定义义 在在仅仅含含有有联联结结词词,的的命命题题公公式式A中中，将将换换成成,换换成成，若若A中中含含有有0或或1，就就将将0换换成成1，1换换成成0，所所得得命命题题公公式称为式称为A的的对偶式对偶式，记为，记为A*.从定义不难看出，从定义不难看出，(A*)*还原成还原成A显显然然，A也也是是A*的的对对偶偶式式。可可见见A与与A*互互为为对偶式。对偶式。2.对偶式和对偶原理对偶式和对偶原理定理定理 设设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)n(1)表表明明，公公式式A的的否否定定等等价价于于其其命命题题变变元元否否定定的的对对偶偶式式；(2)表表明明，命命题题变变元元否否定定的的公公式式等等价价于于对对偶式之否定。偶式之否定。3.对偶式和对偶原理对偶式和对偶原理定理（对偶原理）定理（对偶原理）设设A，B为两个命题公式，为两个命题公式，若若A B，则，则A*B*.有了等值式、代入规则、替换规则和对偶有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为方更多的等值式，使化简命题公式更为方便。便。4.判定问题判定问题真值表真值表等值演算等值演算范式范式5.析取范式与合取范式析取范式与合取范式文字文字:命题变项及其否定的总称命题变项及其否定的总称如如 p,q简单析取式简单析取式:有限个文字构成的析取式有限个文字构成的析取式如如 p,q,pq,p q r,简单合取式简单合取式:有限个文字构成的合取式有限个文字构成的合取式如如 p,q,pq,p q r,注注意意：一一个个命命题题变变元元或或其其否否定定既既可可以以是是简简单单合合取取式，也可是简单析取式，如式，也可是简单析取式，如p，q等。等。6.析取范式与合取范式析取范式与合取范式n定理：定理：简单合取式为永假式的充要条件是：它简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。同时含有某个命题变元及其否定。n定理：定理：简单析取式为永真式的充要条件是：它简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。同时含有某个命题变元及其否定。7.析取范式与合取范式析取范式与合取范式简单析取式简单析取式:有限个文字构成的析取式有限个文字构成的析取式如如 p,q,pq,p q r,简单合取式简单合取式:有限个文字构成的合取式有限个文字构成的合取式如如 p,q,pq,p q r,析取范式析取范式:由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2Ar,其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式:由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A1 A2Ar,其中其中A1,A2,Ar是是简单析取式简单析取式8.析取范式与合取范式析取范式与合取范式(续续)范式范式:析取范式与合取范式的总称析取范式与合取范式的总称公式公式A的析取范式的析取范式:与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式:与与A等值的合取范式等值的合取范式说明：说明：单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式形如形如 pq r,p qr 的公式既是析取范式，的公式既是析取范式，又是合取范式又是合取范式 (为什么为什么?)9.命题公式的范式命题公式的范式定理定理 任何命题公式都存在着与之等值的析取范式任何命题公式都存在着与之等值的析取范式与合取范式与合取范式.求公求公式式A的范式的步骤：的范式的步骤：(1)消消去去A中中的的,（若若存存在在）（消消去去公公式式中中除除、和和 以外公式中出现的所有联结词以外公式中出现的所有联结词）(2)否否定定联联结结词词 的的内内移移或或消消去去（使使用用(P)P和和德德摩根律摩根律）(3)使用分配律使用分配律 对对 分配（析取范式）分配（析取范式）对对 分配（合取范式）分配（合取范式）公式的范式存在，但公式的范式存在，但不惟一不惟一，这是它的局限性，这是它的局限性10.求公式的范式举例求公式的范式举例例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1)A=(pq)r解解 (pq)r (pq)r （消去（消去）pqr （结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）11.求公式的范式举例求公式的范式举例(续续)(2)B=(pq)r解解(pq)r (pq)r （消去第一个（消去第一个）(pq)r （消去第二个（消去第二个）(p q)r （否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续：(p q)r (p r)(q r)（对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成）12.极小项与极大项极小项与极大项定义定义 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式(简单析取式简单析取式)中，中，若每个命题变项均以文字的形式在其中出现且仅出现一若每个命题变项均以文字的形式在其中出现且仅出现一次次，而而且且第第i（1 i n）个个文文字字出出现现在在左左起起第第i位位上上，称称这这样样的简单合取式（简单析取式）为的简单合取式（简单析取式）为极小项极小项（极大项极大项）.n例如，两个命题变元例如，两个命题变元p和和q，其构成的小项有，其构成的小项有p q，pq，p q和和 pq；而三个命题变元；而三个命题变元p、q和和r，其构，其构成的小项有成的小项有p q r，p qr，pq r，pqr，p q r，p qr，pq r，pqr。13.极小项与极大项极小项与极大项定义定义 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式(简单析取式简单析取式)中，中，若每个命题变项均以文字的形式在其中出现且仅出现一若每个命题变项均以文字的形式在其中出现且仅出现一次次，而而且且第第i（1 i n）个个文文字字出出现现在在左左起起第第i位位上上，称称这这样样的简单合取式（简单析取式）为的简单合取式（简单析取式）为极小项极小项（极大项极大项）.例例如如，由由两两个个命命题题变变元元p和和q，构构成成大大项项有有p q，pq，p q，pq；三三个个命命题题变变元元p，q和和r，构构成成p q r，p qr，pq r，pqr，p q r，p qr，pq r，pqr。14.极小项与极大项极小项与极大项说明：说明：n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的十是该极小项成真赋值的十进制表示进制表示.（将命题变元按字典序排列，并且把命题变将命题变元按字典序排列，并且把命题变元与元与1对应，命题变元的否定与对应，命题变元的否定与0对应，则可对对应，则可对2n个小项个小项依二进制数编码依二进制数编码）用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成假赋值的十是该极大项成假赋值的十进制表示进制表示。（。（将将n个命题变元排序，并且把命题变元与个命题变元排序，并且把命题变元与对应，命题变元的否定与对应，则可对对应，命题变元的否定与对应，则可对2n个大项按个大项按二进制数编码二进制数编码）mi(Mi)称为极小项称为极小项(极大项极大项)的名称的名称.mi与与Mi的关系的关系:mi Mi,Mi mi 15.极小项与极大项极小项与极大项(续续)由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1M0M1M2M3极小项极小项极大项极大项16.由由p,q,r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项极小项极小项极大项极大项公式公式成真成真赋值赋值名称名称公式公式成假成假赋值赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q rp q rp q rp q r p q r p q r p q r p q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M717.小项的性质：小项的性质：n(a)没没有有两两个个小小项项是是等等价价的的，即即是是说说各各小小项项的的真真值值表都是不同的；表都是不同的；n(b)任任意意两两个个不不同同的的小小项项的的合合取取式式是是永永假假的的：mi mj，ij。n(c)所有小项之析取为永真：所有小项之析取为永真：mi。n(d)每每个个小小项项只只有有一一个个解解释释为为真真，且且其其真真值值1位位于于主对角线上。主对角线上。18.大项的性质：大项的性质：n(a)没有两个大项是等价的。没有两个大项是等价的。n(b)任任何何两两个个不不同同大大项项之之析析取取是是永永真真的的，即即Mi Mj，ij。n(c)所有大项之合取为永假，即所有大项之合取为永假，即Mi。n(d)每每个个大大项项只只有有一一个个解解释释为为假假，且且其其真真值值0位位于于主对角线上。主对角线上。19.主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式:由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式:由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3 是是主析取范式主析取范式 (p qr)(p qr)M1 M5 是是主合取范主合取范式式 A的主析取范式的主析取范式:与与A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式:与与A等值的主合取范式等值的主合取范式.20.主析取范式与主合取范式主析取范式与主合取范式(续续)定理定理 任何命题公式都存在着与之等值的主析取范任何命题公式都存在着与之等值的主析取范式和主合取范式式和主合取范式,并且是惟一的并且是惟一的.用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，并）表示，并按角标从小到大顺序排序按角标从小到大顺序排序.21.主析取范式与主合取范式主析取范式与主合取范式(续续)用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：(1)先求析取范式先求析取范式 (2)删除析取范式中所有为永假的简单合取式删除析取范式中所有为永假的简单合取式 (3)用等幂律化简简单合取式中同一命题变元的重用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如复出现为一次出现，如p pp。(4)用同一律补进简单合取式中未出现的所有命题用同一律补进简单合取式中未出现的所有命题变元，如变元，如q，则，则pp（q q)，并用分配律展开，并用分配律展开之，将相同的简单合取式的多次出现化为一次出之，将相同的简单合取式的多次出现化为一次出现，现，这样得到了给定公式的主析取范式。这样得到了给定公式的主析取范式。22.从从A的主析取范式求其主合取范的主析取范式求其主合取范式的步骤式的步骤n(a)求出求出A的主析取范式中设有包含的小项。的主析取范式中设有包含的小项。(b)求出与求出与(a)中小项的下标相同的大项。中小项的下标相同的大项。(c)做做(b)中大项之合取，即为中大项之合取，即为A的主合取范的主合取范式。式。例如，例如，(pq)qm1 m3，则，则(pq)qM0 M2。23.求公式的主范式求公式的主范式例例 求公式求公式 A=(pq)r的主析取范式与主合的主析取范式与主合 取范式取范式.(1)求主析取范式求主析取范式 (pq)r (p q)r,（析取范式）（析取范式）(p q)(p q)(r r)(p qr)(p q r)m6 m7,24.求公式的主范式求公式的主范式(续续)r (p p)(q q)r (pq r)(p q r)(pq r)(p q r)m1 m3 m5 m7 ,代入代入并排序，得并排序，得 (pq)r m1 m3 m5 m6 m7（主析取范式）主析取范式）25.求公式的主范式求公式的主范式(续续)(2)求求A的主合取范式的主合取范式 (pq)r (p r)(q r),（合取范式）（合取范式）p r p(qq)r (p q r)(pq r)M0 M2,26.求公式的主范式求公式的主范式(续续)q r (pp)q r (p q r)(p q r)M0 M4 ,代入代入并排序，得并排序，得 (pq)r M0 M2 M4 （主合取范式）（主合取范式）27.主范式的用途主范式的用途与真值表相同与真值表相同(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值 例如例如 (pq)r m1 m3 m5 m6 m7，其成真赋值为其成真赋值为001,011,101,110,111，其余的赋值其余的赋值 000,010,100为为成假赋值成假赋值.类似地，由主合取范式也可立即求出成类似地，由主合取范式也可立即求出成 假赋值和成真赋值假赋值和成真赋值.28.主范式的用途主范式的用途(续续)(2)判断公式的类型判断公式的类型 设设A含含n个命题变项，则个命题变项，则 A为重言式为重言式A的主析取范式含的主析取范式含2n个极小项个极小项 A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式 A的主析取范式为的主析取范式为0 A的主合析取范式含的主合析取范式含2n个极大项个极大项A为非重言式的可满足式为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项的主合取范式中至少含一个且不含全部极大项29.主范式的用途主范式的用途(续续)例例 用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值：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显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值.(3)判断两个公式是否等值判断两个公式是否等值说明：说明：由公式由公式A的主析取范式确定它的主合取范式，反之亦然的主析取范式确定它的主合取范式，反之亦然.用公式用公式A的真值表求的真值表求A的主范式的主范式.30.主范式的用途主范式的用途(续续)例例 某公司要从赵、钱、孙、李、周五名新毕某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习业的大学生中选派一些人出国学习.选派必须选派必须满足以下条件：满足以下条件：(1)(1)若赵去，钱也去；若赵去，钱也去；(2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去；(3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人；(4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去；(5)(5)若周去，则赵、钱也去若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出试用主析取范式法分析该公司如何选派他们出国？国？31.例例(续续)解此类问题的步骤为：解此类问题的步骤为：将简单命题符号化将简单命题符号化 写出各复合命题写出各复合命题 写出由写出由中复合命题组成的合取式中复合命题组成的合取式 求求中所得公式的主析取范式中所得公式的主析取范式32.例例(续续)解解 设设p：派赵去，：派赵去，q：派钱去，：派钱去，r：派孙去，：派孙去，s：派李去，：派李去，u：派周去：派周去.(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)33.例例(续续)A (pq r su)(p qrs u)结论：由结论：由可知，可知，A的成真赋值为的成真赋值为00110与与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）周去（孙、李不去）.A的演算过程如下的演算过程如下:A (p q)(qr)(q r)(s u)(u(p q)(r s)(rs)（交换律（交换律)B1=(p q)(qr)(q r)(p qr)(pq r)(qr)（分分配配律）律）34.例例(续续)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)得得 A B1 B2 B3 (pq r su)(p qrs u)注意：在以上演算中多次用矛盾律注意：在以上演算中多次用矛盾律要求：自己演算一遍要求：自己演算一遍35.