1-6 其他联结词

定义 1-6.1：设 $P$$P$ 为 $Q$$Q$ 是两个命题公式，复合命题 $P\bar{\vee }Q$$P \overline \lor Q$，称作 $P$$P$ 和 $Q$$Q$ 的不可兼析取。 $P\bar{\vee }Q$$P \overline \lor Q$ 的真值为 $T$$T$，当且仅当 $P$$P$ 与 $Q$$Q$ 的真值一相同时为 $T$$T$，否则， $P\bar{\vee }Q$$P \overline \lor Q$ 的真值为 $F$$F$。

联结词“$\bar{\vee }$$\overline \lor$”的定义如表 1-6.1 所示。

表 1-6.1

从上述定义可知联结词“$\bar{\vee }$$\overline \lor$”有以下性质：

设 $P$$P$、$Q$$Q$、$R$$R$ 为命题公式，则有

(1) $P\bar{\vee }Q⟺Q\bar{\vee }P$$P \overline \lor Q \iff Q \overline \lor P$

(2) $(P\bar{\vee }Q)\bar{\vee }R⟺P\bar{\vee }(Q\bar{\vee }R)$$(P \overline \lor Q) \overline \lor R \iff P \overline \lor (Q \overline \lor R)$

(3) $P\vee (Q\bar{\vee }R)⟺(P\wedge Q)\bar{\vee }(P\wedge R)$$P \lor (Q \overline \lor R) \iff (P \land Q) \overline \lor (P \land R)$

(4) $(P\bar{\vee }Q)⟺(P\wedge \mathrm{\neg }Q)\vee (\mathrm{\neg }P\wedge Q)$$(P \overline \lor Q) \iff (P \land \neg Q) \lor (\neg P \land Q)$

(5) $(P\bar{\vee }Q)⟺\mathrm{\neg }(P\leftrightarrow Q)$$(P \overline \lor Q) \iff \neg (P \leftrightarrow Q)$

(6) $P\bar{\vee }P⟺F，F\bar{\vee }P⟺P，T\bar{\vee }P⟺\mathrm{\neg }P$$P \overline \lor P \iff F，F \overline \lor P \iff P，T \overline \lor P \iff \neg P$

定理 1-6.1：设 $P$$P$、$Q$$Q$、$R$$R$ 为命题公式，如果 $P\bar{\vee }Q⟺R$$P \overline \lor Q \iff R$，则 $P\bar{\vee }R⟺Q，Q\bar{\vee }R⟺P$$P \overline \lor R \iff Q，Q \overline \lor R \iff P$，且 $P\bar{\vee }Q\bar{\vee }R$$P \overline \lor Q \overline \lor R$ 为一矛盾式。

定义 1-6.2：设 $P$$P$ 和 $Q$$Q$ 是两个命题公式，复合命题 $P\stackrel{c}{\to }Q$$P \overset{c}{\to} Q$ 称作命题 $P$$P$ 和 $Q$$Q$ 的条件否定， $P\stackrel{c}{\to }Q$$P \overset{c}{\to} Q$ 的真值为 $T$$T$，当且仅当 $P$$P$ 的真值为 $T$$T$，$Q$$Q$ 的真值为 $F$$F$，否则， $P\stackrel{c}{\to }Q$$P \overset{c}{\to} Q$ 的真值为 $F$$F$。

联结词“$\stackrel{c}{\to }$$\overset{c}{\to}$”的定义如表 1-6.2 所示。

表 1-6.2

从定义可知 $P\stackrel{c}{\to }Q⟺\mathrm{\neg }(P\to Q)$$P \overset{c}{\to} Q \iff \neg (P \to Q)$。

定义 1-6.3：设 $P$$P$ 和 $Q$$Q$ 是两个命题是公式，复合命题 $P\uparrow Q$$P \uparrow Q$ 称作 $P$$P$ 和 $Q$$Q$ 的“与非”。当且仅当 $P$$P$ 和 $Q$$Q$ 的真值都是 $T$$T$ 时， $P\uparrow Q$$P \uparrow Q$ 为 $F$$F$，否则 $P\uparrow Q$$P \uparrow Q$ 的真值都为 $T$$T$。

联结词“$\uparrow$$\uparrow$”的定义如表 1-6.3 所示。

表 1-6.3

从上表可以看出 $P\uparrow Q⟺\mathrm{\neg }(P\wedge Q)$$P \uparrow Q \iff \neg (P \land Q)$，故联结词“$\uparrow$$\uparrow$”可称为“与非”。

联结词“$\uparrow$$\uparrow$”有如下几个性质：

(1) $P\uparrow P⟺\mathrm{\neg }(P\wedge P)⟺\mathrm{\neg }P$$P \uparrow P \iff \neg (P \land P) \iff \neg P$

(2) $(P\uparrow Q)\uparrow (P\uparrow Q)⟺\mathrm{\neg }(P\uparrow Q)⟺P\wedge Q$$(P \uparrow Q) \uparrow (P \uparrow Q) \iff \neg (P \uparrow Q) \iff P \land Q$

(3) $(P\uparrow P)\uparrow (Q\uparrow Q)⟺\mathrm{\neg }P\uparrow \mathrm{\neg }Q⟺\mathrm{\neg }(\mathrm{\neg }P\wedge \mathrm{\neg }Q)⟺P\vee Q$$(P \uparrow P) \uparrow (Q \uparrow Q) \iff \neg P \uparrow \neg Q \iff \neg (\neg P \land \neg Q) \iff P \lor Q$

