命题逻辑等值演算ppt课件.ppt

《命题逻辑等值演算ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、漳州师范学院计算机科学与工程系第二章命题逻辑等值演算2021/10/5第二章命题逻辑等值演算等值式析取范式与合取范式联结词完备集可满足性问题与消解法知识点：等值式、置换规则、等值演算、(主)析取范式、(主)合取范式、联结词完备集、其它联结词、可满足性问题、消解法教学要求：深刻理解和掌握命题逻辑中的基本概念教学重点：等值演算、(主)析取范式、(主)合取范式学时:42021/10/5§2.1等值式定义2.1设A,B是两个命题公式,若A,B构成的等价式AB为重言式,则称A与B是等值的,记为AB16组(24个)重要的等值式双重否定律A⇔┐┐A幂等律A⇔A∨A,A⇔A∧A交换律A∨B⇔B

2、∨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®2021/10/5§2.1等值式同一律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

3、)⇔┐A代入实例：例如在蕴涵等值式中1.取A=p,B=q时，得到等值式p→q⇔┐p∨q2.取A=p→q,B=┐p时，得到等值式(p→q)→┐p⇔┐(p→q)∨┐p®2021/10/5§2.1等值式判别两个公式是否等值的方法真值表法等值演算以一组基本的又是重要的重言式为基础进行公式之间的演算置换规则：设Ф(A)是含公式A的命题公式Ф(B)是用公式B置换了Ф(A)中的A后得到的命题公式若B⇔A,则Ф(B)⇔Ф(A)代入规则：在一个重言式(矛盾式)中，将同一命题变项全部用同一个命题公式替换后，得到的公式仍是重言式(矛盾式)®2021/10/5§2.1等值式例1用等值演算法验证等值式(p∨

4、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)®2021/10/5§2.2析取范式与合取范式每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形--范式范式有两种析取范式合取范式文字:命题变项及其否定统称作文字。简单析取式:仅有有限个文字构成的析取式。简单合取式:

5、仅有有限个文字构成的合取式。析取范式:由有限个简单合取式构成的析取式。合取范式:由有限个简单析取式构成的合取式。注意:一个文字既是简单析取式，又是简单合取式。一个公式的析取范式或合取范式不是唯一的。p,┐pp∧┐q∧rp∨┐q∨r(p∧┐q)∨(p∧r)(p∨┐q)∧(p∨r)®2021/10/5§2.2析取范式与合取范式一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式范式存在定理:任一命题公式都存在着与之等值的析取范式与合取范式求范式可使用如下步骤:1.消去联结词→,↔2.否定号的消去（利用双重否定律）或内移（利用

6、德摩根）3.利用分配律：利用∧对∨的分配律求析取范式利用∨对∧的分配律求合取范式®2021/10/5§2.2析取范式与合取范式极小项:在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上,称这样的简单合取式为极小项。极大项:在含有n个命题变项的简单析取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上,称这样的简单析取式为极大项。主析取范式:设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该

7、析取范式为主析取范式。主合取范式:设由n个命题变项构成的合取范式中所有的简单析取式都是极大项，则称该合取范式为主合取范式。®2021/10/5§2.2析取范式与合取范式p,q,r形成的极小项与极大项设mi与Mi是命题变项p1,p2,…,pn形成的极小项和大项，则┐mi⇔Mi，┐Mi⇔mi®2021/10/5§2.2析取范式与合取范式任何命题公式都存在与之等值的主析取范式和主合取范式并且是唯一的。注意：由公式的主析取范式求主合取范式反之，也可以由公式的主合取范式确定主析