構成規則

数理論理学における構成規則（こうせいきそく、英: Formation rule）もしくは形成規則とは、アルファベットからなる記号列のうち、どれが当該言語で統語論的に正しいかを定める規則である。構成規則で言及されるのは記号列の配置や操作といった統語論的対象のみであり、従って式のテンプレート:仮リンクを定めるに先立って定義されている（形式文法も参照）。

形式体系

テンプレート:Main アルファベット、構成規則、ならびにテンプレート:仮リンクからなる体系は形式体系と呼ばれる。ここで、推論体系とは推論規則の集合と公理の集合の一方もしくはその両方からなる体系をいう。形式体系を定めれば、一つまたは複数の式から別の一つの式を演繹できるようになる。命題論理や述語論理は形式体系の例である。

命題論理と述語論理

命題論理の構成規則は以下の形をとる。

• $\varphi$が論理式であるとき、$\mathrm{\neg }\varphi$も論理式である。
• $\varphi$と$\psi$が論理式であるとき、$(\varphi \wedge \psi )$、$(\varphi \to \psi )$、$(\varphi \vee \psi )$、$(\varphi \leftrightarrow \psi )$も論理式である。

述語論理の場合、この他に量化記号に関する次の規則がある。

• $\varphi$が論理式、$\alpha$が変数であるとき、$\mathrm{\forall }\alpha \varphi$、$\mathrm{\exists }\alpha \varphi$も論理式である。

関連項目

• 形式体系
• 形式言語
• 形式文法
• 有限オートマトン