Can modern SAT-Solvers utilise the symmetry of First Order Logic?

Question

Apologies if the question is trivial or is wrongly stated, I am a Physicist!

Assuming that we have a universally quantified first-order logic sentence, all variables are universally quantified, defined over a finite domain $\mathcal{D}$. Then what are the most efficient ALL-SAT (algorithms that enumerate all models of a formula) algorithms in literature? In my understanding, DPLL and CDCL based algorithms have no way of discerning symmetries which would be inherent to a grounded FOL formula.

Trivial Example:

Let the domain $\mathcal{D} = \{a,b\}$ $$\forall x F(x)$$ Then the grounding of this sentence is, $$F(a)\land F(b)$$ So the brute force idea would be to just check all $2^{\#ground atoms}$ assignments and in this case, only {F(a): True , F(b): True} is the model. But obviously this is a trivial example, if we ground the formula for more complex sentence then, do SAT-solvers solve this as just another propositional case or are there methods to use the "symmetry" from the First Order sentence?

Answer 1

There exist first order (FO) logic systems that allow you to actually write FO constraints, and to reason with them in very intricate ways. E.g., see the IDP system.

For instance, I took a small variation of your example and coded it up in the online IDP editor:

vocabulary V{
    type D
    P(D)
}


theory T: V{
    ?x: P(x).
}


structure S:V{
    D = {a;b}
}

procedure main(){
    //stdoptions.symmetrybreaking="static"
    printmodels(allmodels(T,S))
}

If you press the run button, it will print all the models (==solutions) of the FO specification, which in this case amounts to three models. The system uses a SAT solver under the hood.

Now, if you uncomment the //stdoptions.symmetrybreaking="static" line, its automatic symmetry detection and breaking kicks in. Run again, and only two models will be printed, as the third is removed by symmetry breaking. Here is a reference to how this is done under the hood.

Now, can modern SAT solvers exploit this symmetry, without knowing the high level FO specification?

Not completely. The problem is that it seems hard to extract the interchangeability of first-order domain elements in the propositional logic formula. While the SAT solver typically can find permutations of variables that represent symmetries, it can not detect the particular structure of the symmetry group imposed by interchangeable FO domains. However, a succesful preprocessor for SAT solvers that partially detects FO interchangeability symmetry is described here and is available for download.

Answer 2

I take that by "symmetry" we are talking about reasoning over the generalities in a first-order formula instead of grounding all the possible assignments. I may be misinterpreting the question, but I'll answer anyway.

First off, there is some definitional inconsistency with first-order logic depending on the field. Modern automated theorem provers do not explicitly provide a domain of discourse (see the first-order problems in the TPTP problem library 1 2). They implement algorithms based upon resolution and first-order unification. This method is closely related to SAT solving since DPLL/CDCL a very efficient top-down-style implementation of the iterated resolution method.

Additionally, the variables are seen to range over not only base-level atoms but over the syntactic combinations of functions AND atoms. Below, you can see that we are applying the substitutions $x := S(x)$, $x := S(S(x))$ etc. This structure is known as the Herbrand Universe and is related to propositional grounding in Herbrand's Theorem. The extension of SAT to include universal quantifiers but over only atomic variables is QBF solving - that looks more like what you're getting at with the $2^{\#groundatoms}$ brute force algorithm.

Generally speaking, in this context, it isn't possible to enumerate all models of a first-order formula. Take the simple problem $f(z) \land \Big[\forall x, f(x) \implies f(S(x)) \Big]$. With repeated applications of resolution, one derives the infinite model $f(z) \land f(S(z)) \land f(S(S(z))) \land \dots$.

That said, I think the best answer to your question is to look into resolution with first-order unification. Unification works with the inherent generalities of first-order terms and instantiates them only as much as necessary in the current logical context. However, it does form an entirely new solver; it's not the kind of thing that you can encode as-is into SAT.

Answer 3

The core of DPLL uses essentially QSAT identity $∃xA = A[x/1] \vee A[x/0]$. When implemented with backtracking space requirements are not high.

function DPLL(Φ)
    [...]
    return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});

If you supply the negation $\neg B$ of your problem to a SAT solver, the SAT solver will decide QSAT $∀x_1..∀x_nB$ for you and act as a tautology checker.

But there are extensions of DPLL resp. SAT solver alternatives which can detect $x=B$ constraints and propagate them, without splitting into symmetric sides $A[x/1]$ and $A[x/0]$. The first order equivalent of this elimination technique is the first order identity

$$∃x(x=t \wedge A) = A[x/t]$$

where $x \notin A$. But for more powerful inferencing you need second order respectively QSAT.