Entscheidungsproblem
Aristotelian and relational

Aristotelian logic considers 4 kinds of sentences: "All p are q", "All p are not q", "Some p is q", "Some p is not q". We can formalize these kinds of sentences as a fragment of first-order logic: ∀ x, p (x) → ± q (x), ∃ x, p (x) ∧ ± q (x) {\displaystyle \forall x,p(x)\to \pm q(x),\quad \exists x,p(x)\wedge \pm q(x)} where p, q {\displaystyle p,q} are atomic predicates, and + q:= q, − q:= ¬ q {\displaystyle +q:=q,\;-q:=\neg q}. Given a finite set of Aristotelean logic formulas, it is NLOGSPACE -complete to decide its S a t {\displaystyle {\rm {Sat}}}. It is also NLOGSPACE-complete to decide S a t {\displaystyle {\rm {Sat}}} for a slight extension (Theorem 2.7): ∀ x, ± p (x) → ± q (x), ∃ x, ± p (x) ∧ ± q (x) {\displaystyle \forall x,\pm p(x)\to \pm q(x),\quad \exists x,\pm p(x)\wedge \pm q(x)} Relational logic extends Aristotelean logic by allowing a relational predicate. For example, "Everybody loves somebody" can be written as ∀ x, b o d y (x), ∃ y, b o d y (y) ∧ l o v e (x, y) {\textstyle \forall x,{\rm {{body}(x),\exists y,{\rm {{body}(y)\wedge {\rm {{love}(x,y)}}}}}}}. Generally, we have 8 kinds of sentences: ∀ x, p (x) → (∀ y, q (x) → ± r (x, y)), ∀ x, p (x) → (∃ y, q (x) ∧ ± r (x, y)) ∃ x, p (x) ∧ (∀ y, q (x) → ± r (x, y)), ∃ x, p (x) ∧ (∃ y, q (x) ∧ ± r (x, y)) {\displaystyle {\begin{aligned}\forall x,p(x)\to (\forall y,q(x)\to \pm r(x,y)),&\quad \forall x,p(x)\to (\exists y,q(x)\wedge \pm r(x,y))\\\exists x,p(x)\wedge (\forall y,q(x)\to \pm r(x,y)),&\quad \exists x,p(x)\wedge (\exists y,q(x)\wedge \pm r(x,y))\end{aligned}}} It is NLOGSPACE -complete to decide its S a t {\displaystyle {\rm {Sat}}} (Theorem 2.15). Relational logic can be extended to 32 kinds of sentences by allowing ± p, ± q {\displaystyle \pm p,\pm q}, but this extension is EXPTIME -complete (Theorem 2.24).
keywords:forbidden_words