Verify a SAT certificate: an assignment of true and false.
What to build
A program that checks whether an assignment satisfies a formula in conjunctive normal form.
Requirements
- Print
satisfiedif every clause is true. - Otherwise print
clause j is falsefor the first false clause, counting from 1.
Input
Line 1: n and m. Then m clauses, each a line of literals (k or −k). Last line: n values, 0 or 1, for x1 … xn.
Output
One line.
Constraints
n ≤ 30; m ≤ 100.
Example
Input:
3 2
1 -2
2 3
1 0 1
Output:
satisfied
Why it works
Checking each clause against the assignment takes time proportional to the formula's size, so SAT is in NP.
Examples
Example 1 · Input
3 2 1 -2 2 3 1 0 1
Expected output
satisfied
Example 2 · Input
3 2 1 -2 2 3 0 1 0
Expected output
clause 1 is false
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A clause is true if any of its literals is true; literal k means x_k is 1, and −k means x_k is 0.
Hint 2
Check the clauses in order and report the first false one.
Solution
Show one correct solution (try it yourself first)
n, m = map(int, input().split())
clauses = [list(map(int, input().split())) for _ in range(m)]
values = list(map(int, input().split()))
def true(literal):
value = values[abs(literal) - 1]
return value == 1 if literal > 0 else value == 0
for j, clause in enumerate(clauses, 1):
if not any(true(lit) for lit in clause):
print(f"clause {j} is false")
break
else:
print("satisfied")