Overview

Boolean Satisfiability, abbreviated SAT, is the problem of deciding whether a Boolean formula admits an assignment that makes it evaluate to true. In the provided evidence, SAT appears in two main roles: (1) as the solving engine at the core of SAT-based formal hardware verification techniques, and (2) as the conceptual origin of related problems such as unsatisfiable-core and minimal unsatisfiable subformula computation, which are reused in adjacent domains such as diagnosing over-constrained constraint-based random simulation.[C1][C2]

Use in formal hardware verification

SAT-based methods are described as a robust solution in formal verification. SAT-based Bounded Model Checking (BMC) is identified as a prominent technique whose performance improvements have made it suitable for larger-scale designs.[C1]

In the described verification setting, the intended behavior of a design is formalized using safety properties. Restricting checking to safety properties leads to bounded properties that can be checked efficiently using a SAT solver.[C3]

A synchronous circuit is modeled as a finite-state machine with inputs, outputs, states, initial states, an output function, and a next-state function. Its transition relation can be written as:

T(s, s') = exists x in B^n : s' == Delta(x, s)

A safety property f = AG(phi) is translated into a Boolean function [[f]]_t that checks the validity of phi at a time point t. The translation is constructed so that a satisfying assignment of [[f]]_t corresponds to a counterexample of phi.[C4]

SAT instances in interval property checking

Interval property checking (IPC) searches for counterexamples by solving a SAT instance that combines an unrolled transition relation with the Boolean encoding of the property. In the provided formalization, the transition relation is unrolled over a bounded interval and connected to a single instantiation of the translated property:

AND_{i=0..c} T(s_{t+i}, s_{t+i+1}) AND [[f]]_t

The result is a SAT problem whose satisfying assignments indicate counterexamples for the checked safety property.[C5]

Relationship to BMC and IPC

SAT-based BMC is presented as one of the prominent SAT-based formal verification techniques. IPC is contrasted with original BMC: IPC verifies only safety properties and uses an arbitrary starting state rather than the initial state used in BMC. A property that holds from an arbitrary state also holds from any reachable state, giving exhaustive verification under that condition.[C6]

Because IPC can start from unreachable states, it can produce false negatives: counterexamples that arise only from unreachable states. The evidence states that such false negatives must be removed by adding invariants that restrict the starting state.[C6]

Related problems: unsatisfiable cores and minimal unsatisfiable subformulas

In the SAT domain, the evidence identifies an analogous sub-problem to diagnosing over-constrained constraint satisfaction problems: computing an unsatisfiable core of an unsatisfiable formula, i.e. identifying an unsatisfiable sub-formula of the overall formula. To obtain a minimal reason for the unsatisfiability, the more complex problem of a minimal unsat core (a minimal unsatisfiable sub-formula) must be considered. Furthermore, all minimal unsat cores are required to determine all contradictions, which is in general very time consuming.[C7]

Practical significance

Within the evidence, SAT is not treated as an isolated topic but as an enabling mechanism for both formal verification workflows and for diagnosing contradictions in constraint-based settings. SAT solvers are used to efficiently check bounded safety properties, SAT instances encode both the transition behavior of a design and the condition whose satisfaction corresponds to a counterexample, and SAT sub-problems (unsat cores and minimal unsatisfiable subformulas) are the natural counterparts of contradiction analysis in over-constrained constraint systems.[C3][C5][C7]