1.3. 命题等价式

数学证明中使用的一个重要步骤就是用真值相同的一条语句替换另一条语句。因此，从给定符合命题生成具有相同真值命题的方法广泛使用与数学证明的构造。

DEFINITION 1复合命题分类

一个真值永远是真的复合命题（无论其中出现的命题变元的真值时什么），称为永真式（tautology），也称为重言式。一个真值永远为假的复合命题称为矛盾式（contradiction）。既不是永真式又不是矛盾式的复合命题称为可能式（contingency）

$p$	$\lnot p$	$p\lor \lnot p$	$p\land \lnot p$
$T$	$F$	$T$	$F$
$F$	$T$	$T$	$F$

逻辑等价式

DEFINITION 2逻辑等价

如果$p\harr{q}$是永真式，则复合命题$\:p\:$和$\:q\:$称为是逻辑等价的。用记号$p\equiv{q}$表示$\:p\:$和$\:q\:$是逻辑等价的。

符号$\equiv$不是逻辑联结词，$p\equiv{q}$不是一个复合命题，而是代表“$p\harr{q}$是永真式”这一语句。有时候用符号$\Harr$来代替$\equiv$表示逻辑等价。

复合命题$\:p\:$和$\:q\:$是等价的当且仅当对应他们的真值的两列完全一致。

德·摩根律

• $\lnot(p\land q) = \lnot{p}\lor\lnot{q}$
• $\lnot(p\lor q) = \lnot{p}\land\lnot{q}$

逻辑等价式

等价式1	等价式2	名称
$p\land T\equiv p$	$p\lor F \equiv p$	恒等律
$p\lor T\equiv T$	$p\land F\equiv F$	支配律
$p\lor p\equiv p$	$p\land p \equiv p$	幂等律
$\lnot(\lnot p)\equiv p$		双重否定律
$p\lor q\equiv q\lor p$	$p\land q\equiv q\land p$	交换律
$(p\lor{q})\lor r\equiv q\lor(p\lor r)$	$(p\land q)\land r\equiv q\land(p\land r)$	结合律
$p\lor(q\land{r})\equiv(p\lor{q})\land(p\lor{r})$	$p\land(q\lor r)\equiv(p\land q)\lor(p\land r)$	分配律
$\lnot(p\land q)\equiv\lnot p\lor\lnot q$	$\lnot(p\lor q)\equiv\lnot p\land\lnot q$	德·摩根律
$p\lor(p\land q)\equiv p$	$p\land(p\lor q)\equiv p$	吸收律
$p\lor\lnot p\equiv T$	$p\land\lnot p\equiv F$	否定律

条件命题的逻辑等价式

• $p\to q \equiv \lnot p \lor q$
• $p\to q \equiv \lnot q \to \lnot p$
• $p\lor{q}\equiv\lnot{p}\to q$
• $p\land{q}\equiv\lnot({p}\to\lnot{q})$
• $\lnot(p \to q)\equiv p \land\lnot q$
• $(p\to{q})\land(p\to{r})\equiv{p\to(q\land{r})}$
• $(p\to{q})\lor(p\to{r})\equiv{p\to(q\lor{r})}$
• $(p\to{r})\land(q\to{r})\equiv{p\lor{q}}\to r$
• $(p\to{r})\lor(q\to{r})\equiv{p\land{q}}\to r$

双条件命题的逻辑等价式

• $p\harr{q}\equiv(p\to{q})\land(q\to{p})$
• $p\harr{q}\equiv\lnot{p}\harr\lnot q$
• $p\harr{q}\equiv(p\land{q})\lor(\lnot{p}\land\lnot{q})$
• $\lnot(p\harr{q})\equiv p\harr\lnot q$

德·摩根律可以扩展为

$$\begin{array}{ll} \lnot(p_1\lor p_2\lor \dots \lor p_n)&=\lnot{p_1} \land \lnot{p_2}\land\dots\land\lnot{p_n}\\ \lnot(p_1\land p_2\land \dots \land p_n)&=\lnot{p_1} \lor \lnot{p_2}\lor\dots\lor\lnot{p_n} \end{array}$$

逻辑等价式证明

分配率： $p\lor(q\land{r})\equiv(p\lor{q})\land(p\lor{r})\:$和$\:p\land(q\lor{r})\equiv(p\land{q})\lor(p\land{r})$

$p$	$q$	$r$	$q\land r$	$p\lor(q\land{r})$	$(p\lor{q})\land(p\lor{r})$	$q\lor{r}$	$p\land(q\lor{r})$	$(p\land{q})\lor(p\land{r})$
$T$	$T$	$T$	$T$	$T$	$T\land{T}=T$	$T$	$T$	$T\lor{T}=T$
$T$	$T$	$F$	$F$	$T$	$T\land{T}=T$	$T$	$T$	$T\lor{F}=T$
$T$	$F$	$T$	$F$	$T$	$T\land{T}=T$	$T$	$T$	$F\lor{T}=T$
$T$	$F$	$F$	$F$	$T$	$T\land{T}=T$	$F$	$F$	$F\lor{F}=F$
$F$	$T$	$T$	$T$	$T$	$T\land{T}=T$	$T$	$F$	$F\lor{F}=F$
$F$	$T$	$F$	$F$	$F$	$T\land{F}=F$	$T$	$F$	$F\lor{F}=F$
$F$	$F$	$T$	$F$	$F$	$F\land{T}=F$	$T$	$F$	$F\lor{F}=F$
$F$	$F$	$F$	$F$	$F$	$F\land{F}=F$	$F$	$F$	$F\lor{F}=F$

