blob: d79e59690d60a697d1402875f53d4e1132fccf8e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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$.
|
