命题逻辑等值演算.pptx

第二章命题逻辑等值演算等值式析取范式与合取范式联结词完备集可满足性问题与消解法知识点:等值式、置换规则、等值演算、(主)析取范式、(主)合取范式、联结词完备集、其它联结词、可满足性问题、消解法教学要求:深刻理解和掌握命题逻辑中的基本概念教学重点:等值演算、(主)析取范式、(主)合取范式学时:4§,B是两个命题公式,若A,B构成的等价式AB为重言式,则称A与B是等值的,记为AB16组(24个)重要的等值式双重否定律A⇔┐┐A幂等律     A⇔A∨A,A⇔A∧A交换律      A∨B⇔B∨A,A∧B⇔B∧A结合律   (A∨B)∨C⇔A∨(B∨C) (A∧B)∧C⇔A∧(B∧C)分配律 A∨(B∧C)⇔(A∨B)∧(A∨C)(∨对∧的分配律)A∧(B∨C)⇔(A∧B)∨(A∧C)(∧对∨的分配律)德摩根律 ┐(A∨B)⇔┐A∧┐B┐(A∧B)⇔┐A∨┐B吸收律      A∨(A∧B)⇔A,A∧(A∨B)⇔A零律       A∨1⇔1,A∧0⇔0®§       A∨0⇔A,A∧1⇔A排中律        A∨┐A⇔1矛盾律        A∧┐A⇔0蕴涵等值式  A→B⇔┐A∨B等价等值式  (A↔B)⇔(A→B)∧(B→A)假言易位      A→B⇔┐B→┐A等价否定等值式   A↔B⇔┐A↔┐B归谬论        (A→B)∧(A→┐B)⇔┐A代入实例:=p,B=q时,得到等值式 p→q⇔┐p∨=p→q,B=┐p时,得到等值式(p→q)→┐p⇔┐(p→q)∨┐p®§   以一组基本的又是重要的重言式为基础进行公式之间的演算置换规则:设Ф(A)是含公式A的命题公式Ф(B)是用公式B置换了Ф(A)中的A后得到的命题公式若B⇔A,则Ф(B)⇔Ф(A)代入规则:在一个重言式(矛盾式)中,将同一命题变项全部用同一个命题公式替换后,得到的公式仍是重言式(矛盾式)®§ 用等值演算法验证等值式(p∨q)→r⇔(p→r)∧(q→r)证:(p→r)∧(q→r)⇔(┐p∨r)∧(┐q∨r)(蕴涵等值式,替换规则)⇔(┐p∧┐q)∨r(分配律)⇔┐(p∨q)∨r(德摩根律)⇔(p∨q)→r(蕴涵等值式)例6 用等值演算法判断公式的类型(1)(p→q)∧p→q(2)┐(p→(p∨q))∧r(3)p∧(((p∨q)∧p)→q)®§,如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形--范式范式有两种析取范式合取范式文字:命题变项及其否定统称作文字。简单析取式:仅有有限个文字构成的析取式。简单合取式:仅有有限个文字构成的合取式。析取范式:由有限个简单合取式构成的析取式。合取范式:由有限个简单析取式构成的合取式。注意:一个文字既是简单析取式,又是简单合取式。一个公式的析取范式或合取范式不是唯一的。p,┐pp∧┐q∧rp∨┐q∨r(p∧┐q)∨(p∧r)(p∨┐q)∧(p∨r)®§:任一命题公式都存在着与之等值的析取范式与合取范式求范式可使用如下步骤:→,↔(利用双重否定律)或内移(利用德摩根):利用∧对∨的分配律求析取范式利用∨对∧的分配律求合取范式®§:在含有n个命题变项的简单合取式中,若每个命题变项和它的否定式不同时出现,而二者之一必出现且仅出现一次,且第i个命题变项或它的否定式出现在从左算起的第i位上,称这样的简单合取式为极小项。极大项:在含有n个命题变项的简单析取式中,若每个命题变项和它的否定式不同时出现,而二者之一必出现且仅出现一次,且第i个命题变项或它的否定式出现在从左算起的第i位上,称这样的简单析取式为极大项。主析取范式:设由n个命题变项构成的析取范式中所有的简单合取式都是极小项,则称该析取范式为主析取范式。主合取范式:设由n个命题变项构成的合取范式中所有的简单析取式都是极大项,则称该合取范式为主合取范式。®§,q,r形成的极小项与极大项设mi与Mi是命题变项p1,p2,…,pn形成的极小项和大项,则┐mi⇔Mi,┐Mi⇔mi®§。注意:由公式的主析取范式求主合取范式反之,也可以由公式的主合取范式确定主析取范式矛盾式无成真赋值,因而矛盾式的主合取范式含2n(n为公式中命题变项