Boolean Satisfiability

Concept

Boolean Satisfiability (SAT) is used in formal verification as the solving basis for techniques such as SAT-based Bounded Model Checking and interval property checking. In the provided evidence, safety properties of synchronous circuits are translated into Boolean functions or SAT instances, where satisfying assignments represent counterexamples to the checked property.

First seen 5/26/2026

Last seen 5/29/2026

Evidence 2 chunks

Wiki v1

WIKI

Overview

Boolean Satisfiability, abbreviated SAT, appears in formal verification as the basis for checking properties of hardware designs. The evidence describes SAT-based methods as a robust solution in formal verification, with SAT-based Bounded Model Checking (BMC) identified as a prominent technique whose performance improvements made it suitable for larger-scale designs.[C1]

Use in property checking

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

2 connections

Interval Property Checking ← uses 100% 3e

IPC uses SAT-based methods for verification.

Bounded Model Checking ← uses 100% 1e

Bounded model checking uses Boolean satisfiability (SAT) as its core solving mechanism.

LINKED ENTITIES

1 links

Safety Property encodes The evidence describes safety properties being translated into Boolean functions and checked as SAT instances.

CITATIONS

6 sources

6 citations — click to expand

[1] SAT-based methods are described as a robust solution in formal verification, and SAT-based Bounded Model Checking is identified as a prominent technique suitable for larger-scale designs after performance improvements. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[2] Safety properties lead to bounded properties that can be checked efficiently using a SAT solver. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[3] A synchronous circuit is modeled as a finite-state machine, and a safety property can be translated into a Boolean function whose satisfying assignment corresponds to a counterexample. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[4] Interval property checking searches for counterexamples by solving a SAT instance that combines an unrolled transition relation with the translated property. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[5] Interval property checking verifies safety properties, uses an arbitrary starting state rather than the initial state used in BMC, and properties that hold from arbitrary states also hold from reachable states. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[6] Interval property checking can produce false negatives from unreachable states, and these are removed by adding invariants that restrict the starting state. Generating an Efficient Instruction Set Simulator from a Complete Property Suite