diff options
Diffstat (limited to 'content/zettel/3d2a.md')
| -rw-r--r-- | content/zettel/3d2a.md | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/content/zettel/3d2a.md b/content/zettel/3d2a.md new file mode 100644 index 0000000..d79e596 --- /dev/null +++ b/content/zettel/3d2a.md @@ -0,0 +1,20 @@ ++++ +title = "Validating SAT and SMT proofs" +date = "2022-08-02" +author = "Yann Herklotz" +tags = [] +categories = [] +backlinks = ["3d2"] +forwardlinks = ["3d2b"] +zettelid = "3d2a" ++++ + +Validating a satisfiable result is quite easy, it's just a matter of +plugging it into the formula. However, a more difficult question is a +proof that a result is unsatisfiable. The main idea is that if a formula +is unsatisfiable, then it should be possible to simplify it to $\perp$. +Therefore, one can prove unsatisfiability by producing a trace of +rewriting rules that simplify the goal into $\perp$. If one can show +that the rewriting rules preserve satisfiability, one can show that +applying them will produce a $\perp$ result and therefore must be +equivalent to $\perp$. |