2第二章 命题逻辑等值演算

第二章 命题逻辑等值演算,Propositional Equivalences,,2.1 等值式,定义2.1 设A,B是两个命题公式，若A，B构成的等价式A  B为重言式，则称A与B是等值的，记作A B 即A B的充要条件是A  B为重言式试证明: ﹁(p∨q) 和(﹁p ∧ ﹁q)是等值的.这一等值式是命题的 De Morgan 定律之一.,2.1 等值式,因为对于p 和q的各种真值指派,命题 ﹁(p∨q)和(﹁p∧﹁q)的真值都是相同的. 所以它们在逻辑上是相等的.,2.1 等值式,证明命题 p→q 和 ﹁p∨q 是等值的.,因为对于p 和q的各种真值指派,命题 p→q和﹁p∨q的真值都是相同的. 所以它们在逻辑上是相等的.,2.1 等值式,1.双重否定律 A ﹁﹁A 2.幂等律 AA ∨A AA ∧ A3.交换律 A∨B B∨A A∧B B ∧ A 4.结合律 (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) A A∧ (A∨B)A,2.1 等值式,8.零律 A ∨1  1 A ∧0  09.同一律 A ∨0  A A ∧1 A 10.排中律 A ∨ ﹁ A 111.矛盾律 A ∧ ﹁A012.蕴含等值式 A→B  ﹁A ∨B13.等价等值式 A B  (A→B) ∧ (B→A)14.假言易位 A→B  ﹁B → ﹁A15.等价否定等值式 A B ﹁A  ﹁B 16.归谬论 (A→B) ∧ (A→﹁B)  ﹁A,2.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∧D)(A∧B)∨(A∧﹁ B) A(A∨B)∧(A∨﹁ B) A,2.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、命题公式的化简,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人百米竞赛，观众甲、乙、丙预测比赛的名次为：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四比赛结束后发现甲、乙、丙各对一半，试问实际名次如何（假设无并列名次）？,2.1 等值式,一、命题公式的对偶性及其对偶处理定义 在仅含有联结词, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A,例：A：（P ∧ ﹁ Q）∨ Q B：（P ∨ Q ）∧0 A * : （P ∨ ﹁ Q) ∧ Q B * ：（P ∧ Q）∨ 1,2.1 等值式,定理 设A和A*互为对偶式，p1,p2,…,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则 (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 命题变项及其否定统称作文字仅由有限个文字构成的析取式称作简单析取式，仅由有限个文字构成的合取式称作简单合取式文字(literal)/符号(symbol)：如：p , ﹁ q大项（large item）/简单析取式（ disjunctive form ）:如：p , ﹁ q , p ∨ q ∨ r小项（small item）/简单合取式（ conjunctive form ）:如：p , p ∧ ﹁ q , p ∧ q ∧ r,,2.2 析取范式与合取范式,定理2.1（1）一个简单析取式是重言式它同时含有某个命题变项及其否定式2）一个简单合取式是矛盾式它同时含有某个命题变项及其否定式为方便起见，有时用Ai表示一个简单析取/合取式 设Ai为： p ∨ q ∨ ﹁ r ∨ s ∨ ﹁ p或设Ai为： p ∧ q ∧ ﹁ r ∧ s ∧ ﹁ p,,2.2 析取范式与合取范式,定义2.3 （1）由有限个简单合取式构成的析取式称作析取范式2）由有限个简单析取式构成的合取式称作合取范式3）析取范式与合取范式统称为范式。

2.2 析取范式与合取范式,定理2.3（范式存在定理）任意一个命题公式都存在与之等值的合取范式和析取范式求范式的步骤：消去联结词→，↔（若存在）消去否定号（双重否定律）或内移（德摩根律）利用分配律,2.2 析取范式与合取范式,例：求(p  q)  r的析取/合取范式 原式((p  q)  r) ∧ (r (p  q) )(﹁(p  q) ∨ r) ∧(﹁ r ∨(p  q) )(﹁ (﹁ p ∨ q) ∨ r) ∧(﹁ r ∨﹁p ∨ q )((p ∧ ﹁ q) ∨ r) ∧(﹁ r ∨﹁p ∨ q )((p∨r)∧(﹁ q∨r)∧(﹁ r∨﹁p∨q ) (合取范式)((p∧﹁ q) ∧(﹁ r∨﹁p ∨ q ) )∨ (r ∧(﹁ r∨﹁p∨q ) )(p∧﹁ q ∧﹁ r )∨ (r ∧﹁p) ∨(r ∧ q ) (析取范式),,2.2 析取范式与合取范式,定义2.4 在含有n个命题变项的简单合取式（简单析取式）中， 若每个命题变项和它的否定式不同时出现， 而二者之一必出现一次， 且第i个命题变项或它的否定式出现在从左算起 的第i位上， 称这样的简单合取式（简单析取式）为极小项（极大项）。

2.2 析取范式与合取范式,可以观察到：每个极小项，如p1 ∧ p2 ∧ p3 ∧… ∧ pn,有且仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进制数为i，就将所对应的极小项记作mi.(参见表2.3 、2.4 )每个极大项，如p1 ∨ p2 ∨ p3 ∨ … ∨ pn,有且仅有一个成假赋值，若成假赋值所对应的二进制数转化为十进制数为i，就将所对应的极小项记作Mi2.2 析取范式与合取范式,定理2.4 极小项与极大项关系 设mi和Mi是命题变项p1 ， p2 ，… ，pn形成的极小项和极大项，则 ﹁ mi  Mi ， ﹁ Mi  mi,,2.2 析取范式与合取范式,定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的证明见P31,,主析取范式的求取：求A的析取范式A'补充命题变元（以满足极小项的定义 ） 形式化简（将重复出现的命题变项、矛盾式、及重复出现的小项都消去）顺序排序，用mi或∑（角码）表示2.2 析取范式与合取范式,例：求(p  q)  r的主析取/合取范式1）接前(p∧﹁ q ∧﹁ r)∨ (r ∧﹁p)∨(r∧q ) (析取范式),(p∧﹁q∧﹁r)∨((q∨﹁q)∧(r∧﹁p))∨((p∨﹁p)∧(r∧q)),(p∧﹁q∧﹁r)∨(﹁p∧q∧r)∨(﹁p∧﹁q∧r)∨ (p∧q∧r)∨(﹁ p∨q∧r),(p∧﹁q∧﹁r)∨(﹁p∧q∧r)∨(﹁p∧﹁q∧r)∨(p∧q∧r), m1∨ m3∨m4∨m7 (主析取范式),,主合取范式的求取求A的合取范式A'补充命题变元（以满足极大项的定义 ） 形式化简（将重复出现的命题变项、矛盾式、及重复出现的大项都消去）顺序排序，用Mi或∏（角码）表示。

2.2 析取范式与合取范式,（2）主合取范式接前(p∨r)∧(﹁ q∨r)∧(﹁ r∨﹁p∨q ) (合取范式）((p∨r)∨(q∧﹁q))∧((p∧﹁p)∨(﹁q∨r))∧(﹁r∨﹁p∨q) (p∨q∨r)∧(p∨﹁q∨r)∧(﹁p∨﹁q∨r)∧(p∨﹁q∨r) ∧(﹁p∨q ∨﹁ r )(p∨q∨r)∧(p∨﹁q∨r)∧(﹁p∨﹁q∨r)∧(﹁p∨q∨﹁ r ) M0∧M2∧M5∧ M6练习：求公式p  q的主析取范式与主合取范式,2.2 析取范式与合取范式,主析取范式的用途：求公式的成真与成假赋值（可以用真值表求主析取范式）判断公式的类型（例2.10）A为重言式当且仅当主析取范式含全部2n个极小项A为矛盾式当且仅当主析取范式不含任何极小项A为可满足式当且仅当主析取范式中至少含一个极小项,。