Adequate SetAn Adequate Set of connectives is a set such that every truth function can be represented by a statement form containing only connectives from that set.

英文定义出处：Logic for Mathematicians Revised Edition 1988 / A.G.Hamilton《数理逻辑（修订版）》

公式¬p ∨p 不定义0 元联结词1，因为定义0 元联结词的公式中不能出现命题变元。若联结词集合S 能够定义一个0 元联结词，则S 中至少有一个0 元联结词。在数学中可定义二元函数 f(x, y) = x+ y，g(x, y) = x， 但不能定义二元函数 f(x, x) = x，h(x, y) = x+ y+ z。 二元函数的两个变元应是不同变元，定义函数值的公式中不能出现其它变元。 平方函数f(x) = x2= x ×x，因此f 可由{×}定义。公式p →q , ¬p∨q, ¬(p∧¬q) 都定义联结词→。因为 p →q ⇔¬p∨qp ↔q ⇔(p∧q) ∨(¬p∧¬q) p ⊕q ⇔(p∧¬q) ∨(¬p∧q) 所以常用联结词¬, ∨, ∧, →, ↔, ⊕都可由{¬, ∨, ∧}定义。 显然，若联结词F 可由S1定义且S1 ⊆S2，则F 可由S2定义。联结词F可由{F} 定义。

证明↔不能由{→}定义。

证明用反证法。给定两个真值赋值v1= {p/1, q/0}和v2= {p/0, q/1}。假设↔能由{→}定义，设定义↔的由{→}生成的公式是A，则A 中最后出现的命题变元是p 或者q。 1.若A 中最后出现的命题变元是p，则v1(A) = 1，而v1(p ↔q)= 0，所以A 与p ↔q 不等值。2.若A 中最后出现的命题变元是q，则v2(A) = 1，而v2(p ↔q)= 0，所以A 与p ↔q 不等值。这与p ↔q⇔A 矛盾。

定义2 设S 是联结词集合。如果每个n (n ≥1) 元的联结词都可由S 定义，则称S为完全集。如果从完全集S 中去掉任何一个联结词就成为不完全的了，就称S 为极小完全集。完全集也称为全功能集

连接词的完全集有很多，比如{~, ∧, ∨}，{~, ∧}，{~, ∨}，{~, →}等等。对于5个常用逻辑符号（~, ∧, ∨, →, ?）来说，如果想组成完全集，必须包括“非”（~），因为没有其他任何一种符号可以表示非的含义。在一个完全集中添加任意一个连接词，它仍然是连接词。

如果引入了“与非”（Nand, ↑）和“或非”（Nor, ↓）做连接词，那么它们单独即可构成完全集，如{↑}，{↓}。可以证明，在所有二元连接词当中（如果我们对于每种二元真值表都定义一个连接词的话），只有这两个连接词可以单独构成完全集

证明一个集合是完全集的方法是，将5个常用符号（~, ∧, ∨, →, ?）分别用该集合中的连接词表示出来。如果承认{~, ∧}是完全集，那么只表示这两个符号就够了。