整論理式の構成である原子論理式や項について一から丁寧に説明してみた

|| 数学の基礎となる言語に相当するもの

『数学の言語』というとだいたいこれです

論理式の概要

「論理式」というのは

『項と関係から作られる原子論理式』と

$\begin{array}{ccc} φ,ψ &\in& \mathrm{AtomicFormula} \end{array}$

『原子論理式と論理記号の組み合わせ』で

$\begin{array}{lcc} φ,ψ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ \lnot φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ φ∧ψ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ φ∨ψ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ φ⇒ψ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ φ⇔ψ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \end{array}$

「変数 $x$ 」を付け加えると

（以下の $φ$ は原子論理式であればなんでもいい）

$\begin{array}{lcc} \forall x \,\, φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ \exists x \,\, φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \end{array}$

↑ と合わせてこんな感じになります。

（以下、これの詳細を解説していきます）

論理記号 Logical Symbol

|| 真偽を確定させられる操作を表現する記号

『演繹ができる記号』のことで

$\begin{array}{lllllll} 1&\top&\mathrm{T}&&&\mathrm{True} \\ \\ 0&\bot&\mathrm{F}&&&\mathrm{False} \\ \\ \\ \lnot & & &&&\mathrm{not} \\ \\ \land && &&& \mathrm{and} \\ \\ \lor && &&& \mathrm{or} \\ \\ \displaystyle \to & & &&&\mathrm{if}\text{-}\mathrm{then} \\ \\ \leftrightarrow&\equiv& &&&\mathrm{equal} \\ \\ \\ \forall&& &&&\mathrm{All} \\ \\ \exists&& &&&\mathrm{Exist} \\ \\ \\ ()&& &&&\mathrm{unit} \\ \\ \coloneqq&\equiv& &&&\mathrm{define} \\ \\ \\ \vdash&& &&&\mathrm{proof} \\ \\ \vDash&& &&& \mathrm{implication} \\ \\ \\ \therefore&& &&&\mathrm{Therefore} \\ \\ \because && &&&\mathrm{Because} \end{array}$

具体的にはこれらのことを指します。

（量化範囲はだいたい一階述語論理に限定される）

非論理記号 Non-(Logical Symbol)

|| 論理記号以外の数学で扱う記号

そのまま「論理記号じゃない記号」のことで

$\begin{array}{cccc} 0&1&2&10 \\ \\ >&<&≧&≦ \\ \\ +&-&×&÷ \end{array}$

こちらの方が圧倒的に多いです。

（論理記号はあくまで論理の基礎になる操作の表現）

$\begin{array}{llllll} \displaystyle \mathrm{non}\text{-}\mathrm{ Logical \,\, Symbol }&\equiv&\mathrm{Symbol}\setminus \mathrm{ Logical \,\, Symbol } \end{array}$

『人が扱う記号』の内

ほとんどはこれに該当します。

非論理記号の分類

これらは大きく４つに分類することが可能で

