本章分为三节：等值式，析取范式与合取范式，联结词的完备集。

等值式

设 A, B是两个命题公式，若 A, B构成的等价式 $A \leftrightarrow B$ 为重言式，则称A与B是等值的，记作 $A\Leftrightarrow B$

16组重要等值式模式

双重否定律
$A\Leftrightarrow \neg\neg B$
幂等律
$A\Leftrightarrow A\vee A$ $A\Leftrightarrow A\wedge A$
交换律
$A\wedge B \Leftrightarrow B\wedge A$ $A\vee B\Leftrightarrow B\vee A$
结合律
$(A\vee B)\vee C \Leftrightarrow A\vee(B\vee C)$ $A\wedge (B\wedge C) \Leftrightarrow (A\wedge B)\wedge C$
分配律
$A\vee (B\wedge C) \Leftrightarrow (A\vee B)\wedge (A\vee C)$ ( $\vee$ 对 $\wedge$ 的分配律)
$A\wedge (B\vee C) \Leftrightarrow (A\wedge B)\vee (A\wedge C)$ ( $\wedge$ 对 $\vee$ 的分配律)
德摩根律
$\neg(A\vee B)\Leftrightarrow \neg A \wedge \neg B$ $\neg(A\wedge B)\Leftrightarrow \neg A \vee \neg B$
吸收律
$A\vee (A\wedge B)\Leftrightarrow A$ $A\wedge (A\vee B)\Leftrightarrow A$
零律
$A \vee 1 \Leftrightarrow 1$ $A \wedge 0 \Leftrightarrow 0$
同一律
$A \vee 0 \Leftrightarrow A$ $A \wedge 1 \Leftrightarrow A$
排中律
$A \vee \neg A \Leftrightarrow 1$
矛盾律
$A \wedge \neg A \Leftrightarrow 0$
蕴含等值式
$A\rightarrow B \Leftrightarrow \neg A \vee B$
等价等值式
$A \leftrightarrow B \Leftrightarrow (A\rightarrow B) \wedge (B\rightarrow A) \Leftrightarrow (A\wedge B)\vee(\neg A \wedge \neg B)$
假言易位
$A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A$
等价否定式
$A\leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$
归谬论
$(A \rightarrow B) \wedge (A\rightarrow \neg B) \Leftrightarrow \neg A$
置换规则：设 $\phi(A)$ 是含公式A的命题公式， $\phi(B)$ 是用公式B置换 $\phi(A)$ 中A的所有出现后的到的公式。若 $B\Leftrightarrow A$ ，则 $\phi(A)\Leftrightarrow \phi(B)$

合取范式与析取范式

命题变相及其否定统称作文字，仅由有限个文字构成的析取式（或合取式）称作简单析取式（或简单合取式） $p,\neg p$ 这两个命题既可被看为是简单析取式也可被看为简单合取式
由有限个简单合取式的析取构成的命题公式（多个与式相或）称作析取范式，由有限个简单析取式的合取构成的命题公式（多个或式相与）称作合取范式。合取范式与析取范式统称为范式。

极大项极小项

（类似数逻极大值极小值）
在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按照下标从小到大或按照字典顺序排列，称这样的简单合取式（简单析取式）为极小项（极大项）

所有简单合取式（简单析取式）都是极小项（极大项）的析取范式（合取范式）称为主析取范式（主合取范式）

命题联结词的完备集

对任意的一个含有n个变量命题公式得到其定义域与值域将其写成 $\left\{ 0,1 \right\}^{n} \rightarrow \left\{ 0,1 \right\}$ 称为n元真值函数
n个命题变项共可构成 $2^{2n}$ 个不同的真值函数。
举个例子：一元真值函数

p	$F_{0}^{(1)}$	$F_{1}^{(1)}$	$F_{2}^{(1)}$	$F_{3}^{(1)}$
0	0	0	1	1
1	0	1	0	1

二元真值函数

p	q	$F_{1}^{(2)}$	$F_{2}^{(2)}$	$F_{3}^{(2)}$	$F_{4}^{(2)}$	$F_{5}^{(2)}$	$F_{6}^{(2)}$	$F_{7}^{(2)}$	$F_{8}^{(2)}$	$F_{9}^{(2)}$	$F_{10}^{(2)}$	$F_{11}^{(2)}$	$F_{12}^{(2)}$	$F_{13}^{(2)}$	$F_{14}^{(2)}$	$F_{15}^{(2)}$
0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

每一个真值函数都与唯一的一个主析取范式（主合取范式）等值。

例如 $F_{0}^{(2)} \Leftrightarrow 0$ （矛盾式）， $F_{1}^{(2)} \Leftrightarrow (p\wedge q) \Leftrightarrow m_{3}$ , $F_{2}^{(2)} \Leftrightarrow (p\wedge \neg q) \Leftrightarrow m_{2}$ , $F_{3}^{(2)} \Leftrightarrow ((p\wedge \neg q)\vee (p\wedge q)) \Leftrightarrow m_{2} \vee m_{3}$

每个主析取范式对应无穷多个等值的命题公式
每一个命题公式又都有唯一等值的主析取范式
所以每个真值函数对应无穷多个等值的命题公式

每个命题公式又都对应唯一的等值的真值函数

大概就是这样子

(此处的图片被吃了)

设S是一个联结词集合，如果任何n(n>=1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集
s={ $\neg ,\wedge,\vee$ }

s={ $\neg ,\wedge$ }

s={ $\neg ,\vee$ }

s={ $\uparrow$ }

s={ $\downarrow$ }

以上均联结词完备集