本篇進(jìn)行有效性和完備性的證明 上一篇講到命題邏輯的語義時(shí)，我們也能感受到 ? 和 ? 的相似之處，本篇將證明兩個(gè)定理，說明他們之間的充分必要關(guān)系。
命題邏輯的有效性（Soundness）
?1,?,?n?ψ??1,?,?n?ψ
定義：若?i=T(true),i∈{1,?,n} 時(shí) ψ 也為真，則 ?1,?,?n?ψ . 定理：?1,?,?n,ψ 都是命題公式, 則當(dāng) ?1,?,?n?ψ 有效時(shí) ?1,?,?n?ψ 證明：由于 ?1,?,?n?ψ 有效， 則有以 ?1,?,?n 為前提的有效證明，則對 ψ 公式長度歸納。 Base: 當(dāng)前提 ? 的長度為1， 也就是原子命題時(shí)。只可能有一種情況就是 ???, 顯然當(dāng) ?=T,?=T. 所以在長度為一時(shí)成立。
Inductive: 假設(shè)定理對長度小于 n 的公式都成立， 則當(dāng)長度為 n+1 時(shí)：
-如果最后的公式最外層的運(yùn)算是 ∧ , ?1∧?2=ψ 其中 ?1∧?2 的長度都小于等于 n+1， 則根據(jù) ?1=T 和 ?2=T 的規(guī)則，可以證明 ψ=?1∧?2=T 。這可以由上一篇的真值表得來。 同樣的之后對命題邏輯遞歸定義中出現(xiàn)的 ∨, → 做歸納就可以完成證明。
