SAT Solver Ontology

FLOW ALGEBRA
SAT SOLVER ONTOLOGY
Kireth Semantic Library | Discrete AI Mathematics
Version: 1.0 | Date: 2026-10-11 | Locale: en-GB
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-ai-mathematics/sat-solver-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Domain-grounded synthesis; source page not independently verified.

1. PURPOSE
Model propositional satisfiability, SAT solving, proofs, search, propagation, and solver outputs using typed entities and auditable inference.

2. TYPES
BooleanVariable := identifier
Literal := Positive(BooleanVariable) | Negative(BooleanVariable)
Clause := finite set of Literal
CNFFormula := finite conjunction of Clause
Assignment := partial map BooleanVariable -> {true,false}
SolverState := (formula, assignment, trail, decision_level, clause_database)
SATResult := SAT(model) | UNSAT(proof) | UNKNOWN(reason)
ProofCertificate := machine-checkable derivation or recognised proof format

3. RELATIONSHIPS
contains_clause(CNFFormula, Clause)
contains_literal(Clause, Literal)
negates(Literal, Literal)
assigns(Assignment, BooleanVariable, Boolean)
satisfies(Assignment, Clause | CNFFormula)
conflicts_with(Assignment, Clause)
implies(Clause, Literal, Assignment)
learns(SolverState, Clause)
backjumps_to(SolverState, DecisionLevel)
certifies(ProofCertificate, UNSATResult)

4. SEMANTICS
EVAL(x,A) = A(x), if x assigned
EVAL(not x,A) = not A(x), if x assigned
EVAL(C,A) = OR(EVAL(l,A) for l in C)
EVAL(F,A) = AND(EVAL(C,A) for C in F)
SAT(F) iff exists total A with EVAL(F,A)=true
UNSAT(F) iff for all total A, EVAL(F,A)=false
Partial assignments may leave a clause unresolved; unresolved is not false.

5. CORE TRANSFORMATIONS
TO_CNF(phi) -> F, preserving satisfiability (equisatisfiable conversion)
UNIT_PROPAGATE(F,A) -> (A', conflict?)
PURE_LITERAL_ELIMINATION(F,A) -> A' [optional preprocessing]
DECIDE(S,x,v) -> S'
ANALYSE_CONFLICT(S) -> (learned_clause, backjump_level)
BACKJUMP(S,level) -> S'
RESTART(S) -> S' [retains permitted learned clauses]
VERIFY_MODEL(F,A) -> Boolean
VERIFY_UNSAT_PROOF(F,P) -> Boolean

6. INFERENCE RULES
UNIT: if clause (l OR l1 OR ... OR lk) has all li false and l unassigned, infer l=true.
CONFLICT: if every literal of a clause is false, infer conflict.
RESOLUTION: from (A OR x) and (B OR not x), infer (A OR B).
LEARN: a conflict-derived clause entailed by the current formula may be added.
BACKJUMP: return to a decision level justified by conflict analysis.
SAT_REPORT: report SAT only with a total satisfying assignment (or verified extension).
UNSAT_REPORT: report UNSAT only after sound exhaustive reasoning or a valid proof.

7. CDCL SOLVER FLOW
INPUT: propositional formula phi
F := TO_CNF(phi)
S := INITIALISE(F)
LOOP:
  propagate := UNIT_PROPAGATE(S)
  IF conflict:
    IF decision_level = 0: RETURN UNSAT(proof_if_available)
    (clause, level) := ANALYSE_CONFLICT(S)
    ADD_LEARNED_CLAUSE(S, clause)
    BACKJUMP(S, level)
    CONTINUE
  IF all clauses satisfied:
    A := EXTEND_TO_TOTAL_MODEL(S.assignment)
    ASSERT VERIFY_MODEL(F,A)
    RETURN SAT(A)
  IF resource_limit_reached: RETURN UNKNOWN(resource_limit)
  (variable,value) := CHOOSE_BRANCH(S)
  DECIDE(S,variable,value)

8. COMPLEXITY
General propositional SAT is NP-complete.
A proposed satisfying assignment is verifiable in polynomial time.
Worst-case solving time is exponential unless major complexity-theoretic assumptions fail.
Practical performance depends on encoding, propagation, branching, learning, and restarts.
2-SAT is solvable in polynomial time; Horn-SAT is solvable in polynomial time.

9. WORKED EXAMPLES
F1 = (x OR y) AND (not x OR y) AND (x OR not y)
A1 = {x:true,y:true}; VERIFY_MODEL(F1,A1)=true; SAT(F1).
F2 = (x) AND (not x)
UNIT on (x) forces x=true; (not x) conflicts; UNSAT(F2).
F3 = (x OR y) AND (not x OR y) AND (x OR not y) AND (not x OR not y)
No assignment to x,y satisfies all four clauses; UNSAT(F3).

10. PROOF AND VALIDATION OBLIGATIONS
V1: Each clause contains only well-formed literals.
V2: Each variable has a unique identifier and Boolean domain.
V3: Every learned clause is logically entailed by the original and previously valid clauses.
V4: Every reported SAT model satisfies the original input, not merely an unchecked encoding.
V5: Equisatisfiable encodings are not necessarily logically equivalent formulas.
V6: UNSAT certificates are independently checked when supplied.
V7: UNKNOWN must not be treated as UNSAT.
V8: Resource and solver-version metadata are recorded for reproducibility.

11. SEMANTIC_EQUIVALENCE
SAT solver ~= propositional satisfiability engine [context-dependent]
CDCL solver is_a SAT solver
DPLL solver is_a SAT solver
SAT differs_from SMT (SMT supports background theories)
SAT differs_from MAX-SAT (optimises satisfied clauses)
SAT differs_from QBF (supports quantified Boolean variables)
CNF encoding may be equisatisfiable_without_being_equivalent_to source formula.

12. CONFIDENCE
formal_semantics: 1.00 [mathematical definitions]
solver_result_sat: 1.00 if original formula and model independently verified
solver_result_unsat: 1.00 if proof independently verified
unverified_solver_claim: provisional; never substitute confidence for proof

13. FLOW_HASH
canonicalise: UTF-8, LF line endings, normalised whitespace, stable entity order
algorithm: SHA-256
value: COMPUTE_AT_PUBLICATION (not fabricated)

14. UPDATE_MODEL
version: 1.0
change_policy: increment version for semantic, inference, or validation changes
revalidate: examples, type rules, soundness claims, cross-ontology links
provenance: preserve source URL, revision date, authorship, and verification status

15. AI_CONSUMPTION
machine_readable: true
intended_tasks: concept retrieval, constraint modelling, solver orchestration, proof checking, educational reasoning
required_guards: distinguish SAT/UNSAT/UNKNOWN; verify model and proof; avoid unsupported performance guarantees
linked_domains: Boolean Logic, Mathematical Logic, Constraint Satisfaction, Graph Algorithms, Computational Complexity, Formal Verification
output_contract: {status: SAT|UNSAT|UNKNOWN, model?: Assignment, proof?: ProofCertificate, diagnostics?: String}

END FLOW ALGEBRA