1.6 一阶逻辑等值演算

等值演算

等值式

定义2.1 若等价式 $A\leftrightarrow B$ 是重言式，则称 $A$ 与 $B$ 等值，记作 $A\iff B$，并称 $A\iff B$ 是等值式。

设公式 $A,B$ 共同含有 $n$ 个命题变项，$A$ 或 $B$ 可能有哑元。若 $A$ 与 $B$ 有相同的真值表，则说明在所有 $2^n$ 个赋值下，$A$ 与 $B$ 的真值都相同，因而等价式 $A\leftrightarrow B$ 为重言式。

基本等值式（24个）

双重否定律

$\neg \neg A\iff A$

幂等律

$A\vee A\iff A$, $A\wedge A\iff A$

交换律

$A\vee B\iff B\vee A$, $A\wedge B\iff B\wedge A$

结合律

$(A\vee B)\vee C\iff A\vee (B\vee C)$, $(A\wedge B)\wedge C\iff A\wedge (B\wedge C)$

分配律

$A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$, $A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$

德摩根律

$\neg (A\vee B)\iff \neg A\wedge \neg B$, $\neg (A\wedge B)\iff \neg A\vee \neg B$

吸收律

$A\vee (A\wedge B)\iff A$, $A\wedge (A\vee B)\iff A$

零律

$A\vee 1\iff 1$, $A\wedge 0\iff 0$

同一律

$A\vee 0\iff A$, $A\wedge 1\iff A$

排中律

$A\vee \neg A\iff 1$

矛盾律

$A\wedge \neg A\iff 0$

蕴涵等值式

$A\to B\iff \neg A\vee B$

等价等值式

$A\leftrightarrow B\iff (A\to B)\wedge (B\to A)$

假言易位

$A\to B\iff \neg B\to \neg A$

等价否定等值式

$A\leftrightarrow B\iff \neg A\leftrightarrow \neg B$

归谬论

$(A\to B)\wedge (A\to \neg B)\iff \neg A$

等值演算与置换规则

等值演算

由已知的等值式推演出新的等值式的过程。

等值演算的基础

1. 等值关系的性质：自反性、对称性、传递性
2. 基本的等值式
3. 置换规则

置换规则

设 $\Phi (A)$ 是含公式 $A$ 的命题公式，$\Phi (B)$ 是用公式 $B$ 置换 $\Phi (A)$ 中 $A$ 的某些出现（未必全部）后得到的命题公式。若 $B\iff A$，则 $\Phi (B)\iff \Phi (A)$。

判断公式类型

• $A$ 为矛盾式当且仅当 $A\iff 0$
• $A$ 为重言式当且仅当 $A\iff 1$

链接到

• 上一个知识点：1.5 一阶逻辑基本概念
• 下一个知识点：1.7 一阶逻辑推理
• 相关知识点：2.2 集合基本运算