离散数学(对偶和范式)

1、a11.5 对偶与范式对偶与范式 对偶式与对偶原理对偶式与对偶原理 析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式 a2对偶式和对偶原理对偶式和对偶原理定义定义 在仅含有联结词在仅含有联结词 , ,的命题公式的命题公式A中，将中，将换成换成, 换成换成，若，若A中含有中含有0或或1，就将，就将0换成换成1，1换成换成0，所得命题公，所得命题公式称为式称为A的的对偶式对偶式，记为，记为A*.从定义不难看出，从定义不难看出，(A*)* 还原成还原成A显然，显然，A也是也是A*的对偶式。可见的对偶式。可见A与与A*互为互为对偶式。对偶式。a3对偶式和对偶原理对偶式

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)表明，命题变元否定的公式等价于对表明，命题变元否定的公式等价于对偶式之否定。偶式之否定。a4对偶式和对偶原理对偶式和对偶原理定理（对偶原理）定理（对偶原理）设设A，B为

3、两个命题公式，为两个命题公式，若若A B，则，则A* B*. .有了等值式、代入规则、替换规则和对偶有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为方更多的等值式，使化简命题公式更为方便。便。a5判定问题判定问题真值表真值表等值演算等值演算范式范式a6析取范式与合取范式析取范式与合取范式 文字文字: :命题变项及其否定的总称命题变项及其否定的总称如如 p, q简单析取式简单析取式: :有限个文字构成的析取式有限个文字构成的析取式如如 p, q, pq, p q r, 简单合取式简单合取式: :有限个文字构成

4、的合取式有限个文字构成的合取式如如 p, q, pq, p q r, 注意：一个命题变元或其否定既可以是简单合取注意：一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如式，也可是简单析取式，如p， q等。等。a7析取范式与合取范式析取范式与合取范式 n定理：定理： 简单合取式为永假式的充要条件是：它简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。同时含有某个命题变元及其否定。n定理：定理： 简单析取式为永真式的充要条件是：它简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。同时含有某个命题变元及其否定。a8析取范式与合取范式析取范式与合取范式 简单析取式

5、简单析取式: :有限个文字构成的析取式有限个文字构成的析取式如如 p, q, pq, p q r, 简单合取式简单合取式: :有限个文字构成的合取式有限个文字构成的合取式如如 p, q, pq, p q r, 析取范式析取范式: :由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2Ar, 其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式: :由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A1 A2Ar , 其中其中A1,A2,Ar是是简单析取式简单析取式a9析取范式与合取范式析取范式与合取范式( (续续) )范式范式: :析取范式与合取范式

6、的总称析取范式与合取范式的总称 公式公式A的析取范式的析取范式: 与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式: 与与A等值的合取范式等值的合取范式说明：说明： 单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式形如形如 pq r, p qr 的公式既是析取范式，的公式既是析取范式，又是合取范式又是合取范式 (为什么为什么?) a10命题公式的范式命题公式的范式 定理定理 任何命题公式都存在着与之等值的析取范式任何命题公式都存在着与之等值的析取范式与合取范式与合取范式. .求公求公式式A的范式的步骤：的范式的步骤： (1) 消去消去A中的中的, （

7、若存在）（若存在）（消去公式中除消去公式中除 、 和和 以外公式中出现的所有联结词以外公式中出现的所有联结词） (2) 否定联结词否定联结词 的内移或消去（的内移或消去（使用使用 ( P)P和德和德摩根律摩根律） (3) 使用分配律使用分配律 对对 分配（析取范式）分配（析取范式） 对对 分配（合取范式）分配（合取范式）公式的范式存在，但公式的范式存在，但不惟一不惟一，这是它的局限性，这是它的局限性 a11求公式的范式举例求公式的范式举例 例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1) A=(pq)r解解 (pq)r ( pq)r （消去（消去） pqr （结合律）（

