Content deleted Content added
→Decidability: three-variable |
→Decidability: add ref |
||
Line 6:
One of the main points is that some important problems about two-variable logic, such as [[satisfiability (logics)|satisfiability]] and [[finite satisfiability (logics)|finite satisfiability]], are [[decidability (computer science)|decidable]]. This result generalizes results about the decidability of fragments of two-variable logic, such as certain [[description logic]]s; however, some fragments of two-variable logic enjoy a much lower [[computational complexity]] for their satisfiability problems.
By contrast, for the three-variable fragment of [[first-order logic]] without function symbols, satisfiability is undecidable.<ref>A. S. Kahr, Edward F. Moore and Hao Wang. ''Entscheidungsproblem Reduced to the ∀ ∃ ∀ Case'', 1962, noting that their ∀ ∃ ∀ formulas use only three variables.</ref>
== Counting quantifiers ==
| |||