Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:instantiation_plus_ground_resolution [2008/04/01 16:20] vkuncak |
sav08:instantiation_plus_ground_resolution [2008/04/02 10:45] vkuncak |
||
---|---|---|---|
Line 9: | Line 9: | ||
The proof system has two rules: ground instantiation and ground resolution. | The proof system has two rules: ground instantiation and ground resolution. | ||
- | **Ground Instantiation Rule** | + | === Ground Instantiation Rule === |
\[ | \[ | ||
Line 18: | Line 18: | ||
Ground substitution is of the form $\{x_1 \mapsto t_1,\ldots,x_n \mapsto t_n\}$ where each $t_i$ is a ground term. | Ground substitution is of the form $\{x_1 \mapsto t_1,\ldots,x_n \mapsto t_n\}$ where each $t_i$ is a ground term. | ||
- | **Ground Resolution Rule** | + | === Ground Resolution Rule === |
If $A$ is a ground atom and $C,D$ are ground claues, then | If $A$ is a ground atom and $C,D$ are ground claues, then | ||
Line 28: | Line 28: | ||
Note that this is propositional resolution where propositional variables have "long names" (they are ground atoms). | Note that this is propositional resolution where propositional variables have "long names" (they are ground atoms). | ||
- | **Ground Factoring** | + | ==== Example ==== |
- | If $A$ is a ground atom and $C$ are ground clauses, | ||
- | \[ | ||
- | \frac{C \cup \{\lnot A, A\}} | ||
- | {C} | ||
- | \] | ||
- | (It is a necessary simplification rule in propositional resolution.) | ||
- | |||
- | ==== Example ==== | ||
===== Completeness ===== | ===== Completeness ===== | ||
Line 43: | Line 35: | ||
The proof is based on [[Herbrand's Expansion Theorem]] (see also the proof of [[Compactness for First-Order Logic]]). | The proof is based on [[Herbrand's Expansion Theorem]] (see also the proof of [[Compactness for First-Order Logic]]). | ||
- | Suppose a set $S$ of clauses is contradictory. By [[Herbrand's Expansion Theorem]] and [[Compactness Theorem|Compactness Theorem for Propositional Formulas]], there is some finite subset $S_0 \subseteq expand(S)$ is contradictory. Then there exists a derivation of empty clause from $S_0$ viewed as set of propositional formulas, using propositional resolution. In other words, there exists a derivation of empty clause from $S_0$ using ground resolution rule. Each element of $S_0$ can be obtained from an element of $S$ using instantiation rule. This means that there exists a proof tree that starts by a single application of instantiation rule, and then performs ground resolution. | + | Suppose a set $S$ of clauses is contradictory. By [[Herbrand's Expansion Theorem]] and [[Compactness Theorem|Compactness Theorem for Propositional Formulas]], there is some finite subset $S_0 \subseteq expand(S)$ is contradictory. Then there exists a derivation of empty clause from $S_0$ viewed as set of propositional formulas, using propositional resolution. In other words, there exists a derivation of empty clause from $S_0$ using ground resolution rule. Each element of $S_0$ can be obtained from an element of $S$ using instantiation rule. This means that there exists a proof tree whose leaves are followed by a single application of instantiation rule, and inner nodes contain ground resolution steps. |