8、结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）a12求公式的范式举例求公式的范式举例( (续续) )(2) B=(pq)r解解 (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续： (p q) r (p r) (q r) （ 对对 分配律）分配律

9、）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成） a13极小项与极大项极小项与极大项 定义定义 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式( (简单析取式简单析取式) )中，中，若每个命题变项均以文字的形式在其中出现且仅出现一若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第次，而且第i（1 i n）个文字出现在左起第）个文字出现在左起第i位上，称这样位上，称这样的简单合取式（简单析取式）为的简单合取式（简单析取式）为极小项极小项（极大项极大项）.n例如，两个命题变元例如，两个命题变元p和和q，其构成的小项有，其构成的小项有p q，

10、pq， p q和和 pq；而三个命题变元；而三个命题变元p、q和和r，其构，其构成的小项有成的小项有p q r，p qr，pq r，pqr， p q r ， p qr， pq r， pqr。a14极小项与极大项极小项与极大项 定义定义 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式( (简单析取式简单析取式) )中，中，若每个命题变项均以文字的形式在其中出现且仅出现一若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第次，而且第i（1 i n）个文字出现在左起第）个文字出现在左起第i位上，称这样位上，称这样的简单合取式（简单析取式）为的简单合取式（简单析取式）为极小项极小项（

11、极大项极大项）.例如，由两个命题变元例如，由两个命题变元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。a15极小项与极大项极小项与极大项 说明：说明：n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的十是该极小项成真赋值的十进制表示进制表示. （将命题变元按字典序排列，并且把命题变将

12、命题变元按字典序排列，并且把命题变元与元与1对应，命题变元的否定与对应，命题变元的否定与0对应，则可对对应，则可对2n个小项个小项依二进制数编码依二进制数编码） 用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成假赋值的十是该极大项成假赋值的十进制表示进制表示。（。（将将n个命题变元排序，并且把命题变元与个命题变元排序，并且把命题变元与对应，命题变元的否定与对应，则可对对应，命题变元的否定与对应，则可对2n个大项按个大项按二进制数编码二进制数编码） mi( (Mi) )称为极小项称为极小项( (极大项极大项) )的名称的名称. mi与与Mi的关系的关系: : mi Mi , Mi

13、 mi a16极小项与极大项极小项与极大项( (续续) )由由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 1 M0M1M2M3 极小项极小项 极大项极大项 a17 由由p, q, r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 极小项极小项 极大项极大项 公式公式 成真成真赋值赋值名称名称 公式公式 成假成假赋值赋值名称名称 p q r

14、 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 r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 a18小项的性质：小项的性质：n(a)没有两个小项是等价的，即是说各小项的真没有两个小项是等价的，即是说各小项的真值表都是不同的；值表都是不同的；n(b)任意两个不同的小项的合取式是永假的：任意两个不同

15、的小项的合取式是永假的：mimj，ij。n(c)所有小项之析取为永真：所有小项之析取为永真： mi。n(d)每个小项只有一个解释为真，且其真值每个小项只有一个解释为真，且其真值1位于位于主对角线上。主对角线上。1nia19大项的性质：大项的性质：n(a)没有两个大项是等价的。没有两个大项是等价的。n(b)任何两个不同大项之析取是永真的，即任何两个不同大项之析取是永真的，即MiMj，ij。n(c) 所有大项之合取为永假，即所有大项之合取为永假，即 Mi。n(d) 每个大项只有一个解释为假，且其真值每个大项只有一个解释为假，且其真值0位于位于主对角线上。主对角线上。1nia20主析取范式与主合取范

16、式主析取范式与主合取范式 主析取范式主析取范式: : 由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式: : 由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为p, q, r时，时， ( pq r) ( p q r) m1 m3 是是主析取范式主析取范式 (p qr) ( p qr) M1 M5 是是主合取范式主合取范式 A的主析取范式的主析取范式: 与与A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式: : 与与A等值的主合取范式等值的主合取范式. a21主析取范式与主合取范式主析取范式与主合取范式( (续续) )定理定理 任

17、何命题公式都存在着与之等值的主析取范任何命题公式都存在着与之等值的主析取范式和主合取范式式和主合取范式, 并且是惟一的并且是惟一的. . 用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤： (1) 先求析取范式（合取范式）先求析取范式（合取范式） (2) 将不是极小项（极大项）的简单合取式（简将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等. (3

18、) 极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，并）表示，并按角标从小到大顺序排序按角标从小到大顺序排序. a22主析取范式与主合取范式主析取范式与主合取范式( (续续) )用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤： (1) 先求析取范式先求析取范式 (2) 删除析取范式中所有为永假的简单合取式删除析取范式中所有为永假的简单合取式 (3)用等幂律化简简单合取式中同一命题变元的重用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如复出现为一次出现，如ppp。 (4) 用同一律补进简单合取式中未出现的所有命题用同一律补进简单合取式中未出现的所有命

19、题变元，如变元，如q，则，则pp（ qq)，并用分配律展，并用分配律展开之，将相同的简单合取式的多次出现化为一次开之，将相同的简单合取式的多次出现化为一次出现，出现， 这样得到了给定公式的主析取范式。这样得到了给定公式的主析取范式。a23从从A的主析取范式求其主合取范的主析取范式求其主合取范式的步骤式的步骤n(a)求出求出A的主析取范式中设有包含的小的主析取范式中设有包含的小项。项。(b) 求出与求出与(a)中小项的下标相同的大项。中小项的下标相同的大项。(c) 做做(b)中大项之合取，即为中大项之合取，即为A的主合取范的主合取范式。式。例如，例如，(pq) qm1 m3，则，则(pq) qM

