命题逻辑等值演算.ppt

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

1、第二章命题逻辑等值演算PropositionalEquivalences2.1等值式定义2.1设A,B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B是等值的，记作AB。即AB的充要条件是AB为重言式。试证明:﹁(p∨q)和(﹁p∧﹁q)是等值的.这一等值式是命题的DeMorgan定律之一.2.1等值式pq﹁(p∨q)﹁p∧﹁q0011010010001100因为对于p和q的各种真值指派,命题﹁(p∨q)和(﹁p∧﹁q)的真值都是相同的.所以它们在逻辑上是相等的.2.1等值式证明命题p→q和﹁p∨q是等值的.pq﹁p∨qp→q00110

2、11110001111因为对于p和q的各种真值指派,命题p→q和﹁p∨q的真值都是相同的.所以它们在逻辑上是相等的.2.1等值式1.双重否定律A﹁﹁A2.幂等律AA∨AAA∧A3.交换律A∨BB∨AA∧BB∧A4.结合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧A)5.分配律A∨(B∧C)(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)6.德摩根律﹁(A∨B)﹁A∧﹁B﹁(A∧B)﹁A∨﹁B7.吸收律A∨(A∧B)AA∧(A∨B)A2.1等值式8.零律A∨11A∧009.同一律A∨0AA∧1A10.排中

3、律A∨﹁A111.矛盾律A∧﹁A012.蕴含等值式A→B﹁A∨B13.等价等值式AB(A→B)∧(B→A)14.假言易位A→B﹁B→﹁A15.等价否定等值式AB﹁A﹁B16.归谬论(A→B)∧(A→﹁B)﹁A2.1等值式由已知的等值式推演出另外一些等值式的过程为等值演算。置换规则：设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，若BA，则(B)(A)。(A∧B)∨(C∧D)(A∨C)∧(A∨D)∧(B∨C)∧(B∨D)(A∨B)∧(C∨D)(A∧C)∨(A∧D)∨(B∧C)∨(B∧

4、D)(A∧B)∨(A∧﹁B)A(A∨B)∧(A∨﹁B)A2.1等值式判断命题公式逻辑等价的方法：1、真值表2、命题公式的演算基本等值定理；公式的代入不变性；等值关系的传递性。2.1等值式试证明:﹁(p∨(﹁p∧q))和﹁p∧﹁q是等值的2.1等值式证明等值式例：验证p(qr)(p∧q)r右﹁(p∧q)∨r(蕴涵等值式)﹁p∨﹁q∨r(德摩根律)﹁p∨(﹁q∨r)(结合律)﹁p∨(qr)(蕴涵等值式)p(qr)(蕴涵等值式)2.1等值式命题公式逻辑等价关系的应用：1、判定是否逻辑等价；2、判断是否为重言式或矛盾式；3、命题公式的化

5、简2.1等值式试证明(p∧q)→(p∨q)是重言式.2.1等值式例：判断公式(pq)∧pq的类型(可见例2.5)原式﹁((pq)∧p)∨q﹁((﹁p∨q)∧p)∨q﹁(﹁p∨q)∨﹁p∨q(p∧﹁q)∨﹁p∨q(p∨﹁p)∧(﹁p∨﹁q)∨q1∧(﹁p∨﹁q)∨q(﹁p∨﹁q)∨q﹁p∨(﹁q∨q)﹁p∨11为重言式2.1等值式例：什麽，如果她不来那么我也不去，没有那回事。P：她来。Q：我去。﹁(﹁P﹁Q)﹁(P∨﹁Q)﹁P∧Q结论:她不来,我去.P24例2.4、2.6例：A，B，C，D4人百米竞赛，观众甲、乙、丙预测比赛的

6、名次为：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比赛结束后发现甲、乙、丙各对一半，试问实际名次如何（假设无并列名次）？2.1等值式一、命题公式的对偶性及其对偶处理。定义在仅含有联结词,∧,∨的命题公式A中，将∨换成∧,∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)*还原成A例：A：（P∧﹁Q）∨QB：（P∨Q）∧0A*:（P∨﹁Q)∧QB*：（P∧Q）∨12.1等值式定理设A和A*互为对偶式，p1,p2,…,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数

7、形式，则(1)A(p1,p2,…,pn)A*(p1,p2,…,pn)(2)A(p1,p2,…,pn)A*(p1,p2,…,pn)定理（对偶原理）设A，B为两个命题公式，若AB，则A*B*.例如，设A(p,q,r)p∧(﹁q∨r)例：(p∧q)∨(﹁p∨(﹁p∨q))﹁p∨q则：(p∨q)∧(﹁p∧(﹁p∧q))﹁p∧q二、命题公式的进一步分类。命题公式的标准化——范式2.2析取范式与合取范式定义2.2命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式，仅由有限个文字构成的合取式称作简单合取式文字(litera

8、l)/符号(symbol)：如：p,﹁q大项（largeitem）