学習目標:
この講義を終えると、学生は以下のことができるようになる。

1. 想起する：リテラルおよび連言正規形・選言正規形の定義を思い出す。
2. 識別する：FNCおよびFNDにおける式の構造を認識する。
3. 活用する：命題論理式の簡略化のためにFNCまたはFNDを用いる。

目次
リテラルの定義
正規形の定義
正規形の定理

命題論理における興味深く有用な結果は、正規形に関連している。これらの内容を詳しく理解するには、まずいくつかの概念を見直す必要がある。

リテラルの定義

リテラルとは、任意の原子的表現、または原子的表現の否定である。この観点から、否定が前置されていない原子的表現を正リテラル、否定が前置されたものを負リテラルと呼ぶ。例えば、A は正リテラルであり、\neg A は負リテラルである。

正規形の定義

式 F が連言正規形（FNC）であるとは、それがリテラルの選言の連言として表現できることを意味する。すなわち：

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

同様に、リテラルの連言の選言として表現される場合、それは選言正規形（FND）である：

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

正規形の定理

命題論理のすべての式は、FNDの式およびFNCの式と同値である。

証明：

これは、式 F の複雑さに関する帰納法によって証明できる。

• 基本の場合：F が原子的表現であるならば、それは同時にFNCおよびFNDの形式で書ける。なぜなら、F\equiv F_D \equiv F_C となり、ここで F_C:=((F\vee F)\wedge (F\vee F)) 、F_D:=((F\wedge F)\vee (F\wedge F)) である。
• 帰納ステップ： G および H が任意の命題論理式であり、それらに対してこの定理の結果が成り立つと仮定する。すなわち、FNC における H_C および G_C、FND における H_D および G_D が存在して：

  G\equiv G_D \equiv G_C

  H\equiv H_D \equiv H_C

  したがって、次のように表現できる：

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  一般性を失うことなく、もし F:= \neg G であるならば、置換定理およびド・モルガンの一般化法則を用いることで、次のようになる：

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  一方で、F:=G\wedge H の場合、置換定理により：

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  これは連言正規形（FNC）である。そして全く同様に、F:=H\vee G であるならば：

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  つまり、選言正規形（FND）である。

  したがって、この帰納法は完結しており、命題論理のすべての式はFNDおよびFNCの形式で表現可能である。

命題論理における連言正規形（FNC）および選言正規形（FND）の研究は、数学や情報科学における複雑な問題の簡略化および解決のための基礎である。任意の論理式がFNDおよびFNCの両方で書けることを主張するこの定理は非常に重要であり、命題をより扱いやすく標準化された形で構造化することを可能にし、その解析と操作を容易にする。この結果の意義は、アルゴリズム設計、論理式の最適化、および人工知能やソフトウェア検証といった様々な分野における問題の効率的な解決に対して、堅実な基盤を提供する点にある。また、この定理を証明するために用いられた帰納法の技法は、論理式の基本的性質に対する理解を強化し、他の数学的文脈においてもその応用可能性を示している。