# ➥命题等价式

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

## ➥逻辑等价式

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

$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$

$\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}\\$

## ➥逻辑等价式证明

$p$ $q$ $r$ $q\land r$ $p\lor(q\land{r})$ $(p\lor{q})\land(p\lor{r})$ $q\lor$ $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$

$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$

• (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$
• (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$

## ➥构造新的逻辑等价式

$\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}$

$\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}$

$\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}$

## ➥其他

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

$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})$

Power by 不蒜子