ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Converting a small Boolean formula to equisatisfiable 3-CNF with extension variables

Example

Consider the formula $φ : = (x \land y) \lor z .$ Introduce $a$ for the subformula $(x \land y)$ and $b$ for $φ$ itself.

Facts & Assumptions

Given: The formula $φ = (x \land y) \lor z$ .

[L1]

The Tseitin transformation introduces extension variables for subformulas and preserves satisfiability with clauses of size at most three, by The Tseitin transformation has linear size and preserves satisfiability.

[L2]

The language $3$ -SAT is NP-complete, so such linear-size translations are the standard bridge from SAT to $3$ -SAT, by 3-SAT is NP-complete.

Verification

technique · direct

1.1

The Tseitin clauses are $(\neg a \lor x)$ , $(\neg a \lor y)$ , $(a \lor \neg x \lor \neg y)$ for $a \leftrightarrow (x \land y)$ , together with $(b \lor \neg a)$ , $(b \lor \neg z)$ , $(\neg b \lor a \lor z)$ for $b \leftrightarrow (a \lor z)$ , and the root clause $(b)$ .

L1givenconstruct

2.1

If $φ$ is satisfiable, set $a$ and $b$ to the truth values of their subformulas; then all clauses in step 1.1 are satisfied. Conversely, any satisfying assignment of those clauses forces $b = 1$ and hence $(x \land y) \lor z = 1$ . So step 1.1 is an explicit equisatisfiable $3$ -CNF encoding of $φ$ , illustrating [L1] and therefore [L2].

L1L2step 1.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)