Revision as of 14:53, 15 August 2014 edit A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,578 edits remove {{orphan}} ← Previous edit		Revision as of 15:06, 15 August 2014 edit undo A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,578 edits →Decidability: three-variable Next edit →
Line 5: 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. == Counting quantifiers ==

Two-variable logic: Difference between revisions