1.2命题逻辑等值演算.ppt
《1.2命题逻辑等值演算.ppt》由会员分享,可在线阅读,更多相关《1.2命题逻辑等值演算.ppt(32页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、本节的主要内容本节的主要内容等值式与基本的等值式等值式与基本的等值式等值演算与置换规则等值演算与置换规则联结词全功能集联结词全功能集 若若A A与与B B有相同的真值表,则说明在有相同的真值表,则说明在2 2n n个赋个赋值下,值下,A A与与B B的真值都相同的真值都相同,于是等价式于是等价式A AB B应应为重言式。为重言式。2.1等值式等值式两公式什么时候代表了同一个命题呢?两公式什么时候代表了同一个命题呢?抽象地看,它们的真假取值完全相同时抽象地看,它们的真假取值完全相同时即代表了相同的命题。即代表了相同的命题。定义定义1.10 1.10 设设A,BA,B是两个命题公式,若等价式是两个
2、命题公式,若等价式A A B B为重言式,则称为重言式,则称A A与与B B是等值的,记作是等值的,记作A AB B。1.等值的定义及说明等值的定义及说明用真值表可以验证两个公式是否等值。用真值表可以验证两个公式是否等值。判断判断A,BA,B是否等值是否等值(A AB)B)判断AB为重言式为重言式 AB的真值表最后一列全为的真值表最后一列全为1在各种赋值下,在各种赋值下,A,B取值完全相同取值完全相同 A,BA,B的真值表完全相同的真值表完全相同说明说明例例2.1 2.1 判断下面两个公式是否等值判断下面两个公式是否等值(pqpq)与与 pqpq 例题例题相等相等解答解答例题例题2.2 2.2
3、 判断下列各组公式是否等值判断下列各组公式是否等值(1)p(qr)(1)p(qr)与与(pq)rpq)r (2)(pq)r(2)(pq)r与与(pq)rpq)r 例题例题相等相等不相等不相等解答解答(1 1)双重否定律)双重否定律 A A A A(2 2)幂等律)幂等律 A A AA AA,A A AA AA(3 3)交换律)交换律 AB AB BA BA,AB AB BA BA(4 4)结合律)结合律 (AB)C(AB)C A(BC)A(BC)(AB)C (AB)C A(BC)A(BC)(5 5)分配律)分配律 A(BC)A(BC)(AB)(AC)(AB)(AC)(对对的分配律)的分配律)A
4、(BC)A(BC)(AB)(AC)(AB)(AC)(对对的分配律)的分配律)(6 6)德)德摩根律摩根律 (AB)(AB)AB AB(AB)(AB)AB AB (7 7)吸收律)吸收律 A(AB)A(AB)A A,A(AB)A(AB)A A2.基本等值式基本等值式(8 8)零律)零律 A1 A1 1 1,A0 A0 0 0(9 9)同一律同一律 A0 A0 A A。A1 A1 A A(1010)排中律)排中律 AA AA 1 1(1111)矛盾律)矛盾律 AA AA 0 0(1212)蕴涵等值式)蕴涵等值式 AB AB AB AB(1313)等价等值式)等价等值式 A AB B (AB)(BA
5、)(AB)(BA)(1414)假言易位)假言易位 AB AB BA BA(1515)等价否定等值式)等价否定等值式A AB B A ABB(1616)归谬论)归谬论 (AB)(AB)(AB)(AB)A A 其中其中A,B,CA,B,C可以代表任意的公式,称这样的等值式为可以代表任意的公式,称这样的等值式为等值式模式。等值式模式。每个等值式模式都给出了无穷多个同类型的具体的等每个等值式模式都给出了无穷多个同类型的具体的等值式。值式。例如,在蕴涵等值式例如,在蕴涵等值式 ABABAB AB 中,中,取取A=pA=p,B=qB=q时,得等值式时,得等值式 pqpqpqpq 取取A=A=pqrpqr,
6、B=B=pqpq时,得等值式时,得等值式(pqr)(pqpqr)(pq)(pqr)(pqpqr)(pq)这些具体的等值式都被称为原来的等值式模式的这些具体的等值式都被称为原来的等值式模式的一个实例。一个实例。说明说明由由已已知知的的等等值值式式推推演演出出另另外外一一些些等等值值式式 的过程为等值演算。的过程为等值演算。置置换换规规则则 :设设(A)(A)是是含含公公式式A A的的命命题题公公式式,(B)(B)是是用用公公式式B B置置换换了了(A)(A)中中所所有有的的A A后后得得 到到 的的 命命 题题 公公 式式,若若 B BA A,则则(B)(B)(A)(A)。3.3.等值演算与置换
7、规则等值演算与置换规则等值演算与置换规则等值演算与置换规则等值演算的基础等值演算的基础等值关系的性质:等值关系的性质:自反性:自反性:A AA A。对称性:若对称性:若A AB B,则,则B BA A。传递性:若传递性:若A AB B且且B BC C,则,则A AC C。基本的等值式基本的等值式置换规则置换规则等值演算的应用等值演算的应用证明两个公式等值证明两个公式等值判断公式类型判断公式类型解判定问题解判定问题关于等值演算的说明关于等值演算的说明证明两个公式等值证明两个公式等值(pq)rpq)r (pr)(qrpr)(qr)例题例题 (pq)rpq)r (pq)rpq)r(蕴含等值式、置换规
8、则)(蕴含等值式、置换规则)(pq)rpq)r(蕴含等值式、置换规则)(蕴含等值式、置换规则)(pq)rpq)r (德摩根律、置换规则)(德摩根律、置换规则)(pr)(qrpr)(qr)(分配律、置换规则)(分配律、置换规则)也可以从右边开始演算也可以从右边开始演算因为每一步都用置换规则,故可不写出因为每一步都用置换规则,故可不写出熟练后,基本等值式也可以不写出熟练后,基本等值式也可以不写出通常不用等值演算直接证明两个公式不等值通常不用等值演算直接证明两个公式不等值解答解答说明说明例例2.3 2.3 用等值演算法验证等值式用等值演算法验证等值式(pq)rpq)r (pr)(qrpr)(qr)(
9、pr)(qrpr)(qr)(pr)(qrpr)(qr)(蕴含等值式蕴含等值式)(pq)rpq)r(分配律分配律)(pq)rpq)r(德摩根律德摩根律)(pq)rpq)r(蕴含等值式蕴含等值式)例题例题解答解答方法一、真值表法。方法一、真值表法。方法二、观察法。易知,方法二、观察法。易知,010010是是(pq)rpq)r的成假赋的成假赋值,而值,而010010是是p(qrp(qr)的成真赋值,所以原不等值的成真赋值,所以原不等值式成立。式成立。例例2.4 2.4 证明:证明:(pq)rpq)r 与与 p(qrp(qr)不等值不等值方法三、通过等值演算化成容易观察真值的情况,方法三、通过等值演算
10、化成容易观察真值的情况,再进行判断。再进行判断。A=(A=(pq)rpq)r (pq)rpq)r (蕴涵等值式)(蕴涵等值式)(pq)rpq)r (蕴涵等值式)(蕴涵等值式)(pq)rpq)r (德摩根律)(德摩根律)B=B=p(qrp(qr)p(qrp(qr)(蕴涵等值式)(蕴涵等值式)pqrpqr (结合律)(结合律)000000,010010是是A A的成假赋值,而它们是的成假赋值,而它们是B B的成真赋值。的成真赋值。例题例题2.5 2.5 用等值演算判断下列公式的类型:用等值演算判断下列公式的类型:(1 1)(pq)pqpq)pq (2 2)(p(pq)rp(pq)r (3 3)p(
11、pq)p)qp(pq)p)q)(1)(1)(pq)pqpq)pq (pq)pqpq)pq (蕴涵等值式)(蕴涵等值式)(pq)p)qpq)p)q (蕴涵等值式)(蕴涵等值式)(pq)p)qpq)p)q (德摩根律)(德摩根律)(pq)p)qpq)p)q (德摩根律)(德摩根律)(pp)(qp)qpp)(qp)q(分配律)(分配律)(1(qp)q(1(qp)q (排中律)(排中律)(qq)pqq)p (同一律)(同一律)1p1p (排中律)(排中律)1 1 (零律)(零律)(重言式)(重言式)解答解答(2)(2)(p(pq)rp(pq)r (p(p pq)rpq)r (ppq)rppq)r 0r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 1.2 命题逻辑 等值 演算
限制150内