第/章命题逻辑 3.2命题公式的等价 定义1.3.3设A和B是两个命题公式,对A和B的任一赋值, A和B的真值都相同,则称4和B是等价的或逻辑相等的,记 为A≌→B 可以证明,命题公式等价有下面的三条性质 (1)自反性,即对任意命题公式A,A<A (2)对称性,即对任意命题公式A和B,若A<>B,则B→A (3)传递性,即对任意命题公式A,B和C,若A<>B, B>C,则A<>C 根据定义1.3.3,可以用真值表证明命题公式是等价的, 请看下面的例题。 【例1.12】根据等价的定义,用真值表证明 p+(q→p)<p(p→q) 证明:构造p(q和→p→(p-→-q的真值表,如表 10所示。p→(q-)和p→(p→-q)所在的列完全相同,它们 具有相同的真值表。所以(q→p)p→(p→q)
第1章 命题逻辑 1.3.2命题公式的等价 定义1.3.3 设A和B是两个命题公式，对A和B的任一赋值， A和B的真值都相同，则称A和B是等价的或逻辑相等的，记 为AB 可以证明，命题公式等价有下面的三条性质： ⑴ 自反性，即对任意命题公式A， AA ⑵ 对称性，即对任意命题公式A和B，若AB，则BA ⑶ 传递性，即对任意命题公式A，B和C，若AB， BC，则AC 根据定义1.3.3，可以用真值表证明命题公式是等价的， 请看下面的例题。 【例1.12】根据等价的定义，用真值表证明 p→(q→p)¬p→(p→¬q) 证明：构造p→(q→p)和p→(p→q)的真值表，如表 1.10所示。p→(q→p)和¬p→(p→¬q)所在的列完全相同，它们 具有相同的真值表。所以p→(q→p)p→(p→¬q)
第/章命题逻辑 表1.10 qq→pp→(→p)p→vqp→(→q) 0 0 0 111 0 0 1111 0 0 0 证明等价的另外一种方法叫做等价演算法,其基本思想 是:先用真值表证明一组基本等价式,以它们为基础进行公 式之间的演算。基本等价式常叫命题定律。下面是常用的命 题定律。 1双重否定律A<→--A 2交换律 AVB→>BVA,A∧B<→B∧A 3结合律 (AVB)VCEAV(BVC) (A∧B)∧C→AA(BAC)
第1章 命题逻辑 表1.10 p q ¬p ¬q q→p p→(q→p) p→¬q ¬p→(p→¬q) 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 证明等价的另外一种方法叫做等价演算法，其基本思想 是：先用真值表证明一组基本等价式，以它们为基础进行公 式之间的演算。基本等价式常叫命题定律。下面是常用的命 题定律。 1.双重否定律 A¬¬A 2.交换律 A∨BB∨A， A∧BB∧A 3.结合律 (A∨B)∨CA∨(B∨C) (A∧B)∧CA∧(B∧C)
第/章命题逻辑 4分配律∧(B∨C→(A∧B)∨(4A∧C) AV(B∧C<(AVB)∧(AVC) 5德摩根律 (AVB)→A∧=B A∧B)→AV=B 6幂等律 A∧A→A,AVA→>A 7吸收律(A∧B)A,A∧(AVB)→A 8零律 AV1<→1,A∧0<>0 9同一律 AV0<→4,A∧1<>A 10排中律 AV=A→1 1矛盾律 A∧=A→>0 12条件等价式A→B<→AVB 13.双条件等价式A4B>(4→B)∧(B→A) 14假言易位式A→B→=B→A 15双条件否定等价式A→BA=B
第1章 命题逻辑 4.分配律 A∧(B∨C)(A∧B)∨(A∧C) A∨(B∧C)(A∨B)∧(A∨C) 5.德摩根律 ¬(A∨B)¬A∧¬B ¬(A∧B)¬A∨¬B 6.幂等律 A∧AA，A∨AA 7.吸收律 A∨(A∧B)A， A∧(A∨B)A 8.零律 A∨11，A∧00 9.同一律 A∨0A， A∧1A 10.排中律 A∨¬A1 11.矛盾律 A∧¬A0 12.条件等价式 A→B¬A∨B 13.双条件等价式 A↔B(A→B)∧(B→A) 14.假言易位式 A→B¬B→¬A 15.双条件否定等价式 A↔B¬A↔¬B
第/章命题逻辑 以上共23个等价式,原则上说,这些公式都可以用真值 表证明。下面仅验证德摩根律 【例1.13】用真值表证明德摩根律ˉ(AVB)>-A∧-B 解:表1.11是(AVB)和→A∧-B的真值表,从表中可以看 出德摩根律成立。 表1.11 B IA B-A∧-BAVB-(AVB) A00 0 0 000 000
第1章 命题逻辑 以上共23个等价式，原则上说，这些公式都可以用真值 表证明。下面仅验证德摩根律。 【例1.13】用真值表证明德摩根律 ¬(A∨B)¬A∧¬B 解：表1.11是¬(A∨B)和¬A∧¬B的真值表，从表中可以看 出德摩根律成立。 表1.11 A B ¬A ¬B ¬A∧¬B A∨B ¬(A∨B) 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0
第/章命题逻辑 定义1.34如果X是合式公式A的一部分且X本身也是合式 公式,则称X为公式A的子公式。 例如,Aq→(pV(p∧q),Xe→p∧q,则X是4的子公式。 定理1.3设是合式公式A的子公式,若X→Y,如果将A 中的用Y来置换,得到的公式记为B,则B与A等价,即A<>B 证明:对A、B的任一赋值,X与Y的真值相同,而A、B 的其它部分完全相同,公式B与公式4的真值必相同。A<B 满足此定理的置换叫做等价置换。 【例117】用等价演算法证明p4→q(p∧q)∨(→p∧-q 证明:p4>q<(p→q)∧(q→p) (双条件等价式) (pVq)∧(=qVp) 条件等价式) 台(p∧-q∨(p/p)∨(q∧-q)∨(q∧p)(分配律) >(∧-q)V0V0V(q∧p) (矛盾律) >(∧vq)V(q∧p) (同一律) <∧q)∨(∧=q) 交换律 返回章日p4q地(PAq)V(⑦vy) 等价的传递性)
第1章 命题逻辑 定义1.3.4如果X是合式公式A的一部分且X本身也是合式 公式，则称X为公式A的子公式。 例如，Aq→(p∨(p∧q))，Xp∧q，则X是A的子公式。 定理1.3.1设X是合式公式A的子公式，若XY，如果将A 中的X用Y来置换，得到的公式记为B，则B与A等价，即AB 证明：对A、B的任一赋值，X与Y的真值相同，而A、B 的其它部分完全相同，公式B与公式A的真值必相同。AB 满足此定理的置换叫做等价置换。 【例1.17】用等价演算法证明 p↔q(p∧q)∨(p∧q) 证明： p↔q(p→q)∧(q→p) (双条件等价式) (¬p∨q)∧(¬q∨p) (条件等价式) (¬p∧¬q)∨(¬p∧p)∨(q∧¬q)∨(q∧p) (分配律) (¬p∧¬q)∨0∨0∨(q∧p) (矛盾律) (¬p∧¬q)∨(q∧p) (同一律) (p∧q)∨(¬p∧¬q) (交换律) p↔q(p∧q)∨(¬p∧¬q) (等价的传递性) 返回章目录