更新时间：2023-01-07 19:13
设 F 是 n 元联结词，p1,…,pn 是不同的命题变元。如果公式 A 中不出现除 p1,…,pn 之外的命题变元，并 A⇔Fp1…pn，则称 A 定义 F。如果存在由联结词集合 S 生成的公式定义 F ，则称 F 可由 S 定义。
设 r 是某种归约。一个集合 A 是 r 完全的是指它是递归可枚举的且对所有递归可枚举集 W 有。
对于图灵归约的 T 完全集有时简称完全集。
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.
定义1
公式 ¬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个常用符号（~, ∧, ∨, →, ?）分别用该集合中的连接词表示出来。如果承认 {~, ∧} 是完全集，那么只表示这两个符号就够了。