Boolean Satisfiability Checking

Technique WIKI v1 · 5/30/2026

In the provided evidence, Boolean satisfiability checking is presented as a Boolean method that can be applied after reducing formulas in the logic of equality with uninterpreted functions (EUF) to propositional formulas. The cited paper uses this reduction-based approach for processor verification and reports efficient experimental results on pipelined processors.

Boolean Satisfiability Checking

Boolean satisfiability checking appears in the provided evidence as one of the Boolean methods used after reducing formulas in the logic of equality with uninterpreted functions (EUF) to propositional formulas. In this role, it is part of a verification workflow for processor control logic and is mentioned alongside Ordered Binary Decision Diagrams (BDDs). [C1]

Role in the cited verification approach

Bryant, German, and Velev state that reducing EUF formulas to propositional formulas makes it possible to apply "Boolean methods such as Ordered Binary Decision Diagrams (BDDs) and Boolean satisfiability checkers" to verification problems. [C1]

The same abstract says the generated propositional formulas can be greatly simplified by exploiting characteristics of the verification conditions, particularly that many equations appear only in positive form. This reduces the interpretations of function symbols that must be considered when proving universal validity. [C2]

Reported use case

The cited paper reports experimental results demonstrating the efficiency of this reduction-based approach when verifying pipelined processors using the method proposed by Burch and Dill. In the evidence provided for this entity, Boolean satisfiability checking is therefore supported specifically as a technique used within that processor-verification setting. [C3]

LINKED ENTITIES

1 links

Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic USES

CITATIONS

3 sources

3 citations

[1] Reducing EUF formulas to propositional formulas enables the use of Boolean satisfiability checkers, alongside BDDs, for verification. Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic

[2] The approach simplifies generated propositional formulas by exploiting verification-condition structure, including that many equations appear only in positive form, thereby restricting the interpretations that must be considered. Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic

[3] The paper reports experimental results showing the efficiency of the approach for verifying pipelined processors using the Burch and Dill method. Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic