定義
完全集設 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)=x =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 可由 S 定義且 S⊆S，則 F 可由 S 定義。聯結詞 F可由 {F} 定義。
證明：↔不能由{→}定義。
證明用反證法。
給定兩個真值賦值 v= {p/1, q/0} 和v= {p/0, q/1}。假設 ↔ 能由 {→} 定義，設定義 ↔ 的由 {→} 生成的公式是 A ，則 A 中最後出現的命題變元是 p 或者 q 。
1、若 A 中最後出現的命題變元是 p ，則v(A)=1，而 v(p↔q)=0 ，所以 A 與 p↔q 不等值。
2、若 A 中最後出現的命題變元是 q ，則v(A)=1，而 v(p↔q)=0 ，所以 A 與 p↔q 不等值。這與 p↔q⇔A 矛盾。
定義2
設 S 是聯結詞集合。如果每個 n(n≥1) 元的聯結詞都可由 S 定義，則稱 S 為完全集。如果從完全集 S 中去掉任何一個聯結詞就成為不完全的了，就稱 S 為極小完全集。完全集也稱為全功能集。
連線詞的完全集有很多，比如 {~, ∧, ∨}，{~, ∧}，{~, ∨}，{~, →} 等等。對於 5 個常用邏輯符號（~, ∧, ∨, →, ?）來說，如果想組成完全集，必須包括“非”（~），因為沒有其他任何一種符號可以表示非的含義。
在一個完全集中添加任意一個連線詞，它仍然是連線詞。
如果引入了“與非”（Nand, ↑）和“或非”（Nor, ↓）做連線詞，那么它們單獨即可構成完全集，如 {↑}，{↓} 。可以證明，在所有二元連線詞當中（如果我們對於每種二元真值表都定義一個連線詞的話），只有這兩個連線詞可以單獨構成完全集。
證明一個集合是完全集的方法是，將5個常用符號（~, ∧, ∨, →, ?）分別用該集合中的連線詞表示出來。如果承認 {~, ∧} 是完全集，那么只表示這兩個符號就夠了。
