第1章命题逻新 1.3.2命题公式的等价 定义1.3.3设A和B是两个命题公式，对A和B的任一赋值， A和B的真值都相同，则称A和B是等价的或逻辑相等的，记 为A一B 可以证明，命题公式等价有下面的三条性质： (I)自反性，即对任意命题公式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一→(p→一q)的真值表，如表 1.10所示。p→(g一→p)和-p→p一→q)所在的列完全相同，它们 具有相同的真值表。所以p→(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章命题逻辑 表1.10 9 q q→p p→(q→p) p→7q 7p→(p→7q) 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台77A 2.交换律 AVB台→BVA,A∧B台B∧A 3.结合律 (AVB)VC台AV(BVC) (A∧B)∧C台A△(B△C
第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)
第1章命题逻辑 4.分配律 A∧(BVC)→(A∧B)V(A∧C) AV(B∧C)→(AVB)∧(AVC 5.德摩根律 (AVB)→A∧B (AΛB)→AVB 6.幂等律 A∧A台A,AVA台A 7.吸收律 AV(A∧B)台A,A∧(AVB)台A 8.零律 AV1台1，A∧0→0 9.同一律 AV0台A,A∧1→A 10.排中律 AVA台I 11.矛盾律 A∧7A台0 12.条件等价式 A→B台AVB 13.双条件等价式 A→B台(A→B)∧(B→A) 14.假言易位式 A→B台7B→7A 15.双条件否定等价式A←B台A←→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
第1章命题逻精 以上共23个等价式，原则上说，这些公式都可以用真值 表证明。下面仅验证德摩根律。 【例1.13】用真值表证明德摩根律(AVB)一A∧B 解：表1.11是(AVB)和-A个B的真值表，从表中可以看 出德摩根律成立。 表1.11 A B A B A∧B AVB (AVB) 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章 命题逻辑 以上共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章命题逻箱 定义1.3.4如果X是合式公式A的一部分且X本身也是合式 公式，则称X为公式A的子公式。 例如，A台q→(pV(p∧q),X台p∧q,则X是A的子公式。 定理1.3.1设X是合式公式A的子公式，若X一Y,如果将A 中的X用Y来置换，得到的公式记为B,则B与A等价，即A一B 证明：对A、B的任一赋值，X与的真值相同，而A、B 的其它部分完全相同，公式B与公式A的真值必相同。A一B 满足此定理的置换叫做等价置换。 【例1.17】用等价演算法证明p→q→(p∧q)V(-p∧q) 证明：pq→(p→q)∧(g→p) (双条件等价式) 台(pVq)∧(qVp) (条件等价式) (p∧q)V(p∧p)V(g∧q)V(g∧p)(分配律) 台p∧q)V0V0V(q∧p) (矛盾律) (p∧q)V(g∧p) (同一律) 台pΛq)V(p∧q) (交换律) p→q台p∧q)V(p∧q) 等价的传递性) 返回章目录
第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) (等价的传递性) 返回章目录