一階述語論理
[Wikipedia|▼Menu]

一階述語論理の項 (term) は次のように帰納的に定義される:
変数と定数記号はすべて項である。

t 1 , ⋯ , t n {\displaystyle t_{1},\,\cdots ,\,t_{n}} が項で、 f {\displaystyle f} がアリティ n の関数記号ならば、 f t 1 , ⋯ , t n {\displaystyle ft_{1},\,\cdots ,\,t_{n}} は項である
[2]

上記の 1. と 2. によって項とされるものだけが項である。

項というのは直観的には議論領域に属するある対象を表す"名前"の役割をもった記号列である。

例. 自然数論の言語は等号を持つ一階の言語で、非論理記号として 、 1 {\displaystyle 1} 変数関数記号 S {\displaystyle S} 、 2 {\displaystyle 2} 変数関数記号 + {\displaystyle +} , ⋅ {\displaystyle \cdot } と定数記号 0 {\displaystyle 0} を持つ。定義より、 x 1 {\displaystyle x_{1}} ,   x 5 {\displaystyle x_{5}} ,   0 {\displaystyle 0} ,   S x 1 {\displaystyle Sx_{1}} ,   S 0 {\displaystyle S0} ,   S S 0 {\displaystyle SS0} ,   + S 0 S 0 {\displaystyle +S0S0} ,   + 0 x 5 {\displaystyle +0x_{5}} ,   ⋅ S x 1 + 0 x 5 {\displaystyle \cdot Sx_{1}+0x_{5}}

はすべて項である。 + S 0 S 0 {\displaystyle +S0S0} や + 0 x 5 {\displaystyle +0x_{5}} といった前置記法は読みにくいため、これらの項を表すのに、通常使われている S ( 0 ) + S ( 0 ) {\displaystyle S(0)+S(0)} や 0 + x 5 {\displaystyle 0+x_{5}} のような表現(中置記法)が用いられることもある。したがって ⋅ S x 1 + 0 x 5 {\displaystyle \cdot Sx_{1}+0x_{5}} は中置記法では S ( x 1 ) ⋅ ( 0 + x 5 ) {\displaystyle S(x_{1})\cdot (0+x_{5})} のように表される。
論理式

項が何らかの対象を表す記号列であったのに対して、論理式は何らかの命題を表すものである。論理式は原子論理式と呼ぶ最も基本的な論理式から結合記号と量化記号を繰り返し用いることによって形成される。まず、原子論理式は次のように定義される:ある正の整数 n {\displaystyle n} に対するアリティ n {\displaystyle n} の述語記号 P {\displaystyle P} と n {\displaystyle n} 個の項 t 1 , ⋯ , t n {\displaystyle t_{1},\,\cdots ,\,t_{n}} を用いて P ( t 1 , ⋯ , t n ) {\displaystyle P(t_{1},\,\cdots ,\,t_{n})} と表される記号列を原子論理式 (atomic formula) と呼ぶ。

原子論理式を用いて、論理式 (well-formed formula, wff) あるいは式 (formula) は次のように帰納的に定義される:
原子論理式は論理式である。

ϕ {\displaystyle \phi } と ψ {\displaystyle \psi } が論理式ならば、 ( ¬ ϕ ) {\displaystyle (\lnot \phi )} , ( ϕ ∧ ψ ) {\displaystyle (\phi \land \psi )} , ( ϕ ∨ ψ ) {\displaystyle (\phi \lor \psi )} , ( ϕ ⇒ ψ ) {\displaystyle (\phi \Rightarrow \psi )} , ( ϕ ⇔ ψ ) {\displaystyle (\phi \Leftrightarrow \psi )} は論理式である。

ϕ {\displaystyle \phi } が論理式で x {\displaystyle x} が変数ならば、 ( ∀ x ϕ ) {\displaystyle (\forall x\phi )} , ( ∃ x ϕ ) {\displaystyle (\exists x\phi )} は論理式である。

上記の 1. と 2. と 3. によって論理式とされるものだけが論理式である。

例. 再び自然数論の言語を考える。定義から、 [ ( S 0 + S 0 ) = S S 0 ] {\displaystyle [(S0+S0)=SS0]} ,  [ ( 0 + x 5 ) = S 0 ] {\displaystyle [(0+x_{5})=S0]}

はすべて原子論理式(したがって論理式)であり、 { ¬ [ ( S 0 + S 0 ) = S S 0 ] } {\displaystyle \{\lnot [(S0+S0)=SS0]\}} ,   { [ ( 0 + x 5 ) = S 0 ] ∧ [ ( S 0 + S 0 ) = S S 0 ] } {\displaystyle \{[(0+x_{5})=S0]\land [(S0+S0)=SS0]\}} ,   { ∀ x 5 [ ( 0 + x 5 ) = S 0 ] } {\displaystyle \{\forall x_{5}[(0+x_{5})=S0]\}} ,   { ∃ x 2 [ ( 0 + x 5 ) = S 0 ] } {\displaystyle \{\exists x_{2}[(0+x_{5})=S0]\}}
自由変数

自然数論の言語における論理式 ( S 0 + S 0 ) = S S 0 {\displaystyle (S0+S0)=SS0} の各記号を通常の意味で解釈すれば「 1 + 1 = 2 {\displaystyle 1+1=2} 」となり、これは真である論理式である。 ¬ [ ( S 0 + S 0 ) = S S 0 ] {\displaystyle \lnot [(S0+S0)=SS0]} は「 1 + 1 ≠ 2 {\displaystyle 1+1\neq 2} 」となるので通常の解釈で偽なる論理式である。また、変数の動く範囲(議論領域)は自然数全体の集合だとすれば、論理式 [ ∀ x 1 ( 0 = S x 1 ) ] {\displaystyle [\forall x_{1}(0=Sx_{1})]} は「すべての自然数 n {\displaystyle n} について 0 = n + 1 {\displaystyle 0=n+1} 」という意味になり、これは偽である論理式であることが分かる。


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:83 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef