Skip to content
STIMSMITH

Conjunctive Normal Form (CNF)

Concept

Conjunctive Normal Form (CNF) is a Boolean formula structure expressed as a conjunction of clauses, where each clause is a disjunction of literals. In SystemVerilog constraint solving, constraints can be composed into Boolean formulas, simplified to CNF, and then handled using SAT/SMT techniques; Sudoku-style constraints illustrate how CNF clause counts can grow rapidly and how duplicate or unnecessary clauses may be reduced.

First seen 7/14/2026
Last seen 7/14/2026
Evidence 5 chunks
Wiki v1

WIKI

Overview

Conjunctive Normal Form (CNF) is a representation of a Boolean formula as a conjunction, or logical AND, of clauses. Each clause is a disjunction, or logical OR, of literals. A literal represents a predicate either in positive form, p, or negative form, !p. In the cited Sudoku constraint-solving paper, the general structure is written as a conjunction of clauses, and CNF is described as essentially a product-of-sums Boolean logic form. [cite: cnf-structure]

A clause may contain multiple literals. If a clause contains exactly one literal, it is a unit clause; that single literal must resolve to true for the clause to resolve to true. [cite: clauses-and-unit-clauses]

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
Performance of a SystemVerilog Sudoku Solver with VCS ← mentions 100% 2e
The paper discusses CNF as the formula structure used by the constraint solver.
Clausal Reduction Optimization ← uses 95% 2e
Clausal reduction optimization reduces the number of CNF clauses to improve solver performance.
VCS ← implements 90% 1e
VCS reduces constraints to CNF as part of its solving process.
Sudoku Constraint Solving ← uses 100% 1e
Sudoku constraint solving uses CNF as the formula structure for the constraint solver.

LINKED ENTITIES

4 links
Performance of a SystemVerilog Sudoku Solver with VCS MENTIONS Extracted graph relationship
VCS IMPLEMENTS Extracted graph relationship
Sudoku Constraint Solving USES Extracted graph relationship
Clausal Reduction Optimization USES Extracted graph relationship

CITATIONS

12 sources
12 citations — click to expand
[1] cnf-structure Performance of a SystemVerilog Sudoku Solver with VCS
[2] clauses-and-unit-clauses Performance of a SystemVerilog Sudoku Solver with VCS
[3] systemverilog-to-cnf Performance of a SystemVerilog Sudoku Solver with VCS
[4] sudoku-clause-growth Performance of a SystemVerilog Sudoku Solver with VCS
[5] range-to-unit-clauses Performance of a SystemVerilog Sudoku Solver with VCS
[6] sudoku-range-clause-count Performance of a SystemVerilog Sudoku Solver with VCS
[7] sudoku-row-constraints Performance of a SystemVerilog Sudoku Solver with VCS
[8] row-inequality-count Performance of a SystemVerilog Sudoku Solver with VCS
[9] parasitic-literals Performance of a SystemVerilog Sudoku Solver with VCS
[10] flat-game-board Performance of a SystemVerilog Sudoku Solver with VCS
[11] clausal-reduction-results Performance of a SystemVerilog Sudoku Solver with VCS
[12] disjunctiveprogramming-cnf DisjunctiveProgramming.jl: Generalized Disjunctive Programming Models and Algorithms for JuMP