リテラル (数理論理学)

リテラルの定義と特徴

数理論理学において、リテラルとは、原子論理式またはその否定を指します。これは、主に古典論理の証明論に関連して登場し、特に連言標準形や導出の方法において重要な役割を果たします。リテラルは大きく2つのタイプに分類され、正リテラルと負リテラルとして知られています。

リテラルの種類

• - 正リテラル：これは単にアトムのことを意味します。例えば、変数「x」は正リテラルの一例です。
• - 負リテラル：このリテラルはアトムの否定を示します。例えば、「¬x」は負リテラルとなります。

これにより、リテラルの「極性」は正リテラルであるか負リテラルであるかによって決定されます。古典論理では二重否定の除去が成り立つため、あるリテラル「l」に対してその否定が「補リテラル」として定義されます。

補リテラルの表現

補リテラルは、リテラル「l」の否定であり、通常「l̅」と表されます。

• - もし「l」が「x」と同じであれば、補リテラルは「¬x」となります。
• - 逆に「l」が「¬x」と同じであれば、補リテラルは「x」となります。

古典論理においてこの二重否定の除去が成り立ちますが、直観主義論理の下では成立しません。連言標準形の文脈においては、リテラルの補元がその論理式の中に現れない場合、そのリテラルは「純粋」とみなされます。

ブール関数におけるリテラル

ブール関数においては、リテラルの概念は変数の個々の出現に関連しています。逆形式か非補形式にかかわらず、変数の各出現はそれぞれリテラルとみなされます。例えば、変数「A」、「B」、「C」を考えた場合、式「¬ABC」は3つのリテラルを含みます。

さらに、「¬AC + ¬B¬C」という式は4つのリテラルを持っています。しかし、式「¬AC + ¬BC」も4つのリテラルを数えることができます。これは、「C」が2回現れることを考慮し、異なる出現としてカウントされるためです。

命題計算と述語計算におけるリテラル

命題計算におけるリテラルは、単に命題変数やその否定を指します。対照的に、述語計算におけるリテラルは原子論理式やその否定を含みます。原子論理式は、述語記号に対していくつかの項に適用されるもので、項は再帰的に定義され、定数記号、変数記号、関数記号から形成されます。

例えば、「¬Q(f(g(x), y, 2), x)」という式は、負リテラルとなります。この式は定数記号「2」、変数記号「x」、「y」、関数記号「f」と「g」、述語記号「Q」から構成されています。これにより、リテラルの概念が秘める数学的な厳密さと全体の体系における意味合いを理解することができます。

まとめ

リテラルは数理論理学における基礎的な要素であり、論理的思考や計算に不可欠な概念です。正リテラルと負リテラルの区別、補リテラルの考え方は、特に論理式の形成や解析において重要です。ブール関数、命題計算、述語計算におけるリテラルの理解を深めることで、数理論理学の応用がより効果的に行えるようになるでしょう。

もう一度検索