Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
sav08:dpll_algorithm_for_sat [2013/04/17 17:35] vkuncak |
sav08:dpll_algorithm_for_sat [2015/04/21 17:30] (current) |
||
---|---|---|---|
Line 90: | Line 90: | ||
**Decision step** (picking variable value): from proofs for | **Decision step** (picking variable value): from proofs for | ||
- | \[ | + | \begin{equation*} |
S' \cup \{p\} \vdash {\it false} | S' \cup \{p\} \vdash {\it false} | ||
- | \] | + | \end{equation*} |
- | \[ | + | \begin{equation*} |
S' \cup \{\lnot p\} \vdash {\it false} | S' \cup \{\lnot p\} \vdash {\it false} | ||
- | \] | + | \end{equation*} |
we would like to construct the proof for | we would like to construct the proof for | ||
- | \[ | + | \begin{equation*} |
S' \vdash {\it false} | S' \vdash {\it false} | ||
- | \] | + | \end{equation*} |
From | From | ||
- | \[ | + | \begin{equation*} |
S' \cup \{p\} \vdash {\it false} | S' \cup \{p\} \vdash {\it false} | ||
- | \] | + | \end{equation*} |
derive proof tree for | derive proof tree for | ||
- | \[ | + | \begin{equation*} |
S' \vdash \lnot p | S' \vdash \lnot p | ||
- | \] | + | \end{equation*} |
and from | and from | ||
- | \[ | + | \begin{equation*} |
S' \cup \{\lnot p\} \vdash {\it false} | S' \cup \{\lnot p\} \vdash {\it false} | ||
- | \] | + | \end{equation*} |
derive proof tree for | derive proof tree for | ||
- | \[ | + | \begin{equation*} |
S' \vdash p | S' \vdash p | ||
- | \] | + | \end{equation*} |
Then combine these two trees with resolution on $\{p\}$ and $\{\lnot p\}$ to get ${\it false}$. | Then combine these two trees with resolution on $\{p\}$ and $\{\lnot p\}$ to get ${\it false}$. | ||