2,761
次編輯
「形式邏輯筆記/第六章」修訂間的差異
→存在量詞(existential qualifier)
Tankianting（討論 | 貢獻） |
Tankianting（討論 | 貢獻） |
||
| （未顯示同一使用者於中間所作的 4 次修訂） | |||
| 行 3： | 行 3： | ||
'''第六章 證明''' | '''第六章 證明''' | ||
證明：一堆命題序列，由premises（前件）推論到結論。 | |||
本文使用 Fitcher 的演繹證明格式，證明與排版產生器請參此網站：https://mrieppel.github.io/fitchjs/ | 本文使用 Fitcher 的演繹證明格式，證明與排版產生器請參此網站：https://mrieppel.github.io/fitchjs/ | ||
| 行 225： | 行 225： | ||
*存在消除 ∃E | *存在消除 ∃E | ||
** | **假設有人工變數c，使得P x推演到B，那麼∃x P x 可證明 B | ||
<pre> | <pre> | ||
m | ∃x P x | m | ∃x P x | ||
n | |_ | n | |_ Pc | ||
p | | B | p | | B | ||
| B ∃E m, n-p | | B ∃E m, n-p | ||
註：c 不能出現於B、子證明之外，以及 P x裏面。 | |||
</pre> | </pre> | ||
| 行 251： | 行 251： | ||
</pre> | </pre> | ||
==6.6證明的策略== | ==6.6證明的策略== | ||
包含下列策略 | |||
* 不要忘記反證法 | |||
* 從目標往回推 | |||
* 從前提往前推 | |||
* 善用替換律 | |||
等 | |||
==6.7證明定理觀念== | |||
* <math>A_1, A_2, ...</math>|-B 表示那些<math>A_i</math>可以證明B。 | |||
* A |- B，表示 B 是 A 的 derivation（衍生）。 | |||
* |- T，則T是定理，不需要任何前件。 | |||
* provably equivalent（證明等價）↔ A |- B 且 B |- A | |||
* <math>A_1, A_2, ...</math> 是證明不一致(provably inconsistent)↔從其中推導出矛盾。如 B , {A_1, A_2, ...} |- B 且 {A_1, A_2, ...} |- ~B。 | |||
==6.8證明與模型== | |||
* 證明一個定理比證明全真句還簡單。反之，證明命題不是定理比證明命題不是全真句還困難。 | |||
* A |- B <-> A |= B（一般而言。註：但是自然數不適用） | |||
**argument vaild<->結論從前件 (premise) 推導出來 | |||
**證明等價 <-> 邏輯等價 | |||
**一致性(consistent) <-> 不是證明不一致。 | |||
何時使用模型？何時使用證明？ | |||
{| class="wikitable" | |||
|- | |||
! 敘述 !! 說明是 !! 說明否 | |||
|- | |||
| A是全真句？ || 證明A || 找模式說A是假的 | |||
|- | |||
| A是矛盾句？ || 證明~A || 用模式說明A是真的 | |||
|- | |||
| A是非全真句？ || 用兩個模型，一個說明A真的，另一個說明A是假的。 || 證明A或證明~A | |||
|- | |||
| A和B等同？ || <nowiki>證明A|-B和B|-A</nowiki> || 用模式說明A和B真僞值不同 | |||
|- | |||
| 命題集合A一致？ || 給模式說明A的所有命題為真 || 從A證明B和~B | |||
|- | |||
| P,∴C valid？ || 證明 P|-C || 給模型說明 P 為真 C 為假。 | |||
|} | |||
==6.9 soundness and completeness== | ==6.9 soundness and completeness== | ||
| 行 258： | 行 297： | ||
*若是任何 A |= B 則 A |- B，則具有完備性 completeness，就是任何為真的命題可以證明出來。 | *若是任何 A |= B 則 A |- B，則具有完備性 completeness，就是任何為真的命題可以證明出來。 | ||
*哥德爾證明謂詞邏輯是完備性的（註：自然數的證明就不是了）。 | *哥德爾證明謂詞邏輯是完備性的（註：自然數的證明就不是了）。 | ||
{{ForAllX}} | |||
[[category:邏輯學]] | |||