哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）02 命题逻辑等值演算

哈尔滨理工大学呻斛生課程 离影数 第2章命题逻辑等值演算 O计算机系

第2章 命题逻辑等值演算 离 散 数 学 哈尔滨理工大学本科生课程 计算机系

本章说可 口本章的主要内容 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式、主析取范式与主合取范式 联结词完备集(不讲) 口本章与后续各章的关系 是第一章的抽象与延伸 是后续各章的现行准备

本章说明 ❑本章的主要内容 – 等值式与基本的等值式 – 等值演算与置换规则 – 析取范式与合取范式、主析取范式与主合取范式 – 联结词完备集(不讲) ❑本章与后续各章的关系 – 是第一章的抽象与延伸 – 是后续各章的现行准备

2.1等值式 口两公式什么时候代表了同一个命题呢? 口抽象地看,它们的真假取值完全相同时即代 表了相同的命题。 口设公式A,B共同含有n个命题变项,可能对A或 B有哑元,若A与B有相同的真值表,则说明在 2n个赋值的每个赋值下,A与B的真值都相同 。于是等价式AB应为重言式

2.1 等值式 ❑两公式什么时候代表了同一个命题呢？ ❑抽象地看，它们的真假取值完全相同时即代 表了相同的命题。 ❑设公式A,B共同含有n个命题变项，可能对A或 B有哑元，若A与B有相同的真值表，则说明在 2 n个赋值的每个赋值下，A与B的真值都相同 。于是等价式AB应为重言式

等值的定义及说明 定义2.1设A,B是两个命题公式,若A,B构成的等 价式AB为重言式,则称A与B是等值的,记作 A→B 说口定义中,A,B,分都是元语言符号 明 日A或B中可能有哑元出现。 p-q台(1pVq)∨(r∧r) r为左边公式中的哑元。 口用真值表可以验证两个公式是否等值

等值的定义及说明 定义2.1 设A,B是两个命题公式，若A,B构成的等 价式AB为重言式，则称A与B是等值的，记作 AB。 说 明 ❑定义中,A,B,都是元语言符号。 ❑A或B中可能有哑元出现。 p→q  (┐p∨q)∨(┐r∧r) r为左边公式中的哑元。 ❑用真值表可以验证两个公式是否等值

例题 例2.1判断下面两个公式是否等值 (p∨q)与1p∧-q 等值 解答 011 1010 0111 000 1000 1111 嗍口在用真值表法判断AB是香为重言式时,真值 表的最后一列可以省略

例题 例2.1 判断下面两个公式是否等值 ┐(p∨q) 与 ┐p∧┐q 解答 说 明 ❑在用真值表法判断AB是否为重言式时，真值 表的最后一列可以省略。 等值

例题 例题2.2判断下列各组公式是否等值 (1)p→(a→r)与(p∧q)→r 等值 (2)(p→q)→r与(p∧q)→r 不等值 解答 pqrp→(q+r)(∧a→r(p→q)→r 000 0001111 0110011 1010101 0 11111101 01011101

例题 例题2.2 判断下列各组公式是否等值 (1)p→(q→r)与(p∧q)→r (2)(p→q)→r与(p∧q)→r 解答 等值 不等值

基本等值式 1.双重否定律 A分1-A 2幂等律 A今A∨A,AA∧A 3交换律 AVB BVA A∧B分B∧A 4.结合律 (A∨B)VG仝AV(BVc) (A∧B)∧G仝A∧(B∧c 5.分配律 A∨(B∧c)分(AVB)∧(AV0) (∨对∧的分配律) A∧(B∨0)分(A∧B)V(AA) (∧对的分配律) 6.德·摩根律 (AVB)-A∧-B (A∧B)分1AV-B 7.吸收律 AV(A∧B)分→A,A∧(AVB)分A

基本等值式 1.双重否定律 A  ┐┐A 2.幂等律 A  A∨A, A  A∧A 3.交换律 A∨B  B∨A， A∧B  B∧A 4.结合律 (A∨B)∨C  A∨(B∨C) (A∧B)∧C  A∧(B∧C) 5.分配律 A∨(B∧C)  (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C)  (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律 ┐(A∨B)  ┐A∧┐B ┐(A∧B)  ┐A∨┐B 7.吸收律 A∨(A∧B)  A，A∧(A∨B)  A

基本等值式 8.零律 A∨11,A∧00 9.同一律 AV0分>A,A∧1A 10.排中律 AV-A台1 11.矛盾律 A∧_A分0 12.蕴涵等值式 A→B台-AVB 13.等价等值式 A<>B分(A→B)∧(B→A) 14.假言易位 A→B-B→1A 15.等价否定等值式AB分1AB 16.归谬论 (A→B)∧(A→B)分1A

基本等值式 8.零律 A∨1  1,A∧0  0 9.同一律 A∨0  A，A∧1  A 10.排中律 A∨┐A  1 11.矛盾律 A∧┐A  0 12.蕴涵等值式 A→B  ┐A∨B 13.等价等值式 AB  (A→B)∧(B→A) 14.假言易位 A→B  ┐B→┐A 15.等价否定等值式 AB  ┐A┐B 16.归谬论 (A→B)∧(A→┐B)  ┐A

对偶原理 个逻辑等值式,如果只含有、V、∧、0、1 那么同时 把∨和∧互换 把0和1互换 得到的还是等值式

对偶原理 一个逻辑等值式，如果只含有┐、∨、∧、0、1 那么同时 把∨和∧互换 把0和1互换 得到的还是等值式

°等值演与置换规则 口各等值式都是用元语言符号书写的,其中A,B,C可以代表任 意的公式,称这样的等值式为等值式模式。 口每个等值式模式都给出了无穷多个同类型的具体的等值式。 例如,在蕴涵等值式A→B台AVB中, 取A=p,B=q时,得等值式p→q分pVq 取A=p∨q∨r,B=p∧q时,得等值式 ( pAvr)→(p∧q)台-(p∨qVr)V(p∧q) 口这些具体的等值式都被称为原来的等值式模式的代入实例。 口由已知的等值式推演出另外一些等值式的过程为等值演算。 口置换规则设Φ(A)是含公式A的命题公式,中(B)是用公式B 置换了Φ(A中所有的A后得到的命题公式,若B→A,则 Φ(B)→Φ(A)

等值演算与置换规则 ❑ 各等值式都是用元语言符号书写的，其中A,B,C可以代表任 意的公式，称这样的等值式为等值式模式。 ❑ 每个等值式模式都给出了无穷多个同类型的具体的等值式。 例如，在蕴涵等值式 A→B┐A∨B 中， 取A=p，B=q时，得等值式 p→q┐p∨q 取A=p∨q∨r，B=p∧q时，得等值式 (p∨q∨r)→(p∧q)  ┐(p∨q∨r)∨(p∧q) ❑ 这些具体的等值式都被称为原来的等值式模式的代入实例。 ❑ 由已知的等值式推演出另外一些等值式的过程为等值演算。 ❑ 置换规则 设Φ(A)是含公式A的命题公式，Φ(B)是用公式B 置换了Φ(A)中所有的A后得到的命题公式，若BA，则 Φ(B)Φ(A)