1-4 真值表与等价公式

定义 1-4.1：在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。

例题1

$\neg P \lor Q$ 的真值表。

表 1-4.1

$P$	$P$	$\neg P$	$\neg P \lor Q$
$T$	$T$	$F$	$T$
$T$	$F$	$F$	$F$
$F$	$T$	$T$	$T$
$F$	$F$	$T$	$T$

例题2

$(P \land Q) \land \neg P$ 的真值表。

表 1-4.2

$P$	$Q$	$P \land Q$	$\neg P$	$(P \land Q) \land \neg P$
$T$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$F$	$T$	$F$
$F$	$F$	$F$	$T$	$F$

例题3

$(P \land Q) \lor (\neg P \land \neg Q)$ 的真值表。

表 1-4.3

$P$	$Q$	$\neg P$	$\neg Q$	$P \land Q$	$\neg P \land \neg Q$	$(P \land Q) \lor (\neg P \land \neg Q)$
$T$	$T$	$F$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$F$	$T$	$T$

例题4

$\neg (P \land Q) \leftrightarrow (\neg P \lor \neg Q)$ 的真值表。

表 1-4.4

$P$	$Q$	$P \land Q$	$\neg (P \land Q)$	$\neg P$	$\neg Q$	$\neg P \lor \neg Q$	$\neg (P \land Q) \leftrightarrow (\neg P \lor \neg Q)$
$T$	$T$	$T$	$F$	$F$	$F$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$T$	$T$	$T$

由表 1-4.4（表 1-4.2）可以看出，有一类公式不论命题变元作何种指派，其真值永为真（假），我们把这类公式记为T（F）。

$n$ $2^n$ 种真值情况。

$\neg P \lor Q$ $P \to Q$ 的对应真值相同，如 表 1-4.5 所示。

表 1-4.5

$P$	$Q$	$\neg P \lor Q$	$P \to Q$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$
$F$	$T$	$T$	$T$
$F$	$F$	$T$	$T$

$(P \land Q) \lor (\neg P \land \neg Q)$ $P \leftrightarrow Q$ 对应的真值相同，如 表 1-4.6 所示。

表 1-4.6

$P$	$Q$	$P \leftrightarrow Q$	$(P \land Q) \lor (\neg P \land \neg Q)$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$
$F$	$T$	$F$	$F$
$F$	$F$	$T$	$T$

定义 1-4.2： $A$ $B$ $P_1, P_2, \cdots, P_n$ $A$ $B$ $P_1, P_2, \cdots, P_n$ $A$ $B$ $A$ $B$ $A \iff B$ 。

例题5

$P \leftrightarrow Q \iff (P \to Q) \land (Q \to P)$

证明，列出真值表：

表 1-4.7

$P$	$Q$	$P \to Q$	$Q \to P$	$P \leftrightarrow Q$	$(P \to Q) \land (Q \to P)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

表 1-4.7 $P \leftrightarrow Q$ $(P \to Q) \land (Q \to P)$ 真值相同，命题得证。

表 1-4.8 列出的命题定律，都可以用真值表予以验证。

表 1-4.8

定律	命题	序号
对合律	$\neg \neg P \iff P$	1
幂等律	$P \lor P \iff P, \quad P \land P \iff P$	2
结合律	$(P \lor Q) \lor R \iff P \lor (Q \lor R)$ $(P \land Q) \land R \iff P \land (Q \land R)$	3
交换律	$P \lor Q \iff Q \lor P$ $P \land Q \iff Q \land P$	4
分配律	$P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$	5
吸收律	$P \lor (P \land Q) \iff P$ $P \land (P \lor Q) \iff P$	6
德·摩根律	$\neg (P \lor Q) \iff \neg P \land \neg Q$ $\neg (P \land Q) \iff \neg P \lor \neg Q$	7
同一律	$P \lor F \iff P, \quad P \land T \iff P$	8
零律	$P \lor T \iff T, \quad P \land F \iff F$	9
否定律	$P \lor \neg P \iff T, \quad P \land \neg P \iff F$	10

例题6

验证吸收律

\begin{array}{r} P \lor (P \land Q) ⟺ P \\ P \land (P \lor Q) ⟺ P \end{array}

证明，列出真值表： 表 1-4.9

$P$	$Q$	$(P \land Q)$	$P \lor (P \land Q)$	$(P \lor Q)$	$P \land (P \lor Q)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$F$

由 表 1-4.9 可知吸收律成立。

$X$ $A$ $X$ $X$ $A$ 的子公式。

定理 1-4.1： $X$ $A$ $X \iff Y$ $A$ $X$ $Y$ $B$ $A$ $A \iff B$ 。

满足该条件的转换称为等价置换（等价代换）。

例题7

$Q \to (P \lor (P \land Q)) \iff Q \to P$

\begin{aligned} 证 明 & 设 A ： Q \to (P \lor (P \land Q)) \\ 因 为 & P \lor (P \land Q) ⟺ P \\ 故 & B ： Q \to P ， 即 A ⟺ B \end{aligned}

