betaFeedback

WorksComputer Science

Apply All, Prove Once: Embedding Parameterized Lemmas in DRAT

Abstract

The deletion-resolution-asymmetric-tautology (DRAT) proof format is widely used to express unsatisfiability proofs of Boolean formulas. Our DRATL format extends DRAT with parameterized lemmas, allowing a single proof to succinctly capture the common case where multiple instances of a pattern occur in a formula, differing in the identities and phases of the variables. Proofs expressed in DRATL can be hierarchical, with the proof of one lemma containing instantiations of others. Our elaborator program expands a DRATL proof containing multiple, nested lemmas into a standard DRAT proof. Most significantly, the elaboration yields compact proofs, where a single sequencing of the proof steps for each lemma covers all of its instantiations. Several case studies demonstrate that lemmas can provide a powerful method to generate short proofs for challenging problems.

Introduction

Proof generation has had a profound impact on the progress and application of Boolean satisfiability (SAT) solvers over the past 25 years. Early developers discovered bugs in their solvers well after deployment, masked by the minimal output generated when the solver states that a formula is unsatisfiable [16, 31]. By requiring the solver to generate a detailed proof of unsatisfiability, such occurrences were readily detected. Even if the solver contains flaws, the successful generation and checking of a proof demonstrates that the particular formula being evaluated is indeed unsatisfiable.

Proof generation became a requirement for solvers in the main track of the annual SAT competition in 2016. Subsequent competitions have had more consistent judging, and the solvers have become noticeably more reliable. It is now rare for a participant to report an incorrect result, even when evaluating formulas never previously tested.

Over time, increasingly powerful proof frameworks have been devised, enabling solvers to handle more challenging problems [11, 20, 21]. A number of formally verified proof checking tools have been developed, providing strong guarantees that a particular execution of the solver can be fully trusted, even if the solver or some of the tools in the chain from the solver to the checker have flaws [11, 12, 19, 26]. The success of proof generation for SAT solvers has inspired similar efforts in other domains, including pseudo-Boolean reasoning [14], quantified Boolean formula (QBF) solvers [25], satisfiability-modulo-theory (SMT) solvers [3, 4], model counters [9, 13], knowledge compilers [7], and hardware model checking [30].

Despite the advances in solvers and proof frameworks, the generated proofs remain totally flat in their structure. They often contain many repetitions of a single pattern of clauses and reasoning steps, differing only in the identities and phases of the variables. As a consequence, the proofs are often very long, containing hundreds of millions of steps. The sheer size of the proofs causes challenges in their generation, storage, and checking. By contrast, a mathematical proof typically has a hierarchical structure, with nested sets of lemmas capturing core concepts. Each lemma need only be proved once, and then it can be applied many times. The hierarchical structure yields more compact proofs, leading to shorter checking times and more manageable storage requirements.

In this paper, we present a framework for adding parameterized lemmas to the widely used deletion resolution-asymmetric-tautology (DRAT) proof framework. Matching the clausal structure of DRAT, each lemma consists of a set of antecedent clauses, a set of consequent clauses, and a proof that the consequent can be derived from the antecedent by a sequence of (augmented) DRAT proof steps. These three components are expressed in terms of a set of parametric variables that do not occur in the input formula. A lemma can be instantiated multiple times, each with a substitution defining a mapping from the parametric variables to problem variables and their complements. An instantiation can also include a qualifier clause, with the negation of this clause defining the context under which the lemma should hold. Lemmas can be nested, with the proof of one lemma instantiating others. Such a structure can dramatically reduce proof size. We have developed the DRATL proof format to describe lemmas, their proofs, and their instantiations by adding a small set of commands to the standard DRAT file format [18].

Two important features of our work enable our approach to fit within existing proof-checking environments and to reduce the effort required for proof checking. First, a proof containing lemmas can be expanded into a standard DRAT proof. Our proof elaborator converts proofs in the DRATL format to ones in the DRAT format. This enables the proofs to be checked using a well-developed tool chain [29], including ones where the final step uses a formally verified checker. Second, the elaboration maintains the property that each lemma is proved only once, regardless of the number of instantiations. The compactness of the proofs carries over to the efficiency with which they can be checked.

The key idea behind our elaborator is captured in the phrase “Apply All, Prove Once.” The proof for a lemma occurs only after all of its instantiations have been identified. The elaborator introduces extension variables for the parametric variables encoding the substitutions for all of the instantiations. It adds a series of proof steps justifying each clause in the lemma antecedent in terms of the existing clauses via the different substitutions. These can include clauses appearing in the proofs of yet-to-be-proved lemmas in which the current lemma will be instantiated. The elaborator then adds the steps of the lemma proof, enabling the proof to be performed for all instantiations simultaneously. The elaborator follows the proof with steps adding instantiations of the consequent clauses.

In this paper we present our lemma framework and the process by which the elaborator can expand lemmas to cover all instantiations such that each proof is carried out only once. We present arguments for the correctness of our elaborator, although it is important to note that the soundness of the generated proof is guaranteed by the formally verified checker at the end of the verification tool chain.

We provide examples where lemmas lead to much more compact proofs than the flat proofs produced by other approaches. Although some of these problems already have known methods for generating compact proofs, our lemma framework provides a general and powerful mechanism for expressing succinct proofs.

In terms of related work, all existing clausal proof frameworks support lemmas consisting of single clauses and without parameters. That is, when a clause is added to the proof, it can be used in multiple inferences. The dependency structure of the proof forms a directed acyclic graph, rather than a tree. This capability is exploited by CDCL SAT solvers, where learned clauses enable the solver to ignore large regions of the solution space. Our ability to have parameters associated with the lemmas takes this capability to a much higher level, increasing their expressive power.

In most proof systems, parameterized lemmas are expressed in first-order logic using quantified variables to serve as the lemma parameters. The lemma can be proved once and then reused via multiple quantifier instantiations. Our approach follows a similar strategy, but without quantification. By first encoding all instantiations with a single set of extension variables, one sequencing of the proof steps suffices.

Background: The DRAT Proof System

Here we present our notation for Boolean formulas and clausal proofs based on the DRAT proof system.

Boolean Formulas. Boolean variable xx has literals xx and xˉ\bar{x}, the complement of xx. For literal ℓ\ell, its associated variable is denoted var⁡(ℓ)\operatorname{var}(\ell). For literal ℓ\ell with variable x=var⁡(ℓ)x = \operatorname{var}(\ell), we let ℓˉ=xˉ\bar{\ell} = \bar{x} when ℓ=x\ell= x and ℓˉ=x\bar{\ell} = x when ℓ=xˉ\ell= \bar{x}. A clause is a set of literals, representing their disjunction. A clause cannot contain both literals xx and xˉ\bar{x} for any variable xx. A Boolean formula in conjunctive normal form (CNF) is a set of clauses, representing their conjunction. We extend var⁡\operatorname{var} to clauses and formulas by saying that var⁡(C)\operatorname{var}(C) is the set of all variables associated with the literals in CC, and var⁡(F)\operatorname{var}(F) is the union of the sets of all variables associated with the clauses in FF. Moreover, given a set of variables XX, define lit⁡(X)=X∪{xˉ∣x∈X}\operatorname{lit}(X) = X \cup\{\bar{x} \mid x \in X\}. We write lit⁡(F)\operatorname{lit}(F) to mean lit⁡(var⁡(F))\operatorname{lit}(\operatorname{var}(F)). Lastly, given two sets of literals, lit⁡(X)\operatorname{lit}(X) and lit⁡(Y)\operatorname{lit}(Y), a substitution σ:lit⁡(X)→lit⁡(Y)\sigma: \operatorname{lit}(X) \to\operatorname{lit}(Y) is a mapping with the additional condition that σ(x)=¬σ(xˉ)\sigma(x) = \neg\sigma(\bar{x}). Following common convention, we use combinations of set notation and logical connectives in writing clauses and formulas. For example, the formula F∪{{x1},{xˉ2,x3}}F \cup\{\{x_1\}, \{\bar{x}_2, x_3\}\} can also be written as F∧x1∧(xˉ2∨x3)F \land x_1 \land(\bar{x}_2 \lor x_3).

