离散数学-耿素云PPT(第5版)1.3-4.ppt

11.3 命题逻辑等值演算命题逻辑等值演算等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则2等值式等值式定义定义 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称，并称AB是是等值式等值式说明：定义中，说明：定义中，A,B,均为元语言符号均为元语言符号,A或或B中中可能有哑元出现可能有哑元出现.例如，在例如，在(pq)(p q)(r r)中，中，r为左边为左边公式的哑元公式的哑元.用真值表可验证两个公式是否等值用真值表可验证两个公式是否等值请验证：请验证：p(qr)(p q)r p(qr)(pq)r 3基本等值式基本等值式双重否定律双重否定律:AA等幂律等幂律：A AA,A AA交换律交换律:A BB A,A BB A结合律结合律:(A B)CA(B C)(A B)CA(B C)分配律分配律:A(B C)(A B)(A C)A(B C)(A B)(A C)4基本等值式基本等值式(续续)德德摩根律摩根律:(A B)AB (A B)AB吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11,A 00 同一律同一律:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA05基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:ABA B等价等值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础6等值演算与置换规则等值演算与置换规则等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则：若：若AB,则则(B)(A)等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2)基本的等值式基本的等值式 (3)置换规则置换规则 7应用举例应用举例证明两个公式等值证明两个公式等值例例1 证明证明 p(qr)(p q)r证证 p(qr)p(q r)（蕴涵等值式，置换规则）（蕴涵等值式，置换规则）(pq)r （结合律，置换规则）（结合律，置换规则）(p q)r （德（德 摩根律，置换规则）摩根律，置换规则）(p q)r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则）说明说明:也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出8应用举例应用举例证明两个公式不等值证明两个公式不等值例例2 证明证明:p(qr)(pq)r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一 真值表法（自己证）真值表法（自己证）方法二方法二 观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的的成真赋值，是右边的成假赋值的成真赋值，是右边的成假赋值.方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.9应用举例应用举例判断公式类型判断公式类型例例3 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德（德 摩根律）摩根律）p(qq)（交换律，结合律）（交换律，结合律）p 0 （矛盾律）（矛盾律）0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.10例例3(续续)(2)(pq)(qp)解解 (pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？11例例3(续续)(3)(p q)(pq)r)解解 (p q)(pq)r)(p(qq)r （分配律）（分配律）p 1 r （排中律）（排中律）p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的可这不是矛盾式，也不是重言式，而是非重言式的可满足式满足式.如如101是它的成真赋值是它的成真赋值,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一,应尽量使演算短些应尽量使演算短些121.4 范式范式析取范式与合取范式析取范式与合取范式主析取范式与主合取范式主析取范式与主合取范式13析取范式与合取范式析取范式与合取范式文字文字:命题变项及其否定的总称命题变项及其否定的总称简单析取式简单析取式:有限个文字构成的析取式有限个文字构成的析取式如如 p,q,pq,p q r,简单合取式简单合取式:有限个文字构成的合取式有限个文字构成的合取式如如 p,q,pq,p q r,析取范式析取范式:由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2Ar,其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式:由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A1 A2Ar,其中其中A1,A2,Ar是是简单析取式简单析取式14析取范式与合取范式析取范式与合取范式(续续)范式范式:析取范式与合取范式的总称析取范式与合取范式的总称公式公式A的析取范式的析取范式:与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式:与与A等值的合取范式等值的合取范式说明：说明：单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式pq r,p qr既是析取范式，又是合取范式既是析取范式，又是合取范式(为什么为什么?)15命题公式的范式命题公式的范式定理定理 任何命题公式都存在着与之等值的析取范式任何命题公式都存在着与之等值的析取范式与合取范式与合取范式.求公求公式式A的范式的步骤：的范式的步骤：(1)消去消去A中的中的,（若存在）（若存在）(2)否定联结词否定联结词 的内移或消去的内移或消去 (3)使用分配律使用分配律 对对 分配（析取范式）分配（析取范式）对对 分配（合取范式）分配（合取范式）公式的范式存在，但不惟一公式的范式存在，但不惟一16求公式的范式举例求公式的范式举例例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1)A=(pq)r解解 (pq)r (pq)r （消去（消去）pqr （结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）17求公式的范式举例求公式的范式举例(续续)(2)B=(pq)r解解(pq)r (pq)r （消去第一个（消去第一个）(pq)r （消去第二个（消去第二个）(p q)r （否定号内移（否定号内移德德 摩根律）摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续：(p q)r (p r)(q r)（对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成）18极小项与极大项极小项与极大项定义定义 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式(简单析取式简单析取式)中，中，若每个命题变项均以文字的形式出现且仅出现一次，称这若每个命题变项均以文字的形式出现且仅出现一次，称这样的简单合取式样的简单合取式(简单析取式简单析取式)为为极小项极小项(极大项）极大项）.说明：说明：n n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项n 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值n 在极小项和极大项中文字均按下标或字母顺序排列在极小项和极大项中文字均按下标或字母顺序排列n 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的十是该极小项成真赋值的十 进制表示进制表示.用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成是该极大项成 假赋值的十进制表示假赋值的十进制表示,mi(Mi)称为极小项称为极小项(极大项极大项)的名称的名称.n mi与与Mi的关系的关系:mi Mi,Mi mi 19极小项与极大项极小项与极大项(续续)由由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极小项极小项极大项极大项20 由由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 1M0M1M2M3M4M5M6M721主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式:由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式:由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3 是是主析取范式主析取范式 (p qr)(p qr)M1 M5 是是主合取范主合取范式式 A的主析取范式的主析取范式:与与A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式:与与A等值的主合取范式等值的主合取范式.22主析取范式与主合取范式主析取范式与主合取范式(续续)定理定理 任何命题公式都存在着与之等值的主析取范任何命题公式都存在着与之等值的主析取范式和主合取范式式和主合取范式,并且是唯一的并且是唯一的.用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，并）表示，并按角标从小到大顺序排序按角标从小到大顺序排序.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)注意：在以上演算中多次用矛盾律注意：在以上演算中多次用矛盾律要求：自己演算一遍要求：自己演算一遍