ユニバーサル限定子のみを使用した非循環グラフを符号化するFOL文

この質問はMath.SEにも掲載されています

$ E(x、y)$のバイナリリレーションがあり、$ E $にいくつかの制約があります。例えば、可能性のある制約の1つは$
E(x、y) Rightarrow T(x、y)$であり、$ T
$は部分的な順序(すなわち、推移的および非対称的)である。この場合、$ E
$の充足可能なインスタンスは非循環式であることがわかります。結果のグラフにサイクルがあるような制約付き$ E
$のインスタンスがある場合にのみ充足可能なFOL文が必要であるとします。これを表現する1つの方法は、パス述語($ P
$)を定義することです。

$$ forall xです。 forall y。 P(x、y) Leftrightarrow E(x、y) vee
が存在する。 E(x、z) wedge P(z、y)\ 存在v。P(v、v) $$

私は$ P $が実際にはパスの述語ではないことを理解しています(
https://math.stackexchange.com/questions/1733901/reachability-and-first-order-logic

)、ただし有限グラフを仮定すると、上記の式はグラフ。 $ E $の制約がサイクルを禁止するのに十分強い場合($ E
$が部分的な順序を意味する例では)、数式は充足できません。

しかし、非循環的であり、かつ式(例えば、無限鎖)に依然として従う無限のグラフが存在する可能性がある。したがって、私は普遍的な量限定子とブール関数のみを使用して数式が必要です。このFOLのサブセットは、EPR(Effectively
propositional
logic)とも呼ばれ、有限のモデルプロパティを持ちます。これは、EPRの式が有限の充足可能モデルを持つ場合にのみ満たされることを意味します。問題はそのような公式が存在するかどうかです。

私が試した1つの潜在的な方法は、直接サイクルグラフを作成することでした。すなわち、サイクルを直接エンコードすることでした:エッジの数=頂点の数で、各頂点は固有の出力エッジと固有の入力エッジを持ちます。後者の2つの制約は汎用量指定子を使用して簡単にエンコードできますが、辺の数と頂点の数が等しいという制約を符号化する方法はありませんでした。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です