Σ論理式およびΠ論理式
前提
定義
量化としては有界量化だけ含む論理式は$ \Delta_0論理式という. $ \Delta_0論理式の集合はクラス$ \Delta_0と呼ぶ.
クラス$ \Delta_0の論理式は,クラス$ \Pi_0とクラス$ \Sigma_0にも含まれるとする.
すなわち,表記上$ \Delta_0 = \Sigma_0 = \Pi_0とする.
$ \varphiが$ \Pi_k論理式であったとき,$ \exists_x.\varphiとなる$ \psiは$ \Sigma_{k+1}論理式である.
$ \Sigma_k論理式の集合はクラス$ \Sigma_kと呼ぶ.
$ \varphiが$ \Sigma_k論理式であったとき,$ \forall_x.\varphiとなる$ \psiは$ \Pi_{k+1}論理式である.
$ \Pi_k論理式の集合はクラス$ \Pi_kと呼ぶ.
クラス$ \Sigma_nと$ \Pi_nの両方に含まれる論理式の集合はクラス$ \Delta_nと呼ぶ.
注意
任意の論理式には同値な冠頭標準形が存在するので,少なくともどこかのクラスに含まれる. クラス$ \Sigma_nに含まれる論理式は全てクラス$ \Sigma_{n+1}にも含まれる.同様にクラス$ \Pi_nに含まれる論理式は全てクラス$ \Pi_{n+1}にも含まれる.
これを$ \Sigma_n \sube \Sigma_{n+1},$ \Pi_n \sube \Pi_{n+1}と表す.
なぜ$ \Sigma,\Piなのか?
$ \exists_x .P(x) \equiv P(0) \lor P(1) \lor P(2) \lor \cdots
と無限の$ \lorで結んだものと考えることが出来る.
もちろん有界量化$ \exists_{x<m}. P(x)ならどこかで打ち切ることが出来る.ともあれ
これに由来して,$ \existsで量化する論理式を$ \Sigma論理式という.
$ \forall_x.P(x) \equiv P(0) \land P(1) \land P(2) \land \cdots
と無限の$ \landで結んだものと考えることが出来る.
Boole代数とのアナロジーで$ \landを論理積ということがある. これに由来して,$ \forallで量化する論理式を$ \Pi論理式という.