命题逻辑等价式 (14组)

Hui Li

• 双重否定律 (Double negation law)

$\mathrm{\neg }\mathrm{\neg }A\iff A$${\lnot}{\lnot}A{\Leftrightarrow}A$

• 等幂律 (Idempotent laws)

$A\vee A\iff A$$A{\vee}A{\Leftrightarrow}A$ $A\wedge A\iff A$$A{\wedge}A{\Leftrightarrow}A$

• 结合律 (Associative laws)

$(A\vee B)\vee C\iff A\vee (B\vee C)$$(A{\vee}B){\vee}C{\Leftrightarrow}A{\vee}(B{\vee}C)$ $(A\wedge B)\wedge C\iff A\wedge (B\wedge C)$$(A{\wedge}B){\wedge}C{\Leftrightarrow}A{\wedge}(B{\wedge}C)$

• 交换律 (Commutative laws)

$A\vee B\iff B\vee A$$A{\vee}B{\Leftrightarrow}B{\vee}A$ $A\wedge B\iff B\wedge A$$A{\wedge}B{\Leftrightarrow}B{\wedge}A$

• 分配律 (Distributive laws)

$A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$$A{\vee}(B{\wedge}C){\Leftrightarrow}(A{\vee}B){\wedge}(A{\vee}C)$ $A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$$A{\wedge}(B{\vee}C){\Leftrightarrow}(A{\wedge}B){\vee}(A{\wedge}C)$

• 吸收律 (Absorption laws)

$A\vee (A\wedge B)\iff A$$A{\vee}(A{\wedge}B){\Leftrightarrow}A$ $A\wedge (A\vee B)\iff A$$A{\wedge}(A{\vee}B){\Leftrightarrow}A$

