定义

• 真值函数: $F:\left{ 0,1 \right}^{n}\to \left{ 0,1 \right}$
• 联结词完备集: 只用集合中的联结词可以表示任何 $n$ 元真值函数

判定

已知 $\left{ \neg,\land,\lor \right}$ 为联结词完备集

• 若待判定集合 $S \supset \left{ \neg,\land,\lor \right}$，则一定是完备集
• 若带判定集合 $S \subset \left{ \neg,\land,\lor \right}$，则一定不是完备集
• 若带判定集合 $S$ 可以用集合中的联结词表示出 $\left{ \neg,\land,\lor \right}$ 中的联结词，则是完备集 比如
  • $p\lor q \Leftrightarrow \neg \neg p\lor q\Leftrightarrow\neg p\to q$ 所以 $\left{ \neg,\to \right}$ 可以表示 $\left{ \lor \right}$
  • $p\lor q\Leftrightarrow \neg(\neg p\land \neg q)$ 所以 $\left{ \neg,\land \right}$ 可以表示 $\left{ \lor \right}$