-
完全集
鎖定
設 F 是 n 元聯結詞，p1,…,pn 是不同的命題變元。如果公式 A 中不出現除 p1,…,pn 之外的命題變元，並 A⇔Fp1…pn，則稱 A 定義 F。如果存在由聯結詞集合 S 生成的公式定義 F ，則稱 F 可由 S 定義。
- 中文名
- 完全集
- 外文名
- Adequate Set，complete set
- 適用範圍
- 數理科學
完全集定義
設 r 是某種歸約。一個集合 A 是 r 完全的是指它是遞歸可枚舉的且對所有遞歸可枚舉集 W 有
。
完全集英文介紹
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.
[2]
完全集簡介
定義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個常用符號（~, ∧, ∨, →, ?）分別用該集合中的連接詞表示出來。如果承認 {~, ∧} 是完全集，那麼只表示這兩個符號就夠了。
