Boolean Satisfiability

Concept

Boolean Satisfiability (SAT) is the decision problem of determining whether a Boolean formula has a satisfying assignment. In the provided evidence, SAT plays a central role in formal hardware verification (as the solving engine behind SAT-based Bounded Model Checking and Interval Property Checking) and is the source of related sub-problems such as unsatisfiable-core and minimal-unsatisfiable-subformula computation that arise in diagnosing over-constrained problems.

First seen 5/26/2026

Last seen 7/13/2026

Evidence 3 chunks

Wiki v2

WIKI

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

READ FULL ARTICLE →

NEIGHBORHOOD

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

explore full graph →

RELATIONSHIPS

4 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.

Contradiction Analysis for Constraint-based Random Simulation ← mentions 90% 1e

The paper mentions Boolean Satisfiability as an analogous domain where unsat core computation is performed.

Minimal Unsatisfiable Subformula ← derived from 90% 1e

Minimal unsatisfiable subformulas are a concept arising in the Boolean satisfiability domain.

LINKED ENTITIES

2 links

Contradiction Analysis for Constraint-based Random Simulation MENTIONS Extracted graph relationship

Minimal Unsatisfiable Subformula DERIVED_FROM Extracted graph relationship

CITATIONS

7 sources

7 citations — click to expand

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

[2] In the SAT domain, the analogous sub-problem to diagnosing over-constrained constraint systems is computing an unsatisfiable core of an unsatisfiable formula, i.e. identifying an unsatisfiable sub-formula of the overall formula. Over-constrained Constraint Analysis for Random Simulation (grosse, rwille, drechsler)

[3] Restricting checking to safety properties leads to bounded properties that can be checked efficiently using a SAT solver. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[4] A synchronous circuit's transition relation can be written as T(s, s') = exists x in B^n : s' == Delta(x, s), and a safety property f = AG(phi) is translated into a Boolean function [[f]]_t such that a satisfying assignment corresponds to a counterexample of phi. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[5] Interval property checking searches for counterexamples by solving the SAT instance AND_{i=0..c} T(s_{t+i}, s_{t+i+1}) AND [[f]]_t, whose satisfying assignments indicate counterexamples for the checked safety property. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[6] IPC verifies only safety properties and uses an arbitrary starting state rather than the initial state used in BMC, giving exhaustive verification under that condition; false negatives arising from unreachable starting states must be removed by adding invariants that restrict the starting state. Generating an Efficient Instruction Set Simulator from a Complete Property Suite

[7] To obtain a minimal reason for unsatisfiability, the more complex problem of a minimal unsat core (minimal unsatisfiable sub-formula) must be considered, and determining all minimal unsat cores is in general very time consuming. Over-constrained Constraint Analysis for Random Simulation (grosse, rwille, drechsler)