德·摩根律：$\lnot(p\land{q})\equiv\lnot{p}\lor\lnot{q}$和$\lnot(p\lor{q})\equiv\lnot{p}\land\lnot q$

$p$	$q$	$\lnot p$	$\lnot q$	$p\land q$	$p\lor q$	$\lnot(p\land{q})$	$\lnot{p}\lor\lnot q$	$\lnot(p\lor{q})$	$\lnot{p}\land\lnot q$
$T$	$T$	$F$	$F$	$T$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$F$	$T$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$T$	$T$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$F$	$F$	$T$	$T$	$T$	$T$

吸收律 $p\lor(p\land{q})\equiv{p}\:$和$\:p\land(p\lor{q})\equiv p$

• (a) 证明：$p\lor(p\land{q})\equiv{p}\:$
  当$p=T$时，无论$p\land{q}$为何真值，$p\lor(p\land{q})$都为$T$
  当$p=F$时，无论$q$为何真值，$p\land{q}$总为$F$，$F\lor{F} = F$
  所以，$p\lor(p\land{q})$与$q$的真值无关，所以$p\lor(p\land{q})\equiv{p}$
• (b)证明：$p\land(p\lor{q})\equiv{p}$
  当$p=T$时，无论$q$为何真值，$p\lor{q}$总为$T$，$T\land{T} = T$
  当$p=F$时，无论$p\land{q}$为何真值，$p\land(p\lor{q})$都为$F$
  所以，$p\land(p\lor{q})$与$q$的真值无关，所以$\land(p\lor{q})\equiv p$

构造新的逻辑等价式

例1： 证明$p\lor{q} \to r \equiv (p \to r)\land(q \to r)$

$$\begin{array}{ll} p\lor{q} \to r &\equiv \lnot(p\lor{q})\lor{r} \\ &\equiv(\lnot{p}\land\lnot{q})\lor{r}\\ &\equiv(\lnot{p}\lor{r})\land(\lnot{q}\lor{r})\\ &\equiv(p\to{r})\land(q\to{r}) \end{array}$$

例2： 证明$\lnot(p\to{q})$和$p\land\lnot{q}$是逻辑等价的。

$$\begin{array}{ll} \lnot(p\to{q}) &\equiv \lnot(\lnot{p}\lor{q}) \\ &\equiv \lnot\lnot{p}\land\lnot{q}\\ &\equiv p\land\lnot{q} \end{array}$$

例3： 证明$(p\land{q})\to(p\lor{q})$为永真式。

$$\begin{array}{ll} (p\land{q})\to(p\lor{q}) &\equiv \lnot(p\land{q})\lor(p\lor{q})\\ &\equiv\lnot{p}\lor\lnot{q}\lor(p\lor{q})\\ &\equiv(\lnot{p}\lor{p})\lor(\lnot{q}\lor{q})\\ &\equiv T\lor{T}\\ &\equiv T \end{array}$$

习题部分

对偶式

对偶式

一个只含逻辑运算符$\land , \lor, \lnot~$的符合命题的对偶式是通过将该命题的每个$\land$用$\lor$替换，每个$\lor$用$\land$替换、$\lnot$保持不变，每个$\bf{T}$用$\bf{F}$替换，每个$\bf{F}$用$\bf{T}$替换而得到的命题。命题$s$的对偶式用$~s^*~$表示

$$(s^*)^* = s$$

与非或非

$NAND$（与非）和$NOR$（或非）

命题$p\enspace NAND\enspace q$在$p$或$q$或两者均为假时为真，而当$p$和$q$为真是为假。命题$p\enspace NOR\enspace q$只在$p$和$q$均为假时为真，否则为真。命题$p\enspace NAND\enspace q$和$p\enspace NOR\enspace q$分别表示为$p\:|\:q$和$p\:\darr\:q$。

$p$	$q$	$p\:\mid\:q$	$(p\land q)$	$\lnot(p\land q)$	$p\:\darr\:q$	$p\lor q$	$\lnot(p\lor{q})$
$T$	$T$	$F$	$T$	$F$	$F$	$T$	$F$
$T$	$F$	$T$	$F$	$T$	$F$	$T$	$F$
$F$	$T$	$T$	$F$	$T$	$F$	$T$	$F$
$F$	$F$	$T$	$F$	$T$	$T$	$F$	$T$

• $p\:\mid\:q\equiv\lnot(p\land{q})$
• $p\:\darr\:q\equiv\lnot(p\lor{q})$