Tableau formula correctness
ProvedPvsNP.tableauCNF_correctThe combined formula is satisfiable exactly when a tableau satisfies the explicitly defined cell, initial, boundary, accepting and local-window constraints.
Status: Known mathematics / implementation obligation awaiting formal proof.
import Definitions.Def_PvsNPFrontier
namespace PvsNP
theorem tableauCNF_correct (S : TableauSpec) :
Satisfiable (tableauCNF S) ↔ ∃ T, ValidTableau S T := by sorry
end PvsNPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
For every specification , there exists a Boolean assignment making every clause of the full tableau formula true if and only if there exists a total natural-valued two-argument function satisfying the validity condition described here. Neither side additionally assumes the stricter specification predicate; all specifications, including those with zero fields, missing lists, and empty accepting lists, are quantified over. Here has , a list of lists of natural numbers, a list of natural numbers, and a list of lists of natural numbers, with no validity restrictions on these fields. Put , , and . The list is the zero-based th list of , or the empty list when that entry is missing. The full tableau formula is the concatenation, in order, of the cell, initial, boundary, accepting, and transition formulas described here. The cell formula consists, in increasing and then increasing , of the clause of all positive literals for , followed by every two-literal clause with , ordered first by and then by . The initial formula has, in increasing and then increasing , the negative unit clause exactly when . The boundary formula has, for each in order, the two positive unit clauses at and , in that order. The accepting formula is a list containing one clause; its literals are for every and with , ordered first by and then by . If no such exists, this is an empty clause rather than an empty formula. The transition formula ranges in increasing order over , , and lexicographically over all six-tuples absent from the list . For each such tuple it has the clause of the six negative literals at positions with symbol indices given by the corresponding entries of , in that order. If or , the transition formula is empty. The validity condition for is the conjunction of: ; ; ; ; and . Values outside the rectangle are unrestricted; the last condition is vacuous for or , and a missing required or an empty makes the condition unsatisfiable. A formula is a finite list of clauses, each clause a finite list of literals . Under an assignment , the literal is true exactly when , a clause is true exactly when some literal in it is true, and a formula is true exactly when every clause is true. Thus an empty clause is false and an empty formula is true. Here , is the set of all finite Boolean lists, including the empty list, and is list length. The supplied body is admitted with sorry; no proof of this assertion is supplied there.