20、0 M2。a24求公式的主范式求公式的主范式例例 求公式求公式 A=(pq)r的主析取范式与主合的主析取范式与主合 取范式取范式. . (1) 求主析取范式求主析取范式 (pq)r (p q) r , （析取范式）（析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 , a25求公式的主范式求公式的主范式( (续续) ) 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（主析取范式）主析取范式） a26求公

21、式的主范式求公式的主范式( (续续) ) (2) 求求A的主合取范式的主合取范式 (pq)r (p r) (q r) , （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2, a27求公式的主范式求公式的主范式( (续续) ) q r (pp) q r (p q r) ( p q r) M0 M4 , 代入并排序，得代入并排序，得 (pq)r M0 M2 M4 （主合取范式）（主合取范式） a28主范式的用途主范式的用途与真值表相同与真值表相同 (1) 求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值 例如例如 (pq)r m1 m3 m5 m6

22、m7， 其成真赋值为其成真赋值为001, 011, 101, 110, 111， 其余的赋值其余的赋值 000, 010, 100为为成假赋值成假赋值. 类似地，由主合取范式也可立即求出成类似地，由主合取范式也可立即求出成 假赋值和成真赋值假赋值和成真赋值. a29主范式的用途主范式的用途( (续续) ) (2) 判断公式的类型判断公式的类型 设设A含含n个命题变项，则个命题变项，则 A为重言式为重言式A的主析取范式含的主析取范式含2n个极小项个极小项 A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式 A的主析取范式为的主析取范式为0 A的主合析取范式含的主合析取范式含2n个极大项个极大项

23、A为非重言式的可满足式为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项的主合取范式中至少含一个且不含全部极大项 a30主范式的用途主范式的用途( (续续) )例例 用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值： 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显见，中的两公式等值，而的不等值显

24、见，中的两公式等值，而的不等值. (3) 判断两个公式是否等值判断两个公式是否等值说明：说明： 由公式由公式A的主析取范式确定它的主合取范式，反之亦然的主析取范式确定它的主合取范式，反之亦然. 用公式用公式A的真值表求的真值表求A的主范式的主范式.a31主范式的用途主范式的用途( (续续) ) 例例 某公司要从赵、钱、孙、李、周五名新毕某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习业的大学生中选派一些人出国学习. 选派必须选派必须满足以下条件：满足以下条件： (1)(1)若赵去，钱也去；若赵去，钱也去； (2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去； (3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人； (4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去； (5)(5)若周去，则赵、钱也去若周去，则赵、钱也去. 试用主析取范式法分析该公司如何选派他们出试用主析取范式法分析该公司如何选派他