轉載於 blog.csdn.net/on_1y/art

在完成命題邏輯系統的定義後，我們想知道這個系統的一切性質，其中最重要的性質就是可靠性與完備性。這一節的兩個定理告訴我們，命題邏輯系統滿足可靠性和完備性。

1 可靠性(Soundness)

1.1 可靠性是指什麼？

可靠性定理：令 φ1, φ2, …, φn 和 ψ 為命題邏輯中的公式，如果 φ1, φ2, …, φn |- ψ 是有效的， 那麼 φ1, φ2, …, φn |= ψ 是有效的。

這個定理是在說，我們為邏輯系統定義好語法和語義後，如果在語法上，我們可以利用推導規則，將φ1, φ2, …, φn 轉化為 ψ，

那麼在語義上，如果φ1, φ2, …, φn 都為T, 那麼ψ一定為T.

1.2 為什麼要引入可靠性的概念？

首先，我們需要理解，可靠性是邏輯系統滿足的一個性質。如果有一天，我們構造了另一個邏輯系統，自己定義了 語法，定義了語義，那麼，我們可能需要問一下自己：我定義的這個邏輯系統滿足可靠性麼？

上面的靠性定理是指在命題邏輯中，我們定義了語法：自然推導規則，推導及其有效性；我們定義了語義：真值表，語義蘊含及其有效性。在由這些定義構成的一個命題邏輯系統中，像可靠性定理描述的那樣的性質是滿足的。一旦我們 證明瞭一個邏輯系統滿足了可靠性，我們就可以利用這個好的性質來做一些事。

1.3 可靠性有什麼用？

現在我們明白了，之前定義的命題邏輯系統滿足可靠性。現在，我們就可以利用這一點來做一點事了。

我們可以利用邏輯系統的可靠性來確定：有一些證明是不存在的。

例如：在命題邏輯系統中給定前提 φ1, φ2, …, φn, 能否證明 ψ ？這其實是在問：

φ1, φ2, … , φn |- ψ 是否是有效的。

如果這個前提和結論非常複雜，那麼你很可能證明不出來，因為證明通常是需要一點靈感的，而靈感通常是難得的。 但是，你證明不出來不能說明這個證明不存在。那我們應該怎麼做呢？

有了可靠性定理，我們就可以將問題轉化為： φ1, φ2, … , φn |= ψ 是否是有效的。

而這個問題，我們完全可以用真值表來確定。

假如我們用真假表確定了， φ1, φ2, … , φn |= ψ 是無效的, 那麼，我們完全可以斷言：

φ1, φ2, … , φn |- ψ 是無效的。即證明不存在。

因為根據可靠性定理，如果 φ1, φ2, …, φn |- ψ 是有效的， 那麼 φ1, φ2, …, φn |= ψ 是有效的， 與我們根據真值表得出的結論相矛盾。

2 完備性(Completeness)

2.1 完備性是指什麼？

完備性定理：令 φ1, φ2, …, φn 和 ψ 為命題邏輯中的公式，如果 φ1, φ2, …, φn |= ψ 是有效的， 那麼 φ1, φ2, …, φn |- ψ 是有效的。

可以看出，這和可靠性定理的定義正好相反。這其實是在說，在一個邏輯系統中，如果從語義上看， φ1, φ2, …, φn |= ψ 是有效的， 那麼我們一定可以為φ1, φ2, …, φn |- ψ 找到一個證明。

在命題邏輯中，完備性定理也是成立的。具體的證明過程參考1

2.2 完備性有什麼用？

與可靠性一樣，完備性也是邏輯系統的性質。那麼完備性有什麼用呢？在一個邏輯系統中，如果我們知道一些前提是 真的，即 φ1, φ2, …,φn 都為真，那麼，我們想知道在這樣的條件下，結論 ψ 也一定是真嗎？即我們想知道 φ1, φ2, …, φn |= ψ 是否是有效的。那麼我們可能想找一個由φ1, φ2, …, φn 到 ψ 的證明，即利用推導規則將 φ1, φ2, …, φn 轉化為 φ. 這時候，完備性就會告訴我們， 如果 φ1, φ2, …, φn |= ψ 是有效的，那麼，這樣 的證明一定存在。假如你的邏輯系統不滿足完備性，那麼即使φ1, φ2, …, φn |= ψ 是有效的，但是它的證明也可能 不存在，那你的努力可能就是徒勞的。

原文：命題邏輯中的語法與語義，可靠性與完備性 - on_1y - CSDN博客


推薦閱讀：
查看原文 >>
相關文章