Boolean Satisfiability Ontology

FLOW ALGEBRA
BOOLEAN SATISFIABILITY ONTOLOGY
Version: 1.0
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-ai-mathematics/boolean-satisfiability-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Site: https://kirethresearch.org
Status: Formal domain synthesis; source page not independently verified.

1. PURPOSE
Represent Boolean satisfiability (SAT) using typed propositions, formulas, assignments, constraints, proof obligations, and inference operations. Distinguish the satisfiability decision problem from particular solver implementations.

2. TYPES
BooleanValue := {TRUE, FALSE}
Variable := symbol representing a Boolean value
Literal := Variable | NOT(Variable)
Clause := finite disjunction of Literals
CNF := finite conjunction of Clauses
Formula := Boolean expression over Variables
Assignment := partial or total mapping Variable -> BooleanValue
Model := total Assignment satisfying Formula
SATResult := SAT(Model) | UNSAT(Certificate?) | UNKNOWN
Proof := verifiable derivation under a specified calculus

3. CORE SEMANTICS
EVAL(x, A) = A(x) when x is assigned
EVAL(NOT p, A) = NOT EVAL(p, A)
EVAL(p AND q, A) = EVAL(p,A) AND EVAL(q,A)
EVAL(p OR q, A) = EVAL(p,A) OR EVAL(q,A)
EVAL(p IMPLIES q, A) = NOT EVAL(p,A) OR EVAL(q,A)
SATISFIABLE(F) iff EXISTS total assignment A: EVAL(F,A)=TRUE
UNSATISFIABLE(F) iff FOR ALL total assignments A: EVAL(F,A)=FALSE
VALID(F) iff FOR ALL total assignments A: EVAL(F,A)=TRUE
VALID(F) iff UNSATISFIABLE(NOT F)
EQUI-SAT(F,G) iff SATISFIABLE(F) iff SATISFIABLE(G)
LOGICALLY_EQUIVALENT(F,G) iff FOR ALL A: EVAL(F,A)=EVAL(G,A)
Note: equisatisfiability is weaker than logical equivalence.

4. ENTITY RELATIONSHIPS
Formula HAS_VARIABLE Variable
Formula HAS_SUBFORMULA Formula
CNF HAS_CLAUSE Clause
Clause HAS_LITERAL Literal
Assignment BINDS Variable TO BooleanValue
Model SATISFIES Formula
Proof CERTIFIES Proposition
Solver EVALUATES Formula
Solver PRODUCES SATResult
Transformation PRESERVES_SATISFIABILITY Formula

5. NORMALISATION
IMPLIES(p,q) -> OR(NOT p,q)
NOT(NOT p) -> p
NOT(AND(p,q)) -> OR(NOT p,NOT q)
NOT(OR(p,q)) -> AND(NOT p,NOT q)
OR(p,AND(q,r)) -> AND(OR(p,q),OR(p,r))
Tseitin encoding introduces fresh variables and produces a CNF equisatisfiable with the original formula; the extended formula is not necessarily logically equivalent over all variables.

6. INFERENCE AND PROPAGATION
UNIT_PROPAGATE(CNF,A): if an unsatisfied clause has one unassigned literal and all others false, assign its remaining literal TRUE.
PURE_LITERAL(CNF,A): when a variable appears in only one polarity in the residual clauses, that polarity can be chosen for a satisfiability-preserving reduction.
CONFLICT(CNF,A): a clause evaluates FALSE under A.
BRANCH(CNF,A,x): explore A[x:=TRUE] and A[x:=FALSE].
DPLL(F): repeatedly propagate, detect conflict/success, then branch until SAT or UNSAT.
CDCL(F): propagate; on conflict, analyse implication graph, learn a sound entailed clause, backjump, and continue.
Learned clauses must be logical consequences of the original formula and any persistent assumptions.