For variables X=var⁡(F)X = \operatorname{var}(F), a truth assignment τ\tau maps every variable in XX to {0,1}\{0, 1\}. It is extended to literals by defining τ(xˉ)=0\tau(\bar{x}) = 0 when τ(x)=1\tau(x) = 1, and τ(xˉ)=1\tau(\bar{x}) = 1 when τ(x)=0\tau(x) = 0. Clause CC is satisfied by τ\tau when some literal ℓ∈C\ell\in C has τ(ℓ)=1\tau(\ell) = 1. Formula FF is satisfied by τ\tau when every clause C∈FC \in F is satisfied by τ\tau. Formula FF is satisfiable when it is satisfied by some assignment τ\tau, and it is unsatisfiable otherwise. The empty clause having no literals is written ⊥\bot. It cannot be satisfied. We also use ⊥\bot to denote any formula containing the empty clause. In a similar fashion, we use ⊤\top to denote a formula with no clauses; it is trivially satisfied. Two formulas FF and GG are equisatisfiable when either both are satisfiable or both are unsatisfiable. Formula FF entails formula GG, written F⊨GF \models G, when every satisfying assignment of FF also satisfies GG.

Clausal Proofs. Clause CC is said to be redundant with respect to FF when the formulas FF and F∪{C}F \cup\{C\} are equisatisfiable. A proof rule is a pair of the form ⟨a,C⟩\langle a, C\rangle, or ⟨d,C⟩\langle d, C\rangle, where CC is a clause, and “a” denotes clause addition, while “d” denotes clause deletion. Addition rule ⟨a,C⟩\langle a, C\rangle is applicable for formula FF when CC is redundant with respect to FF. Its application yields the formula F′=F∪{C}F' = F \cup\{C\}. Deletion rule ⟨d,C⟩\langle d, C\rangle is always applicable. It yields the formula F′=F∖{C}F' = F \setminus\{C\}. Observe that addition rules maintain equisatisfiability, but applying a deletion rule can turn an unsatisfiable formula into a satisfiable one.

For formula FF, a clausal proof consists of a sequence Π\Pi of proof steps R1,R2,…,RsR_1, R_2, \ldots, R_s, defining a sequence of formulas F0,F1,…,FsF_0, F_1, \ldots, F_s, where F0=FF_0 = F and each formula FiF_i is the result of applying rule RiR_i to Fi−1F_{i-1} for 1≤i≤s1 \leq i \leq s. Each addition step must be applicable. That is, for rule Ri=⟨a,Ci⟩R_i = \langle a, C_i\rangle, clause CiC_i must be redundant with respect to Fi−1F_{i-1}. For a clausal proof Π\Pi, var⁡(Π)\operatorname{var}(\Pi) and lit⁡(Π)\operatorname{lit}(\Pi) are defined analogously to their formula counterparts.

Proof rule RiR_i in the sequence is said to be implication preserving when it preserves entailment, i.e., Fi−1⊨FiF_{i-1} \models F_i. This can be guaranteed for a deletion rule by prohibiting the deletion of clauses from the original formula FF. For a proof step adding clause CiC_i, implication preservation can be guaranteed when Fi−1⊨CiF_{i-1} \models C_i.

A clausal proof of unsatisfiability for formula FF is a proof ending with the proof rule Rs=⟨a,⊥⟩R_s = \langle a, \bot\rangle. Any formula FF having a clausal proof of unsatisfiability must be unsatisfiable.

For formula GG, a clausal derivation of GG from formula FF is a sequence Π\Pi of implication-preserving rules R1,R2,…,RsR_1, R_2, \ldots, R_s, such that applying these rules yields a formula FsF_s with G⊆FsG \subseteq F_s. Such a derivation guarantees the entailment F⊨GF \models G.

The formula shown on the left side of Figure 1 will serve as an example in our presentation. A clausal derivation based on that formula is shown on the right. Each clause is numbered, starting with those in the input and continuing with those added by the proof. Each step of the derivation either adds or deletes a clause. The proof adds unit clauses with literals z2z_2, z4z_4, and z‾1\overline{z}_1, which we can write as the conjunction z‾1∧z2∧z4\overline{z}_1 \land z_2 \land z_4.

Boolean Formula and Clausal Derivation Examples

Figure 1. Boolean Formula and Clausal Derivation Examples

The proof also deletes the intermediate clause z2∨z4z_2 \lor z_4. We describe the column labeled “Dependencies” after we have presented the applicable proof rules.

Proof Rules. A unit clause consists of a single literal ℓ\ell. It is only satisfied by an assignment τ\tau having τ(ℓ)=1\tau(\ell)=1. The process of unit propagation iteratively simplifies a formula, where each iteration 1) identifies a unit clause consisting of literal ℓ\ell, 2) removes all clauses containing ℓ\ell, and 3) eliminates literal ℓˉ\bar{\ell} from every clause containing it. This process iterates until a (unique) fixed point is reached. We write F⊨1GF \models_1 G when applying unit propagation to formula FF yields formula GG. We can see that unit propagation preserves implication. That is, any assignment τ\tau satisfying FF will also satisfy GG when F⊨1GF \models_1 G. Conversely, any formula FF for which F⊨1⊥F \models_1 \bot must be unsatisfiable.

Clause C=ℓ1∨ℓ2∨⋯∨ℓkC=\ell_1\lor\ell_2\lor\cdots\lor\ell_k satisfies the Reverse Unit Propagation (RUP) proof rule [28] with respect to formula FF, when the following process succeeds:

  1. Formula FF is augmented by unit clauses consisting of the negated literals of CC:

F′=F∧ℓˉ1∧ℓˉ2∧⋯∧ℓˉkF' = F \land\bar{\ell}_1 \land\bar{\ell}_2 \land\cdots\land\bar{\ell}_k
  1. Unit propagation yields the empty clause: F′⊨1⊥F' \models_1 \bot.

Applying proof rule ⟨a,C⟩\langle a,C\rangle to FF when CC satisfies the RUP proof rule with respect to FF preserves implication: any assignment τ\tau satisfying FF will also satisfy CC.

Returning to the example of Figure 1, we can now explain the field labeled “Dependencies.” For each clause addition, it shows the IDs of the clauses that reduce to unit clauses when performing unit propagation to validate a RUP clause addition, with the final clause yielding ⊥\bot. For the deletion step, the dependency gives the ID of the deleted clause. We can see that the proof is implication preserving, since all additions used the RUP proof rule, and the only deletion was for a proof clause.

Clause CC satisfies the Resolution Asymmetric Tautology (RAT) proof rule [22] with respect to formula FF for pivot literal ℓ\ell, where ℓ∈C\ell\in C, when for every clause D∈FD \in F such that ℓˉ∈D\bar{\ell} \in D, the following process succeeds:

  1. Form the set of literals R=C∪(D∖ℓˉ)R=C\cup(D\setminus\bar{\ell}).

  2. Either: (a) RR contains literals xx and xˉ\bar{x} for some variable xx, or (b) RR satisfies the RUP rule with respect to FF.

Clause CC satisfies the RAT rule with respect to FF when it does so for some pivot ℓ∈C\ell\in C. Applying proof rule ⟨a,C⟩\langle a,C\rangle when CC satisfies the RAT proof rule with respect to FF maintains equisatisfiability, but it may eliminate assignments that satisfy FF. That is, there may be an assignment τ\tau that satisfies FF, but it fails to satisfy CC.

The RUP proof rule satisfies a monotonicity property such that if clause CC satisfies the RUP rule with respect to formula FF, then it also does so for any formula F′F' such that F′⊇FF'\supseteq F. Such is not the case for the RAT rule, since it can depend on the absence of a clause. As a consequence, the deletion rule is an important capability for DRAT proofs. By deleting some clauses that are no longer needed, it may be possible to perform RAT additions that would otherwise be prohibited.

A clause CC satisfying the RUP rule with respect to FF will also satisfy the RAT rule, with any literal ℓ∈C\ell\in C serving as the pivot. Given its power, it can be helpful to highlight two special cases where clause CC satisfies the RAT rule with respect to formula FF for pivot ℓ\ell: RUP: Clause CC satisfies the RUP rule with respect to FF

