定理

維基百科,自由的百科全書
前往: 導覽搜尋
Confusion grey.svg
提示:本條目的主題不是科學定律

定理英語Theorem)是經過受邏輯限制的證明為真的陳述。一般來說,在數學中,只有重要或有趣的陳述才叫定理。證明定理是數學的中心活動。一個定理陳述一個給定類的所有(全稱)元素一種不變的關係,這些元素可以是無窮多,它們在任何時刻都無區別地成立,而沒有一個例外。(例如:某些ax,某些ay,就不能算是定理)。

猜想是相信為真但未被證明的數學敘述,或者叫做命題,當它經過證明後便是定理。猜想是定理的來源,但並非唯一來源。一個從其他定理引伸出來的數學敘述可以不經過成為猜想的過程,成為定理。

如上所述,定理需要某些邏輯框架,繼而形成一套公理公理系統)。同時,一個推理的過程,容許從公理中引出新定理和其他之前發現的定理。

命題邏輯,所有已證明的敘述都稱為定理。

各種數學敘述(按重要性來排列)[編輯]

  1. 引理(又稱輔助定理補理)-某個定理的證明的一部分的敘述。它並非主要的結果。引理的證明有時還比定理長,例如舒爾引理
  2. 推論-一個從定理隨之而即時出現的敘述。若命題B可以很快、簡單地推導出命題A,命題A為命題B的推論。
  3. 命題
  4. 定理
  5. 數學原理

結構[編輯]

定理一般都有許多條件。然後有結論——一個在條件下成立的數學敘述。通常寫作「若條件,則結論」。用符號邏輯來寫就是條件→結論。而當中的證明不視為定理的成分。

逆定理[編輯]

若存在某敘述為A→B,其逆敘述就是B→A。逆敘述成立的情況是A←→B,否則通常都是倒果為因,不合常理。若果敘述是定理,其成立的逆敘述就是逆定理

  • 若某敘述和其逆敘述都為真,條件必要且充足
  • 若某敘述為真,其逆敘述為假,條件充足。
  • 若某敘述為假,其逆敘述為真,條件必要。

邏輯中的定理[編輯]

在邏輯語言中的定理,它表示一個公式集合,並且該公式集合中的每一個公式都代表著知識的一個片段,由此我們可以給定理一個更準確的表達(這裡所說的定理指的是在一階邏輯中的定理,通常來說任意一個命題集合往往不一定是定理)。
定理在邏輯中的定義
一個定理是一個含有(L-propositions)由建立於語言集合L上的命題組成的非空集合,這個定理(或這個命題集合)我們記作T,這些建立於語言集合L上的命題必須符合如下屬性:
對所有在T中的命題φ(L-propositions),如果T |= φ,那麼φ∈T
比如 一個永真命題集合是一個定理,這個永真命題集合被包含在所有建立在語言集合L上的定理中
我們說一個定理是另外一個定理T的擴展(extension),前提是該定理包含定理T
有一個命題集合A,我們稱一個集合命題集合A的定理(記作)Th(A),當Th(A)={ φ | A |= φ }
顯而易見A |= Th(A),所以Th(A)是一個定理
比如我們有一個集合,記做G,G有三個基於語言L上的命題,語言L={ e,f },其中e是常數符號,f是函數符號
三個命題如下:
\forall x \forall y \forall z f(f(x,y),z)=f(x,f(y,z)),
\forall x  f(x,e)=x \and f(e,x)=x,
\forall x \exist y f(x,y)=e \and f(y,x)=e
那麼如果有Th(G)={ φ | G |= φ },那麼Th(G)是G的定理
當然如果A和B是兩個命題集合且滿足A⊆B,那麼Th(A)⊆Th(B)
我們說一個定理T是完整的(Complete),若且唯若對於和T一樣構建在同樣語言集合上的所有命題φ,要麼φ∈T,要麼˥φ∈T
注意:這個概念不能和定理T的完備性(Completude)混淆,完備性是證明在定理T中的永真命題是遞推可枚舉的(recursivement enumerable),但是不能說它一定是完整的
一個定理T稱作是穩健的(Consistante),若且唯若∀φ∈T,˥φ∉T
不是所有的定理T是完整的
比如Th(Φ)一個空集合{Φ}的定理是所有真命題集合,但是Th(Φ)不是完整的
假如我們有ψ= ∃x∃y x≠y對於ψ來說,它既不是永真命題,也不是永假命題,它是一個可滿足式的命題,
也就是說Th(Φ)|ǂ ψ且Th(Φ)|ǂ ˥ψ
因此ψ∉Th(Φ),所以我們說Th(Φ)不是完整的
我們說對所有的解釋(Interpretation)I,Th(I)是一個定理,並且Th(I)既是穩健的又是完整的

命題集合的可計算性問題(Calculabilite)[編輯]

我們可以通過可計算性(Calculabilite)這一概念來解釋命題集合的滿足性問題,也就是說是對於命題集合在可決定性問題上(Decidabilite)是否存在一個肯定的測試結果,還是一個否定的測試結果 我們知道當我們用任何一種計算機語言編寫程序編譯成功並執行中,在計算機上執行的目標代碼是以二進制表示的一串0和1的組合比如01010011........... 如果轉化成十進制表示的話,這個二進制組合就對應一個實數 更進一步,對於一個任一公式φ(公式是一個演算法),我們通過計算機編程實現公式φ的演算法,根據上面的描述,該程序必定有一個唯一的實數與之對應 也就是說φ→ n(φ)n(φ)是一個代表由公式φ所對應的實數(這個函數是單射的(Injection)) 那麼我就可以簡單的通過一個一一對應(Bijection)的函數g對應於某一個一階邏輯的公式集合印射到到自然數集合中 那麼我們假設公式集合中有ψ個公式,ψ是一個自然數,對於公式集合中的每一個公式,我們假設{φ0,φ1,....},它們對應的自然數n(φi)<ψ 通過這樣的方式我們把邏輯和計算機可計算性問題相聯繫,也就是說如果要證明一階邏輯公式的可滿足性問題轉化成計算機可計算性的問題加以證明,如果在計算機可決定性問題的證明中,證明它是一個可決定的問題,既它是一個肯定測試,那麼對於對應的邏輯公式來說,該公式必定是可滿足的

  • 定理1一個沒有量詞(Quantificateur)的有限命題集合Γ的可滿足性問題(Satisfaisabilite)是可以決定的(Decidable)
證明:假設命題集合Γ中的每個元素由以下組成:
一個以語言集合L構建的項集合(L-Term),我們記作項集合T,根據項的組成語法規則,T肯定是有有限個數的項,並且每個項是由語言集合L中的符號有限組成。
如果T為空集(即空項集合),那麼我們在SAT命題的情況下,Γ就認為是可決定的(Decidable)。
如果Γ是可滿足的,假設存在一個解釋(或模型)I, I |= Γ,I的解釋域是D,假設存在另外一個解釋域D',滿足以下條件D'=I(T)={I(t)∈D|t∈T}
我們在D'上定義另一個解釋(或模型)I',定義如下:

//如果……(under construction)

  • 定理2一階邏輯命題的永真性(Validite)是可以通過一個肯定測試(Test Positif)來知道的。
    • 證明:
  • 定理3所有公理化(Axiomatisable)的定理T是可遞推枚舉的(Recursivement Enumerable)。
    • 證明:
  • 定理4所有公理化的完整的(Complete)定理T是可遞推的。
    • 證明:
  • 定理5所有可遞推枚舉的定理T是公理化的。
    • 證明:

參見[編輯]