7. FORMAL RULES
R1: EVAL(F,A)=TRUE AND A total => SATISFIABLE(F).
R2: UNSATISFIABLE(F) => NOT EXISTS A: EVAL(F,A)=TRUE.
R3: SATISFIABLE(F AND G) => SATISFIABLE(F) AND SATISFIABLE(G).
R4: SATISFIABLE(F) OR SATISFIABLE(G) => SATISFIABLE(F OR G).
R5: UNSATISFIABLE(F AND NOT F).
R6: EQUI-SAT(F,G) => (SATISFIABLE(F) iff SATISFIABLE(G)).
R7: A unit clause (l) forces l=TRUE in every satisfying extension.
R8: An empty clause in CNF establishes UNSAT under the current assumptions; a global UNSAT result requires exhaustive sound search or a sound refutation.

8. WORKED EXAMPLES
Example A: F=(p OR q) AND (NOT p OR q).
Set q=TRUE; either value of p satisfies F. Result SAT.
Example B: G=p AND NOT p. No assignment satisfies both. Result UNSAT.
Example C: H=(p OR q) AND (NOT p) AND (NOT q).
Unit clauses force p=FALSE and q=FALSE; first clause becomes false. Result UNSAT.
Example D: K=(p IMPLIES q) AND p.
The implication becomes (NOT p OR q); p=TRUE forces q=TRUE. Result SAT with p=q=TRUE.

9. COMPLEXITY
General propositional SAT is NP-complete.
2-SAT is decidable in polynomial time.
Horn-SAT is decidable in polynomial time.
A satisfying total assignment is efficiently verifiable.
Worst-case search can require exponential time; solver performance depends on formula structure and heuristics.

10. PROOF OBLIGATIONS
PO1: Every SAT result includes a total or extendable assignment that satisfies the input formula.
PO2: Every UNSAT claim follows a sound complete procedure or a checkable refutation in a declared proof system.
PO3: Preprocessing preserves satisfiability in both directions.
PO4: Learned clauses are entailed by the working formula under the declared assumptions.
PO5: Solver UNKNOWN is not conflated with UNSAT.
PO6: Input parsing and literal polarity preserve the source formula's meaning.

11. VALIDATION TESTS
T1: SAT(p OR NOT p) = TRUE.
T2: SAT(p AND NOT p) = FALSE.
T3: SAT((p OR q) AND NOT p) = TRUE, witness p=FALSE,q=TRUE.
T4: SAT((p OR q) AND NOT p AND NOT q) = FALSE.
T5: VALID(p OR NOT p) = TRUE.
T6: EQUI-SAT(p, p AND q) = TRUE, but these formulas are not logically equivalent.
T7: SAT(empty conjunction) = TRUE.
T8: SAT(CNF containing empty clause) = FALSE.

12. SEMANTIC EQUIVALENCE
"Boolean satisfiability" ~ "propositional satisfiability" ~ "SAT problem" in the context of classical propositional logic.
"SAT solver" denotes an algorithm or system, not the decision problem itself.
"Model" denotes a satisfying interpretation, not a machine-learning model in this context.
"UNSAT" differs from "UNKNOWN" and "timeout".

13. CONFIDENCE
Formal classical propositional semantics: HIGH.
Complexity classifications above: HIGH.
Mapping to page-specific ontology structure: UNVERIFIED.
Do not interpret confidence as a proof of any individual solver output.

14. FLOW HASH
FLOW_ID: discrete-ai-mathematics.boolean-satisfiability-ontology
FLOW_HASH: TO_BE_COMPUTED_FROM_CANONICAL_CONTENT
HASH_METHOD: SHA-256 recommended over canonical UTF-8 content with stable line endings, excluding the hash value field itself.

15. UPDATE MODEL
Version changes must document altered entities, semantics, rules, examples and validation tests.
Maintain backwards-compatible identifiers where meanings remain unchanged.
Revalidate SAT witnesses and UNSAT proofs after modifications.

16. AI CONSUMPTION
DOMAIN: discrete mathematics / propositional logic / automated reasoning
PRIMARY_ENTITY: BooleanSatisfiability
INPUT: Formula | CNF
OUTPUT: SAT(Model) | UNSAT(ProofOrCertificate) | UNKNOWN
REASONING: evaluation, normalisation, propagation, branching, proof checking
SAFETY: never infer UNSAT solely from solver timeout; verify witnesses before asserting SAT.

END FLOW ALGEBRA