3命题逻辑等值演算

命题公式等值演算命题公式等值演算（Propositional Formula Equivalence）是数理逻辑领域中的一个重要概念和技巧。

本文将介绍命题公式等值演算的基本思想和常用方法，并通过一些例子来详细说明。

一、命题公式等值关系的定义在逻辑学和计算机科学中，命题公式是由包含命题变量、逻辑运算符和括号构成的表达式。

而命题公式等值关系则是指两个命题公式具有相同的真值。

换句话说，当且仅当两个命题公式在每一个赋值下具有相同的真值时，它们才是等值的。

例如，对于命题变量p和q，表达式(p∧q)∨(¬p∧¬q)和(p∨¬q)∧(¬p∨q)是等值的，因为它们在每一个赋值下的真值相同。

二、命题公式等值演算的基本规则命题公式等值演算是通过一系列基本规则来推导等值式的过程。

下面是一些常用的基本规则：1. 交换律：p∧q ≡ q∧p，p∨q ≡ q∨p2. 结合律：(p∧q)∧r ≡ p∧(q∧r)，(p∨q)∨r ≡ p∨(q∨r)3. 分配律：p∧(q∨r) ≡ (p∧q)∨(p∧r)，p∨(q∧r) ≡ (p∨q)∧(p∨r)4. 吸收律：p∧(p∨q) ≡ p，p∨(p∧q) ≡ p5. 否定律：p∨¬p ≡ T，p∧¬p ≡ F6. 德摩根定律：¬(p∧q) ≡ ¬p∨¬q，¬(p∨q) ≡ ¬p∧¬q7. 双重否定律：¬(¬p) ≡ p三、命题公式等值演算的应用命题公式等值演算是数理逻辑中的一项基础技术，可以应用于证明命题的等价关系、简化复杂的命题公式以及构造等价的命题公式等领域。

1. 证明等价关系通过命题公式等值演算，可以证明两个命题公式之间的等价关系。

例如，要证明(p∨q)∧(¬p∨q) ≡ q，可以使用分配律、交换律和吸收律等基本规则进行推导。

2. 简化命题公式当给定一个复杂的命题公式时，可以利用命题公式等值演算的基本规则来简化它，使得它更加易于理解和计算。

离散数学知识点总结（1）-命题逻辑⼀、命题命题：陈述句，有唯⼀真值/⾮真既假（不⼀定知道）简单命题/命题常元：真值确定。

命题变元p：常⽤来表⽰命题。

只有明确表⽰某个命题时才有具体的含意和确定的真值。

命题联结词/命题运算符：否定联结词┐、合取联结词∧、析取联结词∨、蕴含联结词→、与⾮联结词、或⾮联结词p→q：当且仅当p真q假时，p→q为假（因此它和┐p∨q等值）。

即p为假时，p→q必定为真⟷：当且仅当、充要条件、反之亦然⼆、命题公式命题公式/命题形式/合式公式/公式：（1）可满⾜式：⾮重⾔的可满⾜式重⾔式/永真式（2）⽭盾式/永假式（不存在成真指派）命题公式不是命题，只有当公式中的每⼀个命题变项都被赋以确定的真值时，公式的真值才被确定，从⽽成为⼀个命题。

三、命题逻辑的等值演算A⟺B：A和B有等值关系。

对任意真值指派，A与B取值相同。

A⟷B为永真式。

等值关系⼀般通过真值表法或者等值演算法得到。

⽽不等值，只能通过真值表法，找到某个真值指派使得⼀个为真⼀个为假德摩根律：┐(A∨B)⟺┐A∧┐B、┐(A∧B)⟺┐A∨┐B蕴含等值式：A→B⟺┐A∨B吸收律：A∨(A∧B)⟺A、A∧(A∨B)⟺A归谬式：(A→B)∧(A→┐B)⟺┐A例题：p→(q→r)⟺┐p∨(┐q∨r)⟺(┐p∨┐q)∨r⟺┐(p∧q)∨r⟺(p∧q)→r四、范式由有限个⽂字的析取所组成的公式称为析取式；由有限个⽂字的合取所组成的公式称为合取式形如A1∨A2∨…∨A n的公式称为析取范式DNF（其中A i为合取式）；形如A1∧A2∧…∧A n的公式称为合取范式CNF（其中A i为析取式）任⼀命题公式都存在着与之等值的析取范式和合取范式，但析取范式和合取范式可能不是惟⼀的。

极⼩项q1∧q2∧…∧q n：⼀共2n种解释，每个极⼩项只在⼀个解释下为真。

每个极⼩项对应⼀个⼆进制数，该⼆进制数正是该极⼩项真值为真的指派，即m0可表⽰┐q1∧┐q2∧…∧┐q n极⼤项q1∨q2∨…∨q n：⼀共2n种解释，每个极⼤项只在⼀个解释下为假。

1命题逻辑的等值演算这一讲讨论命题公式之间的等值关系，其中一些重要的等值关系将用于对命题公式进行等值运算和设计推理规则。

1. 等值式定义1.1 若命题公式A 和B 是恒等的布尔代数式，即在任何赋值下二者的值总相等，则称二者是等值的，记为A B A B ≡⇔或者称为等值式。

注意，等值式不是逻辑公式，而是逻辑学的公式。

显然，A ≡B 当且仅当A B ↔是永真公式。

等值关系的性质：（1） 自反性：对任何公式A ，都有 A A ≡。

（2） 对称性：若 A B ≡，则 B A ≡。

（3） 传递性：若 A B ≡且若 B C ≡，则 A C ≡。

例1.2 试证明下列等值式。

a a ⌝⌝≡证明：当a =1时，左式=101⌝⌝=⌝==右式。

当a =0时，左式=010⌝⌝=⌝==右式。

因此，左式恒等于右式。

依定义，该等值式成立。

例1.3试证明下列等值式。

()()() a b c a b a c ∧∨≡∧∨∧证明：当a =1时，左式=b c ∨，右式=b c ∨，两边相等。

当a =0时，左式=0，右式=0，两边相等。

因此，该等值式成立。

2上述两例中的证明方法可以称为代数分析法。

还有一种演算方法，可以将将左式等值地变形为右式。

这种保持公式真值的演算称为等值演算。

2. 等值演算规则：替换等值演算是将当前公式中的某个子公式替换为与之等值的公式。

替换在课本中称为置换，与抽象代数中的置换（permutation ）是不同的概念。

替换的定义如下。

定义3.1 设[] A Φ是一个命题公式，A 是出现在其中某处的一个子公式。

若用另外一个公式B 替换[] A Φ中的A ，则可得一个新公式，记为[] A Φ。

我们称这种公式变形为替换（replacement ）。

注意，这里A 是指[] A Φ中某一处出现的子公式，不是[] A Φ中所有与A 相同的子公式。

例如，将()()p q p r ⌝⌝→∨⌝⌝→中第二次出现的子公式p ⌝⌝替换为p ，得()()p q p r ⌝⌝→∨→定理3.2（替换原理）若 A B ≡，则[][] A B Φ≡Φ。