2変数ロジック

数理論理学とコンピュータサイエンスにおいて、2変数論理は、 2つの異なる変数のみを使用して式を記述できる1階論理の一部です。^{[1]この部分は通常、}関数記号なしで研究されます。

2変数論理に関するいくつかの重要な問題、例えば充足可能性や有限充足可能性などは決定可能である。^{[2]この結果は、特定の}記述論理など、2変数論理の断片の決定可能性に関する結果を一般化するものである。しかし、2変数論理の断片の中には、充足可能性問題に対する計算複雑度がはるかに低いものもある。

対照的に、関数記号のない一階述語論理の3変数部分では、充足可能性は決定不可能である。^[3]

関数記号を持たない一階述語論理の2変数フラグメントは、計数量指定子[ ^4]、したがって一意性量指定子を追加しても決定可能であることが知られています。高い数値の計数量指定子はその論理では表現できないため、これはより強力な結果です。

数え上げ量指定子は、隣接するノード、つまりが存在することを示すことができるため、有限変数ロジックの表現力を実際に向上させます。数え上げ量指定子がない場合、同じ式に変数が必要になります。 ${\displaystyle n}$${\displaystyle \Phi =\exists x\exists ^{\geq n}yE(x,y)}$${\displaystyle n+1}$

2変数論理とワイスファイラー・レマン（または色彩改良）アルゴリズムの間には強いつながりがあります。2つのグラフが与えられた場合、任意の2つのノードが同じ型を持つ場合、つまり、カウントを伴う2変数論理で同じ式を満たす場合に限り、色彩改良で同じ安定した色を持ちます。 ^[5]${\displaystyle C^{2}}$