1、1.3 命题逻辑等值演算命题逻辑等值演算等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则第1页1等值式等值式定义定义 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称，并称AB是是等值式等值式说明：定义中，说明：定义中，A,B,均为元语言符号均为元语言符号,A或或B中中可能有哑元出现可能有哑元出现.比如，在比如，在(pq)(p q)(r r)中，中，r为左边为左边公式哑元公式哑元.用真值表可验证两个公式是否等值用真值表可验证两个公式是否等值请验证：请验证：p(qr)(p q)r p(qr)(pq)r 第2页2基本等值式基本等值式双重否定律双重
2、否定律: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)第3页3基本等值式基本等值式(续续)德德摩根律摩根律:(A B)AB (A B)AB吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11,A 00 同一律同一律:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA0第4页4基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:ABA B等价等值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等
3、值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A注意注意:A,B,C代表任意命题公式代表任意命题公式切记这些等值式是继续学习基础切记这些等值式是继续学习基础第5页5等值演算与置换规则等值演算与置换规则等值演算等值演算:由已知等值式推演出新等值式过程由已知等值式推演出新等值式过程置换规则置换规则：若：若AB,则则(B)(A)等值演算基础：等值演算基础：(1)等值关系性质：自反、对称、传递等值关系性质：自反、对称、传递 (2)基本等值式基本等值式 (3)置换规则置换规则 第6页6应用举例应用举例证实两个公式等值证实两个公式等值例例1 证实证实 p(qr)(p q)r证证 p(qr)p(
4、q r)（蕴涵等值式，置换规则）（蕴涵等值式，置换规则）(pq)r （结合律，置换规则）（结合律，置换规则）(p q)r （德（德 摩根律，置换规则）摩根律，置换规则）(p q)r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则）说明说明:也能够从右边开始演算（请做一遍）也能够从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出 熟练后，基本等值式也能够不写出熟练后，基本等值式也能够不写出第7页7应用举例应用举例证实两个公式不等值证实两个公式不等值例例2 证实证实:p(qr)(pq)r 用等值演算不能直接证实两个公式不等值用等值演算不能直接证实两个公式
5、不等值,证实两证实两个公式不等值基本思想是找到一个赋值使一个成个公式不等值基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一 真值表法（自己证）真值表法（自己证）方法二方法二 观察赋值法观察赋值法.轻易看出轻易看出000,010等是左边等是左边成真赋值，是右边成假赋值成真赋值，是右边成假赋值.方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.第8页8应用举例应用举例判断公式类型判断公式类型例例3 用等值演算法判断以下公式类型用等值演算法判断以下公式类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德（德 摩
6、根律）摩根律）p(qq)（交换律，结合律）（交换律，结合律）p 0 （矛盾律）（矛盾律）0 （零律）（零律）由最终一步可知，该式为矛盾式由最终一步可知，该式为矛盾式.第9页9例例3(续续)(2)(pq)(qp)解解 (pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最终一步可知，该式为重言式由最终一步可知，该式为重言式.问：最终一步为何等值于问：最终一步为何等值于1？第10页10例例3(续续)(3)(p q)(pq)r)解解 (p q)(pq)r)(p(qq)r （分配律）（分配律）p 1 r （排中律）（排中律）p r （同一律）（同一
7、律）这不是矛盾式，也不是重言式，而是非重言式可这不是矛盾式，也不是重言式，而是非重言式可满足式满足式.如如101是它成真赋值是它成真赋值,000是它成假赋值是它成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一,应尽可能使演算短些应尽可能使演算短些第11页111.4 范式范式析取范式与合取范式析取范式与合取范式主析取范式与主合取范式主析取范式与主合取范式第12页12析取范式与合取范式析取范式与合取范式文字文字:命题变项及其否定总称命题变项及其否定总称简单析取式简单析取式:有限个文字组成析取式有限个文字组成
8、析取式如如 p,q,pq,p q r,简单合取式简单合取式:有限个文字组成合取式有限个文字组成合取式如如 p,q,pq,p q r,析取范式析取范式:由有限个简单合取式组成析取式由有限个简单合取式组成析取式 A1 A2Ar,其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式:由有限个简单析取式组成合取式由有限个简单析取式组成合取式 A1 A2Ar,其中其中A1,A2,Ar是是简单析取式简单析取式第13页13析取范式与合取范式析取范式与合取范式(续续)范式范式:析取范式与合取范式总称析取范式与合取范式总称公式公式A析取范式析取范式:与与A等值析取范式等值析取范式公式公式A合取范式合
9、取范式:与与A等值合取范式等值合取范式说明：说明：单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式pq r,p qr既是析取范式，又是合取范式既是析取范式，又是合取范式(为何为何?)第14页14命题公式范式命题公式范式定理定理 任何命题公式都存在着与之等值析取范式任何命题公式都存在着与之等值析取范式与合取范式与合取范式.求公求公式式A范式步骤：范式步骤：(1)消去消去A中中,（若存在）（若存在）(2)否定联结词否定联结词 内移或消去内移或消去 (3)使用分配律使用分配律 对对 分配（析取范式）分配（析取范式）对对 分配（合取范式）分配（合取范式）公式范式存在，但不惟
10、一公式范式存在，但不惟一第15页15求公式范式举例求公式范式举例例例 求以下公式析取范式与合取范式求以下公式析取范式与合取范式(1)A=(pq)r解解 (pq)r (pq)r （消去（消去）pqr （结合律）（结合律）这既是这既是A析取范式（由析取范式（由3个简单合取式组成析个简单合取式组成析取式），又是取式），又是A合取范式（由一个简单析取式合取范式（由一个简单析取式组成合取式）组成合取式）第16页16求公式范式举例求公式范式举例(续续)(2)B=(pq)r解解(pq)r (pq)r （消去第一个（消去第一个）(pq)r （消去第二个（消去第二个）(p q)r （否定号内移（否定号内移德德
11、摩根律）摩根律）这一步已为析取范式（两个简单合取式组成）这一步已为析取范式（两个简单合取式组成）继续：继续：(p q)r (p r)(q r)（对对 分配律）分配律）这一步得到合取范式（由两个简单析取式组成）这一步得到合取范式（由两个简单析取式组成）第17页172元真值函数对应真值表元真值函数对应真值表p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0
12、 1 0 1 0 1第18页18极小项与极大项极小项与极大项定义定义 在含有在含有n个命题变项简单合取式个命题变项简单合取式(简单析取式简单析取式)中，中，若每个命题变项均以文字形式出现且仅出现一次，称这若每个命题变项均以文字形式出现且仅出现一次，称这样简单合取式样简单合取式(简单析取式简单析取式)为为极小项极小项(极大项）极大项）.说明：说明：n n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项n 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值n 在极小项和极大项汉字字均按下标或字母次序排列在极小项和极大项汉字字均按下标或字母次序排列n 用用mi表示第
13、表示第i个极小项，其中个极小项，其中i是该极小项成真赋值十是该极小项成真赋值十 进制表示进制表示.用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成是该极大项成 假赋值十进制表示假赋值十进制表示,mi(Mi)称为极小项称为极小项(极大项极大项)名称名称.n mi与与Mi关系关系:mi Mi,Mi mi 第19页19极小项与极大项极小项与极大项(续续)由由p,q两个命题变项形成极小项与极大项两个命题变项形成极小项与极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p
14、 q p q 0 0 0 1 1 0 1 1M0M1M2M3极小项极小项极大项极大项第20页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
15、 0 11 1 01 1 1M0M1M2M3M4M5M6M7第21页21主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式:由极小项组成析取范式由极小项组成析取范式主合取范式主合取范式:由极大项组成合取范式由极大项组成合取范式比如，比如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3 是是主析取范式主析取范式 (p qr)(p qr)M1 M5 是是主合取范主合取范式式 A主析取范式主析取范式:与与A等值主析取范式等值主析取范式 A主合取范式主合取范式:与与A等值主合取范式等值主合取范式.第22页22主析取范式与主合取范式主析取范式与主合取范式
16、(续续)定理定理 任何命题公式都存在着与之等值主析取范任何命题公式都存在着与之等值主析取范式和主合取范式式和主合取范式,而且是唯一而且是唯一.用等值演算法求公式主范式步骤：用等值演算法求公式主范式步骤：(1)先求析取范式（合取范式）先求析取范式（合取范式）(2)将不是极小项（极大项）简单合取式（简将不是极小项（极大项）简单合取式（简 单析取式）化成与之等值若干个极小项析单析取式）化成与之等值若干个极小项析 取（极大项合取），需要利用同一律（零取（极大项合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称极小项
17、（极大项）用名称mi（Mi）表示，并）表示，并按角标从小到大次序排序按角标从小到大次序排序.第23页23求公式主范式求公式主范式例例 求公式求公式 A=(pq)r主析取范式与主合主析取范式与主合 取范式取范式.(1)求主析取范式求主析取范式 (pq)r (p q)r,（析取范式）（析取范式）(p q)(p q)(r r)(p qr)(p q r)m6 m7,第24页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（主析取范式）主析取
18、范式）第25页25求公式主范式求公式主范式(续续)(2)求求A主合取范式主合取范式 (pq)r (p r)(q r),（合取范式）（合取范式）p r p(qq)r (p q r)(pq r)M0 M2,第26页26求公式主范式求公式主范式(续续)q r (pp)q r (p q r)(p q r)M0 M4 ,代入代入并排序，得并排序，得 (pq)r M0 M2 M4 （主合取范式）（主合取范式）第27页27主范式用途主范式用途与真值表相同与真值表相同(1)求公式成真赋值和成假赋值求公式成真赋值和成假赋值 比如比如 (pq)r m1 m3 m5 m6 m7，其成真赋值为其成真赋值为001,01
19、1,101,110,111，其余赋值其余赋值 000,010,100为为成假赋值成假赋值.类似地，由主合取范式也可马上求出成类似地，由主合取范式也可马上求出成 假赋值和成真赋值假赋值和成真赋值.第28页28主范式用途主范式用途(续续)(2)判断公式类型判断公式类型 设设A含含n个命题变项，则个命题变项，则 A为重言式为重言式A主析取范式含主析取范式含2n个极小项个极小项 A主合取范式为主合取范式为1.A为矛盾式为矛盾式 A主析取范式为主析取范式为0 A主合取范式含主合取范式含2n个极大项个极大项A为非重言式可满足式为非重言式可满足式A主析取范式中最少含一个且不含全部极小项主析取范式中最少含一个
20、且不含全部极小项A主合取范式中最少含一个且不含全部极大项主合取范式中最少含一个且不含全部极大项第29页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主析取范式确定它主合取范式，反之亦然主析取范式确定它主
21、合取范式，反之亦然.用公式用公式A真值表求真值表求A主范式主范式.第30页30主范式用途主范式用途(续续)例例 某企业要从赵、钱、孙、李、周五名新毕业某企业要从赵、钱、孙、李、周五名新毕业大学生中选派一些人出国学习大学生中选派一些人出国学习.选派必须满足选派必须满足以下条件：以下条件：(1)(1)若赵去，钱也去；若赵去，钱也去；(2)(2)李、周两人中最少有一人去；李、周两人中最少有一人去；(3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人；(4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去；(5)(5)若周去，则赵、钱也去若周去，则赵、钱也去.试用主析取范式法
22、分析该企业怎样选派他们出国试用主析取范式法分析该企业怎样选派他们出国？第31页31例例(续续)解这类问题步骤为：解这类问题步骤为：将简单命题符号化将简单命题符号化 写出各复合命题写出各复合命题 写出由写出由中复合命题组成合取式中复合命题组成合取式 求求中所得公式主析取范式中所得公式主析取范式第32页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)
23、(q r)(r s)(rs)(u(p q)第33页33例例(续续)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)（分分配配律）律）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)第34页34例例(续续)得得 A B1 B2 B3 (pq r su)(p qrs u)注意：在以上演算中屡次用矛盾律注意：在以上演算中屡次用矛盾律要求：自己演算一遍要求：自己演算一遍 A (pq r su)(p qrs u)结论：由结论：由可知，可知，A成真赋值为成真赋值为00110与与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）周去（孙、李不去）.第35页35