Blocked Clause: Every clause DD such that ℓˉ∈D\bar{\ell} \in D also contains a literal m≠ℓˉm \ne\bar{\ell}, such that mˉ∈C\bar{m} \in C.

The RAT rule enables a proof to add variables not found in the original formula FF. These are known as extension variables, and they provide the DRAT proof system with the capabilities of the powerful extended-resolution proof system [27]. Suppose formula FF has X=var⁡(F)X = \operatorname{var}(F) and step RiR_i in clausal proof Π\Pi yields formula FiF_i having var⁡(Fi)=X∪Z\operatorname{var}(F_i) = X \cup Z. That is, ZZ is the set of extension variables in the proof clauses that have been added and not yet deleted. We say that assignment τ:X→{0,1}\tau: X \to\{0,1\} satisfies FiF_i if there is an assignment τ∗:X∪Z→{0,1}\tau^* : X \cup Z \to\{0,1\} that satisfies FiF_i, such that τ∗(x)=τ(x)\tau^*(x) = \tau(x) for all x∈Xx \in X. With this definition, it can be shown that any application of the RAT proof rule having a literal of an extension variable as its pivot preserves implication.

To summarize, a clausal derivation can contain any of the following proof steps:

  1. A deletion step that does not delete a clause in the original formula FF.

  2. An addition step based on the RUP proof rule.

  3. An addition step based on the RAT proof rule, having the literal of an extension variable as the pivot.

Embedding Lemmas in DRAT

A lemma consists of a set of antecedent clauses A\mathcal{A}, a set of consequent clauses CC, and a clausal derivation Π\Pi of CC from A\mathcal{A}. These components are defined over a set of variables ZZ disjoint from those in the top-level formula FF. These variables are partitioned into variables ZprobZ_{\mathrm{prob}} that map, via substitutions, back to literals in FF and variables ZauxZ_{\mathrm{aux}} internal to the lemma proof. The auxiliary variables enable the lemma proof to employ extended resolution.

The instantiation of a lemma is based on a substitution σ:lit⁡(Zprob)→lit⁡(F)\sigma: \operatorname{lit}(Z_{\mathrm{prob}}) \to\operatorname{lit}(F) and a set of qualifying literals Q⊆lit⁡(F)Q \subseteq\operatorname{lit}(F), such that ¬Q\neg Q limits the context under which the lemma must hold. Our procedure derives the consequent, mapped back to literals in FF, for multiple instantiations and multiple sets of qualifying literals without needing to apply Π\Pi multiple times.

The Embedding Procedure

Based on the notation we have introduced, we assume that the sets of variables ZZ, ZprobZ_{\mathrm{prob}}, and ZauxZ_{\mathrm{aux}} obey the following:

Z=var⁡(A)∪var⁡(C)∪var⁡(Π)Z∩var⁡(F)=∅Z = \operatorname{var}(\mathcal{A}) \cup\operatorname{var}(C) \cup\operatorname{var}(\Pi) \qquad Z \cap\operatorname{var}(F) = \varnothing
Z=Zprob∪Zauxvar⁡(A),var⁡(C)⊆ZprobZ = Z_{\mathrm{prob}} \cup Z_{\mathrm{aux}} \qquad \operatorname{var}(\mathcal{A}), \operatorname{var}(C) \subseteq Z_{\mathrm{prob}}

Since Π\Pi is a clausal derivation, we require that any of its addition steps based on the RAT proof rule have pivot literal ℓ\ell such that ℓ∈lit⁡(Zaux)\ell\in\operatorname{lit}(Z_{\mathrm{aux}}). Let the consequent CC consist of the clauses C={C1,C2,…,Cm}C = \{C_1, C_2, \ldots, C_m\}. In the following, we add a number of “fresh” variables, each being a previously unused extension variable.

Given K≥2K \ge2 applications of the lemma, let σk:lit⁡(Zprob)→lit⁡(F)\sigma_k : \operatorname{lit}(Z_{\mathrm{prob}}) \to\operatorname{lit}(F) be the desired substitution and QkQ_k be the set of qualifying literals for the kkth instantiation. All of the clauses in σk(A)\sigma_k(\mathcal{A}) must be RUP with respect to F∧¬QkF \land\neg Q_k. For the construction, introduce fresh variable tt and fresh variables s1,…,s(K−1)ms_1,\ldots,s_{(K-1)m}. For convenience define s0=⊤s_0 = \top and sKm=⊥s_{Km} = \bot. The clause CC guarded by tt is defined to be the clause t‾∨C\overline{t} \lor C. It behaves exactly like CC when tt is set to 11, and it is satisfied otherwise. Finally, let Dk,j=Qk∨σk(Cj)D_{k,j} = Q_k \lor\sigma_k(C_j) be the translation of consequent clause jj for instantiation kk. The procedure is presented in Figure 3 using the notation [n][n] to represent the set {1,…,n}\{1,\ldots,n\}. We now prove the correctness of the embedding.

Theorem 1 (Embedding Correctness). Suppose that FF, A\mathcal{A}, CC, Π\Pi, σk\sigma_k, and QkQ_k satisfy the conditions above for all kk in [K][K] and that all variables introduced are fresh. Then the procedure in Figure 3 is a valid DRAT derivation of F∪{Dk,j∣k∈[K],j∈[m]}F \cup\{D_{k,j} \mid k \in[K], j \in[m]\}.

Proof. To prove the theorem, we show that the additions and deletions of every step are valid and result in the desired formula at the end.

Prefixes The first step adds definitional clauses encoding sr↔(sr−1∧Dk,j)s_r \leftrightarrow(s_{r-1} \land D_{k,j}). Added in order of increasing rr, these additions are valid via blocked clause addition.