例题8

$(P \land Q) \lor (P \land \neg Q) \iff P$

证 明 (P \land Q) \lor (P \land \neg Q) ⟺ P \land (Q \lor \neg Q) ⟺ P \land T ⟺ P

例题9

$P \to (Q \to R) \iff Q \to (P \to R) \iff \neg R \to (Q \to \neg P)$

\begin{aligned} 证 明 P \to (Q \to R) ⟺ \neg P \lor (\neg Q \lor R) ⟺ \neg Q \lor (\neg P \lor R) ⟺ Q \to (P \to R) \\ 又 P \to (Q \to R) ⟺ \neg P \lor (\neg Q \lor R) ⟺ R \lor (\neg Q \lor \neg P) ⟺ \neg R \to (Q \to \neg P) \end{aligned}

例题10

$((P \lor Q) \land \neg (\neg P \land (\neg Q \lor \neg R))) \lor (\neg P \land \neg Q) \lor (\neg P \land \neg R) \iff T$

\begin{aligned} 证 明 原 式 左 边 & ⟺ ((P \lor Q) \land \neg (\neg P \land \neg (Q \land R))) \lor \neg (p \lor Q) \lor \neg (P \lor R) \\ ⟺ ((P \lor Q) \land (P \lor (Q \land R))) \lor \neg (P \lor Q) \lor \neg (P \lor R) \\ ⟺ ((P \lor Q) \land ((P \lor Q) \land (P \lor R))) \lor \neg ((P \lor Q) \land (P \lor R)) \\ ⟺ ((P \lor Q) \land (P \lor R)) \lor \neg ((P \lor Q) \land (P \lor R)) \\ ⟺ T \end{aligned}

$P$	$Q$	$P \land Q$	$\neg P$	$(P \land Q) \land \neg P$
$T$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$F$	$T$	$F$
$F$	$F$	$F$	$T$	$F$

$P$	$Q$	$\neg P$	$\neg Q$	$P \land Q$	$\neg P \land \neg Q$	$(P \land Q) \lor (\neg P \land \neg Q)$
$T$	$T$	$F$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$F$	$T$	$T$

$P$	$Q$	$P \land Q$	$\neg (P \land Q)$	$\neg P$	$\neg Q$	$\neg P \lor \neg Q$	$\neg (P \land Q) \leftrightarrow (\neg P \lor \neg Q)$
$T$	$T$	$T$	$F$	$F$	$F$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$T$	$T$	$T$

$P$	$Q$	$P \to Q$	$Q \to P$	$P \leftrightarrow Q$	$(P \to Q) \land (Q \to P)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$P$	$Q$	$(P \land Q)$	$P \lor (P \land Q)$	$(P \lor Q)$	$P \land (P \lor Q)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$F$

$P$	$Q$	$P \land Q$	$\neg P$	$(P \land Q) \land \neg P$
$T$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$F$	$T$	$F$
$F$	$F$	$F$	$T$	$F$

$P$	$Q$	$\neg P$	$\neg Q$	$P \land Q$	$\neg P \land \neg Q$	$(P \land Q) \lor (\neg P \land \neg Q)$
$T$	$T$	$F$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$F$	$T$	$T$

$P$	$Q$	$P \land Q$	$\neg (P \land Q)$	$\neg P$	$\neg Q$	$\neg P \lor \neg Q$	$\neg (P \land Q) \leftrightarrow (\neg P \lor \neg Q)$
$T$	$T$	$T$	$F$	$F$	$F$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$T$	$T$	$T$

$P$	$Q$	$P \to Q$	$Q \to P$	$P \leftrightarrow Q$	$(P \to Q) \land (Q \to P)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$P$	$Q$	$(P \land Q)$	$P \lor (P \land Q)$	$(P \lor Q)$	$P \land (P \lor Q)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$F$

$P$	$Q$	$P \land Q$	$\neg P$	$(P \land Q) \land \neg P$
$T$	$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$F$	$T$	$F$
$F$	$F$	$F$	$T$	$F$

$P$	$Q$	$\neg P$	$\neg Q$	$P \land Q$	$\neg P \land \neg Q$	$(P \land Q) \lor (\neg P \land \neg Q)$
$T$	$T$	$F$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$F$	$T$	$T$

$P$	$Q$	$P \land Q$	$\neg (P \land Q)$	$\neg P$	$\neg Q$	$\neg P \lor \neg Q$	$\neg (P \land Q) \leftrightarrow (\neg P \lor \neg Q)$
$T$	$T$	$T$	$F$	$F$	$F$	$F$	$T$
$T$	$F$	$F$	$T$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$T$	$T$	$T$

$P$	$Q$	$P \to Q$	$Q \to P$	$P \leftrightarrow Q$	$(P \to Q) \land (Q \to P)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$P$	$Q$	$(P \land Q)$	$P \lor (P \land Q)$	$(P \lor Q)$	$P \land (P \lor Q)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$F$