• 德$\cdot$$\cdot$摩根律 (De Morgan's laws)

$\mathrm{\neg }(A\wedge B)\iff \mathrm{\neg }A\vee \mathrm{\neg }B$${\lnot}(A{\wedge}B){\Leftrightarrow}{\lnot}A{\vee}{\lnot}B$ $\mathrm{\neg }(A\vee B)\iff \mathrm{\neg }A\wedge \mathrm{\neg }B$${\lnot}(A{\vee}B){\Leftrightarrow}{\lnot}A{\wedge}{\lnot}B$

• 同一律 (Identity laws)

$A\vee F\iff A$$A{\vee}F{\Leftrightarrow}A$ $A\wedge T\iff A$$A{\wedge}T{\Leftrightarrow}A$

• 零律 (Domination laws)

$A\vee T\iff T$$A{\vee}T{\Leftrightarrow}T$ $A\wedge F\iff F$$A{\wedge}F{\Leftrightarrow}F$

• 补余律 (Negation laws)

$A\vee \mathrm{\neg }A\iff T$$A{\vee}{\lnot}A{\Leftrightarrow}T$ $A\wedge \mathrm{\neg }A\iff F$$A{\wedge}{\lnot}A{\Leftrightarrow}F$

• 条件转化律 (Conditionals, Material Implication)

$A\to B\iff \mathrm{\neg }A\vee B$$A{\rightarrow}B{\Leftrightarrow}{\lnot}A{\vee}B$ $A\to B\iff \mathrm{\neg }B\to \mathrm{\neg }A$$A{\rightarrow}B{\Leftrightarrow}{\lnot}B{\rightarrow}{\lnot}A$ $\mathrm{\neg }(A\to B)\iff A\wedge \mathrm{\neg }B$${\lnot}(A{\rightarrow}B){\Leftrightarrow}A{\wedge}{\lnot}B$

• 双条件转化律 (Biconditionals, Material Equivalence)

$A\leftrightarrow B\iff (A\to B)\wedge (B\to A)$$A{\leftrightarrow}B{\Leftrightarrow}(A{\rightarrow}B){\wedge}(B{\rightarrow}A)$ $A\leftrightarrow B\iff (A\wedge B)\vee (\mathrm{\neg }A\wedge \mathrm{\neg }B)$$A{\leftrightarrow}B{\Leftrightarrow}(A{\wedge}B){\vee}({\lnot}A{\wedge}{\lnot}B)$

• 归缪律 (Reductio ad absurdum)

$(A\to B)\wedge (A\to \mathrm{\neg }B)\iff \mathrm{\neg }A$$(A{\rightarrow}B){\wedge}(A{\rightarrow}{\lnot}B){\Leftrightarrow}{\lnot}A$

• 输入输出律(Exportation, Importation)

$(A\wedge B)\to C\iff A\to (B\to C)$$(A{\wedge}B){\rightarrow}C{\Leftrightarrow}A{\rightarrow}(B{\rightarrow}C)$

命题逻辑蕴含式 (9组)

• 化简式 (Simplification)

$A\wedge B\Rightarrow A$$A{\wedge}B{\Rightarrow}A$ $A\wedge B\Rightarrow B$$A{\wedge}B{\Rightarrow}B$

• 附加式 (Addition)

$A\Rightarrow A\vee B$$A{\Rightarrow}A{\vee}B$ $B\Rightarrow A\vee B$$B{\Rightarrow}A{\vee}B$

• 假言推理 (Modus ponens)

$A\wedge (A\to B)\Rightarrow B$$A{\wedge}(A{\rightarrow}B){\Rightarrow}B$

• 拒取式 (Modus tollens)

$\mathrm{\neg }B\wedge (A\to B)\Rightarrow \mathrm{\neg }A$${\lnot}B{\wedge}(A{\rightarrow}B){\Rightarrow}{\lnot}A$

• 析取三段论 (Disjunctive syllogism)

$\mathrm{\neg }A\wedge (A\vee B)\Rightarrow B$${\lnot}A{\wedge}(A{\vee}B){\Rightarrow}B$

• 假言三段论 (Hypothetical syllogism)

$(A\to B)\wedge (B\to C)\Rightarrow (A\to C)$$(A{\rightarrow}B){\wedge}(B{\rightarrow}C){\Rightarrow}(A{\rightarrow}C)$

• 双条件三段论

$(A\leftrightarrow B)\wedge (B\leftrightarrow C)\Rightarrow (A\leftrightarrow C)$$(A{\leftrightarrow}B){\wedge}(B{\leftrightarrow}C){\Rightarrow}(A{\leftrightarrow}C)$

• 构造性二难 (Constructive dilemma)

$(A\to B)\wedge (C\to D)\wedge (A\wedge C)\Rightarrow B\wedge D$$(A{\rightarrow}B){\wedge}(C{\rightarrow}D){\wedge}(A{\wedge}C){\Rightarrow}B{\wedge}D$ $(A\to B)\wedge (C\to D)\wedge (A\vee C)\Rightarrow B\vee D$$(A{\rightarrow}B){\wedge}(C{\rightarrow}D){\wedge}(A{\vee}C){\Rightarrow}B{\vee}D$

• 二难推论 (Disjunction elimination)

$(A\to B)\wedge (C\to B)\wedge (A\wedge C)\Rightarrow B$$(A{\rightarrow}B){\wedge}(C{\rightarrow}B){\wedge}(A{\wedge}C){\Rightarrow}B$ $(A\to B)\wedge (C\to B)\wedge (A\vee C)\Rightarrow B$$(A{\rightarrow}B){\wedge}(C{\rightarrow}B){\wedge}(A{\vee}C){\Rightarrow}B$

谓词逻辑等价式和蕴含式

• 量词的转换律

$\mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }A(x)\iff \mathrm{\exists }xA(x)$${\lnot}{\forall}x{\lnot}A(x){\Leftrightarrow}{\exists}xA(x)$ $\mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }A(x)\iff \mathrm{\forall }xA(x)$${\lnot}{\exists}x{\lnot}A(x){\Leftrightarrow}{\forall}xA(x)$ $\mathrm{\neg }\mathrm{\forall }xA(x)\iff \mathrm{\exists }x\mathrm{\neg }A(x)$${\lnot}{\forall}xA(x){\Leftrightarrow}{\exists}x{\lnot}A(x)$ $\mathrm{\neg }\mathrm{\exists }xA(x)\iff \mathrm{\forall }x\mathrm{\neg }A(x)$${\lnot}{\exists}xA(x){\Leftrightarrow}{\forall}x{\lnot}A(x)$

• 量词辖域的扩张与收缩律

设$B$$B$是不含个体变元$x$$x$的谓词公式,则:

$\mathrm{\forall }x(A(x)\vee B)\iff \mathrm{\forall }xA(x)\vee B$${\forall}x(A(x){\vee}B){\Leftrightarrow}{\forall}xA(x){\vee}B$ $\mathrm{\forall }x(A(x)\wedge B)\iff \mathrm{\forall }xA(x)\wedge B$${\forall}x(A(x){\wedge}B){\Leftrightarrow}{\forall}xA(x){\wedge}B$ $\mathrm{\exists }x(A(x)\vee B)\iff \mathrm{\exists }xA(x)\vee B$${\exists}x(A(x){\vee}B){\Leftrightarrow}{\exists}xA(x){\vee}B$ $\mathrm{\exists }x(A(x)\wedge B)\iff \mathrm{\exists }xA(x)\wedge B$${\exists}x(A(x){\wedge}B){\Leftrightarrow}{\exists}xA(x){\wedge}B$

• 量词的分配律