Bindings This step adds two clauses for each problem variable and application. Fix an instantiation kk and a variable z∈Zprobz \in Z_{\mathrm{prob}}. The clause z‾∨s‾(k−1)m∨skm∨σk(z)\overline{z} \lor\overline{s}_{(k-1)m} \lor s_{km} \lor\sigma_k(z) is RAT on z‾\overline{z}. If k=1k = 1, then it is added by blocked clause addition. If k>1k > 1, every clause in the formula which contains the complement, zz, contains sk′ms_{k'm} for some k′<kk' < k. Thus, the resulting set of literals in the RAT check will have both sk′ms_{k'm} and s‾(k−1)m\overline{s}_{(k-1)m}. When negated, these units propagate down the chain and result in a conflict, satisfying the RAT condition. For the opposing clause, z∨s‾(k−1)m∨skm∨σk(z‾)z \lor\overline{s}_{(k-1)m} \lor s_{km} \lor\sigma_k(\overline{z}), the argument is the same except that the previously added clause contains z‾\overline{z} and therefore gives RAT one additional check. The check succeeds because the resulting set of literals contains both σk(z)\sigma_k(z) and σk(z‾)\sigma_k(\overline{z}).

Antecedent The clauses t‾∨A\overline{t} \lor A for all A∈AA \in\mathcal{A} are added via blocked clause addition. The clauses of the second set are all RAT on tt. For every k∈[K]k \in[K], the only clauses that are relevant to the RAT check for t∨s‾(k−1)m∨skm∨Qkt \lor\overline{s}_{(k-1)m} \lor s_{km} \lor Q_k are the guarded antecedent clauses. For each antecedent clause AA, the RAT condition requires that t∨sˉ(k−1)m∨skm∨Qk∨At \lor\bar{s}_{(k-1)m} \lor s_{km} \lor Q_k \lor A is RUP. Negating this clause results in the two units sˉ(k−1)m\bar{s}_{(k-1)m} and sˉkm\bar{s}_{km} establishing the bindings z↔σk(z)z \leftrightarrow\sigma_k(z) for z∈Zprobz \in Z_{\mathrm{prob}}. The bindings, along with the units ¬A\neg A, establish the units ¬σk(A)\neg\sigma_k(A). Along with the units ¬Qk\neg Q_k, this results in a conflict as σk(A)∨Qk\sigma_k(A) \lor Q_k is RUP from FF by assumption.

StepClauses or operationRule
1. PrefixesFor r=1,…,(K−1)mr = 1,\ldots,(K-1)m and k,jk,j such that r=(k−1)m+jr=(k-1)m+j: (sˉr∨sˉr−1)\left(\bar{s}_r \lor\bar{s}_{r-1}\right), (sˉr∨Dk,j)\left(\bar{s}_r \lor D_{k,j}\right)Blocked on sˉr\bar{s}_r
(sr∨sˉr−1∨ℓˉ)\left(s_r \lor\bar{s}_{r-1} \lor\bar{\ell}\right), for each ℓˉ∈Dk,j\bar{\ell} \in D_{k,j}Blocked on srs_r
2. BindingsFor k∈[K]k \in[K], increasing, and z∈Zprobz \in Z_{\mathrm{prob}}: zˉ∨sˉ(k−1)m∨skm∨σk(z)\bar{z} \lor\bar{s}_{(k-1)m} \lor s_{km} \lor\sigma_k(z)RAT on zˉ\bar{z}
z∨sˉ(k−1)m∨skm∨σk(zˉ)z \lor\bar{s}_{(k-1)m} \lor s_{km} \lor\sigma_k(\bar{z})RAT on zz
3. AntecedentWith fresh tt: t∨At \lor A for all A∈AA \in\mathcal{A}Blocked on tt
t∨sˉ(k−1)m∨skm∨Qkt \lor\bar{s}_{(k-1)m} \lor s_{km} \lor Q_k for all k∈[K]k \in[K]RAT on tt
4. ProveFor each step ⟨R,P⟩∈Π\langle R,P\rangle\in\Pi: tˉ∨P\bar{t} \lor P if R=aR=aRAT/RUP as in Π\Pi
Delete tˉ∨P\bar{t} \lor P if R=dR=dDeletion
5. Prefix UnitsFor r=1,…,(K−1)mr=1,\ldots,(K-1)m: srs_rRUP
6. ConsequentFor every k∈[K]k \in[K] and j∈[m]j \in[m]: Dk,jD_{k,j}RUP
7. CleanupDelete the added clauses other than the consequent Dk,jD_{k,j} preserving every clause of FF.Deletion

Table 3. The seven-step procedure to embed a lemma into DRAT. Tautologies are omitted.

Prove For each step of Π\Pi, if it is an addition ⟨a,P⟩∈Π\langle a,P\rangle\in\Pi, then tˉ∨P\bar{t} \lor P is redundant via the same mechanism as in Π\Pi. There are two cases: PP is either RAT on an auxiliary variable or RUP. If it is RAT on an auxiliary variable, since that variable only occurs in Π\Pi, it is still RAT on that auxiliary variable. If it is RUP, on the other hand, then the addition of tˉ∨P\bar{t} \lor P is RUP. The unit tt activates the antecedent clauses A\mathcal{A} and the earlier guarded steps of Π\Pi, so PP is RUP exactly as it is in Π\Pi. If it is a deletion ⟨d,P⟩\langle d,P\rangle, then the clause tˉ∨P\bar{t} \lor P is deleted.

Prefix Units Inductively, assume that all units s1s_1 through si−1s_{i-1} have been derived. Choose kk such that (k−1)m<i≤km(k-1)m < i \le km. Negating the unit sis_i propagates up the prefix chain established in step 1, yielding the unit skms_{km}. Since (k−1)m<i(k-1)m < i, s(k−1)ms_{(k-1)m} is already derived, and therefore the bindings from step 2 activate, yielding z↔σk(z)z \leftrightarrow\sigma_k(z) for z∈Zprobz \in Z_{\mathrm{prob}}. Moreover, since si−1s_{i-1} is already derived, by the prefix clauses in step 1, negating sis_i also derives ¬Dk,j\neg D_{k,j} for some j≤mj \le m with i=(k−1)m+ji=(k-1)m+j. Since Qk⊆Dk,jQ_k \subseteq D_{k,j}, the negation of Dk,jD_{k,j} provides the units in ¬Qk\neg Q_k, which, along with s‾km\overline{s}_{km} and s(k−1)ms_{(k-1)m} propagate tt. Finally, recognizing that σk(Cj)⊆Dk,j\sigma_k(C_j) \subseteq D_{k,j} and that the bindings z↔σk(z)z \leftrightarrow\sigma_k(z) are active, the units tt and ¬Cj\neg C_j conflict with the jjth consequent of step 4, t∨Cjt \lor C_j.

Consequent After establishing all of the prefix units, the consequent clauses Dk,jD_{k,j} for k<Kk < K and all jj follow immediately from the prefix clauses in the first step. Similarly, all of the DK,jD_{K,j} are valid since negating each clause yields both ¬σK(Cj)\neg\sigma_K(C_j) and ¬QK\neg Q_K. The latter, along with the prefix units, propagates tt, which activates the guarded consequent clauses of step 4. In particular, ¬σK(Cj)\neg\sigma_K(C_j) and the active bindings σK\sigma_K conflict with the now active consequent CjC_j.

Cleanup Clause deletions are unconditional in DRAT, so we can freely delete all of the scaffolding, yielding a DRAT derivation of F∪{Dk,j∣k∈[K],j∈[m]}F \cup\{D_{k,j} \mid k \in[K], j \in[m]\} as desired.

Embedding Example

As an example of the embedding, consider the formula consisting of the conjunction of the four blocks in Figure 2. These are three copies of the formula in Figure 1, replacing ziz_i with aia_i, bib_i, and cic_i, and with blocks bb and cc under the qualifiers a‾2\overline{a}_2 and b1b_1 respectively. It is augmented with a conflicting clause a1∨b‾2∨c‾4a_1 \lor\overline{b}_2 \lor\overline{c}_4 which makes the formula unsatisfiable. Our lemma will be the derivation of units z‾1\overline{z}_1, z2z_2, and z4z_4 as in Figure 1. Once proven, we can then apply this lemma to the variables in each block, with the applications to blocks bb and cc under qualification, to derive units a‾1\overline{a}_1, b2b_2, and c4c_4, obtaining a contradiction.

Figure 2. An unsatisfiable formula. Each block, conditioned on the units from the previous, derives the three unit literals corresponding to z‾1\overline{z}_1, z2z_2, and z4z_4 which falsify the final clause.

Prefixes The first step in the embedding procedure adds prefix clauses. Since there are K=3K = 3 applications, we need K−1=2K - 1 = 2 sets of prefix variables, each for deriving m=3m = 3 consequent clauses. To do this, the procedure adds clauses:

a’s prefix chainb’s prefix chains1↔a‾1s4↔s3∧(b‾1∨a‾2)s2↔s1∧a2s5↔s4∧(b‾2∨a‾2)s3↔s2∧a4s6↔s5∧(b‾4∨a‾2)\begin{array}{c|c} a\text{'s prefix chain} & b\text{'s prefix chain} \\ s_1 \leftrightarrow\overline{a}_1 & s_4 \leftrightarrow s_3 \land(\overline{b}_1 \lor\overline{a}_2) \\ s_2 \leftrightarrow s_1 \land a_2 & s_5 \leftrightarrow s_4 \land(\overline{b}_2 \lor\overline{a}_2) \\ s_3 \leftrightarrow s_2 \land a_4 & s_6 \leftrightarrow s_5 \land(\overline{b}_4 \lor\overline{a}_2) \end{array}

Variable srs_r is equivalent to the conjunction of the first rr instantiated consequent clauses. This gives the procedure access to “selectors” for application kk of the form s‾km∧s(k−1)m\overline{s}_{km} \land s_{(k-1)m} which intuitively mean “we know the consequents of instantiations through k−1k - 1 are valid, but we don’t know about instantiation kk.”

Bindings The key insight of this construction is the introduction of bindings conditional on selectors. Throughout the proof, we want to maintain the invariant that lemma variables ZprobZ_{\mathrm{prob}} are bound to the earliest application that has not been checked. To do this, step 2 binds the parameters conditionally on the selectors. Antecedent Next, the procedure adds the lemma’s antecedent clauses. Since the previous step introduced the bindings, the antecedent clauses are neither RUP nor RAT, in general. Thus, step 3 adds guarded versions that can be activated later.

aa’s bindings
sˉ3→z1↔a1\bar{s}_3 \to z_1 \leftrightarrow a_1
sˉ3→z2↔a2\bar{s}_3 \to z_2 \leftrightarrow a_2
sˉ3→z3↔a3\bar{s}_3 \to z_3 \leftrightarrow a_3
sˉ3→z4↔a4\bar{s}_3 \to z_4 \leftrightarrow a_4

Table 10a.

bb’s bindings
sˉ6∧s3→z1↔b1\bar{s}_6 \land s_3 \to z_1 \leftrightarrow b_1
sˉ6∧s3→z2↔b2\bar{s}_6 \land s_3 \to z_2 \leftrightarrow b_2
sˉ6∧s3→z3↔b3\bar{s}_6 \land s_3 \to z_3 \leftrightarrow b_3
sˉ6∧s3→z4↔b4\bar{s}_6 \land s_3 \to z_4 \leftrightarrow b_4

Table 10b.

cc’s bindings
s6→z1↔c1s_6 \to z_1 \leftrightarrow c_1
s6→z2↔c2s_6 \to z_2 \leftrightarrow c_2
s6→z3↔c3s_6 \to z_3 \leftrightarrow c_3
s6→z4↔c4s_6 \to z_4 \leftrightarrow c_4

Table 10c.

Guarded Antecedent
t→z1∨z2∨zˉ3t \to z_1 \lor z_2 \lor\bar{z}_3
t→zˉ1∨zˉ2∨z3t \to\bar{z}_1 \lor\bar{z}_2 \lor z_3
t→z2∨z3∨zˉ4t \to z_2 \lor z_3 \lor\bar{z}_4
t→zˉ2∨zˉ3∨z4t \to\bar{z}_2 \lor\bar{z}_3 \lor z_4
t→z1∨z3∨z4t \to z_1 \lor z_3 \lor z_4
t→zˉ1∨zˉ3∨zˉ4t \to\bar{z}_1 \lor\bar{z}_3 \lor\bar{z}_4
t→zˉ1∨z2∨z4t \to\bar{z}_1 \lor z_2 \lor z_4

Table 10d.

Activators
sˉ3→t\bar{s}_3 \to t
a2∧sˉ3∧sˉ6→ta_2 \land\bar{s}_3 \land\bar{s}_6 \to t
bˉ1∧s6→t\bar{b}_1 \land s_6 \to t

Table 10e.

Prove Once Step 4 proves the lemma on the ZZ variables. It simply replays the proof, guarded by tt as follows:

Proof Replay
t→z2∨z4t \to z_2 \lor z_4
t→z2t \to z_2
delete t→z2∨z4t \to z_2 \lor z_4
t→z4t \to z_4
t→zˉ1t \to\bar{z}_1

Table 10f.

Prefix Units At this point, the prefix units follow in order, s1,…,s6s_1, \ldots, s_6.

Consequent All that is left to do is derive the consequent clauses by reading them off:

aa’s consequentbb’s consequentcc’s consequent
aˉ1\bar{a}_1bˉ1∨aˉ2\bar{b}_1 \lor\bar{a}_2cˉ1∨b1\bar{c}_1 \lor b_1
a2a_2b2∨aˉ2b_2 \lor\bar{a}_2c2∨b1c_2 \lor b_1
a4a_4b4∨aˉ2b_4 \lor\bar{a}_2c4∨b1c_4 \lor b_1

Table 10g.

With the consequents derived, the empty clause is RUP, showing that the formula is unsatisfiable.

proof ::= step*
step ::= clause                         add a clause (DRAT)
       | d clause                       delete a clause (DRAT)
       | lemma                           declare and prove a lemma
       | apply                           apply a lemma
lemma ::= L id n x a m                  n parameters, x auxiliary variables
          clause^a                       a antecedent clauses, over variables 1, ..., n
          clause^m                       m consequent clauses, over variables 1, ..., n
          step*                          proof of the lemma, over variables 1, ..., n + x
          e id
apply ::= l id lit^n 0 [ lit* 0 ]       arguments, optional qualifier
clause ::= lit* 0

The DRATL Format for Lemma-Based Proofs

DRATL extends DRAT to enable proofs structured as hierarchies of lemmas. DRATL adds two extensions to the DRAT format: lemma definitions and lemma instantiations. The full grammar can be seen in Figure 4. An example DRATL proof, replicating the one from § 3, is shown in Figure 5. The new components are as follows:

Grammar for the DRATL format

Figure 4. Grammar for the DRATL format

Lemma Definition A lemma is defined by first giving a header with a user-specified, unique numeric ID, as well as the number of parameters, auxiliary variables, antecedent clauses, and consequent clauses. Then the antecedent and consequent clauses are listed, followed by the proof of the consequent from the antecedent.

Lemma Application An application consists of a lemma ID and one literal per parameter, where the literal in position ii specifies the value of σ(zi)\sigma(z_i). The instantiation concludes with an optional list of literals forming the qualifying literals QQ.

Elaboration

Our elaborator translates a DRATL proof into a DRAT proof following a variation of the procedure in Figure 3. All of the additional complexity arises from nested lemmas, where a lemma ii is instantiated as part of the proof of another lemma jj. In this section, we define what it means for a DRATL proof to be semantically valid, describe how we elaborate such files, and prove that the elaboration results in a valid DRAT proof.

A scope is defined to be either the top-level proof or the proof of a lemma. A scope’s formula is the set of clauses relative to which the proof is checked. At the top level, it is the original formula FF and within a lemma it is the antecedent. A scope’s proof and consequent are defined similarly. A scope’s proof can be divided into two parts: the preamble, consisting of all steps before any lemma is applied, and the body, consisting of the remainder of the proof steps. For a DRATL proof to be valid, we require the following:

  1. For each lemma application, the conditions described in Figure 3 are met with respect to its enclosing scope’s formula and preamble.

ActionClauseComment
L1 4 0 7 34 parameters, 0 auxiliaries, 7 antecedents, 3 consequents
z1∨z2∨z3‾z_1 \lor z_2 \lor\overline{z_3}antecedent
z1‾∨z2∨z3\overline{z_1} \lor z_2 \lor z_3
z2∨z3∨z4‾z_2 \lor z_3 \lor\overline{z_4}
z2‾∨z3∨z4\overline{z_2} \lor z_3 \lor z_4
z1∨z3‾∨z4z_1 \lor\overline{z_3} \lor z_4
z1‾∨z3‾∨z4‾\overline{z_1} \lor\overline{z_3} \lor\overline{z_4}
z1‾∨z2∨z4\overline{z_1} \lor z_2 \lor z_4
z1‾\overline{z_1}consequent
z2z_2
z4z_4
az2∨z4z_2 \lor z_4proof of the consequent
az2z_2
dz2∨z4z_2 \lor z_4
az4z_4
az1‾\overline{z_1}
e1end of lemma 1
l1:a1,a2,a3,a41 : a_1, a_2, a_3, a_4consequent a1‾,a2,a4\overline{a_1}, a_2, a_4
l1:b1,b2,b3,b4 [a2‾]1 : b_1, b_2, b_3, b_4 \ [\overline{a_2}]consequent b1‾∨a2‾,b2∨a2‾,b4∨a2‾\overline{b_1} \lor\overline{a_2}, b_2 \lor\overline{a_2}, b_4 \lor\overline{a_2}
l1:c1,c2,c3,c4 [b1]1 : c_1, c_2, c_3, c_4 \ [b_1]consequent c1‾∨b1,c2∨b1,c4∨b1\overline{c_1} \lor b_1, c_2 \lor b_1, c_4 \lor b_1
a⊥\botRUP from the consequents and the conflicting clause

Table 5. The DRATL proof of the formula in Figure 2 with the lemma of Figure 1. A qualifier is shown in brackets after the arguments. The presentation is stylized, using literal symbols instead of numbers.

  1. If lemma ii is used in the proof of lemma jj, lemma jj is not used, directly or indirectly, in the proof of lemma ii.

  1. In all scopes, the RAT steps in the proof’s body must be valid with respect to all instantiated consequents of all lemma applications in the scope.

  1. Deletion steps are not allowed to delete instantiated consequent clauses.

  1. Every scope’s proof is a valid derivation of its consequent from its formula when lemma applications, given by instantiation σ\sigma and qualifier QQ, are interpreted as the instantiated consequent σ(C)∨Q\sigma(C) \lor Q for C∈CC \in\mathcal{C}.

Item 3 is required because DRAT is non-monotonic. While it appears restrictive, it did not hinder our ability to write compact DRATL proofs. Specifically, we found that only using RAT steps in a proof’s preamble was sufficiently expressive. Item 4 is required because lifting all consequent clauses to the top exposes them to premature deletion.

Given a valid DRATL proof, the elaboration algorithm follows a simple procedure. First, the elaborator emits the top level’s preamble. When the first lemma application is encountered, we topologically sort the lemmas by application. That is, if lemma ii is used in the proof of lemma jj, then ii comes before jj in this ordering. Then, it applies the steps of Figure 3 in two phases. The elaborator’s setup phase applies steps 1 through the preambles of step 4 on each lemma in reverse topological order. Then the conclusion phase applies the bodies of the proofs in step 4, as well as steps 5 through 7, on each lemma in topological order. Moreover, when a lemma ii is used in the proof of lemma jj, it is implicitly qualified by t‾j\overline{t}_j, the negated guard literal for lemma jj. Finally, the body of the top level’s proof is replayed.

This construction uses two phases to satisfy opposing dependency orders; a single one does not suffice. If lemma ii is used in the proof of lemma jj, then an instantiation of lemma ii, namely the one which is used in lemma jj, has antecedent clauses that are RUP from the antecedent and preamble of lemma jj. This would seem to require that lemma jj be elaborated before lemma ii. On the other hand, the consequent for lemma jj depends on the instantiated consequent from lemma ii. This would seem to require that lemma ii be elaborated before lemma jj. The two-phase approach resolves this tension. We now prove the correctness of this approach.

Theorem 2 (Elaboration Correctness). The elaboration of a valid DRATL proof results in a valid DRAT proof.

Proof. To show that the nested elaboration algorithm results in a valid DRAT proof, we argue that each of the justifications from Figure 3 still applies.

Fix a lemma ii which may be applied within lemma jj. Since the prefix, problem, auxiliary, and tt variables are disjoint for each lemma, steps 1 and 2 work as they did in Theorem 1. The only complexity in step 3 is due to the RAT check on tt possibly depending on the antecedent and preamble for lemma jj. By the reverse topological ordering of the setup phase, the antecedent and preamble for lemma jj have already been emitted, but their clauses are guarded by t‾j\overline{t}_j. However, during elaboration, the application of lemma ii inside lemma jj is implicitly qualified by t‾j\overline{t}_j, allowing the argument to follow exactly as in Theorem 1. The last step of the setup phase, the preamble, has no lemma instantiations, and is the same as before.

In the conclusion phase of lemma ii, the only clauses remaining that mention the variables of ii are from its own elaboration and the instantiated consequents of the lemmas applied in its proof. This is because the topological ordering of the conclusion phase guarantees that all lemmas used in the proof of lemma ii have already been elaborated and undergone cleanup, leaving only their instantiated consequents. Due to the restriction on deleting instantiated consequents, every clause available at a given step of the DRATL proof for lemma ii is also available, in guarded form, at the corresponding step of the elaborated proof. In this manner, RUP steps remain valid by monotonicity, while RAT steps remain valid by Item 3, allowing the body to be replayed. Steps 5 through 7 involve only the clauses of lemma ii and are therefore unchanged.

After all lemmas have been elaborated, at the top level, the remaining proof body is valid with respect to all of the instantiated consequents and is otherwise a valid DRAT proof. Therefore, the resulting elaborated DRAT proof is valid.

Experimental Results

Three case studies probe the approach from different sides. Using lemmas for the mutilated chessboard enables an effective strategy based on extended resolution to scale even further by reducing the overhead of adding formulas implementing modular arithmetic. On the queen graphs, a single lemma enables reducing many copies of a subformula describing a clique. Lemmas for the Mycielski graph follow its inductive structure, enabling a factorial reduction in size.

Mutilated Chessboard

The mutilated chessboard problem has long served as a challenge for automated reasoning tools [23]. The problem considers an n×nn \times n chessboard, with the corners on the upper left and the lower right removed. It attempts to tile the board with dominoes, with each domino covering two squares. For even values of nn, both removed squares are white. Since each domino covers one white and one black square, no tiling is possible.

Labeling the squares of a chessboard as having rows 1 (upper) to nn (lower) and columns 1 (left) to nn (right), the standard Boolean encoding of the problem introduces two sets of variables describing the placement of horizontal and vertical dominoes, respectively. Variable hr,ch_{r,c} for 1≤r≤n1 \le r \le n and 1≤c<n1 \le c < n encodes whether a domino is placed horizontally on row rr spanning columns cc and c+1c + 1. Variable vr,cv_{r,c} for 1≤r<n1 \le r < n and 1≤c≤n1 \le c \le n encodes whether a domino is placed vertically on column cc spanning rows rr and r+1r + 1. The upper-left and lower-right corners are omitted via unit clauses h1,1h_{1,1}, vˉ1,1\bar{v}_{1,1}, hˉn,n−1\bar{h}_{n,n-1}, and vˉn−1,n\bar{v}_{n-1,n}. For every other square, there are 2–4 variables describing possible placements of dominoes on that square. For each square, 2–7 clauses constrain exactly one of these to be set to 1. It can be shown that any resolution proof of unsatisfiability for this encoding must be of exponential size [1]. The plot labeled kissat in Figure 6 demonstrates how difficult this problem is for CDCL solvers, showing the number of proof clauses as a function of nn. Even for n=20n = 20, kissat generates a proof with over 65 million clauses.

Total number of clauses in formula and proofs of mutilated chessboard problems

Figure 6. Total number of clauses in formula and proofs of n×nn \times n mutilated chessboard problems. Historical methods were limited to n≤128n \le128. Direct generation with mod-3 propagation scales beyond n=1000n = 1000. Using lemmas (strips or tiled) greatly decreases the proof size for large values of nn, even becoming more compact than the formulas themselves.

Others have found ways to overcome exponential performance on this problem, such as by applying symmetry reduction via the propagation-redundancy (PR) proof system [20]. The PR proofs can then be translated into DRAT, with polynomial but significant overhead. The plots in Figure 6 labeled “PR proof” and “PR converted to DRAT” show their published results, reaching n=50n = 50. Although it can be seen that the PR proofs, and their translation to DRAT, greatly improve on kissat, other approaches generally outperform the DRAT versions, and the results reported here even improve on the PR proof sizes.

More recent work using proof-generating binary decision diagram (BDD) packages demonstrated success for up to n=128n = 128 using two different approaches. One used a strategy inspired by symbolic model checking to scan from the left side of the board to the right, tracking the possible sets of assignments to the variables hr,ch_{r,c} for 1≤r≤n1 \le r \le n as cc ranges from 1 to n−1n - 1 [6]. Their published results are shown in the plot “BDD, Column scan.” The second converted the problem into one involving pseudo-Boolean constraints, encoding the mismatch between the total number of white and black squares. They observed that the arithmetic could be computed modulo-3 and still capture the mismatch [5]. Their results are shown in the plot “BDD, Mod-3 equations.”

Rather than using BDDs as an intermediate step, we can combine the ideas of column scanning and mod-3 arithmetic directly into an extended resolution proof. That is, we set up formulas encoding mod-3 counters summing wr,c⋅hr,cw_{r,c} \cdot h_{r,c} for 1≤r≤n1 \le r \le n, where wr,c=(r+cmod2)+1w_{r,c} = (r + c \mathop{\mathrm{mod}} 2) + 1. For c=1c = 1, the sum will be 2. Each successive column will preserve the sum, and then a conflict will arise at the final column. The plot labeled “Mod-3 propagation, Flat” shows that this approach scales far better than any previous method. Whereas all the previously cited methods have DRAT proofs exceeding one million clauses for n≥50n \ge50, the direct encoding reaches n=140n = 140 before hitting that limit.

Lemmas allow us to push the scaling of modular arithmetic even further, by reducing the number of clauses added to encode and reason about mod-3 counters. For a width ww where n−2n - 2 is a multiple of ww, we can divide the board into the left column, a series of strips ww columns wide, and the right column. A single lemma suffices to show that the count at the left boundary of a strip is preserved when scanning to its right boundary. By setting ww to around n\sqrt{n}, we get balance between the number of mod-3 counters that connect the successive strips and the number of counters within the lemma between the columns of a single strip. When there are no suitable divisors of n−2n - 2, we may need to add a second lemma for a width w′<ww' < w. These results are shown as the plot “Mod-3 propagation, Strips” in Figure 6. For large values of nn, we can see that the use of lemmas substantially reduces the proof size. These proofs scale to n=318n = 318 before reaching one million clauses. In keeping with the DRATL requirements, all of the mod-3 counters must be introduced as part of the preamble for the top-level proof. Remarkably, for large values of nn, these proofs become smaller than the input formula, with the crossover occurring around n=1100n = 1100.

As a final optimization, we can subdivide the strips of width ww into columns of height hh and encode summations of both sets of variables hr,ch_{r,c} and vr,cv_{r,c}. As before, we may need to add an extra lemma for a smaller width, as well as lemmas for smaller heights. The exact setting of the parameters requires balancing many considerations, but we were able to train a regression model to select the parameters. These results are shown as the plot “Mod-3 propagation, Tiled” in Figure 6. As can be seen, it improves on the strips approach only for large values of nn, reaching one million clauses with n=384n = 384. For n≥380n \ge380, these proofs are smaller than the original input formula.

As these results show, mod-3 propagation alone enables compact proofs of the mutilated chessboard problem, but the use of lemmas greatly reduces the amount of overhead. At n=1000n = 1000, the tiled proofs are over 9×9\times smaller than the flat ones.

The scaling of these proofs presents a challenge for checking with our verification toolchain, consisting of DRAT-TRIM [18], a tool for expanding a DRAT proof into a more detailed form, followed by the formally verified CAKE_LPR checker [26]. We can only validate the flat proofs for up to n=320n = 320 and the strips and tiled proofs for up to n=420n = 420. The runtimes for DRAT-TRIM become impractical beyond that point, exceeding 30,000 seconds. Enabling more efficient checking is a clear priority for future work.

Queen Graph Coloring

The queen graph QnQ_n has the squares of an n×nn \times n board as vertices, adjacent when a queen moves between them. QnQ_n is not nn-colorable for n∈{8,9,10}n \in\{8, 9, 10\}. The n=10n = 10 formula, even when extended with symmetry breaking (fixing the diagonal), is hard for CDCL solvers. Solvers cannot easily infer surjectivity on the maximum cliques: in an nn-coloring, every row, column, and long diagonal uses every color. This is a pigeonhole-style consequence with no short resolution proof. Deriving these clique hints HQ,k=⋁v∈Qxv,kH_{Q,k} = \bigvee_{v \in Q} x_{v,k} for clique QQ and color kk collapses the instances. For n≥11n \ge11, QnQ_n is conjectured to be nn-colorable. Colorings are known for 11≤n≤2611 \le n \le26 [10]. Clique hints also boost performance on satisfiable formulas.

We derive the clique hints using a single lemma with n2n^2 parameters representing the assignment of nn colors to nn vertices. Its antecedent clauses require each vertex to have at least one color and prohibit two vertices from sharing a color. Its nn consequent clauses state that every color occurs in the clique. The lemma uses the chain derivation of Grosof, Zhang, and Heule [17], with 52n3\frac{5}{2}n^3 steps and all newly introduced variables treated as auxiliaries. We apply the lemma to each of the 2n+22n + 2 maximum cliques: the nn rows, nn columns, and two long diagonals. In each application, the instantiated antecedent consists of input clauses. Deriving all nn hints together allows them to share the same parameter bindings. An alternative lemma deriving a single clique hint would also require n2n^2 parameters. Applying it separately for each color would increase the number of binding clauses by a factor of nn.

The pipeline verifies end to end from the plain formula, within the substitution redundancy (SR) proof system [8], a generalization of DRAT. First, for symmetry breaking, n2n^2 SR steps fix the main diagonal to nn different colors, each witnessed by a color swap in the style of orbital fixing [2]. Second, the clique hints are derived via our lemma approach and turned into DRAT using the elaborator. Finally, CaDiCaL (version 3.0) produces that last part of the proof by solving the formula extended with the symmetry-breaking unit clauses and the clique hints. The concatenation is a single DSR proof of the original formula, checked by dsr-trim, whose annotated output is then checked by srcheck, the formally verified checker of [11], in under a dozen seconds per instance. With symmetry breaking, but without the hints, CaDiCaL takes 5.7 seconds at n=8n = 8 and 801 seconds at n=9n = 9, and does not solve n=10n = 10. With symmetry breaking and clique hints, all three instances are refuted in seconds (Table 1).

nnclauses + sym. unitstime w/o hintslemma appl.clique hintstime w/ hintsflat totalelaboratedend-to-end proofcheck
87,680 + 85.7 s181440.01 s134,3525,1268,0170.1 s
912,501 + 9801 s201800.26 s247,3207,19829,1470.6 s
1019,300 + 10> 3600 s2222012.5 s427,2409,773403,61311 s

Table 1. Queen graphs: one hint lemma per size, proved once and applied to all 2n+22n+2 maximum cliques. The first three columns show the size of the board and the number of clauses + symmetry-breaking units and the CDCL runtime without clique hints, respectively. The fourth column shows the number of lemma applications, followed by the number of added clique hints (consequent clauses). The last four columns show the size of deriving every hint by replaying the derivation once per hint (no lemmas), the sizes of the elaborated lemma proof and of the end-to-end proof, and the time to check the latter. The n=10n = 10 instance was not solved within an hour.

Mycielski Graphs

Mycielski’s construction takes a graph GG and returns a graph M(G)M(G) with the same clique number and chromatic number one higher [24]. Starting from M2=K2M_2 = K_2, the iterates Mk=M(Mk−1)M_k = M(M_{k-1}) are triangle-free with χ(Mk)=k\chi(M_k) = k. Refuting the (k−1)(k-1)-coloring of MkM_k is a classic hard family. The textbook proof is an induction: MkM_k consists of Mk−1M_{k-1}, a shadow vertex uvu_v per vertex vv with uvu_v adjacent to the neighbors of vv, and an additional vertex ww adjacent to all shadows. If ww has color aa, every shadow avoids aa, so recoloring each aa-colored vv to its shadow’s color turns a (k−1)(k-1)-coloring of MkM_k into a (k−2)(k-2)-coloring of Mk−1M_{k-1}, which does not exist by the same argument one level down.

This induction is a tower of lemmas, and it exercises every distinctive feature of DRATL at once. Lemma LjL_j has the coloring constraints of MjM_j as its antecedent clauses and a single empty consequent: it states that the (j−1)(j-1)-coloring of MjM_j is contradictory, and an application under qualifier QQ concludes Q∨⊥=QQ \lor\bot= Q: a refutation made reusable by the qualifier alone. The proof of LjL_j defines the j−1j-1 recolorings and derives their coloring constraints (all RUP), then applies Lj−1L_{j-1} to each, under the qualifier Zw,aZ_{w,a}; each application concludes (Zw,a)(Z_{w,a}), and the empty clause follows from the at-least-one clause for ww. The lemmas require no bookkeeping parameters: an application inside a lemma’s proof is automatically qualified by that proof’s activation guard, so conclusions carry exactly one caller guard at any nesting depth.

Nesting allows a single proof of each lemma to serve all of its instantiations. Without sharing, each application of LjL_j requires a separate copy of its proof, including the j−1j-1 applications of Lj−1L_{j-1}. Recursively expanding these applications yields a proof whose size grows like (k−1)!(k-1)!, while the nested proof grows linearly in the formula size up to a factor kk (Table 2). Elaboration adds only about five percent for the largest instance, preserving the sharing expressed in the DRATL proof.

graphclauseslemmasDRATLelaboratedflatcheck
M4M_{4}7123854634630.03 s
M5M_{5}30732,3242,6803,7610.05 s
M6M_{6}1,227411,92513,22128,1710.26 s
M7M_{7}4,625555,04859,190211,0332.8 s
M8M_{8}16,7116236,189248,3431,653,90532 s

Table 2. Mycielski graphs: the nested lemma tower. The first three columns show the graph, number of clauses and number of lemmas, respectively. “DRATL” shows the lines of the proof as written, “elaborated” and “flat” the additions of the expanded proof and of the expansion without lemma sharing; “check” is the total checking time: dsr-trim on the elaborated proof, then the formally verified srcheck on its annotated output.

Conclusions

This paper demonstrates that hierarchy can be introduced into a clausal proof framework to yield more compact proofs than the flat proofs generated by existing solvers and preprocessors. The ability to efficiently elaborate hierarchical proofs into flat ones avoids the need for new proof frameworks or checking tools. Our results demonstrate the utility of this approach for several highly structured challenge problems.

A clear next step in this effort is to have the elaborator also generate the full proof details, yielding a proof in the LRAT extension of the DRAT format [12]. Such a capability should be straightforward — the lemma proofs are fully self-contained, and deriving the hints for the steps outlined in Figure 3 is mostly a matter of bookkeeping. This would enable a direct interface to multiple formally verified proof checkers [11, 19, 26].

The method of elaborating lemmas described in Figure 3 could also be incorporated into other proof systems that allow the introduction of extension variables. These include clausal proof systems that generalize DRAT [11, 20, 21], as well as the VeriPB proof framework for pseudo-Boolean reasoning [15]. As with the RAT rule, these other proof systems include non-monotonic proof rules. Some limitations may need to be imposed on how these rules are used within the proof of a lemma to ensure that no conflict arises with an instantiation.

Another direction for research is to incorporate lemma extraction into a CDCL SAT solver, either as part of a preprocessing or an inprocessing step. The solver could identify multiple instances of a common clausal pattern and introduce a lemma creating a more useful representation of that pattern, similar to our processing of clique constraints in the Queen graph coloring problem.

References

References

  1. [1]Aleknovich, M.: Mutilated chessboard problem is exponentially hard for resolution. Theoretical Computer Science 310(1–3), 513–525 (2004)DOI
  2. [2]Anders, M., Codel, C., Heule, M.J.H.: Simplify, order, break, repeat. In: Theory and Applications of Satisfiability Testing (SAT). LIPIcs (2026)DOI
  3. [3]Armand, M., Faure, G., Grégoire, B., Keller, C., Théry, L., Werner, B.: A modular integration of SAT/SMT solvers to Coq through proof witnesses. In: Certified Programs and Proofs. LNCS, vol. 7086 (2011)DOI
  4. [4]Barrett, C., de Moura, L., Fontaine, P.: Proofs in satisfiability modulo theories. In: Paleo, B.W., Dehayе, D. (eds.) All about Proofs, Proofs for All, Mathematical Logic and Foundations, vol. 55. Cambridge University Press (2015)
  5. [5]Bryant, R.E., Biere, A., Heule, M.J.H.: Clausal proofs for pseudo-Boolean reasoning. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS). LNCS, vol. 12651, pp. 76–93 (2022)DOI
  6. [6]Bryant, R.E., Heule, M.J.H.: Generating extended resolution proofs with a BDD-based SAT solver. ACM Transactions on Computational Logic 24(4), 1–28 (2023)
  7. [7]Bryant, R.E., Nawrocki, W., Avigad, J., Heule, M.J.H.: Certified knowledge compilation with application to formally verified model counting. Journal of Artificial Intelligence Research 82, 2057–2099 (2025)arxiv.org/abs/2501.12906
  8. [8]Buss, S., Thapen, N.: DRAT proofs, propagation redundancy, and extended resolution. In: Theory and Applications of Satisfiability Testing (SAT). LNCS, vol. 11628 (2019)DOI
  9. [9]Capelli, F., Lagniez, J.M., Marquis, P.: Certifying top-down decision-DNNF compilers. In: AAAI Conference on Artificial Intelligence (2021)
  10. [10]Chvátal, V.: Colouring the queen graphs. https://users.encs.concordia.ca/~chvatal/queengraphs.html, accessed 16 October 2026
  11. [11]Codel, C.R., Avigad, J., Heule, M.J.H.: Verified substitution redundancy checking. In: Formal Methods in Computer-Aided Design (FMCAD). pp. 186–196 (2024)DOI
  12. [12]Cruz-Filipe, L., Heule, M.J.H., Hunt, W.A., Kaufmann, M., Schneider-Kamp, P.: Efficient certified RAT verification. In: Conference on Automated Deduction (CADE). LNCS, vol. 10395, pp. 220–236 (2017)
  13. [13]Fichte, J.K., Hecher, M., Roland, V.: Proofs for propositional model counting. In: Theory and Applications of Satisfiability Testing (SAT). Schloss Dagstuhl (2022)
  14. [14]Gocht, S., McCreesh, C., Nordström, J.: VeriPB: The easy way to make your combinatorial search algorithm trustworthy. In: From Constraint Programming to Trustworthy AI (2020)
  15. [15]Gocht, S., Nordström, J.: Certifying parity reasoning efficiently using pseudo-Boolean proofs. In: AAAI Conference on Artificial Intelligence. pp. 3768–3777 (2021)
  16. [16]Goldberg, E.I., Novikov, Y.: Verification of proofs of unsatisfiability for CNF formulas. In: Design, Automation and Test in Europe (DATE). pp. 886–891 (2003)
  17. [17]Grosof, I., Zhang, N., Heule, M.J.H.: Towards the shortest DRAT proof of the pigeonhole principle. In: Proceedings of Pragmatics of SAT (PoS) (2022)arxiv.org/abs/2207.11284
  18. [18]Heule, M.J.H.: The DRAT format and DRAT-trim checker. CoRR abs/160.06229 (2016)arxiv.org/abs/1610.06229
  19. [19]Heule, M.J.H., Hunt, W.A., Kaufmann, M., Wetzler, N.D.: Efficient, verified checking of propositional proofs. In: Interactive Theorem Proving. LNCS, vol. 10499, pp. 269–284 (2017)DOI
  20. [20]Heule, M.J.H., Kiesl, B., Biere, A.: Clausal proofs of mutilated chessboards. In: NASA Formal Methods (NFM). LNCS, vol. 11460, pp. 204–210 (2019)DOI
  21. [21]Heule, M.J.H., Kiesl, B., Biere, A.: Strong extension-free proof systems. Journal of Automated Reasoning 64, 533–554 (2019)DOI
  22. [22]Järvisalo, M., Heule, M.J.H., Biere, A.: Inprocessing rules. In: International Joint Conference on Automated Reasoning (IJCAR). LNCS, vol. 7364, pp. 355–370 (2012)
  23. [23]McCarthy, J.: A tough nut for proof procedures. Tech. Rep. Memo 16, Stanford Artificial Intelligence Project (1964)
  24. [24]Mycielski, J.: Sur le coloriage des graphes. Colloquium Mathematicum 3, 161–162 (1955)DOI
  25. [25]Niemetz, A., Preiner, M., Lonsing, F., Seidl, M., Biere, A.: Resolution-based certificate extraction for QBF. In: Theory and Applications of Satisfiability Testing (SAT). LNCS, vol. 7317, pp. 430–435 (2012)DOI
  26. [26]Tan, Y.K., Heule, M.J.H., Myreen, M.O.: Verified propagation redundancy and compositional UNSAT checking in CakeML. International Journal of Software Tools for Technology Transfer 25, 167–184 (2023)DOI
  27. [27]Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Automation of Reasoning: 2: Classical Papers on Computational Logic 1967–1970. pp. 466–483. Springer (1983)
  28. [28]Van Gelder, A.: Verifying RUP proofs of propositional unsatisfiability. In: Artificial Intelligence and Mathematics (ISAIM) (2008)
  29. [29]Wetzler, N.D., Heule, M.J.H., Hunt Jr., W.A.: DRAT-trim: Efficient checking and trimming using expressive clausal proofs. In: Theory and Applications of Satisfiability Testing (SAT). LNCS, vol. 8561, pp. 422–429 (2014)DOI
  30. [30]Yu, E., Biere, A., Heljanko, K.: Progress in certifying hardware model checking results. In: Computer Aided Verification (CAV). LNCS, vol. 12760, pp. 363–386 (2021)DOI
  31. [31]Zhang, L., Malik, S.: Validating SAT solvers using an independent resolution-based checker: Practical implementations and other applications. In: Design, Automation and Test in Europe (DATE). pp. 880–885 (2003)

Paper details

vlnc:W_fa7nze3g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents