本篇進行有效性和完備性的證明 上一篇講到命題邏輯的語義時，我們也能感受到 ?$/vdash$ 和 ?$/models$ 的相似之處，本篇將證明兩個定理，說明他們之間的充分必要關系。

命題邏輯的有效性（Soundness）

?1,?,?n?ψ??1,?,?n?ψ$/phi_1,/cdots,/phi_n/vdash /psi /Rightarrow /phi_1,/cdots,/phi_n/models /psi$

定義：若?i=T(true),i∈{1,?,n}$/phi_i = T(true), i/in /{1,/cdots,n/}$ 時 ψ$/psi$ 也為真，則 ?1,?,?n?ψ$/phi_1,/cdots,/phi_n/models /psi$ . 定理：?1,?,?n,ψ$/phi_1,/cdots,/phi_n,/psi$ 都是命題公式, 則當 ?1,?,?n?ψ$/phi_1,/cdots,/phi_n/vdash /psi$ 有效時 ?1,?,?n?ψ$/phi_1,/cdots,/phi_n/models /psi$ 證明：由于 ?1,?,?n?ψ$/phi_1,/cdots,/phi_n/vdash /psi$ 有效， 則有以 ?1,?,?n$/phi_1,/cdots,/phi_n$ 為前提的有效證明，則對 ψ$/psi$ 公式長度歸納。 Base: 當前提 ?$/phi$ 的長度為1， 也就是原子命題時。只可能有一種情況就是 ???$/phi /vdash /phi$, 顯然當 ?=T,?=T$/phi = T, /phi = T$. 所以在長度為一時成立。

Inductive: 假設定理對長度小于 n 的公式都成立， 則當長度為 n+1 時：

-如果最后的公式最外層的運算是 ∧$/wedge$ , ?1∧?2=ψ$/phi_1/wedge/phi_2 = /psi$ 其中 ?1∧?2$/phi_1/wedge/phi_2$ 的長度都小于等于 n+1， 則根據 ?1=T$/phi_1 = T$ 和 ?2=T$/phi_2 = T$ 的規則，可以證明 ψ=?1∧?2=T$/psi = /phi_1 /wedge /phi_2 = T$ 。這可以由上一篇的真值表得來。 同樣的之后對命題邏輯遞歸定義中出現的 ∨$/vee$, →$/rightarrow$ 做歸納就可以完成證明。