第二章-命题逻辑等值演算.ppt

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

1、第二章命题逻辑等值演算本章的主要内容：等值式与重言蕴涵式公式的标准型--范式联结词完备集本章与其他各章的联系是第一章的抽象与延伸是后续各章的先行准备2.1等值式和重言蕴涵式一、等值式与基本的等值式1．等值式定义2.1若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式。注意：（1）符号“”与“↔”的区别与联系。“”不是联结词，AB不表示一个公式，它表示两个公式间的一种关系，即等值关系。“↔”是联结词，A↔B是一个公式。AB当且仅当A↔B是重言式。（2）可以验证等值关系是等价关系。（3）当A是重言式时，A1；当

2、A是矛盾式时，则A0。可传递性：对任意公式A,B,C，若AB，BC，则AC。对称性：对任意公式A,B，若AB，则BA。自反性：对任意公式A，有AA。2.基本的等值式双重否定律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同

3、一律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注意：要牢记各个等值式，这是继续学习的基础3.等值式的判别例用真值表法证明：(pq)pq解令：A=(pq)，B=pq，构造A，B以及AB的真值表如下：由于公式AB所标记的列全为1，因此AB。pqpq(pq)pqpqAB0001111101101001111001011010

4、0001(1)真值表法例用真值表法证明：pqpq解令A=pq，B=pq构造A，B以及AB的真值表如下：由于公式AB所标记的列全为1，因此AB.pqppqpqAB001111011111100001110111例用真值表法判断pqpq是否成立.解令A=pq，B=pq构造A，B以及AB的真值表由于公式AB所标记的列不全为1，AB不是重言式，因此AB不成立。pqpqpqpqAB0011111011001001100101100111代入规则对于重言式中的任一命题变元出现的每

5、一处均用同一命题公式代入，得到的仍是重言式。(2)等值演算法例：(pq)↔(qp)A∧BA∧B置换规则设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中的所有的A后得到的命题公式，若BA，则(B)(A)等值演算等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。(A)(pq)r(B)(p∨q)rpqp∨q(pq)r(p∨q)r例如：例：证明下列等值式：(pq)(p(pq))pq证明：(pq)(p(

6、pq))(pq)((pp)q)(结合律)(pq)(pq)(幂等律)(pq)(pq)(交换律)p(q(pq))(结合律)pq(吸收律)例：证明等值式：（pq）∧（rq）（p∨r）q证明：(pq）∧（rq）（p∨q）∧(r∨q)(蕴涵等值式)（p∧r）∨q(分配律)(p∨r)∨q(德摩根律)(p∨r)q(蕴涵等值式)所以（pq）∧（rq）（p∨r）q例：将下面程序语言进行化简：ifAthenifBthenXelseYifBthenXelseY解：该程

7、序流程图如下：StartABBXYEndFTFTFT执行X的条件：(A∧B)∨(A∧B)B∧(A∨A)B执行Y的条件：(A∧B)∨(A∧B)B∧(A∨A)BStartBXYEndTF化简结果：ifBthenXelseY练习：用等值演算法证明下列等值式：(1)q(pr)(p∧q)r(2)（pq）（p∧q）∨（p∧q）解（1）(p∧q)r（2）（p∧q）∨（p∧q）(（p∨q）∧（q∨p）)(（pq）∧（qp）)（pq）(p∧q)∨r(p∨q)∨rq∨(p

8、∨r)q(pr)二、重言蕴涵式与基本重言蕴涵式注意：符号“”和“”的区别和联系与符号“”与“↔”的区别和联系类似。“”不是联结词，“AB”不是公式，它表示公式A与B之间存在蕴涵关系。“”是