$\mathrm{\forall }x(A(x)\wedge B(x))\iff \mathrm{\forall }xA(x)\wedge \mathrm{\forall }xB(x)$${\forall}x(A(x){\wedge}B(x)){\Leftrightarrow}{\forall}xA(x){\wedge}{\forall}xB(x)$ $\mathrm{\exists }x(A(x)\vee B(x))\iff \mathrm{\exists }xA(x)\vee \mathrm{\exists }xB(x)$${\exists}x(A(x){\vee}B(x)){\Leftrightarrow}{\exists}xA(x){\vee}{\exists}xB(x)$

• 量词的消去

在某一解释$I$$I$下,若个体域为有限集,如$D=\{a_1,a_2,\cdots ,a_n\}$$D=\{a_{1},a_{2},{\cdots},a_{n}\}$,则由量词的定义可得出: $\mathrm{\forall }xA(x)\iff A(a_1)\wedge A(a_2)\wedge \cdots \wedge A(a_n)$${\forall}xA(x){\Leftrightarrow}A(a_{1}){\wedge}A(a_{2}){\wedge}{\cdots}{\wedge}A(a_{n})$ $\mathrm{\exists }xA(x)\iff A(a_1)\vee A(a_2)\vee \cdots \vee A(a_n)$${\exists}xA(x){\Leftrightarrow}A(a_{1}){\vee}A(a_{2}){\vee}{\cdots}{\vee}A(a_{n})$ 其中$A(a_i)(i=1,2,\cdots ,n)$$A(a_{i})(i=1,2,{\cdots},n)$为用$a_i$$a_{i}$代入公式$A(x)$$A(x)$中自由出现的$x$$x$得到的公式.

• 含有量词的永真蕴含式

$\mathrm{\forall }xA(x)\vee \mathrm{\forall }xB(x)\Rightarrow \mathrm{\forall }x(A(x)\vee B(x))$${\forall}xA(x){\vee}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\vee}B(x))$ $\mathrm{\exists }x(A(x)\wedge B(x))\Rightarrow \mathrm{\exists }xA(x)\wedge \mathrm{\exists }xB(x)$${\exists}x(A(x){\wedge}B(x)){\Rightarrow}{\exists}xA(x){\wedge}{\exists}xB(x)$ $\mathrm{\forall }x(A(x)\to B(x))\Rightarrow \mathrm{\forall }xA(x)\to \mathrm{\forall }xB(x)$${\forall}x(A(x){\rightarrow}B(x)){\Rightarrow}{\forall}xA(x){\rightarrow}{\forall}xB(x)$ $\mathrm{\exists }xA(x)\to \mathrm{\forall }xB(x)\Rightarrow \mathrm{\forall }x(A(x)\to B(x))$${\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))$

这些永真蕴含式的逆均不成立.

• 多个量词的使用

$\mathrm{\forall }x\mathrm{\forall }yA(x,y)\iff \mathrm{\forall }y\mathrm{\forall }xA(x,y)$${\forall}x{\forall}yA(x,y){\Leftrightarrow}{\forall}y{\forall}xA(x,y)$ $\mathrm{\exists }x\mathrm{\exists }yA(x,y)\iff \mathrm{\exists }y\mathrm{\exists }xA(x,y)$${\exists}x{\exists}yA(x,y){\Leftrightarrow}{\exists}y{\exists}xA(x,y)$ $\mathrm{\forall }x\mathrm{\forall }yA(x,y)\Rightarrow \mathrm{\exists }y\mathrm{\forall }xA(x,y)$${\forall}x{\forall}yA(x,y){\Rightarrow}{\exists}y{\forall}xA(x,y)$ $\mathrm{\forall }y\mathrm{\forall }xA(x,y)\Rightarrow \mathrm{\exists }x\mathrm{\forall }yA(x,y)$${\forall}y{\forall}xA(x,y){\Rightarrow}{\exists}x{\forall}yA(x,y)$ $\mathrm{\exists }y\mathrm{\forall }xA(x,y)\Rightarrow \mathrm{\forall }x\mathrm{\exists }yA(x,y)$${\exists}y{\forall}xA(x,y){\Rightarrow}{\forall}x{\exists}yA(x,y)$ $\mathrm{\exists }x\mathrm{\forall }yA(x,y)\Rightarrow \mathrm{\forall }y\mathrm{\exists }xA(x,y)$${\exists}x{\forall}yA(x,y){\Rightarrow}{\forall}y{\exists}xA(x,y)$ $\mathrm{\forall }x\mathrm{\exists }yA(x,y)\Rightarrow \mathrm{\exists }y\mathrm{\exists }xA(x,y)$${\forall}x{\exists}yA(x,y){\Rightarrow}{\exists}y{\exists}xA(x,y)$ $\mathrm{\forall }y\mathrm{\exists }xA(x,y)\Rightarrow \mathrm{\exists }x\mathrm{\exists }yA(x,y)$${\forall}y{\exists}xA(x,y){\Rightarrow}{\exists}x{\exists}yA(x,y)$