完全集

設 F 是 n 元聯結詞，p₁,…,p_n 是不同的命題變元。如果公式 A 中不出現除 p₁,…,p_n 之外的命題變元，並 A⇔Fp₁…p_n，則稱 A 定義 F。如果存在由聯結詞集合 S 生成的公式定義 F ，則稱 F 可由 S 定義。

基本介紹

• 中文名：完全集
• 外文名： Adequate Set，complete set
• 適用範圍：數理科學

定義

設 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個常用符號（~, ∧, ∨, →, ?）分別用該集合中的連線詞表示出來。如果承認 {~, ∧} 是完全集，那么只表示這兩個符號就夠了。