命題論理の決定可能性
定理
証明
$ \varphiは命題論理の論理式とする
$ \varphiに登場する命題を$ p_1,p_2,\dots,p_nとする.
命題に対しての付値関数$ fについて,
$ f(p_1) = 1,f(p_2)=0,\dots,f(p_n)=1であるとき,$ f = (1,0,\dots,1)と表すことにする.
$ f_1 = (0,0,\dots,0,0)
$ f_2 = (0,0,\dots,0,1)
$ f_{2^n} = (1,1,\dots,1,1)
のように全ての可能性を列挙すると,$ 2^n個の付値関数$ f_iが決まる.
後は,関数$ f_iで$ \varphiを評価し,妥当であるかを判定する.
妥当であるかを判定するのは決定可能.
関数$ f_iも有限個しかない.
よって,$ \varphiが充足可能かどうかは決定可能である.