定义 1-6.4：设 $P$$P$ 和 $Q$$Q$ 是两个命题公式，复合命题 $P\downarrow Q$$P \downarrow Q$ 称作 $P$$P$ 和 $Q$$Q$ 的“或非”，当且仅当 $P$$P$ 和 $Q$$Q$ 的真值都为 $F$$F$ 时， $P\downarrow Q$$P \downarrow Q$ 的真值为 $T$$T$，否则 $P\downarrow Q$$P \downarrow Q$ 的真值都为 $F$$F$。

联结词“$\downarrow$$\downarrow$”的定义如表 1-6.4 所示。

表 1-6.4

从上表可以看出 $P\downarrow Q⟺\mathrm{\neg }(P\vee Q)$$P \downarrow Q \iff \neg (P \lor Q)$，故联结词“$\downarrow$$\downarrow$”可称作“或非”。

联结词“$\downarrow$$\downarrow$”有如下几个性质：

(1) $P\downarrow P⟺\mathrm{\neg }(P\vee P)⟺\mathrm{\neg }P$$P \downarrow P \iff \neg (P \lor P) \iff \neg P$

(2) $(P\downarrow Q)\downarrow (P\downarrow Q)⟺\mathrm{\neg }(P\downarrow Q)⟺P\vee Q$$(P \downarrow Q) \downarrow (P \downarrow Q) \iff \neg (P \downarrow Q) \iff P \lor Q$

(3) $(P\downarrow P)\downarrow (Q\downarrow Q)⟺\mathrm{\neg }P\downarrow \mathrm{\neg }Q⟺P\wedge Q$$(P \downarrow P) \downarrow (Q \downarrow Q) \iff \neg P \downarrow \neg Q \iff P \land Q$

最小联结词组，对于任何一个命题公式，都能由仅包含这些联结词的命题公式等价代换。这是因为

(1) 由 $(P\leftrightarrow Q)⟺(P\to Q)\wedge (Q\to P)$$(P \leftrightarrow Q) \iff (P \to Q) \land (Q \to P)$，故可把包含"$\leftrightarrow$$\leftrightarrow$“的公式等价变换为包含”$\wedge$$\land$“和”$\to$$\to$“的公式。

(2) 由 $P\to Q⟺\mathrm{\neg }P\vee Q$$P \to Q \iff \neg P \lor Q$，说明包含”$\to$$\to$“的公式可以变换为包含”$\mathrm{\neg }$$\neg$“和”$\vee$$\lor$“的公式。

(3) 由 $P\wedge Q⟺\mathrm{\neg }(\mathrm{\neg }P\vee \mathrm{\neg }Q)$$P \land Q \iff \neg (\neg P \lor \neg Q)$， $P\vee Q⟺\mathrm{\neg }(\mathrm{\neg }P\wedge \mathrm{\neg }Q)$$P \lor Q \iff \neg (\neg P \land \neg Q)$，说明”$\wedge$$\land$“和”$\vee$$\lor$“可以相互代换。

故由”$\mathrm{\neg }$$\neg$“、”$\wedge$$\land$“，”$\vee$$\lor$“、”$\to$$\to$“、”$\leftrightarrow$$\leftrightarrow$“这五个联结词组成的命题公式，必可由 $\{\mathrm{\neg },\vee \}$$\{\neg, \lor\}$ 或 $\{\mathrm{\neg },\wedge \}$$\{\neg, \land\}$ 组成的命题公式所替代。

对于其他一些联结词，根据定义及有关性质有：

故任意命题公式都可由仅包含 $\{\mathrm{\neg },\vee \}$$\{\neg, \lor\}$ 或 $\{\mathrm{\neg },\wedge \}$$\{\neg, \land\}$ 的命题公式等价代换。所需注意的是上述联结词组 $\{\mathrm{\neg },\vee \}$$\{\neg, \lor\}$ 和 $\{\mathrm{\neg },\wedge \}$$\{\neg, \land\}$ 不能再归为 $\{\mathrm{\neg }\}$$\{\neg\}$， $\{\vee \}$$\{\lor\}$， $\{\wedge \}$$\{\land\}$ 或 $\{\vee ,\wedge \}$$\{\lor, \land\}$。因为从合式公式定义可以看出包含二元联结词的命题公式不能用仅包含一元联结词的命题公式等价代换，同时如有

的形式，则对该等价式右边所出现的变元，都指派真值 $T$$T$，由于 $\wedge$$\and$ 和 $\vee$$\lor$ 的各次复合结果，其真值必为 $T$$T$，而该式的左边的真值为 $F$$F$，产生矛盾，说明”$\mathrm{\neg }$$\neg$“是不能由”$\vee$$\lor$“或”$\wedge$$\land$“的复合所替代，故最小联结词组应为 $\{\mathrm{\neg },\vee \}$$\{\neg, \lor\}$ 或 $\{\mathrm{\neg },\vee \}$$\{\neg, \lor\}$。

当然，由联结词”$\uparrow$$\uparrow$“和联结词”$\downarrow$$\downarrow$“的性质，可知联结词”$\mathrm{\neg }$$\neg$“、”$\wedge$$\land$“和”$\vee$$\lor$“可分别用”$\uparrow$$\uparrow$“或”$\downarrow$$\downarrow$“所替代，故最小联结词组亦可为 $\{\uparrow \}$$\{\uparrow\}$ 或 $\{\downarrow \}$$\{\downarrow\}$。