发布时间 : 星期四 文章命题逻辑的等值演算更新完毕开始阅读a8c02bf0960590c69fc3763e
命题逻辑的等值演算
这一讲讨论命题公式之间的等值关系，其中一些重要的等值关系将用于对命题公式进行等值运算和设计推理规则。 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时，左式=??1??0?1=右式。
当a=0时，左式=??0??1?0=右式。 因此，左式恒等于右式。
依定义，该等值式成立。
例1.3试证明下列等值式。
a?(b?c)?(a?b)?(a?c)
证明：当a=1时，左式=b?c，右式=b?c，两边相等。
当a=0时，左式=0，右式=0，两边相等。 因此，该等值式成立。
1
上述两例中的证明方法可以称为代数分析法。还有一种演算方法，可以将将左式等值地变形为右式。这种保持公式真值的演算称为等值演算。 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] 。
证明：对公式的层次和最外层联结词用数学归纳法。略。 证毕
3. 等值定律
在等值演算中，每一步替换都要应用一个等值式。常用的一些基本等值式可以用等值定律来描述。等值定律是等值式的共同模式，它在形式上与等值式相同，不过其中的变元表示任何命题公式，而不是命题。例如，下面的等值定律中变元A代表任何命题公式。
??A?A
这条定律表明，若将其中的变元A统一替换为任意某个公式时，则所得的总是等值式。因此，例如，根据这条定律，可得下列等值式。
(1) ??a?a(2) ??(p?q)?p?q (3) ??(c?d)?c?d2
因此，等值定律是描述一批无限多个等值式的模式。
反之，根据任何等值式，都可以确定一条对应的等值定律，只要把其中的命题变元视为命题公式变元即可。为了证明这一点，我们引入如下概念。
定义3.1 设?(a)为含变元a的命题公式，将其中a的所有出现统一替换为某公式A，所得的公式记为?(A)。这种变形操作称为代入或代换（substitution）。
依定义3.3， ?(0)表示将?(a)中的a统一替换为0后所得的公式。类似地，我们可以确定?(1)的含义。
思考：试比较替换与代入的区别。
定理3.2（代入原理） 命题逻辑等值式在代入后仍然是等值式。
证明 设?(a)与?(a) 是两个等值的命题公式，其中a是这两个公式中所含的一个变元。设A是任何命题公式。我们只需证明?(A) ??(A) 即可。首先，由?(a) ??(a) 可得
?(0) ??(0) 且?(1) ??(1) 。设?为A的任意赋值。若在赋值?下A为真，则?(A) =?(1) 且?(A) =?(1)，从而有?(A) =?(A) 。若在赋值?下A为假，则?(A) =?(0) 且?(A) =?(0)，从而有?(A) =?(A) 。因此，在任何赋值下，总有?(A) =?(A) ，所以根据定义我们有?(A) ??(A)。 证毕
定理意义：代入原理表明代入操作不改变等值式的等值性，即对等值式进行代入操作后所得的任然是等值式。因此，一个等值式可推广为一条等值定律。 4. 基本等值定律
下面这15组等值定律形式简单，但演算能力足够强大，与替换规则相配合，可以证明所有的等值式。
1） 双重否定律
??A?A
2） 幂等律
A?A?A A?A?A
3
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
证明：用代数分析法证明第一条德摩根律如下。 （1）当A=1时，左边=?B ，右边=?B ，两边相等。 （2）当A=0时，左边=1，右边=1，两边相等。 （3）因此，根据等值定律定理，该等值定律成立。
第二条德摩根律可以类似证明。 证毕
7） 吸收律
A?(A?B)?A A?(A?B)?A
证明：用代数分析法很容易证明以上两条吸收律，略。 证毕
练习4.1 除了上面7个等值定律之外，常用的还有如下8条。建议读者用代数分析法逐个验证其正确性。
8） 零律
4
A?0?0 A?1?1
9） 同一律
A?1?A A?0?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 A?B??B??A
15）归谬律
(A?B)?(A??B)??A
5. 等值演算举例
例5.1 课本第19页例2.3。用等值演算验证等值式
(p?q)?r?(p?r)?(q?r)
从左边开始演算：
读者也可以尝试从右边开始演算： 例5.2 课本第21页例2.6。推荐自学。
5