$\begin{array}{ccl} 非論理記号 & \left\{ \begin{array}{lclc} 定数記号 && 0,1,2,...,a,b,c,... \\ \\ 変数記号 && x,y,z,... \\ \\ 関数記号 && +,-,...,f,g,h,... \\ \\ 述語記号 && \in, = , <,..., R ,... \end{array} \right. \end{array}$

これらの総称が「非論理記号」になります。

（無数に作れるので重要なのは分類になる）

引数の個数 Arity

「関数記号」「述語記号」の

『引数の個数』については

$\begin{array}{ccl} 1+2 && \mathrm{Arity}(+)=2 \\ \\ f(x_1,...,x_n) && \mathrm{Arity}(f)=n \\ \\ \\ a=b && \mathrm{Arity}(=) =2 \\ \\ e \in S && \mathrm{Arity}(\in) =2 \\ \\ R(x_1,...,x_n) && \mathrm{Arity}(R)=n \end{array}$

実は「記号の定義時点」で定められるため

必ず固定された値になります。

（変数のように振る舞わない）

$\begin{array}{ccc} \mathrm{Arity}(2) &=&0 \end{array}$

また定数のアリティは必ずこうなるため

定数はアリティ $0$ の関数記号とも言われます。

関数記号の例外

補足しておくと

$\begin{array}{lllrlllll} \displaystyle \sum_{k=1}^{n}a_k&=&a_1+a_2+a_3+\cdots +a_{n-1}+a_n&+&0 \\ \\ \displaystyle \sum_{}^{}&=& & &0 \\ \\ \\ \displaystyle\prod_{k=1}^{n}a_k&=&a_1\times a_2\times a_3 \cdots a_{n-1} \times a_n &\times&1 \\ \\ \displaystyle \prod_{}^{}&=& & &1 \end{array}$

このような大型演算子は

$\begin{array}{lllll} \displaystyle \sum_{}^{}&=&0 \\ \\ \displaystyle \prod_{}^{}&=&1 \end{array}$

『アリティが固定された関数記号』とは言えず

「関数記号」の定義を逸脱します。

しかし「使う引数が最初から分かってる」なら

（引数が可変ではないとして総和演算子を考える）

$\begin{array}{ccc} \displaystyle \sum_{k=1}^{n}a_k &&\displaystyle \mathrm{Arity}\left( \sum_{k=1}^{n} \right)=n \end{array}$

これは「アリティ $n$ の関数記号」になります。

（つまり引数を数えた後に定義すれば関数になる）

言語 Language

|| 非論理記号について定義するとできあがる成果物

「定数」「変数」「関数」「述語」の記号の集まり

$\begin{array}{ccc} Lは言語である &\Longleftrightarrow& L=(\mathrm{Const},\mathrm{Var},\mathrm{Func},\mathrm{Pred}) \end{array}$

全体像としてはこのように定義されますが

この時点では定義として不十分になります。

記号集合の定義

「言語 $L$ 」の定義において

まず最初に定義される部分は

$\begin{array}{lcl} \mathrm{Const}は定数記号集合 &\Longleftrightarrow& \mathrm{Const}の要素は定数記号 \\ \\ \mathrm{Var}は変数記号集合 &\Longleftrightarrow& \mathrm{Var}の要素は変数記号 \\ \\ \mathrm{Func}は関数記号集合 &\Longleftrightarrow& \mathrm{Func}の要素は関数記号 \\ \\ \mathrm{Pred}は述語記号集合 &\Longleftrightarrow& \mathrm{Pred}の要素は述語記号 \end{array}$

これら「記号の集合」についての定義で

（「言語である」という述語の要請的定義はここで終わり）

$\begin{array}{lcl} c\in \mathrm{Const} &\Longleftrightarrow& cは定数記号である \\ \\ x\in \mathrm{Var} &\Longleftrightarrow& xは変数記号である \end{array}$

まずこれが定義されてから「言語」は定義されます。

（関数記号と述語記号はこの時点では定義不十分）

アリティの定義

「記号集合の定義」の後に必要なのが

$\begin{array}{ccc} f(x,y) &\Longrightarrow& fはアリティ2の関数記号である \end{array}$

「関数記号」「述語記号」の定義で必要になる

「アリティ」の表現方法となる定義で

$\begin{array}{lcl} f^n\in \mathrm{Func} &\Longleftrightarrow& fはアリティnの関数記号である \\ \\ P^n\in \mathrm{Pred} &\Longleftrightarrow& Pはアリティnの述語記号である \end{array}$

これにより

「アリティ」の情報を付加した

「関数記号」「述語記号」を表現できるようになります。

言語の中身の定義

以上の前提が整った後

$\begin{array}{ccc} 実際の運用 & \left\{ \begin{array}{l} 新しい変数記号が必要→その場で導入 \\ \\ 新しい関数記号が必要→その場で定義 \\ \\ 新しい述語記号が必要→その場で追加 \end{array} \right. \end{array}$

「言語」の『具体的な中身』は定義できるようになり

（基本的には最初から無限に用意されてる）

$\begin{array}{lcl} \mathrm{Const}&=& \{a,b,c,α,β,ε ,...,a_1,a_2,...,a_n,...\} \\ \\ \mathrm{Var}&=& \{x,y,z,p,q,r,...,x_1,x_2,...x_n,...\} \\ \\ \mathrm{Func}&=& \{+^2,×^2,...,f^2,g^2,...,f^n,...\} \\ \\ \mathrm{Pred}&=& \{\in^{2},=^{2},<^2,...,R^n,...\} \end{array}$

これによって「論理式」の定義の準備が完了します。

（これは構成的定義でアリティの定義までが要請的定義）

項 Term

|| 分かるようで分からない単語

これは「変数」と「定数」のことで

$\begin{array}{ccc} 定数 && 0,1,a,b,c &\in& \mathrm{Term} \\ \\ 変数 && x,y,z &\in& \mathrm{Term} \\ \\ 関数 && 1+1,a+b,f(x,y) &\in& \mathrm{Term} \end{array}$

その中身はこんな感じになっています。

（関数は定数か変数を出力します）

関数という単語の注意点

この「項」は記号ベースというより

$\begin{array}{ccc} 1+2, \,\, 2\times 3, \,\, a+b, \,\, 1+x, \,\, f(x,y) && 〇 \\ \\ +,\times, f && × \end{array}$

「定数」「変数」ベースなので

「関数記号」は定義に含まれていません。

項と関数記号の組み合わせ

「関数」は「定数か変数を出力する」ので

$\begin{array}{ccc} f(x) &\to& c,x \end{array}$

↑ の定義のままでも特に問題は無いんですが

$\begin{array}{ccc} 1+1+1&=&1+(1+1) \\ \\ & & f(a,f(b,c)) \end{array}$

同様の理屈で

これも「項」だと言えるので

$\begin{array}{ccc} \mathrm{Constant} &\in& \mathrm{Term} \\ \\ \mathrm{Variable} &\in& \mathrm{Term} \\ \\ \\ \mathrm{Function}(\mathrm{Constants}) &\in& \mathrm{Term} \\ \\ \mathrm{Function}(\mathrm{Variables}) &\in& \mathrm{Term} \end{array}$

↑ の定義を踏まえた上で

$\begin{array}{ccc} \mathrm{Function}(\mathrm{Term}) &\in& \mathrm{Term} \end{array}$

これもまた「項」と呼ばれます。

（ここまでが項の厳密な定義）

原子論理式 Atomic Formula

|| 最小サイズの論理式

これは「真偽を判定できる最小単位」になるもので

$\begin{array}{ccc} a=b, \,\, e\in S, \,\, x<y &\in& \mathrm{AtomicFormula} \\ \\ R(t_1,t_2,...,t_n) &\in& \mathrm{AtomicFormula} \end{array}$

その定義はこのようになっています。

（項と同様に関係記号は含まない）

補足しておくと

$\begin{array}{ccc} a=b &\to& R(t_1,t_2) &\to& =(a,b) \\ \\ e\in S &\to& R(t_1,t_2) &\to& \in (e,S) \\ \\ x<y &\to& R(t_1,t_2) &\to& <(x,y) \end{array}$

私たちが扱う関係はだいたい「二項関係」です。

（無いことはないけど他はあんまり見ない）

整論理式 Well-Formed Formula

|| 数学のスタンダードな言語になるもの

「論理式」というとだいたいこれを指していて

$\begin{array}{ccc} φ,ψ &\in& \mathrm{AtomicFormula} \end{array}$

↑ で紹介したように

「命題記号」の部分については

このような形で定義されています。

「量化」に関しても

$\begin{array}{lcc} \forall x \,\, φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ \exists x \,\, φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \end{array}$

紹介した通りなんですが

$\begin{array}{ccc} \forall x & & \exists x \end{array}$

この部分については

「一階述語論理の範囲」という制限があり

（個体『自由変数または束縛変数』の量化まで）

$\begin{array}{ccc} f(x) &\to& \forall x && 〇 \\ \\ f(x) &\to& \forall f && × \end{array}$

具体的にはここまでしか許されてません。

（二階以上だと $f$ も量化が許される）

帰納的に定義するために

実は ↑ の定義はまだ不足していて

$\begin{array}{ccc} φ,ψ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \end{array}$

↑ までの定義から得られたこれから

（原子論理式と記号の組み合わせのみ）

「命題記号」についてと

$\begin{array}{lcc} \forall x \,\, φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \\ \\ \exists x \,\, φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \end{array}$

「量化記号」についての定義を

それぞれまた追加でする必要があります。

（ ↑ と合わせてここまでが整論理式の厳密な定義）

というのも

↑ の時点では

$\begin{array}{ccc} \forall x \,\, \Bigl( \forall y \,\, φ \Bigr) \end{array}$

こういった「整論理式と記号の組み合わせ」は

「整論理式」とは呼べない状態にありました。

しかし「論理式」に対する要請は

（論理式にしたいという直感的な要求）

$\begin{array}{ccc} \forall x \,\, \forall y \,\, φ &\in& \mathrm{Well}\text{-}\mathrm{Formed}\mathrm{Formula} \end{array}$

これも「論理式である」ことを求めているので

結果、この定義が必要になります。

（最小の形 → それを拡張する形）

目次

論理式の概要

論理記号 Logical Symbol

非論理記号 Non-(Logical Symbol)

非論理記号の分類

引数の個数 Arity

関数記号の例外

言語 Language

記号集合の定義

アリティの定義

言語の中身の定義

項 Term

関数という単語の注意点

項と関数記号の組み合わせ

原子論理式 Atomic Formula

整論理式 Well-Formed Formula

帰納的に定義するために