2
$\begingroup$

Since relational monadic first-order logic has finite model property, its SAT problem is decidable. In H.Behmann's paper, he extended this result to fragment of SOL where all predicates, free and bound are monadic. I am not familiar with SOL and his paper was not written in English. Can you give me any hint to prove this result?

Thanks!

Improve this question
$\endgroup$
1
  • $\begingroup$ Several sources on line describe it briefly, saying it is proved by quantifier elimination. For anyone who wants to look into this, the article is Behmann "Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem" Mathematische Annalen 86 (1922): 163-229. gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN002268752 $\endgroup$
    – Colin McLarty
    Commented Sep 21, 2013 at 13:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .